[PYTHON] Résolvez les problèmes d'optimisation des combinaisons avec les outils OR de Google (5) Décidez d'un cours de date

introduction

Cet article est le 5ème article à résoudre le problème pratique du texte de référence "Série de résolution de problèmes par Python: Comment faire un modèle d'optimisation à l'aide d'une bibliothèque d'analyse de données" sur l'optimisation mathématique.

Le premier article est ci-dessous. Veuillez d'abord voir ici.

Résolvez le problème pratique du modèle d'optimisation mathématique avec les OU-Tools de Google (1) Le problème de remplissage de masse le plus simple https://qiita.com/ttlabo/private/7e8c93f387814f99931f

Décidons un cours de date

Il s'agit d'un problème appliqué qui apparaît dans le texte de référence. Essayons les problèmes suivants à la fois.

: speech_balloon: Problème

ruby:8.4.problème

Rencontre dans un parc d'attractions avec 8 attractions(8-Figure 4)。
Maximisez la satisfaction totale dans le délai de 200 minutes.
Il n'est pas nécessaire de faire le tour de tous les cours de dates.
Optimiser le cours de date qui remplit les conditions.

: question: ** Penser **

■ Politique de modélisation Compte tenu de la limite de temps de 200 minutes, nous envisagerons de maximiser autant que possible la satisfaction sans faire le tour. Pour ce faire, préparez les variables suivantes.

: point_right: définition de variable

\begin{eqnarray*}

S_i\;&\small{:=}&\;\small{Choix de la i-ème attraction}\\
M_{ij}\;&\small{:=}&\;\small{Passer de la i-ème attraction à la j-ème attraction}\\
satisfy\;&\small{:=}&\;\small{Satisfaction finale(Total)}\\
stayTime\;&\small{:=}&\;\small{Temps de séjour final(Total)}\\
moveTime\;&\small{:=}&\;\small{Temps de trajet final(Total)}\\
totalTime\;&\small{:=}&\;\small{Tout le temps(Somme de la satisfaction finale et du temps de séjour)}

\end{eqnarray*}

La résolution de l'optimisation donne la valeur optimale de ces variables pour déterminer le cours de la date. De plus, les valeurs et informations connues à l'avance sont définies comme des constantes comme suit.

: point_right: définition constante

\begin{eqnarray*}

Satisfaction satisfaction constanteDef\\
Rester à temps constant stayTimeDef\\
Déplacer la constante de temps moveTimeDef

\end{eqnarray*}

L'ordre est inversé, mais définissez d'abord les valeurs des constantes comme suit: (1) Définissez la valeur de la constante de satisfaction comme suit.

ruby:8.4.renshu.py

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

satisfDef est un tableau, et la satisfaction de la i-ème attraction est satisfDef [i]. Par exemple, le niveau de satisfaction de la deuxième attraction est de 36. Le numéro d'indice de l'attraction sera compté à partir de 0. (2) Définissez les valeurs de la constante de temps de séjour comme suit.

ruby:8.4.renshu.py

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

stayTimeDef est un tableau et le temps de séjour de la i-ème attraction est stayTimeDef [i]. (3) Réglez les valeurs de la constante de temps de mouvement comme suit.

ruby:8.4.renshu.py

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

moveTimeDef est un type Dictinary, et le temps pour passer de i à j est moveTimeDef [i, j]. Par exemple, le temps de trajet lors du passage de la 0e attraction (entrée) à la 3e attraction (tasse à café) est moveTimeDef [0,3], soit 7 minutes.

(1) Constante de satisfaction, (2) Constante de temps de séjour et (3) Constante de temps de déplacement sont les valeurs définies dans le texte de référence.

Ensuite, définissez les variables Si et Mij comme suit. (1) Si est défini comme suit.

ruby:8.4.renshu.py

#Variables selon lesquelles choisir une attraction
# 1:Choisir/ 0:Non séléctionné
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

Ici, les 0e à 8e attractions sont définies par les variables «1: Select» ou «0: Do not select» (type BoolVar). Par exemple, si S [4] = 1, cela signifie choisir la 4ème attraction.

(2) Mij est défini comme suit.

ruby:8.4.renshu.py

#Variable de passer de i à j concernant le mouvement
# 1:En mouvement/ 0:Ne bougez pas
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

Ici, chaque combinaison d'attractions 0e à 8e est définie par la variable «1: move» ou «0: do not move» (type BoolVar). Il y a 9 combinaisons x 9 combinaisons, 81 combinaisons au total. Par exemple, si M [1,3] = 1, cela signifie passer de la première attraction à la troisième attraction.

En utilisant les variables et constantes ci-dessus, résolvez le problème d'optimisation tout en définissant diverses conditions (contraintes) entre les variables et les constantes.

: a: ** Réponse **

Considérez le programme. Le contenu du programme suit essentiellement le guide OR-Tools de Google. (https://developers.google.com/optimization)

Écrivez un sort au début du programme.

ruby:8.4.renshu.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

Puisqu'il est résolu par le solveur de planification d'entiers mixtes, il est déclaré ci-dessous.

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)

Ensuite, nous définissons des constantes.

ruby:8.4.renshu.py

#Définition constante=================================================================

#Nom de l'attraction
attrDef = ['','entrée','Café','bateau','Coupe','Restaurant','grande roue',
           'Maison hantée','Coaster','Labyrinthe']

#Constante de satisfaction
satisfyDef = [0,50,36,45,79,55,63,71,42]

#Rester constant dans le temps
stayTimeDef = [0,20,28,15,35,17,18,14,22]

La première définition ci-dessus attrDef n'est pas utilisée dans ce programme. Cette fois, je l'ai défini pour le moment. Comme je l'ai écrit dans l'explication de la définition constante, satisfactionDef et stayTimeDef sont des tableaux, et le numéro d'index et le numéro d'attraction sont liés. Le numéro d'index 0 correspond au numéro d'attraction 0 (entrée), la satisfaction est 0 et le temps de séjour est 0. Le temps de trajet est défini comme suit.

ruby:8.4.renshu.py

#Constante de temps de déplacement
# moveTimeDef[i,j]← Il est temps de passer de i à j
moveTimeDef = {}
moveTimeDef[0,0] = 0
moveTimeDef[0,1] = 9
moveTimeDef[0,2] = 0
moveTimeDef[0,3] = 7
〜

Ici, le temps de trajet de l'itinéraire qui ne peut pas être parcouru est réglé sur 0. Dans ce qui précède, seuls 4 itinéraires sont décrits, mais tous les itinéraires sont définis dans la source entière publiée ci-dessous. Ensuite, définissez les variables.

ruby:8.4.renshu.py

#Définition variable=================================================================

#Variables selon lesquelles choisir une attraction
# 1:Choisir/ 0:Non séléctionné
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

#Variable de passer de i à j concernant le mouvement
# 1:En mouvement/ 0:Ne bougez pas
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

Comme expliqué précédemment, S et M ci-dessus sont déclarés comme des variables prenant 0/1. Le solveur OR-Tools calcule et décide quelle valeur prendre.

ruby:8.4.renshu.py

#Déclarer satisfaction
satisfy = solver.IntVar(0.0, 1000, 'satisfy')
#Déclarez la durée du séjour
stayTime = solver.IntVar(0.0, 1000, 'stayTime')
#Variable de temps de trajet
moveTime = solver.IntVar(0.0, 1000, 'moveTime')
#Variable de temps entier
totalTime = solver.IntVar(0.0, 1000, 'totalTime')

Déclarez la satisfaction ci-dessus, le temps de séjour, le temps de trajet et le temps total (temps de séjour + temps de trajet) comme des variables qui prennent des nombres entiers de 0 à 100, respectivement. Maintenant que nous avons préparé les constantes et les variables, définissons les conditions (définissons l'expression de contrainte).

En ce qui concerne le paramétrage de l'expression de contrainte, le texte de référence a le supplément suivant, nous allons donc l'assembler en incluant cette condition.

ruby:8.4.problème

・ Une fois que vous avez sélectionné une attraction, visitez-la.
・ Quittez lorsque vous entrez dans l'attraction.
-Connecté depuis l'entrée.(Ne finissez pas au milieu)

Voici la source des contraintes.

ruby:8.4.renshu.py

#Expression de contrainte===================================================================

#Assurez-vous de passer l'entrée
solver.Add(S[0] == 1)

Définissez l'expression de contrainte ci-dessus pour l'entrée. Puisque l'entrée est toujours sélectionnée, réglez la valeur de S [0] sur 1.

ruby:8.4.renshu.py

#Définir des restrictions de mouvement
#Définissez M sur 0 pour les itinéraires qui ne bougent pas
solver.Add(M[0,0] == 0)
solver.Add(M[0,2] == 0)
solver.Add(M[0,5] == 0)
~

Définissez l'itinéraire de la même manière que la définition de constante ci-dessus. Puisque M est une variable, le solveur peut la déterminer, mais ici elle est définie explicitement. Réglez M [i, j] sur 0 pour les itinéraires qui ne bougent pas. Par exemple, vous ne pouvez pas passer de la 0e à la 0e attraction, et ainsi de suite de la 0e à la 5e attraction. Définissez un total de 41 itinéraires sur 0.

ruby:8.4.renshu.py

#Paramètres pour éviter la duplication(L'attraction n'est visitée qu'une seule fois. Les cas où les deux ne sont pas visités sont possibles)
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)
~

Après être passé d'une certaine attraction i à j ci-dessus, définissez les conditions pour que l'itinéraire de mouvement ne soit pas inversé et retourné à i. Par exemple, si vous passez de la 0ème attraction à la 1ère attraction, M [0,1] = 1, définissez la valeur de M [1,0] sur l'itinéraire inverse sur 0 (ne bougez pas). Je vais. La même chose s'applique à l'itinéraire de mouvement inverse. Aussi, si M [0,1] + M [1,0] == 1, il se déplacera toujours, donc même s'il ne bouge pas, M [0,1] + M [1,0] <= 1 Je vais. Configurez un total de 20 itinéraires.

ruby:8.4.renshu.py

#Conditions pour M
#Ne passez pas d'une attraction à plusieurs attractions en même temps
for i in range(9):
    solver.Add(solver.Sum([M[i,j] for j in range(9)]) <= 1)

Définissez les conditions ci-dessus pour ne pas passer d'une attraction à plusieurs attractions en même temps. Ceci est défini comme le fait que chaque attraction i ne peut emprunter qu'un seul itinéraire vers chaque j (voir la figure ci-dessous).

Ensuite, définissez la condition de continuité de l'itinéraire comme suit. La continuité de l'itinéraire signifie que vous ne sélectionnez pas les attractions qui ne sont pas connectées comme indiqué dans la figure ci-dessous.

L'expression de contrainte de la condition selon laquelle l'itinéraire est connecté (continu) est la suivante.

ruby:8.4.renshu.py

#Condition de continuité de l'itinéraire
#0 point de départ
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 point de départ
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]))
~

Regardons ce qui précède à partir de la première attraction. Il existe trois voies vers l'attraction 1: M [0,1], M [3,1], M [4,1]. Comme le montre la figure ci-dessous (modèle 1), disons que vous entrez dans l'attraction 1 par un itinéraire. Ici, on suppose que M [4,1] est entré parmi M [0,1], M [3,1], M [4,1](flèche rouge).

Une seule des trois routes peut être empruntée pour entrer dans l'attraction 1, de sorte que la valeur de l'un quelconque de M [0,1], M [3,1], M [4,1] est 1, et les autres La valeur de sera 0. Définissez ce qui suit comme expression de contrainte.

solver.Sum ([M [s, 1] pour s à l'étape]) = 1… Équation ①

Puisque la condition de réglage de l'expression de contrainte est "Sortez lorsque vous entrez dans une attraction", considérez l'itinéraire pour passer de l'attraction 1 à une autre attraction. Comme le montre la figure ci-dessus (modèle 2), trois attractions peuvent être déplacées de l'attraction 1, mais vous devrez en sélectionner une. L'expression de contrainte permettant d'en sélectionner une parmi trois est

solver.Sum ([M [1, s] pour s à l'étape]) = 1… Équation ②

Sera. Cependant, puisque nous avons supposé que nous prendrions la route de M [4,1] plus tôt, la route qui peut réellement être prise est soit M [1,2], soit M [1,5](figure ci-dessus (schéma 3)). Le solveur calculera la route à emprunter.

De plus, il est possible que vous ne puissiez pas accéder à l'attraction 1, auquel cas vous ne passerez pas à la suivante. Dans ce cas, la somme de Ms pour les routes entrantes et sortantes est de 0. Par conséquent, les conditions de l'itinéraire pour entrer et sortir de l'attraction 1 devraient être les suivantes en utilisant les équations (1) et (2).

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

Jusqu'à présent, nous avons expliqué l'expression de contrainte de continuité d'itinéraire pour l'attraction 1. Dans la source réelle, chacune de l'attraction 0 à l'attraction 8 est définie de la même manière. Les expressions de contrainte pour le reste des attractions sont définies à travers les sources répertoriées ci-dessous.

En outre, pensez à la relation entre les attractions que vous visitez et les itinéraires d'entrée et de sortie avant et après. Similaire à la condition de continuité de chemin, mais définit la relation entre S et M comme une expression de contrainte.

ruby:8.4.renshu.py

#Définition de la relation entre S et M
#0 point de départ
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 point de départ
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)
~

Concernant ce qui précède, le contenu de l'expression de contrainte signifie "Si vous visitez une certaine attraction, il y a un itinéraire entrant et sortant. Si vous ne visitez pas, vous ne prenez pas d'itinéraire." Regardons cela à partir de l'attraction 1. Tout d'abord, vérifiez la carte d'itinéraire suivante.

Lors de la sélection de l'attraction 1, il existe des itinéraires possibles pour entrer et sortir. En regardant le modèle 1 pour la route entrante, ce qui suit est établi car il suit une des routes bleu M [0,1], route verte M [3,1] et route rouge M [4,1]. Faire.

solver.Sum ([M [s, 1] pour s à l'étape]) = 1… Équation ①

De même pour l'itinéraire de sortie, la condition de la somme des itinéraires de chaque couleur est

solver.Sum ([M [1, s] pour s à l'étape]) = 1… Équation ②

Lorsque vous visitez l'attraction 1, la valeur de S [1] est 1, vous pouvez donc relier cette valeur aux équations (1) et (2) comme suit.

Valeur de S [1] - (Formule ① + Formule ②) ÷ 2 = 0 ... Formule ③

De plus, cette formule ③ tient même si vous ne visitez pas l'attraction 1. Puisque la valeur de S [1] est 0, et les valeurs des équations ① et ② sont également 0, respectivement.

0　-　(0　+　0)　÷　2　=　0

Par conséquent, la relation entre S et M peut être définie en utilisant l'équation (3) comme suit.

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

Dans la source réelle, chacune de l'attraction 0 à l'attraction 8 est définie de la même manière. Les expressions de contrainte pour le reste des attractions sont définies à travers les sources répertoriées ci-dessous.

Ceci conclut l'explication des expressions de contraintes complexes. Les contraintes restantes sont définies ci-dessous.

ruby:8.4.renshu.py

#Calcul de la satisfaction
satisfy = solver.Sum([S[i] * satisfyDef[i] for i in range(9)])

#Calcul du temps de séjour
stayTime = solver.Sum([S[i] * stayTimeDef[i] for i in range(9)])

#Calcul du temps de trajet
moveTime = solver.Sum([M[i,j] * moveTimeDef[i,j] for i in range(9) for j in range(9)])

#Calcul du temps total
totalTime = stayTime + moveTime

La satisfaction et le temps de séjour ci-dessus sont multipliés par la valeur d'attraction sélectionnée S [i] et chaque valeur constante, et la somme de celles-ci est prise. Si vous sélectionnez une attraction, la valeur S [i] est 1, sinon S [i] est 0, donc si vous prenez la somme, seule la valeur de l'attraction sélectionnée sera calculée.

Pour le temps de trajet, multipliez chaque combinaison i, j par la valeur M [i, j] et la valeur constante de l'itinéraire de déplacement, et prenez la somme de celles-ci. En outre, la durée totale est «temps de séjour + temps de trajet».

Enfin, la condition est «Maximiser la satisfaction totale dans le délai de 200 minutes».

ruby:8.4.renshu.py

#Contraintes de temps globales
solver.Add(totalTime <= 200)

#Maximisez la satisfaction
solver.Maximize(satisfy)

Les conditions ci-dessus pour la durée totale de 200 minutes ou moins et les conditions pour maximiser la satisfaction sont définies séparément.

C'est tout pour définir l'expression de contrainte. Ensuite, la solution est exécutée.

ruby:8.4.renshu.py

status = solver.Solve()

Dans la source suivante, si une solution est trouvée, la valeur S [i] à chaque i et la valeur M [i, j] à i, j lors du déplacement seront affichées.

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.')

C'est la fin de la programmation. Le résultat réel de l'exécution est le suivant.

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

À la suite du calcul d'optimisation, le cours de la date a été décidé. Le parcours ne prend que 200 minutes et le niveau de satisfaction est de 405.

En outre, la répartition du temps de séjour et du temps de déplacement était de 141 minutes pour le temps de séjour et de 51 minutes pour le temps de déplacement.

En regardant l'attraction à sélectionner, la valeur autre que S [2] est 1, donc C'est un itinéraire pour visiter des attractions autres que les bateaux.

De plus, l'itinéraire à parcourir est basé sur la valeur de M [i, j]. 　0 → 3 → 6 → 7 → 8 → 5 → 4 →1→0 J'ai la réponse.

L'ensemble du programme est présenté ci-dessous.

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)


#Définition constante=================================================================

#Nom de l'attraction
attrDef = ['','entrée','Café','bateau','Coupe','Restaurant','grande roue',
           'Maison hantée','Coaster','Labyrinthe']

#Constante de satisfaction
satisfyDef = [0,50,36,45,79,55,63,71,42]

#Rester constant dans le temps
stayTimeDef = [0,20,28,15,35,17,18,14,22]

#Constante de temps de déplacement
# moveTimeDef[i,j]← Il est temps de passer de i à j
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


#Définition variable=================================================================

#Variables selon lesquelles choisir une attraction
# 1:Choisir/ 0:Non séléctionné
S = {}
for i in range(9):
    S[i] = solver.BoolVar("S%i" % i)

#Variable de passer de i à j concernant le mouvement
# 1:En mouvement/ 0:Ne bougez pas
M = {}
for i in range(9):
    for j in range(9):
        M[i,j] = solver.BoolVar("M%i%i" % (i,j))

#Déclarer satisfaction
satisfy = solver.IntVar(0.0, 1000, 'satisfy')
#Déclarez la durée du séjour
stayTime = solver.IntVar(0.0, 1000, 'stayTime')
#Variable de temps de trajet
moveTime = solver.IntVar(0.0, 1000, 'moveTime')
#Variable de temps entier
totalTime = solver.IntVar(0.0, 1000, 'totalTime')


#Expression de contrainte===================================================================

#Assurez-vous de passer l'entrée
solver.Add(S[0] == 1)

#Définir des restrictions de mouvement
#Définissez M sur 0 pour les itinéraires qui ne bougent pas
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)

#Paramètres pour éviter la duplication(L'attraction n'est visitée qu'une seule fois. Les cas où les deux ne sont pas visités sont possibles)
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)


#Conditions pour M
#Ne passez pas d'une attraction à plusieurs attractions en même temps
for i in range(9):
    solver.Add(solver.Sum([M[i,j] for j in range(9)]) <= 1)

#Condition de continuité de l'itinéraire
#0 point de départ
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 point de départ
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 point de départ
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 points de départ
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 point de départ
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 points de départ
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 point de départ
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 point de départ
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 points de départ
step = [4,5,7]
solver.Add(solver.Sum([M[8,s] for s in step]) == solver.Sum([M[s,8] for s in step]))

#Définition de la relation entre S et M
#0 point de départ
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 point de départ
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 point de départ
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 points de départ
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 point de départ
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 points de départ
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 point de départ
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 point de départ
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 points de départ
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)

#Calcul de la satisfaction
satisfy = solver.Sum([S[i] * satisfyDef[i] for i in range(9)])

#Calcul du temps de séjour
stayTime = solver.Sum([S[i] * stayTimeDef[i] for i in range(9)])

#Calcul du temps de trajet
moveTime = solver.Sum([M[i,j] * moveTimeDef[i,j] for i in range(9) for j in range(9)])

#Calcul du temps total
totalTime = stayTime + moveTime

#Contraintes de temps globales
solver.Add(totalTime <= 200)

#Maximisez la satisfaction
solver.Maximize(satisfy)


#Exécution de la solution
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.')

Exposition

Cet article est basé sur les exercices décrits dans le texte de référence «Série de résolution de problèmes avec Python: Comment créer un modèle d'optimisation à l'aide d'une bibliothèque d'analyse de données» sur l'optimisation mathématique.

■ Texte de référence "Série de résolution de problèmes par Python: Comment créer un modèle d'optimisation à l'aide d'une bibliothèque d'analyse de données" Tsutomu Saito [Auteur] Modern Science Company [édition]

Opinions etc.

Si vous avez des opinions ou des corrections, veuillez nous en informer.