KURZUS: Alkalmazott operációkutatás

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!

x 1 , x 2 , x 3 0 x 1 +3 x 2 + x 3 12 x 1 +2 x 2 + x 3 = 10 z=20 x 1 +30 x 2 +40 x 3 max

Vegyen elő egy négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a B 0 táblázat. Írja be az alábbi mezőkbe a kapott értékeket! Ahol nincs elem, oda tegye "-" jelet.

a) Írja ide a B 0 táblázat z* sorának elemeit:
z*
b) Végezze el a bázis-transzformációt, amelynek eredménye a B 1 táblázat. Válasszon generáló elemet a 3. oszlopból! Írja ide a B 1 táblázat utolsó két sorának elemeit:
-z
z*
c) Értékelje a B 1 -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 B 1 -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:

x 1 =
x 2 =
x 3 =
z =

2. Egy lineáris programozási feladat megoldása során eljutottunk a B 2 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 2 -ből látszik, hogy a célfüggvény nem korlátos.
A B 2 -ből látszik, hogy alternatív optimum van.
b) Az optimális megoldást:

x 1 =
x 2 =
x 3 =
z =

c) Alternatív optimuma van:

x 1 =
x 2 =
x 3 =
z =

d) Egy másik alternatív optimum:

x 1 =
x 2 =
x 3 =
z =

3. Oldja meg a duál párján keresztül az alábbi lineáris programozási feladatot!

x 1 , x 2 , x 3 0 x 1 + x 2 + x 3 50 2 x 1 + x 2 20 z=20 x 1 +18 x 2 +8 x 3 min

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 B 0 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 0 y 1 y 2
x 1
x 2
x 3
z
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:

x 1 =
x 2 =
x 3 =
z opt =

c) duál feladat optimális megoldása:

y 1 =
y 2 =
z opt =