Gazdasági Ismeretek | Operációkutatás » Operációkutatás feladatok megoldással

Minta az 1. Házi feladat megoldására, ÁVF, 2000/2001 I félév 1. Feladat: Megoldás: Standard alak: − x2 + x2 − x2 x2≥0, − x2 2x1 x1 x1 x1≥0, (− x1 − x3 − x3 + x3 x3≥0, − x3 + x4 + x4 − x4 x4≥0, − x4 + x5 − x6 x6≥0 ) x5≥0, =4 =2 =2 max Mesterséges változókkal bővített standard alak: 2x1 x1 x1 x1≥0, ( (− x1 − x2 + x2 − x2 x2≥0, − x3 − x3 + x3 x3≥0, + x4 + x4 − x4 x4≥0, − x2 − x3 − x4 + p1 + x5 x5≥0, − x6 x6≥0, p1≥0, p1 + p2 p2≥0 + p2) ) =4 =2 =2 min max Mesterséges változókkal bővített standard alak átzárójelezve és az első fázis célfüggvénye maximalizálásra változtatva: 4 2 2 0 0 − − − − − (2x1 ( x1 ( x1 x1≥0, − x2 + x2 − x2 x2≥0, − x3 − x3 + x3 x3≥0, + x4 + x4 − x4 x4≥0, ( x1 + x2 + x3 + x4 + p1 + x5 x5≥0, − x6 x6≥0, ( p1≥0, p1 ) ) + p2) p2≥0 + p2) ) =0 =0 =0 =Hmax =zmax Az első fázis célfüggvényéből a

mesterséges változókat eliminálva: 4 2 2 −6 0 − − − − − (2x1 ( x1 ( x1 x1≥0, (−3x1 ( x1 − x2 + x2 − x2 x2≥0, +2x2 + x2 − x3 − x3 + x3 x3≥0, + x4 + x4 − x4 x4≥0, + x3 + x4 + p1 + x5 x5≥0, 1 − x6 x6≥0, + x6 p1≥0, ) ) + p2) p2≥0 ) ) =0 =0 =0 =Hmax =zmax Az induló szimplex tábla: B0 p1 x5 p2 ∆Hj ∆zj xB 4 2 2 −6 0 x1 2 1 1 −3 1 ↑ x2 −1 1 −1 2 1 x3 −1 −1 1 0 1 x4 1 1 −1 0 1 x5 0 1 0 0 0 x6 0 0 −1 1 0 p1 1 0 0 0 0 θi 2 2 2 p2 0 0 1 0 0 ← Az I. fázis iterációi: B1 p1 x5 x1 ∆Hj ∆zj xB 0 0 2 0 −2 x1 0 0 1 0 0 x2 1 2 −1 −1 2 ↑ x3 −3 −2 1 3 0 x4 3 2 −1 −3 2 x5 0 1 0 0 0 x6 2 1 −1 −2 1 p1 1 0 0 0 0 B2 x2 x5 x1 ∆Hj ∆zj xB 0 0 2 0 −2 x1 0 0 1 0 0 x2 1 0 0 0 0 x3 −3 4 −2 0 6 x4 3 −4 2 0 −4 x5 0 1 0 0 0 x6 2 −3 1 0 −3 x3 −3 4 −2 6 x4 3 −4 2 −4 x5 0 1 0 0 x6 2 −3 1 −3 ↑ θi 0 − 2 x5 0 1 0 0 x6 1 0 0 0 θi 0 0 − p2

−2 −1 1 3 −1 p1 1 −2 1 1 −2 p2 −2 3 −1 1 3 ← θi A II. fázis iterációi: B2 x2 x5 x1 ∆zj xB 0 0 2 −2 x1 0 0 1 0 x2 1 0 0 0 B3 x6 x5 x1 ∆zj xB 0 0 2 −2 x1 0 0 1 0 x2 1/2 3/2 − 1/2 3/2 x3 − 3/2 − 1/2 − 1/2 3/2 x4 3/2 1/2 1/2 1/2 ← A feladatnak létezik megengedett megoldása és véges optimuma! Az optimális megoldás: x1 = 2.0, x2 = 00, x3 = 00, x4 = 00, zopt = − 20 2 2. Feladat: Megoldás: Standard alak: x1 2x1 −2x1 x1≥0, (−2x1 +2 x2 −2 x2 − x2 x2≥0, −2 x2 + x3 −2x3 −2 x3 x3≥0, + x3 − x4 − x4 +2 x4 x4≥0, + x4 − x5 =2 =4 =3 + x6 x5≥0, x6≥0, − x7 x7≥0 ) max Mesterséges változókkal bővített standard alak: x1 2x1 −2x1 x1≥0, ( (−2x1 +2 x2 −2 x2 − x2 x2≥0, + x3 −2x3 −2 x3 x3≥0, − x4 − x4 +2 x4 x4≥0, −2 x2 + x3 + x4 − x5 +p1 + x6 x5≥0, x6≥0, − x7 x7≥0, p1≥0, p1 +p2 p2≥0 +p2) ) =2 =4 =3 min max Mesterséges változókkal

bővített standard alak átzárójelezve és az első fázis célfüggvénye maximalizálásra változtatva: 2 4 3 0 0 − − − − − (x1 (2x1 (−2x1 x1≥0, ( (2x1 2 x2 −2 x2 − x2 x2≥0, +2 x2 + x3 −2 x3 −2 x3 x3≥0, − x3 − x4 − x4 +2 x4 x4≥0, − x5 + p1 + x6 x5≥0, x6≥0, − x7 x7≥0, p1≥0, p1 − x4 ) ) + p2) p2≥0 + p2) ) =0 =0 =0 =Hmax =zmax Az első fázis célfüggvényéből a mesterséges változókat eliminálva: 2 4 3 0 0 − − − − − (x1 (2x1 (−2x1 x1≥0, (x1 (2x1 2 x2 −2 x2 − x2 x2≥0, − x2 +2 x2 + x3 −2 x3 −2 x3 x3≥0, + x3 − x3 − x4 − x4 +2 x4 x4≥0, − x4 − x4 − x5 + p1 + x6 x5≥0, + x5 3 x6≥0, − x7 x7≥0, + x7 p1≥0, ) ) + p2) p2≥0 ) ) =0 =0 =0 =Hmax =zmax Az induló szimplex tábla: B0 p1 x6 p2 ∆Hj ∆zj xB 2 4 3 −5 0 x1 1 2 −2 1 2 x2 2 −2 −1 −1 2 ↑ x3 1 −2 −2 1 −1 x2 1 0 0 0 0 x3 1/2 −1 −3/2 3/2 −2 x4 −1 −1 2 −1 −1 x5

−1 0 0 1 0 x6 0 1 0 0 0 x7 0 0 −1 1 0 p1 1 0 0 0 0 p2 0 0 1 0 0 θi 2 − − p1 1/2 1 1/2 1/2 −1 p2 0 0 1 0 0 θi − − 8/3 ← Az I. fázis iterációi: B1 x2 x6 p2 ∆Hj ∆zj xB 1 6 4 −4 −2 B2 x2 x6 p2 ∆Hj ∆zj xB 7/3 34/3 8/3 0 −2 x1 1/2 3 3/2 3/2 1 x1 1 5 1 0 1 x4 − 1/2 −2 3/2 − 3/2 0 ↑ x5 − 1/2 −1 − 1/2 1/2 1 x2 1 0 0 0 0 x3 0 −3 −1 0 −2 x4 0 0 1 0 0 x5 − 2/3 − 5/3 − 1/3 0 1 x6 0 1 0 0 0 x2 1 0 0 0 x3 0 −3 −1 −2 ↑ x4 0 0 1 0 x5 − 2/3 − 5/3 − 1/3 1 x6 0 1 0 0 x6 0 1 0 0 0 p1 2/3 5/3 1/3 1 −1 p2 1/3 4/3 2/3 1 0 ← θi A II. fázis iterációi: B2 x2 x6 p2 ∆zj xB 7/3 34/3 8/3 −2 x1 1 5 1 1 θi A feladat célfüggvénye az adott korlátozó feltételek mellett tetszőlegesen nagy értéket felvehet, vagyis a feladatnak nincs véges optimuma. 4 3. Feladat: Megoldás: Standard alak: 2 x1 − 2x1 2 x1 x1≥0, (2 x1 + x2 − 2 x2 + x2 x2≥0, − x2 + x3 +2 x3 + 2 x3 x3≥0, −2

x3 −2 x4 + x4 − 2 x4 x4≥0, − x4 − x5 x5≥0, +x6 x6≥0 ) =4 =2 =4 max Mesterséges változókkal bővített standard alak: 2 x1 − 2x1 2 x1 x1≥0, ( (2 x1 + x2 − 2 x2 + x2 x2≥0, + x3 +2 x3 + 2 x3 x3≥0, −2 x4 + x4 − 2 x4 x4≥0, − x2 −2 x3 − x4 − x5 x5≥0, +p1 +p2 =4 =2 =4 + p2) ) min max +x6 x6≥0 p1 Mesterséges változókkal bővített standard alak átzárójelezve és az első fázis célfüggvénye maximalizálásra változtatva: 4 2 4 − − − 0 0 − − (2x1 (−2 x1 ( 2 x1 x1≥0, ( (−2x1 + x2 − 2 x2 + x2 x2≥0, + x3 +2 x3 +2 x3 x3≥0, − 2x4 + x4 −2 x4 x4≥0, + x2 +2 x3 + x4 − x5 x5≥0, + p1 + x6 x6≥0, p1≥0, p1 ) + p2) ) p2≥0 + p2) ) =0 =0 =0 =Hmax =zmax Az első fázis célfüggvényéből a mesterséges változókat eliminálva: 4 2 4 − − − −6 0 − − (2x1 (−2 x1 ( 2 x1 x1≥0, ( (−2x1 + x2 − 2 x2 + x2 x2≥0, + x2 + x2 + x3 +2 x3 +2 x3 x3≥0, −3 x3 +2 x3 −

2x4 + x4 −2 x4 x4≥0, + x4 + x4 − x5 x5≥0, + x5 5 + p1 + x6 x6≥0, p1≥0, ) + p2) ) p2≥0 ) ) =0 =0 =0 =Hmax =zmax Az induló szimplex tábla: B0 p1 p2 x6 ∆Hj ∆zj xB 4 2 4 −6 0 x1 2 −2 2 0 −2 x2 1 −2 1 1 1 x3 1 2 2 −3 2 ↑ x4 −2 1 −2 1 1 x5 −1 0 0 1 0 x6 0 0 1 0 0 p1 1 0 0 0 0 p2 0 1 0 0 0 θi 4 1 2 ← Az I. fázis iterációi: B1 p1 x3 x6 ∆Hj ∆zj xB 3 1 2 −3 −2 x1 3 −1 4 −3 0 B2 p1 x3 x2 ∆Hj ∆zj xB 5/3 5/3 2/3 −5/3 −4 x1 1/3 1/3 4/3 −1/3 −4 ↑ B3 p1 x3 x1 ∆Hj ∆zj xB 3/2 3/2 1/2 −3/2 −2 x1 0 0 1 0 0 x2 2 −1 3 −2 3 ↑ x3 0 1 0 0 0 x2 0 0 1 0 0 x2 −1/4 −1/4 3/4 1/4 3 x4 −5/2 1/2 −3 5/2 0 x3 0 1 0 0 0 x5 −1 0 0 1 0 x4 −1/2 −1/2 −1 1/2 3 x3 0 1 0 0 0 x4 −1/4 −1/4 − 3/4 1/4 0 x6 0 0 1 0 0 x5 −1 0 0 1 0 p1 1 0 0 0 0 p2 −1/2 1/2 −1 3/2 −1 x6 −2/3 1/3 1/3 2/3 −1 x5 −1 0 0 1 0 p1 1 0 0 0 0 x6 −3/4 1/4 1/4 3/4 0 θi 3/2 − 2/3 p2 1/6 1/6

−1/3 7/6 0 p1 1 0 0 0 0 ← θi 5 5 1/2 p2 1/4 1/4 −1/4 13/12 −1 ← θi A feladatnak nincs megengedett megoldása, mert a bevezetett mesterséges változók összegének a minimuma 3/2 és ez nagyobb mint nulla. Budapest, 2000. szeptember 27 Dr. Szántai Tamás sk főiskolai tanár 6 Minta a 2. Házi feladat megoldására, ÁVF, 1999/2000 II félév 1. Oldja meg a duális feladat megoldásával az alábbi lineáris programozási feladatot! Adja meg a w1, w2, w3, w4 változók optimális értékeit, valamint a célfüggvénynek ezekre a w1, w2, w3, w4 értékekre felvett optimális értékeit! 2 w1 − w1 − w1 w1≥0, (− w1 − w2 − w2 + w2 w2≥0, − w2 +2 w3 − w3 − w3 w3≥0, −3 w3 +2 w4 +2 w4 − w4 w4≥0 − w4 ) ≥4 ≥1 ≥2 max! Mivel tudjuk, hogy duál duálja az eredeti primál feladat, azért tekintsük a fenti feladatot minimalizálandó célfüggvénnyel: 2 w1 − w1 − w1 w1≥0, ( w1 − w2 − w2 + w2 w2≥0, + w2 +2 w3 − w3

− w3 w3≥0, +3 w3 +2 w4 +2 w4 − w4 w4≥0 + w4 ) ≥4 ≥1 ≥2 min! Ez a feladat duál alakú, így az ő duál párja az a primál alakú feladat, amelynek éppen ő a duális párja. Ha x1, x2, x3 jelöli ennek a feladatnak a változóit, akkor ez a feladat: 2 x1 − x1 2 x1 2 x1 x1≥0, (4 x1 − x2 − x2 − x2 +2 x2 x2≥0, + x2 − x3 + x3 − x3 − x3 x3≥0 +2 x3) ≤1 ≤1 ≤3 ≤1 max! Vezessük be az x4, x5, x6, x7 segéd változókat: 2 x1 − x1 2 x1 2 x1 x1≥0, (4 x1 − x2 − x2 − x2 +2 x2 x2≥0, + x2 − x3 + x3 − x3 − x3 x3≥0, +2 x3 + x4 + x5 + x6 x4≥0, x5≥0, x6≥0, + x7 x7≥0 ) =1 =1 =3 =1 max! Ebben a feladatban az x4, x5, x6, x7 segéd változók kifejezett változók, így átzárójelezés után azt kapjuk, hogy 7 1− 1− 3− 1− 0− (2 x1 (− x1 (2 x1 (2 x1 x1≥0, (−4 x1 − x2 − x2 − x2 +2 x2 x2≥0, − x2 − x3 + x3 − x3 − x3 x3≥0, −2 x3 + x4 ) ) ) + x7) x7≥0 ) + x5 + x6 x4≥0,

x5≥0, x6≥0, =0 =0 =0 =0 max! Ebből az induló szimplex tábla és az ezt követő iterációk szimplex táblái rendre: B0 x4 x5 x6 x7 ∆zj xB 1 1 3 1 0 x1 B1 x4 x3 x6 x7 ∆zj xB 2 1 4 2 2 x1 B2 x4 x3 x6 x2 ∆zj B3 x1 x3 x6 x2 ∆zj xB 6 3 8 2 8 xB 2 3 2 0 14 2 −1 2 2 −4 1 −1 1 1 −6 x1 x2 −1 −1 −1 2 −1 x3 −1 1 −1 −1 −2 ↑ x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 0 x7 0 0 0 1 0 θi − 1 − − x2 −2 −1 −2 1 −3 ↑ x3 x4 1 0 0 0 0 x5 1 1 1 1 2 x6 0 0 1 0 0 x7 0 0 0 1 0 θi − − − 1 x2 x3 0 0 0 1 0 3 0 3 1 −3 ↑ x1 0 1 0 0 0 x2 1 0 0 0 0 x4 1 0 0 0 0 0 1 0 0 0 x3 0 0 0 1 0 x4 1/3 0 −1 −1/3 1 0 1 0 0 0 x5 3 2 3 1 5 x5 1 2 0 0 8 x6 0 0 1 0 0 x6 0 0 1 0 0 ← ← θi 4/3 − 8/3 2 x7 2 1 2 1 3 x7 2/3 1 0 1/3 5 ← θi Ez a feladat optimális szimplex táblája, melyből leolvasható a duális feladat optimális megoldása: x1=2, x2=0, x3=3, x4=0, x5=0, x6=2, x7=0 és az optimum zopt=14. Ha

most x4, x5, x6, x7 helyett u1, u2, u3, u4 jelöli a feladat segéd változóit és az optimális szimplex tábla felső sorában azonosítjuk a duál feladat megfelelő w1, w2, w3, w4 változóit és v1, v2, v3 segéd változóit, akkor a ∆zj sorból leolvashatjuk a duál, vagyis az eredeti feladat optimális megoldását is: B3 x1 x3 xB 2 3 v1 x1 v2 x2 1 0 v3 x3 0 0 w1 u1 1/3 0 0 1 8 w2 u2 1 2 w3 u3 0 0 w4 u4 2/3 1 θi u3 x2 ∆zj 2 0 14 0 0 0 0 1 0 −1 −1/3 1 0 0 0 0 0 8 1 0 0 0 1/3 5 Így duális pár optimális megoldása: w1=1, w2=8, w3=0, w4=5, v1=0, v2=0, v3=0 és az optimuma f=14, vagyis a f = −14 . feladatban kérdezett maximalizálandó célfüggvényre 2. Oldja meg az alábbi szállítási feladatot: 8 3 7 4 1 9 5 8 4 9 5 5 7 2 3 8 1 4 6 1 4 3 7 36 2 34 10 27 33 27 17 33 36 81 167 Az induló megoldást Vogel és Korda módszerével keressük meg (valószínű, hogy ez nehezen lesz követhető). 26 10 36 10 8

3 7 4 5 8 4 9 7 2 3 8 6 34 34  3 2 1 1 10 10  7 7  2 27 27  5 2  17 1 9 5 16 4 7 20 1 3 4 7 33 16  4 4  5 5 5 5 27 7  5 3 2  26 20 47 17 33 36 81 167   37 10 8 5 7 6  5 7 5  5 5 5 Letisztázva az induló megoldást és a duál változókat a baloldali és a felső peremre kiszámítva, valamint a bal alsó sarokba a javítás mutatószámait kiszámítva: −1 4 0 1 0 2 8 4 0 3 4 26 7 5 6 1 10 10 9 5 5 8 16 6 2 4 1 7 20 3 3 3 34 34 9 6 2 3 10 36 4 3 7 1 17 4 2 8 8 3 2 7 27 27 4 1 3 0 5 4 7 1 33 27 17 33 36 81 167 Szerencsés módon máris megtaláltuk az optimális megoldást, hiszen a bal alsó sarkok mindegyikében nemnegatív szám áll. Tekintsük mégis a (4,5) cellát, itt a bal alsó sarokban 0 található, tehát hozzá hurkot szerkesztve egy alternatív optimális megoldást lehet megtalálni. A hurok a következő: (4,5) − (3,5) − (3,6) − (2,6) −

(2,1) − (4,1) Ebben a (4,5) cellától páratlan távoli cellákba beírt szállítások rendre 16, 7 és 10, ezek minimuma 7, így egy alternatív optimális megoldást ad a következő szállítási tábla: −1 4 0 1 0 2 8 4 0 3 4 33 7 5 3 36 34 34 8 6 10 10 2 4 1 27 27 4 9 5 5 3 3 3 1 9 6 2 3 6 4 3 7 1 17 4 2 8 8 3 2 7 5 0 9 7 33 9 1 27 3 4 7 1 27 17 33 36 81 167  4 4 3  0  1 Megjegyzés: Mindaddig, ameddig a bal alsó sarkokba számított számok között van negatív, a fentihez hasonló transzformációkat kell végrehajtani. A feladat egyik optimális megoldása: 1 5: 17 egység 1 egységárral = 17 2 1: 33 egység 5 egységárral = 165 3 5: 9 egység 1 egységárral = 9 3 6: 27 egység 4 egységárral = 108 4 1: 3 egység 6 egységárral = 18 4 2: 34 egység 1 egységárral = 34 4 3: 10 egység 2 egységárral = 20 4 4: 27 egység 4 egységárral = 108 4 5: 7 egység 3 egységárral = 21 Összesen: 500 10 3.

Oldja meg az alábbi hozzárendelési feladatot: 20 50 16 56 42 8 64 18 23 5 2 21 8 19 36 66 29 20 58 8 36 19 5 13 21 16 19 2 21 60 20 49 52 29 50 56 39 9 49 57 24 34 21 27 11 27 65 22 33 Először minden sor minden eleméből le kell vonni a sor legkisebb elemét, ezért minden sor mellett feltüntetjük a legkisebb elemet: 20 50 16 56 42 8 64 18 23 5 2 21 8 19 36 66 29 20 58 8 36 19 5 13 21 16 19 2 21 60 20 49 52 29 50 56 39 9 49 57 24 34 21 27 11 27 65 22 33 2 45 11 54 26 0 62 0 18 0 0 5 0 17 18 61 24 18 42 0 34 1 0 8 19 0 11 0 3 55 15 47 36 21 48 38 34 4 47 41 16 32 3 22 6 25 49 14 31 1 0 8 19 0 11 0 0 3 55 15 47 36 21 48 3 38 34 4 47 41 16 32 4 3 22 6 25 49 14 31 3 A levonások után keletkező tábla: Másodszorra ugyanezt megtesszük minden oszlopra: 2 45 11 54 26 0 62 0 0 18 0 0 5 0 17 0 18 61 24 18 42 0 34 0 11 18 5 5 2 16 8 2 2 45 11 54 26 0 62 0 18 0 0 5 0 17 18 61 24 18 42 0 34 1 0 8 19 0 11 0 0 52 12 44 33 18 45 34 30 0 43 37 12 28 0

19 3 22 46 11 28 18 61 24 18 42 0 34 ↓ 1 0 8 19 0 11 0 ↑ 0 52 12 44 33 18 45 ↓ 34 30 0 43 37 12 28 ↑ Lefedjük az összes nullát minimális számú fedővonallal: 2 45 11 54 26 0 62 ↓ 0 18 0 0 5 0 17 ↑ 0 19 3 22 46 11 28 ← ← A fedetlen elemek legkisebbike 3, ezt levonjuk a fedetlenekből és hozzáadjuk a kétszer fedettekhez: 2 42 8 51 23 0 59 ↓ 3 18 0 0 5 3 17 ↑ 18 58 21 15 39 0 31 ↓ 4 0 8 19 0 14 0 ↑ 0 49 9 41 30 18 42 37 30 0 43 37 15 28 0 16 0 19 43 11 25 ← ← ← A fedetlen elemek legkisebbike 15, ezt levonjuk a fedetlenekből és hozzáadjuk a kétszer fedettekhez: 12 2 27 8 36 8 0 44 ↓ 3 18 0 0 5 3 17 ↑ 18 43 21 0 24 0 16 ↓ 4 0 8 19 0 14 0 ↑ 0 34 9 26 15 18 27 37 15 0 28 22 15 13 0 1 0 4 28 11 10 ← ← ← ← A fedetlen elemek legkisebbike 1, ezt levonjuk a fedetlenekből és hozzáadjuk a kétszer fedettekhez: 2 26 8 36 7 0 43 4 18 1 1 5 4 17 18 42 21 0 23 0 15 ↓ 5 0 9 20 0 15 0

↑ 0 33 9 26 14 18 26 37 14 0 28 21 15 12 0 0 0 4 27 11 9 ← ← ← ← ← A fedetlen elemek legkisebbike 5, ezt levonjuk a fedetlenekből és hozzáadjuk a kétszer fedettekhez: 2 26 8 36 2 0 38 4 18 1 1 0 4 12 18 42 21 0 18 0 10 5 5 9 20 0 20 0 0 33 9 26 9 18 16 37 14 0 28 16 15 7 0 0 0 4 22 11 4 A fenti táblában az összes nullát már csak 7 vonallal lehetett volna lefedni, ezért kellett, hogy létezzen 7 darab egymást mint sakkbástya nem ütő nulla szám a táblában. Ezeket félkövér betűkkel jelöltem Végül is az eredeti táblában a feladat optimális megoldása: 1 5: 21 2 7: 3 6: 9 4 3: 20 5 2: 6 1: 8 7 4: 2 Összesen: 27 21 108 13