|
|
künstliches Optimierungssystem
I. Charakterisierung: Jedes mathematische Optimierungssystem der Form
das als Hilfssystem dazu dient, zu einem NN-Gleichungssystem
eine zulässige kanonische Form und damit eine zulässige Basislösung für dieses System ((2´),(3´)) zu ermitteln bzw. nachzuweisen, daß eine derartige Lösung nicht existiert.
II. Bezeichnungsweisen: Die Variablen y1, y2, ..., yn werden als künstliche Variablen, y0 als künstliche Zielvariable, die Funktion (1) als künstliche Zielfunktion und die Zahl y0*, die jedem Vektor (x1*, x2*, ..., xn*, y1*, y2*, ..., yn*) von Zahlen x1*. x2*, ..., xn*, y1*, y2*, ..., yn*, insbes. auch jeder Lösung von ((2), (3)) durch die Funktion (1) zugeordnet ist, als künstlicher Zielwert bezeichnet.
III. Optimale Lösungen: 1. Auf das System ((1),(2),(3),(4)) läßt sich nach Umformung von (1) in eine Zielgleichung und Eliminierung der künstlichen Variablen y1, y2, ..., ym daraus (indem man (1) durch die Summe von (1) und des (-1)-fachen sämtlicher Gleichungen von (2) ersetzt) sofort der primale Simplexalgorithmus zur Bestimmung einer optimalen Lösung anwenden. - 2. Das System ((1),(2),(3),(4)) hat immer eine optimale Lösung. - 3. Ist der (künstliche) Zielwert dieser Lösung größer als Null, so hat das ursprüngliche System ((2´),(3´)) überhaupt keine zulässige Lösung. - 4. Ist der künstliche Zielwert dagegen gleich Null, so liegt i. d. R. eine kanonische Form des Optimierungssystems ((1),(2),(3),(4)) vor, bei der sämtliche künstlichen Variablen y1, y2, ..., yn Nichtbasisvariable (und damit gleich Null) sind, bzw. eine derartige Form läßt sich dann stets durch eine Folge primaler Simplexschritte erzeugen. Man streicht daraus die (umgeformte) künstliche Zielgleichung, die Zielvorschrift (4) sowie aus den umgeformten Gleichungen von (2) und aus (3) die künstlichen Variablen. Das verbleibende NN-Gleichungssystem weist zugleich eine kanonische Form von ((2´),(3´)) auf, entsprechend ist die ausgewiesene Basislösung eine (zulässige) Basislösung von ((2´),(3´)).
IV. Ökonomische Bedeutung: K.O. dienen z. B. im Rahmen der Zwei-Phasen-Simplexmethode oder der M-Methode zur Erzeugung einer ersten zulässigen kanonischen Form für ein gewisses betrachtetes lineares Optimierungssystem (kanonisches lineares Optimierungssystem) bzw. für dessen Restriktionssystem (kanonisches lineares Gleichungssystem). Kommerzielle Softwarepakete für lineare Optimierungsprobleme verwenden dagegen andere Techniken, so daß die Behandlung von k.O. in der Literatur zur linearen Optimierung hauptsächlich aus didaktischen Gründen erfolgt.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
