Python in der Optimierung

Einführung

In meinem Unternehmen entwickle ich Software mithilfe der Technologie zur Kombinationsoptimierung (z. B. Minimierung der Transportkosten in der Logistik). Früher habe ich Optimierungsmodelle mit C ++ und C # erstellt, heute verwende ich häufig Python. Hier werden wir Python in die Optimierung einführen.

Vorteile von Python

Die Gründe für die Verwendung von Python sind folgende.

--Einfach zu verstehen. Da das Modell nach mathematischer Formel und das Modell nach Python nahe beieinander liegen, können Sie sich auf wesentlichere Beschreibungen konzentrieren und ein Modell erstellen, das einfach zu warten ist. sample.png

--Kurzbeschreibungsbetrag ist erforderlich. Die Größe des Programms ist ein Bruchteil der von C ++.

Python soll langsamer laufen als Compilersprachen wie C ++. Bei der Optimierung wird Python jedoch hauptsächlich für die Modellerstellung (Modellierung) und für die Ausführung von Optimierungsalgorithmen in C ++ usw. geschriebene dedizierte Software (Solver) verwendet. Selbst wenn Sie Python zur Optimierung verwenden, spielt die Ausführungszeit daher keine große Rolle.

Bei der Optimierungsmodellierung werden hauptsächlich die Pakete PuLP und Pandas verwendet.

--PuLP ist ein mathematisches Modellierungspaket und pandas ist ein Datenanalysepaket. --Pandas eignet sich für den Umgang mit Daten, die in einer Tabelle unter den im Modell enthaltenen Daten ausgedrückt werden können, und kann die komplizierte Verarbeitung auf leicht verständliche Weise beschreiben. Pandas verwendet Numpy auch intern. --Numpy verwendet eine hochoptimierte lineare Algebra-Bibliothek, die in C oder Fortran geschrieben ist, und kann Matrixberechnungen effizient berechnen.

Über PuLP

Führen Sie die folgenden Schritte aus, um das mathematische Optimierungsproblem zu lösen:

--Erstellen Sie mit dem Modellierer ein mathematisches Modell

Solver ist eine Software, die ein mathematisches Modell als Eingabe verwendet, das mathematische Modell löst und den Wert (die Lösung) einer Variablen ausgibt.

image.png

PuLP ist eine vom COIN-Projekt erstellte Software und wird ein Modellierer sein. Mit PuLP können Sie verschiedene Löser wie CBC, Gurobi und GLPK verwenden. Standardmäßig wird CBC verwendet. Wenn Sie PuLP installieren, wird CBC gleichzeitig installiert.

--CBC: COIN Project Free Solver (kurz für COIN-OR Branch and Cut) https://projects.coin-or.org/Cbc

Das Problem, das PuLP bewältigen kann, ist das Optimierungsproblem für gemischte Ganzzahlen. Das gemischte ganzzahlige Optimierungsproblem ist eine Art mathematisches Optimierungsproblem und weist die folgenden Eigenschaften auf.

Weitere Informationen finden Sie auf der Referenzseite.

Wie benutzt man PuLP?

Betrachten Sie das folgende Problem.

Problem


Ich möchte viele chemische Produkte X und Y herstellen, die aus den Materialien A und B synthetisiert werden können.
Um 1 kg X herzustellen, benötigen Sie 1 kg A und 3 kg B.
Um 1 kg Y herzustellen, benötigen Sie 2 kg A und 1 kg B.
Der Preis für X und Y beträgt 100 Yen pro kg.
Um die Summe der Preise von X und Y zu maximieren, wenn Material A nur 16 kg und B nur 18 kg wiegt
Finden Sie heraus, wie viele X und Y erstellt werden sollen.

prob.png

Das mathematische Modell des Problems ist wie folgt. Die Darstellung eines mathematischen Modells mit einem Ausdruck wird als Formalisierung bezeichnet.

formula.png

Lassen Sie uns dies mit PuLP modellieren und lösen.

python3


from pulp import *
m = LpProblem(sense=LpMaximize) #Mathematisches Modell
x = LpVariable('x', lowBound=0) #Variable
y = LpVariable('y', lowBound=0) #Variable
m += 100 * x + 100 * y #Zielfunktion
m += x + 2 * y <= 16 #Obergrenze des Materials A.
m += 3 * x + y <= 18 #Obergrenze des Materials B.
m.solve() #Führen Sie den Solver aus
print(value(x), value(y)) # 4, 6

Das Folgende ist eine kurze Erklärung in der Reihenfolge.

Paketimport

from pulp import *

Erstellen eines mathematischen Modells

Bei Minimierungsproblemen: m = LpPrblem () Bei Maximierungsproblemen: m = LpProblem (sense = LpMaximize)

Variablen erstellen

Kontinuierliche Variable: x = LpVariable (Variablenname, lowBound = 0) 0-1 Variable: x = LpVariable (Variablenname, cat = LpBinary) Liste der stetigen Variablen: x = [LpVariable (i-ter Variablenname, lowBound = 0) für i im Bereich (n)] Variablennamen müssen unterschiedlich sein

Einstellen der Zielfunktion

m + = Ausdruck

Einschränkungsbedingung hinzufügen

m + = Ausdruck == Ausdruck m + = Ausdruck <= Ausdruck m + = Ausdruck> = Ausdruck

Ausdrucksbeispiel

2 * x + 3 * y - 5

Summe: lpSum (Liste der Variablen) Inneres Produkt: lpDot (Liste der Koeffizienten, Liste der Variablen)

Führen Sie den Solver aus

m.solve()

Werte von Variablen, Ausdrücken und Zielfunktionen

Wert (Variable), Wert (Ausdruck), Wert (Ziel)

Über die Kombination von PuLP und Pandas

Das Kombinieren von PuLP und Pandas und das Verwalten von Variablen (LpVariable) in einer Pandas-Tabelle (DataFrame) erleichtert das Verständnis der Formulierung.

Nehmen Sie als Beispiel das Problem der Transportoptimierung.

Transportoptimierungsproblem

Ich möchte Teile von einer Gruppe von Lagern zu einer Gruppe von Fabriken transportieren. Ich möchte einen Plan finden, der die Transportkosten minimiert.

Transportkosten Montagewerk
F1 F2 F3 F4 Versorgung
Lager W1 10 10 11 17 35
W21619121441
W31512141242
Nachfrage 28 29 31 25

Parametereinstellungen

Stellen Sie die erforderlichen Parameter ein. (Die Zahlen sind die gleichen wie in der vorherigen Tabelle)

python3


import numpy as np, pandas as pd
from itertools import product
from pulp import *
np.random.seed(1)
nw, nf = 3, 4
pr = list(product(range(nw),range(nf)))
Liefern= np.random.randint(30, 50, nw)
Nachfrage= np.random.randint(20, 40, nf)
Versandkosten= np.random.randint(10, 20, (nw,nf))

Mathematisches Modell ohne Pandas

Auf Variablen wird über Indizes zugegriffen.

python3


m1 = LpProblem()
v1 = {(i,j):LpVariable('v%d_%d'%(i,j), lowBound=0) for i,j in pr}
m1 += lpSum(Versandkosten[i][j] * v1[i,j] for i,j in pr)
for i in range(nw):
    m1 += lpSum(v1[i,j] for j in range(nf)) <=Liefern[i]
for j in range(nf):
    m1 += lpSum(v1[i,j] for i in range(nw)) >=Nachfrage[j]
m1.solve()
{k:value(x) for k,x in v1.items() if value(x) > 0}
>>>
{(0, 0): 28.0,
 (0, 1): 7.0,
 (1, 2): 31.0,
 (1, 3): 5.0,
 (2, 1): 22.0,
 (2, 3): 20.0}

Mathematisches Modell mit Pandas

Auf Variablen kann über Tabellenattribute zugegriffen werden. Zuerst erstellen wir eine Tabelle.

python3


a = pd.DataFrame([(i,j) for i, j in pr], columns=['Warenhaus', 'Fabrik'])
a['Versandkosten'] = Versandkosten.flatten()
a[:3]
Lager Fabrik Transportkosten
00010
10110
20211

Lassen Sie uns auf die gleiche Weise ein mathematisches Modell erstellen.

python3


m2 = LpProblem()
a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in a.index]
m2 += lpDot(a.Versandkosten, a.Var)
for k, v in a.groupby('Warenhaus'):
    m2 += lpSum(v.Var) <=Liefern[k]
for k, v in a.groupby('Fabrik'):
    m2 += lpSum(v.Var) >=Nachfrage[k]
m2.solve()
a['Val'] = a.Var.apply(value)
a[a.Val > 0]
Lager Fabrik Transportkosten Var Val
0 0 0 10 v0 28.0
1 0 1 10 v1 7.0
6 1 2 12 v6 31.0
7 1 3 14 v7 5.0
9 2 1 12 v9 22.0
11 2 3 12 v11 20.0

Ausdrücke mit Indizes mussten sich daran erinnern, was die Indizes bedeuteten. Die Kombination von PuLP und Pandas erleichtert jedoch das Verständnis des mathematischen Modells, wie unten gezeigt.

Referenzseite

das ist alles

Recommended Posts

Python in der Optimierung
Lösen Sie Optimierungsprobleme mit Python
Quadtree in Python --2
CURL in Python
Metaprogrammierung mit Python
Python 3.3 mit Anaconda
Geokodierung in Python
SendKeys in Python
Metaanalyse in Python
Unittest in Python
Optimierung der FX-Systolenparameter in Python
GPyOpt, ein Paket zur Bayes'schen Optimierung in Python
Epoche in Python
Zwietracht in Python
Deutsch in Python
DCI in Python
Quicksort in Python
nCr in Python
N-Gramm in Python
Programmieren mit Python
Plink in Python
Konstante in Python
FizzBuzz in Python
SQLite in Python
Schritt AIC in Python
LINE-Bot [0] in Python
CSV in Python
Reverse Assembler mit Python
Reflexion in Python
Konstante in Python
nCr in Python.
Format in Python
Scons in Python 3
Puyopuyo in Python
Python in Virtualenv
PPAP in Python
Quad-Tree in Python
Reflexion in Python
Chemie mit Python
Hashbar in Python
DirectLiNGAM in Python
LiNGAM in Python
In Python reduzieren
In Python flach drücken
Ich habe versucht, die Bayes'sche Optimierung von Python zu verwenden
Sortierte Liste in Python
Täglicher AtCoder # 36 mit Python
Clustertext in Python
AtCoder # 2 jeden Tag mit Python
Täglicher AtCoder # 32 in Python
Täglicher AtCoder # 6 in Python
Täglicher AtCoder # 18 in Python
Bearbeiten Sie Schriftarten in Python
Singleton-Muster in Python
Dateioperationen in Python
Lesen Sie DXF mit Python
Täglicher AtCoder # 53 in Python
Tastenanschlag in Python