Lineare Optimierung

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Allgemein

Die lineare Optimierung beschäftigt sich mit Problemen, die darin bestehen, dass eine lineare Funktion vorgegeben ist, die maximiert bzw. minimiert werden soll und die einschränkenden Voraussetzungen für eine Lösung in Form von linearen Ungleichungen vorgegeben sind. Mit der linearen Optimierung können in der Spieltheorie unter Anderem Nash-Gleichgewichte in gemischten Strategien in einem endlichen Normalformen-Nullsummenspiel bestimmt werden.

Ein Beispiel zur Verdeutlichung:

Maximiere x1 + x2

Einschränkende Voraussetzungen:

 -x_1+x_2 \le 1

3x_1+8x_2 \le 10

4x_1+12x_2 \le 130

2x_1+12x_2 \le 100

wobei x_1,x_2 \ge 0

Angewandtes Beispiel

Ein angewandtes Beispiel zur linearen Optimierung sei wie folgt gegeben: Auf einem Markt verkauft ein Unternehmen zwei Produkte. Mit dem ersten Produkt erzielt das Unternehmen einen Gewinn von 5 Euro, mit dem Zweiten einen Gewinn von 8 Euro. Die Herstellungszeit für Produkt 1 beträgt 10 Stunden, die für Produkt 2 30 Stunden, und es ist eine obere Schranke von 100 Stunden zur Herstellungszeit vorgegeben. Der Gewinn soll nun maximiert werden. Dies kann durch folgende Gleichungen ausgedrückt werden:

1) 10x_1 + 30x_2 \le 100

2) Maximiere 5x1 + 8x2

Analog kann eine Funktion minimiert werden, z.B. wenn Verluste in einem Unternehmen so gering wie möglich gehalten werden sollen.

Für einen tiefergehenden Einblick in diese angewandten Beispiele mit linearer Optimierung möchte ich auf das Projekt Operation-Research verweisen

Formale Darstellung eines linearen Optimierungsproblems

Formal sieht ein lineares Optimierungsproblem folgendermaßen aus:

maximiere d_1 x_1+d_2 x_2+\ldots+d_n x_n

wobei

\sum_{i=1}^n a_{1i} x_i = b_1

\sum_{i=1}^n a_{2i} x_i = b_2

...

\sum_{i=1}^n a_{ki} x_i = b_k

wobei x_i \ge 0, d_i, b_j,a_{ji} \in \mathbb{R}, i={1,...,n},j={1,...,k}, n \in \mathbb{N}


Simplex-Methode

Im Folgenden wird ein Algorithmus zur Bestimmung einer Lösung für lineare Optimierungsprobleme angegeben. Es handelt sich hierbei um die Simplex-Methode:

Erläuterung anhand eines Beispiels

Hierzu betrachten wir als Einführung ein allgemeines Beispiel, und werden im weiteren Verlauf dann konkrete Bedingungen für die Existenz einer Lösung formulieren.

Es sei folgendes Problem gegeben:

max 2x1 + 3x2 + x3

3x1 + 2x2 + 3x3 < = 10

2x1 + 4x2 + x3 < = 15

Im Folgenden suchen wir ein m mit m=max 2x_1+3x_2+x_3, m \in \mathbb{R}

Wir schreiben die Gleichung um, um das bereits beschriebene formale lineare Optimierungsproblem zu erhalten:

(1) m = 2x1 + 3x2 + x3

(2) x4 = 10 − 3x1 − 2x2 − 3x3

(3) x5 = 15 − 2x1 − 4x2x3

Wie hier zu sehen ist, wurden neue Variablen eingeführt, um die Lösung besser berechnen zu können. Es wurde bereits für das formale lineare Optimiernugsproblem festgelegt: x_i \ge 0, 1 \le i \le 5

Als Erstes erraten wir eine Lösung, die wir dann im weiteren Verlauf optimieren werden. Dabei ist zu beachten, dass keine der Bedingungen aus (2)-(3) verletzt werden. Setzen wir z.B. x1 = 0,x2 = 0,x3 = 0, so erhalten wir mit m=0 eine erste Lösung, denn aus (2) ergibt sich nun x_4 =10 \ge 0 und x_5=15 \ge 0, damit sind die Bedingungen für x_i, 1 \le i \le 5 erfüllt. Da dieser Wert aber sicherlich noch nicht der Höchste sein wird, werden wir in weiteren Schritten versuchen unser m zu erhöhen.

Weiter ist festzustellen, dass in (1) alle x_i,1 \le i \le 3 positive Koeffizienten haben. Dies ist entscheidend für die weitere Vorgehensweise, da ansonsten der Wert von m durch eine Wahl mit negativen Koeffizienten nicht erhöht, sondern verringert wird!

Es kann nun eine Beliebige der drei Variablen ausgewählt werden.

Fällt die Auswahl auf x1, so muss hierbei die Einhaltung der Gleichungen (2) und (3) beachtet werden. Nun muss die obere Schranke für die Variable x1 überprüft werden unter Beachtung der Voraussetzung x_4,x_5 \ge 0. Es ergibt sich aus (2) bzw. (3):

x_4 \ge 0, daraus folgt: x_1 \le \frac{10}{3}

x_5 \ge 0, daraus folgt: x_1 \le 7,5,

wobei wir x2 = 0,x3 = 0 gesetzt haben.

Um keine der Voraussetzungen x_i \ge 0, 1 \le i \le 5 zu verletzen, fällt die Wahl auf (2).

Als nächster Schritt formen wir die Gleichung (2) um und erhalten (5). Das Ergebnis setzen wir in die Gleichung (1) bzw. (3) ein und erhalten (4) bzw. (6). Dies ergibt:

(4) m=2*(-\frac{1}{3} x_4+\frac{10}{3}-\frac{2}{3} x_2-x_3)+3x_2+x_3=\frac{20}{3}+\frac{5}{3} x_2-x_3-\frac{2}{3}x_4

(5) x_1=-\frac{1}{3} x_4+\frac{10}{3}-\frac{2}{3} x_2-x_3

(6) x_5=15-2*(-\frac{1}{3} x_4+\frac{10}{3}-\frac{2}{3} x_2-x_3)-4x_2-x_3=\frac{25}{3}+\frac{2}{3} x_4-\frac{8}{3} x_2+x_3

Wird für 2 \le i \le 4 xi = 0 gesetzt, so ergibt sich für m als Lösung 20/3, da aus (5) bzw. (6) folgt: x_1=\frac{10}{3} \ge 0, x_5=\frac{25}{3} \ge 0

Es ist offensichtlich, dass dies eine bessere Lösung ist.

Als nächster Schritt steht nur noch die Variable x2 zur Auswahl, da diese als Einziges einen positiven Koeffizienten hat. Es wird zunächst überprüft, welche obere Schranke für x2 gewählt werden darf: Für x3 = 0,x4 = 0 gilt in (5) bzw. (6):

x_1 \ge 0, es ergibt sicht: x2 kann bis auf 5 erhöht werden.

x_5 \ge 0, es ergibt sicht: x2 kann bis auf \frac{25}{8} erhöht werden.

Da bekanntlich \frac{25}{8} < 5, muss hier die Gleichung (6) ausgewählt werden.

Umformen dieser Gleichung zu (9) und einsetzen des Ergebnisses in (4) und (5) liefert uns (7) und (8):

(7) m=\frac{20}{3}+\frac{5}{3}*(\frac{25}{8}-\frac{3}{8} x_5+\frac{1}{4} x_4+\frac{3}{8} x_3)-x_3-\frac{2}{3}x_4=\frac{95}{8}-\frac{3}{8} x_3-\frac{1}{4} x_4-\frac{5}{8} x_5

(8) x_1=\frac{10}{3}-\frac{1}{3}x_4-\frac{2}{3}*(\frac{25}{8}-\frac{3}{8} x_5+\frac{1}{4} x_4+\frac{3}{8} x_3)-x_3=\frac{5}{4}-\frac{5}{4} x_3-\frac{1}{2} x_4+\frac{1}{4} x_5

(9) x_2=\frac{25}{8}-\frac{3}{8} x_5+\frac{1}{4} x_4+\frac{3}{8} x_3

In (7) sind nun alle Koeffizienten von x3,x4,x5 negativ, und damit kann das Ergebnis nicht mehr erhöht werden. Wir erhalten als Lösung: m=\frac{95}{8}, x_1=\frac{5}{4},x_2=\frac{25}{8},x_3=0,x_4=0,x_5=0

indem wir in der jeweiligen Gleichung auf der rechten Seite die xi gleich 0 setzen Damit wurde unter Anwendung der Simplex-Methode eine optimale Lösung gefunden.

Vorgehensweise

Allgemeine Betrachtung: Besitze ein Gleichungssystem k Gleichungen und n Unbekannte. Seien b_i,x_j,a_{ij},d_j \in \mathbb{R}, 1 \le i \le k,1 \le j \le n, m \in \mathbb{R} Hierbei sind die aij und die dj die Koeffizienten der Unbekannten xj und wir definieren:


(0) m=\sum_{i=1}^n d_i x_i

(1) \sum_{i=1}^n a_{1i} x_i \le b_1

(2) \sum_{i=1}^n a_{2i} x_i \le b_2

(3) \sum_{i=1}^n a_{3i} x_i \le b_3

... ...

(k) \sum_{i=1}^n a_{ki} x_i \le b_k, wobei x_i \ge 0


1. Phase

1. Schritt:

Füge für (1)-(k) neue Variablen hinzu, um das Gleichungssystem besser lösen zu können. Wir stellen fest:

Gilt \sum_{i=1}^n a_{ji} x_i \le b_j für ein beliebiges j, so folgt:

0 \le b_j-\sum_{i=1}^n a_{ji} x_i

Also existiert ein x_{fix} \in \mathbb{R} mit der Eigenschaft: x_{fix}:=b_j-\sum_{i=1}^n a_{ji} x_i \ge 0

Diese Feststellung wenden wir nun auf die Gleichungen (1)-(k) an und bekommen:

(1) x_{n+1}=b_1-\sum_{i=1}^n a_{1i} x_i

(2) x_{n+2}=b_2-\sum_{i=1}^n a_{2i} x_i

(3) x_{n+3}=b_3-\sum_{i=1}^n a_{3i} x_i

... ...

(k) x_{n+k}=b_k-\sum_{i=1}^n a_{ki} x_i

wobei x_{n+1},x_{n+2},...,x_{n+k} \in \mathbb{R}, x_i \ge 0, i \in {n+1,n+2, \ldots,n+k}


2. Schritt: 

Finde für m in der Gleichung (0) eine Lösung: Setze alle x_i, 1 \le i \le (n+k) gleich 0. Es folgt, dass m = d0 eine Lösung ist, was sehr erfreulich ist.

3. Schritt:

Untersuche in (0) alle x_i, 1 \le i \le (n+k) auf nicht negative Koeffizienten. Wähle aus diesen xi eine spezielle Variable aus, die wir mit xk' bezeichnen.

4. Schritt:

Um eine obere Schranke für xk' zu erlangen werden aus allen Gleichungen (1)-(k), in denen der Koeffizient von xk' die Bedingung aik' > 0 erfüllt, Ungleichungen (1°)-(k°) berechnet, indem in jeder dieser Gleichungen alle x_i,i \in {1,...,n + k}\{k'} 0 gesetzt werden und anschliessend nach xk' umgeformt wird.


In der ersten Phase bedeutet dies für die gegenwärtigen Gleichungen (1)-(k):

(1°) x_{n+1}=b_1-a_{1 k'} x_{k'} \rightarrow_{Bedingung: a_{1k'} > 0} x^{1}_{k'}:=x_{k'} \le \frac{b_1}{a_{1k'}} , da x_{n+1} \ge 0

(2°) x_{n+2}=b_2-a_{2 k'} x_{k'} \rightarrow_{Bedingung: a_{2k'} > 0}  x^{2}_{k'}:=x_{k'} \le \frac{b_2}{a_{2k'}} , da x_{n+2} \ge 0

(3°) x_{n+3}=b_3-a_{3 k'} x_{k'} \rightarrow_{Bedingung: a_{3k'} > 0}  x^{3}_{k'}:=x_{k'} \le \frac{b_3}{a_{3k'}} , da x_{n+3} \ge 0

... ...

(k°) x_{n+k}=b_k-a_{k k'} x_{k'} \rightarrow_{Bedingung: a_{nk'} > 0} x^{k}_{k'}:=x_{k'} \le \frac{b_k}{a_{kk'}} , da x_{n+k} \ge 0



Um uns die Aufgabe zu erleichtern, und keine der Bedingungen x_i \ge 0, 1 \le i \le k zu verletzen, wählen wir x0 aus der Menge {{x}^{i}_{k'}:1\le i \le k}, das die Bedingung x^{0} \le \frac{b_s}{a_{i k'}}, \forall s \in {s' \in {1,\ldots,k}:as'k' > 0} erfüllt.


Wir bezeichnen s als eine Zahl, die uns angibt, aus welcher Gleichung (s) von (1),...,(k) x° durch Nullsetzen der übrigen xi berechnet wurde.

5. Schritt:

In der Gleichung (s) muss nun nach xk' umgeformt werden.

In der ersten Phase bedeutet dies für die gegenwärtige Gleichung (s):

x^{(neu)}_{k'}:=x_{k'}=\frac{b_s-[a_{s1} x_1+a_{s2} x_2+...+...+a_{sn} x_n]+a_{k'} x_{k'}-x_{n+s}}{a_{k'}}.


6. Schritt:

Setze nun das Erbgebnis aus dem 5. Schritt, x^{(neu)}_{k'}, in alle Gleichungen, ausser (s), ein.

In der ersten Phase bedeutet dies für die gegenwärtigen Gleichungen (0)-(k):

(0) m=d_0+d_1 x_1+d_2 x_2+\ldots+d_{k'} x^{(neu)}_{k'}+d_{k'+1} x_{k'+1}+ \ldots+d_n x_n

\rightarrow m=d^{'}_0+d^{'}_1 x_1+...+d^{'}_n x_n   wobei d^{'}_i \in \mathbb{R}, 0 \le i \le n

(1) x_{n+1}=b_1-[a_{11} x_1+a_{12} x_2+\ldots+a_{1 k'} x^{(neu)}_{k'}+a_{1,k'+1} x_{k'+1}+\ldots+a_{1n} x_n]

\rightarrow x_{n+1}=b^{'}_1-\sum_{i=1}^n a^{'}_{1i} x_i

(2) x_{n+2}=b_2-[a_{21} x_1+a_{22} x_2+\ldots+a_{2 k'} x^{(neu)}_{k'}+a_{2,k'+1} x_{k'+1}+\ldots+a_{2n} x_n]

\rightarrow x_{n+1}=b^{'}_2-\sum_{i=1}^n a^{'}_{2i} x_i

(3) x_{n+3}=b_3-[a_{31} x_1+a_{32} x_2+\ldots+a_{3 k'} x^{(neu)}_{k'}+a_{3,k'+1} x_{k'+1}+\ldots+a_{3n} x_n]

\rightarrow x_{n+1}=b^{'}_3-\sum_{i=1}^n a^{'}_{3i} x_i

... ...

(k) x_{n+k}=b_k-[a_{k1} x_1+a_{k2} x_2+\ldots+a_{k k'} x^{(neu)}_{k'}+a_{k,k'+1} x_{k'+1}+\ldots+a_{kn} x_n]

\rightarrow x_{n+k}=b^{'}_k-\sum_{i=1}^n a^{'}_{ki} x_i

wobei a^{'}_{ij} \in \mathbb{R}, 1 \le i \le k, 1 \le j \le n, b^{'}_s \in \mathbb{R}, 1 \le s \le k

7. Schritt:

Beginne mit der nächsten Phase und wiederhole die Schritte 2.-6. aus der ersten Phase, unter Verwendung der neuen Gleichungen (0)-(k) im 5. und 6. Schritt.

Wiederhole in den darauffolgenden Phasen solange, bis in (0) alle Koeffizienten von x_i, 1 \le i \le (n+k) negativ sind.

Dann setzen wir in (0)-(k) auf der rechten Seite der Gleichungen alle x_i, 1 \le i \le (n+k) gleich 0 und haben unsere maximale Lösung gefunden, denn es folgt für (0): m=C, wobei C \in \mathbb{R} ein Ergebnis, das max m=\sum_{i=0}^n d_i x_i erfüllt. Durch Nullsetzen der Variablen xi auf der rechten Seite der Gleichungen (1)-(k) ergeben sich dann auch die Werte der Variablen xi aus (0),i \in {1,...,k}.

Hinweis: 

In der linearen Programmierung erweist es sich als günstig, die aij als Matrixdarstellung zu betrachten:

A:= \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ \ldots & \ldots & \ldots \\ a_{k1} & a_{k2} & ... & a_{kn} \end{pmatrix}

Diese Matrix kann dann in einem Array abgespeichert werden.

Ausserdem kann bi als Vektor b:=(b1,...,bk)T betrachten werden, der ebenfalls als Array abgespeichert wird.

Desweiteren ist es nützlich die sogenannte Tableauschreibweise zu verwenden.

Für einen tiefergehenden Einblick in die lineare Programmierung insbesondere unter Verwendung der Tableauschreibweise möchte ich auf das Projekt lineare Programmierung verweisen.


Bedingungen an eine Lösung

a) Es gilt: b_i \ge 0.

Dies wird an folgendem Beispiel erläutert:

max m = x1 + x2

2x_1+12x_2 \le -1

daraus folgt: 0 \le -1-2x_1-12x_2 Also existiert ein x \in \mathbb{R} mit x = − 1 − 2x1 − 12x2 Nach unserer Methode müssen wir für eine Lösung von m nun x1 = 0,x2 = 0 setzen. Daraus folgt: x=-1. Wir haben aber an unser x die Bedingung x \ge 0. Widerspruch!

b) Der Koeffizient von xk' in (0) ist grösser oder gleich 0.
   Der Koeffizient von x° ist grösser als 0. 

Angenommen der Koeffizient x° wäre negativ: x_{k'} < \frac{b_i}{a_{i k'}} für ein bestimmtes i \in \mathbb{N}. Der Ausdruck \frac{b_i}{a_{i k'}} ist aber negativ, da b_i \ge 0,a_{i k'} < 0. Es ergibt sicht, dass xk' < 0 negativ ist. Wir hatten aber an unser xk' die Bedingung der Positivität. Somit ist der Koeffizient von x° grösser als 0.

c) Es ist immer darauf zu achten, dass bei der Auswahl von xk' auch eine obere Schranke existiert

, da es ansonsten eine unbeschränkte Lösung für xk' gibt, und dadurch die Gleichung (0) möglicherweise kein Maximum bsitzt

Beispiel: (wie immer seien hier x_1 \ge 0,x_2 \ge 0)

(0) maximiere x1 + 0 * x2

wobei

(1) x_2 \ge 2

(2) x1 = 1

Die Lösungen sind hier:x_1=1,x_2 \ge 2. Dennoch hat hier m ein Maximum.

Beispiel:

(0) maximiere x1 + 1 * x2

wobei

(1) x_2 \ge 2

(2) x1 = 1

Die Lösungsmenge ist hier x_1=1,x_2 \ge 2. Aber m ist nicht nach oben beschränkt, da x2 beliebig hohe Werte annehmen kann.


d) Erfüllt ein Gleichungssystem nicht die Anforderungen, so kann ein Ausweg evt. mit der Substitution gefunden werden.

Ist zum Beispiel b_i \ge 0 nicht für alle i \in {1,...,k} erfüllt, so kann zunächst versucht werden, eine Lösung zu erraten, diese wird in den Variablen x^{l}_1,x^{l}_2,\ldots,x^{l}_n gespeichert.

Nun wird neu definiert:

x^{n}_1:=x^{l}_1+x_1,x^{n}_2:=x^{l}_2+x_2,\ldots,x^{n}_n:=x^{l}_n+x_n

Ersetzen wir nun xi durch diese x_i^{n} in unseren Gleichungen (0)-(k), und fügen wir (n) neue Gleichungen hinzu, die durch (k+m) x^{n}_m:=x^{m}+x_m, m \in {1,...,n} bezeichnet werden, so erhalten wir auch neu berechnete Konstanten b_i, i \in {1,...,k} sodass dann die neuen Gleichungen möglicherweise die Anforderungen für die Verwendung der Simplex-Methode erfüllen. Es ist allerdings zu bedenken, dass dies einen erheblichen Mehraufwand an Rechenzeit bedeutet.

Um eine systematische Berechnung einer Lösung, sofern eine existiert, auch dann zu erhalten, wenn nicht alle b_i \ge 0 sind, existiert die Zweiphasenmethode, allerdings wird hier nicht näher darauf eingegangen.

e) Voraussetzungen für eine eindeutige Lösung

Um eine eindeutige Lösung zu bekommen, müssen die Bedingungen in f) erfüllt sein, und es muss in unserer letzten Wiederholungsphase der Schritte 2.-6. das Ergebnis in der Gleichung (0) derart sein, dass alle Koeffizienten von xi negativ sind.

f) Forderung an eine Lösung in endlicher Zeit (insbesondere für die Programmierung wesentlich):

Erstens: bi>0, i \in {1,...,k}

Annahme: bi = 0 und i=k'

\rightarrow x^{0}=0, und der neu berechnete Wert m aus (0) bleibt unverändert.

Darüberhinaus bleiben auch alle neu berechneten Variablen in ihren Werte unverändert. Dieses Problem tritt insbesondere nach einer Degeneration auf.

Bei der Degeneration besteht das Problem, dass für x° mehrere Kandidaten bestehen, d.h. (mindestens) zwei Gleichungen die Bedingung für x° erfüllen, also (mindestens) zwei Variablen b_i=b_j, i \neq j, i,j \in {1,...,k} existieren, und daraus eine weitere Variable x_i,(n+1) \le i \le (n+k), die in unseren ursprünglichen Gleichungen/Ungleichungen nicht enthalten war, sondern nach dem 1. Schritt ergänzt wurde , beim Umformen der Ersten dieser (mindestens) zwei Gleichungen und anschliessendes Einsetzen in die Zweite dieser (mindestens) zwei Gleichungen und Nullsetzen der übrigen Variablen xi in der zweiten Gleichung auf der rechten Seite gleich 0 ist.

Beispiel:


(0*) max x1 + x2

(1*) x_1+x_2-x_3 \le 2

(2*) -x_1+x_2+x_3 \le 2

wobei x_1,x_2,x_3 \ge 0

(0) x1 + x2

(1) x4 = 2 − x1x2 + x3

(2) x5 = 2 + x1x2x3

wobei x_1,x_2,x_3,x_4,x_5 \ge 0

Alle x_i,1 \le i \le 5 0 setzen.

Wähle x2 aus (0) aus.

Setze in (1) und (2) x2 = 0,x3 = 0,x1 = 0:

=> x_2 \le 2 in (1), x_2 \le 2 in (2)

Wähle die Gleichung (1) zum Umformen aus:

(1') x2 = 2 − x4x1 + x3

Einsetzen von (1') in (2):

 x_4=2+x_1-(2-x_4-x_1+x_3)=0+\ldots

=> b2 = 0

Setze nun x1 = 0,x2 = 0,x3 = 0

Es folgt: x4 = 0.

Die Variable x4 war in unseren ursprünglichen Gleichungen/Ungleichungen ( (0*),(1*),(2*) ) nicht enthalten.


Es ist zu beachten, dass wenn mehrere bi = 0 sind, dies in in einer Endlosschleife enden kann, da dann ein Zyklus bei den Berechnungen entstehen kann. Für eine Vertiefung kann evt. auf die Lineare Programmierung verwiesen werden.

Zweitens: a),b) und c) müssen erfüllt sein.

Beispiel für die Anwendung in der Spieltheorie

Wie schon in unserem Abschnitt Allgemein erwähnt, können mithilfe der Simplex Methode auch Nash-Gleichgewichte in gemischten Strategien in einem endlichen Normalformen-Nullsummenspiel berechnet werden.

(Für Beispiele zur Berechnung von Nash-Gleichgewichten in gemischten Strategien ohne Verwendung der Simplex-Methode sei auf Spiele wie Matching Pennies, Kampf der Geschlechter,Stein-Schere-Papier oder Angsthasenspiel zu verweisen)

Hierzu sei folgendes Beispiel gegeben:

Auszahlungsmatrix zweier Spieler in einem endlichen Normalformenspiel:

A B C
A 1,1 2,0 0,2
B 0,2 1,1 2,0
C 2,0 0,2 1,1

A,B,C seien hier die möglichen verschiedenen Strategien für Spieler 1 bzw. Spieler 2.


Wir werden nun separat für den Spieler 1 und den Spieler 2 die optimale Strategie berechnen. Dabei halten wir uns an die in dem Abschnitt Vorgehensweise beschriebenen Schritte 1.-7.


Spieler 1:

1. Phase

Aufstellung der Gleichungen:

(0) max m

(1) m \le u_1(A,A)*x_1+u_1(A,B)*x_2+u_1(A,C)*x_3

(2) m \le u_1(B,A)*x_1+u_1(B,B)*x_2+u_1(B,C)*2x_3

(3) m \le u_1(C,A)*x_1+u_1(C,B)*x_2+u_1(C,C)*x_3

(4) x1 + x2 + x3 = 1

wobei m \in \mathbb{R},x_1,x_2,x_3 \ge 0

und ui(.,.) bezeichne hierbei die jeweilige Nutzenfunktion des Spielers i, i \in {1,2}


daraus ergibt sich:

(0) max m

(1) m \le x_1+2x_2

(2) m \le x_2+2x_3

(3) m \le 2x_1+x_3

(4) x1 + x2 + x3 = 1

wobei m \in \mathbb{R} und x_1,x_2,x_3 \ge 0


Wir wenden den 1. Schritt an:

(0) max m

(1) x4 = 0 − m + x1 + 2x2

(2) x5 = 0 − m + x2 + 2x3

(3) x6 = 0 − m + 2x1 + x3

(4) x7 = 1 − x1x2x3

wobei m \in \mathbb{R} und x_1,x_2,x_3,x_4,x_5,x_6,x_7 \ge 0


2. Schritt:

Finde eine Lösung: Setze alle x_i, 1 \le i \le 7 gleich 0. Es ergibt sich m=0 als eine erste Lösung

3. Schritt:

Wir wählen x1, hierbei wurde der Trick angewendet, dass wir m als m + 0 * x1 schreiben können.

4. Schritt:

In den Gleichungen (1)-(3) hat unser x1 keine Beschränkung nach oben, aber in Gleichung (4): x_1 \le 1, falls x2 = 0,x3 = 0

5. Schritt: Umformen von (4):

(4) x1 = 1 − x7x2x3

6. Schritt:

(0) m

(1) x4 = 0 − m + (1 − x7x2x3) + 2x2 = 1 − mx7 + x2x3

(2) x5 = 0 − m + x2 + 2x3

(3) x6 = 0 − m + 2 * (1 − x7x2x3) + x3 = 2 − m − 2x7 − 2x2x3

2. Phase

2. Schritt: m=0

3. Schritt: Wähle m aus

4. Schritt: Wir stellen fest:

aus (1) folgt m \le 1

aus (2) folgt m=0

aus (3) folgt m \le 2

aus (4) folgt nichts Insgesamt ergibt sich also als Auswahl die Gleichung (2)

5. Schritt: (2) m = 0 − x5 + x2 + 2x3

6. Schritt:

(0) x5 + x2 + 2x3

(1) x4 = 1 − ( − x5 + x2 + 2x3) − x7 + x2x3 = 1 + x5 − 3x3x7

(3) x6 = 2 − ( − x5 + x2 + 2x3) − 2x7 − 2x2x3 = 2 + x5 − 3x2 − 3x3 − 2x7

(4) x1 = 1 − x7x2x3


3. Phase

2.Schritt: m=0

3. Schritt: Wähle x3 aus

4. Schritt: Wir stellen fest:

aus (1) folgt: x_3 \le \frac{1}{3}

aus (2) folgt: x3 besitzt keine obere Schranke

aus (3) folgt: x_3 \le \frac{2}{3}

aus (4) folgt: x_3 \le 1

Insgesamt ergibt sich die Auswahl der Gleichung (1)

5. Schritt:

(1) x_3 = \frac{1}{3}-\frac{1}{3}*x_4+\frac{1}{3}*x_5-\frac{1}{3}*x_7


6. Schritt:

(0) -x_5+x_2+2*(\frac{1}{3}-\frac{1}{3}*x_4+\frac{1}{3}*x_5-\frac{1}{3}*x_7)=\frac{2}{3}-\frac{1}{3}*x_5+x_2-\frac{2}{3}*x_4-\frac{2}{3}*x_7

(2) m=0-x_5+x_2+2*(\frac{1}{3}-\frac{1}{3}*x_4+\frac{1}{3}*x_5-\frac{1}{3}*x_7)=\frac{2}{3}-\frac{1}{3}*x_5+x_2-\frac{2}{3}*x_4-\frac{2}{3}*x_7

(3) x_6=2+x_5-3x_2-3*(\frac{1}{3}-\frac{1}{3}*x_4+\frac{1}{3}*x_5-\frac{1}{3}*x_7)-2x_7=1-3*x_2+x_4+x_7

(4) x_1=1-x_7-x_2-(\frac{1}{3}-\frac{1}{3}*x_4+\frac{1}{3}*x_5-\frac{1}{3}*x_7)=\frac{2}{3}-\frac{2}{3}*x_7-x_2+\frac{1}{3}*x_4-\frac{1}{3}*x_5


4. Phase

2. Schritt: m=\frac{2}{3}

3. Schritt: Wähle x2 aus

4. Schritt:

aus (1) folgt nichts

aus (2) folgt: x_2 \le \frac{2}{3}

aus (3) folgt: x_2 \le \frac{1}{3}

aus (4) folgt: x_2 \le 1

Insgesamt ergibt sich die Auswahl von (3)

5. Schritt: (3) x_2 = \frac{1}{3}-\frac{1}{3}*x_6+\frac{1}{3}*x_4-\frac{1}{3}*x_7

6. Schritt:

(0) \frac{2}{3}-\frac{1}{3}x_5+(-\frac{1}{3}x_6+\frac{1}{3}+\frac{1}{3}x_4-\frac{1}{3}x_7)-\frac{2}{3}x_4-\frac{2}{3}x_7=1-\frac{}{3}x_5-\frac{1}{3}x_6-\frac{1}{3}x_4-x_7

(1) x_3 = \frac{1}{3}-\frac{1}{3}x_4+\frac{1}{3}x_5-\frac{1}{3}x_7

(2) m=\frac{2}{3}-\frac{1}{3}x_5+(-\frac{1}{3}x_6+\frac{1}{3}+\frac{1}{3}x_4-\frac{1}{3}x_7)-\frac{2}{3}x_4-\frac{2}{3}x_7=1-\frac{}{3}x_5-\frac{1}{3}x_6-\frac{1}{3}x_4-x_7

(4) x_1=\frac{2}{3}-\frac{2}{3}x_7-(-\frac{1}{3}x_6+\frac{1}{3}+\frac{1}{3}x_4-\frac{1}{3}x_7)+\frac{1}{3}x_4-\frac{1}{3}x_5=\frac{1}{3}-\frac{1}{3}x_7+\frac{1}{3}x_6-\frac{1}{3}x_5

5. Phase

m=1 als Lösung

Für die Variablen x1,x2,x3 folgt:

aus (1) folgt: x_3=\frac{1}{3}

aus (2) folgt: m = 1

aus (3) folgt: x_2=\frac{1}{3}

aus (4) folgt: x_1=\frac{1}{3}

wobei x4 = 0,x5 = 0,x6 = 0,x7 = 0



Die Rechnung für Spieler 2 ergibt sich aus folgenden Gleichungen analog zur Rechnung von Spieler 1. Aufstellung der Gleichungen:

(0) max m

(1) m \le u_2(A,A)*x_1+u_2(A,B)*x_2+u_2(A,C)*x_3

(2) m \le u_2(B,A)*x_1+u_2(B,B)*x_2+u_2(B,C)*2x_3

(3) m \le u_2(C,A)*x_1+u_2(C,B)*x_2+u_2(C,C)*x_3

(4) x1 + x2 + x3 = 1

wobei x_1,x_2,x_3 \ge 0


daraus ergibt sich:

(0) max m

(1) m \le x_1+2x_2

(2) m \le x_2+2x_3

(3) m \le 2x_1+x_3

(4) x1 + x2 + x3 = 1

wobei x_1,x_2,x_3 \ge 0


Damit ist das Nash-Gleichgewicht in gemischten Strategien ((x1,x2,x3),(x1,x2,x3))=((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})).


Allgemein

Wird in jeder Gleichung auf der linken wie rechten Seite ein konstanter Wert c \in \mathbb{Z} abgezogen, erhält man:

(0) max (m-c)

(1) (m-c) \le x_1+2x_2-c

(2) (m-c) \le x_2+2x_3-c

(3) (m-c) \le 2x_1+x_3-c

(4) x1 + x2 + x3c = 1 − c

wobei m \in \mathbb{R} und x_1,x_2,x_3 \ge 0


D.h. ist m eine Lösung für obige Gleichungen mit c=0, so ist (m-c) auch eine Lösung für obige Gleichungen mit c \neq 0.

Betrachten wir speziell den Fall c=1, so ergibt sich:

(0) max (m-1)

(1) (m-1) \le x_1+2x_2-1

(2) (m-1) \le x_2+2x_3-1

(3) (m-1) \le 2x_1+x_3-1

(4) x1 + x2 + x3 − 1 = 1 − 1

wobei x_1,x_2,x_3 \ge 0

Daraus folgt: (da x1 + x2 + x3 = 1)

(0) max m'

(1) m' \le -x_1+x_2

(2) m' \le -x_1+x_3

(3) m' \le x_1-x_2

(4) x1 + x2 + x3 = 1

Da m=1 in unserem Beispiel war, ist nun m'=(m-1)=0.

Damit wurde aber gerade das Nash-Gleichgewicht in gemischten Strategien für das Nullsummenspiel Stein-Schere-Papier berechnet.

Da beide Gleichungssysteme die gleichen Lösungen besitzen, haben wir somit zugleich das Nash-Gleichgewicht in gemischten Strategien ((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})) für das Stein-Schere-Papier Spiel berechnet.



Allgemein

Um allgemein das Nash-Gleichgewicht in gemischten Strategien aus einer Auszahlungsmatrix in einem endlichen Normalformen-Nullsummenspiel mit der Simplex-Methode zu lösen, kann bei zwei Spielern wie folgt vorgegangen werden (hierbei sei S11,S12,...,S1N bzw. S21,S22,...,S2K die möglichen verschiedenen Strategien des Spieler 1 bzw. Spieler 2 wobei N die Anzahl der Strategien für Spieler 1 und K die Anzahl der Strategien für Spieler 2 bezeichnet):


S21 S22 S23 S24 ... S2N
S11 (a11,b11) (a12,b12) (a13,b13) (a14,b14) ... (a1N,b1N)
S12 (a21,b21) (a22,b22) (a23,b23) (a24,b24) ... (a1N,b2N)
S13 (a31,b31) (a32,b32) (a33,b33) (a34,b34) ... (a3N,b3N)
S14 (a41,b41) (a42,b42) (a43,b43) (a44,b44) ... (a4N,b4N)
... ... ... ... ... ... ...
S1K (aK1,bK1) (aK2,bK2) (aK3,bK3) (aK4,bK4) ... (aKN,bKN)

wobei N,K>0, N,K \in \mathbb{N}

und ui(.,.) bezeichne hierbei die jeweilige Nutzenfunktion des Spielers i, i \in {1,2}


Aufstellen der Gleichungen:

Spieler 1:

(0) max m

(1) m < = x1u1(S11,S21) + x2u1(S11,S22) + x3u1(S11,S23) + ...xNu1(S11,S2N)

(2) m < = x1u1(S12,S21) + x2u1(S12,S22) + x3u1(S12,S23) + ...xNu1(S12,S2N)

(3) m < = x1u1(S13,S21) + x2u1(S13,S22) + x3u1(S13,S23) + ...xNu1(S13,S2N)

(4) m < = x1u1(S14,S21) + x2u1(S14,S22) + x3u1(S14,S23) + ...xNu1(S14,S2N)

...

(k) m < = x1u1(S1K,S21) + x2u1(S1K,S22) + x3u1(S1K,S23) + ...xNu1(S1K,S2N)

(k+1) x_1+x_2+\ldots+x_N=1

wobei m \in \mathbb{R}

Spieler 2:

(0) max m

(1) m < = x1u2(S11,S21) + x2u2(S12,S21) + x3u2(S13,S21) + ...xNu2(S1K,S21)

(2) m < = x1u2(S11,S22) + x2u2(S12,S22) + x3u2(S13,S22) + ...xNu2(S1K,S22)

(3) m < = x1u2(S11,S23) + x2u2(S12,S23) + x3u2(S13,S23) + ...xNu2(S1K,S23)

(4) m < = x1u2(S11,S24) + x2u2(S12,S24) + x3u2(S13,S24) + ...xNu2(S1K,S24)

...

(k) m < = x1u2(S11,S2N) + x2u2(S12,S2N) + x3u2(S13,S2N) + ...xNu2(S1K,S2N)

(k+1) x_1+x_2+\ldots+x_N=1

wobei m \in \mathbb{R}, x_i \ge 0, 1 \le i \le N


Anschliessend wird für die jeweiligen Spieler eigens mit der 1. Phase aus dem Abschnitt Vorgehensweise begonnen, um eine Lösung für unser m und unsere Variablen x_1,x_2,\ldots,x_N zu erlangen





Zusammenfassung

Dies war eine Einführung in die lineare Optimierung, in der die Simplex-Methode zur Bestimmung von Lösungen für lineare Optimierungsprobleme ausführlich dargelegt wurde. Es wurde anhand von Beispielen aufgezeigt, wie eine Lösung zu finden ist, und Bedingungen formuliert, die eine Lösung garantieren. Zuletzt wurde ein Beispiel aus der Spieltheorie gegeben, bei dem ein Nash-Gleichgewicht in gemischten Strategien in einem endlichen Normalformen-Nullsummenspiel mithilfe der Simplex-Methode bestimmt wurde, um einen konkreten Anwendungsbezug zu diesem Gebiet herstellen zu können.

Anwendung siehe Das "traveling salesman problem"


Literatur:

Schwarz: Numerische Mathematik, 1997 4. Auflage
Meine Werkzeuge