M-Methode

Big-M-Methode. 1. Begriff: Spezielle Technik zur Erzeugung einer ersten zulässigen kanonischen Form für lineare Optimierungssysteme in Normalform. - 2. Ablauf: Die M.-M-Methode verwendet wie die Zwei-Phasen-Simplexmethode ein künstliches Optimierungssystem, allerdings ein solches, bei dem die ursprüngliche Zielfunktion
nicht völlig außer acht gelassen wird, sondern die üblicherweise verwendete künstliche Zielfunktion
wird ersetzt durch
und die Zielvorschrift
wenn x0 zu minimieren ist, bzw. durch
und
wenn x0 zu maximieren ist. - M ist dabei eine "große" Zahl, die bewirken soll, daß die künstlichen Variablen y1, y2, ... , ym unverzüglich, d. h. insbes. vor den übrigen Variablen x1, x2, ... , xn zu Nichtbasisvariablen werden. Ist das erreicht, kann man die künstlichen Variablen mit ihren Koeffizienten aus dem gesamten System eliminieren. Damit ist die Phase 1 beendet, und man macht wie üblich weiter mit der Phase 2. Gelingt es nicht, alle künstlichen Variablen zu Nichtbasisvariablen zu machen, so existiert überhaupt keine zulässige Lösung des betreffenden Systems. Die besondere Berücksichtigung der jeweiligen Zielvorschrift des ursprünglichen Systems von (3) und (4) einerseits, bzw. in (3') und (4') andererseits soll bewirken, daß zu Beginn der Phase 2 nicht nur eine zulässige, sondern bereits eine gute Lösung zur Verfügung steht. - 3. Bedeutung: Die Verwendung sehr großer Zahlen für M im Vergleich zu den übrigen Zielkoeffizienten c1, c2, ... , cn kann zu numerischen Schwierigkeiten führen. Kommerzielle Softwarepakete verwenden deshalb andere Techniken zur Erzeugung einer ersten kanonischen Form.

<< vorheriger Begriff

nächster Begriff>>

M-DAX

M1