Lineare Optimierung < Lineare Gleich.-sys. < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | Ein Bäcker hat 80kg Roggenmehl, 50kg Weizenmehl und 60kg Maismehl.
Er will möglichst viele Brote dreier unterschiedlicher Sorten backen.
Sorte A enthält 30% Roggenmehl, 50% Weizenmehl und 20% Maismehl.
Sorte B enthält 80% Roggenmehl, 20% Weizenmehl und 0% Maismehl.
Sorte C enthält 60% Roggenmehl, 10% Weizenmehl und 30% Maismehl. |
Hallo,
habe das in der Aufgabe beschriebene Problem eines LGS schon mal gepostet und versehentlich eine zu kurze Forumfälligkeit gewählt. Die Frage ist noch immer ungelößt:
Die Matrix lautet:
0,3|0,8|0,6|80
0,5|0,2|0,1|50
0,2|0,0|0,3|60
Gauß liefert mir die Lösungsmenge {87;-39;142}
Simplex liefert mir die Lösungsmenge {82;0;93}
Die Lösungsmenge soll sein {72;59;18}
Welchen Rechenschritt muß ich machen um aus einem (eindeutig lösbaren) LGS, welches z.B. einen negativen Wert enthält nur positive Werte zu erhalten, die in ihrer Summe maximiert oder minimiert sind.
Simplex ist in diesem Fall nicht zielführend, weil alle Koordinaten mit >0 besetzt werden sollen.
Vielleicht gibt es hier eine Simplexlösung, die die Optimierung für eine möglichst breite Lösungsmenge liefert. Die würde mich nebenbei sehr interessieren.
Der Lösungsansatz müßte aber sehr viel einfachere Rechenschritte mit einer Quotientenbildung enthalten, soweit ich weis.
Mehr Info habe ich leider nicht.
Könnte mir jemand den Lösungsweg posten, bitte.
Vielen Dank!
Dazu antwortete Abakus kurz darauf:
Hallo,
die Aufgabe ist unterbestimmt. Es fehlt die (vermutlich geltende?) Angabe,
dass alle Brote (egal, von welcher Sorte sie sind) die gleiche Mehl-Masse haben sollen.
Gruß Abakus
Wie sähe denn ein normalbestimmtes Gleichungssystem aus 1. bei gleicher und 2. bei ungleicher Mehlmasse, ohne dass ich die Prozentzahlen gleich zu Beginn der Rechnung in Gramm je Brot umrechnen müßte? Das heißt, bekomme ich diese Zusatzbedingung des Brotgewichts mit einer zusätzlichen Zeile hin? Wenn ja, wie würde diese bei 1 kg je Brot lauten? Wie müßte die zusätzliche Zeile bei unterschiedlichen Gewichten aussehen?
PS:Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.onlinemathe.de/forum/Optimierungsproblem-7
http://www.uni-protokolle.de/foren/viewt/276701,0.html
Habe dort aber bisher keine brauchbare Antwort erhalten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:32 Sa 12.02.2011 | | Autor: | lexjou |
Hallo,
versuche mal mit Mengen und zu rechnen bei dieser Aufgabe! ;)
Male Dir am Besten das entsprechende Diagramm dazu auf!
|
|
|
| |
|
> versuche mal mit Mengen und zu rechnen bei dieser Aufgabe!
> ;)
Mit Mengen zu rechnen klappt schon. Aber ich kann doch unmöglich immer alle Varianten durchprobieren.
> Male Dir am Besten das entsprechende Diagramm dazu auf!
>
Diesen Lösungsansatz kenne ich noch nicht. Könntest Du vielleicht ein Beispiel posten, bitte?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:39 So 13.02.2011 | | Autor: | lexjou |
Hallo,
>
> > Male Dir am Besten das entsprechende Diagramm dazu auf!
> >
>
> Diesen Lösungsansatz kenne ich noch nicht. Könntest Du
> vielleicht ein Beispiel posten, bitte?
Ich meine die Venn-Diagramme! Damit kommt man bei solchen Aufgaben meist ungeahnt schnell zur Lösung ;)
Gruß
lexjou
|
|
|
| |
|
Hi lexjou,
Venn-Diagramme kenn ich, wußte aber nicht, dass man die hier anwenden kann. Ich versteh auch noch nicht wie. Könntest Du mir ein kleines Beispiel oder einen Link posten, damit ich den Bezug zu linearen Gleichungssystemen herstellen kann, bitte.
Gruß
student
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 16.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:38 So 13.02.2011 | | Autor: | abakus |
> Ein Bäcker hat 80kg Roggenmehl, 50kg Weizenmehl und 60kg
> Maismehl.
>
> Er will möglichst viele Brote dreier unterschiedlicher
> Sorten backen.
>
> Sorte A enthält 30% Roggenmehl, 50% Weizenmehl und 20%
> Maismehl.
> Sorte B enthält 80% Roggenmehl, 20% Weizenmehl und 0%
> Maismehl.
> Sorte C enthält 60% Roggenmehl, 10% Weizenmehl und 30%
> Maismehl.
Hallo,
nehmen wir an, er soll a Brote der Sorte A, b Brote der Sorte B und c Brote der Sorte C backen.
Für die benötigten Mehlmengen gilt (wie in deiner Matrix):
0,3a+0,8b+0,6c [mm] \le [/mm] 80
0,5a+0,2b+0,1c [mm] \le [/mm] 50
0,2a+0,0b+0,3c [mm] \le [/mm] 60
Die Summe a+b+c soll maximal sein, UND a, b und c sind nichtnegative ganze Zahlen.
Was ich der Aufgabe nicht entnehme, ob diese Zahlen sogar mindestens 1 sein müssen oder auch Null sein dürfen ("Brote dreier unterschiedlicher Sorten" schließt eine Anzahl 0 eigentlich aus.)
Die drei gegeben "Begrenzungsgleichungen" sind drei unterschiedlich "schiefe" Ebenen, die sich gegenseitig schneiden. Mögliche Lösungspunkte liegen "unter dem Dach" aller drei Ebenen und natürlich im 1. Oktanten.
Empfohlenes Vorgehen:
Bestimme von je 2 der drei Ebenen ihre Schnittgerade. Begrenze diese Schnittgerade auf den Abschnitt, der durch den ersten Oktantemn führt und dort wiederum auf die Teilstrecke der Schnittgeraden, die UNTERHALB der jeweils dritten Ebene liegt.
Du erhältst somit drei Strecken, die vom gemeinsamen Schnittpunkt S aller Ebenen zu je einem Schnittpunkt mit den drei Koordinatenebenen führen.
Teste nun S und die drei anderen Punkte darauf, wo a+b+c maximal ist.
Das tust du, indem du die Ebene 1*a+1*b+1*c=d durch S gehen lässt und den dafür erforderlichen Wert für d bestimmst. Bei den anderen drei Punkten erhälst du für deren Koordinaten jeweils ein anderes d. Der Punkt mit dem größten d liefert den größtmöglichen Wert für a+b+c.
Unangenehm wird es, wenn bei diesem maximalen d die Zahlen a, b und c nicht ganzzahlig sind. Dann müsstest du d ein wenig verkleinern, bis a und b und c ganzzahlig sind. Der beste Punkt liegt dann vielleicht nicht mehr auf der Kante des Begrenzungskörpers, sondern im Inneren.
Gruß Abakus
> Hallo,
>
> habe das in der Aufgabe beschriebene Problem eines LGS
> schon mal gepostet und versehentlich eine zu kurze
> Forumfälligkeit gewählt. Die Frage ist noch immer
> ungelößt:
>
> Die Matrix lautet:
>
> 0,3|0,8|0,6|80
> 0,5|0,2|0,1|50
> 0,2|0,0|0,3|60
>
> Gauß liefert mir die Lösungsmenge {87;-39;142}
> Simplex liefert mir die Lösungsmenge {82;0;93}
>
> Die Lösungsmenge soll sein {72;59;18}
>
> Welchen Rechenschritt muß ich machen um aus einem
> (eindeutig lösbaren) LGS, welches z.B. einen negativen
> Wert enthält nur positive Werte zu erhalten, die in ihrer
> Summe maximiert oder minimiert sind.
> Simplex ist in diesem Fall nicht zielführend, weil alle
> Koordinaten mit >0 besetzt werden sollen.
> Vielleicht gibt es hier eine Simplexlösung, die die
> Optimierung für eine möglichst breite Lösungsmenge
> liefert. Die würde mich nebenbei sehr interessieren.
>
> Der Lösungsansatz müßte aber sehr viel einfachere
> Rechenschritte mit einer Quotientenbildung enthalten,
> soweit ich weis.
>
> Mehr Info habe ich leider nicht.
>
> Könnte mir jemand den Lösungsweg posten, bitte.
>
> Vielen Dank!
>
>
>
> Dazu antwortete Abakus kurz darauf:
>
> Hallo,
> die Aufgabe ist unterbestimmt. Es fehlt die (vermutlich
> geltende?) Angabe,
> dass alle Brote (egal, von welcher Sorte sie sind) die
> gleiche Mehl-Masse haben sollen.
> Gruß Abakus
>
>
>
> Wie sähe denn ein normalbestimmtes Gleichungssystem aus 1.
> bei gleicher und 2. bei ungleicher Mehlmasse, ohne dass ich
> die Prozentzahlen gleich zu Beginn der Rechnung in Gramm je
> Brot umrechnen müßte? Das heißt, bekomme ich diese
> Zusatzbedingung des Brotgewichts mit einer zusätzlichen
> Zeile hin? Wenn ja, wie würde diese bei 1 kg je Brot
> lauten? Wie müßte die zusätzliche Zeile bei
> unterschiedlichen Gewichten aussehen?
>
>
> PS:Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> http://www.onlinemathe.de/forum/Optimierungsproblem-7
> http://www.uni-protokolle.de/foren/viewt/276701,0.html
> Habe dort aber bisher keine brauchbare Antwort erhalten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:46 Mo 14.02.2011 | | Autor: | einstudent |
Wow Abakus! Klasse erklärt :)
Vielen Dank und die besten Wünsche von einstudent!
|
|
|
|
