Simplex (lineare Optimierung)

[Dreas]

Hallo Leute,

hat sich von Euch schon mal jemand mit der Programmierung eines Simplex-Logarithmus auseinandergesetzt?
Es geht dabei um lineare Optimierung.
Ich möchte gern ein Programm zur Produktionsoptimierung schreiben.
Bsp.:
....................Artikel1...Artikel2..Kapazität
MaschineA..........5h.........2h......24h
MaschineB..........1h.........5h......24h
Montagegruppe..6h.........6h......36h
Gewinn/Stk.....500........800

Gewinn ist in Abhängigkeit der Kapazitäten (Nebenbedingungen) zu maximieren: z=500x1+800x2

Schriftlich sicherlich nicht zu schwer zu lösen. Aber ich habe Zweifel, wie ich das in Delphi am
geschicktesten angehe.
Immerhin muss ich mit Pivot-Tabellen und wohl auch mit Gauss rechnen.
Bis jetzt habe ich eine Eingabeform, auf der der Anwender die Anzahl der Artikel und die der Nebenbedingungen
auswählen kann. Dann wird eine Eingabematrix erzeugt, in die man die jeweiligen Werte eintragen kann.
Die Matrix ist ein StringGrid. Somit sind alle Werte, die zur Berechnung nötig sind definiert.
Ist aber der Weg über ein StrinGrid sinnvoll?
Es wäre echt toll, wenn jemand einen Denkanstoß geben könnte, wie ich die Berechnung am besten realisieren könnte.
Oder wenn jemand Internetseiten kennt, die sich damit auseinandersetzen (am besten mit Bezug zur Programmierung) bitte
auch posten.

Danke schon mal
MfG Dreas

[mika]

Ich kann die zwar leider nichtz weiterhelfen aber falls du eine Lösung findest (den Thread
hab ich erstmal zu den Lesezeichen hinzugefügt :) würd ich dich darum bitten mir die auch
zu erklären.

Ich schreib auch grade an einem Programm das die zu produzierenden Einheiten aus der Warenwirtschaft
der Firma ausliest und dann auf die in den Stammdaten eingetragenen Maschinen verteilt.
Wichtig ist ganz klar das alles rechtzeitig zum versprochenen Termin fertig wird.
Da am Abend alle produzierten Daten wieder eingelesen werden weiss man irgendwann welche
Artikel man am besten/schnellsten auf welcher Maschine produzieren muss. Schwierig dabei
ist das nur eine begrenzte Anzahl an Formen, die auf die Maschine aufgesetzt werden muss
um den Artikel zu produzieren, vorhanden ist und man möglichst wenig Formenumbauten
verursachen sollte.

Das Frontend für die manuelle Planung mit D&D ist schon fertig, soll aber eigentlich wenn der
Automatische Planer läuft nur im Notfall benutzt werden falls Spezielle Aufträge anfallen...



Gruß, Michel.


--
Auf jegliche orthographischen, grammatikalischen sowie regeln der interpunktion wurde mit
absicht verzichte :=)

[neolithos]

Ich habe mal ein Programm für mein Taschenrechner geschrieben! Bei jenem habe ich die Matrix genauso gebildet und berechnet wie ich es auf dem Papier machen würde.

Eigentlich hast du alles schon erkannt, du musst nur noch den Algorithmus implementieren.

Falls du noch Fragen zum Verfahren selbst hast, Frag einfach! Da kram ich auch noch mal meine Vorlesungsmitschriften aus.

[Dreas]

hi neolithos,

in was für einer Sprache hast Du denn das Programm für den Taschenrechner geschrieben?
Könnte ich mit dem Code evtl. was anfangen?
Es wäre nett, wenn Du deine Schritte bis zum Ergebnis kurz aufführen könntest.
Dann hätte ich schon mal einen groben Überblick, wie ich die Sache anpacken könnte.

@mika
Wenn ich das Simplex-Verfahren erfolgreich implementiert hab, geb ich dir Bescheid.
Von mir aus kannst du dann auch das ganze Proggi mit Code haben.

Gruss
Dreas

[neolithos]

Das Programm ist in Basic für den Casio 9850G. Habe leider kein Link-Kabel kann es also dir nicht geben. Leider ist das Dokument wo das Verfahren erklärt ist 2 Seiten und ich habe leider keinen Scanner.

Stichwort: Basisaustauschverfahren.

Das Anfangstableaus hast du ja schon.

Smybole:
c1x1+c2x2+...+cn*xn --> max

a11x1 + a12x2+...+a1nxn + xn+1 = b1
a21x1 + a22x2+...+a2nxn + xn+2 = b1
....
am1x1 + am2x2+...+amnxn + xn+m = b1

x1,x2,xn+m >= 0

[neolithos]

1. Simplex-Tableaus der Ausgangspunkt:

Code:

   | xN       | 1 
------------------
xB | A-1B AN  | xB
------------------
Z  | deltaN   | zakt

2. zakt = x(0) optimal

Kommst du bis hier klar?

[Dreas]

Habe das Programm soweit fertig.

Wenn noch Interesse an der Lösung besteht, bitte eben Bescheid sagen.
Dann schieb ich alles aufn Webspace.
Wäre auch nett, wenn einer, der eine Simplexaufgabe zur Hand hat, das Programm auf Richtigkeit testen könnte.

Ansonsten schönen Dank für die Hilfe bisher...

[HLukas]

Zitat:

Habe das Programm soweit fertig.

Vorstehender Beitrag ist schon etwas älter (2004). Aber wo ist
das Programm zum Testen?