[PYTHON] Lösen Sie Probleme bei der Kombinationsoptimierung mit den OR-Tools von Google. (5) Legen Sie einen Termin fest

Einführung

Dieser Artikel ist der fünfte Artikel zur Lösung des Übungsproblems des Referenztextes "Problemlösungsserie von Python: Erstellen eines Optimierungsmodells mithilfe einer Datenanalysebibliothek" zur mathematischen Optimierung.

Der erste Artikel ist unten. Bitte sehen Sie zuerst hier.

Lösen Sie mathematische Optimierungsmodellübungen mit den OR-Tools von Google (1) Das einfachste Problem beim Füllen von Massen https://qiita.com/ttlabo/private/7e8c93f387814f99931f

Entscheiden wir uns für einen Date-Kurs

Dies ist ein angewandtes Problem, das im Referenztext angezeigt wird. Versuchen wir die folgenden Probleme sofort.

: language_balloon: Problem

ruby:8.4.Problem

Dating in einem Vergnügungspark mit 8 Sehenswürdigkeiten(8-Figur 4)。
Maximieren Sie die Gesamtzufriedenheit innerhalb des Zeitlimits von 200 Minuten.
Es ist nicht notwendig, alle Datumskurse zu durchlaufen.
Optimieren Sie den Datumskurs, der die Bedingungen erfüllt.

: Frage: ** Denken **

■ Modellierungsrichtlinie In Anbetracht des Zeitlimits von 200 Minuten werden wir in Betracht ziehen, die Zufriedenheit so weit wie möglich zu maximieren, ohne alles zu tun. Bereiten Sie dazu die folgenden Variablen vor.

: point_right: Variablendefinition

\begin{eqnarray*}

S_i\;&\small{:=}&\;\small{Ob Sie die i-te Attraktion wählen}\\
M_{ij}\;&\small{:=}&\;\small{Ob Sie von der i-ten Attraktion zur j-ten Attraktion wechseln möchten}\\
satisfy\;&\small{:=}&\;\small{Endgültige Zufriedenheit(Gesamt)}\\
stayTime\;&\small{:=}&\;\small{Letzte Aufenthaltszeit(Gesamt)}\\
moveTime\;&\small{:=}&\;\small{Letzte Reisezeit(Gesamt)}\\
totalTime\;&\small{:=}&\;\small{Ganze Zeit(Summe aus endgültiger Zufriedenheit und Verweildauer)}

\end{eqnarray*}

Das Lösen der Optimierung ergibt den optimalen Wert dieser Variablen, um den Datumsverlauf zu bestimmen. Darüber hinaus werden im Voraus bekannte Werte und Informationen wie folgt als Konstanten definiert.

: point_right: Konstante Definition

\begin{eqnarray*}

Zufriedenheit ständige ZufriedenheitDef\\
Zeit konstant bleiben stayTimeDef\\
Verschieben Sie die Zeitkonstante moveTimeDef

\end{eqnarray*}

Die Reihenfolge ist umgekehrt, aber stellen Sie zuerst die Werte für die Konstanten wie folgt ein: (1) Stellen Sie den Wert der Zufriedenheitskonstante wie folgt ein.

ruby:8.4.renshu.py

satisfyDef = [0,50,36,45,79,55,63,71,42]

befriedigtDef ist ein Array, und die Befriedigung der i-ten Anziehungskraft ist befriedigtDef [i]. Zum Beispiel beträgt die Zufriedenheit der zweiten Attraktion 36. Die Indexnummer der Attraktion wird ab 0 gezählt. (2) Stellen Sie die Werte für die Verweilzeitkonstante wie folgt ein.

ruby:8.4.renshu.py

stayTimeDef = [0,20,28,15,35,17,18,14,22]

stayTimeDef ist ein Array und die Verweildauer der i-ten Attraktion ist stayTimeDef [i]. (3) Stellen Sie die Werte für die Bewegungszeitkonstante wie folgt ein.

ruby:8.4.renshu.py

moveTimeDef = {}
moveTimeDef[0,3] = 7
～

moveTimeDef ist ein diktärer Typ, und die Zeit für den Wechsel von i nach j ist moveTimeDef [i, j]. Beispielsweise beträgt die Reisezeit beim Übergang von der 0. Attraktion (Eingang) zur 3. Attraktion (Kaffeetasse) moveTimeDef [0,3], was 7 Minuten bedeutet.

(1) Zufriedenheitskonstante, (2) Verweilzeitkonstante und (3) Fahrzeitkonstante sind die im Referenztext definierten Werte.

Definieren Sie als Nächstes die Variablen Si und Mij wie folgt. (1) Si ist wie folgt definiert.

ruby:8.4.renshu.py

#Variablen, ob eine Attraktion ausgewählt werden soll
# 1:Wählen/ 0:Nicht ausgewählt
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

Hier werden die 0. bis 8. Attraktionen entweder durch Variablen "1: Auswählen" oder "0: Nicht auswählen" (Typ BoolVar) definiert. Wenn beispielsweise S [4] = 1 ist, bedeutet dies, dass Sie die 4. Attraktion auswählen.

(2) Mij ist wie folgt definiert.

ruby:8.4.renshu.py

#Variable, ob in Bezug auf die Bewegung von i nach j bewegt werden soll
# 1:Ziehen um/ 0:Nicht bewegen
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

Hier wird jede Kombination der 0. bis 8. Attraktion entweder durch die Variable "1: Verschieben" oder "0: Nicht verschieben" (Typ BoolVar) definiert. Es gibt 9 Kombinationen x 9 Kombinationen, insgesamt 81 Kombinationen. Wenn beispielsweise M [1,3] = 1 ist, bedeutet dies, von der ersten zur dritten Attraktion zu wechseln.

Lösen Sie mithilfe der obigen Variablen und Konstanten das Optimierungsproblem, während Sie verschiedene Bedingungen (Einschränkungen) zwischen den Variablen und Konstanten festlegen.

: a: ** Antwort **

Betrachten Sie das Programm. Der Inhalt des Programms folgt im Wesentlichen dem OR-Tools-Handbuch von Google. (https://developers.google.com/optimization)

Schreiben Sie zu Beginn des Programms einen Zauber.

ruby:8.4.renshu.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

Da es durch den Mixed Integer Planning Solver gelöst wird, wird es unten deklariert.

ruby:8.4.renshu.py

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Als nächstes definieren wir Konstanten.

ruby:8.4.renshu.py

#Konstante Definition=================================================================

#Name der Attraktion
attrDef = ['','Eingang','Cafe','Boot','Tasse','Restaurant','Riesenrad',
           'Spukhaus','Untersetzer','Matze']

#Zufriedenheitskonstante
satisfyDef = [0,50,36,45,79,55,63,71,42]

#Zeitkonstante bleiben
stayTimeDef = [0,20,28,15,35,17,18,14,22]

Die obige erste Definition attrDef wird in diesem Programm nicht verwendet. Diesmal habe ich es vorerst definiert. Wie ich in der Erklärung der konstanten Definition geschrieben habe, sind ZufriedenheitDef und StayTimeDef Arrays, und die Indexnummer und die Attraktionsnummer sind verknüpft. Die Indexnummer 0 entspricht der Attraktionsnummer 0 (Eingang), die Zufriedenheit ist 0 und die Aufenthaltszeit ist 0. Die Reisezeit ist wie folgt definiert.

ruby:8.4.renshu.py

#Reisezeitkonstante
# moveTimeDef[i,j]← Zeit, von i nach j zu wechseln
moveTimeDef = {}
moveTimeDef[0,0] = 0
moveTimeDef[0,1] = 9
moveTimeDef[0,2] = 0
moveTimeDef[0,3] = 7
〜

Hier wird die Fahrzeit der Route, die nicht befahren werden kann, auf 0 gesetzt. Oben sind nur 4 Routen beschrieben, aber alle Routen sind in der gesamten unten angegebenen Quelle definiert. Definieren Sie als Nächstes die Variablen.

ruby:8.4.renshu.py

#Variablendefinition=================================================================

#Variablen, ob eine Attraktion ausgewählt werden soll
# 1:Wählen/ 0:Nicht ausgewählt
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

#Variable, ob in Bezug auf die Bewegung von i nach j bewegt werden soll
# 1:Ziehen um/ 0:Nicht bewegen
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

Wie zuvor erläutert, werden S und M oben als Variablen deklariert, die 0/1 annehmen. Der OR-Tools-Solver berechnet und entscheidet, welchen Wert er annehmen soll.

ruby:8.4.renshu.py

#Zufriedenheit erklären
satisfy = solver.IntVar(0.0, 1000, 'satisfy')
#Geben Sie die Aufenthaltsdauer an
stayTime = solver.IntVar(0.0, 1000, 'stayTime')
#Reisezeit variabel
moveTime = solver.IntVar(0.0, 1000, 'moveTime')
#Ganze Zeitvariable
totalTime = solver.IntVar(0.0, 1000, 'totalTime')

Deklarieren Sie die oben genannte Zufriedenheit, Verweilzeit, Reisezeit und Gesamtzeit (Verweilzeit + Reisezeit) als Variablen, die Ganzzahlen von 0 bis 100 annehmen. Nachdem wir die Konstanten und Variablen vorbereitet haben, legen wir die Bedingungen fest (setzen Sie den Einschränkungsausdruck).

In Bezug auf die Einstellung des Einschränkungsausdrucks enthält der Referenztext die folgende Ergänzung, daher werden wir ihn einschließlich dieser Bedingung zusammenstellen.

ruby:8.4.Problem

・ Wenn Sie eine Sehenswürdigkeit ausgewählt haben, besuchen Sie sie.
・ Verlassen Sie die Attraktion, wenn Sie sie betreten.
-Verbunden vom Eingang.(Nicht in der Mitte enden)

Unten ist die Quelle der Einschränkungen.

ruby:8.4.renshu.py

#Einschränkungsausdruck===================================================================

#Achten Sie darauf, den Eingang zu passieren
solver.Add(S[0] == 1)

Stellen Sie den obigen Einschränkungsausdruck für den Eingang ein. Da der Eingang immer ausgewählt ist, setzen Sie den Wert von S [0] auf 1.

ruby:8.4.renshu.py

#Bewegungseinschränkungen festlegen
#Setzen Sie M für Routen, die sich nicht bewegen, auf 0
solver.Add(M[0,0] == 0)
solver.Add(M[0,2] == 0)
solver.Add(M[0,5] == 0)
~

Stellen Sie die Route wie oben beschrieben ein. Da M eine Variable ist, kann der Löser sie bestimmen, aber hier wird sie explizit festgelegt. Setzen Sie M [i, j] für Routen, die sich nicht bewegen, auf 0. Beispielsweise können Sie nicht von der 0. zur 0. Attraktion usw. von der 0. zur 5. Attraktion wechseln. Setzen Sie insgesamt 41 Routen auf 0.

ruby:8.4.renshu.py

#Einstellungen zur Vermeidung von Doppelarbeit(Die Sehenswürdigkeit wird nur einmal besucht. Fälle, in denen beide nicht besucht werden, sind möglich)
solver.Add(M[0,1] + M[1,0] <= 1)
solver.Add(M[0,3] + M[3,0] <= 1)
solver.Add(M[0,4] + M[4,0] <= 1)
~

Nachdem Sie sich von einer bestimmten Attraktion i nach j oben bewegt haben, stellen Sie die Bedingungen so ein, dass die Bewegungsroute nicht umgekehrt wird und wieder zu i zurückkehrt. Wenn Sie beispielsweise von der 0. Attraktion zur 1. Attraktion wechseln, ist M [0,1] = 1, und setzen Sie den Wert von M [1,0] auf der umgekehrten Route auf 0 (nicht bewegen). Ich werde. Gleiches gilt für den Rückwärtsweg. Wenn M [0,1] + M [1,0] == 1 ist, bewegt es sich immer, und selbst wenn es sich nicht bewegt, ist M [0,1] + M [1,0] <= 1 Ich werde. Richten Sie insgesamt 20 Routen ein.

ruby:8.4.renshu.py

#Bedingungen für M.
#Bewegen Sie sich nicht gleichzeitig von einer Attraktion zu mehreren Attraktionen
for i in range(9):
    solver.Add(solver.Sum([M[i,j] for j in range(9)]) <= 1)

Stellen Sie die oben genannten Bedingungen ein, um nicht gleichzeitig von einer Attraktion zu mehreren Attraktionen zu wechseln. Dies ist definiert als die Tatsache, dass jede Attraktion i nur eine Route zu jedem j nehmen kann (siehe Abbildung unten).

Definieren Sie als Nächstes die Kontinuitätsbedingung der Route wie folgt. Routenkontinuität bedeutet, dass Sie keine Attraktionen auswählen, die nicht verbunden sind (siehe Abbildung unten).

Der Einschränkungsausdruck der Bedingung, dass die Route verbunden ist (kontinuierlich), lautet wie folgt.

ruby:8.4.renshu.py

#Routenkontinuitätsbedingung
#0 Startpunkt
step = [1,3,4]
solver.Add(solver.Sum([M[0,s] for s in step]) == solver.Sum([M[s,0] for s in step]))
#1 Ausgangspunkt
step = [0,2,3,4,5]
solver.Add(solver.Sum([M[1,s] for s in step]) == solver.Sum([M[s,1] for s in step]))
~

Schauen wir uns das Obige ab der ersten Attraktion an. Es gibt drei Wege zur Attraktion 1: M [0,1], M [3,1], M [4,1]. Nehmen wir an, Sie betreten die Attraktion 1 auf einem bestimmten Weg, wie in der folgenden Abbildung (Muster 1) dargestellt. Hier wird angenommen, dass M [4,1] unter M [0,1], M [3,1], M [4,1] eingegeben wird (roter Pfeil).

Es kann nur eine der drei Routen verwendet werden, um in die Attraktion 1 einzutreten. Der Wert von M [0,1], M [3,1], M [4,1] ist also 1 und die anderen Der Wert von wird 0 sein. Legen Sie Folgendes als Einschränkungsausdruck fest.

solver.Sum ([M [s, 1] für s in Schritt]) = 1… Gleichung ①

Da die Einstellungsbedingung des Einschränkungsausdrucks "Beim Betreten einer Attraktion ausgehen" lautet, sollten Sie die Route berücksichtigen, um von Attraktion 1 zu einer anderen Attraktion zu gelangen. Wie in der obigen Abbildung (Muster 2) gezeigt, gibt es drei Attraktionen, die von Attraktion 1 verschoben werden können. Sie müssen jedoch eine davon auswählen. Der Einschränkungsausdruck zur Auswahl von eins aus drei ist

solver.Sum ([M [1, s] für s in Schritt]) = 1… Gleichung ②

Wird sein. Da wir jedoch davon ausgegangen sind, dass wir die Route von M [4,1] früher nehmen würden, ist die Route, die tatsächlich genommen werden kann, entweder M [1,2] oder M [1,5](obige Abbildung (Muster 3)). Der Löser berechnet, welchen Weg er einschlagen soll.

Es ist auch möglich, dass Sie die Attraktion 1 nicht betreten können. In diesem Fall wechseln Sie nicht zur nächsten. In diesem Fall beträgt die Summe von Ms sowohl für die eingehende als auch für die ausgehende Route 0. Daher sollten die Bedingungen der Route zum Betreten und Verlassen der Attraktion 1 unter Verwendung der Gleichungen (1) und (2) wie folgt sein.

solver.Sum([M[1,s] for s in step]) == solver.Sum([M[s,1] for s in step])

Bisher haben wir den Einschränkungsausdruck der Routenkontinuität für Attraktion 1 erklärt. In der tatsächlichen Quelle wird jede der Attraktionen 0 bis 8 auf dieselbe Weise definiert. Die Einschränkungsausdrücke für den Rest der Attraktionen werden in den unten aufgeführten Quellen definiert.

Berücksichtigen Sie außerdem die Beziehung zwischen den von Ihnen besuchten Attraktionen und den Ein- und Ausstiegsrouten vorher und nachher. Ähnlich der Pfadkontinuitätsbedingung, definiert jedoch die Beziehung zwischen S und M als Einschränkungsausdruck.

ruby:8.4.renshu.py

#Definition der Beziehung zwischen S und M.
#0 Startpunkt
step = [1,3,4]
solver.Add(S[0] - (solver.Sum([M[0,s] for s in step]) + solver.Sum([M[s,0] for s in step])) / 2 == 0)
#1 Ausgangspunkt
step = [0,2,3,4,5]
solver.Add(S[1] - (solver.Sum([M[1,s] for s in step]) + solver.Sum([M[s,1] for s in step])) / 2 == 0)
~

In Bezug auf das Obige bedeutet der Inhalt des Einschränkungsausdrucks "Wenn Sie eine bestimmte Attraktion besuchen, gibt es eine Route, die ein- und ausgeht. Wenn Sie nicht besuchen, nehmen Sie keine Route." Schauen wir uns das ab Attraktion 1 an. Überprüfen Sie zunächst die folgende Routenkarte.

Bei Auswahl von Attraktion 1 gibt es mögliche Routen zum Ein- und Aussteigen. Betrachtet man Muster 1 für die einzugebende Route, so wird Folgendes festgelegt, da es einer der Routen der blauen Route M [0,1], der grünen Route M [3,1] und der roten Route M [4,1] folgt. Machen.

solver.Sum ([M [s, 1] für s in Schritt]) = 1… Gleichung ①

In ähnlicher Weise ist für die Ausgangsroute die Bedingung der Summe der Routen jeder Farbe

solver.Sum ([M [1, s] für s in Schritt]) = 1… Gleichung ②

Wenn Sie Attraktion 1 besuchen, ist der Wert von S [1] 1, sodass Sie diesen Wert wie folgt mit den Gleichungen (1) und (2) verbinden können.

Wert von S [1] - (Formel ① + Formel ②) ÷ 2 = 0 ... Formel ③

Darüber hinaus gilt diese Formel ③ auch dann, wenn Sie Attraktion 1 nicht besuchen. Da der Wert von S [1] 0 ist und die Werte der Gleichungen ① und ② ebenfalls 0 sind.

0　-　(0　+　0)　÷　2　=　0

Daher kann die Beziehung zwischen S und M unter Verwendung von Gleichung (3) definiert werden und ist wie folgt.

S[1] - (solver.Sum([M[1,s] for s in step]) + solver.Sum([M[s,1] for s in step])) / 2 == 0

In der tatsächlichen Quelle wird jede der Attraktionen 0 bis 8 auf dieselbe Weise definiert. Die Einschränkungsausdrücke für den Rest der Attraktionen werden in den unten aufgeführten Quellen definiert.

Damit ist die Erklärung komplizierter Einschränkungsausdrücke abgeschlossen. Die verbleibenden Einschränkungen sind unten definiert.

ruby:8.4.renshu.py

#Berechnung der Zufriedenheit
satisfy = solver.Sum([S[i] * satisfyDef[i] for i in range(9)])

#Berechnung der Verweildauer
stayTime = solver.Sum([S[i] * stayTimeDef[i] for i in range(9)])

#Berechnung der Reisezeit
moveTime = solver.Sum([M[i,j] * moveTimeDef[i,j] for i in range(9) for j in range(9)])

#Berechnung der Gesamtzeit
totalTime = stayTime + moveTime

Die obige Zufriedenheit und Verweilzeit werden mit dem ausgewählten Attraktions-S [i] -Wert und jedem konstanten Wert multipliziert und die Summe davon wird genommen. Wenn Sie eine Attraktion auswählen, ist der S [i] -Wert 1, andernfalls ist S [i] 0, wenn Sie also die Summe nehmen, wird nur der Wert der ausgewählten Attraktion berechnet.

Multiplizieren Sie für die Reisezeit jede i, j-Kombination mit dem M [i, j] -Wert und dem konstanten Wert der Reiseroute und nehmen Sie die Summe davon. Außerdem ist die Gesamtzeit "Aufenthaltszeit + Reisezeit".

Schließlich lautet die Bedingung "Maximieren Sie die Gesamtzufriedenheit innerhalb des 200-Minuten-Zeitlimits".

ruby:8.4.renshu.py

#Allgemeine Zeitbeschränkungen
solver.Add(totalTime <= 200)

#Maximieren Sie die Zufriedenheit
solver.Maximize(satisfy)

Die obigen Bedingungen für die Gesamtzeit von 200 Minuten oder weniger und die Bedingungen für die Maximierung der Zufriedenheit werden separat definiert.

Das ist alles zum Festlegen des Einschränkungsausdrucks. Nachfolgend wird die Lösung ausgeführt.

ruby:8.4.renshu.py

status = solver.Solve()

Wenn in der folgenden Quelle eine Lösung gefunden wird, werden der S [i] -Wert bei jedem i und der M [i, j] -Wert bei i, j beim Bewegen angezeigt.

ruby:8.4.renshu.py

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    print('satisfy', satisfy.solution_value())
    print('stayTime', stayTime.solution_value())
    print('moveTime', moveTime.solution_value())
    print('totalTime', totalTime.solution_value())
    for i in range(9):
        print(i,S[i].solution_value())
    for i in range(9):
        for j in range(9):
            if M[i,j].solution_value() >= 0.5:
                print('M',i,j,'=',M[i,j].solution_value())

else:
    print('The problem does not have an optimal solution.')

Dies ist das Ende der Programmierung. Das tatsächliche Ausführungsergebnis ist wie folgt.

Solution: ok Objective value = 405.0 culculate Time = 427 milliseconds satisfy 405.0 stayTime 141.0 moveTime 59.0 totalTime 200.0 0 1.0 1 1.0 2 0.0 3 1.0 4 1.0 5 1.0 6 1.0 7 1.0 8 1.0 M 0 3 = 1.0 M 1 0 = 1.0 M 3 6 = 1.0 M 4 1 = 1.0 M 5 4 = 1.0 M 6 7 = 1.0 M 7 8 = 1.0 M 8 5 = 1.0

Als Ergebnis der Optimierungsberechnung wurde der Datumsverlauf festgelegt. Die Strecke dauert nur 200 Minuten und die Zufriedenheit beträgt 405.

Darüber hinaus wurde eine Aufschlüsselung von Verweilzeit und Reisezeit von 141 Minuten für die Verweildauer und 51 Minuten für die Reisezeit festgestellt.

Betrachtet man die zu wählende Attraktion, so ist der andere Wert als S [2] 1, also Es ist eine Route, um andere Attraktionen als Boote zu besuchen.

Außerdem basiert die Route auf dem Wert von M [i, j]. 　0 → 3 → 6 → 7 → 8 → 5 → 4 →1→0 Ich habe die Antwort bekommen.

Das gesamte Programm ist unten dargestellt.

ruby:8.4.renshu.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


#Konstante Definition=================================================================

#Name der Attraktion
attrDef = ['','Eingang','Cafe','Boot','Tasse','Restaurant','Riesenrad',
           'Spukhaus','Untersetzer','Matze']

#Zufriedenheitskonstante
satisfyDef = [0,50,36,45,79,55,63,71,42]

#Zeitkonstante bleiben
stayTimeDef = [0,20,28,15,35,17,18,14,22]

#Reisezeitkonstante
# moveTimeDef[i,j]← Zeit, von i nach j zu wechseln
moveTimeDef = {}
moveTimeDef[0,0] = 0
moveTimeDef[0,1] = 9
moveTimeDef[0,2] = 0
moveTimeDef[0,3] = 7
moveTimeDef[0,4] = 12
moveTimeDef[0,5] = 0
moveTimeDef[0,6] = 0
moveTimeDef[0,7] = 0
moveTimeDef[0,8] = 0
moveTimeDef[1,0] = 9
moveTimeDef[1,1] = 0
moveTimeDef[1,2] = 11
moveTimeDef[1,3] = 12
moveTimeDef[1,4] = 7
moveTimeDef[1,5] = 13
moveTimeDef[1,6] = 0
moveTimeDef[1,7] = 0
moveTimeDef[1,8] = 0
moveTimeDef[2,0] = 0
moveTimeDef[2,1] = 11
moveTimeDef[2,2] = 0
moveTimeDef[2,3] = 0
moveTimeDef[2,4] = 14
moveTimeDef[2,5] = 8
moveTimeDef[2,6] = 0
moveTimeDef[2,7] = 0
moveTimeDef[2,8] = 0
moveTimeDef[3,0] = 7
moveTimeDef[3,1] = 12
moveTimeDef[3,2] = 0
moveTimeDef[3,3] = 0
moveTimeDef[3,4] = 11
moveTimeDef[3,5] = 0
moveTimeDef[3,6] = 7
moveTimeDef[3,7] = 12
moveTimeDef[3,8] = 0
moveTimeDef[4,0] = 12
moveTimeDef[4,1] = 7
moveTimeDef[4,2] = 14
moveTimeDef[4,3] = 11
moveTimeDef[4,4] = 0
moveTimeDef[4,5] = 9
moveTimeDef[4,6] = 13
moveTimeDef[4,7] = 9
moveTimeDef[4,8] = 13
moveTimeDef[5,0] = 0
moveTimeDef[5,1] = 13
moveTimeDef[5,2] = 8
moveTimeDef[5,3] = 0
moveTimeDef[5,4] = 9
moveTimeDef[5,5] = 0
moveTimeDef[5,6] = 0
moveTimeDef[5,7] = 13
moveTimeDef[5,8] = 7
moveTimeDef[6,0] = 0
moveTimeDef[6,1] = 0
moveTimeDef[6,2] = 0
moveTimeDef[6,3] = 7
moveTimeDef[6,4] = 13
moveTimeDef[6,5] = 0
moveTimeDef[6,6] = 0
moveTimeDef[6,7] = 7
moveTimeDef[6,8] = 0
moveTimeDef[7,0] = 0
moveTimeDef[7,1] = 0
moveTimeDef[7,2] = 0
moveTimeDef[7,3] = 12
moveTimeDef[7,4] = 9
moveTimeDef[7,5] = 13
moveTimeDef[7,6] = 7
moveTimeDef[7,7] = 0
moveTimeDef[7,8] = 6
moveTimeDef[8,0] = 0
moveTimeDef[8,1] = 0
moveTimeDef[8,2] = 0
moveTimeDef[8,3] = 0
moveTimeDef[8,4] = 13
moveTimeDef[8,5] = 7
moveTimeDef[8,6] = 0
moveTimeDef[8,7] = 6
moveTimeDef[8,8] = 0


#Variablendefinition=================================================================

#Variablen, ob eine Attraktion ausgewählt werden soll
# 1:Wählen/ 0:Nicht ausgewählt
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

#Variable, ob in Bezug auf die Bewegung von i nach j bewegt werden soll
# 1:Ziehen um/ 0:Nicht bewegen
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

#Zufriedenheit erklären
satisfy = solver.IntVar(0.0, 1000, 'satisfy')
#Geben Sie die Aufenthaltsdauer an
stayTime = solver.IntVar(0.0, 1000, 'stayTime')
#Reisezeit variabel
moveTime = solver.IntVar(0.0, 1000, 'moveTime')
#Ganze Zeitvariable
totalTime = solver.IntVar(0.0, 1000, 'totalTime')


#Einschränkungsausdruck===================================================================

#Achten Sie darauf, den Eingang zu passieren
solver.Add(S[0] == 1)

#Bewegungseinschränkungen festlegen
#Setzen Sie M für Routen, die sich nicht bewegen, auf 0
solver.Add(M[0,0] == 0)
solver.Add(M[0,2] == 0)
solver.Add(M[0,5] == 0)
solver.Add(M[0,6] == 0)
solver.Add(M[0,7] == 0)
solver.Add(M[0,8] == 0)
solver.Add(M[1,1] == 0)
solver.Add(M[1,6] == 0)
solver.Add(M[1,7] == 0)
solver.Add(M[1,8] == 0)
solver.Add(M[2,0] == 0)
solver.Add(M[2,2] == 0)
solver.Add(M[2,3] == 0)
solver.Add(M[2,6] == 0)
solver.Add(M[2,7] == 0)
solver.Add(M[2,8] == 0)
solver.Add(M[3,2] == 0)
solver.Add(M[3,3] == 0)
solver.Add(M[3,5] == 0)
solver.Add(M[3,8] == 0)
solver.Add(M[4,4] == 0)
solver.Add(M[5,0] == 0)
solver.Add(M[5,3] == 0)
solver.Add(M[5,5] == 0)
solver.Add(M[5,6] == 0)
solver.Add(M[6,0] == 0)
solver.Add(M[6,1] == 0)
solver.Add(M[6,2] == 0)
solver.Add(M[6,5] == 0)
solver.Add(M[6,6] == 0)
solver.Add(M[6,8] == 0)
solver.Add(M[7,0] == 0)
solver.Add(M[7,1] == 0)
solver.Add(M[7,2] == 0)
solver.Add(M[7,7] == 0)
solver.Add(M[8,0] == 0)
solver.Add(M[8,1] == 0)
solver.Add(M[8,2] == 0)
solver.Add(M[8,3] == 0)
solver.Add(M[8,6] == 0)
solver.Add(M[8,8] == 0)

#Einstellungen zur Vermeidung von Doppelarbeit(Die Sehenswürdigkeit wird nur einmal besucht. Fälle, in denen beide nicht besucht werden, sind möglich)
solver.Add(M[0,1] + M[1,0] <= 1)
solver.Add(M[0,3] + M[3,0] <= 1)
solver.Add(M[0,4] + M[4,0] <= 1)
solver.Add(M[1,2] + M[2,1] <= 1)
solver.Add(M[1,3] + M[3,1] <= 1)
solver.Add(M[1,4] + M[4,1] <= 1)
solver.Add(M[1,5] + M[5,1] <= 1)
solver.Add(M[2,4] + M[4,2] <= 1)
solver.Add(M[2,5] + M[5,2] <= 1)
solver.Add(M[3,4] + M[4,3] <= 1)
solver.Add(M[3,6] + M[6,3] <= 1)
solver.Add(M[3,7] + M[7,3] <= 1)
solver.Add(M[4,5] + M[5,4] <= 1)
solver.Add(M[4,6] + M[6,4] <= 1)
solver.Add(M[4,7] + M[7,4] <= 1)
solver.Add(M[4,8] + M[8,4] <= 1)
solver.Add(M[5,7] + M[7,5] <= 1)
solver.Add(M[5,8] + M[8,5] <= 1)
solver.Add(M[6,7] + M[7,6] <= 1)
solver.Add(M[7,8] + M[8,7] <= 1)


#Bedingungen für M.
#Bewegen Sie sich nicht gleichzeitig von einer Attraktion zu mehreren Attraktionen
for i in range(9):
    solver.Add(solver.Sum([M[i,j] for j in range(9)]) <= 1)

#Routenkontinuitätsbedingung
#0 Startpunkt
step = [1,3,4]
solver.Add(solver.Sum([M[0,s] for s in step]) == solver.Sum([M[s,0] for s in step]))
#1 Ausgangspunkt
step = [0,2,3,4,5]
solver.Add(solver.Sum([M[1,s] for s in step]) == solver.Sum([M[s,1] for s in step]))
#2 Ausgangspunkt
step = [1,4,5]
solver.Add(solver.Sum([M[2,s] for s in step]) == solver.Sum([M[s,2] for s in step]))
#3 Ausgangspunkte
step = [0,1,4,6,7]
solver.Add(solver.Sum([M[3,s] for s in step]) == solver.Sum([M[s,3] for s in step]))
#4 Ausgangspunkt
step = [0,1,2,3,5,6,7,8]
solver.Add(solver.Sum([M[4,s] for s in step]) == solver.Sum([M[s,4] for s in step]))
#5 Ausgangspunkte
step = [1,2,4,7,8]
solver.Add(solver.Sum([M[5,s] for s in step]) == solver.Sum([M[s,5] for s in step]))
#6 Ausgangspunkt
step = [3,4,7]
solver.Add(solver.Sum([M[6,s] for s in step]) == solver.Sum([M[s,6] for s in step]))
#7 Ausgangspunkt
step = [3,4,5,6,8]
solver.Add(solver.Sum([M[7,s] for s in step]) == solver.Sum([M[s,7] for s in step]))
#8 Ausgangspunkte
step = [4,5,7]
solver.Add(solver.Sum([M[8,s] for s in step]) == solver.Sum([M[s,8] for s in step]))

#Definition der Beziehung zwischen S und M.
#0 Startpunkt
step = [1,3,4]
solver.Add(S[0] - (solver.Sum([M[0,s] for s in step]) + solver.Sum([M[s,0] for s in step])) / 2 == 0)
#1 Ausgangspunkt
step = [0,2,3,4,5]
solver.Add(S[1] - (solver.Sum([M[1,s] for s in step]) + solver.Sum([M[s,1] for s in step])) / 2 == 0)
#2 Ausgangspunkt
step = [1,4,5]
solver.Add(S[2] - (solver.Sum([M[2,s] for s in step]) + solver.Sum([M[s,2] for s in step])) / 2 == 0)
#3 Ausgangspunkte
step = [0,1,4,6,7]
solver.Add(S[3] - (solver.Sum([M[3,s] for s in step]) + solver.Sum([M[s,3] for s in step])) / 2 == 0)
#4 Ausgangspunkt
step = [0,1,2,3,5,6,7,8]
solver.Add(S[4] - (solver.Sum([M[4,s] for s in step]) + solver.Sum([M[s,4] for s in step])) / 2 == 0)
#5 Ausgangspunkte
step = [1,2,4,7,8]
solver.Add(S[5] - (solver.Sum([M[5,s] for s in step]) + solver.Sum([M[s,5] for s in step])) / 2 == 0)
#6 Ausgangspunkt
step = [3,4,7]
solver.Add(S[6] - (solver.Sum([M[6,s] for s in step]) + solver.Sum([M[s,6] for s in step])) / 2 == 0)
#7 Ausgangspunkt
step = [3,4,5,6,8]
solver.Add(S[7] - (solver.Sum([M[7,s] for s in step]) + solver.Sum([M[s,7] for s in step])) / 2 == 0)
#8 Ausgangspunkte
step = [4,5,7]
solver.Add(S[8] - (solver.Sum([M[8,s] for s in step]) + solver.Sum([M[s,8] for s in step])) / 2 == 0)

#Berechnung der Zufriedenheit
satisfy = solver.Sum([S[i] * satisfyDef[i] for i in range(9)])

#Berechnung der Verweildauer
stayTime = solver.Sum([S[i] * stayTimeDef[i] for i in range(9)])

#Berechnung der Reisezeit
moveTime = solver.Sum([M[i,j] * moveTimeDef[i,j] for i in range(9) for j in range(9)])

#Berechnung der Gesamtzeit
totalTime = stayTime + moveTime

#Allgemeine Zeitbeschränkungen
solver.Add(totalTime <= 200)

#Maximieren Sie die Zufriedenheit
solver.Maximize(satisfy)


#Lösungsausführung
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    print('satisfy', satisfy.solution_value())
    print('stayTime', stayTime.solution_value())
    print('moveTime', moveTime.solution_value())
    print('totalTime', totalTime.solution_value())
    for i in range(9):
        print(i,S[i].solution_value())
    for i in range(9):
        for j in range(9):
            if M[i,j].solution_value() >= 0.5:
                print('M',i,j,'=',M[i,j].solution_value())

else:
    print('The problem does not have an optimal solution.')

Ausstellungsstück

Dieser Artikel basiert auf den Übungen im Referenztext "Problemlösungsserie mit Python: Erstellen eines Optimierungsmodells mithilfe einer Datenanalysebibliothek" zur mathematischen Optimierung.

■ Referenztext "Problemlösungsserie von Python: So erstellen Sie ein Optimierungsmodell mithilfe einer Datenanalysebibliothek" Tsutomu Saito [Autor] Modern Science Company [Verlagswesen]

Meinungen etc.

Wenn Sie Meinungen oder Korrekturen haben, lassen Sie es uns bitte wissen.