Simplexalgorithmus für Minimierung, wie vorgehen?

Aufrufe: 120     Aktiv: 27.10.2022 um 13:58

0

Hallo, kann mir jemand den Simplex Algorithmus vielleicht kurz erklären?

 

Ich habe eine Aufgabe aus dem realen leben, bei der ich vermutlich den Simplex bräuchte und die in etwa so aussieht:

Matrix M, Eingabevektor e und Ausgabevektor a mit

M*e=a

Die Elemente in M und e=(e1,e2,...,en) sind aus {0,1} und a=(a1,a2,...,an) soll Zahlen >=1 enthalten.

 

Konkret ist M fest vorgegeben und ich suche die e1-en so dass einerseits wie gesagt a1-an>=1 weiterhin erfüllt ist und aber

die Summe von e1-en so klein wie möglich ist.

Es sollen alle möglichst viele Werte ei gleich 0 sein und nur wenige 1.

 

Ich würde vermuten dass es hier um einen Fall für den Simplexalgorithmus geht da ich ja lineare Ungleichungen (mit Variabeln e1-en), die Alle >=1sein sollen.

Und unter diesen Bedingungen

f(e,...,en)e1+e2+...+en minimiert werden soll.

Kann mir Jemand sagen wie ich das angehen könnte?

 

Müsste da ein systematisches Vorgehen wissen da in meienr ufgabe seeeeehr viele Variabeln da sind und ich das daher in Java programmieren will, also es automatisch gelöst wird.

Diese Frage melden
gefragt

Student, Punkte: 304

 

Könntest Du vor dem Posten grundsätzlich Dein Pamphlet nochmal Korrektur lesen und die Leerzeilen entfernen? Schreib doch erstmal dafür ein Java-Programm!   ─   mikn 26.10.2022 um 21:32
Kommentar schreiben
1 Antwort
0
So eine Aufgabe ist gar nicht so trivial. Man sollte sich also zunächst grundsätzlich mit der Theorie eines solchen Verfahrens befassen, bevor man sich an eine Implementierung wagt. Und auch dann sollte man die eigene Implementierung anhand einfacher Beispiele durchrechnen, um zu schauen, ob das Verfahren funktioniert. In Anlehnung an deine andere Frage mit einer Matrix der Dimension $13\cdot 10^6\times 13\cdot 10^6$ ist dabei natürlich noch zu überlegen, ob das überhaupt umsetzbar ist. Matlab liefert dafür beispielsweise eine Größe von 125949.1 Gigabyte nur für die Matrix! Da deine Matrix $M$ ganz offensichtlich dünnbesetzt ist (viele Nullen), bietet es sich also an, mit einer entsprechenden Datenstruktur zu arbeiten. Matlab braucht für eine Matrix nur aus Nullen bereits ca. 100 MB Speicher. Für eine dünnbesetzte Matrix, die ca. 8 Mio. Einsen enthält (von 169 Bio. Einträgen) werden schon ca. 375 MB benötigt. Ist also auch eine Frage, wie viele Einsen letztendlich bei so vielen Einträgen vorkommen.

Du müsstest dir also auch erst einmal überlegen, wie du das in Java umsetzen kannst, bevor du damit dein Problem lösen kannst. Mit einem zweidimensionalen Array als Matrixstruktur kommst du damit jedenfalls nicht weit. Immerhin musst du die Daten ja auch verarbeiten. Für die Erstellung oben genannter Matrix mit zufallsgenerierten Einsen benötigt Matlab bspw. schon um die 10 Sekunden (ist jetzt auch nicht der schnellste Rechner). 

Bevor man also "mal eben" so ein Verfahren umsetzt, steht man also vor vielen anderen Problemen. Da frage ich mich natürlich, woher diese Anwendung kommt und was das Ziel ist.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 26.5K

 

Naja, Hintergrund ist mal wieder was Dämliches:
Ich will eine Liste an Lottozahlentipps finden, die möglichst klein ist und aber 3 Richtige garantiert.
ALso egal welche 6 Zahlen gezogen werden, irgendeine zahlenkombi aus der Liste hat 3+ gemeinsame Zahlen.

Dazu will ich erst ml abstrahieren, von allen möglichen 6stelligen Lottozahlen, welche mit welcher "in Verbindung ist", also 3+ Zahlen teilt.


Un diese "Verbindungsmatrix" hat dann halt im worst case sehr sehr viele EInträge.
Gut, wenn man die Symmetrie beachtet, sind es maximal (49 über 6)*(49 über 6 +1)/2=9.7773562e+13 , also ca. so 10^14 Einträge.

Natürlich sind bestimmt viele davon Null, aber ja.... geprüft werden müssen sie am Anfang ja doch damit man weiß ob an der Stelle in der Matrix eine 1 oder eine 0 steht.

  ─   densch 27.10.2022 um 13:34

Gerade bei Problemen in dieser Größenordnung muss man Symmetrien etc. ausnutzen, siehe Antwort. Ich bin mir aber auch sicher, dass man dieses Problem viel eleganter lösen kann, da du ja höchstens 49 Tipps brauchst. Und das ist dann wieder eine ganz andere Größenordnung als 10^14!   ─   cauchy 27.10.2022 um 13:45

Ach, das mit den 49 Tipps ist natürlich Blödsinn. Ich bin halt nicht im Thema drin. Aber es sollte doch auch einfach über Binomialkoeffizienten zu berechnen sein.   ─   cauchy 27.10.2022 um 13:58

Kommentar schreiben