Lineares Optimierungs-Problem lösen.

[Jürgen W. (lovos)]

Hallo,
es geht um die Optimierungsaufgabe in
http://optimierung.mathematik.uni-kl.de/mamaeusch/aktivitaeten/lehrerfortbildung/uebungen_ddorf121103.pdf
http://optimierung.mathematik.uni-kl.de/mamaeusch/aktivitaeten/lehrerfortbildung/loesungen_ddorf121103.pdf

Der Simplex-Algorithmus funktioniert hier vermutlich nicht, aber ohnehin 
wollte ich die Lösung heuristisch finden mit einem selbstgeschriebenen 
Computerprogramm, welches alle Kombinationen in der "feasible region" 
durchprüft.
Ich habe 11 (Un-)Gleichungen.

$$(1)~ 2 x_1 + 50 x_2 + 6 x_3 + 74 x_4 \leq 60$$

$$(2)~ 2 x_1 + 50 x_2 + 6 x_3+ 74 x_4 \geq 54$$

$$(3)~ 1 x_1 + 75 x_2+ 13 x_3+ 96 x_4 \leq 80$$

$$(4)~ 1 x_1 + 75 x_2+ 13 x_3+ 96 x_4 \geq 39$$

$$(5)~ 5 x_1 + 83 x_2+ 5 x_3+ 105 x_4 \leq 90$$

$$(6)~ 5 x_1 + 83 x_2+ 5 x_3+ 105 x_4 \geq 24$$

$$(7)~ x_1 + x_2 + x_3 + x_4 = 1$$

$$(8)~ x_1 \geq 0$$

$$(9)~ x_2 \geq 0$$

$$(10)~ x_3 \geq 0$$

$$(11)~ x_4 \geq 0$$

Ich würde jeweils 4 herausnehmen, das LGS (Lineare Gleichungssystem) 
lösen, und die Lösung in die restlichen 7 Ungleichungen einsetzen, um 
festzustellen, ob alle Ungleichungen erfüllt sind.
4 aus 11 ergibt 330 Möglichkeiten, aber die Gleichung (7) muss bei jeder 
Kombination dabei sein, und die Ungleichungen 1 und 2 sind linear 
abhängig (auch 3/4, 5/6) und dürfen nicht gemeinsam in einem LGS 
vorkommen. Das reduziert die Möglichkeiten auf 96.
D.h. Von den 96 sind vielleicht ca. 50 gültig, mit diesen berechne ich 
jeweils die Optimierungsfunktion, und dann habe ich die optimale Lösung.
Das kann ein PC leicht schaffen.
Frage: Hat jemand sowas schon mal gemacht? Welche PC-Software gibt es, 
die sowas bewerkstelligen kann?

[Walter T. (nicolas)]

Also eigentlich hast Du hier nur 8 Zwangsbedingungen, von denen 7 
Ungleichheitszwangsbedingungen sind. Es fehlt noch die Zielfunktion (die 
Funktion, die minimiert werden soll.

Ehrlich gesagt verstehe ich nicht, was Du mit 330 Möglichkeiten und 
einer Heuristik meinst. Die Zahlen dürften ja keine ganzen Zahlen sein, 
also gibt es unzählich viele Lösungen, von denen entweder die gesamte 
Pareto-optimale Lösungsmenge oder nur eine Teillösung gefragt ist.

Für solche Aufgabenstellungen ist Matlab sehr gut, da man die 
Hyperflächen für die Zwangsbedingungen und den Lösungsverlauf 
komfortabel darstellen kann und mit fmincon auch ein sehr 
leistungsfähiger Optimierer vorhanden ist.

Viele Grüße
Nicolas

[Tux (Gast)]

Also mit Optimierung habe ich mich noch nicht beschäftigt aber ich würde 
mal die "üblichen Verdächtigen" versuchen also Oktave bzw. Matlab oder 
Mathematica damit geht jedenfalls QR bzw. LR Zerlegung und ähnliches.

[ich (Gast)]

Aus meiner Sicht eine klassische Simplex-Aufgabe.

Btw. Die Kostenfunktion fehlt oben. In der Aufgabe steht sie.

Den Goooogler nach Simplex fragen und irgendein Java-Applet verwenden. 
Fertig.

[ich (Gast)]

http://www.simplexme.com/de/

z.B. ;P

[Jürgen W. (lovos)]

> Es fehlt noch die Zielfunktion (die Funktion, die minimiert werden soll.

Man muss zuerst die Aufgabe lesen und vllt. die Lösung anschauen.
Da steht alles drin.

> Ehrlich gesagt verstehe ich nicht, was Du mit 330 Möglichkeiten

$${11 \choose 4} = 330$$

>einer Heuristik meinst.
vllt. der falsche Audruck. Ich meinte nicht mit ausgefeilten Algorithmen 
lösen z.B. Simplex-Tableau, sonder Ausrechnen aller Schnittpunkte und 
Minimum durch probieren suchen

>also gibt es unzählich viele Lösungen
Im Prinzip schon, d.h. die feasible region umfasst unendliche viele 
Punkte.
Aber nicht alle sind optimal hinsichtlich der Optimierungsfunktion.

[Jürgen W. (lovos)]

http://www.simplexme.com/de/
Ergebnis ist angehängt.
Echt cool.

[daniel root (Gast)]

http://www.gnu.org/software/glpk/

dürfte straight forward übersetzbar sein

[Lothar Feige (Gast)]

hallo,

das mit dem simplexme, war eine feine Sache, allerdings gibt es diese 
seite jetzt nichtmehr.
ich befasse mich auch mit diesen aufgaben, habe auch einige schon 
gelöst, mit block, lineal und Kuli und Taschenrechner mit 
bruchfunktion... www.feinet.de  neben anderem ist da auch ein link, zu 
den simplexaufgaben.

meine frage, haben sie zufällig kontakt zu den Urhebern der simplexme 
seite?
die hatten da ein super Programm geschrieben, aber es gibt diese seite 
nichtmehr. uni Mannheim müsste das gewesen sein.

falls sie mehr wissen, bitte kurze E-Mail an mich, Lothar feige,

[e-mail]

Danke.

Gruß von Lothar Feige

[Lothar Feige (Gast)]

Wieso soll der Simplex da nicht funktionieren, bzw. solver?

nur bei minimierungsaufgaben, muss man das dualtheorem einführen, um die 
aufgabe "normal" ablesen zu können.

Falls Interesse besteht, ich löse die Aufgaben auch Händisch und mit 
Block und Stift, und Taschenrechner mit Bruchfunktion, wegen der 
abstruden Zahlen...

lassen Sie es mich wissen, ich bin immer erfreut, interessierte zu 
finden.

Gruß von Lothar Feige von www.feinet.de   da gbt es auch eine Seite zu 
den Simplexaufgaben.... Nur Mit.

Gruß von Lothar Feige

[Purzel H. (hacky)]

Das Ganze sollte nicht allzu kompliziert sein. Die Zahlen sind zwischen 
null und eins, mit Summe gleich eins. Dann folgen 6 ungleichungen mit 4 
unbekannten.

Also mal auf gleichheit loesen, und dann anmalen was aussen und innen 
ist

[Lothar Feige (Gast)]

Falls Interesse besteht, die Aufgaben der Linearen Optimierung, auf 
einfache Art und Wise zu lösen:

http://www.feinet.de/lieneop/mausgang.htm

Ich habe dort mal eine Aufgabe ins Netz gestellt, noch eine 
interessante:

Minimierungsaufgabe, Zuschnittsproblem:

http://www.feinet.de/lieneop/zuschnit1.htm

Wie gesagt, falls Interesse besteht, die simplexme.com/de Seite besteht 
wieder, ich habe mich mit einem der Autoren in Verbindung gesetzt.

Gruß von Lothar Feige

Suche noch andere, Interessierte, am Linearen Optimieren, Min- Max- 
Aufgaben, (Statistik hätte ich noch im Angebot:


http://www.feinet.de/stapage/statisti.htm

Das Lösen von Transportproblemen auch, aber da gibt es auch vernünftige 
Bücher. Gruß von Lothar Feige