Benutzer:Chi-Vinh/Notizen/Lineare Programmierung

Lineare Programmierung

Gegenstand des Satzes: Lineares Ungleichungssystem =

Sei A·x ≥ b ein lineares Ungleichungssystem mit Zielfunktion γ  : $F^{n}$ → F .

Prämisse: Existenz von zwei optimalen Lösungen

Besitzt A · x ≥ b bzgl. γ wenigstens zwei optimale Lösungen

Behauptung: Existenz unendlich vieler optimaler Lösungen

So existieren unendlich viele optimale Lösungen von A · x ≥ b bzgl. γ.

Satz 11.5:

Gegenstand des Satzes

Sei A eine m×n - Matrix und A·x ≥ b ein lösbares lineares Ungleichungssystem. Die Zielfunktion sei γ(x) = $g_{0}$ + $g_{1}$ · $x_{1}$ + ... + $g_{n}$ · $x_{n}$ , wobei x = ($x_{1}$ , ..., $x_{n}$ ) ist.

Prämisse, Eigenschaft

Wenn ein w ∈ F n existiert mit γ(w) > $g_{0}$ und A · w ≥ 0

Behauptung: γ auf Lösungsmenge L:= { alle x | A · x ≥ b }

Dann ist γ auf der Lösungsmenge L von A · x ≥ b unbeschrännkt.

Satz 11.6:

Gegenstand:

Sei L die Lösungsmenge des linearen Ungleichungssystems A · x ≥ b mit b = $(b_{1},...,b_{m})$ ∈ $F^{m}$ und seien $z_{i}$ , 1 ≤ i ≤ m die Zeilenvektoren der m × n - Matrix.

A. Die Zielfunktion sei γ(x) = $g_{0}$+ g · x, mit g = ($g_{1}$ , ..., $g_{n}$ ) ∈ $F^{n}$ , x = ($x_{1},...,x_{n}$ ) und g 0 ∈ F .

Prämisse:

Angenommen es gibt eine Teilmenge T der Ziffern {1, 2, ..., m} derart, dass die folgenden drei Bedingungen erfüllt sind:

• a) {$z_{t}$ | t ∈ T } ist eine Basis des Zeilenraumes von A.
• b) Es gibt ein v ∈ L mit $z_{t}$ · v = $b_{t}$ für alle t ∈ T .
• c) g = P t∈T h t · z t ist eine Linearkombination der Zeilenvektoren z t von A, t ∈ T , mit Koeffizienten h t ≤ 0.

Behautptung:

Dann gelten die folgenden Aussagen:

• (1) Das lineare Gleichungssystem

(G) $z_{t}$ · x = $b_{t}$ , t ∈ T ist lösbar.

• (2) Jede Lösung v ∈ F n von (G) ist eine optimale Lösung von A · x ≥ b bzgl. γ.

Eckenfindung

Satz 12.3:

Die folgenden elementaren Spaltenumformungen einer (m + 1) × (n + 1) - Matrix C mit den Spaltenvektoren $s_{1},...,s_{n+1}$ sind zulässig:

• 1) Vertauschung der Spaltenvektoren s i und s j , mit 1 ≤ i, j ≤ n.
• 2) Multiplikation der i - ten Spalte mit einem 0 6= λ ∈ F , wobei 1 ≤ i ≤ n ist.
• 3) Ersetzung der i - ten Spalte durch die Summe s i +λ·s j f¨ur ein λ ∈ F , wobei i 6= j und j ≤ n ist (es darf i = n + 1 sein).

Satz 12.4:

Sei u eine Lösung des linearen Ungleichungssystems A · x ≥ b mit m × n - Koeffizientenmatrix A. Sei γ(x) = $g_{0}$ + g · x die Gewinnfunktion und B = A k g G ! die zu u gehörige Ausgangsmatrix. Sei C eine Matrix, welche aus B durch zulässige Spaltenumformungen hervorgeht. Wenn C einen Spaltenvektor s j mit j ≤ n hat, dessen Komponenten alle das gleiche Vorzeichen haben und dessen letzte Komponente von Null verschieden ist

dann gelten folgende Aussagen:

• a) Es gibt ein w ∈ Fn mit γ(w) > $g_{0}$ und A · w ≥ 0
• b) γ ist auf der Lösungsmenge L von A · x ≥ b nach oben unbeschränkt.

Sei C eine (m + 1) × (n + 1) - Matrix mit den Zeilenvektoren $z_{1},...,z_{m}+1$ . Eine Teilmenge T von {1, . . . , m + 1} heißt Eckmenge von C, wenn die folgenden Bedingungen erfüllt sind:

• • a) Die Zeilenvektoren $z_{t}$ , t ∈ T , sind voneinander verschiedene Einheitsvektoren.
  • b) $z_{t}$ 6= $e_{n+1}$ für alle t ∈ T .
  • c) Wenn j ≤ n und die j-te Spalte 6= 0 ist, dann ist $z_{t}$ = $e_{j}$ für ein t ∈ T .

Satz 12.5:

Sei u eine Lösung des linearen Ungleichungssystems (U) A · x ≥ b mit m × n - Koeffizientenmatrix A. Sei γ(x) = $g_{0}$ + g · x die Gewinnfunktion und B = A k g G ! die zu u gehörige Ausgangsmatrix. Sei C eine Matrix, welche aus B durch zulässige Spaltenumformungen hervorgeht und die folgenden Eigenschaften hat:

• 1) Die Kontrollspalte von C ist ≥ 0.
• 2) Die Gewinnzeile von C ist ≤ 0.
• 3) C hat eine Eckmenge T .

Dann gilt:

• a) T erfüllt die Bedingungen von Satz 11.6.
• b) Sind $z_{i}$ , 1 ≤ i ≤ m, die Zeilen von A, dann ist das Gleichungssystem

(L) $z_{t}$ · x = $b_{t}$ , t ∈ T, x = ($x_{1},...,x_{n}$ )

lösbar, und jede Lösung v ∈ Fn des Gleichungssystems (L) ist eine optimale Lösung von (U) mit Gewinn γ(v) gleich dem Gewinn G ∗ von C.

Eckenfindungs-Algorithmus

Sei B eine (m + 1) × (n + 1)− Matrix mit Gewinnzeile g = (g 1 , . . . , g n ) und Kontrollspalte k = ($k_{1}$ , . . . , $k_{n}$ ) ≥ 0. Wir setzen zunächst h = 1.

1. (Maximumkriterium) Wähle einen Spaltenindex j mit h ≤ j ≤ n derart, dass s j 6= 0 und |g j | möglichst groß sind. Wenn ein solches j nicht existiert, dann endet der Algorithmus. Wenn es mehrere Möglichkeiten zur Wahl von j gibt, wählt man daraus das kleinste j.

2. (Quotientenkriterium) Ist $s_{j}$ = ($b_{1}j$ , . . . , $b_{m}j$ , $g_{j}$ ) die im ersten Schritt gewählte Spalte, dann ist die relevante Zeilenindexmenge R = {i | $b_{i}j$ 6= 0 und $b_{i}j$ · $g_{j}$ ≤ 0}.

• (a) Wenn R = ∅ , dann bricht der Algorithmus ab (unbeschränkter Fall).
• (b) Wenn R 6= ∅ , wähle einen Zeilenindex i ∈ R mit ki |bij | ≤ kr |brj | für alle r ∈ R. Gibt es daf¨ur mehrere Möglichkeiten, so w¨ahlt man i minimal unter diesen.

• 3. Ersetze B durch die Matrix, welche aus B durch Spaltenpivotierung an der Stelle (i, j) entsteht.

• 4. Wenn j 6= h , ersetze B durch die Matrix, welche aus B durch Vertauschung der j-ten und der h-ten Spalte entsteht.

• 5. Ersetze h durch h + 1.

Wiederhole die Schritte 1 bis 5 so lange, bis der Algorithmus endet.

Satz 12.7

Wendet man den Eckenfindungs-Algorithmus auf eine (m + 1) × (n + 1) - Matrix B mit Kontrollspalte k ≥ 0 an, dann gelten folgende Aussagen:

• a) Im Eckenfindungsalgorithmus werden nur zulässige Spaltenumformungen vorgenommen.
• b) Der Eckenfindungs-Algorithmus endet nach spätestens 5 · n Schritten. Darüber hinaus hat die Endmatrix $B^{*}$ die folgenden Eigenschaften:

c) Die Kontrollspalte von $B^{*}$ ist ≥ 0.

d) Der Gewinn von $B^{*}$ ist mindestens so groß wie der Gewinn von B.

e) Wenn der Eckenfindungs-Algorithmus beim Maximumkriterium endet, dann hat $B^{*}$ eine Eckmenge, nämlich die Menge der Pivotzeilen.

f) Wenn der Eckenfindungs-Algorithmus beim Quotientenkriterium abbricht, dann hat $B*$ eine Spalte $s_{j}$ mit j ≤ n, deren Komponenten alle das gleiche Vorzeichen haben und deren letzte Komponente von Null verschieden ist.

Eckentausch

Gegenstand

Sei B (m + 1) × (n + 1) - Matrix mit Gewinnzeile g, Kontrollspalte k ≥ 0 und Eckmenge T .

Prämisse, Eigenschaft

Sei C eine Matrix, die aus B durch Anwendung des EckenaustauschAlgorithmus hervorgeht.

Behauptung

Dann gelten die folgenden Aussagen:

a) Beim Eckenaustausch-Algorithmus werden nur zulässige Spaltenumformungen vorgenommen.

b) Die Kontrollspalte von C ist ≥ 0.

c) Der Gewinn von C ist mindestens so groß wie der Gewinn von B .

d) C hat eine Eckmenge.

e) Wenn der Eckenaustausch-Algorithmus mit C bei Anwendung des Maximumkriteriums endet, dann erfüllt C alle Bedingungen von Satz 12.5.

f) Wenn der Eckenaustausch-Algorithmus mit C bei Anwendung des Quotientenkriteriums endet, dann erfüllt C alle Bedingungen von Satz 12.4.