[PYTHON] Plan de mesure optimal - Extrait du numéro d'octobre du magazine OR

Qu'est-ce que c'est

OR Society Numéro d'octobre de la revue [Dossier spécial "** Students 'OR **"](http://www.orsj.or.jp/ De e-library / elcorsj.html # 6110), je voudrais aborder le problème d'optimisation de manière appropriée et le résoudre avec Python. Comme préparation, vous avez besoin de pandas, de pulpe, d'oolpy. Pour la construction de l'environnement, [Utiliser l'optimisation des combinaisons](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88% Veuillez vous référer à E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Problème de plan de mesure optimal

Permettez-moi d'utiliser le problème de l'article "Créer un plan de mesure optimal pour la pyramide".

Je souhaite installer plusieurs scanners aux points candidats et les scanner avec un laser pour acquérir des données. Minimisez le nombre de scanners et maximisez la quantité de données acquises.

Façon de penser

Dans l'article, il est résolu en deux étapes, mais c'est gênant, alors augmentons le coût d'installation de 10 fois et résolvons-le en une seule étape.

Résoudre avec Python

Tout d'abord, créez des données aléatoires.

python

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

n = 4 #Points candidats
np.random.seed(3)
a = np.random.rand(n, n).round(3)
a #quantité de données
>>>
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 #Mesurable
>>>
array([[1, 1, 1, 0],
       [1, 1, 0, 1],
       [1, 0, 1, 1],
       [0, 1, 0, 1]])

Formulez et résolvez.

python

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

c'est tout