KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

4. lecke: Programozási feladatok megoldása Solver programmal

Érzékenységvizsgálat

Tanulási útmutató

A lineáris és nemlineáris programozási feladatok megoldására és az optimális megoldás utóelemzésére jól felhasználható az Excel táblázatkezelő.

A Solver program leírását a tankönyvben megtalálja. Kövesse a jegyzet útmutatásait úgy, hogy nyissa meg az Excel táblázatkezelőt. Figyeljen a jegyzetben található szakkifejezésekre! Ezeket jól jegyezze meg.

Az érzékenységvizsgálat lényegét és eseteit a tankönyv 3.1 és 3.2. fejezetében találja. Ezt elég azután áttanulmányozni, ha az elemzést a számítógépével megvalósította.

Tevékenységek
  • Figyelmesen olvassa el a Solver program leírását. Előre nyissa meg az Excel táblázatkezelő programot, hogy a leírtakat a táblázatkezelőn mindjárt azonosítsa, illetve megvalósítsa.
  • A 3. lecke tanulása során megismerte, hogy mit nevezünk együttható mátrixnak (A), jobb oldal vektorának ( b ¯ ), célfüggvénynek (z) és a változók vektorának ( x ¯ ). Ezeknek megfelelő tartományokat, cellákat kell kijelölni az Excel-táblázaton, és célszerű a képernyőn látható módon elnevezni ezeket.
  • Ha az MSZORZAT (A; x ¯ ) műveletet túl bonyolultnak találja (az is, mert nehéz javítani), akkor ajánlható a képletek cellába való beírása. Pl. H9 cellába ezt beírni:
    =8*C11+6*C12+2*C13+10*C14+2*C15 majd Enter.
  • A képletek elemeit érdemes rámutatással beírni, mert így kisebb a hiba lehetősége! Hasonlóan lehet az egyenlőtlenség bal oldalának képletét a kijelölt cellába beírni. Ennél is kényelmesebb a SZORZATÖSSZEG függvény használata. ( f x , Mat. és trigonom.)
  • Ha valamelyik legördülő menüben nem ért valamit, akkor bátran használja a Súgót, igen hasznos részletes információt ad a gyakorlati kivitelezéshez és az elmélethez is!
  • A modell adatainak bevitele és a célfüggvény valamint a korlátozó feltételek képleteinek elhelyezése után hívja meg a Solver parancsot. Itt kell értelemszerűen az előzően Excel celláiban elhelyezett képleteket és változókat bejelölni.
  • A Beállítások lenyíló menüben igen fontos bejelölni, hogy Lineáris modellt feltételezünk vagy nem. Hasonlóan fontos (hátha elfelejtettük) a Nemnegatív feltételezés bejelölése, mert ez a változók nemnegatívitását biztosítja. Mint tudja ez a lineáris programozási feladatoknál alapfeltétel!
  • A többi opció beállítása most még nem szükséges. (Súgóban megtalálható a fogalmak definíciója). Ezeket akkor kell beállítani, ha a "Solver nem talál megoldást" című üzenetet kapja. Előfordulhat, hogy azért nem kapott megoldást, mert kevés a beállított idő, vagy túl nagy pontossággal akarja a változó értékeit meghatározni (a Solver közelítő megoldásokat ad!), vagy az egyenlőségeket teljesíteni! Természetesen az is lehet, hogy tényleg nincs optimális megoldás valamilyen a tankönyvben korábban tárgyalt eset miatt.
  • Ha a tankönyvben található példát Ön is sikerrel megoldotta a Solver program segítségével, akkor oldja meg a könyv 1.5.2. fejezetében található, szimplex módszerrel már megoldott feladatot. Ha nehézséget okoz az elhelyezés, akkor a mellékelt "4. téma mintafeladata" Excel-fájlban ezt tanulmányozhatja. Így tudja ellenőrizni, hogy sikeres volt-e az Exceles elképzelése. Természetesen minden feladat megoldása ellenőrizhető: visszahelyettesíti a kapott optimális megoldást az eredeti feladatba.
  • Ha az eddig elmondottakat jól begyakorolta, akkor foglalkozzon az érzékenység- vizsgálattal.  Jól jegyezze meg az erőforrások árnyékára és a redukált költség fogalmak jelentőségét és azt, hogyan kell ezt az Érzékenység jelentésből leolvasni.
  • Ezen ismeretek birtokában végezzen Ön is egy érzékenységvizsgálatot! Tegye fel a "Mi lenne, ha..." típusú kérdést a probléma megoldása kapcsán. Pl. Mi lenne, ha az egyik erőforrás kapacitását 5 egységgel megnövelnénk? (Hiszen ezt az erőforrást teljesen kihasználtuk, korlátozza a termelés méretét, a célfüggvény értékét).
Követelmények
  • Meg tudjon oldani egy adott programozási feladatot Solver segítségével.
  • Excel*táblázaton elhelyezett programozási feladatot meg tudjon Solverrel oldani, és válaszolni tudjon a következő típusú kérdésekre:
    • Milyen változtatást kell megtenni a modellen, hogy a programba nem került változó is bekerülhessen?
    • Milyen változtatást kell tennem, hogy az erőforrások szűk keresztmetszetét növeljem és a célfüggvény is a legnagyobb mértékben növekedjék.

Bemutató feladat

Oldjuk meg Solver segítségével a következő feladatot:

x 1 , x 2 , x 3 0 2 x 1 + x 2 + x 3 16 x 1 + x 2 +2 x 3 = 10 x 1 +2 x 2 + x 3 16 z= x 1 +3 x 2 + x 3 max

Vigyük be az Excelbe az adatokat az alábbi módon:

A z* a megoldásvektor lesz, ennek értékei jelenleg nullával egyenlők. A b vektor előtt üresen hagyott oszlopba elő kell állítani az egyenletek algebrai formáját.

Az E3 oszlopba írjuk be: =SZORZATÖSSZEG(B3:D3;$B$7:$D$7).

A kapott érték természetesen itt is nulla lesz. Ezt másoljuk be az összes egyenlet sorába (E4; E5).

Az E6 cellába fogjuk a célfüggvény értékét megkapni, ide most az alábbi kerül:
=SZORZATÖSSZEG(B6:D6;$B$7:$D$7)

Ezután a feladatot oldjuk meg Solverrel. A Solvert az eszközök menüben találjuk meg. Nem automatikus része az Excelnek, külön kell telepíteni. Telepítés után azonban nem működik automatikusan. Az Eszközök menüben, a Bővítménykezelő ablakában be kell jelölni a Solver bővítmény választódobozát.

Hívjuk meg a Solvert az Eszközök menüből.

1.Célcellának jelöljük be az E6-t, ekkor az ablakban a következőt látjuk:$E$6
2.Jelöljük meg a max-t, hiszen a feladat maximumot kér.
3.A módosuló celláknak jelöljük be a B7;D7-t, ekkor az ablakban megjelenik: $B$7:$D$7
4.Korlátozó feltételek: egyenként kell felvenni őket:
    • $E$3<=$G$3
    • $E$4=$G$4
    • $E$5>=$G$5
5.A Beállítás gombra kattintva bejövő ablakon két dolgot kell megjelölni
    • A lineáris modell feltételezése
    • A nem negatív feltételezés
6.Ezután kattintsunk a megoldás gombra.
7.A megjelenő ablakba már láthatjuk az eredményt:
8.Ezután kérdezzük le az Eredményt és az érzékenységjelentést.

Eredményjelentés:

A célfüggvény értéke 38. A változók értékénél látható, hogy x3 változó értéke nullával egyenlő, ez azt jelenti, hogy ne szerepeljen a programban. A korlátozó feltételeknél látható, hogy az általunk megadott korlátok mennyire teljesültek.

Érzékenységjelentés:

1.Módosuló cellák: A redukált költség oszlopában, amely változó sorában érték van, azt a változót nem vonjuk be a bázisba. AZ oszlopban szereplő értékek megmutatják, hogy miért ne szerepeljen a változó a programban. Ha van érték, az azt jelenti, hogy a célfüggvény értékét ennyivel csökkentené a változó minden egyes egysége. Ez esetünkben 3,667. Hogy ezt elkerüljük, növelni kellene x3 célfüggvénybeli együtthatóját. Jelen esetben legfeljebb 3,667 egységgel. A feladat még optimális marad, de fennáll az alternatív optimum lehetősége. Ez a megengedhető növekedés/csökkenés oszlop jelentése.  A redukált költségoszlop értékei minimumfeladatnál pozitív előjelűek, ami azt jelenti, hogy növelnék a minimumot. Maximum feladat esetében negatív előjelűek, mert csökkentenék az optimumot.
2.Korlátozó feltételek: A Shadow árnyékár azt mutatja meg, hogy ha egy erőforrás korlátozottan áll rendelkezésre, kapacitásának egységnyi változása hogyan változtatja meg a célfüggvény értékét. A megengedhető növekedés/csökkenés oszlopban azokat a határokat látjuk, amelyek között a feltételek jobb oldalán álló kapacitás változhat az adott bázis változatlansága mellett.
Önellenőrző feladatok

1. Oldja meg a következő feladatot Solver programmal!

x 1 , x 2 , x 3 0 x 1 +3 x 3 6 x 1 + x 2 + x 3 2 x 1 + x 2 + x 3 = 8 z=110 x 1 +50 x 2 +120 x 3 max

Javaslom, hogy a B4:D6 tartományba helyezze el az együttható mátrixot, a B7:D7 tartományba a célfüggvény együtthatóit, F4:F6 cellákba a jobb oldal konstansait, a változók értékei a B9-D9 tartományban legyen olvasható, a célfüggvény képletét az F7 cellába írja be. Javaslom, hogy a feltételrendszer bal oldali képleteit a H4:H6 tartományba helyezze el. Hívja meg a Solver programot, töltse ki a felkínált táblázatokat!

Oldja meg a feladatot, majd adja meg az optimális megoldást!

Írja be a mezőkbe a jó megoldást!

x 1 =
x 2 =
x 3 =
z =

2. Oldja meg a következő programozási feladatot, a Solver program segítségével.

x 1 , x 2 , x 3 0 3 x 1 +2 x 3 6 2 x 1 + x 2 + x 3 15 x 1 + x 2 + x 3 = 8 z=110 x 1 +50 x 2 +70 x 3 max

Helyezze el az Excel-táblázaton. Oldja meg, majd válaszoljon a következőkre:

a) Az optimális megoldás:

x1 =
x2 =
x3 =
Zopt=

b) A változók redukált költsége rendre:

c) Az erőforrások árnyékára rendre:

Milyen változást kell megtenni a modellen, hogy a programba be nem került változó is bekerülhessen?

a) Melyik változó célfüggvénybeli együtthatóját kell megváltoztatni?

A . változó

b) Hogyan kell változtatni az értékét?
növelni kell
csökkenteni kell
c) Legalább mennyivel kell változtatni az értékét?

d) Mi lesz ezután az optimális megoldás?

x 1 =
x 2 =
x 3 =
z =