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

Időpont: 
2018. május 17. 14:15 és 15:45 között
Helyszín: 
H épület 306-os terem
Kategória: 
Előadás
Szervezés: 
BME-egyetem
Kapcsolattartó: 
Differenciálegyenletek Tanszék

Előadó: Tollner Dávid (BME)

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.