Polyeder nicht leer? < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Untersuche, ob folgender Polyeder nicht leer ist!
A:=
{ x [mm] \in \IR^4 [/mm] | [mm] 2x_1 -4x_2 +x_3 [/mm] = -7
[mm] x_1 +2x_2 +x_4 [/mm] = 3
[mm] x_i \ge [/mm] 0 , i = 1,2,3,4 } |
Huhu
Meine Vorüberlegungen sind, dass ich ja sozusagen eine Funktion [mm] \IR^4 \to \IR^2 [/mm] betrachte. Man könnte die Koeffizienten der gleichungssysteme als Matrix schreiben zu.
M := [mm] \pmat{ 2 & -4 & 1 & 0 \\ 1 & 2 & 0 & 1 } [/mm] und b = [mm] \vektor{-7 \\ 3}
[/mm]
zu finden ist also ein x [mm] \in \IR^4 [/mm] , komponentenweise alle größer gleich 0 der obige Gleichung erfüllt ( oder zeigen, dass es keinen solchen Vektor gibt)
Allerdings weiß ich hier nicht weiter. Betrachte ich M bestehen aus 4 Spaltenvektoren (oder muss ich 2 Zeilenvektoren [mm] \in \IR^4 [/mm] betrachten ?), so ergibt sich, dass ich 2 der 4 Vektoren rausschmeissen kann und eine Basis habe mit den kanonischen Basisvektoren [mm] \vektor{1 \\ 0} \vektor{0 \\ 1} [/mm] . Wie gehe ich nun weiter vor?
Lg,
Eve
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:56 Sa 20.04.2013 | | Autor: | fred97 |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> Untersuche, ob folgender Polyeder nicht leer ist!
>
> A:=
>
> { x [mm]\in \IR^4[/mm] | [mm]2x_1 -4x_2 +x_3[/mm] = -7
> [mm]x_1 +2x_2 +x_4[/mm] = 3
> [mm]x_i \ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
0 , i = 1,2,3,4 }
> Huhu
>
> Meine Vorüberlegungen sind, dass ich ja sozusagen eine
> Funktion [mm]\IR^4 \to \IR^2[/mm] betrachte. Man könnte die
> Koeffizienten der gleichungssysteme als Matrix schreiben
> zu.
>
> M := [mm]\pmat{ 2 & -4 & 1 & 0 \\ 1 & 2 & 0 & 1 }[/mm] und b =
> [mm]\vektor{-7 \\ 3}[/mm]
>
> zu finden ist also ein x [mm]\in \IR^4[/mm] , komponentenweise alle
> größer gleich 0 der obige Gleichung erfüllt ( oder
> zeigen, dass es keinen solchen Vektor gibt)
>
> Allerdings weiß ich hier nicht weiter. Betrachte ich M
> bestehen aus 4 Spaltenvektoren (oder muss ich 2
> Zeilenvektoren [mm]\in \IR^4[/mm] betrachten ?), so ergibt sich,
> dass ich 2 der 4 Vektoren rausschmeissen kann und eine
> Basis habe mit den kanonischen Basisvektoren [mm]\vektor{1 \\ 0} \vektor{0 \\ 1}[/mm]
> . Wie gehe ich nun weiter vor?
>
>
> Lg,
>
> Eve
Bestimme die Lösungsmenge des LGS
$ [mm] 2x_1 -4x_2 +x_3 [/mm] $ = -7
$ [mm] x_1 +2x_2 +x_4 [/mm] $ = 3
und schau nach, ob es Lösungen [mm] (x_1,...,x_4) [/mm] gibt mit [mm] x_i\ge [/mm] 0 für i=1,2,3,4
fred
|
|
|
| |
|
>
> Bestimme die Lösungsmenge des LGS
>
> [mm]2x_1 -4x_2 +x_3[/mm] = -7
> [mm]x_1 +2x_2 +x_4[/mm] = 3
>
>
> und schau nach, ob es Lösungen [mm](x_1,...,x_4)[/mm] gibt mit
> [mm]x_i\ge[/mm] 0 für i=1,2,3,4
>
> fred
Also an für sich gibt es denke ich keine Lösung, da rang(M) = rang(M|b) [mm] \not= [/mm] rang(max) ist. Aber wie kann ich das problem mathematisch korrekt formulieren und zeigen, dass es wirklich keinen Vektor gibt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:42 Sa 20.04.2013 | | Autor: | fred97 |
> >
> > Bestimme die Lösungsmenge des LGS
> >
> > [mm]2x_1 -4x_2 +x_3[/mm] = -7
> > [mm]x_1 +2x_2 +x_4[/mm] = 3
> >
> >
> > und schau nach, ob es Lösungen [mm](x_1,...,x_4)[/mm] gibt mit
> > [mm]x_i\ge[/mm] 0 für i=1,2,3,4
> >
> > fred
>
> Also an für sich gibt es denke ich keine Lösung, da
> rang(M) = rang(M|b) [mm]\not=[/mm] rang(max) ist
Was bedeutet rang(max) ???
Das Lgs ist lösbar !!!
FRED
> . Aber wie kann ich
> das problem mathematisch korrekt formulieren und zeigen,
> dass es wirklich keinen Vektor gibt?
>
|
|
|
| |
|
> > >
> > > Bestimme die Lösungsmenge des LGS
> > >
> > > [mm]2x_1 -4x_2 +x_3[/mm] = -7
> > > [mm]x_1 +2x_2 +x_4[/mm] = 3
> > >
> > >
> > > und schau nach, ob es Lösungen [mm](x_1,...,x_4)[/mm] gibt mit
> > > [mm]x_i\ge[/mm] 0 für i=1,2,3,4
> > >
> > > fred
> >
> > Also an für sich gibt es denke ich keine Lösung, da
> > rang(M) = rang(M|b) [mm]\not=[/mm] rang(max) ist
>
> Was bedeutet rang(max) ???
sry meinte den größtmöglichen Rang.
> Das Lgs ist lösbar !!!
>
>
> FRED
M = [mm] \pmat{ 2 & -4 & 1 & 0 \\ 1 & 2 & 0 & 1 } [/mm] b = [mm] \vektor{-7 \\ 3}
[/mm]
Also b ist eine negative Linearkombination der linearen Hülle von den Spaltenvektoren M. Also gibt es eine Hyperebene {x [mm] \in \IR^4 [/mm] : [mm] c^T [/mm] * x = 0}, die t-1 linear unabhängige Vektoren aus den Spaltenvektoren von M enthält. ( In dem Fall also bei 2 lin. unabh. Vektoren -> Hyperebene [mm] \in \IR [/mm] )
Es gilt einerseits [mm] c^T [/mm] b < 0 und [mm] c^T m_1 \ge [/mm] 0 ,......, [mm] c^T m_4 \ge [/mm] 0.
t sei [mm] rang(m_1,....,m_4,b) [/mm] = 2
Soviel verstehe ich.
Jetzt nehme ich mir eine linear unabh. Teilmenge raus aus M, nennen wir sie mal D:= ( [mm] \vektor{1 \\ 0} [/mm] , [mm] \vektor{0 \\ 1} [/mm] )
b ist dann gleich [mm] \lambda_1 [/mm] * [mm] \vektor{1 \\ 0} \lambda_2 [/mm] * [mm] \vektor{0 \\ 1}
[/mm]
, wobei [mm] \lambda_1 [/mm] = -7 und [mm] \lambda_2 [/mm] = 3.
(daher negative Linearkombination)
Jetzt wähl ich den kleinsten Index / die kleinste Indexmenge h der negativen [mm] \lambda, [/mm] in dem Fall [mm] \lambda_1 [/mm] . (h=1)
Sei nun {x : [mm] c^T [/mm] x = 0} die von D \ [mm] {m_h} [/mm] aufgespannte Hyperebene.
Also von [mm] \vektor{0 \\ 1}
[/mm]
Normiere c sodass [mm] c^T [/mm] * [mm] m_h [/mm] = 1 (nicht nötig da [mm] m_h [/mm] kanon. Standardvektor)
An der STelle weiß ich nicht weiter, ob ich dieses Verfahren nochmal anwenden muss, da [mm] c^T [/mm] * [mm] m_2 [/mm] < 0 ist
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:18 Sa 20.04.2013 | | Autor: | fred97 |
Mein Gott, was machst Du da für Sachen ?
Löse das LGS ! Schreib die Lösungsmenge hin !
Schau nach ob es Lösungsvektoren mit Einträgen [mm] \ge [/mm] 0 gibt !
Mach das doch mal !
FRED
|
|
|
| |
|
> Mein Gott, was machst Du da für Sachen ?
Das ist die Art, auf die wir es theoretisch machen sollen bzw ich will verstehen, wie das auf die Weise funktioniert. Weißt du , wie ich es so machen kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:38 Sa 20.04.2013 | | Autor: | fred97 |
> > Mein Gott, was machst Du da für Sachen ?
>
>
> Das ist die Art, auf die wir es theoretisch machen sollen
> bzw ich will verstehen, wie das auf die Weise funktioniert.
> Weißt du , wie ich es so machen kann?
Ich hab keine Ahnung, wie Du das machen sollst !
Aber es geht viel einfacher, als ich zunächst vorgeschlgen habe:
Nimm an, es gibt [mm] x_1,...,x_4 \ge [/mm] 0 mit
$ [mm] 2x_1 -4x_2 +x_3 [/mm] $ = -7
$ [mm] x_1 +2x_2 +x_4 [/mm] =3$
Aus der ersten Gl. bekommen wir:
[mm] 4x_2-7 =2x_1+x_3 \ge [/mm] 0, also [mm] x_2 \ge [/mm] 7/4.
Mit der 2. Gl. ergibt das
$ [mm] 3=x_1 +2x_2 +x_4 \ge x_1+x_4+ [/mm] 7/2 [mm] \ge [/mm] 7/2=3,5$
Widerspruch !
FRED
|
|
|
| |
|
Fred
Nimm an, es gibt $ [mm] x_1,...,x_4 \ge [/mm] $ 0 mit
$ [mm] 2x_1 -4x_2 +x_3 [/mm] $ = -7
$ [mm] x_1 +2x_2 +x_4 [/mm] =3 $
Aus der ersten Gl. bekommen wir:
$ [mm] 4x_2-7 =2x_1+x_3 \ge [/mm] $ 0, also $ [mm] x_2 \ge [/mm] $ 7/4.
Mit der 2. Gl. ergibt das
$ [mm] 3=x_1 +2x_2 +x_4 \ge x_1+x_4+ [/mm] 7/2 [mm] \ge [/mm] 7/2=3,5 $
Widerspruch !
FRED
-> Vielen lieben Dank für die Lösung!
Ich möchte diese Frage trotzdem für eventuelle Optimierungsstudenten öffnen, denen dieses Verfahren vielleicht bekannt vorkommt:
M = [mm]\pmat{ 2 & -4 & 1 & 0 \\ 1 & 2 & 0 & 1 }[/mm] b = [mm]\vektor{-7 \\ 3}[/mm]
Also b ist eine negative Linearkombination der linearen
Hülle von den Spaltenvektoren M. Also gibt es eine
Hyperebene [ x [mm]\in \IR^4[/mm] : [mm]c^T[/mm] * x = 0 ] , die t-1 linear
unabhängige Vektoren aus den Spaltenvektoren von M
enthält. ( In dem Fall also bei 2 lin. unabh. Vektoren ->
Hyperebene [mm]\in \IR[/mm] )
Es gilt einerseits [mm]c^T[/mm] b < 0 und [mm]c^T m_1 \ge[/mm] 0 ,.....,
[mm]c^T m_4 \ge[/mm] 0.
t sei [mm]rang(m_1,....,m_4,b)[/mm] = 2
Soviel verstehe ich.
jetzt nehme ich mir eine linear unabh. Teilmenge raus aus
M, nennen wir sie mal D:= ( [mm]\vektor{1 \\ 0}[/mm] , [mm]\vektor{0 \\ 1}[/mm]
)
b ist dann gleich [mm]\lambda_1[/mm] * [mm]\vektor{1 \\ 0} \lambda_2[/mm] *
[mm]\vektor{0 \\ 1}[/mm], wobei [mm]\lambda_1[/mm] = -7 und [mm]\lambda_2[/mm] = 3.
(daher negative Linearkombination)
Jetzt wähl ich den kleinsten Index / die kleinste
Indexmenge h der negativen [mm]\lambda,[/mm] in dem Fall [mm]\lambda_1[/mm] .
(h=1)
Sei nun [ x : [mm]c^T[/mm] x = 0] die von D \ [mm]{m_h}[/mm] aufgespannte
Hyperebene.
Also von [mm]\vektor{0 \\ 1}[/mm]
Normiere c sodass [mm]c^T[/mm] * [mm]m_h[/mm] = 1 (nicht nötig da [mm]m_h[/mm] kanon.
Standardvektor)
An der STelle weiß ich nicht weiter, ob ich dieses
Verfahren nochmal anwenden muss, da [mm]c^T[/mm] * [mm]m_2[/mm] < 0 ist
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mo 22.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
