Opti:Min.problem:lösbar,unlösb < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:26 Do 12.04.2018 | | Autor: | Noya |
| Aufgabe | Für welche $c [mm] \in \IR^2$ [/mm] ist
$min [mm] \{c^T*x : x_1 + x_2 \le 3 , x_1 \le 2\}$
[/mm]
lösbar, eindeutig lösbar, unlösbar? |
Hallo ihr Lieben,
wir haben das Minimierungsproblem gegeben :
$min [mm] \{c_1*x_1+c_2*x_2 : x_1 + x_2 \le 3 , x_1 \le 2\}$
[/mm]
aus den beiden Nebenbedingungen ergibt sich nur ein Schnittpunkt bei (2,1).
lösungsbereich ist beschränkt durch [mm] x_1 \le [/mm] 2 und [mm] x_1+x_2 \le [/mm] 3 ( [mm] x_2 \le 3-x_1, [/mm] also Steigung m =-1)
die Zielfunktion (ZF) ist ja [mm] c_1*x_1+c_2*x_2=z \gdw x_2= \bruch{z}{c_2}-\bruch{c_1}{c_2}*x_1
[/mm]
so. Optimalpunkt muss Ecke sein : dementsprechen kann nur (2,1) optimal sein.
unendlich viele Lsg:
wenn ZF parallel zu einer NB so gibt es unendlich viele Lösungen. Heißt die Steigung dieser beiden Gerade muss gleich sein.
würde hier bedeuten :
ZF [mm] :x_2= \bruch{z}{c_2}-\bruch{c_1}{c_2}*x_1
[/mm]
NB1 : [mm] x_2 \le 3-x_1
[/mm]
also wenn [mm] m=\bruch{c_1}{c_2}=1 \gdw c_1=c_2
[/mm]
NB2 [mm] x_1 \le [/mm] 2 ist ja in dem Sinne keine Fkt und hat keine Steigung
unlösbar:
Wann existiert keine Lösung?
eindeutig lösbar :
Wann existiert eine eindeutige Lösung?
es wäre super wenn ihr mir dazu ein paar Ideen liefern könntet und mir somit helft.
Liebe Grüße
Noya
|
|
| |
|
Hiho,
die Aufgabe lässt sich mit recht trivialen Überlegungen lösen.
Eine Anmerkung zu deinem Ansatz:
> die Zielfunktion (ZF) ist ja [mm]c_1*x_1+c_2*x_2=z \gdw x_2= \bruch{z}{c_2}-\bruch{c_1}{c_2}*x_1[/mm]
man sollte sich immer überlegen, ob die Operationen, die man macht, überhaupt funktionieren. Nirgends ist angegeben, dass [mm] $c_1$ [/mm] oder [mm] c_2 [/mm] ungleich Null sein müssen… und schon machst du hier eine unerlaubte Operation.
Nun zum "trivialen" Ansatz.
Überlege dir folgende Fälle:
1.) [mm] $c_1 [/mm] > 0 [mm] \vee c_2 [/mm] > 0$
2.) [mm] $c_1 [/mm] = [mm] c_2 [/mm] = 0$
3.) sonst
Bei allen Fällen ergibt sich die Lösung relativ leicht, zur Kontrolle
1.) Keine Lösung
2.) Lösung nicht eindeutig
3.) Lösung nicht eindeutig
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:17 Fr 13.04.2018 | | Autor: | Noya |
> und schon machst du hier eine unerlaubte Operation.
Stimmt....
>
> Nun zum "trivialen" Ansatz.
>
> Überlege dir folgende Fälle:
>
> 1.) [mm]c_1 > 0 \vee c_2 > 0[/mm]
> 2.) [mm]c_1 = c_2 = 0[/mm]
> 3.) sonst
>
> Bei allen Fällen ergibt sich die Lösung relativ leicht,
Nö irgendwie nicht so...
habe versucht jetzt alle möglichen Fällen zubetrachten...
[mm] c_1 x_1 [/mm] + [mm] c_2 x_2 [/mm] =z
1.Fall [mm] c_1=0 [/mm] und
1.1: [mm] c_2 [/mm] <0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}
[/mm]
1.2: [mm] c_2 [/mm] >0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}
[/mm]
1.3: [mm] c_2 [/mm] =0 [mm] \Rightarrow [/mm] 0=z
2.Fall [mm] c_1 [/mm] >0
1.Fall [mm] c_1=0 [/mm] und
2.1: [mm] c_2 [/mm] <0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}-\bruch{c_1}{c_2}x_1
[/mm]
2.2: [mm] c_2 [/mm] >0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}-\bruch{c_1}{c_2}x_1
[/mm]
2.3: [mm] c_2 [/mm] =0 [mm] \Rightarrow x_1= \bruch{z}{c_1}
[/mm]
3.Fall [mm] c_1<0 [/mm] und
3.1: [mm] c_2 [/mm] <0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}-\bruch{c_1}{c_2}x_1
[/mm]
3.2: [mm] c_2 [/mm] >0 [mm] \Rightarrow x_2 [/mm] = [mm] \bruch{z}{c_2}-\bruch{c_1}{c_2}x_1
[/mm]
3.3: [mm] c_2 [/mm] =0 [mm] \Rightarrow x_1=\bruch{z}{c_1}
[/mm]
jetzt müsste ich ja rein theoretisch noch zu testen was bei welchem z passiert oder? irgendwie ralle ich das nicht so...
> zur Kontrolle
>
> 1.) Keine Lösung
> 2.) Lösung nicht eindeutig
> 3.) Lösung nicht eindeutig
>
> Gruß,
> Gono
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:10 Di 17.04.2018 | | Autor: | meili |
Hallo Noya,
> > und schon machst du hier eine unerlaubte Operation.
> Stimmt....
> >
> > Nun zum "trivialen" Ansatz.
> >
> > Überlege dir folgende Fälle:
> >
> > 1.) [mm]c_1 > 0 \vee c_2 > 0[/mm]
> > 2.) [mm]c_1 = c_2 = 0[/mm]
> > 3.)
> sonst
> >
> > Bei allen Fällen ergibt sich die Lösung relativ leicht,
> Nö irgendwie nicht so...
> habe versucht jetzt alle möglichen Fällen
> zubetrachten...
> [mm]c_1 x_1[/mm] + [mm]c_2 x_2[/mm] =z
> 1.Fall [mm]c_1=0[/mm] und
> 1.1: [mm]c_2[/mm] <0 [mm]\Rightarrow x_2[/mm] = [mm]\bruch{z}{c_2}[/mm]
> 1.2: [mm]c_2[/mm] >0 [mm]\Rightarrow x_2[/mm] = [mm]\bruch{z}{c_2}[/mm]
> 1.3: [mm]c_2[/mm] =0 [mm]\Rightarrow[/mm] 0=z
>
> 2.Fall [mm]c_1[/mm] >0
> 1.Fall [mm]c_1=0[/mm] und
> 2.1: [mm]c_2[/mm] <0 [mm]\Rightarrow x_2[/mm] =
> [mm]\bruch{z}{c_2}-\bruch{c_1}{c_2}x_1[/mm]
> 2.2: [mm]c_2[/mm] >0 [mm]\Rightarrow x_2[/mm] =
> [mm]\bruch{z}{c_2}-\bruch{c_1}{c_2}x_1[/mm]
> 2.3: [mm]c_2[/mm] =0 [mm]\Rightarrow x_1= \bruch{z}{c_1}[/mm]
>
> 3.Fall [mm]c_1<0[/mm] und
> 3.1: [mm]c_2[/mm] <0 [mm]\Rightarrow x_2[/mm] =
> [mm]\bruch{z}{c_2}-\bruch{c_1}{c_2}x_1[/mm]
> 3.2: [mm]c_2[/mm] >0 [mm]\Rightarrow x_2[/mm] =
> [mm]\bruch{z}{c_2}-\bruch{c_1}{c_2}x_1[/mm]
> 3.3: [mm]c_2[/mm] =0 [mm]\Rightarrow x_1=\bruch{z}{c_1}[/mm]
>
> jetzt müsste ich ja rein theoretisch noch zu testen was
> bei welchem z passiert oder? irgendwie ralle ich das nicht
> so...
So wie ich die Aufgabe verstanden habe, soll $z$ minimiert werden, für
[mm] $x_1$, $x_2$ [/mm] entsprechend den Nebenbedingungen. Und die Frage
ist, wie hängt es von den [mm] $c_1$, $c_2$ [/mm] ab, ob es überhaupt eine
Lösung (also ein Minumum von $z$) gibt, ob es eine Lösung oder
eine eindeutige Lösung gibt.
Da alle [mm] $x_1 [/mm] < 0$ und [mm] $x_2 [/mm] < 0$ die Nebenbedingungen erfüllen,
gibt es für [mm] $c_1 [/mm] > 0$ und [mm] $c_2 [/mm] > 0$ kein Minimunm von $z$.
Für [mm] $c_1 [/mm] = 0$ und [mm] $c_2 [/mm] = 0$ ist $z = 0$ für alle [mm] $(x_1, x_2)$.
[/mm]
Welche Werte kann $z$ annehmen für [mm] $c_1 [/mm] < 0$ und [mm] $c_2 [/mm] < 0$ ?
Für [mm] $c_1 [/mm] < 0$ und [mm] $c_2 [/mm] < 0$ und [mm] $c_1 [/mm] = [mm] c_2$ [/mm] und [mm] $x_2 [/mm] = - [mm] x_1 [/mm] +3$
ist $z = [mm] -3|c_2|$.
[/mm]
>
> > zur Kontrolle
> >
> > 1.) Keine Lösung
> > 2.) Lösung nicht eindeutig
> > 3.) Lösung nicht eindeutig
> >
> > Gruß,
> > Gono
>
Gruß
meili
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:38 Di 17.04.2018 | | Autor: | Gonozal_IX |
Hallo meili,
danke fürs Einspringen… ich kam noch nicht dazu zu antworten. Ich muss mich übrigens korrigieren beim dritten Fall. Dort gibt es auch nicht immer eine Lösung, bspw. für [mm] $c_2 [/mm] > [mm] c_1$
[/mm]
Gruß,
Gono
|
|
|
|
