Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » revidiertes simplexverfahren

revidiertes simplexverfahren

Universität / Fachhochschule

Tags: Beispiel, Lineare Optimierung, Optimierung, revidiert, Simplex, Simplex Verfahren, Simplexalgorithmus

mokaan aktiv_icon

16:26 Uhr, 01.01.2011

Hallo Ihr alle
Ich habe hier ein Lineares Programm, dass ich mithilfe des revidierten Simplex-Verfahrens lösen soll. Jedoch steige ich bei den ganzen Bezeichnungen zum Schluss nicht mehr durch.
Hier erst einmal das Programm:

m a x

5 x_{1} + 6 x + 9 x_{3} + 8 x_{4}

u n t e r

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

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

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

Nun wende ich das revidierte Simplexverfahren an:

Durch Einfügen von Schlupfvariablen erhalte ich dann eine Matrix

A

, auf die ich mich dann bezüglich Basis und Nichtbasis beziehen kann:

A = (\begin{array}{rcl} 1 & 2 & 3 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 \end{array})

Die Zielfunktion ist dann:

c^{T} = (5, 6, 9, 8, 0, 0)

Schritt 0 (Start):
Basis:

B = (5, 6)

Nichtbasis:

N = (1, 2, 3, 4)

Der Lösungsvektor:

\overline{b} = b = (\binom{5}{1})

Schritt 1, Optimalitätstest (BTRAN):
a) Löse Gleichungssystem

y^{T} A_{B} = c_{B}^{T}

(\binom{y_{1}}{y_{2}})

(\begin{array}{rcl} 1 & 0 \\ 0 & 1 \end{array}) = (\binom{0}{0})

\Rightarrow

(\binom{y_{1}}{y_{2}})

=

(\binom{0}{0})

b) Berechne reduzierte Kosten

{\overline{c}}_{N}^{T} = c_{N}^{T} - y^{T} A_{N} = (5, 6, 9, 8)

c) Falls

{\overline{c}}_{N} \leq 0

, dann Optimal (hier noch nicht der Fall)

Schritt 2, Pivotspaltenauswahl (PRICE):
Wähle

s

, so dass

{\overline{c}}_{N (S)} = max_{j \in N} {{\overline{c}}_{N (j)}}

Da der größte Eintrag

9

ist, folgt hier dann

s = 3

.

Schritt 3, Beschränktheitstest (FTRAN):
a) Löse

A_{B} d = - A_{N (s)}

\Rightarrow (\begin{array}{rcl} 1 & 0 \\ 0 & 1 \end{array}) (\binom{d_{1}}{d_{2}})

=

(\binom{- 3}{- 1})

\Rightarrow (\binom{d_{1}}{d_{2}})

=

(\binom{- 3}{- 1})

b) ist

d \geq 0

dann unbeschränkt (hier auch nicht der Fall).

Schritt 4, Schrittweitenbestimmung (RATIO):
Wähle

r

, so dass

- \frac{{\overline{b}}_{r}}{d_{r}} = min_{i} {- \frac{{\overline{b}}_{i}}{d_{i}} : d_{i} < 0}

Hier also

min {\frac{- 5}{- 3}; - \frac{- 1}{- 1}}

Der zweite Wert ist das Minimum

\to r = 2

Ich hoffe, das soweit alles stimmt.
Jetzt kommt nämlich der Punkt, andem ich nicht mehr sicher bin, wie es weiter geht.
Also wir haben aufgeschrieben:

Schritt 5, Aktualisierung (UPDATE):

B \leftarrow (B (1), . . . B (r - 1), N (s), B (r + 1), . . ., B (m))

N \leftarrow (N (1), . . . N (s - 1), N (r), B (s + 1), . . ., B (n))

Löse

A_{B} \overline{b} = b

, gehe dann zu Schritt 1.

Meine neune Basis ist dann also

B = (5, 3)

, die neue Nichtbasis ist

N = (1, 2, 6, 4)

.
Wenn ich jetzt aber das Gleichungssystem löse, nehme ich dann schon die neue Basis, oder noch die alte?
Und vor allem: kenne ich

b

und suche ein neues

\overline{b}

oder kenne ich

\overline{b}

und suche ein neues

b

?

Schon einmal Danke für die Hilfe
mokaan

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

836804

	Status: nicht eingeloggt	Noch nicht registriert?