Hallo,

wir haben zur Aufgabe, ein Programm zu schreiben, dass eine jeweils optimale Lösung ausgibt.
Eine Zielfkt. soll max. od. min. werden in Abhängigkeit von div. Nebenbedingungen.
Das geht am besten mittels Simplex-Methode.
Nur fehlt uns irgendwie das Grundgerüst, worauf wir aufbauen können.
Wir sind nicht sicher, wie man diese Art Aufgaben am sinnvollsten programmiert.
Hat von Euch schon mal jemand an so einer Fragestellung gearbeitet und kann Denkanstöße liefern?
Oder kennt Ihr Internetseiten, die sich damit auseinandersetzen (mit Delphi-Bezug)?

Danke schon mal...


Moderiert von UGrohne: Topic aus Sonstiges verschoben am So 16.10.2005 um 06:46

Ja die lineare Optimierung kann auf Basis des Simplex-Algorithmus optimale Lösung bei sbsoluter Linearität des Problems finden. Der einfache Simplex-Algorithmus ist im Buch Numerical Recipes in Pascal beschrieben. Die Quelltexte sind im Web frei downzuladen. Glaube aber nicht, dass man sowas einfach abtippen sollte, da man hier schon verstehen muß, was der Algorithmus macht, sonst erkennt man eventuelle Fehlfunktionen nicht. Simplex selber ist ein 20´Zeiler, maximal, also keine große Sache. Es gibt aber etliche Erweiterungen. Weiteres auf Anfrage.

Grüße // Martin

Weiteres auf Anfrage - da lass ich mich ned lange bitten
Ich hab für ne VU auf der Uni ebenfalls ein lineares Problem zu lösen - Verfahren egal. Anbieten tut sich natürlich auch hier der Simplex-Algorithmus
(Alternativen die mir einfallen wären z.B. Ellipsoidmethode, da für hinreichend viele Variable (und bei mir sind es 250 000) schneller, aber wesentlich komplexer und daher nicht so einfach zu verstehen)

Simplex-Verfahren geht ja immer von einer Ecke des durch die (Un)gleichungen entstandenen Polyeders zu einer mit einer besseren Bewertung (also höherem Zielfunktionswert). Wenns keine bessere Ecke mehr gibt, hab ich eine optimale Lösung.

Mein Problem ist jetzt folgendes: Ich brauch als allererstes mal eine gültige Startlösung. Da mein Problem durch Gleichungen gegeben ist, kann ich nicht einfach die Null als Ausgangspunkt wählen, was ja bei Ungleichungen oft möglich ist.
Außerdem will ich wenn möglich einen Zwei-Phasen-Simplex vermeiden, da dieser (Code und Laufzeit) aufwändiger ist. Außerdem ist die Startlösung beim Zwei-Phasen-Simplex alles andere als gut (zumindest im Allgemeinen).
Ich will jetzt mal wissen: Muß ich überhaupt an einem Eck des Polyeders beginnen? Oder reicht es, auf einer Seitenfläche zu starten? Da könnte man gute (heuristische) Startlösungen verwenden.
Weiters: Um die Laufzeit gering zu halten, empfiehlt sich ein Netzwerk-Simplex. Was ist genau der Unterschied, bzw. was bringt er wirklich?

Danke!
Stephan