○○ Résolution de problèmes dans le département de mathématiques avec optimisation

Qu'est-ce que c'est

["Département de mathématiques de l'Université Takeshi no Koma"](https://ja.wikipedia.org/wiki/%E3%81%9F%E3%81%91%E3%81%97%E3%81%AE%E3% 82% B3% E3% 83% 9E% E5% A4% A7% E6% 95% B0% E5% AD% A6% E7% A7% 91) J'ai essayé celui qui semble être résolu par l'optimisation. C'était.

Préparation à l'exécution en Python

python


import scipy.optimize, numpy as np, networkx as nx
from itertools import product
from pulp import *
from ortoolpy import addvar, addvars, addbinvar, addbinvars

Importez-le d'abord.

Problème d'attribution

Attribuez aux joueurs de baseball A à E des positions pour maximiser la force de l'équipe (plus le nombre est bas, mieux c'est).

joueur 1ère base 2e base 3e base SS champ extérieur
A 6 5 6 5 6
B 8 7 6 8 7
C 4 5 4 4 5
D 6 7 6 4 7
D 10 8 10 7 10

Problème de correspondance parfaite du poids minimum C'est vrai.

python


w = np.array([[6,5,6,5,6],
              [8,7,6,8,7],
              [4,5,4,4,5],
              [6,7,6,4,7],
              [10,8,10,7,10]])
N = len(w)
g = nx.Graph()
for i,j in product(range(N),range(N)):
    g.add_edge(i, j+N, weight=w.max()-w[i][j])
r = nx.max_weight_matching(g)
for i in range(N):
    print('ABCDE'[i], ['1ère base','2e base','3e base','SS','champ extérieur',][r[i]-N])
>>>
Un champ extérieur
B 3e base
C 1ère base
D SS
E 2e base

J'ai eu la même réponse.

Problème de lieu de réunion

Où la distance totale parcourue est-elle minimisée lorsque 1 à 5 personnes se rassemblent au même endroit?

[Problème d'optimisation non linéaire](bfbf4c185ed7004b5721 #% E9% 9D% 9E% E7% B7% 9A% E5% BD% A2% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E5% 95% Ce sera 8F% E9% A1% 8C).

Compte tenu de la distance dans la norme L2, [problème Weber](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A6%E3%82%A7%E3%83 % BC% E3% 83% 90% E3% 83% BC% E5% 95% 8F% E9% A1% 8C) C'est vrai.

python


pos = np.array([[1,2,1],[3,7,5],[5,3,2],[6,5,2],[7,1,3]]) # x,y,Nombre de personnes
def func(x):
    return sum(p[2]*np.linalg.norm(p[:2]-x) for p in pos)
print(scipy.optimize.fmin(func, [0,0]))
>>>
[ 4.80539237  4.38561398]

Puisqu'il s'agit d'un modèle de grille, je vais également calculer la norme L1.

python


m = LpProblem()
vx = addvar(cat=LpInteger)
vy = addvar(cat=LpInteger)
vp = addvars(pos.shape[0])
vq = addvars(pos.shape[0])
m += lpDot(pos[:,2], vp) + lpDot(pos[:,2], vq)
for i in range(pos.shape[0]):
    m += vp[i] >=   pos[i,0]-vx
    m += vp[i] >= -(pos[i,0]-vx)
    m += vq[i] >=   pos[i,1]-vy
    m += vq[i] >= -(pos[i,1]-vy)
m.solve()
print(value(vx),value(vy))
>>>
5.0 5.0

Problème de livraison postale chinoise

Partez du bureau de poste, livrez le courrier à tous les foyers, retournez à nouveau au bureau de poste, trouvez un itinéraire qui minimise la distance parcourue pendant ce temps.

[Problème de livraison postale chinoise](https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BA%BA%E9%83] % B5% E4% BE% BF% E9% 85% 8D% E9% 81% 94% E5% 95% 8F% E9% A1% 8C). Un coup (Oyler fermé) Si possible, le plus petit va de soi. Puisque vous pouvez écrire en un seul trait en éliminant les points d'ordre impair, vous pouvez résoudre le problème de correspondance parfaite du poids minimum en pondérant la distance uniquement avec les points d'ordre impair. La fermeture Euler se trouve dans nx.eulerian_circuit. Le programme est omis.

Problème de chaîne de chaussures

Trouvez la longueur la plus courte (la longueur jusqu'au nœud) lorsque vous passez la ficelle de chaussure à travers les chaussures à 16 trous, 8 dans chaque rangée, pour pouvoir les porter correctement! Chaque trou doit être connecté au trou de la rangée opposée.

Faites un graphique.

python


N = 8
g = nx.Graph()
for i in range(N):
    g.add_edge(i,i+N)
    if i<N-1:
        g.add_edge(i,i+N+1)
    if i:
        g.add_edge(i,i+N-1)
        g.add_edge(i-1,i)
        g.add_edge(i+N-1,i+N)
nx.draw_networkx(g)

image.png

J'essaierai de le résoudre.

python


def len_(i,j):
    k =abs(i-j)
    return 1 if k==1 else 2 if k==N else 2.236
m = LpProblem()
#Création de variables
for i,j in g.edges():
    g.edge[i][j]['Var'] = addbinvar()
m += lpSum([len_(i,j)*g.edge[i][j]['Var'] for i,j in g.edges()]) #Fonction objective
for i in range(2*N):
    #Il y a des points d'entrée et de sortie
    m += lpSum(dc['Var'] for dc in g.edge[i].values()) == 2
    m += lpSum(dc['Var'] for j,dc in g.edge[i].items()
               if abs(i-j) >= N-1) >= 1 #Connectez-vous avec l'autre côté
for k in range(1,N-2):
    #Relier
    m += lpSum(g.edge[i][j]['Var'] for i,j in
               [[k,k+1],[k,k+N+1],[k+N,k+1],[k+N,k+N+1]]) == 2
m.solve()
print(value(m.objective))
for i,j in g.edges():
    if value(g.edge[i][j]['Var']) > 0:
        print((i,j), end=', ')
>>>
25.416000000000004
(0, 8), (0, 1), (8, 9), (9, 2), (1, 10), (10, 11),
(2, 3), (11, 4), (3, 12), (12, 13), (4, 5), (13, 6),
(5, 14), (14, 15), (6, 7), (15, 7), 

J'ai eu la même réponse.

Kakkuro

Il y a 5 cartes avec des numéros de 0 à 9 écrits au recto et au verso (il n'y a pas de numéros en double). Si vous ajoutez les chiffres au recto, vous obtenez "19", et si vous retournez les trois à partir de la gauche, vous obtenez "20" si vous additionnez les nombres que vous pouvez voir. De même, il était de «35» pour l'avant et l'arrière avant et arrière, «11» pour l'avant et l'arrière avant et arrière, et «31» pour l'avant et l'arrière avant et arrière. Répondez aux numéros sur le devant de la première carte que vous avez vue dans l'ordre!

image.png

python


hint = [[(1,1,1,1,1),19],
        [(0,0,0,1,1),20],
        [(0,0,1,0,0),35],
        [(1,1,0,1,0),11],
        [(1,0,1,0,1),31]]
r = range(10)
m = LpProblem()
v = addbinvars(10,10) # i:position,j:Nombres
for i in r:
    m += lpSum(v[i]) == 1
    m += lpSum(v[j][i] for j in r) == 1
for ptn,n in hint:
    m += lpSum(lpDot(r,v[i if j else i+5])
        for i,j in enumerate(ptn)) == n
m.solve()
print((np.vectorize(value)(v)@r).reshape(2,-1))
>>>
[[ 3.  1.  9.  2.  4.]
 [ 6.  8.  0.  7.  5.]]

La même réponse.

Bill

Bâtiment C'est un casse-tête.

image.png

python


n = 5
hint = [([0,3,0,3,0], 1, 0,   0,   0,  0,  1),
        ([0,2,0,0,4], 1, 0,   0, n-1,  0, -1),
        ([0,0,0,4,0], 0, 1,   0,   0,  1,  0),
        ([0,4,0,0,0], 0, 1, n-1,   0, -1,  0)]
m = LpProblem()
v = np.array(addbinvars(n, n, n))
r = np.array(addvars(n, n))
def add(m, r, k, p, q, y, x):
    if k==0:
        return
    u = addbinvars(n-1)
    m += lpSum(u) == k - 1
    vmx = r[p,q]
    for i in range(1,n):
        vnx = r[p + y*i][q + x*i]
        m += vmx + n * u[i-1] >= vnx + 1
        m += vmx + 1 <= vnx + n - n * u[i-1]
        vtm = addvar()
        m += vmx <= vtm
        m += vnx <= vtm
        vmx = vtm
    m += vmx <= n
for i in range(n):
    for j in range(n):
        m += lpSum(v[i,j,:]) == 1
        m += lpDot(range(n), v[i,j]) + 1 == r[i,j]
        m += lpSum(v[i,:,j]) == 1
        m += lpSum(v[:,i,j]) == 1
    for h in hint:
        add(m, r, h[0][i], h[1]*i+h[3], h[2]*i+h[4], h[5], h[6])
m.solve()
np.vectorize(value)(r).astype(int).T.tolist()
>>>
[[4, 1, 3, 2, 5],
 [5, 4, 1, 3, 2],
 [3, 5, 2, 1, 4],
 [1, 2, 4, 5, 3],
 [2, 3, 5, 4, 1]]

C'est la même réponse.

c'est tout

Recommended Posts

○○ Résolution de problèmes dans le département de mathématiques avec optimisation
Résolution de "cubes en cubes" avec optimisation des combinaisons
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée
Étudier les mathématiques avec Python: résoudre des problèmes simples de probabilité
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Résolution d'équations de mouvement en Python (odeint)
Rechercher par la valeur de l'instance dans la liste
Résoudre les problèmes d'optimisation avec Python
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée
[Astuces] Problèmes et solutions dans le développement de python + kivy
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
L'histoire de la participation à AtCoder
[Compris dans la figure] Gestion de l'environnement virtuel Python par Pipenv
Utilisez le vecteur appris par word2vec dans la couche Embedding de LSTM
Lire la sortie standard d'un sous-processus ligne par ligne en Python
La puissance des solveurs d'optimisation combinée
L'histoire du "trou" dans le fichier
Résolution de l'amplitude des observations d'interféromètre
Résolution de la phase des observations de l'interféromètre
Trouvez la valeur minimale de la fonction par la méthode d'optimisation du groupe de particules (PSO)
Explication du modèle d'optimisation de la production par Python
[Comprendre en 3 minutes] Le début de Linux
Vérifiez le comportement du destroyer en Python
Le résultat de l'installation de python sur Anaconda
Comparaison des solutions aux problèmes d'appariement de poids
Lisez le fichier ligne par ligne avec Python
Lisez le fichier ligne par ligne avec Python
Principes de base pour exécuter NoxPlayer en Python
Pandas du débutant, par le débutant, pour le débutant [Python]
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
À la recherche du FizzBuzz le plus rapide en Python
Résolution du gain complexe des observations d'interféromètre
Trouver l'itinéraire des patrouilleurs en optimisant
[Calcul scientifique / technique par Python] Résolution du problème de la valeur aux limites des équations différentielles ordinaires au format matriciel, calcul numérique
Divise la chaîne de caractères par le nombre de caractères spécifié. En Ruby et Python.
Obtenir l'heure Unix de l'heure spécifiée par JST quel que soit le fuseau horaire du serveur avec Python
Obtenez le dernier élément du tableau en fractionnant les chaînes en Python et PHP
Sortie du nombre de cœurs de processeur en Python
Vérifiez le fonctionnement d'OpenCV3 installé par Anaconda
Signification de {numéro de version} dans le package mysql rpm
[Python] Trier la liste de pathlib.Path dans l'ordre naturel
Décidons le cours de date par optimisation de combinaison
Changer la taille de police de la légende dans df.plot
Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Faites correspondre la distribution de chaque groupe en Python
Trier les éléments d'un tableau en spécifiant des conditions
Afficher le résultat du traitement de la géométrie en Python
Copiez la liste en Python
Trouvez le nombre de jours dans un mois
Lire la sortie du sous-processus, ouvrir en temps réel
Découvrez la fraction de la valeur saisie en python
Résolution du problème N Queen avec l'optimisation continue / combinée
L'histoire de la recherche du n optimal dans N poing
Résolution du problème N Queen avec l'optimisation des combinaisons
Correction des arguments de la fonction utilisée dans map
Trouvez la solution de l'équation d'ordre n avec python
L'histoire de la lecture des données HSPICE en Python