Frage zum Dualitätssatz < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Hallo,
ich habe eine Minimierungsaufgabe (Ursprungsproblem) folgender Art:
In verschiedenen Nahrungsmitteln stecken pro Mengeneinheit verschiedene Mengen unterschiedlicher Vitamine. Ich muss mindenstens ... Mengen Vitamine der jeweiligen Sorten aufnehmen, will aber die Kosten für die dafür notwendigen Nahrungsmittel minimieren.
Ich habe dieses Problem in ein Maximierungsproblem (Äquivalenzproblem) umgeformt und mit dem Simplex-Verfahren gelöst. Dann muss man ja die Schlupfvariablen der Lösung betrachten. Diese sind alle null oder negativ. Wenn man von diesen Schlupfvariablen das Vorzeichen umkehrt, so hat man die Lösungen des Ausgangsproblems. |
Meine Fragen sind nun:
1.) Ist es immer so, dass man die Vorzeichen umkehren muss? Oder könnte es auch mal eine andere Umrechnungsvorschrift geben um von der Lösung des Äquivalenzproblems auf die Lösung des Ursprungsproblems zu kommen?
2.) Warum erhält man auf diese Art überhaupt die Lösung? Also wie kann man erklären, dass die Lösung des Ursprungsproblems in den vorzeichenverkehrten Schlupfvariablen des Äquivalenzproblems steht?
Vielen Dank für Eure Hilfe! Ich habe diese Frage nirgendwo sonst gestellt.
PS: Falls jemand einen guten Link kennt, z.B. zu einer Facharbeit über das Simplex-Verfahren oder über eine andere einfache Darstellung wäre ich sehr dankbar. Auch den Beweis des Simplex-Verfahrens oder des Dualitätssatzes würde ich gerne mal sehen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mo 25.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
