Lineare Optimierung < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Optimaler Produktionsplan: Ein Autohersteller hat ein Montagewerk in Österreich und eines in Deutschland, beide können PKWs und LKWs montieren. Das Montagewerk in Österreich kann pro Tag höchstens 600 Fahrzeuge (also PKWs und LKWs zusammen) montieren, wobei Montagekosten von 1000 Euro pro PKW anfallen und 1600 Euro pro LKW. Das Werk in Deutschland kann pro Tag maximal 400 Fahrzeuge montieren, wobei Kosten von 800 Euro pro PKW und 1500 Euro pro LKW entstehen. Nun soll der Autohersteller innerhalb eines Tages 500 PKWs und 200 LKWs liefern. Wie viele PKWs/LKWs sollte er für diesen Auftrag jeweils in Österreich und Deutschland produzieren, sodass die Gesamt-Montagekosten minimal sind? (Tipp: Wenn Sie x=Anzahl der PKWs, die in Ö montiert werden, ansetzen, und y=Anzahl der LKWs, die in Ö montiert werden, dann ist 500 − x=Anzahl der PKWs, die in D montiert werden, und 200 − y = Anzahl der LKWs, die in D montiert werden.) |
Hallo!
Ich komme leider auf keinen grünen Zweig. Ich habe folgende Randbedingungen ermittelt:
1) x + y [mm] \le [/mm] 600
2) -x -y [mm] \le [/mm] -100 (Im Billig-Lohnland Dtl können maximal 400 KFZ hergestellt werden, daher müssen mindestens 100 aus AU kommen).
Die Zielfunktion lautet dann: f = 1000x + 1600y + 800(500 - x) + 1500(200 - y) = 700000 + 200x + 100y
Da die Zielfunktion minimiert werden soll, gilt es, folgende Funktion zu maximieren:
f' = -f = -700000 - 200x - 100y
Das Simplex-Tableau sieht dann wie folgt aus:
[mm] \pmat{ 1 & 1 & 1 & 0 & 600 \\ -1 & -1 & 0 & 1 & -100 \\ 200 & 100 & 0 & 0 & 700000 }
[/mm]
In der letzten Zeile sind leider alle Koeffizienten positiv :-( Wie kann ich jetzt das Pivot-Element finden?
Muss ich noch irgendeine "Startecke" suche? Irgendwas hab ich noch nicht ganz verstanden :-(
|
|
| |
|
Hallo,
> Optimaler Produktionsplan: Ein Autohersteller hat ein
> Montagewerk in Österreich und eines in Deutschland, beide
> können PKWs und LKWs montieren. Das Montagewerk in
> Österreich kann pro Tag höchstens 600 Fahrzeuge (also
> PKWs und LKWs zusammen) montieren, wobei Montagekosten von
> 1000 Euro pro PKW anfallen und 1600 Euro pro LKW. Das Werk
> in Deutschland kann pro Tag maximal 400 Fahrzeuge
> montieren, wobei Kosten von 800 Euro pro PKW und 1500 Euro
> pro LKW entstehen. Nun soll der Autohersteller innerhalb
> eines Tages 500 PKWs und 200 LKWs liefern. Wie viele
> PKWs/LKWs sollte er für diesen Auftrag jeweils in
> Österreich und Deutschland produzieren, sodass die
> Gesamt-Montagekosten minimal sind? (Tipp: Wenn Sie x=Anzahl
> der PKWs, die in Ö montiert werden, ansetzen, und y=Anzahl
> der LKWs, die in Ö montiert werden, dann ist 500 −
> x=Anzahl der PKWs, die in D montiert werden, und 200 − y
> = Anzahl der LKWs, die in D montiert werden.)
>
>
> Hallo!
> Ich komme leider auf keinen grünen Zweig. Ich habe
> folgende Randbedingungen ermittelt:
>
> 1) x + y [mm]\le[/mm] 600
> 2) -x -y [mm]\le[/mm] -100 (Im Billig-Lohnland Dtl können maximal
> 400 KFZ hergestellt werden, daher müssen mindestens 100
> aus AU kommen).
>
> Die Zielfunktion lautet dann: f = 1000x + 1600y + 800(500 -
> x) + 1500(200 - y) = 700000 + 200x + 100y
> Da die Zielfunktion minimiert werden soll, gilt es,
> folgende Funktion zu maximieren:
>
> f' = -f = -700000 - 200x - 100y
>
> Das Simplex-Tableau sieht dann wie folgt aus:
>
> [mm]\pmat{ 1 & 1 & 1 & 0 & 600 \\ -1 & -1 & 0 & 1 & -100 \\ 200 & 100 & 0 & 0 & 700000 }[/mm]
>
> In der letzten Zeile sind leider alle Koeffizienten positiv
> :-( Wie kann ich jetzt das Pivot-Element finden?
> Muss ich noch irgendeine "Startecke" suche? Irgendwas hab
> ich noch nicht ganz verstanden :-(
Zwei Dinge:
- die Zielfunktion gehört in die oberste Zeile, sie ist ja gar nicht Teil des eigentlichen Tableaus.
- Deine zweite Nebenbedingung basiert auf einer falschen Annahme (dass nämlich die Autos samt und sonders alle in A oder in D gefertigt werden). Sie (die Bedingung) muss korrekt lauten:
[mm] 500-x+200-y\le{400}
[/mm]
Und das ist gleichbedeutend zu
[mm] -x-y\le{-300}
[/mm]
Vielleicht helfen dir diese beiden Hinweise schon, einen Anfang zu finden?
Gruß, Diophant
|
|
|
| |
|
Hallo nochmal,
du musst mir hier bitte noch ein Bisschen weiter auf die Sprünge helfen:
> - die Zielfunktion gehört in die oberste Zeile, sie ist ja
> gar nicht Teil des eigentlichen Tableaus.
In meinem ![[]](/images/popup.gif) Lehrbuch wird die Zielfunktion als letzte Zeile in das Tableau geschrieben, aber das nur am Rande...
> - Deine zweite Nebenbedingung basiert auf einer falschen
> Annahme (dass nämlich die Autos samt und sonders alle in A
> oder in D gefertigt werden).
Das verstehe ich nicht: x bezeichnet doch die Anzahl der in A gefertigten PKW, y die in A gefertigten LKW. Wieso bedeutet dann "x + z [mm] \ge [/mm] 100", dass entweder (alle KFZ in A) oder (alle KFZ in G) gefertigt werden?
Auch habe ich jetzt immer noch keinen negativen Koeffizienten auf der linken Seite der Zielfunktion im Tableau. Kannst du mir mal zeigen, wie das Start-Tableau aussehen müsste, und dann den/die ersten (paar) Schritt(e)?
Danke und Gruß,
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:31 Fr 20.04.2018 | | Autor: | Diophant |
Hallo,
> du musst mir hier bitte noch ein Bisschen weiter auf die
> Sprünge helfen:
nee, müssen tut hier niemand etwas. 
> > - die Zielfunktion gehört in die oberste Zeile, sie ist ja
> > gar nicht Teil des eigentlichen Tableaus.
>
> In meinem
> Lehrbuch
> wird die Zielfunktion als letzte Zeile in das Tableau
> geschrieben, aber das nur am Rande...
Ok.
> > - Deine zweite Nebenbedingung basiert auf einer falschen
> > Annahme (dass nämlich die Autos samt und sonders alle in A
> > oder in D gefertigt werden).
>
> Das verstehe ich nicht: x bezeichnet doch die Anzahl der in
> A gefertigten PKW, y die in A gefertigten LKW. Wieso
> bedeutet dann "x + z [mm]\ge[/mm] 100", dass entweder (alle KFZ in
> A) oder (alle KFZ in G) gefertigt werden?
>
> Auch habe ich jetzt immer noch keinen negativen
> Koeffizienten auf der linken Seite der Zielfunktion im
> Tableau.
Bevor wir hier weitermachen: das fragliche Buch kenne und besitze ich nicht. Es gibt zwei Möglichkeiten, wie man das Simplex-Verfahren auf Minimierungsprobleme anwendet:
- durch Umkehr des Auswahlkriteriums für die Pivotspalte
- durch Vorzeichenumkehr der Zielfunktion und Maximierung der so erhaltenen Funktion.
> Kannst du mir mal zeigen, wie das Start-Tableau
> aussehen müsste, und dann den/die ersten (paar)
> Schritt(e)?
Nun, du hast ja schon eine Zielfunktion f' aufgestellt, dann vermutet man natürlich, dass du diese maximieren möchtest. Wieso verwendest du sie dann aber nicht in deinem Tableau?
Weiter ist es natürlich möglich, dass ich deine Überlegungen zur zweiten Nebenbedingung falsch eingeschätzt habe. Das ist aber völlig egal, entscheidend ist, dass sie falsch ist.
Also bevor das alles nicht geklärt ist, sehe ich keinen Sinn darin, hier weiterzumachen.
Gruß, Diophant
|
|
|
| |
|
Ich bin gerade vollends verwirrt.
Das mit meiner falschen Bedingung habe ich mittlerweile verstanden und war nur ein Schusselfehler.
Im Grund denke ich, ist das hier das richtige Start-Tableau:
[mm] \pmat{ 1 & 1 & 1 & 0 & 600 \\ -1 & -1 & 0 & 1 & -300 \\ 200 & 100 & 0 & 0 & -700000 }
[/mm]
Allerdings komme ich hier auf einen Zielwert von 730000 mit [mm] x_1 [/mm] = 0 und [mm] x_2 [/mm] = 300.
Diese Lösung bestätigt sich auch hier
Laut Lehrbuch ist die korrekte Lösung aber 740 000 mit [mm] x_1 [/mm] = 100 und [mm] x_2 [/mm] = 200.
Was ist richtig?
|
|
|
| |
|
Hallo,
deine Frage und meine Antwort auf deine vorige Frage haben sich überschnitten, schaue also dort auch nochmal nach.
> Ich bin gerade vollends verwirrt.
> Das mit meiner falschen Bedingung habe ich mittlerweile
> verstanden und war nur ein Schusselfehler.
Ok, dann wäre das geklärt.
> Im Grund denke ich, ist das hier das richtige
> Start-Tableau:
>
> [mm]\pmat{ 1 & 1 & 1 & 0 & 600 \\ -1 & -1 & 0 & 1 & -300 \\ 200 & 100 & 0 & 0 & -700000 }[/mm]
>
An diesem Tableau sind zwei Dinge falsch:
- die Vorzeichen in der letzten Zeile müssen alle negativ sein.
- es fehlen zwei Zeilen respektive zwei Bedingungen.
Aber das steht wie gesagt alles in meiner vorigen Antwort.
> Allerdings komme ich hier auf einen Zielwert von 730000 mit
> [mm]x_1[/mm] = 0 und [mm]x_2[/mm] = 300.
Das ist falsch, kann ja auch gar nicht anders sein.
> Diese Lösung bestätigt sich auch
> hier
>
> Laut Lehrbuch ist die korrekte Lösung aber 740 000 mit [mm]x_1[/mm]
> = 100 und [mm]x_2[/mm] = 200.
>
> Was ist richtig?
Die Musterlösung natürlich. Wie gesagt: Zielfunktion richtig eintragen, die zwei fehlenden Bedingungen ergänzen, und dann solltest du es hinbekommen.
Gruß, Diophant
|
|
|
| |
|
Hallo!
> An diesem Tableau sind zwei Dinge falsch:
>
> - die Vorzeichen in der letzten Zeile müssen alle negativ
> sein.
> - es fehlen zwei Zeilen respektive zwei Bedingungen.
Ich hatte heute leider keine Zeit es durchzurechnen, habe aber deinen Input mit den zwei Zusatzbedingungen mal hier eingegeben und durchrechnen lassen. Ich hänge das Ergebnis mal als Screenshot an diesen Post an. Ich weiß nicht, ob es mehrere Möglichkeiten gibt, das Start-Tableau aufzustellen, aber wie du siehst, steht auch hier im Start-Tableau auf der linken Seite 200 und 100 und auf der rechten -700000.
Allerdings kommt der auch jetzt auf den korrekten Zielwert:
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Hallo,
> > An diesem Tableau sind zwei Dinge falsch:
> >
> > - die Vorzeichen in der letzten Zeile müssen alle negativ
> > sein.
> > - es fehlen zwei Zeilen respektive zwei Bedingungen.
>
> Ich hatte heute leider keine Zeit es durchzurechnen, habe
> aber deinen Input mit den zwei Zusatzbedingungen mal
> hier eingegeben
> und durchrechnen lassen. Ich hänge das Ergebnis mal als
> Screenshot an diesen Post an. Ich weiß nicht, ob es
> mehrere Möglichkeiten gibt, das Start-Tableau
> aufzustellen, aber wie du siehst, steht auch hier im
> Start-Tableau auf der linken Seite 200 und 100 und auf der
> rechten -700000.
Das war dann doch mein Fehler. Ich selbst habe ja wie gesagt die 700000 einfach weggelassen und als Zielfunktion
f'=-200x-100y
verwendet. Die 700000,- € habe ich einfach nachher zum Resultat wieder hinzuaddiert. Aber wenn man es so macht, dann wechseln die 700000 ja die Seite und damit das Vorzeichen, das hatte ich übersehen. Sorry.
Gruß, Diophant
|
|
|
| |
|
Wenn du dir die vom Generator erzeugte Rechnung anschaust, da wird im ersten Schritt das Pivot-Element in Zeile 2, Spalte 2 gewählt: Warum?
|
|
|
| |
|
Hallo,
> Wenn du dir die vom Generator erzeugte Rechnung anschaust,
> da wird im ersten Schritt das Pivot-Element in Zeile 2,
> Spalte 2 gewählt: Warum?
Zuerst wird ja die Spalte gewählt. Da ist [mm] x_2=100 [/mm] in der Zielfunktion der kleinere Wert, also sollte die Spalte schon einmal klar sein.
Zum besseren Verständnis muss man hier darauf hinweisen, dass der Simplex-Rechner die Funktion f minimiert, aber beim Eintrag in das Tableau offensichtlich auf die Vorzeichenumkehr verzichtet (so verstehe ich das zumindest, und so sind auch die -700000 zu erklären).
Und für die Zeile gibt es ja dann nicht wirklich eine Wahl.
Die Umkehrung der Optimierungsrichtung wird hier also durch die Umkehr des Auswahlkriteriums für die Pivotspalte sowie durch die entsprechnede Abänderung das Abbruchkriteriums erreicht und nicht durch eine Vorzeichenumkehr in der Zielfunktion mit anschließender Maximierung.
Ich möchte auch an dieser Stelle noch eine kritische Anerkung loswerden. Das ist ja nun kein ganz leichter Stoff, und offensichtlich hast du ihn noch nicht so gut verstanden (was natürlich nicht schlimm ist, mir geht es da ähnlich, weil ich das Simplex-Verfahren im Beruf relativ selten benötige und auch immer zuerst wieder nachschlagen muss).
-----------------------------------------------------------------------
Wenn man zu solch komplexem Stoff aber Hilfestellung über eine Rechenkontrolle hinaus wünscht: ganz ehrlich, dann sollte man seine Anliegen präziser und ausführlicher vortragen, als dies hier geschehen ist. Dazu gehören insbesondere
- Kenntnisstand/Verständnisschwierigkeiten
- In diesem Fall: Angaben zur dir bekannten Vorgehensweise (denn das Simplexverfahren ist zwar vom Kern her immer das gleiche, aber die Vorgehensweisen bei der schriftlichen Durchführung sowie die Behandlung von Minimierungsproblemen variieren nun einmal.
- Ausführliche Problembeschreibung. Also hier z.B. nicht nur die Frage, warum das Pivotelement so und nicht anders gewählt wurde sondern eine möglichst präzise Beschreibung, warum dir das unklar ist.
Gruß, Diophant
|
|
|
| |
|
Hallo,
da du gerade online bist:
die Zielfunktion ist
f'=-200x-100y
Die Festkosten kann man weglassen und am Ende wieder dazurechnen.
Die Nebenbedingunen sind
[mm] x+y\le{600}
[/mm]
[mm] -x-y\le{-300}
[/mm]
[mm] x\le{500}
[/mm]
[mm] y\le{200}
[/mm]
Ein Tableau solltest du damit jetzt hinbekommen. Und was die Pivotisierung betrifft, solltest du dann schon näher erläutern, wo genau du nicht weiterkommst.
Zur Kontrolle: die optimale Lösung ist gegeben mit 100 PKW sowie 200 LKW, die in Österreich gefertigt werden. Also in Koordinaten: bei (x,y)=(100,200) liegt das Minimum der Zielfunktion.
Gruß, Diophant
|
|
|
|
