| |
| Autor |
 Lineare Programme: Entfernen einer inaktiven Nebenbedingung ändert Optimallösung nicht. |
|
Schachspieler
Junior 
Dabei seit: 01.06.2018
Mitteilungen: 7
 |  Themenstart: 2021-12-28
|
Hallo,
ich habe folgendes Problem zu lösen:
Sei ein Lineares Programm gegeben (Maximierungsproblem, muss nicht ganzzahlig sein). Sei x* eine Optimallösung des LP. Sei ax<=b eine Nebenbedingung, die in x* nicht aktiv ist, also nicht mit Gleichheit erfüllt ist. Zeige nun, dass sich die Optimallösung nicht ändert, wenn man diese Nebenbedingung entfernt.
Meine Ideen: Dass die Optimallösung nicht kleiner wird, wenn man die NB entfernt ist klar. Aber wie zeigt man, dass sie nicht größer werden kann? Meine Überlegung war, dass wenn man annimmt, die "neue" Optimallösung liegt nun in dem Teil, der durch den Wegfall der NB nun zulässig ist, dass daraus folgen würde, dass die "alte" Optimallösung dann an einer Ecke liegt, die an diesen Teil "angrenzt", aber ich weiß nicht, wie man das zeigt. Wie komme ich da weiter?
|
 Profil
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 2248
 | Beitrag No.1, eingetragen 2021-12-29
|
Hallo Schachspieler!
Ich kenne das so:
die Lösungen von linearen Optimierungsproblemen finden sich auf Ecken des Lösungsbereichs. Sie können auch auf einer Kante oder Fläche des Lösungsbereichs zu finden sein.
Ganzzahligkeit wäre für die Berechenbarkeit eher ein Nachteil - dadurch wird das Problem meist schwerer.
Viele Grüße
Ronald
|
Profil
|
Schachspieler
Junior
Dabei seit: 01.06.2018
Mitteilungen: 7
| Beitrag No.2, vom Themenstarter, eingetragen 2021-12-29
|
Hallo Ronald,
vielen Dank für die schnelle Antwort.
Dass eine optimale Lösung an einer Ecke und/oder Kante liegt, ist mir bewusst. Meine Frage geht in die Richtung:
Wenn ich jetzt eine Lösung gefunden habe, die an einer Ecke liegt und optimal ist, und dann eine Nebenbedingung entferne, die an dieser Ecke nicht mit Gleichheit erfüllt ist (also inaktiv ist), dann bleißt die Optimallösung an der gleichen Ecke. Vorstelen kann ich mir das schon, aber wie zeigt man das?
|
Profil
|
Goswin
Senior 
Dabei seit: 18.09.2008
Mitteilungen: 1787
Wohnort: Chile, Ulm
 | Beitrag No.3, eingetragen 2021-12-29
|
\quoteon(2021-12-28 08:05 - Schachspieler im Themenstart)
Dass die Optimallösung nicht kleiner wird, wenn man die NB entfernt ist klar. Aber wie zeigt man, dass sie nicht größer werden kann?
\quoteoff
Falls eine neue Opimallösung \(x^\prime\!\ne\!x^*\) mit streng größerem Zielfunktionswert als \(x^*\) existiert, dann würde sie natürlich auch keine der aktiven Nebenbedingungen verletzen. Aber dann würde innerhalb der Strecke zwischen beiden Lösungen, also in
\[
\{ \lambda x^* + (1-\lambda) x^\prime ~:~ 0<\lambda<1 \}
\]
ein Punkt existieren, der sämtliche Nebenbedingungen erfüllt und einen streng größeren Zielfunktionswert als \(x^*\) hat.
(Das musst du natürlich etwas genauer begründen)
|
Profil
|
| Schachspieler hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
