Forum:  Numerik & Optimierung
Thema: Optimalwert beweisen
Themen-Übersicht
LamyOriginal
Aktiv
Dabei seit: 20.11.2018
Mitteilungen: 211
Aus:
Themenstart: 2020-09-28 14:48

Hallo,
ich lerne für meine Optimierungsklausur und verstehe den Lösungsweg einer Aufgabe nicht. Wäre sehr nett, wenn mir den einer erklären könnte.

Sei $A \in \mathbb{R^{mxm}}$ invertierbar und $b, c \in \mathbb{R^{m}}$ Betrachten Sie das Lineare Problem
$min c^Tx$
$s.t. Ax \leq b$.
Zeigen Sie, dass für den Optimalwert p∗ gilt:
p*=$\begin{cases}
    & c^TA^{-1}b                    && \text{falls}\ (A^{-1})^T c \leq 0 \\
    & -\infty                && \text{sonst} \\
  \end{cases}$

Ist als Optimalwert der optimale Zielfunktionswert gemeint?

Als Bilddatei habe ich den Lösungsweg beigefügt. Ich verstehe nicht wie man bei der Fallunterscheidung von $A^{-1}^Tc$ vorgegangen ist und dann das zugehörige y bestimmt hat und warum das LP im Fall >0 unbeschränkt ist.



Danke für jede Hilfe!


Creasy
Senior
Dabei seit: 22.02.2019
Mitteilungen: 557
Aus: Bonn
Beitrag No.1, eingetragen 2020-09-29 13:49

Hallo,

Schauen wir mal auf den eindimensionalen Fall:

Angenommen du willst die Funktion f(z)=az minimieren mit a und z reelle Zahlen und zwar unter der nebenbedingung z<= b für eine reelle Zahl b. Graphisch ist f eine Gerade durch den Ursprung. Wenn man bei b auf der x Achse eine senkrechte Gerade zieht, dann siind
Alle z<=b links von diesem Strich. Anschaulich suchen wir also den kleinsten ywert der Gerade, wo der x wert links von b liegt. (Mal es dir mal auf).

Da müssen wir jetzt unterscheiden: fällt die Gerade? Dann ist der Niedrigste y wert so weit rechts wie möglich also an der Stelle b.
Wenn die Gerade steigt, so ist der y wert umso kleiner , je näher x gegen -unendlich geht. Das Minimum ist daher -unendlich.

Hilft das bereits? Ansonsten müsstest du deine Frage etwas konkretisieren, was du genau an der Lösung nicht verstehst.

Und wenn mein Handy noch einmal ein y zu einem x oder ein b zu einem
n macht - weine ich :)

Grüße Creasy


LamyOriginal
Aktiv
Dabei seit: 20.11.2018
Mitteilungen: 211
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-29 19:27

2020-09-29 13:49 - Creasy in Beitrag No. 1 schreibt:
Hallo,

Schauen wir mal auf den eindimensionalen Fall:

Angenommen du willst die Funktion f(z)=az minimieren mit a und z reelle Zahlen und zwar unter der nebenbedingung z<= b für eine reelle Zahl b. Graphisch ist f eine Gerade durch den Ursprung. Wenn man bei b auf der x Achse eine senkrechte Gerade zieht, dann siind
Alle z<=b links von diesem Strich. Anschaulich suchen wir also den kleinsten ywert der Gerade, wo der x wert links von b liegt. (Mal es dir mal auf).

Da müssen wir jetzt unterscheiden: fällt die Gerade? Dann ist der Niedrigste y wert so weit rechts wie möglich also an der Stelle b.
Wenn die Gerade steigt, so ist der y wert umso kleiner , je näher x gegen -unendlich geht. Das Minimum ist daher -unendlich.

Hilft das bereits? Ansonsten müsstest du deine Frage etwas konkretisieren, was du genau an der Lösung nicht verstehst.

Und wenn mein Handy noch einmal ein y zu einem x oder ein b zu einem
n macht - weine ich :)

Grüße Creasy

Alles gut, danke für die Erklärung, aber ich habe diese Aufgabe mit der Lagrange Dualität gelöst und so viel besser verstanden 😊




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249574=110
Druckdatum: 2020-12-05 23:25