Gazdasági Ismeretek | Operációkutatás » Operációkutatás példamegoldás

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 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 0 1 0 0 0 x3 0 0 0 1 0 0 1 0 0 0 x4 1 0 0 0 0 x4 1/3 0 −1 −1/3 1 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 0 1 w1 u1 1/3 0 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 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 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 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: 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