[PYTHON] Optimisation apprise avec OR-Tools Part0 [Introduction]

Ce blog est ce que

Nous allons apprendre l'optimisation mathématique en utilisant les outils OR développés par Google. La plupart du contenu est basé sur ce livre. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Cliquez ici pour une liste de codes par auteur Le code décrit dans ce blog est presque le même que celui d'origine de l'auteur, et il n'est que partiellement corrigé en japonais.

La rigueur mathématique et le commentaire théorique sont peu prioritaires. S'il vous plaît, pardonnez-moi.

Cette fois: Introduit

Basé sur un exemple simple ・ Quel est le problème d'optimisation? ・ Comment utilisez-vous OR-Tools? je vais étudier

Réglage de la scène

Vous êtes en charge des amphibiens à l'animalerie. Il semble qu'ils gardent ** Hikigaeru, Sanshou et triton dans le même réservoir. Je veux en garder le plus possible, mais la nourriture est limitée. Au fait, ** la nourriture est de l'eau, du grillon, de la mouche ** (pourquoi est-ce un exemple?) Selon le type, le nombre d'aliments que vous mangez dans une journée est différent, ** Comment pouvez-vous en garder le plus au total? **

Quantité de nourriture à manger par jour pour chaque amphibien

Formulation

Tout d'abord, définissez la variable de décision. Cette fois, nous demanderons "le nombre de grenouilles, de sardines et de tritons qui maximise le total".

\begin{align}
&x_0 :Grenouille Hiki\\
&x_1 :Sanshou\\
&x_2 :Triton\\
\end{align}\\
Cependant, 0\leq x_i \leq 1000

La fonction que je veux maximiser cette fois est

x_0 + x_1 + x_2

toit. Ce n'est pas grave si vous gardez 1000 animaux chacun! Cependant, il existe des restrictions sur la nourriture. J'ai 1500 mizus, je mange 2 grenouilles par jour, 1 sardine et 1 triton.

2x_0 + x_1 + x_2 \leq 1500

De même pour les grillons et les mouches.

x_0 + 3x_1 + 2x_2 \leq 3000\\
x_0 + 2x_1 + 3x_2 \leq 5000

Maintenant, la mise en œuvre

Il prend la forme de la définition d'un ou de plusieurs solveurs et de l'ajout de variables, de fonctions objectifs et de contraintes (Add). Lors de la définition, le titre du solveur (cette fois «coexistence des amphibiens») et le solveur à utiliser (cette fois GLOP) sont spécifiés comme arguments. GLOP est un solveur de planification linéaire.

coexistence.py

from ortools.linear_solver import pywraplp

def solve_coexistence():
    t = 'Coexistence des amphibiens'
    s = pywraplp.Solver(t, pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
    
    x = [s.NumVar(0, 1000, 'x[%i]' % i) for i in range(3)]  #　0 <= x <=1000. Variable déterminante
    pop = s.NumVar(0, 3000, 'pop')                          # 0 <= pop <=3000. Variable objectif
    
    s.Add(2*x[0] + x[1] + x[2] <= 1500)       #Contrainte Mizu
    s.Add(x[0] + 3*x[1] + 2*x[2] <= 3000)     #Contrainte de cricket
    s.Add(x[0] + 2*x[1] + 3*x[2] <= 4000)     #Contrainte de mouches
    s.Add(pop == x[0] + x[1] + x[2])          #Fonction objective
    s.Maximize(pop)                           #Spécifiez que vous souhaitez maximiser la pop
    s.Solve()                                 #résoudre


    ##Renvoie la valeur de la fonction objectif et la valeur du déterminant
    return pop.SolutionValue(), [e.SolutionValue() for e in x]

Cliquez ici pour le code à exécuter

test_coexistence.py

from __future__ import print_function
from coexistence import solve_coexistence

pop, x = solve_coexistence()  #Appelez la fonction définie et stockez le résultat
T = [['type', 'nombre']]          #Nom de la colonne lors de l'affichage des résultats
for i in range(3):
    T.append([['Grenouille Hiki','Sanshou','Triton'][i], x[i]])   #Ajouter un nom et un numéro à la ligne i
T.append(['total', pop])

for e in T:
    print(e[0], e[1])

Résultat d'exécution

Oui, c'est la solution optimale. Il y a trop de tritons et tu peux rire Je ne sais pas si les tritons mangent beaucoup de mizu et de grillons (quelques-uns) et mangent beaucoup de mouches (beaucoup), alors j'en ai eu beaucoup. En réalité, j'aimerais mettre beaucoup de Sanshoou parce qu'il se vend mieux, ou je ne veux pas vendre de triton parce qu'il ne se vend pas bien, mais cette fois, il est introduit, donc par ici.

Je viens de réaliser que la prochaine fois, je parlerai plus en détail de la façon d'utiliser OR-Tools. Alors qu'avez-vous fait cette fois?