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.