Programazio linealari buruzko kontzeptuak

Programazio lineal gisa ezagututako teknika matematikoa honetarako erabiltzen da: nolabaiteko murrizketen mendeko abiatze-aldagai batzuek baldintzatutako buruketa bati soluzio ezin hobea lortzeko. Programazioaren ohiko buruketa honako hau izango litzateke: A motatako n produktu eta B motatako m produktu edukita, proportzio desberdinetako bi pakete motatan ontzira daitezkeenak eta pakete bakoitzerako prezio desberdinarekin, zenbat mota bakoitzeko pakete eratu behar izango dira diru-sartze handiena erdiestekotan.

Buruketaren antolamenduan zenbait funtsezko kontzeptu erabiltzen dira:

• Aldagaiak.
• Ezartzen diren murrizketak, inekuazio linealek adierazita.
• Helburuko funtzioa, lineal motatakoa, buruketa deskribatzen duena.

Balizko soluzio multzoak murrizketa-multzoa edo soluzio egingarriko multzoa izena hartzen du. Soluzioa murrizketa-inekuazioek zehaztutako azaleran kokatu behar da. Azalera horrek eskualde egingarri gisa ezagutzen da.

Inekuazio linealen sistemaren eskualde egingarria:

Eskualde egingarria akotatuta, irudian bezala, edo akotatu gabe egon daiteke. Akotatuta egonez gero, grafikoki honela irudikatzen da: poligono gisa, murrizketen poligonoak dauzkan aldeak baino gutxiago edo berdinak izanez (irudian, akotatutako poligonoak lau alde dauzka, eta murrizketak ere lau dira).

Helburuko funtzioa maximizatu edo minimizatzen duenari esaten zaio soluzio ezin hobea. Soluzio hori bakarra bada, eskualde egingarriko erpin edo muturreko puntu batean egoten da beti.

Irudi-metodoaren bidezko ebazpena

Programazio linealaren buruketa bat irudien bidez ebazteko ondoko hau egin behar da:

• Sistemaren inekuazioak irudien bidez irudikaturik, murrizketa-multzoa lortuko da.
• Baldin eta helburuko funtzioa f (x,y)= ax + by bada, funtzio honekiko zuzen paraleloak egingo dira (ax + by=k erakoak izango direnak). Zuzenok murrizketa-multzoko erpin bakoitzetik pasatu behar dute.
• Helburuko funtzioa zein erpinetan egiten den maximoa (edo minimoa) ikusi behar izango da. Jatorrian ordenaturik, zuzenetan zeinek daukan handiena (edo txikiena) kontuan besterik ez da hartu behar.

Teknika hau mailaren zuzenen metodo gisa ezagutzen da.

Ebazteko metodo algebraikoa

Programazio linealaren buruketa bat metodo algebraikoen bidez ebazteko, honako jardunbide eraginkorra aplikatu behar izango da:

• 1. Aldagaiak zehaztuko dira.
• 2. Dagoen murrizketa bakoitzeko, ordezkari den inekuazio lineal bat idatziko da.
• 3. Helburuko funtzioaren adierazpen matematikoa zehaztuko da.
• 4. Hasierako inekuazio linealen multzoa abiapuntutzat harturik, ekuazioen sistema karratuak egingo dira. Adibidez, lau inekuazio bi ezezagunekin edukiz gero, ekuazio linealen sei sistema desberdin egin litezke (desberdintasuna berdintasunaren truke ordezkatuz).
• 5. Sistema hauek guztiok ebatzi eta lortutako puntuen balio idazten da, soluzio bezala.
• 6. Puntuok inekuazio bakoitzean egiaztatu behar dira. Murrizketa guztiak betetzen direnak eskualde egingarriko erpinak izango dira.
• 7. Erpin bakoitzerako helburuko funtzioaren balioa kalkulatuko da.
• 8. Soluzio ezin hobea helburuko funtzioa maximoa (edo minimoa, buruketaren antolamenduaren arabera) den horretarako izango da.

Teknika horrek erpinen metodoa izena hartzen du.

Soluzio motak

Bi aldagai dauzkan programazio linealen buruketetan askotariko soluzio ezin hobeak gerta daitezke:

• Soluzio bakarra.
• Era askotako soluzioa (soluzio infinituak).
• Akotatu gabeko soluzioa (soluziorik eza), helburuko funtzioak muturreko baliorik eduki ezean, eskualde egingarria akotatuta ez dago eta.
• Soluzio ez-egingarria, inekuazioen sisteman puntu komunik ez egotearen ondorioz, eskualde egingarririk egoten ez denean.
• Soluzio endekatua, baldin eta puntu bakar batean (endekatua deritzona) bat egiten badute eskualde egingarria mugatzen duten zuzenen artetik hiruk edo gehiagok.