Operációkutatás gazdaságinformatikusoknak
Tartalomjegyzék
Bevezetés
Az operációkutatás alapvető elveivel, módszereivel való megismerkedés egy bevezető előadássorozat keretében. A laborgyakorlatokon az operációkutatás rendelkezésre álló szoftvereit és azok gyakorlati feladatok megoldására történő alkalmazási lehetőségeit mutatjuk be. A hallgatók elsajátítják, hogyan lehet operációkutatási algoritmusokra készült számítógépes szoftverekkel gyakorlati alkalmazási feladatokat megoldani. A tárgy elvégzése során lehetőség nyílik saját, önálló szoftverek fejlesztésére és azokkal történő feladatmegoldásokra is.
Házi feladatok
A tárgyból 4 db házi feladat van, ezek mindegyikét legalább elégségesre kell teljesíteni az aláírás megszerzéséhez. A kapott jegyek átlagai beleszámítanak az év végi jegybe. Mindenki egyéni feladatot kap, e-mailben kell beadni a megadott határidőig. Késés esetén rosszabb jegyet ad (késés függvényében). Az első két házi viszonylag könnyebb, az utolsó kettőt a félév végén adja már ki, amikor egyébként is sok más dolog van. Ezeknek a kijavítása mindig vizsgaidőszakra csúszik.
- házi feladat: általános LP feladat matematikai modelljének felírása, a feladat megoldás Excel Solver segítségével, majd az eredmény elemzése (érzékenységvizsgálat).
- házi feladat: egy szállítási feladat megoldása GAMS-ban az XPRESS-MP megoldóval megoldani. A fájlokat kell beküldeni, matematikai modellt felírni, árnyékárakról, redukált költségekről írni pár szót.
- házi feladat: egy hozzárendelési feladatot kell AMPL-ben megírni, majd a CPLEX megoldóval megoldani. A fájlokat kell beküldeni, matematikai modellt felírni, illetve az érzékenységvizsgálatot megcsinálni.
- házi feladat:egy tanult módszer programozása lesz valamilyen nyelven (ez lehet C/C++, Java, Pascal, stb. és akár Matlab kód is). A lehetséges módszerek: Szimplex módszer, Disztribúciós módszer, Magyar módszer, B&B hátizsák feladatra, Duál szimplex. Minden nyelvhez korlátozott számú feladatot tud adni, ezért jelentkezési sorrendben kapjuk a feladatokat, érdemes több nyelvet is megjelölni.
Vizsga
Beugró
A vizsga elején az alábbi módszerekkel meg kell tudni oldani egy kapott feladatot: szimplex, kétfázisos szimplex, duál szimplex, magyar módszer, disztribúciós szimplex, és a korlátozás és szétválasztás módszer hátizsák feladatra. A feladat viszonylag egyszerű, meg van adva hozzá a módszer is, a lényeg, hogy lássa, érted és tudod alkalmazni az adott algoritmust.
Tételek
- Általános lineáris programozási feladat (kb. 3.1 kivéve 56.o.) Grafikus megoldás (3.2,3.3).
- Lineáris programozási feladatokra vezető gazdasági modellek (3.6,3.8,3.10,3.11).
- Lineáris programozási feladatok különböző alakjai. (4.1, a kanonikus alak nincs a könyvben, csak órai jegyzetben!) Elemi bázis transzformáció, bázismegoldás. (4.2) Szimplex módszer normál feladatra (4.3).
- Alternatív optimumok, nem korlátos feladat, degeneráció. (4.5, 4.6, 4.7 vagy Ferenczi 31-35.o) Kétfázisú szimplex módszer (4.9).
- Grafikus érzékenységvizsgálat (5.1) Képletek (5.2) Érzékenységvizsgálat (5.3).
- A duál feladat felírása. (5.4 222.o-ig) A duál feladat értelmezése. (5.5) Gyenge dualitási tételek (5.6 233.o-ig).
- Erős dualitási tétel (5.6 233.o-tól) Gazdasági értelmezés: árnyékárak.(5.7) Dualitás és érzékenységvizsgálat (5.8).
- Általános feladat duálisa (5.4 222.o-tól), Komplementaritási tétel (5.9), Duál szimplex algoritmus (5.10).
- A kiegyensúlyozott és nem kiegyensúlyozott szállítási feladat, tiltótarifa. (6.1), Bázismegoldás keresése (6.2) A szállítási feladat szimplex táblája, disztribúciós módszer. Optimalitás kritérium. (6.3)
- Összetett szállítási feladat. (6.6) Hozzárendelési feladat. Magyar módszer (6.5).
- Hálózati alapmodellek (7.1): legrövidebb út (7.2), Minimális költségű hálózati folyam problémák (7.5) Hálózati szimplex módszer (7.7)
- Egészértékű lineáris programozási modellek (8.1). A korlátozás és szétválasztás módszere (8.3, 8.4). Hátizsák feladatra (8.5).
- Korlátozás és szétválasztás módszere gépütemezésre (8.6), Sztochasztikus készletmodellek - Újságárus probléma (15.1-15.4)
- Általános lineáris programozási feladat (kb. 3.1 kivéve 56.o.) Grafikus megoldás (3.2,3.3).
- Lineáris programozási feladatokra vezető gazdasági modellek (3.6,3.8,3.10,3.11).
- Lineáris programozási feladatok különböző alakjai. (4.1, a kanonikus alak nincs a könyvben, csak órai jegyzetben!) Elemi bázis transzformáció, bázismegoldás. (4.2) Szimplex módszer normál feladatra (4.3).
- Alternatív optimumok, nem korlátos feladat, degeneráció. (4.5, 4.6, 4.7 vagy Ferenczi 31-35.o) Kétfázisú szimplex módszer (4.9).
- Grafikus érzékenységvizsgálat (5.1) Képletek (5.2) Érzékenységvizsgálat (5.3).
- A duál feladat felírása. (5.4 222.o-ig) A duál feladat értelmezése. (5.5) Gyenge dualitási tételek (5.6 233.o-ig).
- Erős dualitási tétel (5.6 233.o-tól) Gazdasági értelmezés: árnyékárak.(5.7) Dualitás és érzékenységvizsgálat (5.8).
- Általános feladat duálisa (5.4 222.o-tól), Komplementaritási tétel (5.9), Duál szimplex algoritmus (5.10).
- A kiegyensúlyozott és nem kiegyensúlyozott szállítási feladat, tiltótarifa. (6.1), Bázismegoldás keresése (6.2) A szállítási feladat szimplex táblája, disztribúciós módszer. Optimalitás kritérium. (6.3)
- Összetett szállítási feladat. (6.6) Hozzárendelési feladat. Magyar módszer (6.5).
- Hálózati alapmodellek (7.1): legrövidebb út (7.2), Minimális költségű hálózati folyam problémák (7.5) Hálózati szimplex módszer (7.7)
- Egészértékű lineáris programozási modellek (8.1). A korlátozás és szétválasztás módszere (8.3, 8.4). Hátizsák feladatra (8.5).
- Korlátozás és szétválasztás módszere gépütemezésre (8.6), Sztochasztikus készletmodellek - Újságárus probléma (15.1-15.3)
