Lineare Programmierung - Methoden und Anwendungen

From Teachwiki
Jump to: navigation, search

Einführung[edit]

Lineare Optimierung ist ein Teilgebiet der mathematischen Optimierung. Zur mathematischen Optimierung gehören desweiteren die nichtlineare, diskrete, kombinatorische und dynamische Optimierung. Die mathematische Optimierung zusammen mit der Simulationstechnik, der Datenanalyse und Prognosetechnik, der Warteschlangen und Bedienungstheorie sowie der Entscheidungs und Spieltheorie gehören zum Fachgebiet des Operations Research. Operations Research ist eine Wissenschaft, die sich mit der Entwicklung von Modellen, mathematischen Planungsmethoden und der Algorithmierung zur Analyse von Problemstrukturen befasst. Anwendungsgebiete finden sich neben den Wirtschaftswissenschaften vorallem in Physik, Mathematik und den Ingenieurswissenschaften.

Geschichtliche Entwicklung[edit]

Operations Research wurde während des zweiten Weltkriegs vorallem in Grossbritannien und den USA entwickelt. In Grossbritannien wurden um 1940 Wissenschaftler aus verschiedenen Fachbereichen (Mathematik und Physik) in den sogenannten Operations Research Groups zusammengefasst. Sie befassten sich mit Militärstrategischen Maßnahmen wie optimale Strategien beim Einsatz von Radar, mathematische Analyse bei der Ubootabwehr oder Problemen bei der optimalen Zusammenstellung von Geleitzügen und Bombergeschwadern. Die Operations Research Groups hatten soviele Erfolge zu verbuchen, dass sich nach Ende des Krieges vorallem Grossfirmen für die Methoden und Techniken interessierten.

Anwendung in den Wirtschaftswissenschaften[edit]

Techniken des Operations Research und der linearen Programmierung kommen vorallem in der Produktionswirtschaft zum Einsatz. Die Bereiche erstrecken sich von Beschaffung, optimaler Lagerhaltung, Logistik, Instandhaltung über Produktionssteuerung bis hin zur Personalplanung. Es geht vorallem um die Lösung von optimalen Standort und Transportproblemen, Programmen zur Tourenplanung und Netzwerkflüssen, Mischungs- Verschnitt- und Maschinenbelegungsproblemen sowie optimalen Produktionsreihenfolgen. Seit einigen Jahren werden die Techniken auch in Industrie, Banken, Versicherungen, Handel, Gesundheitswesen und in der öffentlichen Verwaltung eingesetzt. Die Entwicklung neuer Methoden zur Lösung von Problemen wurde durch den Computer stark begünstigt. Heute kann man damit hochkomplexe Probleme lösen mit viel weniger Zeit und vorallem Kosten. Man kann die OR Methoden auch ohne Computerkenntnisse verstehen, jedoch ist eine Lösung von höherdimensionalen praktischen und theoretischen Problemstellungen kaum ohne Softwareeinsatz möglich. Man kann sehr viele Probleme als lineare Programme formulieren. Dazu später mehr. Ein lineares Programm kann leicht bis zu einhundertausend Variablen und ebensoviele Nebenbedingungen haben. Beliebte Softwareprogramme zur Lösung von LP's sind zum Beispiel AMPL, SAS, Lindo, Lingo, R.

Lineare Programme in Standardform[edit]

Die allgemeine Form ist gegeben durch...


maximiere \sum_{j=1}^{n}c_{j}x_{j}\,

unter den Nebenbedingungen:

\sum_{j=1}^{n}a_{ij}x_{j}<b_{i} (i= 1,2,....m\,)

x_{j}>0\, (j=1,2,...n\,)

Lineare Probleme dieser Art werden als LP Programme in Standard Form bezeichnet. Was beschreibt ein LP in Standardform. Zum einen sind alle Nebenbedingungen linear und die letzten n\, der n + m\, Nebenbedingungen sind die sogenannten nichtnegativitäts Nebenbedingungen. Wenn Probleme in Standardform dargestellt werden erleichtert es die weiteren Rechnungen mit Standardverfahren. Es besteht jedoch die Möglichkeit durch geeignete Transformationen ein LP das nicht in Standardform ist in Standardform zu überführen. Folgende Optimierungsprobleme werden als sogenannte lineare Programme oder kurz LP's bezeichnet.

Beispiel 1)

maximiere: 5x_{1}+4x_{2}+3x_{3}\,


unter den Nebenbedingungen:

2x_{1}+3x_{2}+x_{3}\leq  5

4x_{1}+x_{2}+2x_{3}\leq 11

3x_{1}+4x_{2}+2x_{3}\leq  8

x_{1},x_{2},x_{3}\geq 0

Im Allgemeinen gilt, wenn die Koeffizienten c_{1},c_{2},......,c_{n}\, vom Typ der reellwertigen Zahlen sind, dann ist die Funktion f der Variablen x_{1},x_{2},.....,x_{n}\, gegeben durch f(x_{1},x_{2},....,x_{n}
)=c_{1}x_{1}+c_{2}x_{2}+....+c_{n}x_{n}=\sum_{j=1}^{n}c_{j}x_{j} eine lineare Funktion. Wenn f eine lineare Funktion ist und b eine reele Zahl, dann wird die Gleichung f(x_{1},x_{2},....,x_{n})=b\, eine lineare Gleichung genannt und die Ungleichungen f(x_{1},x_{2}
,....,x_{n})\leq b oder f(x_{1},x_{2},....,x_{n}) \geq  b\, lineare Ungleichungen. Ein lineares Programmierungsproblem ist das Problem der Maximierung oder Minimierung einer linearen Funktion unter der Einbeziehung von linearen Nebenbedingungen.

Simplex Algorithmus[edit]

Das Simplex Verfahren ist die wichtigste Methode bei der Lösung von linearen Programmen. Ein lineares Programm kann mit Hilfe des Simplex entweder nach endlich vielen Schritte gelöst werden, oder führt zu keinem Ergebnis weil das LP unbeschränkt, schlecht formuliert oder einfach unlösbar ist. Die Arbeitsweise des Simplex ist dabei denkbar genial. Der Lösungsraum eines hochdimensionalen LP's, beschränkt durch zahlreiche Nebenbedingungen kann durch ein konvexes Polyeder (Vielflächner) dargestellt werden. Jeder Eckpunkt kann hierbei eine optimale Lösung darstellen. Die Idee des Simplex ist es, an einer Ecke zu starten und den Zielfunktionswert mit den Zielfunktionswerten alle

benachbarten Ecken zu vergleichen. Wird eine Ecke gefunden die einen höheren Zielfunktionswert aufweist, so wird die Prozedur wiederholt.
Abbildung 1: Lösungsraum des Simplex als Polyeder
Der Simplexalgorithmus läuft dabei an den Kanten des Polyeders entlang bis er eine optimale Lösung gefunden hat. Der Vorteil liegt auf der Hand. Der Simplex braucht im optimalen Fall nur wenige Ecken zu evaluieren, bis er eine Lösung findet. Wenn aber zwischen der Start - und der Zielecke sehr viele kurze Kanten liegen, kommt er nur langsam voran. Im schlechtesten Fall benötigt er exponentielle Zeit. Ist aber für die meisten praktischen Probleme schneller als jeder bisher bekannter Algorithmus. Ein entscheidender Vorteil des Simplex ist, wenn bereits eine optimale Lösung gefunden wurde kann man zusätzliche Nebenbedingungen hinzufügen oder die b_{i} Werte der Nebenbedingungen verändern. Der Simplex startet dann "warm" von der alten optimalen Lösung und durchläuft nicht noch einmal das gesamte Optimierungsproblem. Der Simplex Algorithmus ist in vielen mathematischen Solvern wie zum Beispiel CPLEX implementiert. Die folgenden Simplexverfahren sollen verdeutlichen, wie der Simplex Algorithmus funktioniert und wie er an ausgewählten Beispielen zu numerischen Lösungen führt. Zum Anfang soll gezeigt werden wie man auch mit graphischen Methoden kleinere Probleme lösen kann . Das lineare Programm muss in Standardform aufgeschrieben werden. Voraussetzungen für die spätere Lösbarkeit sind eine lineare Zielfunktion sowie lineare Nebenbedingungen, desweiteren sind alle Variablen als nichtnegativ anzunehmen.

Graphische Methode und Eckpunktmethode[edit]

Lineare Programme mit nur 2 Variablen lassen sich sehr gut mit einem kartesischem Koordinatensystem lösen. Dazu werden zuerst alle Nebenbedingungen des folgenden Beispiels. max {20x_{1}+30x_{3}\mid x_{1}\leq 60,x_{2}\leq 50,x_{1}+2x_{2}\leq 120} in das Koordinatensystem eingezeichnet. Jede bindende Nebenbedingung verkleinert den Lösungsraum. Für den bivariaten Fall das grüne Vieleck. Die optimale Lösung kann nur auf einer der Ecken liegen da dort die Ressourcen optimal genutzt werden. Als nächstes wird die

Abbildung 2: Grafische Lösung des Simplex


Abbildung 2: Grafische Lösung des Simplex

Zielfunktion z=20x_{1}+30x_{2} in das Koordinatensystem eingezeichnet und durch Parallelverschiebung so lange verschoben, bis sie auf die Ecke trifft die am weitesten aussen liegt. Die Kombination (x_{1},x_{2})=(60,30) die man nach der Parallelverschiebung ablesen kann, ist in diesem Fall die optimale Lösung. Eine andere Methode auch Eckpunktmethode genannt, besteht darin alle Ecken im Löungsraum nach dem höchsten Zielfunktionswert zu evaluieren. Ein Vergleich der vier zulässigen Kombinationen ergibt für (x_{1},x_{2})=(60,0)}einen Zielfunktionswert z=1200, für (x_{1},x_{2})=(20,50) z=1900, für (x_{1},x_{2})=(0,50) gilt z=1500 und für (x_{1},x_{2})=(60,30) findet sich schließlich ebenfalls die optimale Lösung mit z=2100.

Revidierter Simplex[edit]

Der revidierte Simplex ist geeignet als Implementierung eines mathematischen Algorithmus für eine effiziente und numerisch stabile Lösung. Jede moderne Software die LP Probleme lösen kann, arbeitet auf irgendeine Weise mit dem revidierten Simplex. Betrachten wir wieder das Beispiel max {20x_{1}+30x_{3}\mid x_{1}\leq 60,x_{2}\leq 50,x_{1}+2x_{2}\leq 120}. Die Variablen s_{i}\, werden als sogenannte Schlupfvariablen bezeichnet. Sie werden eingeführt, um die Ungleichungen in Gleichungen umzuwandeln, da diese mathematisch einfacher zu betrachten sind. Die Idee des revidierten Simplex ist das gesamte lineare Gleichungssystem aus Nebenbedingungen und Zielfunktion in Matrixschreibweise zu verfassen. Die beiden Simplexgleichungen bilden die Grundlage des reviderten Simplex Basisvariablen bekommen im folgenden den Index B und Nichtbasisvariablen den Index N.

Simplexgleichungen

(1) w_{B}= G_{B}^{-1}b-G_{B}^{-1}G_{N}w_{N}\,

(2) z=\gamma _{B}^{\prime }G_{B}^{-1}b+(\gamma _{N}^{\prime}-\gamma _{B}^{\prime}G_{B}^{-1}G_{N})w_{N}\,


Es gilt ist (\gamma _{N}^{\prime}-\gamma _{B}^{\prime}G_{B}^{-1}G_{N})w_{N}\leq 0 so ist w=(w_{B},w_{N})\,=(G_{B}^{-1}b,0) ein optimales Programm und z=\gamma _{B}^{\prime }G_{B}^{-1}b\, der optimale Wert.


Das Optimierungsproblem in Matrixschreibweise ist wie folgt gegeben.


maximiere \begin{bmatrix}
20 & 30
\end{bmatrix}
\begin{bmatrix}
x_{1} \\ 
x_{2}
\end{bmatrix}

unter den Nebenbedingungen


\begin{bmatrix}
1 & 0 & 1 & 0 & 0 \\ 
0 & 1 & 0 & 1 & 0 \\ 
1 & 2 & 0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
x_{1} \\ 
x_{2} \\ 
s_{1} \\ 
s_{2} \\ 
s_{3}
\end{bmatrix}
=
\begin{bmatrix}
60 \\ 
50 \\ 
120
\end{bmatrix}


Vor der ersten Iteration lässt sich das LP folgendermaßen darstellen..


B_{0}=\ \{s_{1},s_{2},s_{3}) \ \ N_{0}=\{x_{1},x_{2}\}


G_{B}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
0 & 0 & 1
\end{bmatrix}
 \ \ G_{N}=
\begin{bmatrix}
1 & 0 \\ 
0 & 1 \\ 
1 & 2
\end{bmatrix}
\qquad


\gamma =[\gamma _{B},\gamma _{N}]=(0,0,0, 20,30)\, y^{\prime }=\gamma_{B}^{\prime}G_{B}^{-1}=(0,0,0)\,



G_{B}^{-1}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
0 & 0 & 1
\end{bmatrix}
\qquad und \ z_{0}=0\qquad w=(w_{B},w_{N})=(60,50,120,0,0)


Vorbereitung zur ersten Iteration


Wahl einer \textit{Eintrittsvariablen} ..... es muss gelten y^{\prime
}g_{N_{i}}\leq \gamma _{N_{i}}\,

y^{\prime }=\gamma _{B_{0}}^{\prime }G_{B_{0}}^{-1}=(0,0,0)\qquad g_{N_{1}}=
\begin{bmatrix}
1 \\ 
0 \\ 
1
\end{bmatrix}
\ \ \ \ g_{N_{2}}=
\begin{bmatrix}
0 \\ 
1 \\ 
2
\end{bmatrix}


y^{\prime }g_{N_{1}}=0\leq \gamma _{N_{1}}=20\ \ \ \ \ y^{\prime
}g_{N_{2}}=0\leq \gamma _{N_{2}}=30\Longrightarrow Bedingung für beide erfüllt z.B mit x_{1}\, als Eintrittsvariable.


Wahl einer Austrittsvariable ......es muss gelten w_{B}-td\geq 0 wobei


w_{B}=G_{B}^{-1}b=(60,50,120) \ und \ \ d=G_{B}^{-1}g_{N_{1}}=(1,0,1)

w_{B}-td=
\begin{bmatrix}
60 \\ 
50 \\ 
120
\end{bmatrix} 
-t
\begin{bmatrix}
1 \\ 
0 \\ 
1
\end{bmatrix} \geq 0 man erhält 60\geq t, 50\geq 0,120\geq t


t\leq 60 ist bindend und s_{1}\, wird Austrittsvariable.


Iteration 1


B_{1}=\ \ \{x_{1},s_{2},s_{3}) N_{1}=s_{1},x_{2}\,


G_{B}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
1 & 0 & 1
\end{bmatrix} \ \ G_{N}=
\begin{bmatrix}
1 & 0 \\ 
0 & 1 \\ 
0 & 2
\end{bmatrix}

\gamma _{B}^{\prime }=(20,0,0)\qquad \qquad \qquad \gamma_{N}^{\prime }=(0,30)

G_{B}^{-1}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
-1 & 0 & 1
\end{bmatrix} und G_{B}^{-1}\ G_{N}= \begin{bmatrix}
1 & 0 \\ 
0 & 1 \\ 
-1 & 2
\end{bmatrix}


w_{B}=G_{B}^{-1}b=\{x_{1},s_{2},s_{3\}})=(60,50,60)


Wir prüfen das Abbruchkriterium...


[\gamma _{N}^{\prime }-\gamma _{B}^{\prime }G_{B}^{-1}G_{N}]=(-20,30)\nleq 0 welches noch nicht erfüllt ist.

Wir müssen eine zweite Iteration starten. Der Zielfunktionswert beträgt z=\gamma _{B}^{\prime}G_{B}^{-1}b=1200


Vorbereitung zur Iteration 2


Wahl einer Eintrittsvariablen ..... es muss gelten y^{\prime}g_{N_{i}}\leq \gamma _{N_{i}}

y^{\prime }=\gamma _{B_{1}}^{\prime }G_{B_{1}}^{-1}=(20,0,0) g_{N_{1}}=
\begin{bmatrix}
1 \\ 
0 \\ 
0
\end{bmatrix} \ \ \ \ g_{N_{2}}=
\begin{bmatrix}
0 \\ 
1 \\ 
2\end{bmatrix}


y^{\prime }g_{N_{1}}=20\leq \gamma _{N_{1}}=0 falsche Aussage!


y^{\prime }g_{N_{2}}=0\leq \gamma _{N_{2}}=30\qquad \Longrightarrow Eintrittsvariable wird x_{2}


Wahl einer Austrittsvariable......es muss gelten w_{B}-td\geq 0 wobei


w_{B}=G_{B}^{-1}b=(60,50,60)^{\prime } \ \ \ \ \ \ d=G_{B}^{-1}g_{N_{2}}=(0,1,2)^{\prime }


w_{B}-td=
\begin{bmatrix}
60 \\ 
50 \\ 
60
\end{bmatrix}
-t
\begin{bmatrix}
0 \\ 
1 \\ 
2
\end{bmatrix} \geq 0 man erhält 60\geq 0, 50\geq t, 30\geq t


t\leq 30 ist bindend und s_{3}\, wird Austrittsvariable.


Iteration 2


B_{2}=(x_{1},s_{2},x_{2})\ \ N_{2}=(s_{1},s_{3})



G_{B}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 1 \\ 
1 & 0 & 2
\end{bmatrix}
\ \ G_{N}=
\begin{bmatrix}
1 & 0 \\ 
0 & 0 \\ 
0 & 1
\end{bmatrix}


\gamma _{B_{1}}^{\prime }=(20,0,30)\qquad \qquad \qquad \gamma_{N_{1}}^{\prime }=(0,0)

G_{B}^{-1}=
\begin{bmatrix}
1 & 0 & 0 \\ 
0.5 & 1 & -0.5 \\ 
-0.5 & 0 & 0.5
\end{bmatrix}
\qquad und \ G_{B}^{-1}\ G_{N}=
\begin{bmatrix}
1 & 0 \\ 
0.5 & -0.5 \\ 
-0.5 & 0.5
\end{bmatrix}


w_{B}=G_{B}^{-1}b=\{x_{1},s_{2},x_{2})=(60,20,30)^{\prime }


Wir prüfen das Abbruchkriterium [\gamma _{N}^{\prime }-\gamma_{B}^{\prime}G_{B}^{-1}G_{N}]=(-5,-15)\nleq 0 welches jetzt erfüllt ist. Der Simplex terminiert an dieser Stelle und wir erhalten nach nur 2 Iterationsschritten die optimale Lösung. Die erhaltenen Werte [\gamma
_{N}^{\prime }-\gamma _{B}^{\prime }G_{B}^{-1}G_{N}] verstehen sich als die negativen dualen Preise der Nebenbedingungen 1 und 3. Der Zielfunktionswert des Maximierungsproblems beträgt z=\gamma_{B}^{\prime }G_{B}^{-1}b=2100.

Kritik

Die Wahl einer Eintrittsvariablen muss nicht immer eindeutig sein. Jede positive Koordinate von [\gamma _{N}^{\prime }-\gamma _{B}^{\prime
}G_{B}^{-1}G_{N}] bestimmt eine mögliche neue Basisvariable. Um zyklisches "Totlaufen" des Simplex zu verhindern, kann man mit der Variablen beginnen, die den kleinsten Index hat (Bland'sche Regel) oder die zum Beispiel die grösste Erhöhung des Zielfunktionswertes verspricht. Die Wahl der Austrittsvariablen muss ebenfalls nicht immer Eindeutig sein. So gibt es bei unbeschränkten Problemen überhaupt keine Austrittsvariable.

Wie schnell arbeitet die Simplex Methode[edit]

In diesem Abschnitt soll kurz auf die Geschwindigkeit und insbesondere auf die Anzahl der benötigten Iterationen der Simplex Methode eingegangen werden. Laut Dantzig (1963) gilt für m<50 und m+n<200 , dass sich die Anzahl der Iterationen gewöhnlich unter  3m/2 bewegen. Laut Dantzig erhöhen sich die Anzahl der Iterationen proportional zur Anzahl der Nebenbedingungen m und nur sehr langsam mit der Anzahl der Variablen n. Für eine fixe Anzahl von Nebenbedingungen erhöhen sich die Anzahl der Iterationen mit der Anzahl der Variablen aber nur logarithmisch mit n. Theoretische Erklärungen dazu geben unter anderem Dantzig (1980) und Smale (1982).Kuhn und Quandt (1963) geben durch Monte Carlo Simulationen nach der sogenannten grössten Koeffizienten Regel einige numerische Werte zur Geschwindigkeit. Die folgenden Angaben sind aus Chvatal (1983) entnommen.

m  /  n 10 20 30 40 50
10 9.4 14.2 17.4 19.4 20.2
20 25.2 30.7 38.0 41.5
30 44.4 52.7 62.9
40 67.6 78.7
50 95.2
Tabelle 1: Anzahl der Iterationen

Grenzen des Simplex Algorithmus[edit]

Die Extrempunkten eines LP sind häufig nicht ganzzahlig. Ein Auf - oder Abrunden einer optimalen Lösung ergibt nicht notwendigerweise eine optimale ganzzahlige Lösung. Als Beispiel soll folgendes Problem betrachtet werden. max {28x_{1}+81x_{3}\mid 18x_{1}+40x_{2}\leq 237,8x_{1}-8x_{2}\leq 23,x_{1}\geq 0,x_{2}\geq0} Der Simplex liefert als optimale Lösung den Punkt (x_{1},x_{2})=(6.069, 3.194) mit dem optimalen Wert z=489.336. Sind wir jedoch an einer ganzzahligen Lösung des Problems interessiert, erhalten wir suboptimale Lösungen. Der nächste zulässige ganzzahlige Punkt wäre (x_{1},x_{2})=(5,3) mit einem Zielfunktionswert von z=434. Die optimale ganzzahlige Lösung hingegen ist jedoch (x_{1},x_{2})=(2,5). Dies zeigt, dass die Anwendung der Simplexmethode mit anschliessender Rundung zur Bestimmung von ganzzahligen Lösungen nicht zu optimalen Ergebnissen führt. Ganzzahlige Lösungen sind aber in vielen Problemstellungen unerlässlich. Man denke an die optimale Bestimmung von Netzwerkflüssen oder kürzeste Wege Problemen, optimale Zusammenstellung von Frachten oder auch Lösung von Kontigentierungsproblemen in der Luftfahrtbranche. Für diese Probleme gibt es bessere ebenfalls iterative Verfahren, wie den Netzwerksimplex oder auch die Branch and Bound Methode, die in Solvern wie CPLEX implementiert sind. Auf diese Verfahren kann im Rahmen dieser Arbeit aber nicht weiter eingegangen werden.

Lösungsmöglichkeiten von LP's mit Hilfe der library lpSolve und linprog in R 2.2.1[edit]

Es gibt eine Vielzahl von Software zum lösen von LP’s. Im folgenden werden 2 Beispiele dargestellt die man mit Hilfe von Bibliotheken der Software R lösen kann. Im ersten Beispiel soll das einfache LP aus Beispiel 1 betrachtet werden.

maximiere: 5x_{1}+4x_{2}+3x_{3}\,


unter den Nebenbedingungen:

2x_{1}+3x_{2}+x_{3}\leq  5

4x_{1}+x_{2}+2x_{3}\leq 11

3x_{1}+4x_{2}+2x_{3}\leq  8

x_{1},x_{2},x_{3}\geq 0


Der einfachste Weg das Programm zu lösen, ist die library linprog in R. Der R Code ist im folgenden gegeben. Der Vektor cvec stellt den Vektor der Zielfunktionskoeffizienten dar, bvec den Vektor der Seitenbeschränkungen und Amat die Matrix A_{ij}.

library(linprog)
cvec<-c(5,4,3)
bvec<-c(5,11,8)
Amat<-rbind(c(2,3,1),c(4,1,2),c(3,4,2))
solveLP(cvec,bvec,Amat,maximum=TRUE,maxiter=1000)

Nach 2 Iterationen erhalten wir den optimalen Zielfunktionswert mit 13 und die optimalen Werte sind (x_1, x_2, x_3) = (2, 0, 1).

Results of Linear Programming / Linear Optimization

Objective function (Maximum):
[1] 13

Iterations in phase 1: 0
Iterations in phase 2: 2

Basic Variables
    opt
1     2
3     1
S 2   1

Constraints
  max actual diff dual price dual.reg
1   5      5    0          1      1.0
2  11     10    1          0      1.0
3   8      8    0          1      0.5

All Variables (including slack variables)
    opt c min c   max c marg. marg.reg.
1     2 5   4.5 6.00000    NA        NA
2     0 4  -Inf 7.00000    -3       1.0
3     1 3   2.5 3.33333    NA        NA
S 1   0 0    NA      NA    -1       1.0
S 2   1 0  -Inf 0.50000     0       1.0
S 3   0 0    NA      NA    -1       0.5


Im folgenden Beispiel soll ein kleines Transportproblem gelöst werden. Es ist die Aufgabe 30 Einheiten von den drei Produktionsstätten O_{1}, O_{2}, O_{3} kostenminimal zu den vier Abnehmern D_{1}, D_{2}, D_{3}, D_{4} zu versenden. Wie suchen nun den kostengünstigsten Versandweg, um den Bedarf zu decken und keine Überbestände in den Produktionsstätten zu haben. Da Angebot gleich der Nachfrage ist und die angebotenden und nachgefragten Mengen ganzzahlig sind, haben wir automatisch die Eigenschaft einer optimalen ganzzahligen Lösung. Die Tabelle gibt die Transportkosten von der Produktionsstättezu den Abnehmern an.


D_{1} D_{2} D_{3} D_{4} Angebot
O_{1} 21 36 43 20 18
O_{2} 60 30 50 43 5
O_{3} 18 10 48 72 7
Nachfrage 4 18 6 2 30
Tabelle 2: Transportkostenmatrix


Im folgenden der R Code zur Lösung des Transportproblems. Es bietet sich an, die library lpSolve zu verwenden da hiermit auch sehr grosse Probleme gelöst werden können.

library(lpSolve)
costs<-matrix(0,3,4)
costs[1,1]<-21; costs[1,2]<-36; costs[1,3]<-43; costs[1,4]<-20; costs[2,1]<-60;
costs[2,2]<-30; costs[2,3]<-50; costs[2,4]<-43; costs[3,1]<-18; costs[3,2]<-10;
costs[3,3]<-48; costs[3,4]<-72;
row.signs<-rep("<",3)
col.signs<-rep(">",4)
row.rhs<-c(18,5,7)
col.rhs<-c(4,18,6,2)
lp.transport(costs,"min",row.signs,row.rhs,col.signs,col.rhs)$solution
Success: the objective function is 818 

     [,1] [,2] [,3] [,4]
[1,]    4    6    6    2
[2,]    0    5    0    0
[3,]    0    7    0    0
Abbildung 3: Optimales Versandproblem



Nach Lösung des Optimierungsproblems bekommen wir folgenden optimalen Versandplan.

Literatur[edit]

- Vasek Chvatal: Linear Programming. W. H. Freeman and Company, New York, 1983

- Dantzig G. B., Thapa M. N.: Linear Programming, Springer, Berlin, Heidelberg, u.a., 1997

- Dürr W., Kleibohm K.: Operations Research, Lineare Modelle und ihre Anwendungen, 3. Aufl., Hanser, München Wien, 1992

- Kurt Helmes - Skript zur Vorlesung OR I und II Wintersemester 04/05 und Sommersemester 05