A Dantzig-Wolfe-féle dekompozíciós algoritmus elmélete és gyakorlati alkalmazása

Előszó

Elméletileg minden lineáris programozási feladat megoldható, ám a számítás végrehajtása gyakran nehézségekbe ütközik. A legnagyobb akadályt a feladat mérete jelentheti.
A lineáris programozási feladatok elektronikus számítógépi megoldásához általában a módosított - szimplex módszert használjuk. Ennél az explicit inverz algoritmusnál számítási ciklusonként egy olyan négyzetes mátrixot /bázisinverzet/ kell transzformálni, melynek mérete körülbelül a feltételek számával egyenlő. Ezt a mátrixot a számítógép belső memóriájában célszerű tartani. Sok gyakorlati problémánál a feltételek száma olyan nagy, hogy ez nem lehetséges.
Ilyenkor a nagy méret miatt amúgyis hosszú számítási idő lényegesen megnő, mert a bázisinverz a háttér memóriába kerül.
G. B. Dantzig és P. Wolfe kidolgoztak egy módszert nagyméretű feladatok megoldására, mely bizonyos strukturális sajátosságok mellett rövidíti a nagy rendszer számítási idejét. Ez egyrészt az iterációk számának csökkentésével, másrészt az egyenletrendszer speciális szerkezetének kihasználásával érhető el. Az eljárás lehetővé teszi a nagyméretű feladatok felbontását és kisebb részfeladatok iteratív megoldása útján történő globális megoldását.
A módszert olyan feladatok megoldására alkották, amelyekben a feltételeknek csak egy kisebb része vonatkozik valamennyi változóra; a feltételek nagyobbik része a változóknak csak egyes csoportjaira jelent korlátozást. Vissza