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: | ||
| ||
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 | |||||||||||||||
| |||||||||||||||
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 feltétel is teljesül. ![]() | |||||||||||||||
2. Milyen típusú feladatok az alábbi modellek? | |||||||||||||||
| |||||||||||||||
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: ![]() | |||||||||||||||
3. Milyen típusú lineáris programozási feladatok az alábbi modellek? | |||||||||||||||
| |||||||||||||||
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: ![]() | |||||||||||||||
4. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel! | |||||||||||||||
Vegyen elő négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a 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 táblázat utolsó sorának elemeit: ![]() | |||||||||||||||
4/b Olvasson le egy lehetséges t megoldást a táblázatból, ha van! Ahol nincs megoldás, oda írjon "-" jelet! = ![]() | |||||||||||||||
4/c Írja le az optimális megoldást, ha létezik! Ha nincs megoldás, a mezőkbe írjon "-" jelet! = ![]() | |||||||||||||||
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!)
![]() |