Nachbarecken bestimmen! < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:29 Fr 09.05.2008 | | Autor: | Bex |
| Aufgabe | Ein Polytop sei durch die folgenden Ungleichungen gegeben:
[mm] x_{1}+x_{2}+x_{3}+x_{4}\le [/mm] 6
[mm] 2*x_{1}+2*x_{2}+x_{3}+x_{4}\le [/mm] 8
[mm] x_{1}+x_{2}+3*x_{3}+x_{4}\le [/mm] 9
[mm] x_{1},x_{2},x_{3},x_{4}\ge [/mm] 0
Bestimmen Sie von den Ecken [mm] (0,0,0,0)^T, (4,0,0,0)^T [/mm] und [mm] (2,0,0,4)^T [/mm] jeweils alle Nachbarecken! (Zwei Ecken heißen benachbart, wenn die eine Ecke aus der anderen durch einen Eckenübergang hervorgeht.)
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Mein Problem ist nun, dass ich ab einer bestimmten Stelle nicht mehr weiterkomme.
Ich weiß das ich erst schauen muss, wann die o.g. Gleichungen = sind. Das sind bei der ersten Ecke nur die letzten, sprich: [mm] x_{1}= [/mm] 0, [mm] x_{2}= [/mm] 0, [mm] x_{3}= [/mm] 0, [mm] x_{4}= [/mm] 0
Dann muss ich diese Gleichungen transformieren (also zu jedem x ein y finden); das sind hier: [mm] y_{1}=x_{1} [/mm] , [mm] y_{2}=x_{2} [/mm] , [mm] y_{3}=x_{3} [/mm] , [mm] y_{4}=x_{4}
[/mm]
Und ab da häng ich wieder. Bitte helft mir wie ich weiter vorgehen muss.
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:23 Sa 10.05.2008 | | Autor: | koepper |
Hallo,
es ist übersichtlicher, wenn du zuerst das Ungleichungssystem durch Hinzufügen von Schlupfvariablen in ein Gleichungssystem überführst. Zu jeder Ecke des Polytops gehört dann eine sogenannte Basis. Das ist eine Menge von (hier 3) Spalten, deren zugehörige Variablen ungleich Null sein dürfen. Alle anderen Variablen sind dann Null. Benachbarte Ecken findest du dann einfach, indem du eine Spalte der Basis gegen eine (zunächst beliebige) andere austauscht. Dann mußt du aber noch für die zugehörige Lösung die Nichtnegativitätsbedingung überprüfen. Wenn die erfüllt ist, ist diese Basis zulässig und du hast eine Nachbarecke gefunden.
Beispiel: Zur (0,0,0,0) Ecke gehöt die Basis bestehend nur aus den 3 Spalten mit den Schlupfvariablen.
LG
Will
|
|
|
|
