MODUL: I. modul: Az operációkutatás tárgya és módszerei
3. lecke: Különböző feladatok megoldása szimplex módszerrel
Módosított normálfeladat, általános feladat, maximum feladat megoldása szimplex módszerrel. Minimumfeladatok megoldási módszerei. Dualitás fogalma.
Tanulási útmutató
Ez a lecke szorosan kapcsolódik az előző leckéhez. Csak akkor foglalkozzon ezzel, ha az előző feladatokat jól, hibátlanul megoldotta és megértette a szimplex táblázat lényegét. Azért nem az előző leckében tárgyaljuk ezeket az eseteket, mert idő kell a szimplex módszer lényegének megértéséhez.
Tevékenységek
Figyelmesen tanulmányozza át a tankönyv 1.5.2. alfejezetét. Különösen fontos, hogy jól értse a szimplex táblázat jelentéseit: Milyen szerepe van az egyenlőségek esetén az u* hiányváltozónak és a z* segéd-célfüggvénynek. A megértés szempontjából a szinte minden szónak fontos jelentése van. Kövesse végig figyelmesen a tankönyvben található feladat megoldását, majd csukja be a tankönyvet és önállóan is gondolja végig a megteendő lépéseket.
Az általános maximum feladat megoldása már csak egy plusz lépés megtételét jelenti: a v többletváltozó bevezetését. A bemutatott feladatot önállóan, külön lapon is oldja meg!
A bázis-transzformáció után mindig értékelje a kapott szimplex táblázatot:
leolvasható-e egy lehetséges megoldás?
ez a lehetséges megoldás optimális-e?
a célfüggvény korlátos-e?
alternatív optimális megoldást kaptunk-e?
Az eredménynek megfelelően tegye meg a szükséges további lépéseket és adja meg a lehetséges válaszokat. Ezek a logikai műveletek minősítik a diplomás embert! Ilyeneket kell gyakran végezni majd a munkahelyen is!
Figyelmesen olvassa el a minimumfeladatok megoldásának gondolatmenetét. Jól jegyezze meg, hogyan lehet a minimumfeladatot visszavezetni maximum feladatra és megoldani az eddig tanult módon.
A dualitás elvének nagy jelentősége van a lineáris programozási feladatok megoldásában. A dualitás fogalma és gazdasági értelmezése, valamint a felhasználás elvei a tankönyvben találhatók. Tanulmányozza figyelmesen ezeket az oldalakat, mert az érzékenységvizsgálatnál nagy hasznát veheti.
A dualitással kapcsolatos kérdések és példák a tankönyv 2.6. fejezetében találhatók. Gyakorlásként oldja meg ezeket!
Követelmények
Fel tudja ismerni, hogy a megoldandó feladat milyen típusú, és ennek megfelelően fel tudja írni az induló szimplex táblázatot. El tudja dönteni, hogy hol kell bevezetni az u* hiány és v többletváltozót. Elő tudja állítani a z* segéd-célfüggvényt.
Önállóan el tudja végezni a bázis-transzformációkat: ki tudja megválasztani a generáló elemet, és hibátlanul el tudja végezni a szükséges számításokat.
Értelmezni tudja az új táblázatokat. El tudja dönteni, hogy milyen megoldással áll szemben, hogyan kell folytatni a lépéssorozatot. A táblázatról le tudja olvasni a kapott eredményt, és hogyan kell azt közölni.
Fel tudja írni egy feladat duál párját. A szimplex táblázatból le tudja olvasni mind a prímál mind a duál feladat optimális megoldását.
Önellenőrző feladatok
1. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel!
Vegyen elő egy négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a táblázat. Írja be az alábbi mezőkbe a kapott értékeket! Ahol nincs elem, oda tegye "-" jelet.
a) Írja ide a táblázat z* sorának elemeit:
z*
b) Végezze el a bázis-transzformációt, amelynek eredménye a táblázat. Válasszon generáló elemet a 3. oszlopból! Írja ide a táblázat utolsó két sorának elemeit:
-z
z*
c) Értékelje a -es táblázatot, és döntse el, hogy az alábbi állítások helyesek-e!
Itt leolvasható egy alternatív optimum.
Itt leolvasható egy lehetséges megoldás.
d) Értékelje a -es táblázatot, és döntse el, hogy az alábbi állítások helyesek-e!
Itt még nem olvasható le egy lehetséges megoldás.
Itt a célfüggvény nem korlátos esete áll fenn!
e) Oldja meg a feladatot, és írja ide az optimális megoldást, ha létezik! Az optimális megoldás:
= = = z =
2. Egy lineáris programozási feladat megoldása során eljutottunk a táblázathoz.
a) Értékelje a táblázatot! Döntse el, hogy melyik állítás igaz!
Az eredeti modell egy módosított maximum feladat volt.
Az eredeti modell egy módosított minimum feladata volt
Az eredeti modell egy általános minimum feladat volt.
A -ből látszik, hogy a célfüggvény nem korlátos.
A -ből látszik, hogy alternatív optimum van.
b) Az optimális megoldást:
= = = z =
c) Alternatív optimuma van:
= = = z =
d) Egy másik alternatív optimum:
= = = z =
3. Oldja meg a duál párján keresztül az alábbi lineáris programozási feladatot!
Vegyen elő egy négyzetrácsos lapot! Írja fel a feladat duál párját! A duál változót jelölje y-nal. Helyezze el ezt a modellt a szimplex táblázatban. Legyen ez a táblázat! Végezzen bázis-transzformációt! Ellenőrzéshez tegye a következőt:
a)Töltse ki a következő táblázatot a duál feladat adataival!
b) Végezze el a szükséges bázis-transzformációkat és írja fel a primál feladat optimális megoldását: