[PYTHON] Optimaler Messplan - Ab der Oktoberausgabe des OP-Magazins

Was ist das

OR Society Oktoberausgabe der Zeitschrift ["** Students 'OR **" - Sonderfunktion](http://www.orsj.or.jp/ Aus e-library / elcorsj.html # 6110) möchte ich das Optimierungsproblem entsprechend aufgreifen und mit Python lösen. Zur Vorbereitung benötigen Sie Pandas, Fruchtfleisch, ortoolpy. Für die Umgebungskonstruktion [Kombinationsoptimierung verwenden](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88% Wir verweisen auf E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Optimales Messplanproblem

Lassen Sie mich das Problem des Papiers "Erstellen eines optimalen Messplans für die Pyramide" verwenden.

Ich möchte mehrere Scanner an den Kandidatenpunkten installieren und sie mit einem Laser scannen, um Daten zu erfassen. Minimieren Sie die Anzahl der Scanner und maximieren Sie die Menge der erfassten Daten.

Denkweise

In diesem Artikel wird es in zwei Schritten gelöst, aber es ist problematisch. Erhöhen wir also die Installationskosten um das Zehnfache und lösen Sie es in einem Schritt.

Löse mit Python

Erstellen Sie zunächst zufällige Daten.

python

import numpy as np
from pulp import *
from ortoolpy import addvar, addvars

n = 4 #Kandidatenpunkte
np.random.seed(3)
a = np.random.rand(n, n).round(3)
a #Datenmenge
>>>
array([[ 0.551,  0.708,  0.291,  0.511],
       [ 0.893,  0.896,  0.126,  0.207],
       [ 0.051,  0.441,  0.03 ,  0.457],
       [ 0.649,  0.278,  0.676,  0.591]])

python

d = np.random.randint(0, 2, (n, n))
d[np.diag_indices(n)] = 1
d #Messbar
>>>
array([[1, 1, 1, 0],
       [1, 1, 0, 1],
       [1, 0, 1, 1],
       [0, 1, 0, 1]])

Formulieren und lösen.

python

m = LpProblem()
x = addvars(n, cat=LpBinary) #Variable
m += lpSum(x)*10 - lpDot(a.sum(1), x) #Zielfunktion
for i in range(n):
    m += lpDot(d[:,i], x) >= 1 #Zwang
m.solve()
[int(value(v)) for v in x]
>>>
[1, 0, 0, 1]

das ist alles