KURZUS: Alkalmazott operációkutatás

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

2. lecke: Lineáris programozás matematikai modelljei és a normálfeladat megoldása szimplex módszerrel

Tanulási útmutató

A lineáris programozás numerikus megoldásának módszereit a tankönyv azonos című fejezetében találja meg.

A módszerek alkalmazása függ a feladat típusától. Ezért fontos, hogy először megismerje a lineáris programozási feladatok típusait.

Az egyenlőtlenségrendszerben előforduló relációk szerint megkülönböztethetünk normál, módosított normál és általános feladatot. Ezek definíciója és mátrix-vektor szimbólumokkal megadott modelljei a tankönyvben találhatók.

A szimplex módszer lényegét pedig a tankönyv 1.5. fejezetében találja.

Tevékenységek

2.1. Figyelmesen olvassa el a lineáris programozási feladat definícióját, majd jól jegyezze meg a használt szimbólumokat és azok elnevezését. A tankönyv 1.3. fejezetében találja a lineáris programozási feladatok skalár, majd alatta a vektor-mátrix jelekkel felírt modelljét. Ezeket jól rögzítse, mert az egész tankönyvben ezeket a formákat használjuk.

2.2. Olvassa el, és jól jegyezze meg a definíciókat és matematikai szimbólumokkal felírt modellek típusait. A feladatok megoldásakor ezeket kell felismerni, hiszen ettől függően kell alkalmazni a matematikai lépéseket.

2.3. Az alkalmazott numerikus módszer (szimplex módszer) lépéseinek leírása és az indoklása a tankönyv 1.5. fejezetében található. A tankönyvben igen tömören van megfogalmazva az eljárás és azok indoklása, ezért többször pontokba foglaltuk az eljárás lényegét. Végeredményben ezt az eljárást kell alkalmazni a megoldás során, de jobban megjegyzi, ha ismeri a matematikai elméletét is.

2.4. Igen fontos, hogy a szimplex táblázatban jól eligazodjon. Ez a táblázat sok információt tartalmaz:

  • hogyan kell leolvasni a lehetséges megoldást?
  • a lehetséges megoldás optimális-e?
  • alternatív megoldást kapott-e?
  • a célfüggvény korlátos-e?

Ezen esetek vizsgálatát hasonlítsa össze a grafikus megoldásnál bemutatott esetekkel!

A bemutatott modelleket oldja meg külön lapon önállóan is. Így meggyőződhet arról, hogy önállóan képes-e megoldani a típusfeladatokat.

Követelmények

2.1. A kulcsszavak kiválasztásával fel tudja írni a lineáris programozási feladatok definícióját.

2.2. A különböző módon megadott modellekről el tudja dönteni, hogy milyen típusú lineáris programozási feladatról van szó.

2.3. Fel tudja írni egy adott lineáris programozási feladat induló szimplex táblázatát. Bázis transzformációt hibátlanul el tudja végezni, a kapott eredményt le tudja olvasni a szimplex táblázatról.

2.4. Egy adott szimplex táblázatról el tudja dönteni, hogy alternatív optimum esetéről van-e szó, vagy a célfüggvény nem korlátos esetéről. Tudni kell, hogy ezekben az esetekben hogyan kell eljárni.

Önellenőrző feladatok
1234567
elsőfokú= egyenlőtlenségeknem negatívnem lineáris
1. Fogalmazza meg az alábbi modellek lényegét a felsorolt kulcsszavak kiegészítésével! A szavak feletti számot írja be a megfelelő mezőbe!

1/a Normál feladatnak nevezünk egy maximum feladatot akkor, ha egyenlőtlenségei értelműek és b ¯ 0 ¯ feltétel is teljesül.

1/b Módosított normálfeladatnak nevezünk egy modellt, ha egyenlőtlenségei értelműek, tartalmaz -t és a jobb oldalon b ¯ 0 ¯ feltétel is teljesül.

1/c Általános feladatnak nevezünk egy lineáris modellt, ha feltételei között a b ¯ 0 ¯ fennáll és reláció is szerepel az egyenlőtlenségben.

1/d Olyan feladatot nevezünk lineáris programozási feladatnak, amelyekben a feltételek egyenletek és , a célfüggvényük is és a bennük szereplő váltózók számértéket vehetnek fel.

2. Milyen típusú feladatok az alábbi modellek?

1. x ¯ 0 ¯ A 1 x ¯ b ¯ 1 A 2 x ¯ = b ¯ 2 z= c ¯ T x ¯ max 2. x ¯ 0 ¯ A x ¯ b ¯ z= c ¯ T x ¯ max
3. x ¯ 0 ¯ A x ¯ b ¯ z= c ¯ T x ¯ min 4. A 1 x ¯ b ¯ 1 A 2 x ¯ b ¯ 2 z= c ¯ T x ¯ min
Párosítsa az alábbi feladatokat az állításokkal! Írja be a modell számát a megfelelő mezőbe! Ahol nincs megoldás, oda írjon "-" jelet!

Normál maximum feladat:
Normál minimum feladat:
Módosított maximum feladat:
Általános maximum feladat:
Általános minimum feladat:

3. Milyen típusú lineáris programozási feladatok az alábbi modellek?

1. x 1 , x 2 , x 3 0 2 x 1 +5 x 2 + x 3 50 x 2 + x 3 10 z=20 x 1 + x 2 x 3 max 2. x 1 , x 2 , x 3 0 2 x 1 +5 x 2 + x 3 50 x 1 x 3 = 10 z= x 1 +10 x 2 x 3 max
3. x 1 , x 2 , x 3 0 2 x 1 +5 x 2 + x 3 50 x 2 + x 3 10 z= x 1 +10 x 2 x 3 min 4. x 1 , x 2 , x 3 0 2 x 1 +5 x 2 + x 3 50 x 1 x 2 x 3 10 z= x 1 +10 x 2 x 3 max
Párosítsa az alábbi feladatokat az állításokkal! Írja be a modell számát a megfelelő mezőbe! Ahol nincs megoldás, oda írjon "-" jelet!

Normál maximum feladat:
Normál minimum feladat:
Módosított maximum feladat:
Általános maximum feladat:
Általános minimum feladat:

4. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel!

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

Vegyen elő négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a B 0 táblázat. Válasszon generáló elemet az első oszlopból. Végezzen bázistranszformációt! Az eredmény a B1 táblázat. Ellenőrzéshez tegye a következőt:

4/a Írja ide a B 1 táblázat utolsó sorának elemeit:

4/b Olvasson le egy lehetséges t megoldást a B 1 táblázatból, ha van! Ahol nincs megoldás, oda írjon "-" jelet!

x 1 =
x 2 =
x 3 =
z =

4/c Írja le az optimális megoldást, ha létezik! Ha nincs megoldás, a mezőkbe írjon "-" jelet!

x 1 =
x 2 =
x 3 =
z =

5. Egy lineáris programozási feladat megoldása során az alábbi szimplex táblázatot kaptuk:

Értékelje a táblázatot: A felkínált válaszok közül válassza ki a helyeset! (Több jó válasz is lehet!)
Leolvasható egy optimális megoldás, amely x 1 =22;   x 2 =0;   x 3 =11;   z = 820.
Leolvasható egy lehetséges megoldás, amely x 1 =22   x 2 =0   x 3 =11   z=820
Alternatív optimuma van a feladatnak.
A célfüggvény nem korlátos, nincs optimális megoldása.
A feladatnak nincs lehetséges megoldása, tehát optimális megoldása sem.
Az optimális megoldás: x 1 =22;   x 2 =80;   x 3 =11;   z = -820.
A feladat degenerált.