Kombinationsoptimierung Das Problem hat seine eigenen Schwierigkeiten. Es gibt mehrere Modellierungsmethoden für dasselbe Problem, und jedes Modell hat seine eigenen Vor- und Nachteile. Das Modellieren ist wichtig. Hier erklären wir am Beispiel des Problems der Behälterverpackung, wie man es entwickelt.
| Bei einer Box mit einer Kapazität von $ c (\ gt 0) $ und $ n $ Gepäckstücken $ N = \ {1, \ dots, n \} $. Die Kapazität des Gepäcks $ i \ in N $ sei $ w_i (\ gt 0) $. Finden Sie ein Sortiment, das die Anzahl der Kisten minimiert, die zum Packen Ihres gesamten Gepäcks benötigt werden. |
Wenn Sie beispielsweise einige schwere Gegenstände auf einem 10-Tonnen-LKW tragen, ist es ein Problem, nach möglichst wenigen LKWs zu fragen.
Referenz [Problem beim Packen des Behälters - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD % E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C)
Formulieren wir es so wie es ist.
| Einstufige Formulierung | ||
| $ \ mbox {Ziel} $ | $ \ sum_i {y_i} $ | Anzahl der Felder |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Gibt an, ob die Box $ j $ in das Gepäck $ i $ gelegt werden soll |
| $ y_j \ in \ {0, 1 \} ~ \ forall j $ | Gibt an, ob Box $ j $ verwendet werden soll Herr Geben Sie $ i $ in eines der Felder ein | |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Füllen Sie die Kapazität des Felds $ j $ aus | |
| $ x_ {ij} \ le y_j ~ \ forall i, j $ | Einschränkungen für $ y $ | |
Tatsächlich ist diese Formulierung für Löser schwer zu lösen und sehr zeitaufwendig zu berechnen.
Infolgedessen ist es schneller, die Anzahl der Kästchen festzulegen, zu prüfen, ob es eine Lösung gibt, und die Anzahl der Kästchen in der äußeren Schleife zu ändern.
Die Formeln A und B, wenn die Anzahl der Kästchen festgelegt ist, sind unten gezeigt.
| Zweistufige Formulierung A | ||
| $ \ mbox {Objective} $ | Keine | weniger Gibt an, ob das Feld $ j $ in i $ eingefügt werden soll |
| $ \ mbox {vorbehaltlich} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Gepäck Geben Sie $ i $ in eines der Felder ein |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Füllen Sie die Kapazität des Felds $ j $ aus | |
| Zweistufige Formulierung B | ||
| $ \ mbox {Ziel} $ | $ y $ | Überkapazität |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Gibt an, ob die Box $ j $ in das Gepäck $ i $ gelegt werden soll |
| $ y \ ge 0 $ | Überschreitung der Kapazität | |
| $ \ mbox {vorbehaltlich} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Gepäck Geben Sie $ i $ in eines der Felder ein |
| $ \ sum_i {w_i x_ {ij}} \ le c + y ~ \ forall j $ | Füllen Sie die Kapazität des Felds $ j $ aus | |
Es hat die folgenden Funktionen.
| Formulierung | Wenn eine Lösung existiert | Wenn es keine Lösung gibt |
|---|---|---|
| Zweistufige Formulierung A. | Sehr Zeit aufwendig | Endet bald |
| Zweistufige Formulierung B. | Endet bald | Sehr Zeit aufwendig |
Wenn Sie A und B parallel ausführen, können Sie schnell feststellen, ob eine Lösung vorhanden ist. Die Anzahl der Boxen kann effizient ermittelt werden, indem 2 Minuten lang gesucht wird.
Gibt es eine schnelle Möglichkeit, Parallelisierung zu vermeiden?
Die genaue Lösungsformulierung ist aufgrund der Symmetrie der Lösung ineffizient (Kasten X und Kasten Y können ausgetauscht werden). In der Praxis verwenden Sie daher häufig die ungefähre Lösungsmethode. Es gibt eine Säulengenerierungsmethode als ungefähre Lösung zur Lösung des Problems der Behälterpackung. Obwohl es sich um eine ungefähre Lösung handelt, kann Genauigkeit erwartet werden. Da es sich jedoch um eine komplizierte Methode handelt, werde ich die Erklärung weglassen. Wenn Sie interessiert sind, lesen Sie bitte das relativ leicht verständliche Dokument (Methode zur Generierung der ersten Spalte). In Python wird die Spaltengenerierungsmethode mit ortoolpy.binpacking ausgeführt, das mit "pip install or toolpy" installiert werden kann.
Andere häufig verwendete Näherungslösungen sind die Greedy-Methode und die lokale Suchmethode, die hier weggelassen werden.
Kombinationsoptimierungsprobleme liegen häufig in der exponentiellen Größenordnung. Wenn das Problem geteilt werden kann, ist dies eine ungefähre Lösung, die jedoch beschleunigt werden kann. Im Allgemeinen [Divisional Governance](https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6% Es heißt B3% 95).
das ist alles