Illés Tibor (BME MI)
Szeparábilis konkáv célfüggvényes,
lineáris feltételes minimalizálási feladat megoldásáról
A lineáris
feltételes szeparábilis konkáv minimalizálási feladatot igen gyakran használják
ipari problémák modellezésére. A teljesség igénye nélkül megemlíthetjük a
konkáv hátizsák feladatot; általánosított folyam feladatokat; a vegyiparból
ismert PNS gráfok segítségével megfogalmazható optimalizálási kérdéseket;
termeléstervezési és szállítási modelleket, stb. A
feladat megoldásának több mint 40 éves szakirodalma van, számos algoritmust
fejlesztettek ki erre a feladatra.
A lineáris feltételes szeparábilis konkáv
minimalizálási feladat két érdekes elméleti tulajdonsággal rendelkezik: (i) NP-
teljes feladat, (ii) ha a megoldáshalmaza politóp akkor az optimális megoldás a
politóp csúcsában is felvétetik.
Előadásunkban egy korlátozás és szétválasztás típusú
algoritmust fogalmazunk meg felhasználva a lineáris programozás érzékenységvizsgálatát.
Időpont: nov. 23. kedd 16:15 Helye: BME, K épület alagsor 66.