lineare Optimierung < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:59 Di 18.09.2007 | | Autor: | Cutie |
| Aufgabe | Lösen Sie die LP Relaxtion des folgenden Problems:
max 16x1 + 19x2 + 31x3 + 31x4
bzgl. 2x1 + 3x2 + 4x3 + 5x4 < 7,
x nichtnegativ und ganzzahlig
b) Führen sie einen Schritt des Gomory Verfahren und notieren sie das das LP Problem mit der neuen Gleichung auch n der zugehörigen Normalform. Hat dieses neue LP problem nun eine optimale Lösung, die ganzzahlig ist?
|
Kann mir jemand helfen. Ich komme mit dieser Aufgabe nicht weiter. Danke schon mal im voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:02 Mi 19.09.2007 | | Autor: | koepper |
Hallo melli,
LP-Relaxation heißt: Ganzahligkeitsbedingung weglassen.
Stelle dann das Simplex-Tableau auf. Du kannst im ersten Pivotschritt im Prinzip jede der Variablen in die Basis aufnehmen, aber ich empfehle, [mm] x_1 [/mm] aufzunehmen. Das Tableau ist dann nach dem ersten Schritt direkt optimal.
Es lautet:
[mm] \begin{tabular}{ccccc|c}
1 & 1.5 & 2 & 2.5 & 0.5 & 3.5 \\ \hline
0 & -5 & -1 & -9 & -8 & -56
\end{tabular}
[/mm]
Den Gomory-Schnitt bekommst du dann aus den fraktionalen Anteilen der ersten (Restriktions-) Zeile. Er lautet
0.5 [mm] x_2 [/mm] + 0.5 [mm] x_4 [/mm] + 0.5 [mm] x_5 \geq [/mm] 0.5
Den fügst du (am besten mit 2 multipliziert) in das Tableau ein. Das Tableau wird dadurch unzulässig und du reoptimierst dann mit dem dualen Simplex-Verfahren... aber alles vorlösen wollte ich jetzt nicht.
Ich hoffe, der Start hilft dir...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:13 Mi 19.09.2007 | | Autor: | Cutie |
danke für die anwort, ich habe es trotzdem nicht verstanden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:06 Do 20.09.2007 | | Autor: | koepper |
Hallo mellie, wenn du etwas präziser erklärst, was genau du nicht verstanden kannst, könnte ich dir ggf. weitere Hinweise geben.
|
|
|
|
