Optimale Basislösung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine zulässige Basislösung eines linearen Programms kann optimal sein, ohne dass [mm] \overline{c}_j \ge [/mm] 0 für alle j=1,...,n.
[mm] (\overline{c}_j [/mm] sind die reduzierten Kosten) |
Hallo zusammen,
meine Frage ist, ob mir jemand erklären kann, wieso obige Behauptung gilt... Ich habe bisher immer angenommen, dass die Lösung nur dann optimal sein kann, wenn die reduzierten Kosten negativ sind.
Ich hoffe mir kann jemand weiterhelfen.
Vielen Dank schonmal im Voraus.
Gruß Michael
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:04 Fr 06.11.2009 | | Autor: | koepper |
Hallo Michael,
> Eine zulässige Basislösung eines linearen Programms kann
> optimal sein, ohne dass [mm]\overline{c}_j \ge[/mm] 0 für alle
> j=1,...,n.
> [mm](\overline{c}_j[/mm] sind die reduzierten Kosten)
das kann nur passieren, wenn du dich in einem entarteten Punkt befindest. Dort hast du zwar möglicherweise noch negative reduzierte Kosten zu irgendeiner Spalte (Variable). Wenn du diese Spalte jedoch in die Basis aufnimmst bekommt sie den Koeffizienten 0. Damit ändert sich zwar die Basis, nicht jedoch der Zielfunktionswert. Du führst de facto also eine oder mehrere Iterationen aus, die zwar die Basis, nicht jedoch den Zielfunktionswert verändern. Irgendwann (wenn du dich nicht im Kreise drehst -- aber das ist so ein Thema für sich...) kommst du dann zu einer optimalen Basislösung, in der keine Spalte mehr negative reduzierte Kosten hat. So eine Basislösung gibt es immer. Das ist garantiert.
LG
Will
|
|
|
| |
|
Vielen Dank für Deine Hilfe,
ich hab ein Beispiel gefunden, bei dem genau das passiert.
Gruß Michael
|
|
|
|
