[PYTHON] Mit OR-Tools erlernte Optimierung [Linearer Plan: Lassen Sie uns Öl raffinieren]

Dieser Blog ist was

Wir lernen die mathematische Optimierung mit von Google entwickelten OR-Tools. Der größte Teil des Inhalts basiert auf diesem Buch. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Klicken Sie hier, um eine Liste der Codes nach Autor anzuzeigen Der in diesem Blog beschriebene Code entspricht fast dem Originalcode des Autors und ist nur teilweise auf Japanisch korrigiert.

Mathematische Genauigkeit und theoretischer Kommentar haben eine niedrige Priorität. Bitte verzeih mir.

Diesmal: Linear Plan-Ölraffinerie-

Modellieren Sie ein lineares Design. Ich mag keine lineare Planung, es tut mir wirklich leid. Diesmal: "Lassen Sie uns den Gewinn maximieren, indem wir die gewünschten Erdölprodukte auf gute Weise aus dem Rohstoff Rohöl herstellen. Ist ein Beispiel. Wenn es sich um die Menge des verwendeten Rohöls handelt, scheinen kontinuierliche Werte zulässig zu sein, daher denke ich, dass dies vielleicht ein Beispiel ist.

Szeneneinstellung

Sie sind ein Grundschüler, der an Ihren Sommerferien-Hausaufgaben arbeitet und kostenlos lernt. Als Sie für eine sozialwissenschaftliche Tour in die Raffinerie gingen, dachten Sie: "Machen Sie effizient Erdölprodukte und machen Sie Gewinn ...", also wählte ich dies als Gegenstand freier Forschung.

Jedes Erdölprodukt, das Sie herstellen möchten, hat einen Oktanwert, und jedes als Rohstoff verwendete Rohöl hat auch einen Oktanwert. (Es scheint, dass der Oktanwert wahrscheinlich kein Klopfen verursacht. Ich wusste nicht, wonach ich suchen sollte, also denke ich, dass es dem Alkoholgehalt entspricht.) Rohöle mit unterschiedlichen Oktanwerten müssen gut gemischt werden, um Erdölprodukte mit einem bestimmten Oktanwert herzustellen. Rohöl kostet je nach Typ unterschiedlich pro Barrel, und Erdölprodukte haben je nach Typ unterschiedliche Verkaufspreise pro Barrel. Bitte beachten Sie die Tabelle, da es schwierig wird, die Bedeutung in Sätzen zu verstehen.

Eine wichtige Annahme hierbei ist, dass der Oktanwert eines Rohölgemisches durch eine lineare Funktion bestimmt wird. Mit anderen Worten, wenn Rohöl mit einem Oktanwert von 80 und Rohöl mit einem Oktanwert von 90 in einem Verhältnis von 4: 6 gemischt werden,

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

Dann wird ein Produkt mit einem Oktanwert von 86 geboren. Ich habe das Gefühl, dass ich es wegen des Problems der Salzlösungskonzentration getan habe.

Da Sie nun Ihre Gewinne maximieren möchten, müssen Sie maximieren (Verkäufe aus den von Ihnen hergestellten Erdölprodukten) - (Kosten aus dem von Ihnen verwendeten Rohöl).

Formulierung

Das Problem ist diesmal, dass Sie wissen möchten, dass "○○ den Gewinn maximiert". Was ist ○○? "Die Menge jedes verwendeten Rohöls" ist etwas unzureichend. Dies liegt daran, dass Sie, wenn Sie sich auf ein bestimmtes Erdölprodukt X konzentrieren, wissen müssen, wie viel Rohöl zur Herstellung von X verwendet wurde. Deshalb,

G_{ij}:Rohölmenge, die ich für Produkt j verwendet habe

Bereiten Sie eine Variable mit dem Namen vor. Daher ist die Determinante als Matrix *** (Rohöltyp) x (Produkttyp) *** definiert. Ich bin froh, wenn ich den Inhalt dieser Tabelle kenne.

Infolgedessen sind die Gesamtmenge des verwendeten Rohöls R und die Gesamtmenge des produzierten Produkts F.

R_i = \sum_{j} G_{ij}:Gesamtmenge des verwendeten Rohöls. Summe in Zeilenrichtung\\
F_j = \sum_{i} G_{ij}:Gesamtproduktion des Produkts j. Summe in Spaltenrichtung

Ist festgelegt. Jetzt können Sie die Zielfunktion definieren. Angenommen, der Stückpreis von Rohöl i beträgt $ c_i $ und der Verkaufspreis von Produkt j beträgt $ p_j $

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

Ist die Zielfunktion. In Bezug auf die Einschränkungsbedingung ist die Einschränkung für den Bereich, den $ R_i und F_j $ annehmen können, problematisch, daher werde ich sie weglassen. Nun, Sie können nicht mehr verwenden, als Sie besitzen, oder Sie müssen es im Bereich der Nachfrage machen.

Das Wichtigste ist diesmal der Oktanwert. Rohöl muss gemischt werden, damit das Produkt einen bestimmten Oktanwert hat, nicht nur das Mischen. Angenommen, der Oktanwert von Rohöl i ist $ O_i $ und der Oktanwert von Produkt j ist $ o_j $ (bereits verwirrend)

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

Muss halten. Wenn dies nicht erfüllt ist, können Sie das gewünschte Produkt nicht herstellen. Die Formulierung wurde vorerst abgeschlossen. Lassen Sie es uns implementieren.

Implementierung

Dieses Mal werde ich nur den Code einführen, der die erforderlichen Funktionen beschreibt. Autor GitHub verfügt über den gesamten erforderlichen Code. Verwenden Sie test_gas_blend.py, um es auszuführen, und my_or_tools.py, um die Verwendung von OR-Tools zu vereinfachen.

gas_blend.Ein Teil von py

from my_or_tools import SolVal,ObjVal,newSolver

def solve_gas(C, D):                                            #Rohölliste,Nehmen Sie eine Liste von Produkten als Argument
  s = newSolver('Gas blending problem')                         #Löser definieren
  nR,nF = len(C),len(D)                                         #Anzahl Rohöl,Holen Sie sich die Anzahl der Produkte
  Roc,Rmax,Rcost = 0,1,2                                        #Rohöloktanwert,Eigener Betrag,Ausgabenpaltennummer
  Foc,Fmin,Fmax,Fprice = 0,1,2,3                                #Produktoktanwert,Untergrenze der Nachfrage,Nachfrageobergrenze,Verkaufspreisspaltennummer
  G = [[s.NumVar(0.0,10000,'') 
        for j in range(nF)] for i in range(nR)]                 #Bereiten Sie eine Matrix von Variablen Gij vor
  R = [s.NumVar(0,C[i][Rmax],'') for i in range(nR)]            #Bereiten Sie die Variable R vor, die die Summe der Zeilenrichtungen von Gij ist
  F = [s.NumVar(D[j][Fmin],D[j][Fmax],'') for j in range(nF)]   #Bereiten Sie die Variable F vor, die die Summe der Spaltenrichtung von Gij ist
  for i in range(nR):                                   
    s.Add(R[i] == sum(G[i][j] for j in range(nF)))              #Gleichung, die R erfüllen sollte
  for j in range(nF):
    s.Add(F[j] == sum(G[i][j] for i in range(nR)))              #Gleichung, die F erfüllen sollte
  for j in range(nF):                                     
    s.Add(F[j]*D[j][Foc] ==                                     #Oktanwertbeschränkungen
          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))             #Kosten für die Verwendung von Rohöl
  Price = s.Sum(F[j]*D[j][Fprice] for j in range(nF))           #Verkäufe aus der Produktgenerierung
  s.Maximize(Price - Cost)                                      #Gewinne maximieren
  rc = s.Solve()
  return rc,ObjVal(s),SolVal(G)

Die Verwendung von "my_or_tools.py" erleichtert das Definieren von Solvern.

Ergebnis

Der Wert unten rechts ist der Vorteil dieser optimalen Lösung.

Takashi konnte während der Sommerferien erfolgreich eine kostenlose Studie einreichen. Ich bin glücklich. Das Schreiben von Formeln und Tabellen in Qiita ist schwierig. Vielleicht bin ich einfach nicht daran gewöhnt. Es gibt fast keine Erklärung für den Algorithmus, da er für meine eigene Überprüfung bestimmt ist und anscheinend nur von OR-Tools formuliert und implementiert wird. Es tut mir leid.