Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Beispiel zum Simplex-Verfahren

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Für das durch

\begin{displaymath} \begin{array}{r\vert rrrr} & \multicolumn{4}{c}{Q} \\ \h... ...2 \\ 3 & 1 & 5 & 5 & 4 \\ 5 & 5 & 3 & 2 & 1 \end{array} \end{displaymath}

beschriebene Transportproblem läuft der Simplex-Algorithmus folgendermaßen ab. Startlösung

\begin{displaymath} \begin{array}{r\vert rrrr} & 5 & 1 & 2 & 4 \\ \hline 4... ... 0 \\ 3 & 1 & 1 & 1 & 0 \\ 5 & 0 & 0 & 1 & 4 \end{array} \end{displaymath}

Nord-West-Regel

\begin{displaymath} \begin{array}{l} x_{1,1} = \min\{p_1,q_1\} = \min\{4,5\} =... ... x_{2,2}=1,\ x_{2,3}=1,\ x_{3,3}=1,\ x_{3,4}=4 \end{array} \end{displaymath}

reduzierter Kostenvektor $ D_K^t = C_K^t - (C_I^t A_I^{-1}) A_K$

$\displaystyle W^t A_I = C_I^t,\quad C^t=[\begin{array}{ccc ccc} c_{1,1}& \ldots& c_{m,1}& c_{1,2}& \ldots& c_{m,n}\end{array}] $

Spaltenindizes von $ A$

$\displaystyle (1,1),(2,1),\ldots,(m,1),(1,2),(2,2),\ldots, (m,2),\ldots, $

$ 1$ in Spalte $ (j,k)$ in Zeilen $ j$ und $ m+k$ $ W^t=[\begin{array}{ccc ccc} u_1& \ldots& u_m& v_1& \ldots& v_n \end{array}]$

$\displaystyle u_j + v_k = c_{j,k}, \quad (j,k)\in I $

im Beispiel

$\displaystyle I = \{(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)\} $

LGS in Tableau-Form

\begin{displaymath} \begin{array}{r\vert rrrr} & \multicolumn{4}{c}{V} \\ \h... ...& & & \\ -2 & 1 & 5 & 5 & \\ -5 & & & 2 & 1 \end{array} \end{displaymath}

sukzessive Lösung

\begin{displaymath} \begin{array}{l} u_1=0,\, v_1=3,\, u_2=-2,\, v_2=7 \\ \qquad v_3=7,\, u_3=-5,\, v_4=6 \end{array} \end{displaymath}

Vergleich mit Kosten für $ (j,k)\notin I$

$\displaystyle c_{j,k} - d_{j,k} = W^t A(:,(k-1)m+j) = u_j + v_k $

in Tableau-Form

\begin{displaymath} \begin{array}{r\vert rrrr} & 3 & 7 & 7 & 6 \\ \hline ... ... & 7 & 6 \\ -2 & & & & 4 \\ -5 &-2 & 2 & & \end{array} \end{displaymath}

Tauschindex

$\displaystyle 6 > c_{1,4} = 2\to (1,4) $

Modifikation der Basislösung

\begin{displaymath} \begin{array}{r\vert rrrr} & 5 & 1 & 2 & 4 \\ \hline ... ... 3 & & & 1 \\ 3 & 2 & 1 & & \\ 5 & & & 2 & 3 \end{array} \end{displaymath}

$ \implies$ $ I \to \{I \backslash (2,3)\} \cup (1,4)$
neue Indexmenge:

$\displaystyle \{(1,1),(1,4),(2,1),(2,2),(3,3),(3,4)\} $

Pivot-Operation mit zwei Tableaus

\begin{displaymath} T_1 = \begin{array}{r\vert c} & V \\ \hline U & C-D \... ...= \begin{array}{r\vert c} & Q \\ \hline P & X \end{array} \end{displaymath}

zweiter Pivot-Schritt

\begin{displaymath} \begin{array}{rcl} \begin{array}{r\vert rrrr} & 3 & 7 & 3... ...\ 3 & 3 & & & \\ 5 & & & 2 & 3 \end{array} \end{array} \end{displaymath}

dritter Schritt

\begin{displaymath} \begin{array}{r\vert rrrr} & 3 & 4 & 3 & 2 \\ \hline ... ...& 3 & \\ -2 & & 2 & 1 & 0 \\ -1 & 2 & 3 & & \end{array} \end{displaymath}

optimal, da $ C-D\le C$ zeigt, ist diese Lösung optimal.
[Verweise]
  automatisch erstellt am 19.  8. 2013