Optimisation apprise avec OR-Tools [Planification linéaire: modèle en plusieurs étapes]

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: Planification linéaire-modèle multi-étapes-

Incorporez «quand» dans vos décisions. En prenant un entrepôt comme exemple, la quantité de commande pour le mois prochain changera en fonction du nombre de stocks dont vous disposez à la fin de ce mois. De même, la quantité de commande pour le mois suivant changera en fonction de la quantité de commande pour le mois suivant. De cette manière, considérez la décision optimale dans une situation où la décision à un stade affecte la décision aux étapes suivantes.

Réglage de la scène

Takashi dirige une savonnerie. Les performances de l'usine affectant l'argent de poche de Takashi, j'ai décidé de rechercher une méthode de fonctionnement efficace.

Le savon est fabriqué en récurant et en mélangeant diverses huiles. Les huiles ont des parfums variés tels que l'abricot et l'avocat, et chaque huile contient divers acides gras (laurin, linole, acide oléique, etc.). Voici un tableau des acides gras $ A_j $ contenus dans l'huile $ i $. image.png Aussi, compte tenu des propriétés du savon (pouvoir nettoyant, moussant, sécheresse de la peau, etc.), bien mélanger pour que la teneur finale en acides gras se situe dans une certaine plage. Ici, on suppose qu'il se situe dans la plage du tableau ci-dessous. image.png Nous considérons ici une décision qui s'étend sur plusieurs mois. Chaque huile peut être achetée pour une utilisation immédiate ou pour le mois suivant. Le tableau ci-dessous montre le prix (dollar / t) de chaque pétrole pour chaque mois. image.png Vous pouvez stocker jusqu'à 1000 tonnes d'huile pour une utilisation ultérieure. Cependant, il y a un coût de stockage mensuel de 5 $ la tonne. De plus, l'usine de Takashi doit répondre à la demande mensuelle de 5 000 tonnes de savon. À l'heure actuelle, l'usine de Takashi dispose des huiles répertoriées dans le tableau ci-dessous. image.png

C'est finalement le sujet principal. ** Quelle quantité d'huile doit être fondue et mélangée pendant quel mois pour minimiser les coûts? </ font> ** Ah, c'était long.

Formulation: variable déterminante

Cela semble être un déterminant de la quantité de chaque huile mélangée chaque mois, mais cela ne suffit pas. Lorsque vous utilisez de l'huile, vous pouvez utiliser ce que vous avez acheté ou ce que vous aviez en stock, nous les distinguons donc. Vous devez également savoir combien vous pouvez acheter pour le stock, étant donné la limite totale de 1000 tonnes.

Par conséquent, nous avons besoin d'au moins trois déterminants pour l'ensemble de pétrole $ O $ et l'ensemble de mois $ M $.

x_{i,j} \geq 0 \quad \forall i \in O, \forall j \in M \achat quad\\
y_{i,j} \geq 0 \quad \forall i \in O, \forall j \in M \quad mixte\\
z_{i,j} \geq 0 \quad \forall i \in O, \forall j \in M \stock quad\\

$ x_ {i, j} $ est la quantité d'huile $ i $ achetée dans le mois $ j $, $ y_ {i, j} $ est l'huile $ i $ mélangée dans le mois $ j $ pour fabriquer du savon Qu'est-ce que $ z_ {i, j} $ est la quantité de pétrole $ i $ que vous avez au début de $ j $ par mois. Représente. De plus, bien que cela ne soit pas strictement obligatoire, nous fournissons également une variable pour le nombre de tonnes de savon fabriquées chaque mois. Cela facilite la description des contraintes. Production mensuelle de $ j $ de savon

t_j \quad \forall j \in M

ça ira.

Formulation: contrainte

Vous devez spécifier comment l'inventaire de chaque huile fluctue chaque mois. Donc

z_{i,j} + x_{i,j} - y_{i,j}= z_{i,j+1} \quad \forall i \in O, \forall j \en M \ {le mois dernier}

Préparez la formule. Cela signifie que le stock au début du mois plus l'achat pour le mois en cours moins l'utilisation pour le mois en cours sera le stock du mois suivant.

Puisqu'il y a des limites inférieures et supérieures pour la capacité de l'entrepôt chaque mois,

C_{min} \leq \sum_{i} z_{i,j} \leq C_{max} \quad  \forall j \in M

Vient ensuite la contrainte de mélange. Il y avait une réglementation sur la gamme d'acides gras dans le produit fini. Nous utiliserons la production mensuelle $ t_j = \ sum_ {i} y_ {i, j} \ quad \ forall j \ in M $. Il existe un ensemble d'acides gras $ A $, et le rapport de la plage spécifiée $ [l_k, u_k] $ pour chaque acide gras $ k \ dans A $ à l'acide gras $ k $ contenu dans l'huile $ i $ $ p_ {i, k} $ Penser à. Ensuite, il existe deux formules pour la plage de teneur en acides gras, la limite inférieure et la limite supérieure.

\sum_i y_{i,j} p_{i,k} \geq l_k t_j \quad \forall k \in A, \forall j \in M \\
\sum_i y_{i,j} p_{i,k} \leq u_k t_j \quad \forall k \in A, \forall j \in M

Enfin, il faut répondre à la demande mensuelle (même si cette fois elle est constante à 5 000 t). Compte tenu de la demande mensuelle de $ j $ $ D_j $,

t_j \geq D_j \quad \forall j \in M

Formulation: fonction objective

Le but de cette période était de minimiser les coûts. Autrement dit, pour minimiser la somme des coûts d'achat et de stockage du pétrole. Le prix unitaire d'achat varie en fonction du pétrole et du mois, mais le coût de stockage par tonne est fixe. Par conséquent, la fonction objectif est

\sum_i \sum_j x_{i,j} P_{i,j} + \sum_i \sum_j z_{i,j}p

$ P_ {i, j} $ est le prix unitaire mensuel du pétrole $ i $, et $ p $ est le coût de stockage par tonne (5 $ cette fois).

la mise en oeuvre

Voici le code pour résoudre cet exemple. my_or_tools.py et tableutils.py Veuillez consulter Author GitHub pour le contenu.

blend_multi.py


from my_or_tools import SolVal, ObjVal, newSolver

def solve_model(Part,Target,Cost,Inventory,D,SC,SL):
    #Part:Tableau des huiles et acides gras,Target:Régulation de la teneur en acides gras,Cost:Coût d'achat du pétrole,Inventory:Stock initial,
    #D:Demande de savon,SC:Coûts de stockage du pétrole,SL:Gamme d'huiles que vous pouvez avoir en stock

  s = newSolver('Multi-period soap blending problem')   #Déclarer le solveur
  Oils= range(len(Part))    #Nombre de types d'huile
  Periods, Acids = range(len(Cost[0])), range(len(Part[0]))     #Nombre de périodes,Types d'acides gras
  Buy = [[s.NumVar(0,D,'') for _ in Periods] for _ in Oils]     #Variable déterminante x. Combien d'huile je dois acheter le mois j
  Blnd = [[s.NumVar(0,D,'') for _ in Periods] for _ in Oils]    #Variable déterminante y. Combien d'huiles je dois utiliser pour le mois j
  Hold = [[s.NumVar(0,D,'') for _ in Periods] for _ in Oils]    #Variable déterminante z. Combien d'huiles j'ai en stock par mois j
  Prod = [s.NumVar(0,D,'') for _ in Periods]    #Variables auxiliaires. Savon produit le mois j
  CostP= [s.NumVar(0,D*1000,'') for _ in Periods]   #Variables auxiliaires. Coût d'achat du mois j
  CostS= [s.NumVar(0,D*1000,'') for _ in Periods]   #Variables auxiliaires. Coût de stockage pour le mois j
  Acid = [[s.NumVar(0,D*D,'') for _ in Periods] for _ in Acids] #Variables auxiliaires. Quantité d'acide gras k produit au mois j
  for i in Oils:                             
    s.Add(Hold[i][0] == Inventory[i][0])    #Contraintes. Le stock au moment de la décision est donné
  for j in Periods:                                      
    s.Add(Prod[j] == sum(Blnd[i][j] for i in Oils)) #Contraintes. La production du mois j est la somme de la quantité d'huile utilisée
    s.Add(Prod[j] >= D) #Contraintes. La production du mois j doit dépasser la demande de ce mois
    if j < Periods[-1]: #Hors le mois dernier
      for i in Oils:
        s.Add(Hold[i][j]+Buy[i][j]-Blnd[i][j] == Hold[i][j+1])  #Contraintes.(Stock au début du mois)+(Montant des achats)-(montant à utiliser)=(Stock au début du mois prochain)
    s.Add(sum(Hold[i][j] for i in Oils) >= SL[0])   #Contraintes. Limite inférieure d'huile pouvant être stockée
    s.Add(sum(Hold[i][j] for i in Oils) <= SL[1])   #Contraintes. Limite supérieure d'huile pouvant être stockée
    for k in Acids: 
      s.Add(Acid[k][j]==sum(Blnd[i][j]*Part[i][k] for i in Oils))   #Contraintes. La quantité d'acide gras k produite au mois j est la somme des produits de la quantité d'huile utilisée et de la teneur en acide gras k de cette huile.
      s.Add(Acid[k][j] >= Target[0][k] * Prod[j])   #Contraintes. Limite inférieure de production d'acide gras k
      s.Add(Acid[k][j] <= Target[1][k] * Prod[j])   #Contraintes. Limite supérieure de production d'acide gras k
    s.Add(CostP[j] == sum(Buy[i][j] * Cost[i][j] for i in Oils))    #Contraintes. Le coût d'achat pour le mois j est la somme du produit du montant d'achat et du prix.
    s.Add(CostS[j] == sum(Hold[i][j] * SC for i in Oils))           #Contraintes. Le coût de stockage pour le mois j est la somme du produit des coûts d'inventaire et de stockage.
  Cost_product = s.Sum(CostP[j] for j in Periods)   #Fonction objective. Coût d'achat total
  Cost_storage = s.Sum(CostS[j] for j in Periods)   #Fonction objective. Coût total de stockage
  s.Minimize(Cost_product+Cost_storage) #Minimisez la somme des coûts d'achat totaux et des coûts totaux de stockage
  rc = s.Solve()
  B,L,H,A = SolVal(Buy),SolVal(Blnd),SolVal(Hold),SolVal(Acid)
  CP,CS,P = SolVal(CostP),SolVal(CostS),SolVal(Prod)
  return rc,ObjVal(s),B,L,H,P,A,CP,CS

my_blend_multi.py


from blend_multi import solve_model

Content = [#Huile et acides gras contenus
    [36,20,33,6,4,0,1],
    [0,68,13,0,0,8,11],
    [0,6,0,66,16,5,7],
    [0,32,0,0,0,14,54],
    [0,0,49,3,39,7,2],
    [45,0,40,0,15,0,0,0],
    [0,0,0,0,0,28,72],
    [36,55,0,0,0,0,9],
    [12,48,34,0,4,2,0]
]

Target = [#Régulation de la teneur en acides gras
    [13.3,23.2,17.8,3.7,4.6,8.8,23.6],
    [14.6,25.7,19.7,4.1,5.0,9.7,26.1]
]

Price = [#Prix mensuel du pétrole
    [118,128,182,182,192],
    [161,152,149,156,174],
    [129,191,118,198,147],
    [103,110,167,191,108],
    [102,133,179,119,140],
    [127,100,110,135,163],
    [171,166,191,159,164],
    [171,131,200,113,191],
    [147,123,135,156,116]
]

Inventory = [#Stock de détention initial
    [15],[52],[193],[152],[70],[141],[43],[25],[89]
]

def main():
    import sys
    import tableutils
    m=len(Content)
    n=len(Content[0])
    k=len(Price[0])
    if len(sys.argv)<=1:
        print('Usage is main [content|target|cost|inventory|run] [seed]')
        return
    """ elif len(sys.argv)>2:
        random.seed(int(sys.argv[2])) """
    C = Content
    T = Target
    K = Price
    I = Inventory
    if sys.argv[1]=='content':  #Tableau de sortie des huiles et des acides gras contenus
        for j in range(m):
            C[j].insert(0,'O'+str(j))
        C.insert(0,['']+['A'+str(i) for i in range(n)])
        tableutils.printmat(C,False,1)
    elif sys.argv[1]=='target': #Sortie de la régulation de la teneur en acides gras
        T.insert(0,['']+['A'+str(i) for i in range(n)])
        T[1].insert(0,'Min')
        T[2].insert(0,'Max') 
        tableutils.printmat(T,True,1)
    elif sys.argv[1]=='cost':   #Prix mensuel du pétrole en sortie
        for j in range(m):
            K[j].insert(0,'O'+str(j))
        K.insert(0,['']+['Month '+str(i) for i in range(k)])
        tableutils.printmat(K)
    elif sys.argv[1]=='inventory':  #Sortie de l'inventaire détenu au moment de la décision
        for j in range(m):
            I[j].insert(0,'O'+str(j))
        I.insert(0,['Oil','Held'])
        tableutils.printmat(I)
    elif sys.argv[1]=='run':    #Exécutez le solveur
        Demand=5000 #Demande mensuelle de savon
        Limits=[0,1000]   #Limites inférieures et supérieures que vous pouvez avoir en stock
        Cost=5
        rc,Value,B,L,H,P,A,CP,CS=solve_model(C,T,K,I,Demand,Cost,Limits)
        if len(B):
            A.append([0 for l in range(len(A[0]))])
            for j in range(len(A)-1):
                for l in range(len(A[0])):
                    A[j][l] = A[j][l]/P[l]
                    A[-1][l] += A[j][l] 
            for j in range(m):
                B[j].insert(0,'O'+str(j))
                L[j].insert(0,'O'+str(j))
                H[j].insert(0,'O'+str(j))
            for l in range(n):
                A[l].insert(0,'A'+str(l))
            A[-1].insert(0,'Total')
            B.insert(0,['Buy qty']+['Month '+str(i) for i in range(k)])
            L.insert(0,['Blend qty']+['Month '+str(i) for i in range(k)])
            H.insert(0,['Hold qty']+['Month '+str(i) for i in range(k)])
            A.insert(0,['Acid %']+['Month '+str(i) for i in range(k)])
            P=[P]
            P[0].insert(0,'Prod qty')
            CP=[CP]
            CP[0].insert(0,'P. Cost')
            CS=[CS]
            CS[0].insert(0,'S. Cost')

            tableutils.printmat(B,True,1)
            tableutils.printmat(L,True,1)
            tableutils.printmat(H,True,1)
            tableutils.printmat(P,True,1)
            tableutils.printmat(CP,True,2)
            tableutils.printmat(CS,True,2)
            tableutils.printmat(A,True,1)

main()

résultat

L'exécution du code ci-dessus donne les résultats suivants: image.png

image.png

image.png

image.png

image.png

Takashi a pu faire fonctionner l'usine de savon d'une bonne manière.

développement

Voici quelques-uns des développements possibles de cet exemple. ・ La demande mensuelle fluctue -La priorité est donnée à la maximisation des profits plutôt qu'à la satisfaction de la demande. Dans ce cas, le prix de vente du produit est requis. ・ Gérez les niveaux d'inventaire par pétrole, pas par total ・ Il peut y avoir une incertitude quant à la quantité d'acides gras contenus dans certaines huiles. Etc.

Résumé

Je suis vraiment fatigué cette fois

Recommended Posts

Optimisation apprise avec OR-Tools [Planification linéaire: modèle en plusieurs étapes]
Optimisation apprise avec OR-Tools [Planification linéaire: gestion de projet]
Optimisation apprise avec OR-Tools [plan linéaire: raffinons l'huile]
Optimisation apprise avec OR-Tools Part0 [Introduction]
Régression avec un modèle linéaire
Programmation linéaire avec PuLP
Résolution d'exercices de modèle d'optimisation mathématique avec les outils OR de Google (3) Problèmes d'optimisation de la production
Résolvez des exercices de modèle d'optimisation mathématique avec les outils OR de Google
[Python] Programmation orientée objet apprise avec Pokemon
[Problème d'optimisation mathématique] Méthode de programmation linéaire utilisant PuLP
Optimisation de la planification de la production à l'aide de la programmation linéaire (Python + PuLP)
Prédire l'été chaud avec un modèle de régression linéaire
Optimisation de portefeuille avec Python (modèle de distribution moyenne de Markovitz)
Découvrez Wasserstein GAN avec le modèle Keras et l'optimisation TensorFlow