Typische Probleme der Kombinationsoptimierung und der Ausführung

Führen Sie typische Probleme in Kombinationsoptimierung und in der Ausführung mit Python auf. ([Lass uns rennen](# Lass uns rennen)) Eine ausführlichere Erklärung finden Sie im Buch "Kombinationsoptimierung".

Typische Problemklasse	#	Typisches Problem	Komplexitätsklasse	Duales Problem
Grafiknetzwerkproblem	1	Minimales Problem mit dem gesamten Flächenbaum	P
	2	Problem mit maximaler stabiler Menge ( Problem mit minimaler Scheitelpunktabdeckung , Maximales Bachproblem des Zusatzgraphen)	NP-Schwierigkeit
	3	Maximales Schnittproblem	NP-Schwierigkeit	< / tr>
	4	Problem mit der kürzesten Route	P
	5	Problem mit maximalem Durchfluss	P	Minimales Schnittproblem
	6	Problem des minimalen Kostenflusses	P	< / tr>
Routenproblem weniger >
	8	Problem mit dem Patrouillenverkäufer	NP-Schwierigkeit
	9	Problem mit der Zustellung chinesischer Post	P.
Problem der kollektiven Abdeckung / Aufteilung	10	Problem mit der Baugruppenabdeckung	NP-Schwierigkeit		11	Problem mit der Gruppenteilung	NP-Schwierigkeit	weniger / tr>
	Planungsproblem	13	Job-Shop-Problem	NP-Schwierigkeit
	Planungsproblem	14	Arbeitsplanungsproblem	NP-Schwierigkeit	< / tr>
Problem mit Aussparung / Störung	15	Rucksackproblem	NP-Schwierigkeit
	16	Problem beim Packen des Behälters	NP-Schwierigkeit	< / tr> weniger >
	Platzierungsproblem	18	Problem bei der Platzierung der Einrichtung	NP-Schwierigkeit
19	Platzierungsproblem	Keine Kapazitätsbeschränkung Problem bei der Platzierung der Einrichtung	NP-Schwierigkeit
Zuweisungs- / Übereinstimmungsproblem	20	Sekundäres Zuordnungsproblem	NP-Schwierigkeit
	21	Allgemeines Zuordnungsproblem	NP-Schwierigkeit
	22	Maximales Übereinstimmungsproblem	P
	23	Problem mit der Gewichtsanpassung	P
	24	Stabiles Übereinstimmungsproblem	(P)

Knoten, die in der Lösung des Problems der maximalen stabilen Menge nicht ausgewählt wurden, sind die Lösung des Problems der minimalen Scheitelpunktabdeckung. ――Die Lieferoptimierung wird oft als XX-Plan wie Lieferplan bezeichnet, aber XX-Plan ist ein alter Name.

Lass uns rennen

Beim Starten von Docker

Installieren Sie Docker Toolbox und von Kitematic das Docker-Image tsutomu7 / typisch_optimization. ) Bitte führen Sie die. Öffnen Sie nach dem Ausführen "http: // localhost: 8888". Das Passwort für das Jupyter Notebook lautet "jupyter". Informationen zur Installation von Docker finden Sie auch unter Bis Sie Jupyter mit Docker starten.

Bei der Installation und Ausführung vor Ort

Bitte installieren Sie die folgende Software. Nach der Installation können Sie den Code ausführen, der mit jedem der oben genannten Probleme verknüpft ist.

--Installieren von Python und pip: Wählen Sie das Zielbetriebssystem im Environment Construction Guide aus und installieren Sie es.

Wir empfehlen die neueste Version der 3er Serie. Einige Bibliotheken funktionieren jedoch möglicherweise nicht mit der neuesten Version. In diesem Fall ist die ältere Version stabiler.
Bibliotheksinstallation: pip install pandas matplotlib jupyter more-itertools scipy networkx ortoolpy

--ortoolpy: Für typische Probleme. Einige haben nur eine minimale Funktionalität und andere sind ineffizient. PuLP (Modellierer und Löser für die mathematische Optimierung) ist ebenfalls installiert.

--Referenz: Es gibt auch eine Methode mit Anaconda, aber die Verwaltung der Bibliothek unterscheidet sich von der oben beschriebenen Methode (Anaconda integriert Python und verschiedene Pakete für Wissenschaft und Technologie). Es ist eine Distribution, die gemacht wurde).

Referenz

Mathematical Optimization Modeler PuLP Cheet Sheet

[PYTHON] Kombinationsoptimierungstypische Probleme und wie es geht

Typische Probleme der Kombinationsoptimierung und der Ausführung

Lass uns rennen

Beim Starten von Docker

Bei der Installation und Ausführung vor Ort

Referenz