Wie kann man ein System von Ungleichheiten lösen?
https://stackoverflow.com/questions/1432580
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe mein Problem (Tabellenlayoutalgorithmus) auf das folgende Problem reduziert:
Stellen Sie sich vor, ich habe n Variablen x1, X2, ..., XN. Ich habe auch einige (unbestimmte) Anzahl von Ungleichheiten wie:
X1 >= 2
x2 + X3 >= 13
usw.
Jede Ungleichungen sind eine Summe von einer oder mehreren Variablen und wird immer mit einer Konstante durch Verwendung des> = Operators verglichen. Ich kann nicht im Voraus sagen, wie viele Ungleichheiten ich jedes Mal haben werde, aber alle Variablen müssen nicht negativ sein, also ist das schon für jede Variable.
Wie kann ich dieses System so lösen, dass die Werte der Variablen so klein wie möglich sind?
Hinzugefügt: Lesen Sie den Artikel von Wikipedia und erkannten, dass ich vergessen habe zu erwähnen, dass die Variablen Ganzzahlen sein müssen. Vermutlich macht es das np-harte, oder?
Lösung
Minimierung von x1 + x2 + ... wobei die XI lineare Einschränkungen erfüllen, wird als lineare Programmierung bezeichnet. Es ist ausführlich in Details in Wikipedia
Andere Tipps
Was Sie haben, gibt es eine ziemlich grundlegende Lineares Programmieren Problem. Sie möchten die Gleichung maximieren X_1 + ... + X_n vorbehaltlich
X_1 >= 2
X_2 + X_3 >= 13
etc.
Es gibt zahlreiche Algorithmen, um diese Art von Problem zu lösen. Das bekannteste ist das Simplex -Algorithmus Dies löst Ihre Gleichung (mit bestimmten Vorbehalten) in dem durchschnittlichen Fall recht effizient, obwohl es LP -Probleme gibt, für die der Simplex -Algorithmus exponentiell viele Schritte zur Lösung (in der Problemgröße) erfordert.
Es gibt verschiedene Implementierungen von LP -Solvers. Zum Beispiel LP_SOLVE sollte die meisten Ihrer Anforderungen erfüllen
Sie können Ihr lineares Modell auch direkt auf die Neos -Plattform veröffentlichen (http://neos.mcs.anl.gov/neos/solvers/index.html). Was Sie einfach zuerst tun müssen, ist Ihr Modell in einer algebraischen Sprache wie Verstärkung zu schreiben. Dann löst Neos das Modell und gibt die Ergebnisse per E-Mail zurück.
