|
|
kanonisches lineares Optimierungssystem
lineares Optimierungssystem in kanonischer Form.
I. Charakterisierung: Jedes lineare Optimierungssystem der Form
bzw. jedes Optimierungssystem, das sich durch Umstellen der Reihenfolge von Restriktionen und/oder Umbenennen von Variablen auf diese Form bringen läßt. - Merkmale: a) In jeder der Gleichungen des Systems ((1), (2)) kommt (mindestens) eine Variable vor, deren Koeffizienten nur in dieser Gleichung den Wert Eins, in den übrigen Gleichungen den Wert Null annehmen (d. h. im System ((1), (2)) die Variablen x0, x1, x2, ..., xm). x0 tritt stets in der Gleichung (1) mit dem Koeffizienten 1 auf, deshalb können die übrigen Variablen (hier x1, x2, ..., xm) mit der beschriebenen Eigenschaft in der Gleichung (1) nur mit dem Koeffizienten Null auftreten. - b) Im Teilsystem (3) ist für jede der Variablen x1, x2, ..., xn, nicht aber für x0 eine Nichtnegativitätsbedingung angegeben.
II. Bezeichnungsweisen: 1. Genau m Variablen, die in bezug auf das System (2) die unter Punkt I. a) aufgeführte Eigenschaft aufweisen, bezeichnet man als gebundene Variablen oder Basisvariablen, die übrigen als freie Variablen oder Nichtbasisvariablen (kanonisches lineares Gleichungssystem). - 2. Gleichung (1) nennt man die zu dem kanonischen Optimierungssystem gehörende modifizierte Zielgleichung, die Koeffizienten a0j, j = 1, 2, ..., n modifizierte Zielkoeffizienten.
III. Zulässige und optimale k. l. O.: 1. Ein k. l. O. nennt man (primal) zulässig, wenn alle rechten Seiten b1, b2, ..., bm des Systems (2) nicht negativ sind. - 2. Ein kanonisches lineares Maximierungssystem (Minimierungssystem) nennt man dual zulässig, wenn die modifizierten Zielkoeffizienten a0j, j = 1, ..., n kleiner (größer) oder gleich Null sind. - 3. Ein k. l. O. nennt man optimal, wenn es primal und dual zulässig ist.
IV. Lösungen: Aus einem primal zulässigen k. l. O. läßt sich sofort eine zulässige Lösung des Systems, die zugehörige Basislösung, in bezug auf das System ((1), (2), (3), (4)) ablesen:
Der Zielwert x0 dieser Lösung ist gleich b0. Ist das kanonische System primal und dual zulässig (d. h. optimal), so handelt es sich bei (2) um eine optimale Lösung des Systems ((1), (2), (3), (4)).
V. Ökonomische Bedeutung: Bei der Bestimmung von optimalen Lösungen für lineare Optimierungsprobleme (etwa mit Hilfe der Zwei-Phasen-Simplexmethode) erstellt man für die betreffenden Optimierungssysteme bzw. für geeignete Hilfssysteme nach gewissen Regeln eine Folge von linearen Optimierungssystemen in kanonischer Form. Dabei gelangt man nach der Konstruktion einer endlichen Anzahl derartiger Systeme entweder zu der Erkenntnis, daß keine optimale Lösung existiert, oder aber zu einem optimalen kanonischen Optimierungssystem, aus dem sich eine optimale Lösung des ursprünglichen Systems sowie der zugehörige Zielwert ablesen lassen.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
