Optimisation apprise avec OR-Tools [plan linéaire: raffinons l'huile]

Ce blog est ce que

Nous apprendrons l'optimisation mathématique à l'aide des 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 des 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 les commentaires théoriques sont peu prioritaires. S'il vous plaît, pardonnez-moi.

Cette fois: raffinerie de pétrole plan linéaire-

Modélisez une conception linéaire. Je n'aime pas la planification linéaire, je suis vraiment désolé. Cette fois, «maximisons les profits en fabriquant les produits pétroliers souhaités à partir de la matière première, le pétrole brut de la bonne manière. Est un exemple. S'il s'agit de la quantité de pétrole brut utilisée, il semble que des valeurs continues soient autorisées, alors je pense que c'est peut-être un exemple.

Réglage de la scène

Vous êtes un élève du primaire travaillant sur vos devoirs de vacances d'été, des études gratuites. Lorsque vous êtes allé à la raffinerie pour une tournée d'études sociales, vous vous êtes dit: "Produisez efficacement des produits pétroliers et faites des bénéfices ...", alors j'ai choisi cela comme sujet de recherche gratuite.

Chaque produit pétrolier que vous souhaitez fabriquer a une valeur d'octane, et chaque pétrole brut utilisé comme matière première a également une valeur d'octane. (Il semble que l'indice d'octane ne provoque probablement pas de cognement. Je ne savais pas quoi chercher, donc je pense que c'est comme la teneur en alcool.) Les huiles brutes avec des indices d'octane différents doivent être bien mélangées pour fabriquer des produits pétroliers avec un indice d'octane spécifique. Le pétrole brut coûte différemment le baril selon le type, et les produits pétroliers ont des prix de vente par baril différents selon le type. Veuillez consulter le tableau car il devient difficile de comprendre la signification des phrases.

Une hypothèse importante ici est que l'indice d'octane d'un mélange de pétrole brut est déterminé par une fonction linéaire. En d'autres termes, lorsque du pétrole brut avec un indice d'octane de 80 et du pétrole brut avec un indice d'octane de 90 sont mélangés dans un rapport de 4: 6,

80\times\frac{4}{10}+90\times\frac{6}{10}=86

Ensuite, un produit avec un indice d'octane de 86 est né. J'ai l'impression de l'avoir fait à cause du problème de concentration de la solution saline.

Maintenant, parce que vous voulez maximiser vos profits, vous devez maximiser (les ventes des produits pétroliers que vous fabriquez) - (les coûts du pétrole brut que vous utilisez).

Formulation

Le problème cette fois est que vous voulez savoir "○○ qui maximise les profits". Qu'est-ce que ○○? «La quantité de chaque pétrole brut utilisé» est un peu insuffisante. En effet, lorsque vous vous concentrez sur un certain produit pétrolier X, vous devez connaître la répartition du pétrole brut utilisé et la quantité de X. Donc,

G_{ij}:Quantité de pétrole brut i utilisée pour le produit j

Préparez une variable appelée. Par conséquent, le déterminant est défini comme une matrice *** (type de pétrole brut) x (type de produit) ***. Je suis content si je connais le contenu de ce tableau.

En conséquence, la quantité totale de pétrole brut utilisé R et la quantité totale de produit fabriqué F

R_i = \sum_{j} G_{ij}:Quantité totale de pétrole brut que j'ai utilisé. Somme dans le sens de la ligne\\
F_j = \sum_{i} G_{ij}:Production totale du produit j. Somme dans le sens de la colonne

Est établi. Vous pouvez maintenant définir la fonction objectif. En supposant que le prix unitaire du pétrole brut i est $ c_i $ et le prix de vente du produit j est $ p_j $

max \sum_{j}F_jp_j-\sum_{i}R_ic_i

Est la fonction objective. Enfin, concernant la condition de contrainte, la contrainte sur la plage que $ R_i et F_j $ peuvent prendre est gênante, je vais donc l'omettre. Eh bien, vous ne pouvez pas utiliser plus que ce que vous possédez, ou vous devez le faire dans la fourchette de la demande.

L'important cette fois est la valeur d'octane. Le pétrole brut doit être mélangé de manière à ce que le produit ait un indice d'octane spécifique, pas seulement un mélange. En supposant que la valeur d'octane du pétrole brut i est $ O_i $ et la valeur d'octane du produit j est $ o_j $ (déjà déroutant)

\sum_{i}O_iG_{ij}=F_jo_j\\

Doit tenir. Si cela n'est pas respecté, vous ne pourrez pas fabriquer le produit souhaité. Pour le moment, la formulation est terminée. Mettons-le en œuvre.

la mise en oeuvre

Cette fois, je présenterai uniquement le code qui décrit les fonctions nécessaires. Auteur GitHub a tout le code nécessaire. Utilisez test_gas_blend.py pour l'exécuter et my_or_tools.py pour rendre OR-Tools plus facile à utiliser.

gas_blend.Partie de py

from my_or_tools import SolVal,ObjVal,newSolver

def solve_gas(C, D):                                            #Liste du pétrole brut,Prenez une liste de produits comme argument
  s = newSolver('Gas blending problem')                         #Définir le solveur
  nR,nF = len(C),len(D)                                         #Nombre de pétrole brut,Obtenez le nombre de produits
  Roc,Rmax,Rcost = 0,1,2                                        #Indice d'octane du pétrole brut,Montant possédé,Numéro de colonne de dépenses
  Foc,Fmin,Fmax,Fprice = 0,1,2,3                                #Indice d'octane du produit,Limite inférieure de la demande,Plafond de la demande,Numéro de colonne du prix de vente
  G = [[s.NumVar(0.0,10000,'') 
        for j in range(nF)] for i in range(nR)]                 #Préparer une matrice de variables Gij
  R = [s.NumVar(0,C[i][Rmax],'') for i in range(nR)]            #Préparez la variable R qui est la somme des directions de ligne de Gij
  F = [s.NumVar(D[j][Fmin],D[j][Fmax],'') for j in range(nF)]   #Préparez la variable F qui est la somme de la direction de colonne de Gij
  for i in range(nR):                                   
    s.Add(R[i] == sum(G[i][j] for j in range(nF)))              #Équation que R devrait satisfaire
  for j in range(nF):
    s.Add(F[j] == sum(G[i][j] for i in range(nR)))              #Équation que F devrait satisfaire
  for j in range(nF):                                     
    s.Add(F[j]*D[j][Foc] ==                                     #Contraintes de valeur d'octane
          s.Sum([G[i][j]*C[i][Roc] for i in range(nR)]))
  Cost = s.Sum(R[i]*C[i][Rcost] for i in range(nR))             #Coûts d'utilisation du pétrole brut
  Price = s.Sum(F[j]*D[j][Fprice] for j in range(nF))           #Ventes issues de la génération de produits
  s.Maximize(Price - Cost)                                      #Maximisez vos profits
  rc = s.Solve()
  return rc,ObjVal(s),SolVal(G)

L'utilisation de my_or_tools.py facilite la définition des solveurs.

résultat

La valeur en bas à droite est l'avantage de cette solution optimale.

Takashi a réussi à soumettre une étude gratuite pendant les vacances d'été. Je suis heureux. Écrire des formules et des tableaux en Qiita est difficile. Peut-être que je n'y suis pas habitué. Il n'y a presque aucune explication de l'algorithme parce que c'est pour mon propre examen, et il semble que ce ne sera que la formulation et la mise en œuvre par OR-Tools, je suis désolé.