Optimierungsproblem Lineare Algebra

30.01.2011, 20:38

_student_

Optimierungsproblem Lineare Algebra

Hallo,

habe folgendes Problem eines LGS:

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.

Die Matrix lautet dann:

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!

31.01.2011, 22:42

Reksilat

Auf diesen Beitrag antworten »

RE: Optimierungsproblem Lineare Algebra
Du solltest vielleicht mal Deine Lösung und die gegebene Lösung vergleichen. Offenbar liefert auch der zulässige Produktionsplan (80;1;90) mehr Brote als (72;59;18).
Irgendwas stimmt da nicht mit der gegebenen Lösung.

Zitat:

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?

Den Simplex-Algorithmus hat man nicht zum Spaß erfunden. Wenn man das auch mit Gauß direkt könnte, würde man sich den Aufwand nicht machen. Augenzwinkern

Zitat:

Simplex ist in diesem Fall nicht zielführend, weil alle Koordinaten mit >0 besetzt werden sollen.

Du könntest $\begin{eqnarray*} x_i':=x_i-1 \end{eqnarray*}$ substituieren. Dann entspricht die Nichtnegativitätsbedingung $\begin{eqnarray*} x_i'\geq 0 \end{eqnarray*}$ gerade Deiner Forderung.

Zitat:

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.

Zitat:

Könnte mir jemand den Lösungsweg posten, bitte.

Prinzip "Mathe online verstehen!"

Gruß,
Reksilat.

01.02.2011, 10:54

_student_

Auf diesen Beitrag antworten »

Zitat:

Du könntest $\begin{eqnarray*} x_i':=x_i-1 \end{eqnarray*}$ substituieren. Dann entspricht die Nichtnegativitätsbedingung $\begin{eqnarray*} x_i'\geq 0 \end{eqnarray*}$ gerade Deiner Forderung.

Das ist es wohl, was mir fehlte. Nur, wie kriege ich das praktisch hin? Ich weis nicht wo ich diese (zusätzliche?) Bedingung einbauen muß. Ich habe doch schon z=x1+x2+x3-190 belegt.

Bitte poste mir ein Beispiel zu meiner aktuellen Aufgabe für die willkürlich gewählte Nichtnegativitätsbedingung $\begin{eqnarray*} x_2':=x_2-7 \end{eqnarray*}$

01.02.2011, 15:49

Reksilat

Auf diesen Beitrag antworten »

Deine erste Gleichung lautet:
$\begin{eqnarray*} 0,3x_1+0,8x_2+0,6x_3\leq 80 \end{eqnarray*}$

Setze $\begin{eqnarray*} x_2':=x_2-7 \end{eqnarray*}$ , dann ist $\begin{eqnarray*} x_2=x_2'+7 \end{eqnarray*}$ und die Gleichung wird zu:
$\begin{eqnarray*} 0,3x_1+0,8x_2'+0,8\cdot 7+0,6x_3\leq 80 \end{eqnarray*}$
bzw.
$\begin{eqnarray*} 0,3x_1+0,8x_2'+0,6x_3\leq 80-5,6=74,4 \end{eqnarray*}$

03.02.2011, 11:11

_student_

Auf diesen Beitrag antworten »

Hi Reksilat,

habs probiert mit 59, dem x2-Wert der angeblich richtigen Lösung. Funzt leider nicht.

Simplex liefert jetzt die Lösungsmenge {73;0;18}

Hier meine Eingabe:

Zielfunktion
z=x1+x2+x3-190

Nebenbediingungen
0,3x1+0,8x2+0,6x3<32.8
0,5x1+0,2x2+0,1x3<38.2
0,2x1+0,0x2+0,3x3<60

Hab ich was verdreht oder falsch konditioniert?

03.02.2011, 12:59

Reksilat

Auf diesen Beitrag antworten »

Was funzt denn nicht?

Du hast Durch die Substitution $\begin{eqnarray*} x_2'=x_2-59 \end{eqnarray*}$ und die Nichtnegativitätsbedingung $\begin{eqnarray*} x_2'\geq 0 \end{eqnarray*}$ gefordert, dass der $\begin{eqnarray*} x_2 \end{eqnarray*}$ -Wert mindestens 59 sein muss, dass also mindestens 59 Brote vom zweiten Typ gebacken werden sollen. Irgendwie ist es auch naheliegend, dass dieses Ergebnis dann rauskommt.
(Beachte, dass Du wieder rücksubstituieren musst. $\begin{eqnarray*} (x_1,x_2',x_3)=(73,0,18) \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} (x_1,x_2,x_3)=(73,59,18) \end{eqnarray*}$ )

Allerdings weiß ich nicht, was das mit der Aufgabe zu tun hat, denn eine derartige Mindestmenge für Typ 2 hast Du zuvor nicht erwähnt.

Gruß,
Reksilat.

06.02.2011, 12:56

_student_

Auf diesen Beitrag antworten »

Ah, jetzt ja!

Sehr gut Resubstitution hatte mir gefehlt. Die Mindestmenge war ganz oben mal angegeben. Mein Problem ist gelöst. Vielen Dank und die besten Wünsche Reksilat. Freude

Könntest Du mir noch zu einer an des Problem anlehnenden Frage weiterhelfen:

Es gibt doch wahrscheinlich eine Art n-dimensionale (in diesem Fall 3-dimensionale) Ortskurve für die Schnittpunkte. Kann ich das in 3D darstellen? Wie berechne ich die Ortskurve in nD?

Gruß
student

06.02.2011, 13:06

Reksilat

Auf diesen Beitrag antworten »

Wieso Plural? Wie viele Schnittpunkte hast Du denn hier? Bzw. was willst Du eigentlich schneiden?

Falls Du die ganzen Basislösungen, also die Ecken der zulässigen Menge meinst, dann wirst Du dafür keine einfachere geschlossene Form finden, als ebene Dein Ausgangssystem. Der Simplex-Algorithmus durchwandert dann die Ecken und sucht nach der optimalen Lösung.

Gruß,
Reksilat.

08.02.2011, 15:48

_student_

Auf diesen Beitrag antworten »

Du hast natürlich recht. smile

Ich hatte ganz vergessen, dass wir es immer nur mit geraden Linien zu tun haben an deren Schnittpunkten (Ecken) sich der Simplex-Algo bis zum Optimum abarbeitet.

Vielen Dank nochmal Reksilat! Wink

Beste Grüße.
student

Neue Frage »

Antworten »

Optimierungsproblem Lineare Algebra

Verwandte Themen