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.

fõoldal