Lineare Optimierung

Neue Frage »

stud1989 Auf diesen Beitrag antworten »
Lineare Optimierung
Meine Frage:
Hab da eine Aufgabe, vllt auch viel zu einfach:

(a) Zeige, dass das LP immer eine zulässige Lösung hat
(b) Zeige, dass das LP immer eine optimale Lösung hat


Meine Ideen:
zu (a) würde ich einfach für alle i und z = 0 setzen, dann sind alle Bedingungen erfüllt, aber ob die das meinen?

zu (b) da z nach oben und nach unten beschränkt ist ( und ), kann das LP nicht unbeschränkt sein, damit gibt es eine (oder mehrere) Optimallösungen. Macht das Sinn?
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
1) Ja, das ist in jedem Falle eine zulässige Lösung.
2) Ist auch richtig (die Bedingung wird hier gar nicht benötigt)
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Danke, aber kann ich immer sagen, dass es (mind.) eine Optimallösung gibt, wenn das LP beschränkt ist? Also nicht nur im Bezug zu dieser Aufgabe, sondern allgemein? Ich suche die ganze Zeit einen Satz aus der Vorlesung, der dies besagt, finde aber nichts unglücklich
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Ja, das kann man allgemein so sagen:
Ist die Zielfunktion auf der zulässigen Menge beschränkt, dann besitzt das LP eine Optimallösung.
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Danke. Hier gehts gleich mit Aufgabe (c) weiter...

Geben Sie das Duale LP an:

ich hab jetzt:


Bin mir bei den Vorzeichen aber nicht ganz sicher. Bei Pi das soll ich der letzten Zeile nur größer/kleiner 0 heißen...
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Zitat:
Original von stud1989




Bin mir bei den Vorzeichen aber nicht ganz sicher. Bei Pi das soll ich der letzten Zeile nur größer/kleiner 0 heißen...
Was soll das heißen? Ungleichungen im primalen Problem werden zu vorzeichenbeschränkten Variablen.

Du solltest das primale Problem erstmal auf Normalenform bringen. Dann kannst du daraus das duale Problem ablesen.
 
 
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
gut also erstmal in Standardform:


so richtig!?
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Ne, auf der rechten Seite taucht bei dir eine zu optimierende Variable auf.

Ich meinte dass du das komplette Ungleichungssystem als Matrixschreibweise darstellst.
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
ich verstehe aber noch nicht ganz die Vorzeichenbedingungen, weil ich es jedes Mal anders lese oder verstehe.

es sei jetzt immer min cx und verschiedene Bedingungen:



Dann hab ich mir für das duale folgendes überlegt:

jeweils max


was ist richtig, was falsch und warum?
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
hmm, 4 und 6 sind wohl falsch, glaub ich. x ist nicht vorzeichenbeschränkt, also müsste da auf jeden Fall ne Gleichung hin, oder?
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
und 1 und 2 darf ich wegen min gar nicht anwenden, so langsam kommts, glaub ich ...
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
So ich probers jetz nochmal mit Aufgabe c



ich bin mir aber nicht sicher was die Bedingung für Auswirkungen auf das Duale hat. Ja, und welche Auswirkungen z hat, da die zu maximierende Variable auch rechts steht ... unglücklich
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
ist das oben nun richtig? Oder welche Auswirkungen hat z?
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Ich kann dir nicht ganz folgen...

Die entsprechende Standardform sieht so aus:




Das ist eine ganz gewöhnliche Standardform.

Du hast m+1 Ungleichungen und n+1 Variablen, also hat das duale Problem n+1 Ungleichungen und m+1 Variablen.

Das solltest du dann direkt in duale Form bringen können.
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
ich glaub ich ahne, was du meinst, ist mir aber zu kompliziert alle Matrizen in Latex zu schreiben.

Am Ende hab ich auf jeden Fall mal:
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Was genau bezeichnet bei dir? Ist das Transponiert oder doch nur ein Variablenindex? verwirrt

Sieht aber soweit ganz richtig aus.
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
ist transponiert (siehe Formeleditor)
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Zitat:
Original von stud1989
ist transponiert (siehe Formeleditor)
Ungewöhnliche Notation, aber egal..

Das duale Problem stimmt so. Freude
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
die Notation ist genau wie in der Vorlesung ;-)
Nur hab ichs oftmal auch mit y statt mit Pi gesehen, aber die Transponierung ist eig. immer dabei ;-)
Oder wie kennst du es?
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Als Transponiert kenne ich nur ein hochgestelltes T geschockt
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
achso ok, ja ich auch, das gibts in diesem Editor aber nich ;-)
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Zitat:
Original von stud1989
achso ok, ja ich auch, das gibts in diesem Editor aber nich ;-)
Einfach ein ganz normales, hochgestelltes ^T.
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
ja, das hab ich mir jetzt auch gedacht^^ Aber danke trotzdem ;-)
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
So, weiter gehts:

Zeigen Sie, dass das LP (siehe oben) immer eine optimale Lösung mit Zielfunktionswert 0 oder 1 hat. (Hinweis: Nutzen Sie Komplementären Schlupf)

Da hab ich jetzt mal alle Gleichungen ausgestellt, die letzte Zeile davon lautet:
,
damit ist max z auch gleich 1

wenn aber , kann z alles sein. Ich hab mir dann mal die Zeile zu hilfe genommen. Wenn z = 0 ist die Gleichung erfüllt und dann ist auch max z = 0

Es könnte aber auch die ganze Klammer mit allen Null sein, oder nicht? ist ja schonmal 0. Ich kann aber auch kein riesiges Gleichungssystem aufsetzen und alle Möglichkeiten durchgehen, oder?

Oder reicht das, da im dualen ja nur max steht und da das dann ja 0 ist!?
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
Hm, ich hätte hier ohne den komplementären Schlupf über das primale Problem argumentiert:
:


Offenbar ist der Funktionswert durch 1 beschränkt, daher existiert in jedem Falle eine Optimallösung.

Fall 1:
Es existiert ein , so dass . In diesem Falle liefert die Optimallösung 1

Fall 2:
Es existiert kein solches x. Dann liefert die Optimallösung 0. Diese Lösung ist in jedem Falle zulässig, also kann das Optimum nicht kleiner sein.

Fall 3:
Das LP hat ein Maximum kannst du zu einem Widerspruch führen.

Hier mit komplementären Schlupf zu argumentieren halte ich für "mit Kanonen auf Spatzen schließen".
stud1989 Auf diesen Beitrag antworten »
RE: Lineare Optimierung
der Hinweis stand so in der Aufgabenstellung...

Aber ist meins also auch richtig?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »