Fourier-Motzkin < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Benutzen Sie den Algorithmus von Fourier-Motzkin, um folgendes Ungleichungssytem zu lösen
2x+y-z [mm] \le [/mm] 9
x-2y-4z [mm] \le [/mm] 4
-x+z [mm] \le1
[/mm]
y-3z [mm] \le [/mm] 7
-3x+2y+z [mm] \le [/mm] 3 |
Hallo zusammen,
ich bearbeite grade diese Aufgabe aber hab noch paar probleme damit da wir diesen Algorithmus noch nicht benutzt haben!
(1) 2x+y-z [mm] \le [/mm] 9
(2) x-2y-4z [mm] \le [/mm] 4
(3) -x+z [mm] \le1
[/mm]
(4) y-3z [mm] \le [/mm] 7
(5) -3x+2y+z [mm] \le [/mm] 3
hier gilt I_+= {1,2} I_-={3,5} [mm] I_0={4}
[/mm]
hab das jetzt noch ein bisschen umgestellt
2x+y-z [mm] \le [/mm] 9
x-2y-4z [mm] \le [/mm] 4
-x+z [mm] \le1
[/mm]
-3x+2y+z [mm] \le [/mm] 3
y-3z [mm] \le [/mm] 7
jetzt wollte ich das x eliminieren aber da stellt sich mir schon die erste frage und zwar:
muss ich jetzt jeweils die gleichung mit dem -x mit den positiven gleichungen addieren also quasi (1)+(3) und (2)+(3) sowieso dann noch (5)+(1) und (5)+(2) oder muss ich nur z.b. (1)+(3) und (5)+(2) rechnen?
erhalte ich dann nach der elimination nur noch 3 gleichungen ohne x?
würde mich über ein bisschen hilfe echt freuen!
gruß,
kekschen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:26 Do 28.04.2011 | | Autor: | barsch |
Hallo Kampfkeks,
> Benutzen Sie den Algorithmus von Fourier-Motzkin, um
> folgendes Ungleichungssytem zu lösen
> 2x+y-z [mm]\le[/mm] 9
> x-2y-4z [mm]\le[/mm] 4
> -x+z [mm]\le1[/mm]
> y-3z [mm]\le[/mm] 7
> -3x+2y+z [mm]\le[/mm] 3
> Hallo zusammen,
>
> ich bearbeite grade diese Aufgabe aber hab noch paar
> probleme damit da wir diesen Algorithmus noch nicht benutzt
> haben!
>
>
> (1) 2x+y-z [mm]\le[/mm] 9
> (2) x-2y-4z [mm]\le[/mm] 4
> (3) -x+z [mm]\le1[/mm]
> (4) y-3z [mm]\le[/mm] 7
> (5) -3x+2y+z [mm]\le[/mm] 3
>
> hier gilt [mm]I_+=[/mm] {1,2} [mm]I_{-}[/mm]={3,5} [mm]I_0={4}[/mm]
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> hab das jetzt noch ein bisschen umgestellt
> 2x+y-z [mm]\le[/mm] 9
> x-2y-4z [mm]\le[/mm] 4
> -x+z [mm]\le1[/mm]
> -3x+2y+z [mm]\le[/mm] 3
> y-3z [mm]\le[/mm] 7
Das ist erst die halbe Miete. Du musst erst noch [mm]2x+y-z\le{9}[/mm] durch 2 und [mm]-3x+2y+z \le[/mm] 3 durch 3 teilen. Die Koeffizienten müssen nämlich auf +1 bzw. -1 normiert werden.
Das sieht dann so aus:
[mm](i) \ \ x+\bruch{1}{2}y-\bruch{1}{2}z \le 4,5[/mm]
[mm](ii) \ \ \ \ \ x-2y-4z \le 4[/mm]
[mm](iii) \ \ \ -x \ \ \\
\ \ +z \le 1[/mm]
[mm](iv)-x+\bruch{2}{3}y+\bruch{1}{3}z\le{1}[/mm]
[mm](v) \ \ y-3z \le 7[/mm]
Nun erhälst du aus jedem Paar, bestehend aus einer Ungleichung mit positivem Koeffizient [mm]I_+[/mm] und einer Ungleichung mit negativen Koeffizient [mm]I_-[/mm] eine neue gültige Ungleichung. Das heißt, du musst [mm](i)[/mm] mit [mm](iii)[/mm], [mm](ii)[/mm] mit [mm](iii)[/mm], [mm](i)[/mm] mit [mm](iv)[/mm] und [mm](ii)[/mm] mit [mm](iv)[/mm] addieren. Du siehst, jede Menge Arbeit.
> würde mich über ein bisschen hilfe echt freuen!
Gruß
barsch
|
|
|
| |
|
Gut dann hab ichs wohl schonmal richtig verstanden! danke für die antwort!
hab jetzt nachdem ich die gleichungen addiert und somit mein x eliminiert hab, folgende gleichungen raus:
[mm] \bruch{1}{2}y +\bruch{1}{2}z \le \bruch{11}{2}
[/mm]
[mm] \bruch{7}{6}y-\bruch{1}{6}z \le \bruch{11}{2}
[/mm]
-2y-3z [mm] \le [/mm] 5
[mm] \bruch{-4}{3}y-\bruch{11}{3}z \le [/mm] 5
y-3z [mm] \le [/mm] 7
[mm] \bruch{1}{2}y +\bruch{1}{2}z \le \bruch{11}{2} [/mm] (*2)
[mm] \bruch{7}{6}y-\bruch{1}{6}z \le \bruch{11}{2} [/mm] (* [mm] \bruch{6}{7})
[/mm]
y-3z [mm] \le [/mm] 7
-2y-3z [mm] \le [/mm] 5 [mm] (*\bruch{1}{2})
[/mm]
[mm] \bruch{-4}{3}y-\bruch{11}{3}z \le [/mm] 5 [mm] (*\bruch{3}{4})
[/mm]
jetzt Normierung nach y
y+z [mm] \le [/mm] 11
[mm] y-\bruch{1}{7}z \le \bruch{33}{7}
[/mm]
y-3z [mm] \le [/mm] 7
[mm] -y-\bruch{3}{2}z \le [/mm] 5
-y- [mm] \bruch{11}{4}z \le \bruch{15}{4}
[/mm]
jetzt Elimination von y
[mm] \bruch{-1}{2}z \le [/mm] 16
[mm] \bruch{-7}{4}z \le \bruch{59}{4}
[/mm]
[mm] \bruch{-23}{14}z \le \bruch{68}{7}
[/mm]
[mm] \bruch{-81}{28}z \le \bruch{238}{28}
[/mm]
[mm] \bruch{-9}{2}z \le [/mm] 12
[mm] \bruch{-23}{4}z \le \bruch{43}{4}
[/mm]
daraus ergibt sich dann
-z [mm] \le [/mm] 32
[mm] -z\le \bruch{59}{7}
[/mm]
[mm] -z\le \bruch{136}{23}
[/mm]
[mm] -z\le \bruch{79}{27}
[/mm]
[mm] -z\le \bruch{8}{3}
[/mm]
[mm] -z\le \bruch{43}{23}
[/mm]
ist das soweit richtig?
gruß,
kekschen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:36 Fr 29.04.2011 | | Autor: | barsch |
Hallo,
> Gut dann hab ichs wohl schonmal richtig verstanden! danke
> für die antwort!
>
> hab jetzt nachdem ich die gleichungen addiert und somit
> mein x eliminiert hab, folgende gleichungen raus:
>
> [mm]\bruch{1}{2}y +\bruch{1}{2}z \le \bruch{11}{2}[/mm]
>
> [mm]\bruch{7}{6}y-\bruch{1}{6}z \le \bruch{11}{2}[/mm]
> -2y-3z [mm]\le[/mm]5
> [mm]\bruch{-4}{3}y-\bruch{11}{3}z \le[/mm] 5
> y-3z [mm]\le[/mm] 7
setzen wir mal voraus bis hier stimmt es (das habe ich jetzt nicht geprüft!)
>
> [mm]\bruch{1}{2}y +\bruch{1}{2}z \le \bruch{11}{2}[/mm] (*2)
> [mm]\bruch{7}{6}y-\bruch{1}{6}z \le \bruch{11}{2}[/mm] (*[mm]\bruch{6}{7})[/mm]
> y-3z [mm]\le[/mm] 7
> -2y-3z [mm]\le[/mm] 5 [mm](*\bruch{1}{2})[/mm]
> [mm]\bruch{-4}{3}y-\bruch{11}{3}z \le[/mm] 5 [mm](*\bruch{3}{4})[/mm]
Ja.
> jetzt Normierung nach y
>
> y+z [mm]\le[/mm] 11
> [mm]y-\bruch{1}{7}z \le \bruch{33}{7}[/mm]
> y-3z [mm]\le[/mm] 7
> [mm]-y-\bruch{3}{2}z \le[/mm] 5
> -y- [mm]\bruch{11}{4}z \le \bruch{15}{4}[/mm]
wenn ich das richtig sehe, liegt hier ein Fehler!
Kleiner Tipp - das ist echt mühsam zu kontrollieren. Der potentielle Helfer muss ja alles nachrechnen. Und da haben die Wenigsten Lust drauf.  Es geht ja auch erst einmal darum, das Prinzip zu verstehen. Rechenfehler sind schnell gemacht, siehe oben. Rechenfehler sind aber nicht so tragisch, wenn man das Prinzip dahinter verstanden hat.
Gruß
barsch
|
|
|
| |
|
Okay da muss ich dir allerdings Recht geben! Danke, dass du mich auf den Fehler aufmerksam gemacht hast!
hab aber dennoch eine frage!
also nehmen wir mal an, dass das bis dahin richtig wäre wie müsste ich denn jetzt weiter vorfahren!
denn hab ich immer ungleichungen mit -z! darf ich diese ungleichungen denn jetzt einfach mit -1 multiplizieren denn dadurch würde sich ja das ungleichungszeichen umdrehen und ich hätte folgendes raus:
z [mm] \ge [/mm] 27
z [mm] \ge \bruch{59}{7}
[/mm]
z [mm] \ge \bruch{101}{23}
[/mm]
z [mm] \ge \bruch{8}{3}
[/mm]
z [mm] \ge \bruch{43}{23}
[/mm]
wenn das jetzt richtig so wäre dann könnte mein z ja mind [mm] \bruch{43}{23} [/mm] sein..und jetzt wäre meine frage wie ich denn mein z nun wählen muss?
gruß
kekschen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:37 Mo 02.05.2011 | | Autor: | barsch |
Hi,
das [mm] $\geq$ [/mm] irritiert mich auch. Damit jedes $ [mm] \geq$ [/mm] erfüllt ist, muss ja z mindestens den Wert 27 haben. Aber wie damit weiter zu Verfahren ist, weiß ich auch nicht. Evtl. (Vermutung meinerseits) ist z=27 zu setzen und dann über Rückwartsrechnung x und y zu berechnen.
Gruß
|
|
|
|
