Content

25. Lineare Optimierung in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 753 - 788

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_753

Bibliographic information
Kapitel25 Lineare Optimierung Kapitel 25 Lineare Optimierung 25.1 Grundlagen L. W. Kantorowitsch Die lineare Optimierung wird häufig auch als lineare Programmierung bezeichnet und ist eine der bedeutendsten Theorien des Operations Research, also dem Wissenschaftsgebiet, das sich speziell mit der Entwicklung und Anwendung quantitativer Modelle und Methoden zur Entscheidungsunterstützung beschäftigt. Zu den Begründern der linearen Optimierung zählen der sowjetische Mathematiker und Ökonom Leonid Witaljewitsch Kantorowitsch (1912–1986) und der US-amerikanische Ökonom und Physiker Tjalling Koopmans (1910–1985). Für ihre Theorie zur optimalen Verwendung knapper Ressourcen erhielten sie im Jahre 1975 den Wirtschaftsnobelpreis. T. Koopmans Zielsetzung der linearen Optimierung ist die Minimierung oder Maximierung einer linearen Zielfunktion mit n Variablen der Form z(x1, . . . , xn) := c1x1 + . . .+ cnxn unter Einhaltung einer Reihe von Nebenbedingungen. Diese können gegeben sein durch lineare Gleichungen der Gestalt ai1x1 + . . .+ ainxn = bi für i = 1, . . . , p und lineare Ungleichungen der Form aj1x1 + . . .+ ajnxn ≤ bj oder ak1x1 + . . .+ aknxn ≥ bk für j = 1, . . . , q und k = 1, . . . , r . Solche Problemstellungen werden unter der Bezeichnung lineare Optimierungsprobleme zusammengefasst, wobei man je nach Minimierung oder Maximierung der Zielfunktion auch genauer von linearem Minimierungsproblem bzw. linearem Maximierungsproblem spricht. Die lineare Optimierung zeichnet sich vor allem dadurch aus, dass sie eine einfache Modellbildung und effiziente Verfahren zur Lösung von linearen Optimierungsproblemen mit bis zu mehreren hunderttausend Variablen und Nebenbedingungen bereitstellt. Aus diesem Grund besitzt die lineare Optimierung für die verschiedensten wirtschaftswissenschaftlichen Bereiche eine große praktische Bedeutung. Sie kommt zum Beispiel in der Spieltheorie, der Produktionsplanung, der Portfoliooptimierung und bei der Lösung von Tourenplanungs-, Mischungs- und Verschnittproblemen zum Einsatz. Darüber hinaus wird die lineare Optimierung häufig auch bei der Lösung mehrdimensionaler nichtlinearer Optimierungsprobleme herangezogen. In den folgenden drei Beispielen werden verschiedene, aber typische lineare Optimierungsprobleme aus den Wirtschaftswissenschaften vorgestellt, um die große Bandbreite der Anwendungsmöglichkeiten der linearen Optimierung zu demonstrieren. Beim ersten Beispiel handelt es sich um ein lineares Minimierungsproblem, das als Transportproblem bezeichnet wird. Es besteht darin, den Transport eines Produktes von mehreren Angebots- zu mehreren Nachfrageorten in optimaler, d. h. kostenminimaler, Weise durchzuführen. Beispiel 25.1 (Lineares Minimierungsproblem: Transportproblem) Betrachtet wird ein Unternehmen mit zwei Filialen F1 und F2, von denen aus drei Großhändler G1,G2 und G3 beliefert werden sollen. Die Transportkosten je Mengeneinheit von den Filialen zu den Großhändlern, der Bedarf der Großhändler und der Lagerbestand der Filialen sind bekannt und in der folgenden Tabelle zusammengefasst: Transportkosten je Mengeneinheit G1 G2 G3 Bestand F1 0,8 1,0 1,2 600 F2 0,4 0,5 0,6 400 Bedarf 200 500 300 1000 Das Unternehmen ist daran interessiert, den Transport von den Filialen zu den Großhändlern so zu organisieren, dass die Gesamttransportkosten minimal sind. Dieses Transportproblem lässt sich als lineares Minimierungsproblem formulieren. Hierzu bezeichnen die Variablen x1,x2,x3 die Transportmengen von F1 zu G1,G2,G3 und x4,x5,x6 die Transportmengen von F2 zu G1,G2,G3. 760 Kapitel 2525.1 Grundlagen Da Transportmengen nicht negativ sein können, müssen für diese Variablen die Nichtnegativitätsbedingungen x1, . . . , x6 ≥ 0 erfüllt sein. Aufgrund der Annahme von mengenproportionalen Transportkosten von den Filialen zu den Großhändlern sind die Gesamttransportkosten durch den Wert der linearen Zielfunktion z(x1, . . . , x6) = 0,8x1 + x2 + 1,2x3 + 0,4x4 + 0,5x5 + 0,6x6 gegeben. Bei der Minimierung dieser Zielfunktion muss jedoch sichergestellt sein, dass der Bedarf der drei Großhändler gedeckt wird und gleichzeitig die Nachfrage der Kapazität der beiden Filialen entspricht. Aus diesen Anforderungen ergibt sich insgesamt das folgende lineare Optimierungsproblem: Minimiere z(x1, . . . , x6)=0,8x1+x2+1,2x3+0,4x4 + 0,5x5 + 0,6x6 (25.1) unter den Nebenbedingungen x1+x2+x3 = 600 x4+x5+x6 = 400 x1 +x4 = 200 (25.2) x2 +x5 = 500 x3 +x6 = 300 und den Nichtnegativitätsbedingungen x1, . . . , x6 ≥ 0. (25.3) Durch die ersten beiden Gleichungen in (25.2) wird sichergestellt, dass die in den beiden Filialen F1 und F2 verfügbaren Bestände vollständig an die drei Großhändler G1,G2 und G3 ausgeliefert werden und die letzten drei Gleichungen in (25.2) sorgen dafür, dass der Bedarf der drei Großhändler gedeckt wird. Gesucht ist also eine Lösung des linearen Gleichungssystems (25.2) der Nebenbedingungen, welche die Nichtnegativitätsbedingungen (25.3) erfüllt und die lineare Zielfunktion (25.1) minimiert. Beim zweiten Beispiel handelt es sich um ein lineares Maximierungsproblem aus der Portfoliooptimierung: Beispiel 25.2 (Lineares Maximierungsproblem: Portfoliooptimierung) Es wird ein Unternehmen betrachtet, das aus vier verschiedenen Anlagen A1, A2, A3 und A4 ein Portfolio bilden möchte. Diese Anlagen unterscheiden sich in den erwarteten jährlichen Renditen und in ihrem Risiko, das durch eine Risikokennzahl ausgedrückt wird. Anlage A1 A2 A3 A4 Erwartete Rendite in % 3 5 10 20 Risikokennzahl 1 2 4 8 Für das konstruierte Portfolio soll dabei gelten, dass a) es eine möglichst hohe erwartete Rendite aufweist, b) mindestens 40% in die Anlage A1 investiert wird und c) die Risikokennzahl des gesamten Portfolios nicht größer als 4 ist. Hierzu bezeichnen die Variablen x1, x2, x3, x4 die Anteile der Anleihen A1, A2, A3 bzw. A4 im Portfolio. Da Anteile nicht negativ sein können, müssen für diese Variablen die Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0 erfüllt sein. Die Rendite des Portfolios ist durch den Wert der linearen Zielfunktion z(x1, x2, x3, x4) = 0,03x1 + 0,05x2 + 0,1x3 + 0,2x4 gegeben. Bei der Maximierung dieser Zielfunktion ist zu berücksichtigen, dass nur Portfolios erlaubt sind, die den beiden Voraussetzungen b) und c) genügen. Dies führt zu dem folgenden linearen Optimierungsproblem: Maximiere z(x1, x2, x3, x4)= 0,03x1+0,05x2+0,1x3 +0,2x4 (25.4) unter den Nebenbedingungen x1+ x2+ x3+ x4 = 1 x1 ≥ 0,4 (25.5) x1+2x2+4x3+8x4 ≤ 4 761 Kapitel 25 Lineare Optimierung und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. (25.6) Durch die Gleichung in (25.5) wird sichergestellt, dass die Summe der Anteile der vier Anleihen gleich Eins ist, und die zwei Ungleichungen in (25.5) stellen sicher, dass die beiden Voraussetzungen b) und c) erfüllt werden. Gesucht ist also eine Lösung des Systems (25.5) bestehend aus einer Gleichung und zwei Ungleichungen, welche die Nichtnegativitätsbedingungen (25.6) erfüllt und die lineare Zielfunktion (25.4) maximiert. Beim dritten und letzten Beispiel handelt es sich um ein sogenanntes Verschnittproblem, bei dem der Verschnitt beim Zuschneiden von Stahlblech minimiert werden soll: Beispiel 25.3 (Lineares Minimierungsproblem: Verschnittproblem) Betrachtet wird ein Betrieb der stahlverarbeitenden Industrie, der Stahlblech von 1,90 m Breite bezieht und es für verschiedene Auftraggeber auf andere Breiten zuschneidet. Aufgrund der gegebenen Auftragslage möchte der Betrieb im kommenden Jahr mindestens 30.000 m zu 0,90 m Breite, mindestens 60.000 m zu 0,70 m Breite und genau 70.000 m zu 0,60 m Breite zuschneiden. Dies soll dabei so geschehen, dass möglichst wenig Verschnitt anfällt. Die folgende Tabelle gibt alle sechs möglichen Schnittkombinationen und den zugehörigen Verschnitt an: Schnittkombinationen 1 2 3 4 5 6 0,90 m Breite 2 1 1 0 0 0 0,70 m Breite 0 1 0 2 1 0 0,60 m Breite 0 0 1 0 2 3 Verschnitt in m 0,10 0,30 0,40 0,50 0 0,10 Die Entscheidungsvariablen x1, x2, x3, x4, x5, x6 sind die Längen der nach den einzelnen Schnittkombinationen aufgeschnittenen Blechbahnen von ursprünglich 1,90m Breite. Da Längen nicht negativ sein können, müssen für diese Variablen die Nichtnegativitätsbedingungen x1, . . . , x6 ≥ 0 erfüllt sein. Für den Verschnitt erhält man die lineare Zielfunktion z(x1, . . . , x6)=0,1x1 + 0,3x2 + 0,4x3 + 0,5x4 + 0,1x6. Bei der Minimierung dieser Zielfunktion muss jedoch sichergestellt sein, dass der Betrieb im kommenden Jahr mindestens 30.000m zu 0,90m Breite, mindestens 60.000m zu 0,70m Breite und genau 70.000m zu 0,60m Breite zuschneiden möchte. Dies führt zu dem folgenden linearen Optimierungsproblem: Minimiere z(x1, . . . , x6) = 0,1x1 + 0,3x2 + 0,4x3 + 0,5x4 + 0,1x6 unter den Nebenbedingungen 2x1+x2+x3 ≥ 30.000 x2 +2x4+ x5 ≥ 60.000 x3 +2x5+3x6 = 70.000 und den Nichtnegativitätsbedingungen x1, . . . , x6 ≥ 0. 25.2 Graphische Lösung linearer Optimierungsprobleme Lineare Optimierungsprobleme mit nur zwei Entscheidungsvariablen lassen sich relativ einfach graphisch lösen. Da jedoch in den meisten praxisrelevanten Problemstellungen mehr als zwei Entscheidungsvariablen auftreten, besteht die Bedeutung der graphischen Lösung vor allem in der geometrischen Veranschaulichung der Rechenschritte des Simplex- Algorithmus. Der Simplex-Algorithmus ist Gegenstand von Abschnitt 25.4 und stellt das Standardverfahren zur Lösung von linearen Optimierungsproblemen dar. Im folgenden Beispiel wird anhand einer Problemstellung aus der Produktionsplanung gezeigt, wie ein lineares Optimierungsproblem mit nur zwei Entscheidungsvariablen graphisch gelöst werden kann: 762 Kapitel 2525.2 Graphische Lösung linearer Optimierungsprobleme Beispiel 25.4 (Graphische Lösung eines linearen Optimierungsproblems) Ein Betrieb produziert zwei Produkte P1 und P2 mit Hilfe von drei Produktionsfaktoren F1, F2 und F3. Die folgende Tabelle gibt die Produktionskoeffizienten, den Bestand an Produktionsfaktoren sowie den Gewinn je produzierter Einheit an: Produktions- Produkte faktoren P1 P2 Bestand F1 4 3 600 F2 2 2 320 F3 3 7 840 Gewinn 2 3 Bezeichnen die Variablen x1 und x2 die Produktionsmengen der beiden Produkte P1 und P2 und hat der Betrieb die Zielsetzung, dass der Gewinn maximiert werden soll, dann führt dies zu dem linearen Optimierungsproblem: Maximiere z(x1, x2) = 2x1 + 3x2 (25.7) unter den Nebenbedingungen 4x1 + 3x2 ≤ 600 2x1 + 2x2 ≤ 320 (25.8) 3x1 + 7x2 ≤ 840 und den Nichtnegativitätsbedingungen x1, x2 ≥ 0. (25.9) Die beiden Nichtnegativitätsbedingungen (25.9) und die drei Nebenbedingungen (25.8) legen jeweils eine Halbebene im R2 fest. Der Durchschnitt dieser fünf Halbebenen ist eine konvexe Menge (vgl. Beispiel 7.26c) und Satz 7.27) und besteht aus allen x ∈ R2, welche die Bedingungen (25.8) und (25.9) erfüllen. Diese x ∈ R2 werden zulässige Lösungen des linearen Optimierungsproblems genannt und die Menge aller zulässigen Lösungen heißt zulässiger Bereich und ist gegeben durch Z := {x ∈ R2 : 4x1 + 3x2 ≤ 600, 2x1 + 2x2 ≤ 320, 3x1 + 7x2 ≤ 840, x1, x2 ≥ 0 } . Aufgrund der Nichtnegativitätsbedingungen x1, x2 ≥ 0 liegtZ im 1. Quadranten und wird durch die x1-Achse und die x2-Achse begrenzt. Die anderen Begrenzungen von Z sind durch die Geraden 4x1+3x2 = 600, 2x1+2x2 = 320 und 3x1 + 7x2 = 840 festgelegt. Diese ergeben sich aus den drei Nebenbedingungen (25.8), wenn sie jeweils voll ausgeschöpft werden. Für einen festen Wert z0 ∈R+ der Zielfunktion z(x1, x2)= 2x1+3x2 liegen alle x=(x1, x2)T ∈ R2 mit z0 = 2x1+3x2 auf einer Geraden, der sogenannten Iso-Gewinn-Geraden zum Gewinn z0. Die Iso-Gewinn-Geraden zu verschiedenen Gewinnen z0 ∈ R+ sind parallel. Zur Ermittlung der optimalen Lösung x∗ ∈ Z wird zunächst die Iso-Gewinn- Gerade z0 = 2x1 + 3x2 zu einem Gewinn z0 ∈ R+ eingezeichnet, so dass die Gerade durch den zulässigen Bereich Z verläuft. Der Wert der Zielfunktion z(x1, x2) = 2x1+3x2 wächst offensichtlich, wenn man x1 oder x2 erhöht. Daher wird zur Ermittlung des maximalen Gewinns die Iso-Gewinn-Gerade parallel nach rechts oben bis zum Rand des zulässigen Bereichs Z verschoben. Da der zulässige Bereich beschränkt ist, erreicht man auf diese Weise den Eckpunkt x∗, für den die Zielfunktion z(x1, x2) = 2x1 + 3x2 unter allen zulässigen Lösungen x ∈ Z ihr Maximum annimmt. Diese optimale Lösung ist gegeben durch x∗ = (70, 90)T und führt zu dem Gewinnmaximum z(70, 90) = 410. Damit besteht das optimale Produktionsprogramm aus 70 Mengeneinheiten des Produkts P1 und 90 Mengeneinheiten des Produkts P2 (vgl. Abbildung 25.1). Die graphische Lösung eines linearen Optimierungsproblems ist nicht mehr möglich, wenn die Zielfunktion und die Nebenbedingungen von mehr als zwei Variablen abhängen. Das Beispiel 25.4 zeigt jedoch zwei wichtige Charakteristika, die alle linearen Optimierungsprobleme aufweisen. Nämlich, dass der zulässige Bereich Z eine konvexe Menge ist (siehe hierzu den folgenden Satz 25.8) und dass die Zielfunktion z im Falle eines beschränkten zulässigen Bereichs Z ihr globales Maximum (im Falle eines linearen Maximierungsproblems) bzw. ihr globales Minimum (im Falle eines linearen Minimierungsproblems) in einem Eckpunkt x∗ von Z annimmt. Folglich kann man sich bei der Suche nach einer optimalen Lösung darauf beschränken, alle Eckpunkte des zulässigen Bereichs Z zu untersuchen. Der Eckpunkt, welcher eingesetzt in die Zielfunktion z den größten bzw. den kleinsten Wert ergibt, ist dann eine optimale Lösung des linearen 763 Kapitel 25 Lineare Optimierung x1 x2 0 50 100 150 200 0 50 100 150 200 250 300 x* z0 = 120 z0 = 300 z0 = 410 4x1 + 3x2 = 600 3x1 + 7x2 = 840 2x1 + 2x2 = 320 Z Abb. 25.1: Graphische Lösung eines linearen Maximierungsproblems mit zwei Variablen x1 und x2 Maximierungs- bzw. Minimierungsproblems. Da jedoch bei linearen Optimierungsproblemen mit vielen Nebenbedingungen und Entscheidungsvariablen die Anzahl an Ecken sehr groß sein kann, wird ein effizientes Verfahren benötigt, welches es erlaubt, nicht alle möglichen Eckpunkte untersuchen zu müssen, um eine optimale Lösung zu erhalten. Das bekannteste Verfahren dieser Art ist der Simplex-Algorithmus, der in Abschnitt 25.4 vorgestellt wird. Mit ihm kann ein lineares Optimierungsproblem mit beliebig vielen Nebenbedingungen und Variablen auf die Existenz einer optimalen Lösung untersucht und – im Falle der Existenz – eine optimale Lösung bestimmt werden. 25.3 Standardform eines linearen Optimierungsproblems Wie in Abschnitt 25.1 erläutert wurde, treten lineare Optimierungsprobleme als Minimierungs- oder Maximierungsprobleme auf. Ferner können auch die Nebenbedingungen in unterschiedlicher Form gegeben sein, nämlich durch lineare Gleichungen ai1x1 + . . .+ ainxn = bi und lineare Ungleichungen aj1x1 + . . .+ ajnxn ≤ bj oder ak1x1 + . . .+ aknxn ≥ bk. Zur Vereinfachung der weiteren Untersuchungen ist es daher zweckmäßig, die vielfältigen Erscheinungsformen von linearen Optimierungsproblemen dadurch einzugrenzen, dass sie vorab in eine einheitliche Form, die sogenannte Standardform, überführt werden: Definition 25.5 (Lineares Optimierungsproblem in Standardform) Ein lineares Optimierungsproblem ist in Standardform, wenn es von folgender Form ist: Maximiere z(x1, . . . , xn) = c1x1 + . . .+ cnxn unter den Nebenbedingungen a11x1 + a12x2 + . . .+ a1nxn ≤ b1 a21x1 + a22x2 + . . .+ a2nxn ≤ b2 ... ... ... ... (25.10) am1x1 + am2x2 + . . .+ amnxn ≤ bm und den Nichtnegativitätsbedingungen x1, . . . , xn ≥ 0. Alternativ kann ein lineares Optimierungsproblem in Standardform auch in Matrixschreibweise angegeben werden: Maximiere z(x) = cT x 764 Kapitel 2525.3 Standardform eines linearen Optimierungsproblems unter den Neben- und Nichtnegativitätsbedingungen A x ≤ b x ≥ 0. Dabei bezeichnet z die Zielfunktion, c := (c1,. . . ,cn)T ∈Rn den Vektor der n Zielfunktionskoeffizienten und x := (x1, . . . , xn) T ∈ Rn den Vektor der nEntscheidungsvariablen (Strukturvariablen). Ferner ist b := (b1, . . . , bm)T ∈ Rm der Vektor mit den m Werten der rechten Seite und A = (aij )m,n die m× n-Koeffizientenmatrix des linearen Ungleichungssystems (25.10). In den folgenden theoretischen Betrachtungen wird stets davon ausgegangen, dass ein gegebenes lineares Optimierungsproblem in Standardform vorliegt. Das heißt, dass es sich um ein lineares Maximierungsproblem handelt, dessen Nebenbedingungen ausschließlich von der Form aj1x1 + . . .+ ajnxn ≤ bj sind. Diese Annahme stellt keine Einschränkung der Allgemeinheit dar. Denn zum einen ist die Minimierung einer Zielfunktion z äquivalent zur Maximierung der Funktion −z. Zum anderen erhält man aus einer Ungleichung der Form ak1x1 + . . .+ aknxn ≥ bk durch Multiplikation mit −1 die äquivalente Ungleichung −ak1x1 − . . .− aknxn ≤ −bk, und eine Gleichung ai1x1 + . . .+ ainxn = bi kann durch die beiden Ungleichungen ai1x1 + . . .+ ainxn≤bi und − ai1x1 − . . .− ainxn≤−bi ersetzt werden. Folglich können alle linearen Optimierungsprobleme in die Standardform überführt werden, wobei sich dadurch die Menge aller x ∈ Rn, welche die Nebenbedingungen erfüllen, nicht verändert. Beispiel 25.6 (Lineare Optimierungsprobleme in Standardform) a) Das lineare Optimierungsproblem in Beispiel 25.2 lautet in Standardform: Maximiere z(x1, x2, x3, x4) = 0,03x1 + 0,05x2 + 0,1x3 + 0,2x4 unter den Nebenbedingungen x1+ x2+ x3+ x4 ≤ 1 −x1− x2− x3− x4 ≤ −1 −x1 ≤−0,4 x1+2x2+4x3+8x4 ≤ 4 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. b) Das lineare Optimierungsproblem in Beispiel 25.3 lautet in Standardform: Maximiere z(x1, . . . , x6)= −0,1x1 − 0,3x2 − 0,4x3 − 0,5x4 − 0,1x6 unter den Nebenbedingungen −2x1−x2−x3 ≤ −30.000 −x2 −2x4− x5 ≤ −60.000 x3 +2x5+3x6 ≤ 70.000 −x3 −2x5−3x6 ≤ −70.000 und den Nichtnegativitätsbedingungen x1, . . . , x6 ≥ 0. c) Das lineare Optimierungsproblem in Beispiel 25.4 ist bereits in Standardform. Zulässiger Bereich und optimale Lösung Die Begriffe zulässiger Bereich und optimale Lösung sind für ein lineares Optimierungsproblem in Standardform wie folgt definiert: Definition 25.7 (Zulässiger Bereich und optimale Lösung) Die Menge Z := {x ∈ Rn : A x ≤ b, x ≥ 0} heißt zulässiger Bereich eines linearen Optimierungsproblems in Standardform mit rechter Seite b ∈ Rm und m× n-Koeffizientenmatrix A. Die Elemente x ∈ Z werden als zulässige Lösungen bezeichnet und ein x∗ ∈ Z mit z(x∗) ≥ z(x) für alle x ∈ Z wird optimale Lösung des linearen Optimierungsproblems genannt. 765 Kapitel 25 Lineare Optimierung Der zulässige Bereich Z enthält somit alle x ∈ Rn, welche die Nebenbedingungen A x ≤ b und die Nichtnegativitätsbedingungen x ≥ 0 erfüllen, und die optimale Lösung x∗ maximiert die Zielfunktion z innerhalb der Menge Z aller zulässigen Lösungen. Der nächste Satz besagt, dass ein zulässiger Bereich Z die angenehme Eigenschaft besitzt, dass für zwei beliebige x1, x2 ∈ Z stets auch deren Konvexkombinationen in Z liegen. Diese Eigenschaft zulässiger Bereiche ist für die folgenden Betrachtungen von großer Bedeutung: Satz 25.8 (Konvexität von Z) Der zulässige Bereich Z eines linearen Optimierungsproblems ist eine konvexe Menge. Beweis: Es sei x := λx1 + (1 − λ)x2 mit λ ∈ [0, 1] eine Konvexkombination zweier zulässiger Lösungen x1, x2 ∈ Z . Dann folgt A x = A (λx1 + (1 − λ)x2) = λA x1 + (1 − λ)A x2 ≤ λb + (1 − λ)b = b. Das heißt, es gilt A x ≤ b und aus x1, x2 ≥ 0 folgt ferner x ≥ 0. Dies impliziert x ∈ Z und damit auch die Konvexität von Z . Aufgrund dieser Eigenschaft und ihrer speziellen Struktur werden zulässige Bereiche Z auch als konvexe Polyeder bezeichnet (vgl. Abbildungen 25.1 und 25.2 für den Spezialfall Z ⊆ R2) . Eckpunkte Von besonderer Bedeutung für die Lösung linearer Optimierungsprobleme sind die Eckpunkte eines zulässigen Bereichs Z . Diese sind wie folgt definiert: x1 x2 Z x1 x2 Z x1 x2 Z Abb. 25.2: Zulässige Bereiche Z im R2 und ihre Eckpunkte (rot gekennzeichnet) Definition 25.9 (Eckpunkt von Z) Ein x ∈ Z heißt Eckpunkt des zulässigen Bereichs Z , wenn es sich nicht als echte Konvexkombination λx1 + (1− λ)x2 mit λ ∈ (0, 1) zweier verschiedener zulässiger Lösungen x1, x2 ∈ Z darstellen lässt. Das heißt, aus x = λx1 + (1 − λ)x2 mit x1 = x2 und λ ∈ [0, 1] folgt λ = 0 oder λ = 1. Die Abbildung 25.2 zeigt für den Spezialfall Z ⊆ R2 (d. h. für den Fall mit nur zwei Entscheidungsvariablen) zwei beschränkte zulässige Bereiche Z (links und in der Mitte) und einen unbeschränkten zulässigen BereichZ (rechts). Es ist zu erkennen, dass sich in allen drei Fällen die Eckpunkte der zulässigen Bereiche zwar als Konvexkombinationen, aber nicht als echte Konvexkombinationen zweier zulässiger Lösungen darstellen lassen. Das in Beispiel 25.4 betrachtete lineare Optimierungsproblem mit nur zwei Entscheidungsvariablen besitzt eine optimale Lösung x∗, die in einem Eckpunkt des zulässigen Bereichs Z liegt. Das folgende Resultat besagt, dass dies kein Zufall ist und für jedes lineare Optimierungsproblem gilt, das eine optimale Lösung besitzt. Aufgrund seiner Bedeutung wird diese Erkenntnis häufig als Hauptsatz der linearen Optimierung bezeichnet. Satz 25.10 (Hauptsatz der linearen Optimierung) Für ein lineares Optimierungsproblem in Standardform Maximiere z(x)=cT x auf Z={x∈Rn :A x≤b, x≥0} mit Z = ∅ gilt: a) Entweder ist mindestens einer der Eckpunkte des zulässigen Bereichs Z eine optimale Lösung x∗ oder 766 Kapitel 2525.3 Standardform eines linearen Optimierungsproblems die Zielfunktion z ist auf Z nach oben unbeschränkt und es existiert damit keine optimale Lösung. b) Ist der zulässige Bereich Z beschränkt, dann ist mindestens einer der Eckpunkte von Z eine optimale Lösung x∗, und eine zulässige Lösung x ∈ Z ist genau dann optimal, wenn sie sich als Konvexkombination aus Eckpunkten von Z darstellen lässt, die ebenfalls optimal sind. Beweis: Zu a): Angenommen, es existiert ein d ∈ Rn mit d ≥ 0, A d = 0 und cT d > 0. Für eine beliebige zulässige Lösung x ∈ Z und alle t ≥ 0 gilt dann x + td ≥ 0 und A(x + td) = A x + tA d = A x ≤ b, also x + td ∈ Z für alle t ≥ 0. Wegen z(x + td) = cT (x + td) = cT x + tcT d −→ ∞ für t −→ ∞ ist in diesem Fall die Zielfunktion z auf Z nach oben unbeschränkt und es existiert somit keine optimale Lösung. Es sei nun angenommen, dass cT d ≤ 0 für alle d ∈ Rn mit d ≥ 0 und A d = 0 gilt. Ferner seien durch {x1, . . . , xk} die endlich vielen Eckpunkte von Z gegeben. Dann lässt sich jede zulässige Lösung x ∈ Z darstellen als x = ∑ki=1 λixi + d mit λ1, . . . , λk ≥ 0, ∑ki=1 λi = 1, d ≥ 0 und A d = 0 (siehe z. B. Werner [72], Seiten 89–91). Daraus folgt z(x) = cT x = cT ( k∑ i=1 λixi + d ) = k∑ i=1 λicT xi+cT d≤ k∑ i=1 λicT xi≤max { cT x1, . . . , cT xk } = max {z(x1), . . . , z(xk)} . Das heißt, unter den optimalen Lösungen ist mindestens ein Eckpunkt. Lineares Optimierungsproblem lösbar nicht lösbar keine zulässige Lösung Z = /0 keine optimale Lösung z auf Z unbeschränkt genau eine optimale Lösung (Eckpunkt) unendlich viele optimale Lösungen (mind. ein Eckpunkt) Abb. 25.3: Die verschiedenen möglichen Fälle bei der Lösung eines linearen Optimierungsproblems Zu b): Die Zielfunktion z ist als stetige Funktion auf einer beschränkten Menge Z beschränkt. Gemäß Aussage a) ist somit mindestens einer der Eckpunkte von Z eine optimale Lösung. Es sei nun x ∈ Z eine optimale Lösung. Dann ist zu zeigen, dass x eine Konvexkombination von Eckpunkten ist, die ebenfalls optimal sind. Da der zulässige Bereich Z nach Voraussetzung beschränkt ist, lässt sich x als Konvexkombination der endlich vielen Eckpunkte x1, . . . , xk von Z darstellen (siehe z. B. Werner [72], Seiten 89–91). Das heißt, es gilt x = ∑ki=1 λixi für λ1, . . . , λk ≥ 0 mit ∑ki=1 λi = 1. Es ist daher nur zu zeigen, dass λi = 0 für alle nicht optimalen Eckpunkte xi gilt. Dazu sei angenommen, dass der Eckpunkt xj nicht optimal ist. Dann gilt z(xj ) < z(x) und es gibt somit ein r > 0 mit z(xj ) = z(x)− r . Daraus folgt z(x) = cT x = k∑ i=1 λicT xi = k∑ i=1 λiz(xi ) ≤ k∑ i=1 λiz(x)− λj r = z(x) k∑ i=1 λi − λj r = z(x)− λj r, also λj = 0. Das heißt, in der Konvexkombination x =∑k i=1 λixi sind Gewichte λi zu nicht optimalen Eckpunkten xi gleich Null. Folglich ist eine optimale Lösung x stets eine Konvexkombination optimaler Eckpunkte. Umgekehrt ist die Konvexkombination optimaler Eckpunkte x∗1, . . . , x∗k ∈ Z mit z(x∗i ) = cT x∗i = c für i = 1, . . . , k wieder eine optimale Lösung. Denn für die Konvexkombination x̃ := ∑ki=1 λix∗i mit λ1, . . . , λk ≥ 0 und ∑k i=1 λi = 1 folgt z(̃x) = cT ( k∑ i=1 λix∗i ) = k∑ i=1 λicT x∗i = k∑ i=1 λic = c k∑ i=1 λi = c. Das heißt, die Konvexkombination x̃ ist ebenfalls optimal. Bezüglich der Lösbarkeit von linearen Optimierungsproblemen lassen sich somit die in der Abbildung 25.3 aufgeführten Fälle unterscheiden. 767 Kapitel 25 Lineare Optimierung Bei der Suche nach der optimalen Lösung x∗ eines linearen Optimierungsproblems kann man sich also auf die endlich vielen Eckpunkte des zulässigen Bereichs Z beschränken. Diese Konzentration auf Eckpunkte führt zu einer wesentlichen Reduktion des Rechenaufwands. Im Prinzip könnte man alle Eckpunkte und zugehörige Zielfunktionswerte berechnen und durch einen anschließenden Vergleich der Zielfunktionswerte eine optimale Lösung x∗ bestimmen (vgl. Beispiel 25.14). Diese Vorgehensweise bietet sich jedoch in den meisten praktischen Problemstellungen nicht an, da die Anzahl von Eckpunkten schnell mit der Anzahl von Nebenbedingungen und Entscheidungsvariablen ansteigt. Ein deutlich effizienterer Ansatz besteht daher in der Anwendung des Simplex-Algorithmus (siehe Abschnitt 25.4). Bei diesem Verfahren wird die zulässige Menge Z so von einem Eckpunkt zu einem benachbarten Eckpunkt durchlaufen, dass sich dabei der Zielfunktionswert nicht verschlechtert. Im Falle der Existenz einer optimalen Lösung erhält man auf diese Weise deutlich schneller eine optimale Lösung, da nicht alle Eckpunkte berechnet werden müssen. Standardform mit Schlupfvariablen Zur Durchführung des Simplex-Algorithmus wird eine algebraische Charakterisierung der Eckpunkte von Z benötigt. Hierzu ist es erforderlich, die Ungleichungen in der Standardform eines linearen Optimierungsproblems in Gleichungen zu überführen. Dies geschieht durch die Einführung von sogenannten Schlupfvariablen und es resultiert dann die sogenannte Standardform mit Schlupfvariablen: Definition 25.11 (Standardform mit Schlupfvariablen) Ein lineares Optimierungsproblem ist in Standardform mit Schlupfvariablen, wenn es von der folgenden Form ist: Maximiere z(x1, . . . , xn) = c1x1 + . . .+ cnxn unter den Nebenbedingungen (25.11) a11x1 + a12x2 + . . .+ a1nxn + xn+1 =b1 a21x1 + a22x2 + . . .+ a2nxn + xn+2 =b2 . . . . . . . . . . . . . . . am1x1 + am2x2 + . . .+ amnxn + xn+m=bm und den Nichtnegativitätsbedingungen x1, . . . , xn, xn+1, . . . , xn+m ≥ 0. Alternativ kann ein lineares Optimierungsproblem in Standardform mit Schlupfvariablen auch in Matrixschreibweise angegeben werden: Maximiere z(x) = cT x (25.12) unter den Bedingungen à x = b (25.13) x ≥ 0. (25.14) Dabei bezeichnet c := (c1, . . . , cn, 0, . . . , 0)T ∈ Rn+m den erweiterten Vektor der Zielfunktionskoeffizienten sowie x := (x1, . . . , xn, xn+1, . . . , xn+m)T ∈ Rn+m den Vektor mit den n Entscheidungsvariablen und den m Schlupfvariablen. Ferner ist b := (b1, . . . , bm)T ∈ Rm der Vektor mit den m Werten der rechten Seite und à = (A,Em) die erweiterte m × (n + m)-Koeffizientenmatrix des linearen Gleichungssystems (25.11). Die ersten n Variablen x1, . . . , xn werden als Entscheidungsvariablen und die letzten m Variablen xn+1, . . . , xn+m als Schlupfvariablen bezeichnet. Durch die Einführung von m Schlupfvariablen resultiert ein zum linearen Optimierungsproblem in Standardform äquivalentes lineares Optimierungsproblem. Das heißt, aus der Lösung des einen linearen Optimierungsproblems erhält man unmittelbar eine Lösung des anderen und umgekehrt. Die m Nebenbedingungen sind nun jedoch nicht mehr in Form von ≤–Ungleichungen, sondern in Form von Gleichungen gegeben. Dies besitzt den Vorteil, dass bei der Lösung eines linearen Optimierungsproblems weitgehend analog zur Lösung eines linearen Gleichungssystems vorgegangen werden kann. Die Schlupfvariablen sind jedoch nicht nur ein „Trick“ zur Überführung von Ungleichungen in äquivalente Gleichungen, sondern sie ermöglichen auch interessante ökonomische Interpretationen (siehe hierzu die Beispiele 25.15 und 25.19). Im folgenden Beispiel wird demonstriert, wie ein lineares Optimierungsproblem in Standardform in die Standardform mit Schlupfvariablen überführt wird: 768 Kapitel 2525.3 Standardform eines linearen Optimierungsproblems Beispiel 25.12 (Standardform mit Schlupfvariablen) Das lineare Optimierungsproblem in Beispiel 25.2 lautet in Standardform mit Schlupfvariablen: Maximiere z(x1, x2, x3, x4) = 0,03x1 + 0,05x2 + 0,1x3 + 0,2x4 unter den Nebenbedingungen x1+ x2+ x3+ x4+x5 = 1 −x1− x2− x3− x4 +x6 = −1 −x1 +x7 =−0,4 x1+2x2+4x3+8x4 +x8 = 4 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0. Das heißt, zu den vier Entscheidungsvariablen x1, x2, x3, x4 sind die vier Schlupfvariablen x5, x6, x7, x8 hinzugekommen. Die erweiterte Koeffizientenmatrix à besitzt den Rang m. Denn es gilt rang(Ã) ≥ min {m, n+m} = m (vgl. Satz 8.34a)), und aus der linearen Unabhängigkeit der letzten m Spalten von à folgt rang(Ã) ≥ m. Also ist rang(Ã) = m. (25.15) Es können daherm linear unabhängige Spalten ai1 , . . . , aim ∈ R m von à ausgewählt und als Basis des Rm aufgefasst werden. Diese m linear unabhängigen Vektoren werden zu einer regulären m×m-Matrix B := (ai1 , . . . , aim ) und die verbleibenden n Spalten aim+1 , . . . , aim+n ∈ Rm von à zu einer m× n-Matrix N := (aim+1 , . . . , aim+n ) zusammengefasst. Entsprechend werden auch die beiden Vektoren c und x in zwei Bestandteile cB := (ci1 , . . . , cim )T und cN := (cim+1 , . . . , cim+n )T bzw. xB := (xi1 , . . . , xim)T und xN := (xim+1 , . . . , xim+n )T zerlegt, wobei dieselbe Sortierung wie bei B und N verwendet wird. Mit dieser Aufteilung von Ã, c und x erhält man für das lineare Optimierungsproblem (25.12)–(25.14) die Darstellung: Maximiere z(x) = cTB xB + cTN xN (25.16) unter den Bedingungen B xB + N xN = b (25.17) xB, xN ≥ 0. (25.18) Da die Matrix B regulär ist, kann das lineare Gleichungssystem (25.17) nach xB aufgelöst werden. Man erhält dann xB = B−1 b − B−1 N xN. (25.19) Setzt man xN = 0, dann liefert dies für (25.17) die Lösung (xB, xN) = (B−1 b, 0) mit höchstens m von Null verschiedenen Einträgen. Ist diese Lösung zulässig, d. h. gilt xB≥0, dann ist der zugehörige n-dimensionale Teilvektor von (xB, xN), der nur aus den Werten für die n Entscheidungsvariablen x1, . . . , xn besteht, ein Eckpunkt des zulässigen Bereichs Z . Dieser Sachverhalt wird durch den folgenden Satz präzisiert: Satz 25.13 (Charakterisierungssatz für Eckpunkte) Es sei x=(x1, . . . , xn+m)T ∈Rn+m eine zulässige Lösung des linearen Optimierungsproblems (25.12)–(25.14). Dann ist der n-dimensionale Teilvektor (x1, . . . , xn)T mit den Werten für die n Entscheidungsvariablen genau dann ein Eckpunkt des zulässigen Bereichs Z , wenn die Spaltenvektoren aj der erweiterten Koeffizientenmatrix Ã, die mit einem positiven Gewicht xj in die Darstellung à x = x1a1 + . . . + xn+man+m = b eingehen, linear unabhängig sind. Beweis: Siehe z. B. Werner [72], Seite 89. Der Nutzen dieses Satzes besteht darin, dass er eine Charakterisierung der Eckpunkte des zulässigen Bereichs Z mit Hilfe der Spaltenvektoren der erweiterten Koeffizientenmatrix à liefert. Zusammen mit dem Wissen, dass genau m Spaltenvektoren von à linear unabhängig sind (vgl. (25.15)), führt dieses Ergebnis zum folgenden simplen Lösungsansatz: Setze n der n+m Variablen x1, . . . , xn+m gleich Null und löse das zugehörige lineare Gleichungssystem. Ist die resultierende Lösung zulässig und sind die Spaltenvektoren von Ã, die zu einem positiven Eintrag xj im Lösungsvektor gehören, linear unabhängig, dann ist der Teilvektor (x1, . . . , xn)T mit 769 Kapitel 25 Lineare Optimierung den Werten für die n Entscheidungsvariablen ein Eckpunkt des zulässigen Bereichs Z . Gemäß dem Hauptsatz der linearen Optimierung (vgl. Satz 25.10) ist er damit auch ein Kandidat für die optimale Lösung des linearen Optimierungsproblems. Da es jedoch insgesamt ( n+m n ) = (n+m)! m! n! Möglichkeiten gibt, aus einer Menge mit n+m Elementen n Elemente auszuwählen, sind bei diesem Ansatz schnell eine große Anzahl linearer Gleichungssysteme zu lösen. Das Lösen eines linearen Optimierungsproblems durch Berechnung aller Eckpunkte wird als Vollenumeration bezeichnet und im folgenden Beispiel demonstriert: Beispiel 25.14 (Vollenumeration bei einem linearen Optimierungsproblem) Das lineare Optimierungsproblem in Beispiel 25.4 lautet nach Einführung von Schlupfvariablen: Maximiere z(x1, x2) = 2x1 + 3x2 unter den Nebenbedingungen 4x1 + 3x2 + x3 = 600 2x1 + 2x2 + x4 = 320 (25.20) 3x1 + 7x2 + x5 = 840 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5 ≥ 0. Es gibt (5 2 ) = 10 Möglichkeiten n = 2 der n+m = 5 Variablen x1, x2, x3, x4, x5 in (25.20) gleich Null zu setzen. Die dadurch resultierenden zehn linearen Gleichungssysteme besitzen die Lösungen: x1 = x2 = 0 : x3 = 600, x4 = 320, x5 = 840 ⇒ Lösung zulässig x1 = x3 = 0 : x2 = 200, x4 = −80, x5 = −560 ⇒ Lösung nicht zulässig x1 = x4 = 0 : x2 = 160, x3 = 120, x5 = −280 ⇒ Lösung nicht zulässig x1 = x5 = 0 : x2 = 120, x3 = 240, x4 = 80 ⇒ Lösung zulässig x2 = x3 = 0 : x1 = 150, x4 = 20, x5 = 390 ⇒ Lösung zulässig x2 = x4 = 0 : x1 = 160, x3 = −40, x5 = 360 ⇒ Lösung nicht zulässig x2 = x5 = 0 : x1 = 280, x3 = −520, x4 = −240 ⇒ Lösung nicht zulässig x3 = x4 = 0 : x1 = 120, x2 = 40, x5 = 200 ⇒ Lösung zulässig x3 = x5 = 0 : x1 = 168019 , x2 = 156019 , x4 = − 40019⇒ Lösung nicht zulässig x4 = x5 = 0 : x1 = 70, x2 = 90, x3 = 50 ⇒ Lösung zulässig Fünf der zehn ermittelten Lösungen (x1, x2, x3, x4, x5)T besitzen ausschließlich nichtnegative Einträge und sind somit zulässig. Die Spaltenvektoren der zugehörigen erweiterten Koeffizientenmatrix à zu einem positiven Eintrag xj im Lösungsvektor (x1, x2, x3, x4, x5)T sind bei diesen fünf zulässigen Lösungen jeweils linear unabhängig. Mit Satz 25.13 folgt daher, dass es sich bei den zugehörigen Teilvektoren (0, 0)T , (0, 120)T , (150, 0)T , (120, 40)T , (70, 90)T mit den Werten für die beiden Entscheidungsvariablen x1 und x2 um die Eckpunkte des zulässigen Bereichs Z handelt. Durch Vergleich der zugehörigen Zielfunktionswerte erhält man, dass (70, 90)T die optimale Lösung x∗ ist und zu einem Zielfunktionswert von z(70, 90) = 410 führt (vgl. Abbildung 25.4). Ökonomische Interpretation von Schlupfvariablen Im folgenden Beispiel wird gezeigt, wie Schlupfvariablen ökonomisch interpretiert werden können: Beispiel 25.15 (Interpretation von Schlupfvariablen) Die optimale Lösung für das lineare Optimierungsproblem in Beispiel 25.4 zur Produktionsplanung ist (x1, x2, x3, x4, x5) T = (70, 90, 50, 0, 0)T (25.21) (vgl. Beispiel 25.14). 770 Kapitel 2525.4 Simplex-Algorithmus x1 x2 0 50 100 150 200 0 50 100 150 200 250 300 Z P10 P1 P2 P3 P4 P5 P6 P7 P8 P9 Abb. 25.4: Lösungen der (5 2 ) = 10 linearen Gleichungssysteme. Davon sind fünf zulässig (rot) und fünf unzulässig (grün) Die beiden ersten Einträge in (25.21) geben die optimalen Werte für die Entscheidungsvariablen x1 und x2 an, d. h. sie sind die optimalen Produktionsmengen für die beiden Produkte P1 und P2. Sie führen zu einem maximalen Zielfunktionswert von z(70, 90) = 410. Die letzten drei Einträge sind die Werte der Schlupfvariablen x3, x4 und x5. Sie lassen sich wie folgt interpretieren: Der Wert x3 = 50 besagt, dass vom Produktionsfaktor F1 eine Restkapazität von 50 Mengeneinheiten vorhanden ist. Dies kann man auch an der ursprünglichen Nebenbedingung 4x1 + 3x2 ≤ 600 erkennen, wenn man x1 = 70 und x2 = 90 einsetzt. Analog drückt der Wert einer Schlupfvariablen bei einer ≥– Nebenbedingung aus, um wieviel der Mindestwert überschritten wird. Wäre zum Beispiel als zweite Nebenbedingung x1 + x2 ≥ 80 zu beachten, d.h eine Mindestproduktion von insgesamt 80 Mengeneinheiten, dann würde die zugehörige Schlupfvariable x4 den Wert 80 annehmen. Denn aus der Ungleichung x1 + x2 ≥ 80 erhält man nach Umformung −x1 − x2 ≤ −80 und die anschließende Einführung der Schlupfvariablen x4 liefert die Gleichung −x1 − x2 + x4 = −80, die für x1 = 70, x2 = 90 und x4 = 80 erfüllt ist. Ist der Wert einer Schlupfvariablen gleich Null, dann drückt sie einen Engpass aus. Für das Beispiel gilt x4 = x5 = 0. Das heißt, die beiden Produktionsfaktoren F2 und F3 sind voll ausgeschöpft und bilden damit Engpasskapazitäten. In Beispiel 25.19 wird erläutert, wie diese Engpasskapazitäten bewertet werden können. 25.4 Simplex-Algorithmus In Beispiel 25.14 wurde gezeigt, dass die optimale Lösung eines linearen Optimierungsproblems theoretisch durch Bestimmung aller Eckpunkte des zulässigen Bereichs Z und einen anschließenden Vergleich der zugehörigen Zielfunktionswerte z(x) bestimmt werden kann. Diese Vollenumeration bedeutet für ein lineares Optimierungsproblem mit n Entscheidungsvariablen und m Nebenbedingungen, dass ( n+m n ) lineare Gleichungssysteme gelöst werden müssen. Das heißt zum Beispiel, dass bei einem vergleichsweise kleinen Optimierungsproblem mit n = 10 Entscheidungsvariablen und 771 Kapitel 25 Lineare Optimierung m = 20 Nebenbedingungen bereits mehr als 30 Millionen lineare Gleichungssysteme zu lösen sind. G. Dantzig Aus diesem Grund wird ein Verfahren benötigt, bei dem zur Lösung eines linearen Optimierungsproblems nicht alle Eckpunkte berechnet werden müssen. Das bekannteste Verfahren dieser Art ist der von dem US-amerikanischen Mathematiker George Dantzig (1914–2005) entwickelte Simplex-Algorithmus. Ausgehend von einem Eckpunkt des zulässigen Bereichs Z wird bei diesem Algorithmus der benachbarte Eckpunkt bestimmt, bei dem der Zielfunktionswert verbessert wird. Diese Vorgehensweise wird solange fortgeführt, bis keine Verbesserung mehr möglich ist. Das heißt, bei diesem „intelligenten Ansatz“ muss nur ein Bruchteil aller Eckpunkte von Z berechnet werden, was im Vergleich zu einer Vollenumeration zu einem enormen Effizienzgewinn führt. J. v. Neumann Dantzig veröffentlichte den Simplex-Algorithmus 1947 während seiner Zeit als mathematischer Berater des US-Verteidigungsministeriums. Es ist daher nicht verwunderlich, dass eine der ersten dokumentierten Anwendungen des Simplex-Algorithmus das sogenannte Diätenproblem des US-amerikanischen Ökonomen George Stigler (1911–1991) war. Es bestand darin, eine möglichst günstige Nahrungszusammenstellung für Soldaten zu bestimmen, die gewisse Vorgaben bezüglich Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllt. An der Lösung dieses – nach heutigen Maßstäben kleinen – linearen Optimierungsproblems mit neun Ungleichungen und 77 Variablen waren damals neun Personen beschäftigt, die zusammen ungefähr 120 Manntage Rechenarbeit benötigten (siehe Bixby [4]). In den Folgejahren wurde die lineare Optimierung und insbesondere der Simplex-Algorithmus von verschiedenen Wissenschaftlern beträchtlich weiterentwickelt. Hierzu zählen zum Beispiel der einflussreiche US-amerikanische Mathema- O. Morgenstern tiker ungarischer Herkunft John von Neumann (1903–1957), einer der genialsten und vielseitigsten Mathematiker des 20. Jahrhunderts, und der österreichische Wirtschaftswissenschaftler Oskar Morgenstern (1902–1977). Sie lieferten im Rahmen ihrer Untersuchungen zur Spieltheorie grundlegende und wichtige Beiträge zur linearen Optimierung. So ist man mittlerweile in der Lage, mit dem Simplex-Algorithmus bzw. seinen Weiterentwicklungen unter Zuhilfenahme von leistungsfähigen Rechnern lineare Optimierungsprobleme mit mehreren hunderttausend Variablen und Ungleichungen innerhalb weniger Stunden zu lösen. Im Folgenden werden die bei einem Iterationsschritt des Simplex-Algorithmus durchzuführenden Rechenschritte erläutert. Zum besseren Verständnis der einzelnen Rechenschritte wird hierzu ein konkretes Beispiel, nämlich das Beispiel 25.4 zur Produktionsplanung, betrachtet. Es lautet in Standardform mit Schlupfvariablen: Maximiere z(x1, x2) = 2x1 + 3x2 (25.22) unter den Nebenbedingungen (1) 4x1+3x2+x3 = 600 (2) 2x1+2x2 +x4 = 320 (25.23) (3) 3x1+7x2 +x5 = 840 mit den Schlupfvariablen x3, x4, x5 (blau) und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5 ≥ 0 (vgl. Beispiel 25.14). Aus dieser Darstellung kann unmittelbar eine zulässige Lösung (x1, x2, x3, x4, x5) T = (0, 0, 600, 320, 840)T mit zugehörigem Zielfunktionswert z(x1, x2) = 0 abgelesen werden. Bei dem Teilvektor (x1, x2)T = (0, 0)T handelt es sich um einen Eckpunkt des zulässigen Bereichs Z (vgl. P1 in Abbildung 25.4). Diese zulässige Lösung und ihr Zielfunktionswert können deshalb so einfach abgelesen werden, weil die von Null verschiedenen Variablen x3, x4 und x5 zum einen jeweils nur in einer Nebenbedingung, und zwar mit dem Koeffizienten 1, vorkommen und zum anderen in der Zielfunktion z nicht enthalten sind. Diese hilfreiche Struktur kann mittels elementarer Umformungen auf benachbarte Eckpunkte 772 Kapitel 2525.4 Simplex-Algorithmus von Z übertragen werden und stellt den Kern des sogenannten Austauschschritts des Simplex-Algorithmus dar. Tauscht man zum Beispiel x2 = 0 gegen x5 = 0 aus, dann erhält man das äquivalente lineare Optimierungsproblem: Maximiere z(x1, x2) = 5 7 x1 − 3 7 x5+360 (25.24) unter den Nebenbedingungen (1′) 19 7 x1 +x3 −3 7 x5 = 240 (2′) 8 7 x1 +x4−2 7 x5 = 80 (25.25) (3′) 3 7 x1+x2 +1 7 x5 = 120 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5 ≥ 0. Aus dieser Darstellung kann wieder unmittelbar eine weitere zulässige Lösung (x1, x2, x3, x4, x5) T = (0, 120, 240, 80, 0)T mit Zielfunktionswert z(x1, x2) = 360 abgelesen werden. Bei dem Teilvektor (x1, x2)T = (0, 120)T handelt es sich um einen zu (x1, x2)T = (0, 0)T benachbarten Eckpunkt des zulässigen Bereichs mit höherem Zielfunktionswert (vgl. P4 in Abbildung 25.4). Die neue Darstellung (25.24)–(25.25) resultiert wie folgt: a) Unter Ausnutzung von 3x1 + 7x2 + x5 = 840 bzw. x2 = 120 − 37x1 − 17x5 (vgl. Nebenbedingung (3) in (25.23)) wird die Variable x2 in der Zielfunktion (25.22) eliminiert und dafür die Variable x5 neu aufgenommen. Man erhält dann die neue Zielfunktion z(x1, x5) = 2x1 + 3 ( 120 − 3 7 x1 − 1 7 x5 ) = 5 7 x1 − 3 7 x5 + 360, in der die von Null verschiedenen Variablen x2, x3 und x4 nicht enthalten sind. b) Durch elementare Zeilenumformungen werden die Nebenbedingungen (1)–(3) in (25.23) so umgeformt, dass die von Null verschiedenen Variablen x2, x3 und x4 jeweils in nur einer Nebenbedingung vorkommen und zwar mit dem Koeffizienten 1. Dies wird dadurch erreicht, dass die Nebenbedingung (3) mit 17 multipliziert wird sowie das 3 7 -fache bzw. das 2 7 -fache der Nebenbedingung (3) von der Nebenbedingung (1) bzw. (2) abgezogen wird. Die Formalisierung dieser Rechenschritte bildet zusammen mit geeigneten Auswahlkriterien, die angeben, welche Variablen ausgetauscht werden sollen, und einem Abbruchkriterium, das angibt, ob die optimale Lösung erreicht ist, den Kern des Simplex-Algorithmus. Basislösungen Das wesentliche Merkmal bei der obigen Berechnung der beiden zulässigen Lösungen bzw. Eckpunkte ist, dass jeweils n Variablen gleich Null gesetzt und die Gleichungen (d. h. Nebenbedingungen) im Austauschschritt so umgeformt werden, dass die von Null verschiedenen Variablen jeweils in nur einer Gleichung auftreten und den Koeffizienten 1 haben. Diese Beobachtung führt zu den Begriffen Basislösung, Nichtbasisvariable und Basisvariable: Definition 25.16 (Basislösung, Nichtbasisvariable und Basisvariable) Es sei x = (x1, . . . , xn+m)T eine Lösung eines linearen Gleichungssystems der Ordnung m×(n+m). Dann heißt x Basislösung des linearen Gleichungssystems, wenn die folgenden beiden Bedingungen erfüllt sind: a) Die Werte von n Variablen sind Null. Diese Variablen heißen Nichtbasisvariablen (kurz NBV) der Basislösung x. b) Die verbleibenden m Variablen treten nicht gemeinsam in einer Gleichung auf und sind jeweils in nur einer Gleichung enthalten, und zwar mit dem Koeffizienten 1. Diese Variablen werden als Basisvariablen (kurz BV) der Basislösung x bezeichnet. Gilt zusätzlich x ≥ 0, dann heißt die Basislösung zulässig. Setzt man zum Beispiel im linearen Gleichungssystem (25.11) bzw. (25.13) für die n Entscheidungsvariablen x1, . . . , xn jeweils den Wert Null ein, dann erhält man die zulässige Basislösung (0, . . . , 0, b1, . . . , bm) ∈ Rn+m. Zwischen Eckpunkten und zulässigen Basislösungen besteht der folgende enge Zusammenhang: 773 Kapitel 25 Lineare Optimierung Satz 25.17 (Zusammenhang Eckpunkte und zulässige Basislösungen) Es sei x = (x1, . . . , xn+m)T eine zulässige Lösung des linearen Optimierungsproblems (25.12)–(25.14). Dann ist der n-dimensionale Teilvektor (x1, . . . , xn)T mit den Werten für die n Entscheidungsvariablen genau dann ein Eckpunkt des zulässigen Bereichs Z , wenn x eine zulässige Basislösung des zum linearen Optimierungsproblem gehörenden linearen Gleichungssystems (25.13) ist. Beweis: Da x = (x1, . . . , xn+m)T eine zulässige Lösung des linearen Optimierungsproblems (25.12)–(25.14) ist, gilt à x = x1a1 + . . .+ xn+man+m = b. (25.26) Es sei nun angenommen, dass x eine zulässige Basislösung ist. Dann erhält man mit der Eigenschaft a) einer Basislösung, dass die Spaltenvektoren aj , die mit einem positiven Gewicht xj in die Darstellung (25.26) eingehen, zu den Basisvariablen gehören müssen. Aus der Eigenschaft b) einer Basislösung folgt weiter, dass es sich bei diesen Spaltenvektoren um linear unabhängige Einheitsvektoren des Rm handelt. Mit Satz 25.13 folgt somit, dass der n-dimensionale Teilvektor (x1, . . . , xn) ein Eckpunkt von Z ist. Umgekehrt sei nun angenommen, dass der n-dimensionale Teilvektor x = (x1, . . . , xn)T ein Eckpunkt von Z ist. Dann folgt mit Satz 25.13, dass die Spaltenvektoren aj , die mit einem positiven Gewicht xj in die Darstellung (25.26) eingehen, linear unabhängig sind. Da jedoch die erweiterte Koeffizientenmatrix à den Rang m besitzt (vgl. (25.15)), impliziert dies, dass mindestens n Einträge von x = (x1, . . . , xn+m)T gleich Null sind. Das heißt, durch Berechnung der zulässigen Basislösungen des zum linearen Optimierungsproblems gehörenden linearen Gleichungssystems à x = b erhält man alle Vektoren x ∈ Rn, die als Kandidaten für eine optimale Lösung des linearen Optimierungsproblems in Frage kommen. In Abbildung 25.5 sind noch einmal die mathematischen Resultate zusammengestellt, die dieser Schlussfolgerung zugrunde liegen. Zum Beispiel sind in den beiden Darstellungen (25.22)– (25.23) und (25.24)–(25.25) die m = 3 Variablen x3, x4, x5 bzw. x2, x3, x4 die Basisvariablen und die n = 2 Variablen x1, x2 bzw. x1, x5 die Nichtbasisvariablen. Die Überführung von (25.22)–(25.23) in (25.24)–(25.25) erfolgt durch einen Austauschschritt, bei dem die Basisvariable x5 durch die Nichtbasisvariable x2 ausgetauscht wird. Das heißt, nach Durchführung des Austauschschritts ist x2 eine Basisvariable Satz 25.8 Zulässiger Bereich Z ist konvex. Eckpunkt von Z zulässige Basislösung von ~Ax = b Satz 25.17 Satz 25.10a) Mindestens einer der Eckpunkte von Z ist eine optimale Lösung oder es existiert keine optimale Lösung. Ergebnis: Bei der Lösung eines linearen Optimierungsproblems kann man sich auf die Berechnung der endlich vielen zulässigen Basislösungen von Ax = b beschränken. ~ Abb. 25.5: Mathematische Grundlagen des Simplex-Algorithmus und x5 eine Nichtbasisvariable. Die Basislösungen der beiden Darstellungen lauten (0, 0, 600, 320, 840)T bzw. (0, 120, 240, 80, 0)T . Da sie nur nichtnegative Einträge besitzen, sind beide Basislösungen zulässig. Simplex-Tableau Für die folgende Darstellung des Simplex-Algorithmus wird angenommen, dass für die rechte Seite des linearen Gleichungssystems (25.11) bzw. (25.13) b1, . . . , bm ≥ 0 bzw. b ≥ 0 (25.27) gilt. Diese Annahme stellt sicher, dass der Ursprung (0, . . . , 0)T ∈ Rn ein Eckpunkt des zulässigen Bereichs Z und (0, . . . , 0, b1, . . . , bm) T ∈ Rn+m (25.28) eine erste zulässige Basislösung ist. Damit kann insbesondere der Fall, dass keine zulässige Lösung existiert, also Z = ∅ gilt, nicht auftreten. Durch Austauschschritte kann die Basislösung (25.28) sukzessive verbessert werden. Gilt dagegen b ≥ 0, dann ist der Ursprung (0, . . . , 0)T ∈ Rn durch die Nebenbedingungen vom zulässigen Bereich Z abgeschnitten 774 Kapitel 2525.4 Simplex-Algorithmus und (25.28) ist damit keine zulässige Basislösung. In einem solchen Fall muss zuerst einmal eine erste zulässige Basislösung ermittelt werden, die dann anschließend durch Austauschschritte wieder verbessert werden kann. Wie bei der Bestimmung einer ersten zulässigen Basislösung zu verfahren ist, wird in Abschnitt 25.6 erläutert. Die verschiedenen Austauschschritte bei der Durchführung des Simplex-Algorithmus werden gewöhnlich in einem Tableau dargestellt, welches als Simplex-Tableau bezeichnet wird. Wie die Überführung der Darstellung (25.22)–(25.23) in die Darstellung (25.24)–(25.25) zeigt, kann die Durchführung eines Austauschschritts zu einer Konstanten in der Zielfunktion z führen. Aus diesem Grund wird die Zielfunktion um eine Konstante z0 ergänzt. Man erhält dann die Gleichung z(x) = c1x1 + c2x2 + . . .+ cnxn + z0 bzw. nach Umformung −z(x)+ c1x1 + c2x2 + . . .+ cnxn = −z0. Die Koeffizienten dieser Gleichung werden mit den Koeffizienten des linearen Gleichungssystems (25.11) übersichtlich in einem Simplex-Tableau zusammengefasst (vgl. Tabelle 25.1). Pivotzeile, Pivotspalte und Pivotelement Für die Durchführung eines Austauschschritts in einem Simplex-Tableau ist das sogenannte Pivotelement von besonderer Bedeutung. Es legt fest, welche Basisvariable gegen welche Nichtbasisvariable ausgetauscht wird. Das Pivotelement ist durch die Pivotzeile (PZ) und die Pivotspalte (PS) festgelegt und wie folgt definiert: NBV NBV · · · NBV · · · NBV BV BV · · · BV · · · BV −z x1 x2 · · · xk · · · xn xn+1 xn+2 · · · xn+l · · · xn+m 1 c1 c2 · · · ck · · · cn 0 0 · · · 0 · · · 0 −z0 0 a11 a12 · · · a1k · · · a1n 1 0 · · · 0 · · · 0 b1 0 a21 a22 · · · a2k · · · a2n 0 1 · · · 0 · · · 0 b2 ... ... ... . . . ... . . . ... ... ... . . . ... . . . ... ... PZ → 0 al1 al2 · · · alk · · · aln 0 0 · · · 1 · · · 0 bl ... ... ... . . . ... . . . ... ... ... . . . ... . . . ... ... 0 am1 am2 · · · amk · · · amn 0 0 · · · 0 · · · 1 bm ↑ PS Tabelle 25.1: Simplex-Tableau mit Pivotelement alk , das den Austausch der Basisvariablen xn+l gegen die Nichtbasisvariable xk anzeigt Definition 25.18 (Pivotelement) Die Zeile im Simplex-Tableau, deren Eintrag in der Spalte der auszutauschenden Basisvariablen gleich 1 ist, wird Pivotzeile genannt, und die Spalte der aufzunehmenden Nichtbasisvariablen heißt Pivotspalte. Die Schnittstelle von Pivotzeile und Pivotspalte wird als Pivotelement bezeichnet. Im Folgenden wird das zu einem Austauschschritt gehörende Pivotelement im Simplex-Tableau in blauer Schrift dargestellt (vgl. Simplex-Tableau 25.1). Das Pivotelement wird dadurch festgelegt, dass man sich entscheidet, welche der n Nichtbasisvariablen neu in die Basis aufgenommen werden soll (d. h. Auswahl der Pivotspalte k) und welche dermBasisvariablen dafür aus der Basis entfernt werden soll (d. h. Auswahl der Pivotzeile l). Diese Entscheidung wird mit Hilfe von Auswahlkriterien getroffen. Auswahl- und Stoppkriterien Zur Auswahl der Pivotspalte und der Pivotzeile gibt es mehrere Möglichkeiten. Im Folgenden wird die ursprünglich von Dantzig vorgeschlagene Methode verwendet. Diese basiert auf den beiden folgenden Auswahl- und Stoppkriterien: a) Auswahl der Pivotspalte (d. h. der aufzunehmenden Nichtbasisvariablen): Wähle die Spalte k mit dem größten positiven Zielfunktionskoeffizienten ck als Pivotspalte. Denn durch Aufnahme der Nichtbasisvariablen xk in die Basis geht der aktuelle 775 Kapitel 25 Lineare Optimierung Zielfunktionswert z = z0 über in z = z0 + ckxk (25.29) und es ist somit sichergestellt, dass der Wert der Zielfunktion z anwächst und der Zuwachs je Mengeneinheit am größten ist. 1. Stoppkriterium: Gilt cj ≤ 0 für alle j = 1, . . . , n+m, dann kann durch Aufnahme einer Nichtbasisvariablen in die Basis der Wert von (25.29) nicht erhöht werden. Es sind dann nur nicht positive Zuwächse beim Zielfunktionswert möglich. Das heißt, der Vektor x∗=(x1, . . . , xn)T mit den Werten für die n Entscheidungsvariablen im Simplex-Tableau ist eine optimale Lösung des linearen Optimierungsproblems und z0 ist der zugehörige maximale Zielfunktionswert. Gilt dabei für die Zielfunktionskoeffizienten aller n Nichtbasisvariablen cj < 0, dann ist die optimale Lösung eindeutig. Andernfalls können die Nichtbasisvariablen xj , deren Zielfunktionskoeffizient cj gleich Null ist, durch weitere Austauschschritte nacheinander in die Basis aufgenommen werden, ohne dass sich dadurch der Wert der Zielfunktion z verändert. Da jedoch gemäß Satz 25.10) jede Konvexkombination optimaler Eckpunkte von Z wieder eine optimale Lösung ist, bedeutet dies, dass unendlich viele optimale Lösungen existieren (vgl. Beispiel 25.21). b) Auswahl der Pivotzeile (d. h. der zu entfernenden Basisvariablen): Wähle die Zeile l, die in der Pivotspalte k einen Eintrag alk > 0 besitzt und der Quotient bl alk am kleinsten ist. Das heißt, wähle die Pivotzeile l so, dass bl alk = min { bi aik : aik > 0 } gilt. Wird das Minimum in mehreren Zeilen angenommen, dann kann eine dieser Zeilen beliebig ausgewählt werden. Durch dieses Vorgehen wird sichergestellt, dass auch die neue Basislösung zulässig ist. 2. Stoppkriterium: Gilt ck > 0 und aik ≤ 0 für alle i = 1, . . . , m, dann ist die Zielfunktion z auf dem zulässigen Bereich Z nach oben unbeschränkt und es existiert somit keine optimale Lösung. Denn setzt man für die zu ck gehörende Nichtbasisvariable xk , die neu in die Basis aufgenommen wird, einen beliebigen Wert q > 0 ein und lässt die übrigen Nichtbasisvariablen unverändert, dann gilt xn+i = bi − aikq ≥ 0 für alle i = 1, . . . , m. Man erhält somit eine neue zulässige Basislösung mit dem Zielfunktionswert z = z0 + ckq. Da q beliebig groß gewählt werden kann und ck > 0 gilt, bedeutet dies, dass die Zielfunktion z nach oben unbeschränkt ist und damit keine optimale Lösung existiert (vgl. Beispiel 25.22). Austauschschritt Nachdem mit der Festlegung des Pivotelements alk bestimmt worden ist, welche Nichtbasisvariable xk neu in die Basis aufgenommen und welche Basisvariable xn+l dafür aus der Basis entfernt werden soll, kann der Austauschschritt vollzogen werden. Dieser Austausch von xn+l gegen xk entspricht im Simplex-Tableau der Anwendung von elementaren Zeilenumformungen, so dass in der Pivotspalte k ein Einheitsvektor mit der 1 in der Schnittstelle (Pivotelement) von Pivotspalte und Pivotzeile erzeugt wird. Man erhält dann das transformierte Simplex-Tableau 25.2. Dabei gilt für die neuen Einträge in diesem Tableau: a′ij := aij − aikalj alk für i = l, j = k c′j := cj − ck alj alk für j = k b′i := bi − bl aik alk für i = l −z′0 := −z0 − bl ck alk Mit der Transformation des Simplex-Tableaus 25.1 in das Simplex-Tableau 25.2 ist der Basistausch xk ↔ xn+l abgeschlossen und das neue Tableau bildet anschließend den Ausgangspunkt für eventuell weitere Austauschschritte. Das Verfahren wird solange fortgeführt, bis es mit einem der beiden oben angegebenen Stoppkriterien abbricht. In Abbildung 25.8 wird der Ablauf des Simplex-Algorithmus übersichtlich in Form eines Flussdiagramms dargestellt. Diese Darstellung berücksichtigt auch die beiden im folgenden Abschnitt 25.5 betrachteten Sonderfälle: a) Existenz unendlich vieler optimaler Lösungen b) Eine nach oben unbeschränkte Zielfunktion z auf dem zulässigen Bereich Z Im folgenden Beispiel wird gezeigt, wie das lineare Optimierungsproblem aus Beispiel 25.4 mit Hilfe des Simplex-Algorithmus gelöst werden kann. Dabei werden analog zur Lösung eines linearen Gleichungssystems mit Hilfe des Gauß- Algorithmus die Zeilen (d. h. die Zielfunktion und die Nebenbedingungen) durchnummeriert und die durchgeführten 776 Kapitel 2525.4 Simplex-Algorithmus NBV NBV · · · BV · · · NBV BV BV · · · NBV · · · BV −z x1 x2 · · · xk · · · xn xn+1 xn+2 · · · xn+l · · · xn+m 1 c′1 c ′ 2 · · · 0 · · · c′n 0 0 · · · c′n+l · · · 0 −z′0 0 a′11 a ′ 12 · · · 0 · · · a′1n 1 0 · · · a′1n+l · · · 0 b′1 0 a′21 a ′ 22 · · · 0 · · · a′2n 0 1 · · · a′2n+l · · · 0 b′2 ... ... ... . . . ... . . . ... ... ... . . . ... . . . ... ... 0 al1 alk al2 alk · · · 1 · · · aln alk 0 0 · · · 1 alk · · · 0 bl alk ... ... ... . . . ... . . . ... ... ... . . . ... . . . ... ... 0 a′m1 a ′ m2 · · · 0 · · · a′mn 0 0 · · · a′mn+l · · · 1 b′m Tabelle 25.2: Transformiertes Simplex-Tableau nach durchgeführtem Austauschschritt mit der neuen Basisvariablen xk und der neuen Nichtbasisvariablen xn+l elementaren Zeilenumformungen rechts in blauer Schrift angegeben. Beispiel 25.19 (Anwendung des Simplex- Algorithmus) Für das lineare Optimierungsproblem aus Beispiel 25.4 erhält man das untenstehende Simplex-Tableau (vgl. (25.22)–(25.23)): NBV NBV BV BV BV −z x1 x2 x3 x4 x5 (0) 1 2 3 0 0 0 0 (1) 0 4 3 1 0 0 600 (2) 0 2 2 0 1 0 320 (3) 0 3 7 0 0 1 840 Daraus lassen sich unmittelbar die erste zulässige Basislösung und der zugehörige Zielfunktionswert ablesen. Sie lauten (0, 0, 600, 320, 840)T bzw. z = 0. Der größte Zielfunktionskoeffizient liegt bei drei, ist also positiv. Damit ist die Voraussetzung des Auswahlkriteriums a) erfüllt. Die zugehörige Variable x2 wird zur neuen Basisvariablen und die zugehörige Spalte zur Pivotspalte. Die Quotienten bi ai2 sind gegeben durch 6003 , 320 2 und 840 7 , wobei der kleinste dieser Quotienten 840 7 = 120 ist. Die zugehörige Zeile, also die dritte Nebenbedingungszeile, wird somit zur Pivotzeile und das Pivotelement ist folglich 7 (Schnittstelle von Pivotzeile und Pivotspalte). Im Austauschschritt wird x2 in die Basis aufgenommen und x5 dafür aus der Basis entfernt. Hierbei wird in der Pivotspalte durch elementare Zeilenumformungen ein Einheitsvektor erzeugt, wobei die 1 an der Stelle steht, wo zuvor das Pivotelement stand. Man erhält dann das folgende Tableau: NBV BV BV BV NBV −z x1 x2 x3 x4 x5 (0′) 1 57 0 0 0 − 37 −360 (0)− 3 · (3′) (1′) 0 197 0 1 0 − 37 240 (1)− 3 · (3′) (2′) 0 87 0 0 1 − 27 80 (2)− 2 · (3′) (3′) 0 37 1 0 0 1 7 120 1/7 · (3) Aus diesem Simplex-Tableau lassen sich die zweite zulässige Basislösung und der zugehörige Zielfunktionswert ablesen. Sie lauten (0, 120, 240, 80, 0)T bzw. z = 360. Da cj ≤ 0 nicht für alle j = 1, . . . , 5 gilt, ist das erste Stoppkriterium nicht erfüllt und somit ein weiterer Austauschschritt erforderlich. Die zum größten Zielfunktionskoeffizienten 57 gehörende Variable x1 wird zur neuen Basisvariablen und die zugehörige Spalte zur Pivotspalte. Die Quotienten bi ai1 sind gegeben durch 24019/7 , 80 8/7 und 1203/7 , wobei der kleinste dieser Quotienten 80 8/7 = 70 ist. Die zugehörige Zeile, also die zweite Nebenbedingungszeile, wird somit zur Pivotzeile und das Pivotelement ist folglich 87 . Im Austauschschritt wird x1 in die Basis aufgenommen und x4 dafür aus der Basis entfernt. Man erhält dann das folgende Tableau: 777 Kapitel 25 Lineare Optimierung BV BV BV NBV NBV −z x1 x2 x3 x4 x5 (0′′) 1 0 0 0 − 58 − 14 −410 (0′)− 5/7 · (2′′) (1′′) 0 0 0 1 − 198 14 50 (1′)− 19/7 · (2′′) (2′′) 0 1 0 0 78 − 14 70 7/8 · (2′) (3′′) 0 0 1 0 − 38 14 90 (3′)− 3/7 · (2′′) (25.30) Daraus lassen sich die dritte zulässige Basislösung und der zugehörige Zielfunktionswert ablesen. Sie lauten (70, 90, 50, 0, 0)T bzw. z = 410. Da nun alle Zielfunktionskoeffizienten cj kleiner oder gleich Null sind, ist das erste Stoppkriterium erfüllt. Das heißt, (70, 90)T ist die gesuchte optimale Lösung x∗ des linearen Optimierungsproblems. Da die Zielfunktionskoeffizienten von Nichtbasisvariablen alle echt kleiner als Null sind, ist die optimale Lösung eindeutig. In Beispiel 25.15 wurde bereits erläutert, dass der Wert Null der beiden Schlupfvariablen x4 und x5 Engpasskapazitäten bei den Produktionsfaktoren F2 und F3 ausdrückt. Mit den zugehörigen Zielfunktionskoeffizienten − 58 und− 14 im letzten Simplex-Tableau können diese Engpasskapazitäten bewertet werden. Gemäß dem letzten Simplex- Tableau hat die Zielfunktion die Form z(x1, x2, x3, x4, x5) = −5 8 x4 − 1 4 x5 + 410. Daraus ist ersichtlich, dass sich der Gewinn z um 58 bzw. 1 4 Geldeinheiten verringert, wenn vom Produktionsfaktor F2 bzw. Produktionsfaktor F3 eine Mengeneinheit weniger eingesetzt wird, also für die zugehörigen Schlupfvariablen x4 = x5 = 1 gilt. Die Zielfunktionskoeffizienten im letzten Simplex-Tableau geben somit den entgangenen Gewinn je nicht eingesetzter Mengeneinheit an Produktionsfaktoren an. In der betriebswirtschaftlichen Literatur spricht man in diesem Zusammenhang von Opportunitätskosten oder Schattenpreisen (vgl. Michel-Torspecken [46], Seite 93). Der Betrieb würde bei einer Kapazitätserweiterung um jeweils eine Mengeneinheit (d. h. x4 = −1 bzw. x5 = −1) einen zusätzlichen Gewinn von 58 bzw. 14 Geldeinheiten erzielen. Der Schattenpreis des Produktionsfaktors F1 ist dagegen gleich Null. Eine zusätzliche Mengeneinheit würde zu keinem höheren Gewinn führen, da bereits eine Restkapazität von 50 Mengeneinheiten vorhanden ist. Im nächsten Beispiel wird mit Hilfe des Simplex- Algorithmus ein lineares Optimierungsproblem mit vier Entscheidungsvariablen und drei Nebenbedingungen gelöst: Beispiel 25.20 (Anwendung des Simplex- Algorithmus) Betrachtet wird das folgende lineare Optimierungsproblem in Standardform mit den vier Entscheidungsvariablen x1, x2, x3, x4: Maximiere z(x1, x2, x3, x4) = 2x1 + x2 + 3x3 + x4 unter den Nebenbedingungen 2x1+4x2 +x4 ≤ 20 x1+ x2+5x3+x4 ≤ 30 (25.31) x2+ x3+x4 ≤ 10 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. Für die Nebenbedingungen (25.31) erhält man nach Einführung von Schlupfvariablen: 2x1+4x2 +x4+x5 = 20 x1+ x2+5x3+x4 +x6 = 30 x2+ x3+x4 +x7 = 10 Die Durchführung des Simplex-Algorithmus führt zu den Simplex-Tableaus in Tabelle 25.3. Im ersten Austauschschritt wurde die Nichtbasisvariable x3 gegen die Basisvariable x6 und im zweiten Austauschschritt die Nichtbasisvariable x1 gegen die Basisvariable x5 ausgetauscht. Im dritten Simplex-Tableau sind bereits alle Zielfunktionskoeffizienten cj kleiner oder gleich Null. Die dritte Basislösung und der zugehörige Zielfunktionswert (10, 0, 4, 0, 0, 0, 6)T bzw. z = 32 sind somit optimal. Das heißt, (10, 0, 4, 0)T ist die gesuchte optimale Lösung x∗ des linearen Optimierungsproblems. Da ferner die Zielfunktionskoeffizienten von allen Nichtbasisvariablen im dritten Simplex-Tableau echt kleiner als Null sind, ist die optimale Lösung eindeutig. 778 Kapitel 2525.5 Sonderfälle bei der Anwendung des Simplex-Algorithmus NBV NBV NBV NBV BV BV BV −z x1 x2 x3 x4 x5 x6 x7 (0) 1 2 1 3 1 0 0 0 0 (1) 0 2 4 0 1 1 0 0 20 (2) 0 1 1 5 1 0 1 0 30 (3) 0 0 1 1 1 0 0 1 10 NBV NBV BV NBV BV NBV BV −z x1 x2 x3 x4 x5 x6 x7 (0′) 1 75 2 5 0 2 5 0 − 35 0 −18 (0)− 3 · (2′) (1) 0 2 4 0 1 1 0 0 20 (2′) 0 15 1 5 1 1 5 0 1 5 0 6 1/5 · (2) (3′) 0 − 15 45 0 45 0 − 15 1 4 (3)− (2′) BV NBV BV NBV NBV NBV BV −z x1 x2 x3 x4 x5 x6 x7 (0′′) 1 0 − 125 0 − 310 − 710 − 35 0 −32 (0′)− 7/5 · (1′) (1′) 0 1 2 0 12 1 2 0 0 10 1/2 · (1) (2′′) 0 0 − 15 1 110 − 110 15 0 4 (2′)− 1/5 · (1′) (3′′) 0 0 65 0 9 10 1 10 − 15 1 6 (3′)+ 1/5 · (1′) Tabelle 25.3: Simplex-Tableaus zu Beispiel 25.20 25.5 Sonderfälle bei der Anwendung des Simplex-Algorithmus Bei der Anwendung des Simplex-Algorithmus können drei Sonderfälle auftreten, deren Kenntnis für die richtige Interpretation der Basislösungen des Simplex-Algorithmus von Bedeutung ist. Daher wird in den folgenden drei Abschnitten anhand von Beispielen gezeigt, wie diese Sonderfälle bei der Anwendung des Simplex-Algorithmus zu identifizieren und interpretieren sind. Mehrdeutigkeit Die optimale Lösung eines linearen Optimierungsproblems muss nicht eindeutig sein. Gemäß dem Hauptsatz der linearen Optimierung (siehe Satz 25.10) ist jede Konvexkombination optimaler Eckpunkte des zulässigen Bereichs Z wieder eine optimale Lösung. Dies bedeutet, dass es für ein lineares Optimierungsproblem möglich ist, dass es keine, genau eine oder unendlich viele optimale Lösungen gibt (vgl. hierzu auch Abbildung 25.3). Wie auf Seite 776 erläutert, kann die Existenz unendlich vieler optimaler Lösungen bei der Anwendung des Simplex-Algorithmus sehr leicht daran erkannt werden, dass im Simplex-Endtableau die Zielfunktionskoeffizienten cj von Nichtbasisvariablen xj gleich Null sind. Zur Verdeutlichung des Falles der Existenz unendlich vieler optimaler Lösungen dient das nächste Beispiel: Beispiel 25.21 (Existenz unendlich vieler optimaler Lösungen) Im Folgenden wird das lineare Optimierungsproblem aus den Beispielen 25.4 und 25.19 mit der leicht veränderten Zielfunktion Maximiere z(x1, x2) = 3x1 + 3x2 betrachtet. Die Anwendung des Simplex-Algorithmus führt zu den folgenden Simplex-Tableaus: 779 Kapitel 25 Lineare Optimierung NBV NBV BV BV BV −z x1 x2 x3 x4 x5 (0) 1 3 3 0 0 0 0 (1) 0 4 3 1 0 0 600 (2) 0 2 2 0 1 0 320 (3) 0 3 7 0 0 1 840 NBV BV BV BV NBV −z x1 x2 x3 x4 x5 (0′) 1 127 0 0 0 − 37 −360 (0)− 3 · (3′) (1′) 0 197 0 1 0 − 37 240 (1)− 3 · (3′) (2′) 0 87 0 0 1 − 27 80 (2)− 2 · (3′) (3′) 0 37 1 0 0 1 7 120 1/7 · (3) BV BV BV NBV NBV −z x1 x2 x3 x4 x5 (0′′) 1 0 0 0 − 32 0 −480 (0′)−12/7 · (2′′) (1′′) 0 0 0 1 − 198 14 50 (1′)−19/7 · (2′′) (2′′) 0 1 0 0 78 − 14 70 7/8 · (2′) (3′′) 0 0 1 0 − 38 14 90 (1′′)−3/7 · (2′′) x1 x2 0 50 100 150 200 0 50 100 150 200 250 300 x*1 x*2 z = 480 Z Abb. 25.6: Lineares Optimierungsproblem mit unendlich vielen optimalen Lösungen Aus dem dritten Simplex-Tableau erhält man eine erste optimale Basislösung und den zugehörigen Zielfunktionswert: (70, 90, 50, 0, 0)T bzw. z = 480 Da jedoch der Zielfunktionskoeffizient c5 der Nichtbasisvariablen x5 gleich Null ist, kann diese in die Basis aufgenommen werden, ohne dass sich der Zielfunktionswert verändert. Man erhält dann das folgende Simplex- Tableau: BV BV NBV NBV BV −z x1 x2 x3 x4 x5 (0′′′) 1 0 0 0 − 32 0 −480 (1′′′) 0 0 0 4 − 192 1 200 4 · (1′′) (2′′′) 0 1 0 1 − 32 0 120 (2′′)+ 1/4 · (1′′′) (3′′′) 0 0 1 −1 2 0 40 (3′′)− 1/4 · (1′′′) Durch (120, 40, 0, 0, 200)T ist somit eine zweite optimale Basislösung gegeben, die ebenfalls den Zielfunktionswert z = 480 liefert. Nach 780 Kapitel 2525.5 Sonderfälle bei der Anwendung des Simplex-Algorithmus Satz 25.10 ist damit auch jede Konvexkombination dieser beiden Basislösungen optimal. Zum Beispiel ist auch 1 2 (70, 90, 50, 0, 0)T + 1 2 (120, 40, 0, 0, 200)T = (95, 65, 25, 0, 100)T eine optimale Basislösung. In Abbildung 25.6 ist die Menge aller Konvexkombinationen von x∗1 := (70, 90, 50, 0, 0)T und x∗2 := (120, 40, 0, 0, 200)T rot eingezeichnet. Unbeschränkte Zielfunktion Bei der Lösung eines linearen Optimierungsproblems in Standardform ist es auch möglich, dass die zu maximierende Zielfunktion z auf dem zulässigen Bereich Z nach oben unbeschränkt ist und damit keine optimale Lösung existiert. Wie auf Seite 776 bereits erläutert wurde, ist dies genau dann der Fall, wenn es einen Zielfunktionskoeffizienten ck > 0 mit aik ≤ 0 für alle i = 1, . . . , m gibt. Das nächste Beispiel verdeutlicht diesen Fall: x1 x2 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 10 Z P1 P2 P3 z(x1, x2) Abb. 25.7: Lineares Optimierungsproblem mit einer auf Z nach oben unbeschränkten Zielfunktion z Beispiel 25.22 (Simplex-Algorithmus bei unbeschränkter Zielfunktion) Betrachtet wird das folgende lineare Optimierungsproblem in Standardform mit den beiden Schlupfvariablen x3 und x4: Maximiere z(x1, x2) = x1 + 2x2 unter den Nebenbedingungen −x1 + 3x2 + x3 = 15 −3x1 + 2x2 + x4 = 3 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. Aus der Abbildung 25.7 ist unmittelbar ersichtlich, dass die Zielfunktion z auf dem zulässigen Bereich Z nach oben unbeschränkt ist. Das heißt, dass dieses lineare Maximierungsproblem keine optimale Lösung besitzt. Dieses Ergebnis erhält man auch durch Anwendung des Simplex-Algorithmus: 781 Kapitel 25 Lineare Optimierung NBV NBV BV BV −z x1 x2 x3 x4 (0) 1 1 2 0 0 0 (1) 0 −1 3 1 0 15 (2) 0 −3 2 0 1 3 NBV BV BV NBV −z x1 x2 x3 x4 (0′) 1 4 0 0 −1 −3 (0)− 2 · (2′) (1′) 0 72 0 1 − 32 212 (1)− 3 · (2′) (2′) 0 − 32 1 0 12 32 1/2 · (2) BV BV NBV NBV −z x1 x2 x3 x4 (0′′) 1 0 0 − 87 57 −15 (0′)− 4 · (1′′) (1′′) 0 1 0 27 − 37 3 2/7 · (1′) (2′′) 0 0 1 37 − 17 6 (2′)+ 3/2 · (1′′) Aus diesen drei Simplex-Tableaus sind die ersten drei zulässigen Basislösungen und der jeweils zugehörige Zielfunktionswert abzulesen. Man erhält: 1) (0, 0, 15, 3)T mit z = 0 2) ( 0, 32 , 21 2 , 0 )T mit z = 3 3) (3, 6, 0, 0)T mit z = 15 Da es jedoch im dritten Simplex-Tableau mit c4 = 57 einen positiven Zielfunktionskoeffizienten mit ai4 ≤ 0 für i = 1, 2 gibt, ist das zweite Stoppkriterium erfüllt. Das heißt, die Zielfunktion z ist aufZ nach oben unbeschränkt und es existiert somit keine optimale Lösung. Degeneration Eine zulässige Basislösung x = (x1, . . . , xn+m)T ∈ Rn+m besitzt die Eigenschaft, dass x ≥ 0 gilt und die Einträge, die zu den n Nichtbasisvariablen gehören, gleich Null sind (vgl. Definition 25.16). Nimmt jedoch auch eine dermBasisvariablen den Wert Null an, d. h. sind mehr als n Einträge der Basislösung x gleich Null, dann wird die zulässige Basislösung als degeneriert oder entartet bezeichnet. Andernfalls heißt sie nicht degeneriert oder nicht entartet. Das Auftreten von Degeneration wird in der Literatur zur linearen Optimierung ausführlich behandelt (siehe z. B. Hadley [22] und Werner [72]). Denn ihr Vorkommen stellt die einzige Möglichkeit dar, dass der Simplex-Algorithmus nicht nach endlich vielen Schritten mit einer optimalen Lösung oder der Information, dass die Zielfunktion z auf dem zulässigen BereichZ nach oben unbeschränkt ist, abbricht. Stattdessen ist es im Falle einer degenerierten Basislösung theoretisch möglich, dass der Simplex-Algorithmus in einen sogenannten Zyklus gerät, bei dem die Austauschschritte immer wieder zu demselben Eckpunkt führen. Dieses Phänomen verhindert somit, dass der Simplex-Algorithmus ohne Zusatzregel ein endliches Verfahren ist. Durch eine „Anti-Zyklen-Regel“, die präzisiert, wie in jedem Austauschschritt die aufzunehmende Nichtbasisvariable und die zu entfernende Basisvariable zu wählen sind, kann jedoch auch im Falle einer degenerierten Basislösung die Endlichkeit des Simplex-Algorithmus gesichert werden. Da jedoch das Phänomen von Zyklen bislang nur in eigens hierzu konstruierten Beispielen beobachtet wurde (siehe z. B. Papadimitriou-Steiglitz [52], Seite 53), spielen Zusatzregeln zur Vermeidung von Zyklen in der Praxis keine Rolle und werden bei der Implementierung des Simplex- Algorithmus nicht berücksichtigt. 25.6 Phase I und Phase II des Simplex-Algorithmus Bei der bisherigen Betrachtung wurde stets angenommen, dass für die rechte Seite des linearen Gleichungssystems (25.13) b ≥ 0 (25.32) gilt (vgl. (25.27)). Diese Annahme stellte sicher, dass (0, . . . , 0, b1, . . . , bm)T ∈ Rn+m nur nichtnegative Einträge besitzt und daher eine erste zulässige Basislösung bzw. der Teilvektor (0, . . . , 0)T ∈ Rn ein Eckpunkt des zulässigen Bereichs Z ist. Mit Hilfe des Simplex-Algorithmus wurde diese zulässige Basislösung dann sukzessive verbessert bis die optimale Lösung resultierte oder man die Information erhielt, dass die Zielfunktion z auf dem zulässigen Bereich Z nach oben unbeschränkt ist und damit keine optimale Lösung existiert. Wenn jedoch ein lineares Optimierungsproblem in Standardform die Annahme (25.32) nicht erfüllt, dann muss zuerst in einer Vorphase, der sogenannten Phase I, eine erste zulässige Basislösung ermittelt werden. Diese zulässige Basislösung dient dann in der Hauptphase, der sogenannten Phase II, 782 Kapitel 2525.6 Phase I und Phase II des Simplex-Algorithmus Abb. 25.8: Ablauf des Simplex-Algorithmus, wobei NBV für Nichtbasisvariable und OL für Optimallösung steht 783 Kapitel 25 Lineare Optimierung als Ausgangspunkt des Simplex-Algorithmus und wird dann wieder wie oben beschrieben durch Austauschschritte sukzessive verbessert. Die Phase I basiert auf den beiden folgenden Auswahl- und Stoppkriterien: a’) Auswahl der Pivotspalte (d. h. der aufzunehmenden Nichtbasisvariablen): Gilt br < 0 für ein r ∈ {1, . . . , m} und ist der kleinste Eintrag ark auf der linken Seite negativ, dann wähle die zugehörige Spalte k als Pivotspalte. 1. Stoppkriterium: Gilt bi ≥ 0 für alle i = 1, . . . , m, dann liegt bereits eine zulässige Basislösung vor. 2. Stoppkriterium: Gibt es ein i ∈ {1, . . . , m} mit bi < 0 und aij ≥ 0 für alle j = 1, . . . , n + m, dann existiert keine zulässige Basislösung. b’) Auswahl der Pivotzeile (d. h. der zu entfernenden Basisvariablen): Gilt bi < 0 für alle i = 1, . . . , m oder aik ≤ 0 für alle i ∈ {1, . . . , m} mit bi > 0, dann wähle Zeile r als Pivotzeile. Andernfalls wähle unter allen Zeilen i ∈ {1, . . . , m}, für die bi ≥ 0 und aik > 0 gilt, die Pivotzeile l so, dass der Quotient bi aik am kleinsten ist. Das heißt, wähle die Pivotzeile l so, dass bl alk = min { bi aik : bi ≥ 0, aik > 0 } gilt. Wird das Minimum in mehreren Zeilen angenommen, dann kann eine dieser Zeilen beliebig ausgewählt werden. Die Rechenschritte von Phase I werden so oft durchlaufen, bis bi ≥ 0 für alle i = 1, . . . , m gilt und damit eine erste zulässige Basislösung vorliegt, oder die Phase I und somit auch der Simplex-Algorithmus ohne zulässige Basislösung abbrechen. Im folgenden Beispiel wird ein lineares Optimierungsproblem in Standardform betrachtet, dass die Annahme (25.32) nicht erfüllt, und für das daher zuerst in Phase I eine zulässige Basislösung bestimmt werden muss. Beispiel 25.23 (Lineares Optimierungsproblem in Standardform mit b ≥ 0) Gegeben sei das folgende lineare Optimierungsproblem in Standardform: Maximiere z(x1, x2) = x1 + x2 + 1 unter den Nebenbedingungen −x2 ≤ −2 x1 − x2 ≤ 0 −x1 − x2 ≤ −2 (25.33) x2 ≤ 4 und den Nichtnegativitätsbedingungen x1, x2 ≥ 0. Für die Nebenbedingungen (25.33) erhält man durch Einführung von Schlupfvariablen: −x2+x3 = −2 x1−x2 +x4 = 0 −x1−x2 +x5 = −2 x2 +x6 = 4 Das erste Simplex-Tableau lautet somit: NBV NBV BV BV BV BV −z x1 x2 x3 x4 x5 x6 (0) 1 1 1 0 0 0 0 −1 (1) 0 0 −1 1 0 0 0 −2 (2) 0 1 −1 0 1 0 0 0 (3) 0 −1 −1 0 0 1 0 −2 (4) 0 0 1 0 0 0 1 4 Daraus lässt sich unmittelbar die erste Basislösung (0, 0,−2, 0,−2, 4)T ablesen. Da sie negative Einträge besitzt, ist sie nicht zulässig und der Teilvektor (0, 0)T mit den Werten für die beiden Entscheidungsvariablen x1 und x2 gehört somit nicht zum zulässigen Bereich Z (vgl. Abbildung 25.9). Bevor der Simplex-Algorithmus angewendet werden kann, muss daher zuerst eine erste zulässige Basislösung bestimmt werden (Phase I). Die erste Nebenbedingungszeile im obigen Tableau enthält mit −2 einen negativen Eintrag auf der rechten und mit −1 einen negativen Eintrag auf der linken Seite. Damit ist die Voraussetzung für das Auswahlkriterium a’) erfüllt. Die zu −1 gehörende Spalte wird somit zur Pivotspalte und die Variable x2 zur neuen Basisvariablen. Gemäß dem Auswahlkriterium b’) kommt dann nur noch die vierte Nebenbedingungszeile als Pivotzeile in Frage. Das heißt, die Variable x6 wird aus der Basis entfernt und 784 Kapitel 2525.7 Dualität x1 x2 0 1 2 3 4 0 1 2 3 4 5 6 x2 = 2 x2 = 4 x1 − x2 = 0 x1 + x2 = 2 Z x* z(x1, x2) Abb. 25.9: Lineares Optimierungsproblem mit (0, 0)T ∈ Z das Pivotelement (Schnittstelle von Pivotspalte und Pivotzeile) ist durch 1 gegeben. Bei der Durchführung des Austauschschritts x2 ↔ x6 wird wie gewohnt durch elementare Zeilenumformungen in der Pivotspalte ein Einheitsvektor erzeugt. Man erhält dann das folgende Simplex-Tableau: NBV BV BV BV BV NBV −z x1 x2 x3 x4 x5 x6 (0′) 1 1 0 0 0 0 −1 −5 (0)− (4) (1′) 0 0 0 1 0 0 1 2 (1)+ (4) (2′) 0 1 0 0 1 0 1 4 (2)+ (4) (3′) 0 −1 0 0 0 1 1 2 (3)+ (4) (4) 0 0 1 0 0 0 1 4 Es gilt nun bi ≥ 0 für i = 1, 2, 3, 4. Das heißt, das erste Stoppkriterium ist erfüllt und durch (0, 4, 2, 4, 2, 0)T und (0, 4)T ist eine erste zulässige Basislösung bzw. ein Eckpunkt vonZ gegeben. Auf die erste zulässige Basislösung kann nun in gewohnter Weise der Simplex-Algorithmus angewendet werden. Man erhält dann für die optimale Basislösung und den zugehörigen Zielfunktionswert (4, 4, 2, 0, 6, 0)T bzw. z = 9. 25.7 Dualität J. v. Neumann auf einer US-amerikanischen Briefmarke Jedem linearen Optimierungsproblem ist in eindeutiger Weise ein sogenanntes duales lineares Optimierungsproblem zugeordnet, weshalb man auch von dem primalen Problem und dem zugehörigen dualen Problem spricht. Die Bedeutung der Dualität für die lineare Optimierung wurde vor allem von dem US-amerikanischen Mathematiker John von Neumann (1903–1957) früh erkannt. Mittlerweile hat sich aus diesen Anfängen eine ganze Dualitätstheorie entwickelt, deren Ergebnisse bei Weiterentwicklungen des Simplex-Algorithmus (siehe hierzu auch Abschnitt 25.8) sowie in vielen anderen Bereichen Anwendung finden. Hierzu zählen zum Beispiel die Spieltheorie, die ganzzahlige lineare Optimierung, die Netzplantechnik oder die Lösung strukturierter linearer Optimierungsprobleme wie Transportund Zuordnungsprobleme. Darüber hinaus besitzt das duale Problem die interessante ökonomische Interpretation als das lineare Optimierungsproblem des wirtschaftlichen Gegenspielers (siehe Seite 791). 785 Kapitel 25 Lineare Optimierung Primales und duales lineares Problem Das primale und das zugehörige duale Problem sind wie folgt definiert: Definition 25.24 (Primales und duales Problem) Ein lineares Optimierungsproblem in Standardform Maximiere zP (x) = cT x (25.34) unter den Bedingungen A x ≤ b und x ≥ 0 (25.35) wird auch als primales Problem (P) bezeichnet. Das lineare Minimierungsproblem Minimiere zD(y) = bT y (25.36) unter den Bedingungen AT y ≥ c und y ≥ 0 (25.37) heißt dann das zu (P) gehörige duale Problem (D). Durch diese Definition wird einem primalen Problem in Standardform (P) ein duales Problem (D) zugeordnet. Da jedoch jedes lineare Optimierungsproblem in ein lineares Optimierungsproblem in Standardform überführt werden kann, ist damit für jedes lineare Optimierungsproblem ein duales Problem erklärt. Insbesondere kann auch das zu (D) duale Problem bestimmt werden. Aus Definition 25.24 ist ersichtlich, dass dann wieder das primale Ausgangsproblem (P) resultiert. Das heißt, dass die Beziehung zwischen primalem und dualem Problem in dem Sinne symmetrisch ist, dass das duale Problem des dualen Problems wieder mit dem primalen Problem übereinstimmt. Es ist daher unerheblich, welches der beiden linearen Optimierungsprobleme als das primale und welches als das duale Problem betrachtet wird. Die Bildung des dualen Problems (D) zu einem primalen Problem in Standardform (P) besteht aus den folgenden fünf einfachen Schritten: a) Aus dem Maximierungsproblem (P) wird ein Minimierungsproblem (D). b) Aus den ≤–Nebenbedingungen werden ≥–Nebenbedingungen. c) Die Koeffizientenmatrix A wird transponiert. d) Die rechte Seite der Nebenbedingungen von (P) wird zum Vektor mit den Zielfunktionskoeffizienten von (D). e) Der Vektor c mit den Zielfunktionskoeffizienten von (P) wird zur rechten Seite der Nebenbedingungen von (D). Besitzt also das primale Problem (P) n Entscheidungsvariablen x1, . . . , xn und m Nebenbedingungen vom Typ ≤, dann hat das zugehörige duale Problem (D) m Entscheidungsvariablen y1, . . . , ym und n Nebenbedingungen vom Typ ≥. Beispiel 25.25 (Primales und zugehöriges duales Problem) a) In Beispiel 25.4 wurde das folgende primale Problem (P) betrachtet: Maximiere zP (x1, x2) = 2x1 + 3x2 unter den Nebenbedingungen 4x1 + 3x2 ≤ 600 2x1 + 2x2 ≤ 320 3x1 + 7x2 ≤ 840 und den Nichtnegativitätsbedingungen x1, x2 ≥ 0. Das zugehörige duale Problem (D) lautet somit: Minimiere zD(y1, y2, y3)=600y1+320y2+840y3 unter den Nebenbedingungen 4y1 + 2y2 + 3y3 ≥ 2 3y1 + 2y2 + 7y3 ≥ 3 und den Nichtnegativitätsbedingungen y1, y2, y3 ≥ 0. Ferner stimmt das duale Problem von (D) mit dem ursprünglich gegebenen primalen Problem (P) überein. b) In Beispiel 25.20 wurde das folgende primale Problem (P) betrachtet: Maximiere zP (x1, x2, x3, x4)=2x1+x2+3x3+x4 unter den Nebenbedingungen 2x1+4x2 +x4 ≤ 20 x1+ x2+5x3+x4 ≤ 30 x2+ x3+x4 ≤ 10 786 Kapitel 2525.7 Dualität und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. Das zugehörige duale Problem (D) lautet somit: Minimiere zD(y1, y2, y3)=20y1+30y2+10y3 (25.38) unter den Nebenbedingungen 2y1 + y2 ≥ 2 4y1 + y2 + y3 ≥ 1 (25.39) 5y2 + y3 ≥ 3 y1 + y2 + y3 ≥ 1 und den Nichtnegativitätsbedingungen y1, y2, y3 ≥ 0. (25.40) Ferner stimmt das duale Problem von (D) mit dem ursprünglich gegebenen primalen Problem (P) überein. Dualitätssätze Im Folgenden bezeichnen die Mengen ZP = {x ∈ Rn : A x ≤ b, x ≥ 0} und ZD = { y ∈ Rm : AT y ≥ c, y ≥ 0} den zulässigen Bereich des primalen bzw. des zugehörigen dualen Problems. Die Tatsache, dass die Strukturen des primalen und des zugehörigen dualen Problems so eng zusammenhängen, legt die Vermutung nahe, dass auch ihre Zielfunktionswerte und optimalen Lösungen in einer engen Beziehung zueinander stehen. Diese Zusammenhänge werden durch sogenannte Dualitätssätze beschrieben. Das folgende als schwacher Dualitätssatz bekannte Resultat besagt, dass der Zielfunktionswert jeder zulässigen Lösung des dualen Problems eine obere Schranke für die Zielfunktionswerte des primalen Problems und umgekehrt der Zielfunktionswert jeder zulässigen Lösung des primalen Problems eine untere Schranke für die Zielfunktionswerte des dualen Problems darstellt: Satz 25.26 (Schwacher Dualitätssatz) Es sei (P) ein primales Problem und (D) das zugehörige duale Problem. Dann gilt: x ∈ ZP und y ∈ ZD ⇒ zP (x) ≤ zD(y) (25.41) Beweis: Für x ∈ ZP und y ∈ ZD gilt A x ≤ b und AT y ≥ c. Daraus folgt unter Berücksichtigung der Rechenregeln für das Transponieren von Matrizen (vgl. Abschnitt 8.5) zP (x) = cT x ≤ (AT y)T x = yT A x = (yT A x)T = (A x)T y ≤ bT y = zD(y) und damit die Behauptung. Das folgende Resultat wird häufig als starker Dualitätssatz bezeichnet. Es sagt aus, dass in (25.41) genau dann zP (x) = zD(y) gilt, wenn x und y optimale Lösungen des primalen bzw. dualen Problems sind. Darüber hinaus besagt es, dass das primale Problem genau dann eine optimale Lösung besitzt, wenn auch für das duale Problem eine optimale Lösung existiert, und dass aus der Existenz von zulässigen Lösungen sowohl für das primale als auch das duale Problem die Existenz von optimalen Lösungen für beide Probleme folgt: Satz 25.27 (Starker Dualitätssatz) Für ein primales Problem (P) und sein zugehöriges duales Problem (D) gelten die folgenden Aussagen: a) Es gilt x∗ ∈ ZP , y∗ ∈ ZD und zP (x∗) = zD(y∗) genau dann, wenn x∗ eine optimale Lösung von (P) und y∗ eine optimale Lösung von (D) ist. b) (P) besitzt eine optimale Lösung x∗ genau dann, wenn (D) eine optimale Lösung y∗ besitzt. c) Aus ZP = ∅ und ZD = ∅ folgt, dass (P) und (D) jeweils eine optimale Lösung x∗ bzw. y∗ besitzen. d) Ist x∗ eine optimale Lösung von (P) und y∗ eine optimale Lösung von (D), dann gilt (b−A x∗)T y∗ = 0 und (AT y∗ − c)T x∗ = 0. Beweis: Zu a): Siehe z. B. Naeve et al. [10], Seiten 360–361. Zu b) und c): Für den umfangreicheren Beweis siehe z. B. Bol [5], Seiten 151–155. 787 Kapitel 25 Lineare Optimierung Zu d): Gemäß Aussage a) gilt cT x∗ = zP (x∗) = zD(y∗) = bT y∗. Zusammen mit (y∗)T A x∗ = (x∗)T AT y∗ folgt daraus 0 = bT y∗ − cT x∗ = bT y∗ − (x∗)T AT y∗ + (y∗)T A x∗ − cT x∗ = (b − A x∗) ︸ ︷︷ ︸ ≥0 T y∗ ︸︷︷︸ ≥0 +(AT y∗ − c) ︸ ︷︷ ︸ ≥0 T x∗︸︷︷︸ ≥0 . Das heißt, es gilt (b−A x∗)T y∗ = 0 und (AT y∗ − c)T x∗ = 0. Der starke Dualitätssatz führt zu den folgenden interessanten Schlussfolgerungen: a) Besitzen das primale Problem (P) und das duale Problem (D) jeweils zulässige Lösungen, dann besitzen sie auch jeweils optimale Lösungen x∗ und y∗ mit zP (x∗) = zD(y∗) (vgl. Satz 25.27a) und c)). b) Ist die Zielfunktion zP des primalen Problems (P) nach oben unbeschränkt, dann besitzt das duale Problem (D) keine zulässige Lösung, und ist umgekehrt die Zielfunktion zD des dualen Problems (D) nach unten unbeschränkt, dann besitzt das primale Problem (P) keine zulässige Lösung. Denn sonst müssten nach Satz 25.27c) sowohl für (P) als auch für (D) optimale Lösungen existieren. c) Besitzt das duale Problem (D) keine zulässige Lösung, dann besitzt das primale Problem (P) entweder eine nach oben unbeschränkte Zielfunktion zP (vgl. Satz 25.27 b)) x1 x2 − 1 0 1 2 3 1 2 3 4 5 6 x1 − x2 = 1 ZP zP(x1, x2) Abb. 25.10: Lineares Optimierungsproblem mit einer auf ZP unbeschränkten Zielfunktion oder es existiert auch für (P) keine zulässige Lösung. Denn bei Existenz einer optimalen Lösung von (P) müsste gemäß Satz 25.27b) auch (D) eine optimale und damit insbesondere eine zulässige Lösung besitzen. Beispiel 25.28 (Primales und duales Problem) Die Zielfunktion des primalen Problems (P) Maximiere zP (x1, x2) = x1 + 2x2 unter den Neben- und Nichtnegativitätsbedingungen x1 − x2 ≤ 1 bzw. x1, x2 ≥ 0 ist auf dem zulässigen Bereich ZP nach oben unbeschränkt (vgl. Abbildung 25.10). Das zugehörige duale Problem (D) Minimiere zD(y1) = y1 unter den Bedingungen y1 ≥ 1,−y1 ≥ 2 bzw. y1 ≥ 0 besitzt daher keine zulässige Lösung. Das heißt, es gilt ZD = ∅. Dies ist auch daraus unmittelbar ersichtlich, dass nicht gleichzeitig die beiden Bedingungen y1 ≥ 0 und y1 ≤ −2 erfüllt sein können. 788 Kapitel 2525.7 Dualität Simultane Lösung des primalen und dualen Problems Mit Hilfe des Simplex-Algorithmus können ein primales Problem in Standardform (P) und das dazugehörige duale Problem (D) simultan gelöst werden. Das heißt, wenn eine optimale Lösung existiert, dann kann nach Anwendung des Simplex-Algorithmus aus dem dabei resultierenden Simplex- Endtableau −z x1 . . . xn xn+1 . . . xn+m 1 −c′1 . . . −c′n −c′n+1 . . . −c′n+m −z′0 0 a′11 . . . a ′ 1n a ′ 1n+1 . . . a ′ 1n+m b ′ 1 ... ... . . . ... ... . . . ... ... 0 a′m1 . . . a ′ mn a ′ mn+1 . . . a ′ mn+m b ′ m nicht nur die optimale Lösung x∗ des primalen Problems (P), sondern auch die optimale Lösung y∗ des dualen Problems (D) abgelesen werden. Diese ist gegeben durch die mit −1 multiplizierten Einträge für die m Schlupfvariablen xn+1, . . . , xn+m von (P) in der Zielfunktionszeile des Simplex-Endtableaus. Das heißt, es gilt y∗ = (c′n+1, . . . , c′n+m )T mit zD(y∗) = bT y∗ = z′0. Folglich kann ein lineares Minimierungsproblem der Form (25.36)–(25.37) dadurch gelöst werden, dass zum zugehörigen dualen Problem (25.34)–(25.35) übergegangen wird. Denn dieses duale Problem ist ein lineares Maximierungsproblem in Standardform, das mit Hilfe des Simplex-Algorithmus gelöst werden kann. Die gesuchte optimale Lösung des linearen Minimierungsproblems kann anschließend wie oben beschrieben aus der Zielfunktionszeile des resultierenden Simplex-Endtableaus abgelesen werden. Beispiel 25.29 (Simultane Lösung des primalen und dualen Problems) a) Die optimale Lösung des in Beispiel 25.25a) betrachteten dualen Problems Minimiere zD(y1, y2, y3)=600y1+320y2+840y3 unter den Nebenbedingungen 4y1 + 2y2 + 3y3 ≥ 2 3y1 + 2y2 + 7y3 ≥ 3 und den Nichtnegativitätsbedingungen y1, y2, y3 ≥ 0 kann aus dem Simplex-Endtableau (25.30) des in Beispiel 25.19 betrachteten zugehörigen primalen Problems leicht abgelesen werden. Sie ist gegeben durch y∗ = ( 0, 5 8 , 1 4 )T mit zD(y∗) = 410. b) Die optimale Lösung des in Beispiel 25.25b) betrachteten dualen Problems (25.38)–(25.40) kann aus dem Simplex-Endtableau des zugehörigen primalen Problems in Beispiel 25.20 leicht abgelesen werden. Sie ist gegeben durch y∗ = ( 7 10 , 3 5 , 0 )T mit zD(y∗) = 32. Im folgenden Beispiel wird die Vorgehensweise anhand eines konkreten Mischungsproblems aus der Nahrungsmittelindustrie demonstriert: Beispiel 25.30 (Simultane Lösung des primalen und dualen Problems) Ein Lebensmittelkonzern produziert die Nahrungsmittelmischung Brainfood, die aus den vier Nahrungsmitteln N1, N2, N3, N4 besteht. Die Nahrungsmittel enthalten die vier Vitamine A,B,C,D in bestimmten Masseneinheiten (ME) mA,mB,mC,mD . Diese Masseneinheiten an Vitaminen je Kilogramm, die Kosten je Kilogramm der Nahrungsmittel und der Mindestbedarf der vier Vitamine sind in der folgenden Tabelle zusammengestellt: ME ME an Vitaminen Mindestbedarf je kg an Vitaminen N1 N2 N3 N4 mA 2 3 2 5 10 mB 1 2 0 2 12 mC 2 1 1 1 20 mD 1 1 0 1 15 Kosten je kg 10 8 12 6 789 Kapitel 25 Lineare Optimierung NBV NBV NBV NBV BV BV BV BV −zD y1 y2 y3 y4 y5 y6 y7 y8 (0) 1 10 12 20 15 0 0 0 0 0 (1) 0 2 1 2 1 1 0 0 0 10 (2) 0 3 2 1 1 0 1 0 0 8 (3) 0 2 0 1 0 0 0 1 0 12 (4) 0 5 2 1 1 0 0 0 1 6 NBV NBV BV NBV NBV BV BV BV −zD y1 y2 y3 y4 y5 y6 y7 y8 (0′) 1 −10 2 0 5 −10 0 0 0 −100 (0)− 20 · (1′) (1′) 0 1 12 1 1 2 1 2 0 0 0 5 1/2 · (1) (2′) 0 2 32 0 1 2 − 12 1 0 0 3 (2)− (1′) (3′) 0 1 − 12 0 − 12 − 12 0 1 0 7 (3)− (1′) (4′) 0 4 32 0 1 2 − 12 0 0 1 1 (4)− (1′) NBV NBV BV BV NBV BV BV NBV −zD y1 y2 y3 y4 y5 y6 y7 y8 (0′′) 1 −50 −13 0 0 −5 0 0 −10 −110 (0′)− 5 · (4′′) (1′′) 0 −3 −1 1 0 1 0 0 −1 4 (1′)− 1/2 · (4′′) (2′′) 0 −2 0 0 0 0 1 0 −1 2 (2′)− 1/2 · (4′′) (3′′) 0 5 1 0 0 −1 0 1 1 8 (3′)+ 1/2 · (4′′) (4′′) 0 8 3 0 1 −1 0 0 2 2 2 · (4′) Tabelle 25.4: Simplex-Tableaus zu Beispiel 25.30 Bezeichnen die Variablen x1, x2, x3, x4 die benötigten Mengen der vier Nahrungsmittel N1, N2, N3, N4 in Kilogramm und hat der Betrieb die Zielsetzung, dass die Kosten unter Beachtung des Mindestbedarfs für die vier Vitamine minimiert werden sollen, dann führt dies zu dem linearen Minimierungsproblem: Minimiere zP (x1, x2, x3, x4)=10x1+8x2+12x3+6x4 (25.42) unter den Nebenbedingungen 2x1 + 3x2 + 2x3 + 5x4 ≥ 10 x1 + 2x2 + 2x4 ≥ 12 (25.43) 2x1 + x2 + x3 + x4 ≥ 20 x1 + x2 + x4 ≥ 15 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. (25.44) Das dazu duale Problem lautet: Maximiere zD(y1,y2,y3,y4)=10y1+12y2+20y3+15y4 (25.45) unter den Nebenbedingungen 2y1 + y2 + 2y3 + y4 ≤ 10 3y1 + 2y2 + y3 + y4 ≤ 8 (25.46) 2y1+ + y3 + ≤ 12 5y1 + 2y2 + y3 + y4 ≤ 6 und den Nichtnegativitätsbedingungen y1, y2, y3, y4 ≥ 0. (25.47) Bei dem linearen Maximierungsproblem (25.45)–(25.47) handelt es sich um ein lineares Optimierungsproblem in Standardform. Die Anwendung des Simplex-Algorithmus auf dieses lineare Maximierungsproblem liefert die Simplex-Tableaus in Tabelle 25.4. 790 Kapitel 2525.7 Dualität Im ersten Austauschschritt wurde die Nichtbasisvariable y3 gegen die Basisvariable y5 und im zweiten Austauschschritt die Nichtbasisvariable y4 gegen die Basisvariable y8 ausgetauscht. Im dritten Simplex-Tableau sind bereits alle Zielfunktionskoeffizienten cj kleiner oder gleich Null und für die optimale Lösung und den zugehörigen Zielfunktionswert des linearen Maximierungsproblems (25.45)–(25.47) erhält man somit y∗ = (0, 0, 4, 2)T bzw. zD(y∗) = 110. Die optimale Lösung des zum linearen Maximierungsproblem gehörigen dualen Problems, also des linearen Minimierungsproblems (25.42)–(25.44), kann ebenfalls aus dem Simplex-Endtableau abgelesen werden und lautet x∗ = (5, 0, 0, 10)T bzw. zP (x∗) = 110. Ökonomische Interpretation der Dualität Das zu einem gegebenen linearen Optimierungsproblem gehörige duale Problem besitzt oftmals eine interessante ökonomische Interpretation, nämlich als das lineare Optimierungsproblem des wirtschaftlichen Gegenspielers. Eine solche Interpretation erlaubt häufig einen tieferen Einblick in die ökonomische Problemstellung. Dies soll im Folgenden anhand einer allgemeinen Fragestellung aus der Produktionsplanung verdeutlicht werden. Betrachtet wird dazu ein Betrieb, der einen Produktionsplan für n Produkte erstellen möchte, welcher unter Beachtung gegebener Kapazitätsbeschränkungen für die m benötigten Produktionsfaktoren zum maximalen Gesamtgewinn führt. Als lineares Problem formuliert lautet diese Problemstellung Maximiere zP (x) = cT x unter den Bedingungen A x ≤ b und x ≥ 0, wobei die Einträge des Vektors x = (x1, . . . , xn)T die Produktionsmengen für die n zu produzierenden Produkte bezeichnen. Das hierzu duale Problem lautet: Minimiere zD(y) = bT y unter den Bedingungen AT y ≥ c und y ≥ 0 Dieses duale Problem kann wie folgt interpretiert werden: Ein Mitbewerber macht dem Betrieb das Angebot, allem Produktionsfaktoren zu kaufen bzw. zu mieten und bietet hierzu für den i-ten Produktionsfaktor yi ≥ 0 Geldeinheiten je Mengeneinheit. Seine Gesamtkosten belaufen sich somit auf m∑ i=1 biyi = bT y = zD(y), und er wird versuchen, diese zu minimieren. Der Betrieb wird jedoch auf dieses Angebot nur eingehen, wenn die Nebenbedingungen m∑ i=1 ajiyi ≥ cj für j = 1, . . . , n (25.48) erfüllt sind. Das heißt, wenn der vom Mitbewerber gezahlte Preis für sämtliche m Produktionsfaktoren zur Produktion einer Mengeneinheit des j -ten Produkts nicht kleiner ist als der Gewinn cj , den der Betrieb erhalten würde, wenn er die Produktion selbst durchführt. In Matrixschreibweise lauten die Nebenbedingungen (25.48) AT y ≥ c. Dies zeigt, dass der Mitbewerber das duale lineare Optimierungsproblem zu lösen hat. Der schwache Dualitätssatz (vgl. Satz 25.26) kann nun wie folgt interpretiert werden: Ist x ∈ Rn ein zulässiger Produktionsplan für den Betrieb und y ∈ Rm ein akzeptables Angebot des Mitbewerbers (d. h. die Nebenbedingungen (25.48) sind erfüllt), dann gilt zP (x) ≤ zD(y). Das heißt, der Betrieb kann keinen größeren Gewinn erzielen als den Betrag, den er bei einem akzeptablen Angebot des Mitbewerbers erhalten würde. Der starke Dualitätssatz besagt, dass der maximale Gewinn des Betriebs gleich den minimalen Kosten des Mitbewerbers ist, unter der Voraussetzung, dass zulässige Produktionspläne und akzeptable Angebote existieren (vgl. Satz 25.27a)). Ferner sagt er aus, dass es zu einem optimalen Produktionsplan x∗ stets ein für den Mitbewerber optimales Angebot y∗ mit zP (x∗) = zD(y∗) gibt (vgl. Satz 25.27a) und b)). Darüber hinaus folgen aus Satz 25.27d) die Gleichgewichtsbedingungen (b − A x∗)T y∗ = 0 und (AT y∗ − c)T x∗ = 0. (25.49) Wird in einem optimalen Produktionsplan x∗ das j -te Produkt hergestellt, ist also xj > 0, dann folgt aus der zweiten Gleichgewichtsbedingung in (25.49) m∑ i=1 ajiy ∗ i = (AT y∗)j = cj . Das heißt, der vom Mitbewerber gezahlte Preis für sämtliche m Produktionsfaktoren zur Produktion einer Mengeneinheit 791 Kapitel 25 Lineare Optimierung des j -ten Produkts ist dann gleich dem Gewinn cj , den der Betrieb erhält, wenn er die Produktion selbst durchführt. Wird die Kapazitätsbeschränkung für den i-ten Produktionsfaktor in einem optimalen Produktionsplan nicht voll ausgeschöpft, gilt also (A x∗)i < bi , dann folgt aus der ersten Gleichgewichtsbedingung in (25.49) y∗i = 0. Der Mitbewerber wird somit in einem für ihn optimalen Angebot y∗ für den i-ten Produktionsfaktor nichts bezahlen. Für viele wirtschaftswissenschaftliche Problemstellungen, die zu linearen Optimierungsproblemen führen, ist eine ähnliche Interpretation des dualen Problems und der Ergebnisse der Dualitätstheorie möglich. 25.8 Dualer Simplex-Algorithmus Der bisher betrachtete Simplex-Algorithmus geht von einem linearen Optimierungsproblem in Standardform aus, das auf der rechten Seite der Nebenbedingungen nur nichtnegative Werte b1, . . . , bm besitzt (vgl. (25.27)). Diese Nichtnegativität der rechten Seite wird dann bei den einzelnen Austauschschritten des Simplex-Algorithmus beibehalten (Erfüllung der Zulässigkeitsbedingung), wobei gleichzeitig versucht wird, in der Zielfunktionszeile nur nicht positive Werte zu erzeugen (Erfüllung der Optimalitätsbedingung), so dass eine optimale Lösung vorliegt. Idee des dualen Simplex-Algorithmus Der duale Simplex-Algorithmus basiert dagegen auf der naheliegenden Idee, diesen Lösungsansatz umzukehren. Das heißt, der duale Simplex-Algorithmus geht von einem Simplex-Tableau aus, dessen Zielfunktionszeile nur nicht positive Werte aufweist, aber die Nichtnegativität der rechten Seite nicht erfüllt ist. Bei den Austauschschritten des dualen Simplex-Algorithmus wird dann sichergestellt, dass die Zielfunktionszeile weiterhin nur nicht positive Werte aufweist (Erfüllung der Optimalitätsbedingung), wobei gleichzeitig versucht wird, auf der rechten Seite nur nichtnegative Werte zu erzeugen (Erfüllung der Zulässigkeitsbedingung). Die erste zulässige Lösung ist dann auch die optimale Lösung, da die Optimalitätsbedingung bei jedem Austauschschritt erhalten wurde. Die Bezeichnung als dualer Simplex-Algorithmus ist dabei dadurch motiviert, dass diese Vorgehensweise der Lösung des dualen Problems mittels des gewöhnlichen Simplex- Algorithmus gleichkommt. Der duale Simplex-Algorithmus bietet sich für lineare Optimierungsprobleme in Standardform an, deren Zielfunktionskoeffizienten cj alle nicht positiv sind und die rechte Seite der Nebenbedingungen negative Werte aufweist. Solche linearen Optimierungsprobleme entstehen häufig auf natürliche Weise, wenn ein Minimierungsproblem mit ausschließlich Nebenbedingungen vom Typ ≥ und Zielfunktionskoeffizienten cj ≥ 0 durch Multiplikation der Zielfunktion und der Nebenbedingungen mit −1 in ein lineares Maximierungsproblem überführt wird (vgl. Beispiel 25.31). In einem solchen Fall ist der duale Simplex- Algorithmus eine interessante Alternative zum gewöhnlichen Simplex-Algorithmus, bei dessen Anwendung zuerst in einer Phase I eine zulässige Lösung ermittelt werden muss. Auswahl- und Stoppkriterien Der duale Simplex-Algorithmus läuft im Wesentlichen wie der gewöhnliche Simplex-Algorithmus ab. Es ist lediglich die Reihenfolge bei der Auswahl der Pivotspalte und der Pivotzeile zu vertauschen. Im Folgenden wird angenommen, dass für die Einträge in der Zielfunktionszeile des Simplex- Ausgangstableaus cj ≤ 0 für alle j = 1, . . . , n+m gilt. Der duale Simplex-Algorithmus basiert dann auf den folgenden Auswahl- und Stoppkriterien: a) Auswahl der Pivotzeile (d. h. der zu entfernenden Basisvariablen): Wähle die Zeile l mit dem kleinsten Wert bl < 0 auf der rechten Seite als Pivotzeile. Diese Wahl der Pivotzeile stellt sicher, dass die rechte Seite der Pivotzeile positiv ist und dabei kein positiver Wert der rechten Seite negativ wird. Wird das Minimum in mehreren Zeilen angenommen, dann kann eine dieser Zeilen beliebig ausgewählt werden. 1. Stoppkriterium: Gilt bi ≥ 0 für i = 1, . . . , m, dann ist die Basislösung zulässig und damit insgesamt optimal. Das heißt, der Vektor x∗ = (x1, . . . , xn)T mit den Werten für die n Entscheidungsvariablen im Simplex-Tableau ist eine optimale Lösung des linearen Optimierungsproblems und z0 ist der zugehörige maximale Zielfunktionswert. Gilt dabei für die Zielfunktionskoeffizienten aller n Nichtbasisvariablen cj < 0, dann ist die optimale Lösung eindeutig. b) Auswahl der Pivotspalte (d. h. der aufzunehmenden Nichtbasisvariablen): Wähle die Spalte k, die in der Pivotzeile l einen Eintrag alk < 0 besitzt und der Quotient ck alk am kleinsten ist. Das 792 Kapitel 2525.8 Dualer Simplex-Algorithmus heißt, wähle die Pivotspalte k so, dass ck alk = min { cj alj : alj < 0 } gilt. Diese Wahl der Pivotspalte verhindert, dass die Einträge in der Zielfunktionszeile positiv werden. 2. Stoppkriterium: Gilt alj ≥ 0 für alle j = 1, . . . , n+m, dann existiert keine zulässige Lösung. Im folgenden Beispiel wird die Anwendung des dualen Simplex-Algorithmus demonstriert: Beispiel 25.31 (Dualer Simplex-Algorithmus) In Beispiel 25.29a) wurde bereits die optimale Lösung des linearen Minimierungsproblems Minimiere z(x1, x2, x3) = 600x1 + 320x2 + 840x3 (25.50) unter den Nebenbedingungen 4x1 + 2x2 + 3x3 ≥ 2 (25.51) 3x1 + 2x2 + 7x3 ≥ 3 und den Nichtnegativitätsbedingungen x1, x2, x3 ≥ 0 (25.52) ermittelt. Dies geschah dadurch, dass die Lösung aus dem Simplex-Endtableau des zugehörigen primalen Problems, einem linearen Optimierungsproblem in Standardform, NBV NBV NBV BV BV −z̃ x1 x2 x3 x4 x5 (0) 1 −600 −320 −840 0 0 0 (1) 0 −4 −2 −3 1 0 −2 (2) 0 −3 −2 −7 0 1 −3 NBV NBV BV BV NBV −z̃ x1 x2 x3 x4 x5 (0′) 1 −240 −80 0 0 −120 360 (0)+ 840 · (2′) (1′) 0 − 197 − 87 0 1 − 37 − 57 (1)+ 3 · (2′) (2′) 0 37 2 7 1 0 − 17 37 −1/7 · (2) NBV BV BV NBV NBV −z̃ x1 x2 x3 x4 x5 (0′′) 1 −50 0 0 −70 −90 410 (0′)+ 80 · (1′′) (1′′) 0 198 1 0 − 78 38 58 −7/8 · (1′) (2′′) 0 − 14 0 1 14 − 14 14 (2′)− 2/7 · (1′′) Tabelle 25.5: Simplex-Tableaus zu Beispiel 25.31 abgelesen wurde. Die optimale Lösung kann jedoch auch mit Hilfe des dualen Simplex-Algorithmus ermittelt werden. Dazu werden die Zielfunktion und die beiden Nebenbedingungen durch Multiplikation mit −1 in ein lineares Maximierungsproblem überführt. Nach Einführung von Schlupfvariablen erhält man das lineare Optimierungsproblem: Maximiere z̃(x1, x2, x3)=−600x1−320x2−840x3 (25.53) unter den Nebenbedingungen −4x1 − 2x2 − 3x3 + x4 = −2 (25.54) −3x1 − 2x2 − 7x3 + x5 = −3 und den Nichtnegativitätsbedingungen x1, x2, x3 ≥ 0. (25.55) Aufgrund der negativen Werte auf der rechten Seite der Nebenbedingungen (25.54) würde bei der Anwendung des gewöhnlichen Simplex-Algorithmus das Simplex- Ausgangstableau keine erste zulässige Basislösung liefern. Das heißt, man müsste in einer Phase I (vgl. Abschnitt 25.6) eine erste zulässige Basislösung ermitteln. Diese Phase I erübrigt sich jedoch bei Anwendung des dualen Simplex-Algorithmus, der aufgrund der ausschließlich negativen Koeffizienten der Zielfunktion (25.53) angewendet werden kann. Der duale Simplex- Algorithmus führt dann zu den Simplex-Tableaus in Tabelle 25.5. 793 Kapitel 25 Lineare Optimierung Im ersten Austauschschritt wurde die Nichtbasisvariable x3 gegen die Basisvariable x5 und im zweiten Austauschschritt die Nichtbasisvariable x2 gegen die Basisvariable x4 ausgetauscht. Mit dem dritten Simplex-Tableau ist die optimale Lösung bereits bestimmt, da alle Zielfunktionskoeffizienten cj weiterhin kleiner oder gleich Null und die Werte auf der rechten Seite nun positiv sind. Für die optimale Lösung und den zugehörigen Zielfunktionswert des linearen Maximierungsproblems (25.53)–(25.55) erhält man somit x∗ = ( 0, 5 8 , 1 4 )T bzw. z̃(x∗) = −410. Das heißt, das lineare Minimierungsproblem (25.50)– (25.52) besitzt ebenfalls die optimale Lösung x∗ =( 0, 58 , 1 4 )T und wegen z=−z̃ ist der zugehörige Zielfunktionswert gegeben durch z(x∗) = 410. Diese Lösung stimmt (natürlich) mit der in Beispiel 25.29a) ermittelten Lösung überein. Vergleicht man die obigen Simplex- Tableaus des dualen Simplex-Algorithmus mit den in Beispiel 25.19 mittels des gewöhnlichen Simplex-Algorithmus ermittelten Simplex-Tableaus, dann stellt man fest, dass die beiden Algorithmen tatsächlich bis auf Unterschiede im Vorzeichen und in der Anordnung von Zeilen und Spalten übereinstimmen. 794

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.