A medián probléma megoldása folytonos költséggel hálózatokon

Időpont: 
2015. október 29. 14:15 és 16:00 között
Helyszín: 
H épület 306-os terem
Kategória: 
Előadás
Szervezés: 
BME-egyetem
Kapcsolattartó: 
Optimalizálási Kutatócsoport

Előadó: Kovács Kristóf (BME)

A hálózaton értelmezett vállalatelhelyezési modellek többségében a kereslet a csúcsokba van koncentrálva. Most egy olyan modellt mutatunk be, ahol a hálózat élein is lehet kereslet, valamilyen valószínűségi eloszlás szerint. A cél egy vállalat elhelyezése úgy, hogy a költségünket minimalizáljuk, ahol a költség a vállalat keresleti pontoktól való össztávolságától függ.

A probléma megoldásához E. Carrizosa és R. Blanquero algoritmusátmmutatjuk be, mely egy Korlátozás és Szétválasztás módszert használ DC felbontással és numerikus integrálással számolt korlátokkal. A számításokban az éleken Béta eloszlás szerint történt a kereslet elosztása.

Továbbá bemutatjuk a problémának egy nehezebb változatát, melyben a keresletnek csak egy adott részét kell lefednünk. Így választhatunk mely éleit és csúcsait fedjük le a hálózatnak, hogy minimalizáljuk a költségünket. Ez egy fordított hátizsák problémához vezet, melyben az áruk a hálózat élei és csúcsai, értékük azok költsége az eredeti modellben és a súlyuk az adott áru kereslete.

Ezen probléma megoldására a fent említett algoritmust fejlesztjük tovább. Futtatási eredményeket mutatunk kis hálózatokon.