Lineare Optimierung - Zulässige Menge

15.11.2010, 11:36

andres

Auf diesen Beitrag antworten »

Lineare Optimierung - Zulässige Menge

Hi,

ich verstehe es irgendwie nicht die zulässige Menge grafisch zu bestimmen.

Hier eine Beispielaufgabe:

Max z=10S + 9D
s.t.
$\begin{eqnarray*} \frac{7}{10}S+1D\leq 630 \end{eqnarray*}$ (1)

$\begin{eqnarray*} \frac{1}{2}S+\frac{5}{6}D\leq 600 \end{eqnarray*}$ (2)

$\begin{eqnarray*} 1S+\frac{2}{3}D\leq 708 \end{eqnarray*}$ (3)

$\begin{eqnarray*} \frac{1}{10}S+\frac{1}{4}D\leq 135 \end{eqnarray*}$ (4)

$\begin{eqnarray*} S,D\geq 0 \end{eqnarray*}$

Für jede Nebenbedingung S=0 / D=0 setzen:

für (1):

S=0 -----> D=630 (0;630)
D=0 -----> S=900 (900;0)

für (2):

S=0 -----> D=720 (0;720)
D=0 -----> S=1200 (1200;0)

für (3):

S=0 -----> D=1062 (0;1062)
D=0 -----> S=708 (708;0)

für (4):

S=0 -----> D=540 (0;540)
D=0 -----> S=1350 (1350;0)

So die Koordinaten für die 4 Geraden habe ich nun.

Mein Problem ist nun, dass ich nicht sicher bin, ob sich die zulässige Menge links oder rechts einer jeden Gerade befindet?

Woran sehe ich das bzw. was muss ich genau tun um zu sehen ob sich die zulässige Menge links- oder rechtsseitig der jeweiligen Gerade befindet?

Wäre sehr nett, wenn es mir jemand erläutern könnte.

Vielen Dank

15.11.2010, 11:38

tigerbine

Auf diesen Beitrag antworten »

RE: Lineare Optimierung - Zulässige Menge
Wie benennst du die Achsen deines Koordiantensystems also x=? y=?

Dann stelle wie aus der Schule gewohnt in die explizite Form der Geraden um. Dann kann man es doch direkt ablesen.

15.11.2010, 11:43

andres

Auf diesen Beitrag antworten »

X-Achse= S
Y-Achse=D

Was meinst du mit umstellen und dann ablesen?
Ich weiß irgendwie gar nicht was ich genau machen muss um rauszukriegen ob die zulässige Menge links-oder rechtsseitig verläuft.

15.11.2010, 11:46

tigerbine

Auf diesen Beitrag antworten »

Ich meine genau das, was ich gesagt habe. Augenzwinkern

Augenzwinkern

Machen wir mal ein "=" hin

implizite Geradenform:
$\begin{eqnarray*} \frac{7}{10}S+1D=630 \end{eqnarray*}$

explizite Geradenform:
$\begin{eqnarray*} D=- \frac{7}{10}S+ 630 \end{eqnarray*}$

Das kannst du doch einzeichnen.

Ich habe keine kritische Operation gemacht, also
$\begin{eqnarray*} D\leq- \frac{7}{10}S+ 630 \end{eqnarray*}$

Nun sollte klar sein ob oberhalb oder unterbalg der Geraden noch Punkte zulässig sind, oder?

15.11.2010, 12:04

andres

Auf diesen Beitrag antworten »

hmmm, nein habs immer noch nicht.

also man hat $\begin{eqnarray*} D\leq -\frac{7}{10}S+630 \end{eqnarray*}$

wenn nun D kleiner als $\begin{eqnarray*} -\frac{7}{10}S+630 \end{eqnarray*}$ befindet sich die zulässige Menge wohl links der Geraden

wenn D größer als $\begin{eqnarray*} -\frac{7}{10}S+630 \end{eqnarray*}$ befindet sie sich rechts der Geraden

Aber was setzt ich nun für D und S ein?

setze ich meine oben ausgerechneten Werte ein (also D=630; S=900) kommt ja

$\begin{eqnarray*} 630\leq 0 \end{eqnarray*}$ heraus, was ja inkorrekt ist.

Wie interpretiere ich das nun???

15.11.2010, 12:08

tigerbine

Auf diesen Beitrag antworten »

Es ist zunächst das Polyeder zu bestimmen. Offensichtlich liegt die zul. hier unterhalb und auf der Geraden. Nun noch alle anderen hinzufügen.

Zitat:

Aber was setzt ich nun für D und S ein?

Die Frage verstehe ich nicht. Ich verstehe auch nicht den Sinn, in die NB (0/0) einzusetzen. Das liefert nur Antwort auf die Frage ob der Punkt zulässig ist. Mehr trägt das nicht zur Lösung bei.

Anzeige

15.11.2010, 12:23

andres

Auf diesen Beitrag antworten »

Was bitte ist ein Polyeder???

Ich glaube du denkst hier schon zu weit.

Also, ich versuchs nochmal:

Ich habe ja in meinem 1. Beitrag für Nebenbedingung (1) jeweils einmal S=0 gesetzt und D=0 gesetzt um zwei Punkte herauszufinden durch um die Gerade zeichnen zu können, sie verläuft also durch den Punkt (0;630) und den Punkt (900;0).

So, nun soll ich aber noch die zulässige Menge bestimmen, d.h. ob sie sich links- oder rechtsseitig der Gerade befindet.

In meinem Lehrbuch ist es nun folgendermaßen dargestellt:

Die zulässige Menge befindet sich linksseitig der Gerade, wenn gilt:

$\begin{eqnarray*} \frac{7}{10}S+1D\leq 630 \end{eqnarray*}$

und rechtsseitig der Gerade, wenn:

$\begin{eqnarray*} \frac{7}{10}S+1D\geq 630 \end{eqnarray*}$

Aber woran erkenne ich denn nun ob es größer oder kleiner gleich 630 ist?
Das ist meine einziges Problem.

setze ich nun S=200 und D=200 in die Gleichung ein, kommt raus
$\begin{eqnarray*} 340\leq 630 \end{eqnarray*}$ , d.h die zulässige Menge befände sich linksseitig der Geraden.

Aber diese Punkte habe ich mir ja nur ausgedacht ich könnte ja auch für S=600 und D=500 einsetzen, was 920 ergäbe, also größer als 630 und somit ein rechtsseitiger Verlauf.

15.11.2010, 12:51

tigerbine

Auf diesen Beitrag antworten »

Ich habe in der HS Mathe angenommen, dass du Geraden zeichnen kannst (Klasse 9). verwirrt

verwirrt

Und stelle sie doch um wie ich es gemacht habe, und du siehst, dass es unterhalb sein muss.

$\begin{eqnarray*} D\leq- \frac{7}{10}S+ 630 \end{eqnarray*}$

S ist "frei", D muss kleiner Gleich dem sein, was auf der Geraden ist. Probiere zu gegen S halt mal 3 Fälle aus, dann wird dir das vielleicht einsichtiger.

Danach geht es (am Abend) weiter. Oder wer anders übernimmt. Wink

Wink

15.11.2010, 13:17

andres

Auf diesen Beitrag antworten »

Sorry, aber genauso sind wir in der Übung vorgegangen und so stehts auch im Lehrbuch.
Weis jetzt auch nicht was daran falsch sein soll, man errechnet zwei Punkte durch nullsetzen der jeweiligen Variable und kann somit die Gerade zeichnen.

Woran sehe ich denn das D kleiner als der rechtsseitige Term ist????
Ich muss doch für D und S irgendwas einsetzen um sagen zu können, dass D kleiner ist.

Verstehe nicht wie man einfach sagen kann D ist kleiner gleich -7/10S + 630 und verläuft somit unterhalb.
Ich könnte ja für D=1000 und S=200 einsetzen und schon wäre diese Aussage falsch!!!

setze ich jetzt z.B. für D=200 und S=200 ein, komme ich auf das Ergebnis

200 <gleich -7/10*200+630
200 <gleich 490

Somit ist dies doch Fakt und bewiesen und kann sagen die zulässige Menge ist links bzw. unterhalb der Geraden!

15.11.2010, 16:55

tigerbine

Auf diesen Beitrag antworten »

1. Es ist mir völlig egal - wie - ihr eine Gerade zeichnet. Das ist Schulstoff. Und mehr als ein Weg führt zum Ziel.

2. Du suchst zulässige Punkte (S|D). Wenn nun die Vorschrift lautet:

$\begin{eqnarray*} D\leq- \frac{7}{10}S+ 630 \end{eqnarray*}$ (*)

Dann frage dich, was darfst du für S einsetzen. Die D Koordinate muss dann kleiner gleich $\begin{eqnarray*} \frac{7}{10}S+ 630 \end{eqnarray*}$ sein. Nun wähle ein solches D. Wo liegt es

Zitat:

Ich könnte ja für D=1000 und S=200 einsetzen und schon wäre diese Aussage falsch!!!

Da ist doch Unsinn. Du sollst S und D ja nicht beliebig wählen. Sondern so, dass erfüllt ist.

Du solltest dich noch mal mit Geradengleichungen aus der Schulmate beschäftigen. Die Form y=mx+t sollte Erinnerungen wecken.

(*) Besagt, dass alle zulässigen Punkte (S|D) eine kleinere (gleich) D-Koordinate haben, also die Punkte auf der Geraden

$\begin{eqnarray*} D=- \frac{7}{10}S+ 630 \end{eqnarray*}$

Also liegen sie unterhalb. Warum soll ich mit da erst einen speziellen Punkt ausrechnen, um das einzusehen. verwirrt

verwirrt

15.11.2010, 17:27

andres

Auf diesen Beitrag antworten »

Hmmm, okay nehmen wir ein Beispiel wo die zulässige Menge sich oberhalb der Gerade befindet.

$\begin{eqnarray*} max z=2x_{1}-2x_{2} \end{eqnarray*}$

s.t.
$\begin{eqnarray*} -x_{1}+x_{2}\leq 2 \end{eqnarray*}$ (1)

$\begin{eqnarray*} -2x_{1}+x_{2}\leq 1 \end{eqnarray*}$ (2)

$\begin{eqnarray*} x_{i}\geq 0 \end{eqnarray*}$

Hier ist nach Ergebnis des Buches die zulässige Menge rechtsseitig/oberhalb der Geraden gekennzeichnet und zwar bei beiden Nebenbedingungen.

zu (1)

$\begin{eqnarray*} -x_{1}+x_{2}\leq 2 \end{eqnarray*}$

umstellen:

$\begin{eqnarray*} x_{2}\leq 2 +x_{1} \end{eqnarray*}$

So, woran sehe ich nun, dass die zulässige Menge sich rechtsseitig/oberhalb der Gerade befindet???? ( wie im Buch gezeigt)

Ich sehe nämlich keinen Unterschied zum vorherigen Beispiel!

15.11.2010, 17:30

tigerbine

Auf diesen Beitrag antworten »

Es stimmt ja auch nicht.

$\begin{eqnarray*} -x_{1}+x_{2}\leq 2 \end{eqnarray*}$

$\begin{eqnarray*} x_{2}\leq x_1 +2 \end{eqnarray*}$

Wieder unterhalb. Besitzt du die Möglichkeit einzuscannen? Oder gibt es das Buch bei Wikibooks?

15.11.2010, 17:37

andres

Auf diesen Beitrag antworten »

nein hab leider keinen scanner....

also kann man dann pauschal sagen, dass bei Gleichungen mit $\begin{eqnarray*} \leq \end{eqnarray*}$ zeichen die zulässige Menge linksseitig/unterhalb der Gerade liegen und bei
Gleichungen mit $\begin{eqnarray*} \geq \end{eqnarray*}$ zeichen sich die zulässige Menge rechtsseitig/oberhalb der Gerade befindet!?

15.11.2010, 18:05

tigerbine

Auf diesen Beitrag antworten »

Nein, das kann man pauschal nicht sagen! Zu unpräzise. Bauart

$\begin{eqnarray*} y \leq mx+t \end{eqnarray*}$ unterhalb

$\begin{eqnarray*} y \geq mx+t \end{eqnarray*}$ oberhalb

15.11.2010, 18:29

andres

Auf diesen Beitrag antworten »

ok, dann danke für die Hilfe

15.11.2010, 18:31

tigerbine

Auf diesen Beitrag antworten »

Bitte.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »