Simplex Algorithmus Verständnis

07.05.2013, 23:47	Max Flow	Auf diesen Beitrag antworten »
Simplex Algorithmus Verständnis Ich weiß wie der Algorithmus funktioniert, wenn man einen Knoten des Polyeders kennt, um daraus einen Knoten zu bestimmen, der eine optimale Lösung realisiert. Wenn ein Problem in der Form maximiere $\begin{eqnarray} c\cdot x \end{eqnarray}$ mit $\begin{eqnarray} Ax\leq b \end{eqnarray}$ beschrieben wird und der Rang von A kleiner als die Anzahl der Komponenten von x ist, dann gibt es aber keine Knoten, was macht man dann? Und wie findet man einen (beliebigen) Knoten, wenn es einen gibt, damit man mit dem Algorithmus anfangen kann?
07.05.2013, 23:55	Max Flow	Auf diesen Beitrag antworten »
Einen Ansatz zur zweiten Frage, den ich gelesen habe: (Bitte ignorieren, wenn jemand diese Frage nur direkt beantworten will): Ein Programm der Art minimiere $\begin{eqnarray} 1\cdot (y'+y'') \end{eqnarray}$ mit $\begin{eqnarray} A'x+y'\leq b' \end{eqnarray}$ und $\begin{eqnarray} A''x-y''\leq b'', y'\geq 0, y''\geq 0 \end{eqnarray}$ zu betrachten, wenn $\begin{eqnarray} b'\geq 0 \end{eqnarray}$ der positive Teil von $\begin{eqnarray} b \end{eqnarray}$ und $\begin{eqnarray} b''<0 \end{eqnarray}$ der negative Teil ist und A', A'' die Matrizen mit den entsprechenden Zeilen von A. Dann entsprechen optimale Lösungen von diesem Programm (bei denen y',y'' Null sein müssen) irgendwelchen Lösungen des ursprünglichen Problems. Aber dieses Problem hat mehr Variablen als Ungleichungen, was mich auf meine erste Frage zurückführt.
08.05.2013, 00:29	Max Flow	Auf diesen Beitrag antworten »
Bei erneuter Lektüre haben sich jetzt doch beide Fragen geklärt. Es ist also nicht nötig zu antworten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »