Lösung für Simplex-Methode

[Superguppy]

Hallo Leute!

Ich soll für eine Freundin und deren Studienkollegin ein Lösungsprogramm für die Simplex-Methode programmieren. Ich habe ein paar handschriftliche Aufzeichnungen aus der Vorlesung von ihnen und sonst eigentlich nicht viel Ahnung. Mangels Wissen bezüglich der Rechentechnik an sich tu ich mir verdammt schwer, da etwas zu implementieren. :mad:

Eine umfangreiche Recherche im Internet hat mir auch nicht wirklich weiter geholfen. Es gibt unzählige kommerzielle Simplex-Löser zu finden. Auch gibt es die eine oder andere Lösung mit offenem Quellcode. Allerdings sind die alle derart komplex, dass ich das auch nicht als Anregung gebrauchen kann. Für mich von Interesse wäre ein möglichst einfach gehaltenes Programm. Es würde auch reichen, wenn man die Ungleichungen im Sourcecode fix einstellt - ich glaube, das würde den Aufwand schon ziemlich reduzieren.

Kann mir jemand von euch vielleicht mit guten Links oder Sourcecodes unter die Arme greifen? Es geht hier nicht um meine Note sondern ich mache das als freundschaftliche Hilfestellung, weswegen meine Motivation nicht so überragend ist, jetzt Bücher über Simplex zu kaufen und zu verstehen. Selbst machen kann sie es übrigens nicht, da sie noch NIE etwas programmiert hat, aber jetzt einfach so aus heiterem Himmel für die Mathe-Übung so etwas machen muss. Was sich der Professor dabei denkt, würde mich auch interessieren ... :rolleyes:

Danke schon im Vorraus!

[Senior Sanchez]

Naja, Simplex-Verfahren geht eigentlich.

Ich habe so etwas mal in gewisser Form in java geschrieben (für nen Wettbewerb), hat schon ne Weile gedauert. Aber man kann das auch algorithmisch durchziehen und das ging nach meinem Mathe-Skript auf Papier immer gut *g*

Blöd wirds nur, wenn man auch solche Dinge wie Phase-I (keine triviale Anfangslösung gefunden -> muss man über ne Art Vorsimplex eine finden) implementieren muss.

[pest]

Kann mir jemand von euch vielleicht mit guten Links oder Sourcecodes unter die Arme greifen? Es geht hier nicht um meine Note sondern ich mache das als freundschaftliche Hilfestellung, weswegen meine Motivation nicht so überragend ist, jetzt Bücher über Simplex zu kaufen und zu verstehen. Selbst machen kann sie es übrigens nicht, da sie noch NIE etwas programmiert hat, aber jetzt einfach so aus heiterem Himmel für die Mathe-Übung so etwas machen muss. Was sich der Professor dabei denkt, würde mich auch interessieren ... :rolleyes:


Ich kann's dir erklären, ist im Prinzip nur nen simpler Gauss-Algorithmus mit minimierendem Basistausch
es gibt aber verschiedene Tabellierungstechniken, was dann einfacher zu programmieren ist, musst du entscheiden

Und wenn du die Normalform als gegeben voraussetzt ist es eine Arbeit von 15 Min ;)


Blöd wirds nur, wenn man auch solche Dinge wie Phase-I (keine triviale Anfangslösung gefunden -> muss man über ne Art Vorsimplex eine finden) implementieren muss.

man bildet mit den Spaltensummen der NBV eine zusätzliche Zielfunktion

[Senior Sanchez]

man bildet mit den Spaltensummen der NBV eine zusätzliche Zielfunktion

Das weiß ich durchaus ;-)
Es ist aber eben ein Fall den es noch zu beachten gilt und jeder zusätzliche Fall ist immer doof.

[pest]

here we go ;)

Vorgeplänkel:
der Simplexalgorithmus findet im Durchschnitt der Halbebenen (bei vorgegebener gültiger Anfangslösung/Ecke) in
endlich vielen Schritten eine Optimallösung (man wandert von einer Ecke des zulässigen Bereichs zur Nächsten,
der minimierende Basistausch garantiert das wir uns mit jedem Schritt verbessern)

ich mach es am Bsp. dieser Aufgabe
die Variante minimiert, für maximieren einfach das VZ der Zielfunktion (ZF) umdrehen und den größten ZF-Koef. zur Bestimmung
der Pivotspalte benutzen


4x1 + 8x2 <= 96
8x1 + 4x2 <= 120
6x1 <= 78
x1>=0, x2>=0

z=-12x1-8x2 -> min!


Normalform mit Hilfe von Schlupfvariablen einführen (das sind unsere Basisvariablen (BV))
3 lin. unabh. Gleichungen = 3 BV


4x1 + 8x2 + x3 = 96
8x1 + 4x2 + x4 = 120
6x1 + x5 = 78


jetzt stellen wir unser Starttableau als Matrix (2D-Array ;) mit dem man rechnen kann) auf

beachte das wir -z Minimieren! Die BV bilden die Zeilen, die NBV (Nebenbedingungsvariablen) die Spalten
dann die Koeffizienten eintragen, d.h. für die Aufg. reicht eine 4x3 Matrix


| x1 x2 |b
x4| 4 8 |96
x5| 8 4 |120
x6| 6 0 |78
----------------
-z| -12 -8 | 0


damit haben wir eine erste zBl (zulässige Basislösung)
einfach die Zeilen lesen x_0 = [x1,x2,x3,x4,x5] = [0,0,96,120,78]

Jetzt die Pivotspalte bestimmen (die Spalte mit dem kleinsten ZF Koeffizienten, hier -12), dann die Pivotzeile (nur pos. Elemente) bestimmen
(kleinster Wert der sich bei Division mit der b-Spalte ergibt, ZF Zeile wird außen vor gelassen)

also 78/6=13 => kleinster Wert in Spalte 1
damit ergibt sich das Pivotelement 6

das heißt wir können BV x6 mit NBV x1 austauschen

Umrechnungsformeln:
Pivotelement = 1/Pivotelement
Pivotspalte = Pivotspalte/-Pivotelement
Pivotzeile = Pivotzeile/Pivotelement
restl. Element = Element - (ElementPivotspalte * ElementPivotzeile)/Pivot

also Zeile für Zeile
4/-6 = -2/3
8-(0*4)/6 = 8
96-(78*4)/6 = 44

8/-6 = -4/3
4-(0*8)/6 = 4
120-(78*8)/6 = 16

1/6 = 1/6
0/6 = 0
78/6 = 13

-12/-6 = 2
-8 - (0*-12)/6 = -8
0 - (78*-12)/6 = 156


| x6 x2 |b
x4| -2/3 8 |44
x5| -4/3 4 |16
x1| 1/6 0 |13
--------------------
-z| 2 -8 |156


unsere neue (bessere Ecke) x_1 = [x1,x2,x3,x4,x5] = [13,0,0,44,16]

Alle ZF-Koeffizienten müssen > 0 sein, wir sind noch nicht fertig ;)
selbes Spiel von vorn
-> Spalte 2 Pivotspalte, 4 ist Pivotelement, wir können x5 mit x2 tauschen,analoge Rechnung


| x6 x5 |b
x4| 2 -2 |12
x2| -1/3 1/4 |4
x1| 1/6 0 |13
--------------------
-z| -2/3 2 |188


immernoch nicht fertig, aber bessere Ecke x_2 = [x1,x2,x3,x4,x5] = [13,4,0,12,0]
wir tauschen x4 mit x6


| x4 x5 |b
x6| 1/2 -1 |6
x2| 1/6 -1/12 |6
x1| -1/12 1/6 |12
--------------------
-z| 1/3 4/3 |192


alle ZF-Koef. sind > 0 -> fertig!
x_3 = [x1,x2,x3,x4,x5] = [12,6,0,0,6]

oder im Entscheidungsraum x* = [12,6]
Optimallösung z* = -192

wie gesagt die Theorie ist nicht einfach aber der Algorithmus super einfach :)
du schuldest mir 20min ;)

[Superguppy]

Ich kann's dir erklären, ist im Prinzip nur nen simpler Gauss-Algorithmus mit minimierendem Basistausch
Öh, was bitte? :confused: Mein Problem ist, dass ich an der FH Informatik studiere und wir dort nur sehr wenig Mathematik haben. Wir haben gerade erst am Ende vom zweiten Semester die Grundlagen von Matrizen gemacht. Soviel zu meinen spärlichen Vorkenntnissen.

ich ess' noch dann mach ich weiter ;)
Sehr nett von dir! :) Ich bin schon gespannt, ob ich das trotz fehlender Vorkenntnisse schnallen werde. Naja, wenn nicht halt die Freundin ein Pech gehabt.

[ESAD]

muss als programm abgegeben werden?
sonst kann man sowas mit einem minimum an aufwand mit excel lösen

wennst willst kann ich dir meine unterlagen raussuchen (sind noch aus der htl) ham das in betriebswirtschaft gemacht

[pest]

Sehr nett von dir! :) Ich bin schon gespannt, ob ich das trotz fehlender Vorkenntnisse schnallen werde. Naja, wenn nicht halt die Freundin ein Pech gehabt.

Du musst es garnicht schnallen, sind ja praktisch nur 4 Rechnungen
viel Spass

[Superguppy]

Als Excel haben es die beiden Damen schon zusammen gebracht ... das ist mehrseitig und absolut nicht beschriftet. Daher für mich nur bedingt zu gebrauchen.

Abgegeben werden muss es als Programm, wobei die Programmiersprache völlig egal ist. Ich sage mal die HTL-Unterlagen könnten eher etwas für mich sein. Von Senior Sanchez habe ich zwar schon Uni-Unterlagen, aber die überfordern mich ziemlich. Vielleicht kapier ich es ja mit den HTL-Unterlagen und wenn nicht ... haben die beiden halt Pech gehabt. Ich hab eh schon viel Zeit hinein gesteckt, ohne ein Ergebnis. :(

EDIT: Lassen wir das mal mit den HTL-Unterlagen ... danke trotzdem derweilen! Ich werds mal versuchen anhand von Pests Anleitung zu verstehen.

[Pinoccio]

Hier (http://www.jumland.de/linnk/Software_Entwic/Softwareprojekt/Softwareprojekt.html) gibt es eine JAVA-Version.

Bitte schön Quellen angeben und Urhhebrrechte beachten. Aber als Inspiration sollte es reichen.


Verdammt, in dem Jar sind ja nur die kompilierten drinne, vergiß meinen Beitrag. :-(

mfg

[jumland]

Hier (http://www.jumland.de/linnk/Software_Entwic/Softwareprojekt/Softwareprojekt.html) gibt es eine JAVA-Version.

Bitte schön Quellen angeben und Urhhebrrechte beachten. Aber als Inspiration sollte es reichen.


Verdammt, in dem Jar sind ja nur die kompilierten drinne, vergiß meinen Beitrag. :-(

mfg

Hallo!

Ich habe - als ich heute in die Logs geschaut habe - diesen Thread entdeckt. Das Programm wurde von mir und meinem Programmierpartner entwickelt und es steht freit zur Nutzung!

Solltest du an den Quelldateien interessiert sein, wären wird bereit dir diese zuzuschicken. Die Sourcedateien sind ausführlich dokumentiert!

Das Programm funktioniert einwandfrei (kannst du ja schonmal testen ;)). Die Klassen sind sauber getrennt und du kannst die Logik des Programms auch ohne die Grafik verwenden oder eine andere Grafik aufsetzen!


Viele Grüße,
Jens Umland

--
www.jumland.de

[pest]

mir war heut langweilig deswegen hab ich das mal schnell in 70 Zeilen C gequetscht ;)

parsing der Eingabe hab' ich angefangen aber dann keinen Bock mehr gehabt als es länger als der Algorithmus wurde ;)

der Algorithmus minimiert und arbeitet in-situ
das Starttableau ist hartkodiert + alle ZF-Koef müssen kleiner 0 sein
es wird getestet ob der zulässige Bereich beschränkt ist
Vertauschungen werden nicht gespeichert, deswegen wird nur der Optimalwert ausgegeben

man müsste noch Fallunterscheidungen hinzufügen wenn die Lsg nicht eindeutig ist oder 0 keine zBl ist


Ausgabe beim Beispiel von oben



n = 1
4.000 8.000 | 96.000
8.000 4.000 | 120.000
6.000 0.000 | 78.000
---------------------------------
-12.000 -8.000 | 0.000

n = 2
-0.667 8.000 | 44.000
-1.333 4.000 | 16.000
0.167 0.000 | 13.000
---------------------------------
2.000 -8.000 | 156.000

n = 3
2.000 -2.000 | 12.000
-0.333 0.250 | 4.000
0.167 0.000 | 13.000
---------------------------------
-0.667 2.000 | 188.000

n = 4
0.500 -1.000 | 6.000
0.167 -0.083 | 6.000
-0.083 0.167 | 12.000
---------------------------------
0.333 1.333 | 192.000

Optimalwert z* = -192.00
Optimalstelle x* = [12.00 6.00]



Ausgabe beim Beispiel von Wikipedia (http://de.wikipedia.org/wiki/Simplex-Verfahren)



n = 1
1.000 2.000 | 170.000
1.000 1.000 | 150.000
0.000 3.000 | 180.000
---------------------------------
-300.000 -500.000 | 0.000

n = 2
1.000 -0.667 | 50.000
1.000 -0.333 | 90.000
0.000 0.333 | 60.000
---------------------------------
-300.000 166.667 | 30000.000

n = 3
1.000 -0.667 | 50.000
-1.000 0.333 | 40.000
0.000 0.333 | 60.000
---------------------------------
300.000 -33.333 | 45000.000

n = 4
-1.000 2.000 | 130.000
-3.000 3.000 | 120.000
1.000 -1.000 | 20.000
---------------------------------
200.000 100.000 | 49000.000

Optimalwert z* = -49000.00
Optimalstelle x* = [130.00 20.00]



Quellcode



#include <stdio.h>
#include <stdlib.h>

void printvec(float *vec,int n)
{
int i=0;
printf("[");while (i<n){if (i>0) printf(" ");printf("%0.2f",vec[i]);i++;};printf("]\n");
}

void printtab(float *tab,int n,int m)
{
int i,j;
float *ttab=tab;
for (i=0;i<n;i++) {
if (i==n-1) printf("---------------------------------\n");
for (j=0;j<m-1;j++) printf("%10.3f",ttab[j]);
printf(" | %10.3f\n",ttab[j]);
ttab+=m;
};printf("\n");
}

int simplex(float *tab,int n,int m,float *xopt,float *minzf)
{
const int m1=m-1; /* Dimension der Koef-Matrix */
const int n1=n-1;
const int nbl = n1+m1;

int i,j,pr,pc,itmp,count,ret;
int *bl;
float fmin,ftmp,pvt;
float *ttab,*utab,*zftab;

bl=(int*)malloc( nbl * sizeof(int)); /* Position der BV+NBV */
for (i=0;i<nbl;i++) bl[i] = i;
for (i=0;i<m1;i++) xopt[i]=0.;

ret=0;count=1;
*minzf = 0.;zftab = &tab[n1*m]; /* Ptr auf ZF */
while (1) {
printf("n = %i\n",count);
printtab(tab,n,m);

/* Pivotsuche, bestimme Pivotspalte pc*/
fmin=*zftab;pc = 0; /* suche kleinsten ZF-Koef*/
for (i=1;i<m1;i++) if (zftab[i] < fmin) {fmin=zftab[i];pc=i;};
if (fmin>0) break;/* alle ZF-Koef >0 */

/* bestimme Pivotzeile pr=min{b/Pivotspalte} */
/* ttab=Ptr auf Pivotspalte,utab=Ptr auf b */
ttab = &tab[pc];utab = &tab[m1];
fmin=1e30;pr = -1;
for (i=0;i<n1;i++) {
if (*utab < 0.) {ret=-2;break;}; /* keine zBl */
if (*ttab > 0.) {
ftmp = *utab / *ttab;
if (ftmp < fmin) {fmin=ftmp;pr=i;};
}
utab+=m;ttab+=m;
}
if (pr==-1) {ret=-1;break;} /* Unbeschraenktheitstest */

/* Umrechnung (inplace) */
itmp=bl[pc];bl[pc] = bl[m1+pr];bl[m1+pr]=itmp; /* Tausche BV/NBV */
/* alle Elem. außer Pivotzeile/spalte */
/* ttab=Ptr auf Matrix[0,0],utab=Ptr auf Pivotzeile, pvt=Pivotelement*/
ttab = tab;utab = &tab[pr*m];pvt = utab[pc];
for (i=0;i<n;i++) {
if (i!=pr) for (j=0;j<m;j++) if (j!=pc) ttab[j] -= (utab[j]*ttab[pc])/pvt;
ttab+=m;
}
/* Pivotzeile/spalte, ttab=Ptr auf Pivotspalte*/
ttab = &tab[pc];
for (i=0;i<n;i++) {
if (i==pr) {
for (j=0;j<m;j++) {if (j!=pc) utab[j] /= pvt;else utab[j] = 1./pvt;};
} else *ttab /= -pvt;
ttab+=m;
}
count++;
}

/* bestimme Optimalwert/stelle, ttab=Ptr auf b*/
ttab = &tab[m1];
for (i=m1;i<nbl;i++) {if (bl[i] < m1) xopt[bl[i]] = *ttab;ttab+=m;}
*minzf=-tab[n*m-1];

free(bl);
return ret;
}

static float mytab[] = {
4.0,8.0,96.0,
8.0,4.0,120.0,
6.0,0.0,78.0,
-12.0,-8.0,0.0};

const int n=4;
const int m=3;

int main(int argc, char *argv[])
{
int ret;
float minzf;
float xopt[m-1];
printf("Simplex by pest\n\n");
ret = simplex(mytab,n,m,xopt,&minzf);
if (ret==-1) printf("LP unbeschränkt\n");
else if (ret==-2) printf("Basislösung nicht zulässig\n");
else {
printf("Optimalwert z* = %0.2f\n",minzf);
printf("Optimalstelle x* = ");printvec(xopt,m-1);
}
return 0;
}



für Fehler in der Beschreibung des Simplex haftet mein Gedächtnis ;) + es geht sicherlich noch kürzer+intelligenter
edit: uh seh grad, mein Programm braucht 3mal weniger Schritte als Obiges ;) :)

[Superguppy]

pest, ich bin beeindruckt! Ich hatte heute Abend ernsthaft mit dem angefangen, nach einer händisch durchgerechneten Vorlage auf kariertem DIN A4 Papier. Ich werde mir erlauben, deinen Code noch etwas zu kommentieren und an die beiden Mädels weiterzugeben. Falls du Interesse an einer Dankesmail von den beiden hast, lass mir doch deine Mailadresse per PN zukommen. :smile:

:umassa: ... Hut ab!

[pest]

klar kein Problem, aber kopier's erst morgen Nachmittag, ich kuck dann nochmal drüber

[Superguppy]

const int n=4; ... ist die Anzahl der Iterationen
const int m=3; ... ist die Anzahl der Gleichungen

Hab ich das soweit eh richtig gesehen?

Achja, interessant finde ich auch, dass die beiden in ihren Mitschriften irgendwelche Koeffizienten alpha, beta, gamma und delta haben, die mir in dem Wiki-Beispiel irgendwie fehlen. :confused:

[pest]

const int n=4; ... ist die Anzahl der Iterationen
const int m=3; ... ist die Anzahl der Gleichungen


n ist die Anzahl der Zeilen ((n-1)=Anzahl der Gleichungen)
m die Anzahl der Spalten (m-1)=Anzahl der NBV)

ich kann auch noch ein paar Kommentare einfügen, frage mich gerade warum ich die Matrix mit nem 1D-Array mache :|,
naja vielleicht benutzt es mal jmd. bei 1000 NBV oder so :D

Iterationen braucht es bis es fertig ist



Achja, interessant finde ich auch, dass die beiden in ihren Mitschriften irgendwelche Koeffizienten alpha, beta, gamma und delta haben, die mir in dem Wiki-Beispiel irgendwie fehlen. :confused:

wie gesagt man kann das Tableau auch anders aufbauen
ich will die Optimalstelle noch bestimmen, sonst ist es ein wenig witzlos

[pest]

hab's noch kommentiert und ein paar Funktionen hinzugefügt, hoffe du verstehst das irgendwie ;)

[Superguppy]

Ich habe schon fast ein schlechtes Gewissen, weil du so viel Zeit für mich investierst. Vielen herzlichen Dank! =)

[elianda]

Hmm eigentlich gibts dazu das Standardwerk "Numerical Recipes in C" bzw. "Numerical Recipes in Fortran":

http://www.nrbook.com/a/bookcpdf.php