A már megtárgyalt anyag:
Mátrixok szorzása, invertálása. Az Ax=b, x>=0, c'x-->max feladat értelmezése.
Megoldás előállítása inverz mátrix segítségével. Optimalitás ellenőrzése.
Bázismegoldás fogalma.
Adott bázis esetén a szimplex tabló felírása és értelmezése.
A nemkorlátos célfüggvény esetének felismerése a szimplex tablóból.
Tétel, mely szerint ha A egy m-szer n-es méretű mátrix, melyhez van olyan x, hogy Ax=b,
akkor rank(A)=m esetén van olyan olyan m-szer m-es B invertálható almátrixa A-nak,
hogy B inverze és b szorzatából is Ax=b valamely megoldását nyerjük. (Ez bázismegoldás lesz.)
Tétel, mely szerint ha A egy m-szer n-es méretű mátrix, melyhez van olyan x>=0, hogy Ax=b,
akkor rank(A)=m esetén van olyan olyan m-szer m-es B invertálható almátrixa A-nak,
hogy B inverzének és b-nek szorzata >=0.
Tétel, mely szerint ha az Ax=b, x>=0, c'x-->max feladatnak van optimális megoldása,
akkor rank(A)=m esetén az (egyik) optimális megoldás a fentiek szerint valamely B inverzéből is megkapható.
A szimplex tabló fogalma, szerkezete és tulajdonságai.
A lexikografikusan kisebb és nagyobb, lexikografikusan pozitív és
lexikografikusan negatív fogalma. Lexikografikusan pozitív szimplex tabló,
és pivotálás a lexikografikus pozitivitás megtartásával.
A lexikografikus szimplex algoritmus,
mely egy lexikografikusan pozitív szimplex tablóból
kiindulva előállít egy optimális bázismegoldást, vagy m+1 oszlopvektort,
melyekre vonatkoztatva is nemkorlátos már a célfüggvény.
A kétfázisú lexikografikus szimplex algoritmus, mely előbb előállít egy lexikografikusan
pozitív szimplex tablót, ha egyáltalán van ilyen, aztán elvégzi a fentemlített
lexikografikus szimplex algoritmust. A kisebbegyenlő és nagyobbegyenlő jeleket tartalmazó
lineáris programozási feladatok átalakítása standard alakra, és megoldásuk kétfázisú
lexikografikus szimplex algoritmussal. Annak megállapítása, hogy három féle output lehetséges:
1. egy optimális bázismegoldás explicit előállítása (ha több is van, csak valamelyik);
2. legfeljebb m+1 ismeretlennek pozitív értékadás paraméter segítségével úgy,
hogy tetszőleges célfüggvényérték elérhető a paraméter alkalmas megválasztásával;
3. bizonyíték a kétfázisú algoritmus első fázisával, hogy egyáltalán nincs megengedett megoldása az eredeti feladatnak.
Gyakorlati alkalmazások és a szimplex algoritmus.
Árnyékárak értelmezése. Duális feladatok felírása.
Kapcsolat az egyenlőtlenségfeltételű
duális feladatpár célfüggvényértékei között.
Megállapítás: Duális duálisa ekvivalens az eredetivel.
Megállapítás: Nemkorlátos célfüggvényű lineáris programozási feladat
duálisának nincs megengedett megoldása.
Dualitási tételek három szintje: 1. ha egy feladatnak van optimális megoldása,
akkor a duálisának is; 2. a két feladat optimális célfüggvényértéke megegyezik;
3. az optimális megoldások rendelkeznek azzal a tulajdonsággal,
hogy ha az egyik feladatban egy optimális megoldás ,,lazán''
teljesít egy egyenlőtlenséget,
akkor a másikban a ,,laza'' egyenlőtlenségnek
megfelelő ismeretlen kötelezően nulla.
A dualitási tételek felhasználása az optimális megoldás megkeresésében.
Részletezés:
Primál alakú feladat (azaz Ax<=b, x>=0, c'x-->max); duál alakú feladat (A'y>=c, y>=0, b'y-->min).
Annak megállapítása, hogy ha a két feladat közül az egyiknek nemkorlátos a célfüggvénye, akkor a másiknak nincs
megengedett megoldása. Ha mindkét feladatnak van megengedett megoldása, akkor mindkét feladatnak van
optimális megoldása is. Ha legalább az egyiknek van optimális megoldása,
akkor a másiknak is. Ha az Ax<=b, x>=0, c'x-->max feladatnak x* optimális megoldása, a duálisának
pedig y* az optimális megoldása, akkor c'x*=b'y*, sőt ahol ,,lazaság'' van az Ax*<=b, x*>=0
egyenlőtlenségekben, ott a megfelelő y*-komponens nulla illetve a megfelelő, y*-ra vonatkozó egyenlőtlenség szoros, és ahol lazaság van a duális
feladat egyenlőtlenségeiben, ott a megfelelő x*-komponens nulla illetve a megfelelő, x*-ra vonatkozó egyenlőtlenség szoros.
Kétszemélyes, nulla összegű mátrixjátékok. Nyereg a mátrixban olyan elem,
mely a saját sorában legkisebb, a saját oszlopában a legnagyobb. Kevert stratégia
egy olyan x>=0 vektor egy M mátrixhoz, hogy x komponenseinek összege 1, és az x'M szorzat
képezhető. Ez Soros "Bicska" Maxi kevert stratégiája. Gipsz Ilonka - a másik játékos - kevert stratégiája egy olyan
y>=0 vektor, melynek komponensei összeadva szintén 1-et tesznek ki, és az My szorzat képezhető.
Ha az x'M-beli és az My-beli nyereg egyenlő, akkor x és y is optimális kevert stratégia.
Margittai Neumann János Lajos (=John Vonneumann)
híres tétele szerint minden M mátrixhoz vannak ilyen optimális stratégiák.
Optimális stratégiák kiszámítása grafikus módszerrel olyan esetekben, amikor a sorok száma (1 vagy) 2,
illetve amikor az oszlopok száma (1 vagy) 2.
Általános mátrixra a maximin (mint legnagyobb sorminimum) és minimax (mint legkisebb oszlopmaximum)
értelmezése, kiszámítása. Tény: az optimálisan kevert sorok illetve oszlopok (azaz x'M és My)
nyereg értékei a maximin és a minimax között vannak.
A lexikografikus duál szimplex módszer.
Annak megállapítása, hogy ez a módszer duál alakú feladatokon mindig működik, ha a minimalizálandó célfüggvényben nincs negatív együttható.
Annak megállapítása, hogy vagy optimális megoldást nyerünk, vagy nincs megengedett megoldás.
Az egészértékű megengedett megoldás igényének feltételek közé írása Gomory vágás segítségével.
A szállítási feladat. Heurisztikus megoldás sorredukcióval, oszlopredukcióval, Voge-Korda-féle mohó
módszerrel. A heurisztikus megoldás ellenőrzése potenciálok segítségével. A magyar módszer az
optimális megoldás megkeresére. A szállítási feladat lineáris programozási feladatként.
A hozzárendelési feladat.
A hátizsák feladat bináris és relaxált változata. A relaxált változat optimális megoldásásának megkeresése.
Becslés (azaz korlátozás) a bináris feladatra a relaxált feladat révén. A szétválasztás fogalma és mikéntje.
A korlátozás és szétválasztás módszere a bináris feladat optimális megoldásának megkeresésére.
A lexikografikus szimplex algoritmus gyors definíciója: http://www.math.bme.hu/~hujter/lexialgo.pdf
A pivotálás hasznáról és módjáról: http://www.math.bme.hu/~hujter/pivot.pdf
A pivotálást segítő programról: http://www.math.bme.hu/~hujter/magyar.txt
A pivotálást segítő program letöltése: http://www.math.bme.hu/~hujter/gjep.zip
Egy szöveges feladat megoldása és az eredmény értelmezése: http://www.math.bme.hu/~hujter/kv.pdf
Prékopa András egy KöMaL-dolgozata 1998-ból (mely a http://db.komal.hu/scan/ helyen is megtalálható): http://picasaweb.google.hu/Hujter.Misi/P#slideshow/5387584047925791090
Konkrét feladatok megoldásokkal: http://picasaweb.google.hu/Hujter.Misi/Ybl#slideshow/5276354852736821186
Második zárthelyi (50 perces) várható időpontja: 09.11.23, 7:50 és 10:10 között. (Aba Abigéltől Kurucz Zsuzsannáig 8:50-re jönnek, a többiek 7:50-re.)
