Modellek és megoldási módszerek a keverési feladatra

Időpont: 
2018. 05. 17. 14:15
Hely: 
BME H. épület 306-os terem
Előadó: 
Tollner Dávid - BME

   

 

                                 MEGHÍVÓ

           Szeretettel meghívjuk Tollner Dávid előadására

              az Optimalizálási Szeminárium keretében

      2018.05.17., csütörtök, 14.15-15.45, BME, H306-os terem

 

 

 

Modellek és megoldási módszerek a keverési feladatra

 

Kémiai anyagok keverési feladatának első operációkutatási modell variánsait Dantzig és szerzőtársai fogalmazták meg több dolgozatban, az 1950-es évek végén. Charnes és Cooper az 1950-es évek elején, a benzin keverési feladatra, ismert minőségi paraméterek esetén, lineáris programozási modelleket írtak fel.

 

Operációkutatási szempontból az általános keverési feladatban ismeretlen mennyiségekhez és minőségekhez kapcsolódó döntési változók szerepelnek. A keverési feladat operációkutatási modelljeiben, jellemzően a lineáris feltételek mellett, bilineáris egyenletek (vagy egyenlőtlenségek) is előfordulnak. A keverési feladat megengedett megoldáshalmaza nem konvex és időnként nem is összefüggő. A keverési probléma globális optimalizálási feladatra vezet.

Az előadásban tárgyalt keverési probléma operációkutatási modelljei lineáris és bilineáris feltételekkel megfogalmazott optimalizálási feladat, ahol forrásokból érkező különböző minőségű nyersanyagokat keverünk össze és a kevert anyagoknak minőségi korlátokat kell teljesíteni az egyes terminálokban. A hálózaton adott keverési feladatokkal kapcsolatos egyik első, fontos eredmény Haverlytől (1978) származik, de a témakörnek az utóbbi 20 évben komoly szakirodalma alakult ki és a gyakorlatban is elterjedtek megoldási módszerek.

Először az általános keverési feladat egymásra épülő P-, Q-, PQ-, TP- és STP-felírásairól lesz szó. A nemlinearitás miatt nem ismerjük a globális optimumot, így az eredmények jóságának a méréséhez bemutatjuk a modellek lineáris relaxációit, ahol a bilineáris feltételt a McCormick-féle konvex és konkáv görbékkel (1976) közelítjük, amiből az optimális megoldásra egy alsó korlátot kapunk. Ezután bemutatásra kerül a javító heurisztika, ami egy megengedett megoldásból indul ki, és addig változtatja a folyamértékeket, amíg egy lokális optimumhoz nem ér. Mivel ez a módszer nagyban függ az indulómegoldástól, így érdemes ezt előállítani más módszerekkel is és vizsgálni a kapott eredményeket. Erre a célra szolgál a bázis konstruáló heurisztika, ami egyszerre egy terminálba küldve épít folyamot. Ebből gyorsan kapunk egy megengedett megoldást, de vannak felesleges szigorítások, amiket a továbbfejlesztett változatában, a konstruáló heurisztikában már elhagyunk.

Végül beszámolunk a tesztpéldák különböző módszerekkel történő megoldásáról, a kapott numerikus eredményekről.