zulässiges/ unbeschr. Problem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:44 Do 12.04.2018 | | Autor: | Noya |
| Aufgabe | $ min [mm] \{ x_1+x_2 : ax_1+x_2 \le 4, 1\le x_1 \le 3, 1\le x_2 \le 3 \}
[/mm]
(a) Für welche Werte von a [mm] \in \IR [/mm] ist das Problem unzulässig oder unbeschränkt?
(b) Berechnen Sie Optimalmenge und Optimalwert in Abhängigkeit von a. |
Hallo ihr Lieben,
ich komme nicht so recht hier voran.
Meine Lösungsmenge ist ja das Quadrat mit den EP (1,1),(1,3),(3,3),(3,1) und darein muss dann noch die Resktriktion : [mm] a*x_1 [/mm] + [mm] x_2 \le [/mm] 4
[mm] \gdw x_2 \le 4-a*x_1
[/mm]
betrachte ich für [mm] 1\le x_1 \le [/mm] 3 fktwerte von [mm] x_2 [/mm]
für [mm] x_1=1 [/mm] : [mm] x_2 [/mm] = 4-a (A)
für [mm] x_1=2 [/mm] : [mm] x_2 [/mm] = 4-2a (B)
für [mm] x_1=3 [/mm] : [mm] x_2 [/mm] = 4-3a (C)
dabei ist zusätzlich wichtig, dass [mm] 1\le x_2 \le [/mm] 3, also für
A : [mm] 1\le x_2 [/mm] = 4-a [mm] \le [/mm] 3 [mm] \gdw [/mm] 1 [mm] \le a\le [/mm] 3
B: [mm] 1\le x_2 [/mm] = 4-2a [mm] \le [/mm] 3 [mm] \gdw \bruch{1}{2} \le [/mm] a [mm] \le \bruch{3}{2}
[/mm]
C: [mm] 1\le x_2 [/mm] = 4-3a [mm] \le [/mm] 3 [mm] \gdw \bruch{1}{3} \le [/mm] a [mm] \le [/mm] 1
heit für mich für alle [mm] a\in \IR \setminu[\bruch{1}{3},3] [/mm] ist das problem unzulässig oder?
Es wäre super wenn ihr mir hier mal helfen könntet.
Schönen Abend noch
Noya
|
|
| |
|
Hallo,
> $ min [mm]\{ x_1+x_2 : ax_1+x_2 \le 4, 1\le x_1 \le 3, 1\le x_2 \le 3 \}[/mm]
>
> (a) Für welche Werte von a [mm]\in \IR[/mm] ist das Problem
> unzulässig oder unbeschränkt?
>
> (b) Berechnen Sie Optimalmenge und Optimalwert in
> Abhängigkeit von a.
> Hallo ihr Lieben,
>
> ich komme nicht so recht hier voran.
> Meine Lösungsmenge ist ja das Quadrat mit den EP
> (1,1),(1,3),(3,3),(3,1) und darein muss dann noch die
> Resktriktion : [mm]a*x_1[/mm] + [mm]x_2 \le[/mm] 4
> [mm]\gdw x_2 \le 4-a*x_1[/mm]
Das ist zwar etwas unglücklich formuliert, aber von der Grundüberlegung her richtig.
> betrachte ich für [mm]1\le x_1 \le[/mm] 3
> fktwerte von [mm]x_2[/mm]
> für [mm]x_1=1[/mm] : [mm]x_2[/mm] = 4-a (A)
> für [mm]x_1=2[/mm] : [mm]x_2[/mm] = 4-2a (B)
> für [mm]x_1=3[/mm] : [mm]x_2[/mm] = 4-3a (C)
Warum betrachtest du hier ganzzahlige x-Werte, es ist ja wohl kein diskretes Problem?
> dabei ist zusätzlich wichtig, dass [mm]1\le x_2 \le[/mm] 3, also
> für
> A : [mm]1\le x_2[/mm] = 4-a [mm]\le[/mm] 3 [mm]\gdw[/mm] 1 [mm]\le a\le[/mm] 3
> B: [mm]1\le x_2[/mm] = 4-2a [mm]\le[/mm] 3 [mm]\gdw \bruch{1}{2} \le[/mm] a [mm]\le \bruch{3}{2}[/mm]
>
> C: [mm]1\le x_2[/mm] = 4-3a [mm]\le[/mm] 3 [mm]\gdw \bruch{1}{3} \le[/mm] a [mm]\le[/mm] 1
> heit für mich für alle [mm]a\in \IR \setminu[\bruch{1}{3},3][/mm]
> ist das problem unzulässig oder?
Es ist genau andersherum. Liegt a in dem von dir ermittelten Intervall, dann ist die durch die Restriktionen vorgegebene Menge nichtleer. Für a=3 besteht sie aus dem Punkt (1,1), für kleinere a entsteht ein Simplex, für a=1/3 ist es schließlich das ganze Quadrat. Außerdem darf a auch kleiner als 1/3 werden, das bedeutet ja letztendlich nur, dass dann die Restriktion [mm] ax_1+x_2 \le{4} [/mm] in jedem Fall erfüllt ist.
Zeichne es dir in einem Koordinatensystem auf!
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:31 Fr 13.04.2018 | | Autor: | Diophant |
Hallo,
ok, da hast du bei dem Intervall für a einen Tippfehler, deshalb wird das falsch angezeigt. Das war mir heute morgen entgangen.
Also was a>3 angeht, da hat du recht. Aber wie gesagt, a<1/3 sollte kein Problem sein. Die zugehörigen Geraden verlaufen oberhalb des Quadrats. Und da sich sowieso alles innerhalb und auf dem Rand des Quadrats 'abspielt', stellt das kein Problem dar, weil es ja eine [mm]\le[/mm]-Restriktion ist.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:52 Fr 13.04.2018 | | Autor: | Noya |
Danke schonmal.
also ich habe das jetzt nochmal gezeichnet.
sobald a [mm] \in [\bruch{1}{3},3] [/mm] schneidet die restriktion [mm] a*x_1+x_2 \le4 [/mm] das oben beschriebene Quadrat. andernfalls liegt es außerhalb. Was genau bedeutet das dann?
Ich habe einfach noch nicht so ganz raus, wann das Problem unzulässig /unbeschränkt ist. Kannst du mir das eventuell genauer erklären?
ja hab da anscheinend vergessen was zu schreiben. Vom Gefühl her würde ich sagen das Problem ist zulässig für a [mm] \in [\bruch{1}{3},3] [/mm] und somit unzulässig für a [mm] \in \IR\setminus [\bruch{1}{3},3].
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:57 Fr 13.04.2018 | | Autor: | Diophant |
Hallo,
> Ich habe einfach noch nicht so ganz raus, wann das Problem
> unzulässig /unbeschränkt ist. Kannst du mir das eventuell
> genauer erklären?
jetzt habe ich keine Zeit mehr (vielleicht kann ja jemand anderes übernehmen?). Aber du könntest nochmals klären, ob das hier wirklich ein Minimierungsproblem ist. Denn wenn man sich die Richtung der Zielfunktion so anschaut, dann interessiert es die Lösung überhaupt nicht, wie groß a ist, so lange wie gesagt [mm] a\le{3} [/mm] gilt.
Das würde ganz anders aussehen (und mehr Sinn ergeben), wenn es um eine Maximierung ginge.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:32 Fr 13.04.2018 | | Autor: | Noya |
Trotzdem schon mal vielen Dank.
Nein es ist ganz sicher, laut Aufgabenstellung, ein Minimierungsproblem. Habe extra nochmal nachgeschaut.
hab mir das nochmal angeguckt.Optimalpunkt für Min.prob ist ja nunmal (1,1), dann wäre der Zielfunktionswert z=2 in allen anderen möglichen Ecken deutlich größer. heißt die restriktion spielt ja so oder so keine wirkliche Rolle,oder?
|
|
|
| |
|
Hallo,
jetzt ist doch nochmal ein Zeitfenster aufgegangen. 
Also schauen wir mal:
> also ich habe das jetzt nochmal gezeichnet.
> sobald a [mm]\in [\bruch{1}{3},3][/mm] schneidet die restriktion
> [mm]a*x_1+x_2 \le4[/mm] das oben beschriebene Quadrat.
Das ist soweit richtig, wie gesagt. Es entsteht dabei ein Simplex mit drei bis fünf Ecken, je nach Lage der Restriktion.
> andernfalls
> liegt es außerhalb. Was genau bedeutet das dann?
Der gültige Bereich für Lösungen eines LP ist stets die Schnittmenge aller Restriktionen.
Wenn a>3 ist, dann verläuft die fragliche Restriktion unterhalb des Quadrats und die Schnittmenge ist somit leer.
Für den Fall [mm]1/3\le{a}\le{3}[/mm] gilt, was du geschrieben hast.
Für den Fall a<1/3 jedoch ist die Schnittmenge einfach das komplette Quadrat.
> Ich habe einfach noch nicht so ganz raus, wann das Problem
> unzulässig /unbeschränkt ist.
Unzulässig ist es, wenn die Schnittmenge der Restriktionen leer ist. Unbeschränkt, wenn es kein Maximum bzw. Minimum gibt. So lange man Positivität voraussetzt, wird ein Minimierungsproblem niemals unbeschränkt sein, bei Maximierungsproblemen dagegen kann das auftreten. Dann bilden die Restriktionen kein Simplex, sondern ein ins Unendliche reichendes Gebiet.
> Kannst du mir das eventuell
> genauer erklären?
>
Also wenn das wirklich ein Minimierungsproblem ist, dann ist die Sache sehr einfach.
Für a>3 haben wir ein unzulässiges Problem, wie gesagt.
Jetzt schauen wir uns einmal die Zielfunktion etwas näher an:
[mm] x_1+x_2=c\ \gdw\ x_2=c-x_1
[/mm]
Graphisch gesehen verläuft die Zielfunktion also auf jeden Fall parallel zur 2. Winkelhalbierenden. Wenn wir uns nun überlegen, wie weit wir die Zielfunktion nach unten verschieben können, so dass sie mit dem zulässigen Gebiet noch mindestens einen gemeinsamen Punkt hat, dann sieht man sofort, dass das Minimum durch den Punkt (1,1) gegeben ist, und zwar wie gesagt unabhängig vom Wert von a, solange [mm] a\le{3}.
[/mm]
Zusammengefasst:
- a>3: kein zulässiges Problem
- alle anderen a: eindeutiges Minimum 1+1=2.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:38 Fr 13.04.2018 | | Autor: | Noya |
Super!!! Vielen vielen lieben Dank!!! :)
|
|
|
|
