Simplexmethode

20.08.2010, 11:14

saz

Simplexmethode

Wir hatten in unserer Optimierungsvorlesung folgenden Satz:

Sei die lineare Optimierungsaufgabe $\begin{eqnarray*} z(x) := c^T \cdot x \to \min (x \in G) \end{eqnarray*}$ wobei $\begin{eqnarray*} G := \{x \in \mathbb{R}^n: A \cdot x = b, x \geq 0 \} \end{eqnarray*}$ gegeben mit $\begin{eqnarray*} G \not= \emptyset \end{eqnarray*}$ und es existiere $\begin{eqnarray*} \alpha \in \mathbb{R} \end{eqnarray*}$ mit $\begin{eqnarray*} z(x) \geq \alpha \end{eqnarray*}$ für alle $\begin{eqnarray*} x \in G \end{eqnarray*}$ . Dann existiert eine optimale Lösung.

Wir hatten das als Folgerung von einem Satz, der besagt, dass (für obige lin. OA, jedoch ohne die Zusatzbedingungen) aus der Existenz eines zulässigen Simplex-Schemas folgt, dass das Simplex-Verfahren nach endlich vielen Schritten abbricht (mit Lösung/Entartung) und das mit Hilfe der Endlichkeit der Ecken bewiesen.
Irgendwie sehe ich aber nicht, wie man den obigen Satz beweisen könnte, da ich ja nicht weiß, ob ein entsprechendes zulässiges Schema überhaupt existiert - und was mir diese untere Schranke $\begin{eqnarray*} \alpha \end{eqnarray*}$ helfen soll.

Danke schon mal! (Leider sind meine eigenen Ideen ziemlich begrenzt, weil es mir eben an einem Ansatz mangelt.)

Edit: Das einzige, was mir gerade noch einfällt, wäre eine Art Auschlußverfahren: Da ich weiß, dass der zulässige Bereich nicht leer ist, kann es nicht an diesem scheitern. Außerdem ist die Zielfunktion nach unten beschränkt, also kann die Entartung $\begin{eqnarray*} z^* = - \infty \end{eqnarray*}$ ebenfalls nicht auftreten. Also bleibt nur, dass eine Lösung existiert. Aber wie ich das in einen Beweis/Formeln packen soll... unglücklich

23.08.2010, 09:54

saz

Auf diesen Beitrag antworten »

Niemand eine Idee? So schwer kann es eigentlich gar nicht sein...

24.08.2010, 20:39

Abakus

Auf diesen Beitrag antworten »

Hallo!

$\begin{eqnarray*} H := \{z(x)~ :~ x \in G~ \} \end{eqnarray*}$ ist nach unten beschränkt, nichtleer; und besitzt daher ein Infimum.

Betrachte jetzt eine (monoton fallende) Folge in H gegen dieses Infimum; hilft das schon was?

Grüße Abakus smile

24.08.2010, 21:05

saz

Auf diesen Beitrag antworten »

Aaaaaah... Meine Idee: Da H beschränkt ist, konvergiert die monoton fallende Folge auf jeden Fall (wenn auch zunächst nicht in H). Um zu zeigen, dass sie in H konvergiert, muss ich zeigen, dass H abgeschlossen ist. Und das folgt daraus, dass G abgeschlossen ist und das Urbild einer stetigen Funktion (da linear) abgeschlossen ist.
Damit folgt, dass ein $\begin{eqnarray*} x \in G \end{eqnarray*}$ existiert mit $\begin{eqnarray*} z(x) =\inf_{q \in H} = \min_{q \in H} \end{eqnarray*}$ .

Oder? smile

24.08.2010, 21:39

Abakus

Auf diesen Beitrag antworten »

Ja, klingt gut wie du es schreibst. Das H ist natürlich erstmal nur nach unten beschränkt, und die Abgeschlossenheit von H ist eine hinreichende (nicht notwendige) Bedingung für die Konvergenz der Folge.

Vermutlich liegt der Knackpunkt hier u.a. darin, auf die Idee zu kommen, die Stetigkeit zu benutzen.

Grüße Abakus smile

09.09.2010, 09:25

saz

Auf diesen Beitrag antworten »

Zitat:

Original von saz
Und das folgt daraus, dass G abgeschlossen ist und das Urbild einer stetigen Funktion (da linear) abgeschlossen ist.

Ist zwar schon wieder eine Weile her, aber wie mir aufgefallen ist, habe ich hier Unsinn geschrieben: G ist zwar abgeschlossen, aber da H ja das Bild von G ist, folgt leider nicht die Abgeschlossenheit von H verwirrt

Irgendwie fällt mir auch kein Ausweg ein, weil man bei einer stetigen Funktion ja nur für kompakte Mengen Aussagen über das Bild der Menge hat (ist dann wieder kompakt), aber kompakt muss G ja nicht sein.

09.09.2010, 13:18

Reksilat

Auf diesen Beitrag antworten »

Ich glaube nicht, dass man hier nur damit, dass G abgeschlossen und z linear ist, zum Ziel kommt.

Man benötigt hier die Eigenschaft, dass G ein (unbeschränktes) Polyeder ist und somit, da G ja nicht leer ist, auch Ecken besitzt. Dann hat man eine Startecke und wendet das Simplex-Verfahren an.

Gruß,
Reksilat.

09.09.2010, 15:00

saz

Auf diesen Beitrag antworten »

Hmh, würde denn die Aussage für $\begin{eqnarray*} G=\{x; A \cdot x \leq b\} \end{eqnarray*}$ stimmen? Und falls ja: Was wäre hier der Ansatz? Weil: Aus der Aussage würde doch dann auch die eigentliche Aussage folgen, oder nicht? Schließlich kann man ja jedes (lineare) Ungleichungssystem in ein Gleichungssystem verwandeln (und umgekehrt)...

Wir haben mit Hilfe von diesem Satz (oben aus dem ersten Post) dann bewiesen, dass die Menge $\begin{eqnarray*} G = \{x; A \cdot x = b\} \end{eqnarray*}$ mindestens eine Ecke hat, aber diese Aussage würde ich ja eigentlich schon brauchen, um den Satz überhaupt zu beweisen.

Ich dachte ja auch erst, dass da vllt. etwas fehlt (oder falsch ist), allerdings kann man im Internet an verschiedenen Stellen lesen, dass bei linearen OA nur drei Fälle auftreten können:
- zulässiger Bereich leer (-> keine Lösung)
- Zielfunktion unbeschränkt (-> keine Lösung)
- anderenfalls existiert Lösung
... und das wäre ja oben durchaus erfüllt (also nichtleer, beschränkt). Insofern müsste man es ja eigentlich irgendwie beweisen können verwirrt

09.09.2010, 15:33

Reksilat

Auf diesen Beitrag antworten »

Zitat:

Original von saz
Wir haben mit Hilfe von diesem Satz (oben aus dem ersten Post) dann bewiesen, dass die Menge $\begin{eqnarray*} G = \{x; A \cdot x = b\} \end{eqnarray*}$ mindestens eine Ecke hat

Wie das? Hier steht doch ein ganz anderes G, welches entweder leer ist, nur aus einem Punkt besteht oder eben ein affiner Unterraum ohne Ecken ist. Wie will man da beweisen, dass eine Ecke existiert?

09.09.2010, 15:56

saz

Auf diesen Beitrag antworten »

Naja, natürlich alles unter der Voraussetzung, dass $\begin{eqnarray*} x \geq 0 \end{eqnarray*}$ (so wie's im ersten Posting stand) - falls das vllt. jetzt missverständlich war.

Bewiesen haben wir es, indem wir eine "Ersatz"-Optimierungsaufgabe definiert haben:

$\begin{eqnarray*} \tilde{G} := \{(x,y) \in \mathbb{R}^n_+ \times \mathbb{R}^m_{-}: A \cdot x + I \cdot y = b \}<br /> \tilde{f} := \sum_{i=1}^m y_i \to \min_{(x,y) \in \tilde{G}} \end{eqnarray*}$

Dann haben wir unter der Voraussetzung, dass $\begin{eqnarray*} \{x \in \mathbb{R}^n_+: A \cdot x = b\} \not= \emptyset \end{eqnarray*}$ den Satz angewendet und eine Ecke erhalten.

Wie könnte man denn die Aussage für $\begin{eqnarray*} G := \{x \in \mathbb{R}^n_+: A \cdot x \leq b \} \end{eqnarray*}$ beweisen?

09.09.2010, 16:27

Reksilat

Auf diesen Beitrag antworten »

Ich denke mal, dass die Idee hier die Folgende ist:

Man hat ein Problem $\begin{eqnarray*} G= \{x \in \mathbb{R}^n_+: A \cdot x = b\} \not= \emptyset \end{eqnarray*}$ , von dem man dank des obigen Satzes weiß, dass es eine optimale Lösung besitzt.
Nun benötigt man für den Simplex aber noch eine Startecke und die wollen wir finden.

Hier kommt das Ersatzproblem rein:
$\begin{eqnarray*} \tilde{G} := \{(x,y) \in \mathbb{R}^n_+ \times \mathbb{R}^m_{+}: A \cdot x + I \cdot y = b \} \end{eqnarray*}$
(Ich nehme an, y soll auch nichtnegativ sein.)

Offensichtlich hat auch dieses Problem die obige Form und auch die ZF ist nach unten beschränkt. Da $\begin{eqnarray*} G\neq \emptyset \end{eqnarray*}$ ist, muss auch $\begin{eqnarray*} \widetilde{G}\neq \emptyset \end{eqnarray*}$ sein. Nach dem obigen Satz hat das Problem also eine Lösung.

Für dieses Problem findet man auch leicht eine Startecke, nämlich $\begin{eqnarray*} x=0 \end{eqnarray*}$ und $\begin{eqnarray*} y=b \end{eqnarray*}$ . Mit dem Simplex berechnet man nun eine optimale Lösung, bei der durch die ZF $\begin{eqnarray*} \tilde{f} \end{eqnarray*}$ natürlich $\begin{eqnarray*} y=0 \end{eqnarray*}$ ist. Das $\begin{eqnarray*} x \end{eqnarray*}$ ist dann eine Startecke für das eigentliche Problem mit der ZF $\begin{eqnarray*} z \end{eqnarray*}$ .

Soweit klar?

Welche Aussage möchtest Du denn nun für das Problem $\begin{eqnarray*} G= \{x \in \mathbb{R}^n_+: A \cdot x \leq b\} \end{eqnarray*}$ beweisen?
Letztlich kann man diese Form doch durch Schlupfvariablen auf die Normalform bringen.

Gruß,
Reksilat.

09.09.2010, 17:21

saz

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
Man hat ein Problem $\begin{eqnarray*} G= \{x \in \mathbb{R}^n_+: A \cdot x = b\} \not= \emptyset \end{eqnarray*}$ , von dem man dank des obigen Satzes weiß, dass es eine optimale Lösung besitzt.

Und wie beweise ich das nun? Das war ja meine eigentliche Frage. Du hattest ja geschrieben, dass man für (unbeschränkte) nichtleere Polyeder weiß, dass diese Ecken haben. Aber wie kann ich das denn beweisen?

Wie man dann daraus schlussfolgert (mit dem was du oben beschrieben hast), dass $\begin{eqnarray*} \{x \in \mathbb{R}^n_+: A \cdot x = b \} \end{eqnarray*}$ eine Ecke hat, ist mir auch klar.

(Und sorry, ja, das y sollte nichtnegativ sein, Tippfehler.)

09.09.2010, 17:27

Reksilat

Auf diesen Beitrag antworten »

Wenn Dir die Konstruktion, die ich gerade lang und breit erklärt habe, bereits klar ist, warum erwähnst Du sie dann überhaupt? Was hat denn das dann mit Deinem Problem zu tun?
Außerdem habe ich in meinem ersten Posting hier was geschrieben, was Dir scheinbar egal war. Jedenfalls hatte Deine Antwort keine Bezug dazu.

09.09.2010, 17:31

saz

Auf diesen Beitrag antworten »

War wohl ein Missverständnis, ich hatte diese Konstruktion auf deine Frage bezogen, wie wir das bewiesen hatten.

Und ich habe meinen Beitrag ja nochmal editiert, was du vllt. nicht gesehen hast, insofern hat es schon einen Bezug. Aber nun gut, eben hier nochmal die Frage:

Du hattest ja geschrieben, dass man für (unbeschränkte) nichtleere Polyeder weiß, dass diese Ecken haben. Aber wie kann ich das denn beweisen?

09.09.2010, 18:36

Reksilat

Auf diesen Beitrag antworten »

Ihr müsst doch irgendwo den Begriff "Ecke" definiert haben. Schau doch da mal nach. Man muss nicht immer alles elementar beweisen. Zumal die Terminologie auch überall etwas unterschiedlich ist.

Schau Dir aber bitte noch mal Deine Antwort auf meinen ersten Beitrag hier an. Wie um Himmels Willen soll ich da auf die Idee kommen, dass Du meine Antwort nicht verstanden hast? Du bringst dort plötzlich zwei neue Probleme an und dadurch wird das Ganze vor allem unübersichtlich.

Gruß,
Reksilat.

09.09.2010, 20:30

saz

Auf diesen Beitrag antworten »

Ja, tut mir leid. Ich habe dein erstes Posting einfach vollkommen missverstanden. Sorry, für den Hick-Hack. Zu deiner Frage: Eigentlich haben wir Ecke so definiert, dass $\begin{eqnarray*} x \in G \end{eqnarray*}$ eine Ecke ist, falls $\begin{eqnarray*} x = \frac{u+v}{2} \Rightarrow u=v=x \end{eqnarray*}$ für $\begin{eqnarray*} u,v \in G \end{eqnarray*}$ . Aber damit kommt man hier wahrscheinlich nicht übermäßig weit.

Wie ich gesehen habe, hatten wir noch die Äquivalenz

$\begin{eqnarray*} x \in G \end{eqnarray*}$ Ecke von G $\begin{eqnarray*} \Leftrightarrow \{a_i^T\}_{i \in I_0} \end{eqnarray*}$ enthält Basis des $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ wobei $\begin{eqnarray*} I_0 := \{i: a_i \cdot x = b\} \end{eqnarray*}$ und Rang A = m

Aber der Satz kann doch eigentlich nun wirklich nicht stimmen - weil aus $\begin{eqnarray*} m \leq n \end{eqnarray*}$ (wegen Rang A =m) ja automatisch folgt, dass die Zeilenvektoren der Matrix keine Basis des $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ enthalten können außer für den Spezialfall $\begin{eqnarray*} m= n \end{eqnarray*}$ . unglücklich

Anmerkung: $\begin{eqnarray*} a_i \end{eqnarray*}$ sind die Zeilenvektoren der Matrix A

10.09.2010, 10:45

Reksilat

Auf diesen Beitrag antworten »

Zitat:

Original von saz
$\begin{eqnarray*} x \in G \end{eqnarray*}$ Ecke von G $\begin{eqnarray*} \Leftrightarrow \{a_i^T\}_{i \in I_0} \end{eqnarray*}$ enthält Basis des $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ wobei $\begin{eqnarray*} I_0 := \{i: a_i \cdot x = b\} \end{eqnarray*}$ und Rang A = m

Also bei Deinem G wird die Gleichung $\begin{eqnarray*} Ax=b \end{eqnarray*}$ doch sowieso in jeder Zeile erfüllt. Diese Definition der Ecke passt also nicht genau auf das Problem.
Bei Deinem Problem würde man zum Beispiel die n Gleichungen $\begin{eqnarray*} x_i\geq 0 \end{eqnarray*}$ noch dazunehmen, dann hat man insgesamt n+m Ungleichungen, von denen bei m Stück sowieso das Gleichheitszeichen steht. Ein Eckpunkt ist dann ein Punkt, bei dem zusätzlich noch n-m Gleichungen der Form $\begin{eqnarray*} x_i=0 \end{eqnarray*}$ erfüllt sind. (Dies sind dann die Nichtbasisvariablen.)
_______

Zumeist interpretiert man Ecken als Schnittpunkte von n Hyperebenen. Dabei steht jede Gleichung $\begin{eqnarray*} a_i\cdot x=b \end{eqnarray*}$ für eine Hyperebene und auch die Gleichungen $\begin{eqnarray*} x_j=0 \end{eqnarray*}$ sind Hyperebenen. Die Menge $\begin{eqnarray*} G'=\{x|Ax=b\} \end{eqnarray*}$ (zunächst ohne NNB) bildet also einen Schnitt von m Hyperebenen; G ist damit ein n-m dimensionaler affiner Unterraum. Dieser kann noch maximal zu n-m Hyperebenen der Form $\begin{eqnarray*} x_i=0 \end{eqnarray*}$ parallel sein und muss demnach mindestens m Hyperebenen der Form $\begin{eqnarray*} x_i=0 \end{eqnarray*}$ schneiden. Durch jeden dieser Schnitte erhält man einen Eckpunkt der Menge $\begin{eqnarray*} G' \end{eqnarray*}$ . Dass ein solcher Eckpunkt auch so gewählt werden kann, dass die restlichen Nichtnegativitätsbedingungen erfüllt sind, kann man sich auch noch überlegen. Ich wollte hier aber nur kurz etwas zur geometrischen Struktur der Menge G schreiben.

Jedenfalls ist die Behauptung, dass die Menge $\begin{eqnarray*} G \end{eqnarray*}$ eine Ecke hat, nicht einfach elementar beweisbar, sondern man muss zuerst ein wenig theoretische Grundlagen sammeln.

Gruß,
Reksilat.

10.09.2010, 11:08

saz

Auf diesen Beitrag antworten »

Okay, danke - für deine Geduld und deine ausfürlichen Erklärungen. Gott

Ich hätte nicht gedacht, dass es so kompliziert ist, zu beweisen, dass G eine Ecke hat - so wie es aussieht, haben wir dann wohl einfach in der Vorlesung nicht die nötigen theoretischen Grundlagen bekommen. Nun gut, dann werde ich mir einfach die Tatsache und dein (geometrisches) Bild so merken.

Danke nochmal.

10.09.2010, 22:50

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von saz

Zitat:

Original von saz
Und das folgt daraus, dass G abgeschlossen ist und das Urbild einer stetigen Funktion (da linear) abgeschlossen ist.

Mit dem Satz vom abgeschlossenen Graphen (Wiki) ist z ein abgeschlossener Operator. Daraus folgt es direkt, aber du kannst auch die Folge weiter betrachten:

betrachte die Urbildfolge zu $\begin{eqnarray*} z(x_n) \end{eqnarray*}$ , also der Folge gegen das Infimum, und versuche nun via Stetigkeit und Linearität von z, die Konvergenz derselben zu zeigen. Ggf. muss noch eine Teilfolge betrachtet bzw. die Folge modifiziert werden, das Bild des Grenzwertes sollte dann das gesuchte Minimum sein.

Grüße Abakus smile

11.09.2010, 10:19

saz

Auf diesen Beitrag antworten »

Zitat:

Original von Abakus
Mit dem Satz vom abgeschlossenen Graphen (Wiki) ist z ein abgeschlossener Operator.

Hey, das ist ja wirklich ein schöner Satz smile

- leider kriegen wir ihn (wenn überhaupt) erst im kommenden Semester in Funktionalanalysis.

Danke auch an dich für deinen Denkanstoß, werde nochmal drüber nachdenken, ob ich beweisen kann, dass $\begin{eqnarray*} (x_n) \end{eqnarray*}$ konvergiert...

11.09.2010, 10:29

Reksilat

Auf diesen Beitrag antworten »

Ich denke nicht, dass man die Konvergenz der $\begin{eqnarray*} x_n \end{eqnarray*}$ zeigen kann.

Beispiel:
$\begin{eqnarray*} G\subset\mathbb{R}^2 \end{eqnarray*}$
$\begin{eqnarray*} x_n=(n,1/n) \end{eqnarray*}$
$\begin{eqnarray*} z: (a,b)\to b \end{eqnarray*}$

Dann konvergiert die Folge $\begin{eqnarray*} z(x_n)=1/n \end{eqnarray*}$ natürlich, aber man kann sich leicht ein abgeschlossenes $\begin{eqnarray*} G \end{eqnarray*}$ konstruieren, in dem kein $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} z(x)=0 \end{eqnarray*}$ existiert.
Zum Beispiel kann man gleich $\begin{eqnarray*} G=\{x_n|n\in\mathbb{N}\} \end{eqnarray*}$ wählen.

Deswegen meinte ich ja, dass man die Eigenschaft, dass $\begin{eqnarray*} G \end{eqnarray*}$ ein Polyeder ist, benötigt.

@saz: Dieser Beitrag über konvexe Polyeder, also gerade die zulässigen Mengen beim Simplex-Algorithmus könnte für Dich auch ganz interessant sein.

Gruß,
Reksilat.

12.09.2010, 18:04

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
Ich denke nicht, dass man die Konvergenz der $\begin{eqnarray*} x_n \end{eqnarray*}$ zeigen kann.

...

Deswegen meinte ich ja, dass man die Eigenschaft, dass $\begin{eqnarray*} G \end{eqnarray*}$ ein Polyeder ist, benötigt.

Ein ziemlich gut treffendes (Gegen-) Beispiel, ja.

Mir würde die Beschränktheit von $\begin{eqnarray*} G \end{eqnarray*}$ bzw. dem unten konstruierten $\begin{eqnarray*} G' \end{eqnarray*}$ reichen (was bei endlich vielen Restriktionen gleichbedeutend zu Polyeder ist): wenn $\begin{eqnarray*} G \end{eqnarray*}$ beschränkt, besitzt die Folge $\begin{eqnarray*} (x_n) \end{eqnarray*}$ darin einen (Folgen-) Häufungspunkt $\begin{eqnarray*} x \end{eqnarray*}$ , und es existiert eine konvergente Teilfolge von $\begin{eqnarray*} (x_n) \end{eqnarray*}$ , die gegen diesen Häufungspunkt $\begin{eqnarray*} x \end{eqnarray*}$ konvergiert. Da $\begin{eqnarray*} G \end{eqnarray*}$ abgeschlossen ist, folgt $\begin{eqnarray*} x \in G \end{eqnarray*}$ und damit muss für den Bildgrenzwert gelten: $\begin{eqnarray*} z(x) = \inf H \in H \end{eqnarray*}$ .

$\begin{eqnarray*} G \end{eqnarray*}$ selbst muss jedoch nicht beschränkt sein, wie in dem Beispiel aufgezeigt. Es reicht allerdings statt $\begin{eqnarray*} G \end{eqnarray*}$ , die Teilmenge $\begin{eqnarray*} G' \end{eqnarray*}$ zu betrachten, die folgende zusätzliche Restriktionen erfüllen soll, wobei an den Lösungen dadurch nichts verändert wird:

$\begin{eqnarray*} c^T \cdot x \leq \inf H + \epsilon \end{eqnarray*}$

und

$\begin{eqnarray*} c^T \cdot x \ge \inf H \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} \epsilon > 0 \end{eqnarray*}$ geeignet klein gewählt. Bei dem Beispiel oben werden aber selbst die zusätzlichen Restriktionen nichts ändern (dh. das $\begin{eqnarray*} G' \end{eqnarray*}$ ist wohl immer noch unbeschränkt dort).

Grüße Abakus smile

Neue Frage »

Antworten »

Simplexmethode

Verwandte Themen