Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Lineares Programm (eindeutige Lösung)
Autor
Universität/Hochschule J Lineares Programm (eindeutige Lösung)
JamesNguyen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 08.11.2020
Mitteilungen: 222
  Themenstart: 2022-05-27

Hallo Leute, ich weiß nicht wie ich folgende Aufgabe angehen kann: Geg: A \el\ \IR^(m x n) mit m < n, c \el\ \IR^n, b \el\ \IR^m Z.z: Das lineare Programm (nicht in Normalform) min c^T x u.d.N. Ax<=b (keine Vorzeichenbeschränkung für x) kann nie eine eindeutige Lösung besitzen. Hat jemand einen Tipp wie ich anfangen könnte. Vielen Dank, James


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3759
  Beitrag No.1, eingetragen 2022-05-27

Überleg dir, dass es zu der Matrix $A$ wegen $m


   Profil
JamesNguyen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 08.11.2020
Mitteilungen: 222
  Beitrag No.2, vom Themenstarter, eingetragen 2022-05-28

Vielen Dank. Ich denke das hat geholfen: An sich ist mir eingefallen: Aus der linearen Algebra kennt man für A \el\ \IR^(m x n) mit m < n \exists\ z != 0: Az = 0 Ist unser lineare Programm nun lösbar und x eine Lösung, d.h. \IR \contains\ f' := min {c^T x: Ax <=b} und dann f' = c^T x mit Ax <= b. Dann haben wir wegen A(x + z) = Ax + Az = Ax + 0 = Ax <= b einen weiteren zulässigen Punkt x + z für den A(x + z) <= b gilt. Genauer weiß man, dass die Lösung von Az = 0 ein Unterraum ist, d.h. alle x + \lambda z sind auch zulässig. Jetzt komme ich aber leider sofort zum nächsten Problem: Es gilt zwar A(x + z) <= b. x + z ist zulässig. Aber für x + z gilt c^T (x + z) = c^T x + c^T z = f' + c^T z Also x + z muss ja nicht unser Minimum so wie die Lösung x realisieren.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3759
  Beitrag No.3, eingetragen 2022-05-28

\quoteon(2022-05-28 00:06 - JamesNguyen in Beitrag No. 2) Also x + z muss ja nicht unser Minimum so wie die Lösung x realisieren. \quoteoff Es sind zwei Fälle zu unterscheiden: 1. Wenn $c^Tz=0$ ist, kann es ein Minimum geben, das ist aber nicht eindeutig. 2. Wenn $c^Tz\ne0$ ist, ist die Zielfunktion unbeschränkt.


   Profil
JamesNguyen
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 08.11.2020
Mitteilungen: 222
  Beitrag No.4, vom Themenstarter, eingetragen 2022-05-28

achso, supi. Danke, ich glaube ich habe es verstanden.


   Profil
JamesNguyen hat die Antworten auf ihre/seine Frage gesehen.
JamesNguyen hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]