Optimalizálás Felsőfokon 2023 ősz

Tárgyleírás

Az (egészértékű) lineáris programozás, mint modellezési eszköz számos esetben hatékony megoldást és mély megértést szolgáltat gráfelméleti/hálózatkutatási problémákhoz. Az utóbbi évtizedekben számos olyan megoldási módszert javasoltak a szakirodalomban, amelyeket aztán egyre többször látni a tudományos cikkekben, alkalmazásokban. Ezen módszerek jelentős része, idő hiányában, már kimarad a kötelező és szakirányos kurzusok tematikájából. Az Optimalizálás Felsőfokon kurzus így ezt a hiányt pótolja. Tamás anyagai a honlapon találhatóak.

1. óra: Bevezetés a matematikai programozásba. Elevenítsük fel a folytonos és az egészértékű programozásban tanultakat, jegyzet. Legfrissebb jegyzet az overleafen

2. óra: Gyorstalpaló az AMPL-hez és modellezéshez: oldjunk meg egy kis gyártási feladatot! majd gyakorlásként egy z összetett gyártási feladatot.

3. óra: Modellezési trükkökhöz oldjuk meg az összetett gyártási feladat,

4. óra: Fejezzük be a modellezési trükköket: nézzük meg hozzá az illesztési feladatot.

Alternatív feltételek: több feltétel adott, azokból nem kell mindnek teljesülnie, de legalább egynek. Hogyan modellezhető?
Mi van, ha azt akarjuk, hogy pontosan az egyik teljesüljön csak?
Ezt lehet általánosítani? N feltétel van, legalább/legfeljebb vagy pontosan K teljesüljön.
Ha akkor tipusú feltételek? pl: Ha gyártunk egy terméket, legalább valamennyit gyártsunk.
Bilineáris tagok: decentralizálási feladatot

Összegezve a modellezési trükkök itt
Vagy hosszabban kicsit másképp itt összefoglalva

5. óra: TUM, slide-ok, jegyzet

6. óra: Feltételgenerálás. TSP feladat, matematikai modellnek a felírása táblán, modell az összes feltétellel: tsp0.mod, adatok: tsp.dat, futtató file: tsp0.run. Nagy adatfile, nagy adatfile részlet, hány feltétel lenne?
Manuális kiskör kizárás: tsp.mod, tsp.run.
Automatikus feltételgenerálás: futtató file automatikus kiskör kizárással (a mod file ugyanaz). futtató file az ÖSSZES kiskör kizárásával (ezt nem néztük)

7. óra: Oszlopgenerálás. Feladat, Megértéshez angol nyelvű fóliák. adat, modell, futtató fájlok.>

8.óra: Branch-and-cut

9.óra: Lagrange duális
10. óra: Bender's dekompozíció. fóliák. extrém sugarak
11. óra: Dantzig-Wolfe dekompozíció. jegyzet fóliák

AMPL letöltése

Hasznos linkek, irodalom:

G.-Tóth Boglárka: Optimalizálási Rendszerek és Matematikai Modellezés példákon keresztül vagy innen
Az AMPL-hez egy angol bevezető és egy hosszabb leírás sok példával a végén szintén angolul.
Az AMPL könyv elérhető itt.
Használjunk AMPL-t colab-on keresztül. https://colab.ampl.com/
Érzékenységvizsgálat AMPL-ben kidolgozott példával: feladat, mod, dat, run, érzékenységvizsgálat eredménye