Simplex: reduzierte Kosten

23.09.2009, 12:56

shihan

Simplex: reduzierte Kosten

Hi,

folgende Frage stellt sich mir, und ich habe leider weder über Google, noch über die Forumssuche, eine für mich verständliche Antwort finden können.

Folgendes Tableau wird in Wikipedia gezeigt:
$\begin{eqnarray*} \left[\left. \begin{matrix} \bar{A} & I & 0\\ \bar{c} & 0 & 1 \end{matrix} \;\right|\; \begin{matrix} \bar{b} \\ \bar{f} \end{matrix} \;\right] \end{eqnarray*}$

Lt Wikipedia ist der Vektor c die "reduzierten Kosten". Was ich dabei nicht verstehe, ist:

welchen Zahlen in einem Beispieltableau der Vektor c entspricht
warum die reduzierten Kosten so heißen wie sie heißen

Vielen Dank für eure Hilfe.

23.09.2009, 15:03

Reksilat

Auf diesen Beitrag antworten »

RE: Simplex: reduzierte Kosten
Hi shihan,

Normalerweise schreibt man die Spalten für die Basisvariablen(BV) (also die Einheitsmatrix in Deinem Tableau) nicht mit, wozu auch, dort stehen eh keine nenneswerten informationen und es ist nur Schreibarbeit. Selbst auf der Wikiseite wird das im Beispiel später weggelassen.
Wozu die vorletzte Spalte gut sein soll, erschließt sich mir auch nicht. Selbst in dem diesem Tableau zugrundeliegenden Script findet die sich nicht.

Zum Vektor $\begin{eqnarray*} \bar{c} \end{eqnarray*}$ :
Nach einer Reihe von Simplexschritten befindet man sich eben in einer Ecke mit gewissen BV und NBV, wobei man in der Zielfunktion die BV eliminieren kann. Wenn nun $\begin{eqnarray*} x \end{eqnarray*}$ der Vektor der NBV ist, so lässt sich die Zielfunktion als $\begin{eqnarray*} z=f-\bar{c}^Tx \end{eqnarray*}$ schreiben. Wenn man nun die NBV $\begin{eqnarray*} x_i \end{eqnarray*}$ um den Wert $\begin{eqnarray*} \alpha \end{eqnarray*}$ erhöht, so reduziert sich die Zielfunktion um den Wert $\begin{eqnarray*} c_i\cdot \alpha \end{eqnarray*}$ und deshalb gibt der Vektor $\begin{eqnarray*} \bar{c} \end{eqnarray*}$ eben an, wie weit sich die Kosten reduzieren lassen. Sind alle Einträge negativ, so lassen sich die Kosten eben nicht mehr reduzieren, der Zielfunktionswert ist also optimal.

Zitat:

Was ich dabei nicht verstehe, ist welchen Zahlen in einem Beispieltableau der Vektor c entspricht

Hast Du denn ein Beispieltableau, in dem Du den Vektor nicht identifizieren kannst?

Gruß,
Reksilat.

23.09.2009, 15:55

shihan

Auf diesen Beitrag antworten »

Danke erstmal für die Erklärung Reksilat, auch wenn sie mir, sagen wir, etwas zu mathematisch ist Augenzwinkern

Lassen wir die unnötigen Dinge weg und gehen wir mal davon aus

$\begin{eqnarray*} \left[\left. \begin{matrix} \bar{A} \\ \bar{c} \end{matrix} \;\right|\; \begin{matrix} \bar{b} \\ \bar{f} \end{matrix} \;\right] \end{eqnarray*}$

entspricht in etwa dem

$\begin{eqnarray*} \left[\left. \begin{matrix} 2 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 30 & 20 & 0 & 0 & 0 \end{matrix} \;\right|\; \begin{matrix} 1500 \\ 1200 \\ 500 \\ 0 \end{matrix} \; \right] \end{eqnarray*}$

Zwischen der letzten und der vorletzten Zeile ist im Skript nochmals eine horizontale Linie gezogen (das habe ich in Latex nicht hinbekommen).
Soweit wie ich bis jetzt gekommen bin, ist (bitte berichtigen, falls ich daneben lieg):

die letzte Zeile ist die Zielfunktionszeile
die 0 rechts unten (unterhalb der imaginären Linie) ist der Zielfunktionswert

Was ist in diesem Fall ein Vektor? (2 1 1)? Ich hab keine Vektoren gegeben, sondern mehrere Gleichung und ein Tableau.
Was ist dann in diesem Fall in diesem Tableau der Vektor A, b, c und f?
Was sind in diesem Tableau die reduzierten Kosten?

Mein eigentliches Problem an der Sache ist, ich soll eine Aufgabe lösen und dabei eine best. Pivot-Regel anwenden, z.B. Blands Rule. Nachdem ich aber nicht weiss, was die reduzierten Kosten sind, kann ich die Regel auch nicht anwenden Augenzwinkern

Danke

23.09.2009, 16:02

Reksilat

Auf diesen Beitrag antworten »

$\begin{eqnarray*} c=\begin{pmatrix}30\\20\end{pmatrix} \end{eqnarray*}$
sind die reduzierten Kosten. Die Bezeichnung ist mMn aber verwirrend, da es sich hier ja nicht wirklich um Kosten handelt, sondern nur um Koeffizienten der Zielfunktion.

$\begin{eqnarray*} A=\begin{pmatrix}2&1\\1&1\\1&0\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} b=\begin{pmatrix}1500\\1200\\500\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} f=0 \end{eqnarray*}$

Horzontale Linie wird mit \hline erzeugt.

Neue Frage »

Antworten »

Simplex: reduzierte Kosten

Verwandte Themen