Memorandum @ Python ODER Seminar: Pulp

Eine Bibliothek zur Modellierung der mathematischen Optimierung. Löser wie "Gurobi", "CBC" und "GLPK" können verwendet werden. Ich weiß nicht viel über Optimierung, deshalb plane ich, in Zukunft zu studieren.

Verfahren zur Erstellung mathematischer Modelle

Das Verfahren zum Lösen eines Problems mit einem mathematischen Modell ist wie folgt.

• () Ist der Klassenname in Zellstoff.

1. Erstellen Sie ein mathematisches Modell (LpProblem)
2. Fügen Sie eine Variable hinzu (LpVariable)
3. Fügen Sie den Zielfunktionsausdruck (LpAffineExpression) hinzu.
4. Fügen Sie eine Einschränkung hinzu (LpConstraint)

Mathematisches Modell: LpProblem

LpProblem(name='NoName', sense=LpMinimize)

--name: Name des mathematischen Modells. Die Standardeinstellung ist "NoName". --sense: Entweder minimieren (LpMinimize) oder maximieren (LpMaximize).

Variable: LpVariable

LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)

--name: Variablenname -- lowBound: Untergrenze --upBound: Obergrenze --cat: Variablentyp

• LpContinuous: Kontinuierliche Variable
• LpInteger: Ganzzahlige Variable
• LpBinary: Binäre Variablen
• e: Wird für spaltenbasiertes Modell verwendet (nicht sicher)

Zielfunktion: LpAffineExpression

Kann wie " x + 2 * y "mit Variablen erstellt werden Es ist auch möglich, dem Ausdruck später Begriffe hinzuzufügen Geben Sie die Zielfunktion als "m + = Ausdruck" an (m ist jedoch ein mathematisches Modell).

Einschränkung: LpConstraint

Kann mit Variablen wie " x + y <= 1 "erstellt werden. Es ist auch möglich, später auf der linken Seite der Einschränkung einen Begriff hinzuzufügen Einschränkungen werden als " m + = Ausdruck <= rechte Seite "angegeben.

Andere

Funktionen, die häufig verwendet werden value (): Ruft den Wert der Variablen ab lpSum (): Finde die Summe der Begriffe lpDot (): Finde das innere Produkt zweier Listen

Der Spickzettel ist hier

Versuchen Sie, das Rucksackproblem zu lösen

Häufige Optimierungsprobleme

Legen Sie so viele Gegenstände wie möglich in einen Rucksack dann:

• Das maximale Gewicht, das in einen Rucksack gesteckt werden kann, beträgt 600 Gramm.

Es gibt Einschränkungen wie. Also, was machst du?

Formulieren

Fügen Sie den Eintrag $ s_i $ → $ v_i = 1 $ ein Setzen Sie nicht das Element $ s_i $ → $ v_i = 0 $

\begin{array}{cl}
\max & \sum_i{s_i \ v_i} \\
\mbox{subject to} & \sum_i{s_i \ v_i} \leq C \\
                 & v_i \in \{0, 1\} ~ \forall i
\end{array}

Mit Zellstoff umsetzen

>>> #Das Gewicht des Artikels
>>> s = [128, 108, 34, 53, 71, 224, 299, 181, 336, 15]
>>> #Maximale Tragfähigkeit des Rucksacks
>>> C = 600
>>> #Bibliotheksvorbereitung
>>> from pulp import LpProblem, LpVariable, LpMaximize, LpBinary
>>> rn = range(len(s))
>>> #Modellvorbereitung
>>> m = LpProblem('knapsack', LpMaximize)
>>> #Variable(0, ob das i-te Element eingeschlossen werden soll/1)
>>> v = [LpVariable('v%d' % i, cat = LpBinary) for i in rn]
>>> #Zielfunktion
>>> m += lpDot(s, v)
>>> #Zwang
>>> m += lpDot(s, v) <= C
>>> #lösen
>>> m.solve()
>>> #Ausgabe
>>> print(LpStatus[m.status], sum(s[i] * value(v[i]) for i in rn))
>>> print([s[i] for i in rn if value(v[i]) > 0.5])
Optimal 600.0
[108, 34, 53, 224, 181]

Andere Optimierungsprobleme

Andere Optimierungsprobleme können durch Formulieren (wie) gelöst werden.

Problem bei der Platzierung der Einrichtung (p-Median)

Das Problem der Auswahl von p aus den Einrichtungskandidaten und der Minimierung der Gesamtentfernung vom Bedarfspunkt zur Einrichtung

Beispiel

• Wählen Sie 4 Unterstände aus den Kandidaten für Unterstände aus und minimieren Sie die Gesamtstrecke zwischen den Bewohnern und den Unterkünften (p == 4).
• $ x_ {ij} $ gibt an, ob der Bewohner j zu Einrichtung i evakuiert, und $ y_i $ gibt an, ob Einrichtung i ausgewählt ist oder nicht (Entfernung ist $ d_ {ij} $).

Formulierung

\begin{array}{cl}
\min & \sum_i{\sum_j{d_{ij} \ x_{ij}}} ~ ~ ~ ~ (1) \\
\mbox{subject to} & \sum_i{y_i} = p ~ ~ ~ ~ (2) \\
                 & \sum_i{x_{ij}} = 1 ~ \forall j ~ ~ ~ ~ (3) \\
                 & x_{ij} \leq y_i ~ \forall i, j ~ ~ ~ ~ (4) \\
                 & x_{ij} \in \{0, 1\} ~ \forall i, j
\end{array}

Sudoku

Das ist üblich.

• Stellen Sie die Zielfunktion nicht ein, solange die Bedingung erfüllt ist
• Eine 0/1-Variable gibt an, ob die Zahl k an der Position von Zeile i und Spalte j verwendet werden soll.
• dargestellt durch v [i, j, k]
• Einschränkung
• An den vertikalen i- und horizontalen j-Positionen kann nur eine Zahl verwendet werden (1)
• In jeder Zeile i (2) kann nur eine Zahl j verwendet werden.
• In jeder Spalte i (3) kann nur eine Zahl j verwendet werden.
• Nur eine Zahl j kann in 3 $ \ mal $ 3 (4) verwendet werden.

Formulierung

\begin{array}{cl}
\min & \mbox{no objective function} \\
\mbox{subject to} & \sum_k{v_{ijk}} = 1 ~ \forall i, j ~ (1)\\
                 & \sum_k{v_{ikj}} = 1 ~ \forall i, j ~ (2) \\
                 & \sum_k{v_{kij}} = 1 ~ \forall i, j ~ (3) \\
                 & 3\Gleiches gilt für die Quadrate von times3~ (4) \\
                 & v_{ijk} \in \{0, 1\} ~ \forall i, j, k
\end{array}

Andere Optimierungsprobleme