[PYTHON] ○○ Probleme im Fachbereich Mathematik mit Optimierung lösen

Was ist das

["Mathematikabteilung der Universität 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) Ich habe das versucht, das durch Optimierung gelöst zu werden scheint. Es war.

Vorbereiten der Ausführung in 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

Importieren Sie es zuerst.

Zuweisungsproblem

Weisen Sie den Baseballspielern A bis E Positionen zu, um die Stärke des Teams zu maximieren (je niedriger die Zahl, desto besser).

Spieler	1. Basis	2. Basis	3. Basis	SS	Außenfeld
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

Problem der perfekten Anpassung des Mindestgewichts Das stimmt.

`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. Basis','2. Basis','3. Basis','SS','Außenfeld',][r[i]-N])
>>>
Ein Außenfeld
B 3. Base
C 1. Basis
D SS
E 2. Basis

Ich habe die gleiche Antwort bekommen.

Problem mit dem Treffpunkt

Wo wird die Gesamtfahrstrecke minimiert, wenn sich 1 bis 5 Personen an einem Ort versammeln?

[Nichtlineares Optimierungsproblem](bfbf4c185ed7004b5721 #% E9% 9D% 9E% E7% B7% 9A% E5% BD% A2% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E5% 95% Es wird 8F% E9% A1% 8C sein).

In Anbetracht der Entfernung in der L2-Norm [Weber-Problem](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) Richtig.

`python`


pos = np.array([[1,2,1],[3,7,5],[5,3,2],[6,5,2],[7,1,3]]) # x,y,Anzahl der Personen
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]

Da es sich um ein Gittermuster handelt, werde ich auch die L1-Norm berechnen.

`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

Problem mit der chinesischen Postzustellung

Verlassen Sie die Post, liefern Sie die Post an alle Häuser, kehren Sie wieder zur Post zurück und suchen Sie eine Route, die die in dieser Zeit zurückgelegte Strecke minimiert.

[Problem mit der chinesischen Postzustellung](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). One-Stroke-Schreiben (Oyler geschlossen )) Wenn möglich, ist das kleinste selbstverständlich. Da Sie mit einem Strich schreiben können, indem Sie die Punkte ungerader Reihenfolge entfernen, können Sie das Problem der perfekten Anpassung des Mindestgewichts (bbebc69ebc2549b0d5d2) lösen, indem Sie den Abstand nur mit den Punkten ungerader Reihenfolge gewichten. Der Euler-Verschluss befindet sich in nx.eulerian_circuit. Das Programm wird weggelassen.

Problem mit der Schuhschnur

Finden Sie die kürzeste Länge (die Länge bis zum Knoten), wenn Sie die Schuhschnur mit 16 Löchern, 8 in jeder Reihe, durch die Schuhe führen, damit Sie sie richtig tragen können! Jedes Loch muss mit dem Loch in der gegenüberliegenden Reihe verbunden werden.

Machen Sie ein Diagramm.

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

Ich werde versuchen, es zu lösen.

`python`


def len_(i,j):
    k =abs(i-j)
    return 1 if k==1 else 2 if k==N else 2.236
m = LpProblem()
#Variablenerstellung
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()]) #Zielfunktion
for i in range(2*N):
    #Es gibt In- und Out-Punkte
    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 #Verbinden Sie sich mit der anderen Seite
for k in range(1,N-2):
    #Verbinden
    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),

Ich habe die gleiche Antwort bekommen.

Kakkuro

Es gibt 5 Karten mit Zahlen von 0 bis 9 auf der Vorder- und Rückseite (es gibt keine doppelten Zahlen). Wenn Sie die Zahlen auf der Vorderseite hinzufügen, erhalten Sie "19", und wenn Sie die drei von links umdrehen, erhalten Sie "20", wenn Sie die Zahlen addieren, die Sie sehen können. In ähnlicher Weise war es "35" für vorne und hinten vorne und hinten, "11" für vorne und hinten vorne und hinten und "31" für vorne und hinten vorne und hinten. Beantworten Sie die Zahlen auf der Vorderseite der ersten Karte, die Sie gesehen haben, in der richtigen Reihenfolge!

`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:Zahlen
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.]]

Die gleiche Antwort.

Bill

Gebäude Es ist ein Rätsel.

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

Dies ist die gleiche Antwort.

das ist alles