[PYTHON] ○○ 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)

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!

`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.

`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