Résolvez des exercices de modèle d'optimisation mathématique avec les outils OR de Google
introduction
Cet article est le 4ème article à résoudre l'exercice 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
Résoudre la place du nombre (Nampure)
Ceci est le troisième exercice du texte de référence. Essayons les problèmes suivants à la fois.
: speech_balloon: Problème
ruby:7.3.problème
Numéro de place dans la figure ci-dessous(Nampre)Résoudre. Cependant, les conditions sont les suivantes.
① Assurez-vous de remplir les nombres 1 à 9 dans tous les carrés 9x9.
(2) Le même numéro ne peut être utilisé qu'une seule fois par ligne, par colonne et par 3x3.
③ Si le numéro est rempli, utilisez ce numéro.
: question: ** Penser **
■ Pensez à un modèle mathématique Considérez 729 boîtes 9x9x9, comme illustré dans la figure 2. La direction de l'axe est la ligne, la colonne et le numéro de cellule. Un numéro de cellule signifie un nombre qui tient dans chaque cadre du nombre.
Supposons qu'une boîte ait des numéros de cellule sélectionnés ou non sélectionnés.
Par exemple, supposons que la première case à partir du bas de la colonne de la ligne 1 ait 1 si le nombre 1 est sélectionné dans la cellule de la 1ère ligne 1 colonne du nombre et 0 s'il n'est pas sélectionné. Ensuite, la deuxième case à partir du bas de la première ligne et de la première cellule de colonne indique si le numéro 2 est sélectionné ou non, et de même, la case du haut indique si le numéro 9 est sélectionné ou non. Celles-ci continuent de la même manière jusqu'à la 9e ligne et la 9e colonne. En général, si la case du numéro de cellule z dans la ligne x y colonne numéro de cellule z est 1, cela signifie que le nombre dans la cellule de la ligne x ligne y colonne du nombre est z.
En supposant une telle boîte, nous la formulerons.
: a: ** Réponse **
Chacune de ces 729 cases sera 0 ou 1. Les contraintes sont les suivantes:
(1) Un seul numéro peut être saisi dans une cellule de Nampre. Autrement dit, la valeur totale de 9 cases de 1x1x9 (ligne x colonne x numéro de cellule) est 1. (2) Un seul numéro peut être saisi dans une ligne de cellules. La valeur totale de 9 boîtes de 9x1x1 est 1 (3) Un seul numéro peut être saisi dans une rangée de cellules. La valeur totale de 9 boîtes de 1x9x1 est 1. (4) Un seul nombre peut être saisi dans le carré 3x3. La valeur totale de 9 boîtes de 3x3x1 est 1.
- Les carrés 3x3 sont les 9 carrés indiqués par la ligne épaisse dans la figure jointe à l'énoncé du problème. (5) Si le numéro est spécifié depuis le début (le chiffre joint à l'énoncé du problème), utilisez ce numéro. La valeur totale d'une boîte de 1x1x1 est 1.
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:7.4.renshu.py
from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np
Puisqu'il est résolu par le solveur de planification d'entiers mixtes, il est déclaré ci-dessous.
ruby:7.4.renshu.py
# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
Définissez les carrés 9x9 du nombre présenté en question dans le tableau à deux dimensions pré.
ruby:7.4.renshu.py
pre = [[0,0,6,0,0,0,0,0,1],
[0,7,0,0,6,0,0,5,0],
[8,0,0,1,0,3,2,0,0],
[0,0,5,0,4,0,8,0,0],
[0,4,0,7,0,2,0,9,0],
[0,0,8,0,1,0,7,0,0],
[0,0,1,2,0,5,0,0,3],
[0,6,0,0,7,0,0,8,0],
[2,0,0,0,0,0,4,0,0]]
Déclarez les cases 9x9x9 comme les dés variables du tableau en trois dimensions.
ruby:7.4.renshu.py
dice = {}
Pour les boîtes 9x9x9 (boîtes à dés), définissez chaque boîte avec une variable. Bouclez la ligne de 1 à 9 avec la variable x. Bouclez la colonne de 1 à 9 avec la variable y. Boucle avec la variable z dans le sens du numéro de cellule.
ruby:7.4.renshu.py
#Définition variable de la boîte à dés
for x in range(9):
for y in range(9):
for z in range(9):
dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))
Les contraintes sont définies ci-dessous.
** Contraintes (1) ** ʻUn seul nombre peut être entré dans une cellule du nombre. Autrement dit, la valeur totale de 9 cases de 1x1x9 (ligne x colonne x numéro de cellule) est 1. '' Utilisez solver.Sum () pour obtenir la valeur totale. La valeur à totaliser est de 1 à 9 carrés dans la direction z des dés, et z est bouclé de 1 à 9 dans la notation d'inclusion (en fait, la valeur d'index boucle de 0 à 8).
ruby:7.4.renshu.py
for x in range(9):
for y in range(9):
solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)
** Contrainte (2) ** ʻUn seul numéro peut être entré dans la cellule d'une ligne. La valeur totale de 9 boîtes de 9x1x1 est 1`
ruby:7.4.renshu.py
for y in range(9):
for z in range(9):
solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)
** Contrainte (3) ** (3) Un seul numéro peut être saisi dans une colonne. La valeur totale de 9 boîtes de 1x9x1 est 1`
ruby:7.4.renshu.py
for x in range(9):
for z in range(9):
solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)
** Contrainte (4) ** (4) Un seul nombre peut être saisi dans le carré 3x3. La valeur totale de 9 boîtes de 3x3x1 est 1`
ruby:7.4.renshu.py
#Boucle dans la direction de l'axe z
for z in range(9):
#Boucle la coordonnée x prise par la cellule centrale du carré 3x3
for m1 in [1,4,7]:
#Boucle la coordonnée y prise par la cellule centrale du carré 3x3
for m2 in [1,4,7]:
solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)
** Contrainte (5) ** (5) Dans la cellule où le nombre est spécifié depuis le début (le chiffre attaché à l'énoncé du problème), c'est le nombre. La valeur totale d'une boîte de 1x1x1 est 1`
ruby:7.4.renshu.py
for x in range(9):
for y in range(9):
if pre[x][y] != 0:
z = pre[x][y]
solver.Add(dice[x,y, z - 1] == 1)
C'est tout pour les contraintes. Trouver une solution. Cette fois, il n'est pas nécessaire de maximiser ou de minimiser.
ruby:7.4.renshu.py
#Exécution de la solution
status = solver.Solve()
Validez le résultat.
ruby:7.4.renshu.py
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print('Solution:')
print('ok')
print('Objective value =', solver.Objective().Value())
#Créer un tableau p pour l'affichage
p = []
for x in range(9):
for y in range(9):
for z in range(9):
if dice[x,y,z].solution_value() > 0.5:
p.append(z + 1)
print(np.reshape(p, (9, 9)))
print("Time = ", solver.WallTime(), " milliseconds")
else:
print('The problem does not have an optimal solution.')
Dans cette exécution, la solution suivante a été obtenue.
Solution: ok Objective value = 0.0 [[5 3 6 8 2 7 9 4 1] [1 7 2 9 6 4 3 5 8] [8 9 4 1 5 3 2 6 7] [7 1 5 3 4 9 8 2 6] [6 4 3 7 8 2 1 9 5] [9 2 8 5 1 6 7 3 4] [4 8 1 2 9 5 6 7 3] [3 6 9 4 7 1 5 8 2] [2 5 7 6 3 8 4 1 9]] Time = 477 milliseconds
Le nombre a été résolu ci-dessus. La figure ci-dessous montre cela dans la masse. La partie rose est la cellule dont le numéro a été décidé à l'avance lorsque la question a été posée.
L'ensemble du programme est décrit ci-dessous.
ruby:7.4.renshu.py
from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np
# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
pre = [[0,0,6,0,0,0,0,0,1],
[0,7,0,0,6,0,0,5,0],
[8,0,0,1,0,3,2,0,0],
[0,0,5,0,4,0,8,0,0],
[0,4,0,7,0,2,0,9,0],
[0,0,8,0,1,0,7,0,0],
[0,0,1,2,0,5,0,0,3],
[0,6,0,0,7,0,0,8,0],
[2,0,0,0,0,0,4,0,0]]
#Définition variable de la boîte à dés
dice = {}
for x in range(9):
for y in range(9):
for z in range(9):
dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))
#Contrainte 1-Un chiffre par carré(1 boîte sur 9 contenant 1 lors de la boucle dans la direction z)
for x in range(9):
for y in range(9):
solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)
#Contrainte 2-Verticale(direction y)Le même nombre est un(direction yにループした際に1が入る箱は9個のうち1個)
for x in range(9):
for z in range(9):
solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)
#Contrainte 3-côté(direction x)Le même nombre est un(direction xにループした際に1が入る箱は9個のうち1個)
for y in range(9):
for z in range(9):
solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)
#Contrainte 4-Un même nombre dans un carré 3x3
#Boucle dans la direction de l'axe z
for z in range(9):
#Boucle la coordonnée x prise par la cellule centrale du carré 3x3
for m1 in [1,4,7]:
#Boucle la coordonnée y prise par la cellule centrale du carré 3x3
for m2 in [1,4,7]:
solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)
#Contrainte 5-Le carré contenant le nombre est ce nombre
for x in range(9):
for y in range(9):
if pre[x][y] != 0:
z = pre[x][y]
#print('z=',z)
solver.Add(dice[x,y, z - 1] == 1)
#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())
#Créer un tableau p pour l'affichage
p = []
for x in range(9):
for y in range(9):
for z in range(9):
if dice[x,y,z].solution_value() > 0.5:
p.append(z + 1)
print(np.reshape(p, (9, 9)))
print("Time = ", solver.WallTime(), " milliseconds")
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.
Recommended Posts