Programozás | Programozás-elmélet » Lineáris programozási (LP) feladatok megoldása szimplex módszerrel

Lineáris programozási (LP) feladatok megoldása szimplex módszerrel A lineáris programozási feladatokban mind a célfüggvény, mind a feltételeket definiáló függvények az �1 , �2 , , �� döntési változók lineáris függvényei. A korlátozó feltételek lehetnek lineáris egyenlőség vagy egyenlőtlenség formájában megadva, és az egyes döntési változók előjelére is lehetnek megkötések. Így azonban még mindig rengeteg féle variációja lehet az LP-feladatoknak, melyekre mind különböző megoldási módszereket kellene konstruálnunk. Szerencsére a feladat optimális megoldásának létezését és meghatározását illetően elegendő egy speciális LP-feladat, az úgynevezett standard feladat vizsgálatára szorítkozni. Egy lineáris programozási feladat standard alakja alatt az alábbi módon való megadását értjük: ��̅ = �̅ (�̅ ≥ 0̅) �̅ ≥ 0̅ �̅� �̅ ��� ahol � a feltételeket definiáló

együtthatók mátrixa, �̅ a döntési változók vektora, �̅ a feltételek jobboldalán álló konstansok vektora, �̅ a célfüggvény együtthatóiból álló vektor, 0̅ zérusokból álló oszlopvektor. Általános alakú LP-feladat standard alakúra transzformálása 1. Minimumfeladat esetén a célfüggvény együtthatóinak (-1)-el való szorzásával alakítjuk át a feladatot maximumfeladattá, ugyanis az �(�) célfüggvénynek abban a pontban van minimuma, ahol a −�(�) célfüggvénynek maximuma. 2. Ha a k-adik feltétel jobboldalán álló bk konstans negatív, a teljes feltételi egyenlőség vagy egyenlőtlenség (-1)-szeresét vesszük. 3. Ha az �� döntési változóra nincs előírva a nemnegativitási feltétel, akkor ezt a változót két, újonnan bevezetett, nemnegatív változó különbségeként írjuk fel: �� = ��′ − �� ′′ alakban. Ha az �� ≤ 0 feltétel van előírva, akkor a változó ellentettjével

számolunk, az �̃� = −�� nemnegatív változó bevezetésével. 4. Ha a k-adik korlátozó feltétel ≤ típusú egyenlőtlenséggel adott akkor a feltétel baloldalához egy nemnegatív �� hiányváltozót adunk, hogy egyenlőséget kapjunk. Ha az l-edik korlátozó feltétel ≥ egyenlőtlenséggel adott, akkor egy nemnegatív � feleslegváltozó kivonásával alakítjuk a feltételt egyenlőséggé. Pivotelem-választás a szimplex táblában 1. A pivotelem csak pozitív szám lehet 2) Olyan oszlopból válasszunk pivotelemet, ahol a célfüggvény sorában pozitív elem áll. (Az ilyen elem feletti vektor bázisba hozásával növelhető a célfüggvényérték) 3) Ha eldöntöttük, hogy melyik oszlopból választunk pivotelemet, akkor az oszlopban azt az elemet válasszuk, ahol teljesül a szűk keresztmetszet kritérium, azaz az adott sorban álló jobboldali konstans és a választandó pivotelem hányadosa a lehető legkisebb. Ha a választásra több

lehetőség is adódik, akkor próbáljuk a kevesebb számolással járó változatot választani. A kétfázisú szimplex módszer A normál LP feladatok esetén (melyek csak ≤ típusú feltételeket tartalmaznak) rendelkezésünkre áll egy kiinduló, lehetséges bázismegoldás az �� hiányváltozókból, így a szimplex algoritmus a szimplex tábla felírása után azonnal elkezdhető. Az általános, standard alakban felírt LP-feladatok esetén ezt a kezdeti bázismegoldást mesterséges változók és mesterséges célfüggvény segítségével állítjuk elő a kétfázisú szimplex módszer első fázisában. A kiinduló bázismegoldás megtalálása érdekében u*-gal jelölt mesterséges változókat adunk azon feltételek baloldalához, ahol = vagy ≥ jel szerepel. A mesterséges változókra szintén megköveteljük a nemnegativitást, és bevezetünk egy z* másodlagos célfüggvényt, az u* változókat tartalmazó sorok összegeként. Először a másodlagos

célfüggvény szerint optimalizálunk, arra törekedve, hogy minden u* változó kikerüljön a bázisból. Ha ez sikerül, és a másodlagos célfüggvény optimuma 0, akkor az azt jelenti, hogy megkaptuk az eredeti feladat egy lehetséges megoldását, amelyből kiindulva a második fázisban meghatározhatjuk az eredeti feladat optimális megoldását. Ha a másodlagos célfüggvény optimuma nem 0, akkor az eredeti feladatnak nincs lehetséges megoldása, így optimális megoldása sem lehet. A továbbiakban néhány normál és általános LP feladat szimplex algoritmussal történő részletes megoldását közöljük. A feladatgyűjtemény szöveges példákat is tartalmaz, így az LP feladatok modelljének felírását is gyakorolhatja az olvasó. A feladatok egy részének forrása Dr. Nagy Tamás Operációkutatás c egyetemi jegyzete. A feladatok mellett megjelöltük az oldalszámot és a példa betűjelét 1. feladat (157a) 2�1 + �2 ≤ 2 − �1 + �2 ≤ 1

�1 , �2 ≥ 0 2�1 + 6�2 ��� Ez egy normál feladat, azaz a szimplex tábla már tartalmaz egy kezdeti bázismegoldást (u1 =2, u2 =1). Az x2 oszlopában kezdjük a pivotálást, mert ott biztosan 1 a pivotelem. u1 u2 -z x1 2 -1 2 x2 1 1 6 b 2 1 0 Most csak egyféleképpen választhatunk pivotelemet. u1 x2 -z x1 3 -1 8 u2 -1 1 -6 b 1 1 -6 x1 x2 -z u1 1/3 1/3 -8/3 u2 - 1/3 2/3 -10/3 b 1/3 4/3 -26/3 1 4 Optimális táblát kaptunk, az optimális megoldás: �1 = 3; �2 = 3. A célfüggvény maximuma: � = 26 . 3 2. feladat (157k) �1 + 2 �2 + 4�3 − �4 ≤ 6 −�3 + �4 ≤ 12 �1 + �3 + �4 ≤ 4 �1 , �2 , �3 , �4 ≥ 0 2�1 + �2 − 3�3 + 5�4 ��� A szimplex táblában érdemes a pivotálást x2 oszlopában kezdeni, mert két nullát is tartalmaz az egyetlen lehetséges pivotelem mellett, így kevesebb számolásra van szükség (a nullák sorai változatlanok maradnak). u1 u2 u3 -z x1 1 0 1 2 x2 2 0 0 1 x3 4

-1 1 -3 x4 -1 1 1 5 b 6 12 4 0 A következő lépésben x1 vagy x4 hozható a bázisba, u3 helyett. Az x4 választása azonban kedvezőbb, mert így rögtön optimális táblát kapunk. x2 u2 u3 -z x1 0,5 0 1 1,5 u1 0,5 0 0 -0,5 x3 2 -1 1 -5 x4 -0,5 1 1 5,5 b 3 12 4 -3 u1 0,5 0 0 -0,5 x3 2,5 -2 1 -10,5 u3 0,5 -1 1 -5,5 b 5 8 4 -25 Az optimális tábla: x2 u2 x4 -z x1 1 -1 1 -4 Az optimális megoldás: �1 = 0; �2 = 5; �3 = 0; �4 = 4. A célfüggvény maximuma: � = 25. 3. feladat (157h) �1 + �2 ≤ 3 0 ≤ �1 ≤ 2 0 ≤ �2 ≤ 2 �1 + �2 ��� A feladatban szereplő változók felülről is konstans korláttal rendelkeznek. Az egyedi korlátok kezelésére léteznek különböző módszerek, de a felső korlátokat külön feltételbe is foglalhatjuk a feladat átfogalmazásával: �1 + �2 ≤ 3 �1 ≤2 �2 ≤ 2 �1 , �2 ≥ 0 �1 + �2 ��� Így egy normál feladatot kaptunk, melynek szimplex táblája az alábbi: u1 u2

u3 -z x1 1 1 0 1 x2 1 0 1 1 b 3 2 2 0 Először az x1 változót hozzuk a bázisba: u1 x1 u3 -z u2 -1 1 0 -1 x2 1 0 1 1 b 1 2 2 -2 u1 1 0 -1 -1 b 1 2 1 -3 Majd az x2 változót: x2 x1 u3 -z u2 -1 1 1 0 A célfüggvény sora már nem tartalmaz pozitív elemet, így a táblázatból kiolvasható megoldás ( �1 = 2; �2 = 1) a feladat egy optimális megoldása. A célfüggvény sorában szereplő 0 érték azonban azt jelenti, hogy alternatív optimum van. Valóban, ha az u2 változót bevisszük a bázisba az u3 változó helyett, az alábbi táblázatot kapjuk: x2 x1 u2 -z u3 1 -1 1 0 u1 0 1 -1 -1 b 2 1 1 -3 Ebből látható, hogy a feladat egy másik optimális megoldása: �1 = 1; �2 = 2. Valójában a feladatnak végtelen sok optimális megoldása van, a két feltárt megoldást összekötő szakasz pontjai. Ezt a szakaszt a két végpont konvex lineáris kombinációjaként adhatjuk meg, a következő módon: �(1; 2) + (1 − �)(2; 1) ahol � ∈ [0;

1] A maximum értéke minden optimális megoldás esetén: � = 3. 4. feladat �2 + �3 ≤ 160 −�1 + �2 + �3 = 100 �1 + �2 + �3 ≥ 180 �1 , �2 , �3 ≥ 0 2�1 + 6�2 + 2�3 ��� Általános feladatról van szó, hiszen egyenlőség és ≥ típusú egyenlőtlenség is van a feltételek között. Ez utóbbi feltétel miatt szükségünk van egy v3 segédváltozóra a standard alakra hozáshoz. Kétfázisú szimplex módszert alkalmazunk, az első fázishoz a második és a harmadik feltétel miatt két mesterséges változót vezetünk be. A szimplex táblában az első átalakítás az x2 változó bázisba vitele: u1 u2* u3* -z z* x1 0 -1 1 2 0 x2 1 1 1 6 2 x3 1 1 1 2 2 v3 0 0 -1 0 -1 b 160 100 180 0 280 Ezután az x1 változó következik: u1 x2 u3* -z z* x1 1 -1 2 8 2 u2* -1 1 -1 -6 -2 x3 0 1 0 -4 0 v3 0 0 -1 0 -1 b 60 100 80 -600 80 Ezzel az átalakítással vége az első fázisnak, mert a mesterséges célfüggvény értéke 0

lett. A továbbiakban nincs szükség a mesterséges célfüggvény sorára (valójában a mesterséges változók oszlopait is törölhetjük), az eredeti célfüggvény alapján pivotálunk tovább, a v3 változót visszük a bázisba. u1 x2 x1 -z z* u3* - 1/2 1/2 1/2 -4 -1 u2* - 1/2 1/2 - 1/2 -2 -1 x3 0 1 0 -4 0 v3 1/2 - 1/2 - 1/2 4 0 b 20 140 40 -920 0 v3 x2 x1 -z x3 0 1 0 -4 u1 2 1 1 -8 b 40 160 60 -1080 A tábla optimális. Az optimális megoldás: �1 = 60; �2 = 160; �3 = 0. A célfüggvény maximuma: � = 1080. 5. feladat (158t) 2�1 + 6�2 + �3 + �4 ≤ 30 �1 + 2�2 + �3 = 10 −�1 + �2 − �3 + �4 ≥ 4 �1 , �2 , �3 , �4 ≥ 0 �1 + 2�2 − 13�3 + 4�4 ��� Általános feladatról van szó, hiszen egyenlőség és ≥ típusú egyenlőtlenség is van a feltételek között. Ez utóbbi feltétel miatt szükségünk van egy v3 segédváltozóra a standard alakra hozáshoz. Kétfázisú szimplex módszert

alkalmazunk, az első fázishoz a második és a harmadik feltétel miatt két mesterséges változót vezetünk be. A szimplex táblában először az x4 változó szerint pivotálunk, mert 1 a megfelelő pivotelem és 0 is van a pivotelem oszlopában. u1 u2* u3* -z z* x1 2 1 -1 1 0 x2 6 2 1 2 3 x3 1 1 -1 -13 0 x4 1 0 1 4 1 v3 0 0 -1 0 -1 b 30 10 4 0 14 Ezután az x3 változót visszük a bázisba, mert szintén 1 a pivotelem, és két 0 is van a sorában. u1 u2* x4 -z z* x1 3 1 -1 5 1 x2 5 2 1 -2 2 x3 2 1 -1 -9 1 u3* -1 0 1 -4 -1 v3 1 0 -1 4 0 b 26 10 4 -16 10 Ezzel az első fázis véget ért, mert a mesterséges célfüggvény értéke 0. u1 x3 x4 -z z* x1 1 1 0 14 0 x2 1 2 3 16 0 u2* -2 1 1 9 -1 u3* -1 0 1 -4 -1 v3 1 0 -1 4 0 b 6 10 14 74 0 Elhagyjuk a mesterséges célfüggvény sorát, valamint a mesterséges változók oszlopait. x1 oszlopában választunk pivotelemet u1 x3 x4 -z x1 1 1 0 14 x2 1 2 3 16 v3 1 0 -1 4 b 6 10 14 74 v3 1 -1 -1 -10 b 6

4 14 -10 v3 2 -1 2 -8 b 2 4 2 -18 Ezután x2-t visszük a bázisba: x1 x3 x4 -z u1 1 -1 0 -14 x2 1 1 3 2 A kapott tábla optimális. x1 x2 x4 -z u1 2 -1 3 -12 x3 -1 1 -3 -2 Az optimális megoldás: �1 = 2; �2 = 4; �3 = 0; �4 = 2. A célfüggvény maximuma: � = 18. 6. feladat (157f) �1 + �3 − �4 = 30 2�1 − 3�2 + �3 + 2�4 ≤ 250 4�1 + 2�2 + 2�3 + �4 ≥ 125 �1 , �3 , �4 ≥ 0; �2 ≤ 0 5�1 − 4�2 + 8�3 + 7�4 ��� A standard alakra hozáshoz a harmadik egyenlőtlenségi feltétel miatt szükségünk van egy v3 segédváltozóra, valamint az x2 változó helyett mindenütt a (-1)-szeresével számolunk. Az első és a harmadik feltétel miatt két mesterséges változót vezetünk be Mivel minimumfeladatról van szó, a célfüggvény együtthatóinak (-1)-szeresét írjuk a táblázatba. A szimplex tábla alakja a következő: x1 x2 x3 x4 u1* 1 0 1 -1 u2 2 3 1 2 u3* 4 -2 2 1 -z -5 -4 -8 -7 z* 5 -2 3 0 Először az

x1 változót visszük a bázisba. v3 0 0 -1 0 -1 b 30 250 125 0 155 u1* x2 x3 x4 x1 1 0 1 -1 u2 -2 3 -1 4 u3* -4 -2 -2 5 -z 5 -4 -3 -12 z* -5 -2 -2 5 Most x4 oszlopából kell pivotelemet választani. v3 0 0 -1 0 -1 b 30 190 5 150 5 u1* x2 x3 u3* v3 b x1 0,2 -0,4 0,6 0,2 -0,2 31 u2 1,2 4,6 0,6 -0,8 0,8 186 x4 -0,8 -0,4 -0,4 0,2 -0,2 1 -z -4,6 -8,8 -7,8 2,4 -2,4 162 z* -1 0 0 -1 0 0 Az első fázis véget ért, és egyúttal a második is. A tábla optimális Az optimális megoldás: �1 = 31; �2 = 0; �3 = 0; �4 = 1. A célfüggvény minimuma: � = 162. 7. feladat (158o) �1 + 4�2 + �3 + 2�4 ≤ 90 3�2 + �4 ≤ 50 �1 + 2�2 + 2�4 = 60 �1 + �3 = 80 �1 , �2 , �3 , �4 ≥ 0 4�1 + 2�2 + �3 + 9�4 ��� A két egyenlőségi feltétel miatt két mesterséges változót vezetünk be. A szimplex táblában először az x1 változó szerint pivotálunk. u1 u2 u3* u4* -z z* x1 1 0 1 1 4 2 x2 4 3 2 0 2 2 x3 1 0 0 1 1 1 x4 2 1 2

0 9 2 b 90 50 60 80 0 140 x3 1 0 0 1 1 1 x4 0 1 2 -2 1 -2 b 30 50 60 20 -240 20 u4* -1 0 0 1 -1 -1 x4 2 1 2 -2 3 0 b 10 50 60 20 -260 0 Ezután az x3 változót visszük a bázisba. u1 u2 x1 u4* -z z* u3* -1 0 1 -1 -4 -2 x2 2 3 2 -2 -6 -2 Ezzel az első fázis véget ért: u1 u2 x1 x3 -z z* u3* 0 0 1 -1 -3 -1 x2 4 3 2 -2 -4 0 A mesterséges célfüggvény sorát, valamint a mesterséges változók oszlopait elhagyhatjuk: u1 u2 x1 x3 -z x2 4 3 2 -2 -4 x4 2 1 2 -2 3 b 10 50 60 20 -260 Az x4 változó bázisba hozásával optimális táblát kapunk: x4 u2 x1 x3 -z x2 2 1 -2 2 -10 u1 0,5 -0,5 -1 1 -1,5 b 5 45 50 30 -275 Az optimális megoldás: �1 = 50; �2 = 0; �3 = 30; �4 = 5. A célfüggvény maximuma: � = 275. 8. feladat (159z) �1 + 2�2 = 5 −�1 + 5�2 ≥ 3 4�1 + 7�2 ≤ 8 �1 tetszőleges, �2 ≥ 0 5�1 + 6�2 ��� Az �1 változóra nincs előjelmegkötés, ezért két nemnegatív változó különbségeként írjuk

fel: �1 = �1′ − �1′′ , ( �1′ ≥ 0 , �1′′ ≥ 0). Az új változók bevezetése után a feladat alakja: �1′ − �1′′ + 2�2 = 5 −�1′ + �1′′ + 5�2 ≥ 3 4�1′ − 4 �1′′ + 7�2 ≤ 8 �1′ , �1′′ , �2 ≥ 0 5�1′ − 5 �1′′ + 6�2 ��� A standard alakra hozáshoz a második egyenlőtlenségi feltétel miatt szükségünk van egy v2 segédváltozóra. Az első és a második feltétel miatt két mesterséges változót vezetünk be. A szimplex módszer lépései az alábbiak: u1* u2* u3 -z z* x1 1 -1 4 5 0 x1 -1 1 -4 -5 0 x2 2 5 7 6 7 v2 0 -1 0 0 -1 b 5 3 8 0 8 u1* x2 u3 -z z* x1 1,4 -0,2 5,4 6,2 1,4 x1 -1,4 0,2 -5,4 -6,2 -1,4 u2* -0,4 0,2 -1,4 -1,2 -1,4 v2 0,4 -0,2 1,4 1,2 0,4 b 3,8 0,6 3,8 -3,6 3,8 u1* x2 v2 -z z* x1 - 1/7 4/7 27/7 11/7 - 1/7 x1 1/7 - 4/7 -27/7 -11/7 1/7 u2* 0 0 -1 0 -1 u3 - 2/7 1/7 5/7 - 6/7 - 2/7 b 19/7 8/7 19/7 -48/7 19/7 x1 x2 v2 -z z* x1 -1 0 0 0 0 u1* 7 4

27 11 -1 u2* 0 0 -1 0 -1 u3 -2 -1 -7 -4 0 b 19 12 76 23 0 Az első fázis véget ért, és egyúttal a második is (a célfüggvény értéke nem javítható tovább). A tábla optimális Az optimális megoldás: �1′ = 0; �1′′ = 19 és ezért �1 = 0 − 19 = −19; �2 = 12. A célfüggvény maximuma: � = −23. 9. feladat (157b) �1 − 2�2 + �3 ≤ 8 3�1 + �2 ≤ −18 2�1 + �2 − 2 �3 ≤ −4 �1 , �2 , �3 ≥ 0 2�1 + �2 − 5�3 ��� A standard alakú LP feladat jobboldalán nem állhatnak negatív számok, ezért a második és harmadik feltételt (-1)-gyel végig kell szoroznunk. A feladat új alakja: �1 − 2�2 + �3 ≤ 8 −3�1 − �2 ≥ 18 −2�1 − �2 + 2 �3 ≥ 4 �1 , �2 , �3 ≥ 0 2�1 + �2 − 5�3 ��� A szimplex tábla két mesterséges változót tartalmaz a második és harmadik feltétel miatt, valamint be kell vezetnünk a v2 és v3 változókat is a standard alakra

hozáshoz. Az induló szimplex tábla: x1 x2 x3 v2 v3 b u1 1 -2 1 0 0 8 u2* -3 -1 0 -1 0 18 u3* -2 -1 2 0 -1 4 -z 2 1 -5 0 0 0 z* -5 -2 2 -1 -1 22 Egyedül az x3 változóval kezdhetjük a pivotálást. Az alábbi táblát kapjuk: u1 u2* x3 -z z* x1 2 -3 -1 -3 -3 x2 -1,5 -1 -0,5 -1,5 -1 u3* -0,5 0 0,5 2,5 -1 v2 0 -1 0 0 -1 v3 0,5 0 -0,5 -2,5 0 b 6 18 2 10 18 Mivel z* sorában nincs pozitív szám, a mesterséges célfüggvény értékét nem tudjuk 0-ra levinni. Ez azt jelenti, hogy a feladatnak nincs nemnegatív bázismegoldása (amit az első fázis végeztével kapnánk), így optimális megoldás sincs. 10. feladat (157d) 8�1 + �2 ≥ 8 2�1 + �2 ≥ 6 �1 + 3�2 ≥ 6 �1 + 6�2 ≥ 8 �1 , �2 ≥ 0 3�1 + 2�2 ��� Mind a négy feltétel ≥ típusú, ezért a standard alakra hozáshoz minden feltételi sorból ki kell vonnunk egy v változót. A feladatot két fázisban oldjuk meg, minden feltételhez hozzá kell adnunk egy mesterséges u*

változót. Mivel minimumfeladatról van szó, a célfüggvény (-1)-szeresével számolunk. Az egymás után számított szimplex táblák az alábbiak: u1* u2* u3* u4* -z z* x1 8 2 1 1 -3 12 x2 1 1 3 6 -2 11 v1 -1 0 0 0 0 -1 v2 0 -1 0 0 0 -1 v3 0 0 -1 0 0 -1 v4 0 0 0 -1 0 -1 b 8 6 6 8 0 28 x1 u2* u3* u4* -z z* u1* 0,125 -0,25 -0,125 -0,125 0,375 -1,5 x2 0,125 0,75 2,875 5,875 -1,625 9,5 v1 -0,125 0,25 0,125 0,125 -0,375 0,5 v2 0 -1 0 0 0 -1 v3 0 0 -1 0 0 -1 v4 0 0 0 -1 0 -1 b 1 4 5 7 3 16 x1 v1 u3* u4* -z z* u1* 0 -1 0 0 0 -1 x2 0,5 3 2,5 5,5 -0,5 8 u2* 0,5 4 -0,5 -0,5 1,5 -2 v2 -0,5 -4 0,5 0,5 -1,5 1 v3 0 0 -1 0 0 -1 v4 0 0 0 -1 0 -1 b 3 16 3 5 9 8 x1 v1 v2 u4* -z z* u1* 0 -1 0 0 0 -1 x2 3 23 5 3 7 3 u2* 0 0 -1 0 0 -1 u3* 1 8 2 -1 3 -2 v3 -1 -8 -2 1 -3 1 v4 0 0 0 -1 0 -1 b 6 40 6 2 18 2 x1 v1 v2 x2 -z z* u1* 0 -1 0 0 0 -1 u4* -1 -23/3 -5/3 1/3 -7/3 -1 u2* 0 0 -1 0 0 -1 u3* 2 47/3 11/3 - 1/3 16/3 -1 v3 -2 -47/3 -11/3 1/3 -16/3 0 v4 1 23/3 5/3

- 1/3 7/3 0 b 4 74/3 8/3 2/3 40/3 0 Az első fázis végére értünk, töröljük a mesterséges változókat. Még szükség van a v4 és v2 változók cseréjére. x1 v1 v4 x2 -z v3 0,2 1,2 -2,2 -0,4 -0,2 v2 -0,6 -4,6 0,6 0,2 -1,4 b 2,4 12,4 1,6 1,2 9,6 Optimális táblát kaptunk, az optimális megoldás: �1 = 2,4; �2 = 1,2. A célfüggvény minimuma: � = 9,6. 11. feladat (159w) �1 + 2�2 + �3 −3�4 = 12 �1 + 3�2 + 2�3 − 5�4 = 13 �1 , �2 , �3 , �4 ≥ 0 6�1 + 7�2 + 8�3 − 14�4 ��� A két egyenlőségi feltétel miatt két mesterséges változóval számolunk az első fázisban. Mivel minimumfeladatról van szó, a célfüggvény (-1)-szeresét írjuk a táblázatba. x1 x2 x3 x4 b u1* 1 2 1 -3 12 u2* 1 3 2 -5 13 -z -6 -7 -8 14 0 z* 2 5 3 -8 25 Az x1 változóval kezdjük a bázisvektorcseréket, mert így 1 a pivotelem. u1* x2 x1 1 2 u2* -1 1 -z 6 5 z* -2 1 Ezután x2-t hozzuk a bázisba. x3 1 1 -2 1 x4 -3 -2 -4 -2 b 12 1

72 1 u1* u2* x3 x4 b x1 3 -2 -1 1 10 x2 -1 1 1 -2 1 -z 11 -5 -7 6 67 z* -1 -1 0 0 0 Az első fázis véget ért, de a tábla még nem optimális. x4-et kell a bázisba hozni A bázisvektorcsere és a mesterséges változók törlése után az alábbi, optimális táblát kaptuk: x4 x2 -z x3 -1 -1 -1 x1 1 2 -6 b 10 21 7 Az optimális megoldás: �1 = 0; �2 = 21; �3 = 0; �4 = 10. A célfüggvény minimuma: � = 7. 12. feladat �1 + �2 + 4�3 ≥ 10 �1 + 3�2 + �3 = 8 �1 , �2 , �3 ≥ 0 �1 + 2�2 + �3 ��� Az első feltétel miatt beiktatjuk a v1 feleslegváltozót. Két mesterséges változóra van szükség a szimplex módszer első fázisához. Mivel minimumfeladatról van szó, a célfüggvény (-1)-szeresét írjuk az induló táblázatba. x1 x2 x3 v1 b u1* 1 1 4 -1 10 u2* 1 3 1 0 8 -z -1 -2 -1 0 0 z* 2 4 5 -1 18 A pivotálást x1-el kezdjük, hogy 1 legyen a pivotelem. u2* x2 x3 v1 u1* -1 -2 3 -1 x1 1 3 1 0 -z 1 1 0 0 z* -2 -2 3 -1 Most

csak az x3 változót hozhatjuk a bázisba. b 2 8 8 2 u2* x2 u1* v1 b x3 - 1/3 - 2/3 1/3 - 1/3 2/3 x1 4/3 11/3 - 1/3 1/3 22/3 -z 1 1 0 0 8 z* -1 0 -1 0 0 Az első fázis végére értünk. Töröljük a mesterséges változókat és folytatjuk a pivotálást az x2 változó bázisba vitelével. x3 x1 -z x2 - 2/3 11/3 1 v1 - 1/3 1/3 0 b 2/3 22/3 8 x1 v1 x3 2/11 - 3/11 x2 3/11 1/11 -z - 3/11 - 1/11 Az optimális megoldás: �1 = 0; b 2 2 6 �2 = 2; �3 = 2. A célfüggvény minimuma: � = 6. 13. feladat �1 + 2�2 + �3 = 16 �1 + �2 + 2 �3 ≤ 17 �1 , �2 , �3 ≥ 0 �1 − �2 + 3�3 ��� Az egyenlőségi feltétel miatt szükségünk van egy mesterséges változóra. Az induló szimplex tábla az alábbi alakú: x1 x2 x3 b u1* 1 2 1 16 u2 1 1 2 17 -z 1 -1 3 0 z* 1 2 1 16 Az x1 változót hozzuk be először a bázisba, amivel a szimplex módszer első fázisa véget is ér. x1 u2 -z z* u1* 1 -1 -1 -1 x2 2 -1 -3 0 x3 1 1 2 0 b 16 1 -16 0

Töröljük a mesterséges változókat és folytatjuk a pivotálást az x3 változó bázisba vitelével. x1 u2 -z x2 2 -1 -3 x3 1 1 2 b 16 1 -16 Optimális táblát kaptunk: x1 x3 -z x2 3 -1 -1 u2 -1 1 -2 b 15 1 -18 Az optimális megoldás: �1 = 15; �2 = 0; �3 = 1. A célfüggvény maximuma: � = 18. 14. feladat 2�1 + �2 ≥1 �1 + �2 − �3 ≥ 3 −�1 + 2�3 ≥ 2 �1 , �2 , �3 ≥ 0 10�1 + 6�2 + 16�3 ��� Ha észrevesszük, hogy a feladat duálisa egy normál feladat, akkor nincs szükség a kétfázisú szimplex módszerre. A duális probléma: 2�1 + �2 − �3 ≤ 10 �1 + �2 ≤6 −�2 + 2�3 ≤ 16 �1 , �2 , �3 ≥ 0 �1 + 3�2 + 2�3 ��� Az induló szimplex tábla: x1 x2 x3 b u1 2 1 -1 10 u2 1 1 0 6 u3 0 -1 2 16 -z 1 3 2 0 Az x2 változót hozzuk először a bázisba. x1 u2 x3 b u1 1 -1 -1 4 x2 1 1 0 6 u3 1 1 2 22 -z -2 -3 2 -18 Az x3 változó behozásával optimális táblát kapunk: x1 u2 u3

b u1 1,5 -0,5 0,5 15 x2 1 1 0 6 x3 0,5 0,5 0,5 11 -z -3 -4 -1 -40 A duális feladat optimális megoldása: �1 = 0; �2 = 6; �3 = 11. Az eredeti (primál) feladat optimális megoldását a célfüggvény sorában találhatjuk, az ui változók alatt, ellenkező előjellel: �1 = 0; �2 = 4; �3 = 1. Az optimális célfüggvényérték mindkét feladat esetében: � = 40. 15. feladat 3�1 + 2�2 −4�3 = 16 −2�1 − �2 + �3 = 12 �1 + �3 = 4 �1 , �2 , �3 , �4 ≥ 0 3�1 + 4�2 + 2�3 ��� A három feltételi egyenletből álló egyenletrendszernek vagy végtelen sok megoldása van, vagy egyértelmű megoldása van, vagy nincs megoldása. Az utóbbi esetben az LP feladatnak sincs optimális megoldása. Ha az egyenletrendszernek egyetlen megoldása van, és egyúttal teljesülnek a változókra rótt nemnegativitási feltételek, akkor ez a megoldás egyben az LP feladat optimális megoldása is. Ha viszont végtelen sok megoldás van, akkor

kétfázisú szimplex módszerrel tudjuk meghatározni ezek közül az optimálisat. Bízva abban, hogy szimplex módszer nélkül is meg tudjuk oldani az LP feladatot, először, bázistranszformációs technikával megoldjuk az egyenletrendszert. Ilyenkor az a cél, hogy egyenként vigyük be a bázisba a változókat. A pivotelem tetszőleges, 0-tól különböző szám lehet. u1 u2 u3 x1 3 -2 1 x2 2 -1 0 x3 -4 1 1 b 16 12 4 u1 u2 x1 u3 -3 2 1 x2 2 -1 0 x3 -7 3 1 b 4 20 4 u1 x2 x1 u3 1 -2 1 u2 2 -1 0 x3 -1 -3 1 b 44 -20 4 u3 u2 u1 b x3 -1 -2 -1 -44 x2 -5 -7 -3 -152 x1 2 2 1 48 A lineáris egyenletrendszernek egyértelmű megoldása van: �1 = 48; �2 = −152; �3 = −44. A megoldás azonban negatív értékeket is tartalmaz, így az eredeti LP feladatnak nincs lehetséges megoldása és optimális megoldása se. 16. feladat Egy anyuka gyermeke születésnapi zsúrjára kétféle szendvicset készít. Egy szalámis szendvicsre 3 gramm vajat, 3 karika tojást

és 2 szelet szalámit tesz. A sonkás szendvicshez 4 gramm vaj, 2 karika tojás és 1 szelet sonka szükséges. A szendvicsek készítéséhez rendelkezésre áll 100 szelet szalámi, 40 szelet sonka, 170 karika tojás és 220 gramm vaj (kenyérszeletből nincs korlátozás, abból elegendően sok van). Melyik szendvicsből hány darabot kell készítenie az anyukának, ha azt akarja, hogy a rendelkezésre álló készletekből összességében a lehető legtöbb szendvics készüljön el? Megoldás: Írjuk fel a feladat matematikai modelljét, vagyis alkalmas változók bevezetése után adjuk meg a célfüggvény egyenletét, illetve a korlátozó feltételeket leíró egyenlőtlenségeket! Tegyük fel, hogy az elkészítendő szalámis szendvicsek száma �1 , a sonkás szendvicsek száma pedig �2 . Vajból a szalámis szendvicsekre 3�1 , a sonkás szendvicsekre 4�2 gramm kerül összesen, mivel azonban csak 220 gramm vaj van, fenn kell állnia a 3�1 + 4�2 ≤ 220

egyenlőtlenségnek. Hasonlóan, a felhasznált tojáskarikák száma 3�1 + 2�2 , mely összeg legfeljebb 170 lehet. a szalámiszeletekre a 2�1 ≤ 100, a sonkaszeletekre az �2 ≤ 40 reláció érvényes Továbbá, egyik változó sem lehet negatív, azaz �1 ≥ 0 és �2 ≥ 0. E feltételek teljesülése mellett keressük az �1 + �2 összeg maximumát. Tehát a feladat matematikai modellje az alábbi kétváltozós LP feladat: 3�1 + 4�2 ≤ 220 3�1 + 2�2 ≤ 170 2�1 ≤ 100 �2 ≤ 40 �1 , �2 ≥ 0 �1 + �2 ��� Ez egy normál feladat, melynek induló szimplex táblája az alábbi: x1 x2 b u1 3 4 220 u2 3 2 170 u3 2 0 100 u4 0 1 40 -z 1 1 0 Először x2 -t hozzuk a bázisba, majd két további pivotálás után optimális táblát kapunk. x1 u4 b u1 3 -4 60 u2 3 -2 90 u3 2 0 100 x2 0 1 40 -z 1 -1 -40 x1 u2 u3 x2 -z u1 1/3 -1 - 2/3 0 - 1/3 u4 -4/3 2 8/3 1 1/3 b 20 30 60 40 -60 x1 u4 u3 x2 -z u1 - 1/3 - 1/2 2/3 1/2 - 1/6 u2 2/3 1/2

-4/3 - 1/2 - 1/6 b 40 15 20 25 -65 Az optimális megoldás: �1 = 40; �2 = 25; ���� = 65. Tehát a rendelkezésre álló készletekből összesen legfeljebb 65 szendvics készíthető, melyből 40 szalámis, 25 pedig sonkás. 17. feladat Egy fogyókúrázó napi C-vitamin és vas szükségletét kétféle gyümölcs, citrom és alma fogyasztásával szeretné fedezni. Tegyük fel, hogy a napi C-vitamin szükséglet 500 egység, és 100 gramm citromban 300 egységnyi, 100gramm almában 100 egységnyi C-vitamin van. Vasból 1,2 mg a napi szükséglet, és 100 gramm citrom 0,2 mg, 100 gramm alma pedig 0,5 mg vasat tartalmaz. A fogyókúrázó a gyümölcsök fogyasztásával legfeljebb 400 kalóriát szeretne bevinni. 100 gr citromban 50, 100 gr almában 80 kalória van. A piacon egy kiló citrom 600 forintba, egy kiló alma 400 forintba kerül. Mennyit vegyen az egyes gyümölcsökből, ha azt szeretné, hogy a lehető legkevesebbet költsön, ne lépje túl az előírt

kalóriamennyiséget, de a napi C-vitamin és vasszükségletét fedezze a megvásárolt gyümölcs? Megoldás: Tegyük fel, hogy a fogyókúrázó �1 ∙ 100 gramm citromot és �2 ∙ 100 gramm almát vásárol a piacon. Ekkor 60�1 + 40�2 a fizetendő összeg, ezt kell minimalizálni. Mindkét változó nemnegatív, és a feladat feltételeiből három további egyenlőtlenséget tudunk felírni korlátozó feltételként. A feladat modellje: 300�1 + 100�2 ≥ 500 0,2�1 + 0,5�2 ≥ 1,2 50�1 + 80�2 ≤ 400 �1 , �2 ≥ 0 60�1 + 40�2 ��� A feladatot kétfázisú szimplex módszerrel oldjuk meg. Az induló szimplex tábla: u1* u2* u3 -z z* x1 300 0,2 50 -60 300,2 x2 100 0,5 80 -40 100,5 v1 -1 0 0 0 -1 v2 0 -1 0 0 -1 b 500 1,2 400 0 501,2 v2 200 -2 160 -80 200 b 260 2,4 208 96 260 Az x2 vektort bevisszük a bázisba: u1* x2 u3 -z z* x1 260 0,4 18 -44 260 Majd az x1 vektort is: u2* -200 2 -160 80 -201 v1 -1 0 0 0 -1 x1 x2 u3 -z z* u1*

0,0038 -0,002 -0,069 0,1692 -1 u2* v1 v2 -0,7692 -0,004 0,76923 2,30769 0,0015 -2,30769 -146,15 0,0692 146,154 46,1538 -0,169 -46,1538 -1 0 0 b 1 2 190 140 0 A szimplex módszer első fázisa véget ért, hiszen a mesterséges célfüggvény értéke 0. Ha töröljük a mesterséges célfüggvény sorát, valamint a mesterséges változók oszlopait, az alábbi táblát kapjuk: x1 x2 u3 -z v1 v2 -0,004 0,76923 0,0015 -2,30769 0,0692 146,154 -0,169 -46,1538 b 1 2 190 140 A tábla optimális, a feladat optimális megoldása: �1 = 1; �2 = 2; ���� = 140. Tehát 100 gr citromot és 200 gr almát kell vásárolni a feltételek teljesüléséhez, és ez 140 Ft-ba fog kerülni. 18. feladat Egy építési vállalkozó kétféle üzemcsarnok építésével foglalkozik. Az A típusú csarnok 4000 m2 lemez, 4 tonna acél, 300 m2 tetőfedő anyag és 200 m3 beton felhasználásával készül el. A B típusú csarnok felépítéséhez 5000 m 2 lemez, 3 tonna acél, 200 m2

tetőfedő anyag és 100 m3 beton szükséges. Az alapanyagok csak korlátozott mennyiségben állnak rendelkezésre: 32000 m2 lemez, 24 tonna acél, 2000 m2 tetőfedő anyag és 1600 m3 beton használható fel az adott szezonban. Egy A típusú csarnok felépítése 4000 $, a B típusú csarnok felépítése 5000 $ nyereséget hoz. Milyen összetételben vállaljon a kétféle csarnokra vonatkozó megrendelésekből a vállalkozó, ha maximalizálni szeretné a nyereségét? Megoldás: Jelölje �1 a felépítendő A típusú csarnokok számát, �2 pedig a B típusúak számát. A feladat az alábbi rendszerrel modellezhető: 4000�1 + 5000�2 ≤ 32000 4�1 + 3�2 ≤ 24 300�1 + 200�2 ≤ 2000 200�1 + 100�2 ≤ 1600 �1 , �2 ≥ 0 4000�1 + 5000�2 ��� Normálfeladatról van szó, két pivotálás után optimális megoldáshoz jutunk: x1 x2 u1 u2 u3 u4 -z 4000 4 300 200 4000 5000 3 200 100 5000 b 32000 24 2000 1600 0 u1 x1 u3 u4 -z u2 -1000 0,25 -75

-50 -1000 x2 2000 0,75 -25 -50 2000 b 8000 6 200 400 -24000 x2 x1 u3 u4 -z u2 -0,5 0,625 -87,5 -75 0 u1 b 0,0005 4 -0,0004 3 0,0125 300 0,025 600 -1 -32000 A célfüggvény sorában szereplő 0 azonban azt jelenti, hogy alternatív optimum esete áll fenn, azaz a feladatnak végtelen sok optimális megoldása van. Az u2 vektor bázisba hozásával az alábbi táblát kapjuk: x2 u2 u3 u4 -z x1 0,8 1,6 140 120 0 u1 b 0,0002 6,4 -0,0006 4,8 -0,04 720 -0,02 960 -1 -32000 A két utolsó táblából leolvashatjuk az optimális megoldások szakaszának végpontjait. Az összes optimális megoldás a végpontok konvex lineáris kombinációja: �(3; 4) + (1 − �)(0; 6,4) ahol � ∈ [0; 1] A maximális bevétel minden optimális megoldás esetén: � = 32000 $. Megjegyzés: A feladat jellegéből adódóan egészértékű megoldást keresünk elsősorban, ezért a kérdéses szakaszon azt a pontot adjuk meg megoldásként, melynek mindkét koordinátája egész, azaz a (3;4)

pontot. Tehát 3 db A típusú és 4 db B típusú csarnokot kell építeni, s így 32000 $ lesz a nyereség. Ugyanígy 32000 $ lenne a nyereség, ha a szakasz egy másik pontját, például a (2;4,8) pontot választanánk. Ez a megoldás értelmezhető úgy, hogy a vállalkozó felépít 2 A típusú csarnokot, s a vállalt 5 B típusúból négyet teljesen, egyet pedig 80%-os készültségben ad át. Ekkor a nyeresége is csak 80%-os, azaz 4000 $ az utolsó csarnokon. Az egészértékű megoldások keresése az integer programozás tárgykörébe tartozik, és általában nehezebb problémát jelent, mint az általános megoldás meghatározása. 19. feladat A távoli jövőben az optimalizálás vizsgára különböző ízesítésű tudástabletták bevételével is fel lehet készülni. Egy spenótos tabletta elfogyasztása 10%-kal, egy eperízű tabletta elfogyasztása 7 %-kal növeli meg a hallgató tudását. (Tehát 4 spenótos és 5 epres tabletta esetén a tananyag

75%-ának lennénk birtokában). Egy spenótos tabletta 2000, egy eperízű tabletta 1500 forintba kerül. A túladagolás elkerülése érdekében a két tablettából összesen legfeljebb 8 darab vehető be, és arra is ügyelnünk kell, hogy legalább annyi eprest vegyünk be, mint spenótost (az utóbbi nem túl kellemes íze miatt). Milyen összetételben vásároljunk a tablettákból, ha a lehető legkevesebbet szeretnénk költeni és 51% a sikeres vizsga teljesítésének feltétele? Megoldás: Jelölje �1 a megvásárlandó spenótos, �2 pedig az eperízű tabletták számát. Az �1 ≤ �2 feltételben egy oldalra rendezve a változókat, az alábbi rendszerrel modellezhetjük a feladatot: �1 − �2 ≤ 0 �1 + �2 ≤ 8 10�1 + 7�2 ≥ 51 �1 , �2 ≥ 0 2000�1 + 1500�2 ��� A harmadik feltétel miatt kétfázisú szimplex módszerrel oldjuk meg a feladatot. Az induló szimplex tábla: u1 u2 u3* -z z* x1 1 1 10 -2000 10 x2 -1 1 7 -1500 7 v3 0

0 -1 0 -1 b 0 8 51 0 51 Először az x1 vektort hozzuk a bázisba, mert itt 1 a pivotelem. x1 u2 u3* -z z* u1 1 -1 -10 2000 -10 x2 -1 2 17 -3500 17 Ezután az x2 vektor következik: v3 0 0 -1 0 -1 b 0 8 51 0 51 x1 u2 x2 -z z* u1 7/17 3/17 - 10/17 -58 14/17 0 u3* 1/17 - 2/17 1/17 205 15/17 -1 v3 - 1/17 2/17 - 1/17 -205 15/17 0 b 3 2 3 10500 0 Az első fázis véget ért, és egyúttal a második is, a tábla már optimális megoldást tartalmaz. A feladat optimális megoldása: �1 = 3; �2 = 3; ���� = 10500. Tehát mindkét tablettából egyaránt 3 szemet kell vásárolni, és 10500 Ft a minimális költség. 20. feladat Egy kis szabóságban ingeket és szoknyákat varrnak. Egy ingen 4 $, egy szoknyán 3 $ nyeresége van a szabóságnak. Egy ing 3 m anyagból 5 óra alatt, egy szoknya 4 m anyagból 2 óra alatt készül el. A cég vezetője azt várja el a varrónőktől, hogy a napi 10 órás munkaidő alatt legalább 4 ruhadarabot készítsenek el,

legfeljebb 12 m anyag felhasználásával. Hány ing és hány szoknya megvarrásával érhető el egy varrónő esetén a maximális profit? Megoldás: Jelölje �1 az egy varrónő által elkészített ingek, �2 pedig a szoknyák számát. A feladat modellje a következő: 3�1 + 4�2 ≤ 12 5�1 + 2�2 ≤ 10 �1 + �2 ≥ 4 �1 , �2 ≥ 0 4�1 + 3�2 ��� A kétfázisú szimplex módszer induló táblája: x1 x2 v3 u1 3 4 0 u2 5 2 0 u3* 1 1 -1 -z 4 3 0 z* 1 1 -1 Az x1 változót hozzuk a bázisba: b 12 10 4 0 4 u2 u1 - 3/5 x1 1/5 u3* - 1/5 -z - 4/5 z* - 1/5 Majd az x2-t: b 6 2 2 -8 2 x2 14/5 2/5 3/5 7/5 3/5 v3 0 0 -1 0 -1 u2 u1 v3 b x2 - 3/14 5/14 0 15/7 x1 2/7 - 1/7 0 8/7 u3* - 1/14 - 3/14 -1 5/7 -z - 1/2 - 1/2 0 -11 z* - 1/14 - 3/14 -1 5/7 Mivel a másodlagos célfüggvény értéke pozitív maradt, és tovább már nem csökkenthető, a feladatnak nincs megoldása. 21. feladat Egy háziasszony eladásra lekvárt és befőttet készít. Összesen

120 kg gyümölcs és 80 kg cukor áll rendelkezésére. Egy üveg lekvárhoz 80 dkg gyümölcsre és 40 dkg cukorra, egy üveg befőtt elkészítéséhez 40 dkg gyümölcsre és 40 dkg cukorra van szüksége. A nyeresége egy üveg lekváron 100 Ft, egy üveg befőttön 80 Ft Hány üveg lekvárt és befőttet kell elkészítenie, hogy maximális nyereséget érjen el és mekkora ez a maximális nyereség? Megoldás: Tegyük fel, hogy a háziasszony �1 üveg lekvárt és �2 üveg befőttet készít. A feladat adataiból a következő modellt állíthatjuk fel: 0,8�1 + 0,4�2 ≤ 120 0,4�1 + 0,4�2 ≤ 80 �1 , �2 ≥ 0 100�1 + 80�2 ��� A normál feladat szimplex táblái: u1 u2 -z x1 0,8 0,4 100 x2 0,4 0,4 80 b 120 80 0 u1 x2 -z x1 0,4 1 20 u2 -1 2,5 -200 b 40 200 -16000 x1 x2 -z u1 2,5 -2,5 -50 u2 -2,5 5 -150 b 100 100 -18000 Az utolsó tábla optimális, melyből leolvashatjuk a megoldást: a háziasszonynak 100 üveg lekvárt és 100 üveg

befőttet kell készítenie, és így 18000 Ft lesz a bevétele. 22. feladat Egy üzemben két terméket (T1, T2) gyártanak, megmunkálásuk két gépen (G1,G2) történik. A T1 termék egy darabjának megmunkálása a G1 gépen 3 órát, a G2 gépen 4 órát vesz igénybe, a T2 termék esetén 4 és 6 óra ez a két adat. A G1 gép kapacitása 130, a G2 gép kapacitása 200 óra. A T1 termék szerelési ideje 1 óra, a T2 terméké 2 óra, a szerelde kapacitása 60 óra. A T1 termék eladási egységára 8, a T2 termék eladási egységára 10 pénzegység. Milyen termékösszetételben érdemes gyártani, ha maximális árbevételre törekszünk, úgy, hogy a gépek kapacitását nem lépjük túl és a szerelde teljes kapacitással dolgozik (azaz egyenlőség van a szereldére vonatkozó feltételben)? Megoldás: Jelölje �1 a T1 termékből gyártandó mennyiséget, �2 pedig a T2 termékből gyártandó mennyiséget. A feladat modellje a következő: 3�1 + 4�2 ≤ 130

4�1 + 6�2 ≤ 200 �1 + 2�2 = 60 �1 , �2 ≥ 0 8�1 + 10�2 ��� Felírjuk az induló szimplex táblát és elvégzünk egy pivotálást: x1 x2 b x1 u3* b u1 3 4 130 u1 1 -2 10 u2 4 6 200 u2 1 -3 20 u3* 1 2 60 x2 0,5 0,5 30 -z 8 10 0 -z 3 -5 -300 z* 1 2 60 z* 0 -1 0 A kétfázisú szimplex módszer első fázisa véget ért. Töröljük a mesterséges célfüggvény sorát és a mesterséges változó oszlopát, majd elvégzünk még egy pivotálást: u1 u2 x2 -z x1 1 1 0,5 3 b 10 20 30 -300 x1 u2 x2 -z u1 1 -1 -0,5 -3 b 10 10 25 -330 A kapott optimális táblából leolvassuk a megoldást: 10 darabot kell gyártani a T1 termékből, 25 darabot a T2 termékből. Az elért maximális nyereség 330 pénzegység. 23. feladat Egy üzem kétféle termék (T1, T2) előállításával foglalkozik. A termékeket három alkatrészből (A1, A2, A3) szerelik össze. Az első táblázat az egyes termékek összeszereléséhez szükséges alkatrészek számát, a

termékek szerelési idejét és a termékek egységárát tartalmazza. Az alkatrészek megmunkálását két gépen (G1,G2) végzik. A második táblázat az alkatrészek egyes gépeken történő megmunkálásának időszükségletét (percben) és a gépek kapacitását mutatja. A szerelde kapacitása 220 perc/nap. Meghatározandó a szerelde és a gépműhely kapacitását túl nem lépő napi termelés az egyes termékekből úgy, hogy az árbevétel maximális legyen! A1 A2 A3 Szer. idő Egységár T1 1 0 2 2 27 T2 0 1 1 1 8 A1 A2 A3 Kapacitás G1 1 0 1 240 G2 7 1 1 630 Megoldás: Jelölje �1 a T1 termékből gyártandó mennyiséget, �2 pedig a T2 termékből gyártandó mennyiséget. A táblázatok adataiból kiderül, hogy a T1 termék egy egységének előállításához 3 percre van szükség a G1 gépen, és 9 percre a G2 gépen. Ugyanezek az adatok a T2 termék esetén: 1 perc a G1 gépen és 2 perc a G2 gépen. Ezek után tudjuk felírni a gépekre vonatkozó

kapacitáskorlátokat és a feladat modelljét: 3�1 + �2 ≤ 240 9�1 + 2�2 ≤ 630 2�1 + �2 ≤ 220 �1 , �2 ≥ 0 27�1 + 8�2 ��� u1 u2 u3 x1 3 9 2 27 x2 1 2 1 8 b 240 630 220 0 u1 u2 x2 x1 1 5 2 11 u1 u3 b u1 x1 1 -1 20 x1 - 2/3 u2 -5 3 90 u3 -5/3 x2 -2 3 180 x2 3 -11 3 -1980 -6 A feladat optimális megoldása: �1 = 50; �2 = 90; ���� = 2070. u3 -1 -2 1 -8 b 20 190 220 -1760 u2 1/3 1/3 -1 -1 b 50 30 90 -2070 24. feladat Három nemnegatív számot kell meghatározni úgy, hogy az elsőt hárommal, a másodikat öttel, a harmadikat hattal szorozva és ezeket a szorzatokat összeadva az így keletkezett szám minél nagyobb legyen. A három szám összege legfeljebb száz lehet. Az első szám kétszeresének és a második számnak az összege pontosan harminc legyen. A harmadik szám kétszeresének és a második számnak az összege legalább ötven legyen. Írja fel a feladat matematikai modelljét és oldja meg a feladatot

szimplex módszerrel! Megoldás: Jelölje �1 , �2 , �3 a keresett számokat. A feladat modellje: �1 + �2 + �3 ≤ 100 2�1 + �2 = 30 �2 + 2�3 ≥ 50 �1 , �2 , �3 ≥ 0 3�1 + 5�2 + 6�3 ��� Két pivotálás után véget ér a kétfázisú szimplex módszer első fázisa: u1 u2* u3* -z z* x1 1 2 0 3 2 x2 1 1 1 5 2 x3 1 0 2 6 2 v3 0 0 -1 0 -1 b 100 30 50 0 80 u1 x2 u3* -z z* x1 -1 2 -2 -7 -2 u2* -1 1 -1 -5 -2 x3 1 0 2 6 2 v3 0 0 -1 0 -1 b 70 30 20 -150 20 u1 x2 x3 -z z* x1 0 2 -1 -1 0 u2* -0,5 1 -0,5 -2 -1 u3* -0,5 0 0,5 -3 -1 v3 0,5 0 -0,5 3 0 b 60 30 10 -210 0 Töröljük a mesterséges célfüggvény sorát és a mesterséges változó oszlopát, majd elvégzünk még egy pivotálást: u1 x2 x3 -z x1 0 2 -1 -1 v3 0,5 0 -0,5 3 b 60 30 10 -210 v3 x2 x3 -z x1 0 2 -1 -1 u1 2 0 1 -6 b 120 30 70 -570 Az utolsó tábla optimális, melyből meghatározhatjuk a megoldást: �1 = 0; �2 = 30; �3 = 70; ���� = 570.

25. feladat Egy üzem háromféle termék előállításával foglalkozik. A termékek megmunkálását két gépen végzik. Az esztergagép kapacitása 80 óra/hét, a marógép kapacitása 70 óra/hét. Az egyes termékfajták egységének megmunkálásához rendre 2, 1, 1 óra szükséges az esztergagépen, a marógépen mindhárom termékre 1 óra ez az adat. A termékek eladási egységára 3, 1 és 2 pénzegység. A termékegységre jutó anyagköltségek rendre 0,8, 0,2 és 0,5 pénzegység. A cél olyan heti termelési terv meghatározása, mellyel legalább 100 pénzegységnyi bevétel érhető el, de az anyagköltségek összege minimális. Megoldás: Jelölje �1 , �2 , �3 az egyes termékekből előállítandó mennyiségeket. A feladat adatainak alapján az alábbi modellt állíthatjuk fel: 2�1 + �2 + �3 ≤ 80 �1 + �2 + �3 ≤ 70 3�1 + �2 + 2�3 ≥ 100 0,8�1 + 0,2�2 + 0,5�3 ��� Két pivotálás után a tábla optimálissá tehető,

de a célfüggvény sorában szereplő 0 azt mutatja, hogy alternatív optimális megoldások is vannak. A célfüggvény minimuma azonban minden esetben 23 pénzegység. Ezt az értéket az �1 = 0; �2 = 40; �3 = 30 megoldással értük el, de például az �1 = 10; �2 = 50; �3 = 10 választással is optimális termelési tervet határozunk meg. u1 u2 u3* -z z* x1 2 1 3 -0,8 3 x2 1 1 1 -0,2 1 x3 1 1 2 -0,5 2 v3 0 0 -1 0 -1 b 80 70 100 0 100 u1 x2 u3* -z z* x1 1 1 2 -0,6 2 u2 -1 1 -1 0,2 -1 x3 0 1 1 -0,3 1 v3 0 0 -1 0 -1 b 10 70 30 14 30 u1 x2 x3 -z z* x1 1 -1 2 0 0 u2 -1 2 -1 -0,1 0 u3* 0 -1 1 0,3 -1 v3 0 1 -1 -0,3 0 b 10 40 30 23 0