ALKALMAZOTT MATEMATIKAI LAPOK 12. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1986)

1986 / 1-2. sz. - Klafszky Emil és Terlaky Tamás: Magyar módszer típusú algoritmusok lineáris programozási feladatok megoldására

Alkalmazott Matematikai Lapok 12 (1986) 1—14 MAGYAR MÓDSZER TÍPUSÚ ALGORITMUSOK LINEÁRIS PROGRAMOZÁSI FELADATOK MEGOLDÁSÁRA KLAFSZKY EMIL—TERLAKY TAMÁS Miskolc Budapest Cikkünkben két új algoritmust közlünk lineáris programozási feladatok megoldására. Ezek a módszerek a Magyar Módszer és a véges criss-cross módszer alapötletét használják fel. DANTZIG— FORD—FULKERSON [3] primál-duál módszeréhez hasonlóan egy (primál vagy duál) megengedett meg­oldást javítunk fokozatosan, miközben TERLARY [9, 10] criss-cross módszerét használjuk az adódó részfeladatok megoldására. Mindkét algoritmus végességét bizonyítjuk. Megmutatjuk, hogy algoritmusaink speciális eseteiként adódik a primál, illetve duál szimplex módszer azon változata, mikor a ciklizálás elkerülésére degenerált esetben a BLAND [2] féle pivotálási szabályt alkalmazzuk, így eljárást adunk arra is, miként származtatható TERLARY [9. 10] cross-cross módszeréből a primál és duál szimplex módszer. 1. Bevezetés Algoritmusaink a Magyar Módszer ötletén alapulnak, és a criss-cross [9] módszer speciális eseteit használják fel az adódó részfeladatok megoldásában. A Magyar Módszer ötlete az alábbi: Vegyünk egy primál duál feladatpárt és a hozzá tartozó komplementaritási feltételeket. Egy primál megengedett megoldásból indulva, ehhez komplementáris duál megoldást konstruálunk. Az algoritmus egyes lépéseiben a primál megengedett megoldást úgy javítjuk, a duál megoldást úgy módosítjuk, hogy a primál célfüggvény értéke határozottan javul, miközben a komplementaritási fel­tételek fennállnak. Ezt a javítást addig ismételjük, míg a duál feltételek is teljesülnek, azaz míg optimális megoldást nem kapunk. Algoritmusainkban a Magyar Módszer fent közölt általános alapötletét, nem pedig konkrét gráfelméleti tartalmát használ­tuk fel. A Magyar Módszer elnevezést indokolja az is, hogy a gráfelméleti Magyar Módszerben megszokott König—Hall tétel helyett az ennek megfelelő Farkas tételt használjuk algoritmusainkban. A Farkas tételben használt alternatívák előállítására a criss-cross módszer speciális eseteit használjuk fel. Bizonyítjuk algoritmusaink végességét. Bemutatjuk, miként adódik a pri­mál, illetve duál szimplex módszer egy változata a fenti algoritmusok speciális ese­teként. Ezen szimplex módszerek a BLAND [2] féle pivotálási szabályt alkalmazzák degeneráció esetén, nem degenerált esetben csak a bázisba be, illetve onnan kikerülő elem választására alkalmazzuk BLAND [2] szabályát. Ezen szimplex módszerek vé­gessége, BLAND [2] bizonyításának adaptálásával, direkt módon is bizonyítható lenne, ez azonban az általunk közölt általánosabb módszerek végességéből is követ­kezik, így lehetővé válik számunkra, hogy a véges criss-cross módszerre alapozva ve­zessük be a szimplex módszer különböző variánsait.­ ­ Alkalmazott Matematikai Lapok 12 (1986)

Next