極端な問題を解決する理由
実際には、最適化手法が使用されているソリューションに対して問題が頻繁に発生します。 新年の贈り物など、複数の選択肢がある日常生活では、特定の購入品質で最小コストの問題を直感的に解決します。
残念なことに、常に直感に頼ることはできません。 あなたが営利会社の従業員であり、広告を担当しているとします。 1か月あたりの広告費用は10,000通貨単位（CU）を超えてはなりません。 1分間のラジオ広告にはCU 5がかかり、テレビ広告には90 CUがかかります 同社は、ラジオ広告をテレビ広告の3倍の頻度で使用する予定です。 実践によると、1分間のテレビ広告は、1分間のラジオ広告の30倍の売り上げをもたらします。
あなたの仕事は、会社の売り上げが最大になる前述の2種類の広告の間で資金の分配を決定することです。 最初に変数を選択します。つまり、テレビ（x1）とラジオ（x2）での分単位の月間ボリュームです。 これで、次のシステムを構成することは難しくありません。
30x1 + x2 –広告からの売り上げを増やします。
90x1 + 5x2 <= 10,000-資金制限;
x2 = 3x1-ラジオの時間と広告の本文の比率。
今しばらくの間、広告について忘れて、前述を要約しようとします。 添付タスクなど、多くのタスクが存在する場合がありますが、それらには次の共通機能があります。 必須とは、変数に線形に依存するターゲット関数の存在です。この例では30x1 + x2であり、着信変数の見つかった値に対して最大値が1つ必要です。 この場合、入力変数の非負性の条件は自動的に満たされます。 次に、再び、条件の存在に応じた量の線形等式と不等式が続きます。 そこで、線形計画問題の1つのグループを作成しました。
いわゆる輸送問題を例として使用して、線形計画問題の別の大きなグループを検討します。 あなたが輸送サービスを提供する営利会社の従業員であるとします。 異なる3つの都市に倉庫を持つ商品のサプライヤがあり、これらの倉庫の同種製品の量はそれぞれa1、a2、a3に等しくなります。 他の3つの都市には、それぞれb1、b2、b3の量のサプライヤから商品を持ち込む必要がある消費者がいます。 表によると、サプライヤから消費者への1から9個の商品の送料も知られています。
x1 ... xnが輸送される貨物の量である場合、目標の機能は輸送の総コストになります。
F（x）= c1 * x1 + c2 * x2 + c3 * x3 + c4 * x4 + c5 * x5 + c6 * x6 + c7 * x7 + c8 * x8 + c9 * x9。
記録する条件。 不等式の形で：
x1 + x2 + x3 <= 20-サプライヤが持っているものより多くを取ることはできません
x4 + x5 + x6 <= 45
x7 + x8 + x9 <= 30
記録する条件。 平等の形で：
x1 + x4 + x7 = b1–必要な量と持参量
x2 + x5 + x8 = b2
x3 + x6 + x9 = b3
ここでは、変数xの非負性の条件がさらに必要です。これらは意味が負ではなく、最小F（x）が求められるためです。 これらの不等式は与えられていません。
これで、線形計画法の基本的なタスクの目標関数と条件を作成する方法がわかりました。 しかし、これらの問題を解決するための幾何学的、シンプレックス、人為的な基礎方法に関する特別な文献を読んだとき、広告とロジスティクスの両方を放棄しました。 しかし、Pythonでシンプルでわかりやすいソリューションを見つけることができます。
典型的な線形計画問題を解決するためのPythonライブラリの選択
Pythonの線形プログラミングについては、3つの特殊なライブラリを知っています。 各ライブラリでこれらの問題の両方に対する解決策を検討してください。 インターフェイスと最適化の結果に加えて、パフォーマンスも評価します。 速度の質的な違いのみが必要なので、これには最も単純なリストを使用して、各プログラムの起動結果を平均化します。
パルプライブラリによる最適化[1]。
「広告について」タスクを解決するためのプログラムのリスト
from pulp import * import time start = time.time() x1 = pulp.LpVariable("x1", lowBound=0) x2 = pulp.LpVariable("x2", lowBound=0) problem = pulp.LpProblem('0',pulp.LpMaximize) problem += 30*x1 +x2, " " problem += 90*x1+ 5*x2 <= 10000, "1" problem +=x2 ==3*x1, "2" problem.solve() print (":") for variable in problem.variables(): print (variable.name, "=", variable.varValue) print (":") print (value(problem.objective)) stop = time.time() print (" :") print(stop - start)
このプログラムの財政状況では、最大の広告利益のために私たちがすでに知っている比率は30 * x1 + x2であり、コストを制限する条件であり、比較のために「1」とマークされています。 ラジオを使用している時間と、フォックステンジで「2」としてマークされている広告本体との関係を忘れていません。 他の演算子の目的は明らかであり、詳細は[1]に記載されています。
パルプを使用して最適化問題を解いた結果。
結果：
x1 = 95.238095
x2 = 285.71429
利益：
3142.85714
時間：
0.10001182556152344
その結果、その使用から期待される利益が最大になる広告時間の値を取得しました。
cvxoptライブラリを使用した最適化[2]。
「広告について」という問題を解決するプログラムのリスト。
from cvxopt.modeling import variable, op import time start = time.time() x = variable(2, 'x') z=-(30*x[0] +1*x[1])# mass1 = (90*x[0] + 5*x[1] <= 10000) #"1" mass2 = (3*x[0] -x[1] == 0) # "2" x_non_negative = (x >= 0) #"3" problem =op(z,[mass1,mass2,x_non_negative]) problem.solve(solver='glpk') problem.status print (":") print(abs(problem.objective.value()[0])) print (":") print(x.value) stop = time.time() print (" :") print(stop - start)
プログラムの構造は前の構造と似ていますが、2つの大きな違いがあります。 まず、cvxoptライブラリは、最大ではなく、ターゲット関数の最小値を見つけるように構成されています。 したがって、目的関数は負のマイナス記号-（30 * x [0] + 1 * x [1]）で取得されます。 結果の負の値は絶対値で導出されます。 第二に、非負変数の非負性に関する制限が導入されました。 これが結果に影響を与えたかどうか、私たちは今見る。
cvxoptを使用して最適化問題を解いた結果。
利益：
3142.857142857143
結果 ：
[9.52e + 01]
[2.86e + 02]
時間：
0.041656494140625
プログラムの実行時間を除き、パルプライブラリと比較して大きな変更はありません。
scipyライブラリを使用した最適化。 最適化 [3]。
「広告について」という問題を解決するプログラムのリスト。
from scipy.optimize import linprog import time start = time.time() c = [-30,-1] # A_ub = [[90,5]] #'1' b_ub = [10000]#'1' A_eq = [[3,-1]] #'2' b_eq = [0] #'2' print (linprog(c, A_ub, b_ub, A_eq, b_eq)) stop = time.time() print (" :") print(stop - start)
リストを一目見れば、データ入力に対する根本的に異なるアプローチを扱っていることを理解するのに十分です。 リストに示されている図は、データ編成の原理を明確にするのに役立ちますが、比較して説明します。 リストc = [-30、-1]は、linprog（）が最小値を探しているため、反対の符号を持つターゲット関数の係数を含みます。 マトリックスA_ubには、条件の変数の係数が不等式の形で含まれています。 このタスクでは、これは90x1 + 5x2 <= 10000です。 inequality-1000の右側の値は、b_ubリストに配置されます。 マトリックスA_eqには、条件の変数の係数が等式の形で含まれています。 このタスクでは、 3x1-x2 = 0で、右側のゼロはb_eqリストに配置されます。
scipyを使用して最適化問題を解いた結果。 最適化する。
楽しい：-3142.8571428571431
メッセージ：「最適化は正常に終了しました。」
nit：2
スラック：配列（[0.]]
ステータス：0
成功：真
x：配列（[95.23809524、285.71428571]）
時間：
0.03020191192626953
計算結果はここでより詳細に表示されますが、結果自体は以前のライブラリと同じです。
「On Advertising」タスクのソリューションの結果によると、scipyライブラリの使用に関して中間的な結論を導き出すことができます。 最適化により、パフォーマンスが向上し、ソースデータの形式がより合理化されます。 ただし、輸送の問題を解決した結果がなければ、最終的な結論を出すには時期尚早です。
輸送の問題の解決策を示しますが、解決策の主要な段階はすでに詳細に説明されているため、詳細な説明はありません。
パルプライブラリによる最適化。
トランスポートの問題を解決するためのプログラムのリスト。
from pulp import * import time start = time.time() x1 = pulp.LpVariable("x1", lowBound=0) x2 = pulp.LpVariable("x2", lowBound=0) x3 = pulp.LpVariable("x3", lowBound=0) x4 = pulp.LpVariable("x4", lowBound=0) x5 = pulp.LpVariable("x5", lowBound=0) x6 = pulp.LpVariable("x6", lowBound=0) x7 = pulp.LpVariable("x7", lowBound=0) x8 = pulp.LpVariable("x8", lowBound=0) x9 = pulp.LpVariable("x9", lowBound=0) problem = pulp.LpProblem('0',pulp.LpMaximize) problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, " " problem +=x1 + x2 +x3<= 74,"1" problem +=x4 + x5 +x6 <= 40, "2" problem +=x7 + x8+ x9 <= 36, "3" problem +=x1+ x4+ x7 == 20, "4" problem +=x2+x5+ x8 == 45, "5" problem +=x3 + x6+x9 == 30, "6" problem.solve() print (":") for variable in problem.variables(): print (variable.name, "=", variable.varValue) print (" :") print (abs(value(problem.objective))) stop = time.time() print (" :") print(stop - start)
輸送の問題を解決するには、配送コストを最小限に抑える必要があるため、目標関数にはマイナス記号が付けられ、絶対値で表示されます。
パルプを使用して輸送問題を解決した結果。
結果：
x1 = 0.0
x2 = 45.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 30.0
x7 = 20.0
x8 = 0.0
x9 = 0.0
送料：
215.0
時間：
0.19006609916687012
cvxoptライブラリを使用した最適化。
トランスポートの問題を解決するためのプログラムのリスト。
from cvxopt.modeling import variable, op import time start = time.time() x = variable(9, 'x') z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* x[8]) mass1 = (x[0] + x[1] +x[2] <= 74) mass2 = (x[3] + x[4] +x[5] <= 40) mass3 = (x[6] + x[7] + x[8] <= 36) mass4 = (x[0] + x[3] + x[6] == 20) mass5 = (x[1] +x[4] + x[7] == 45) mass6 = (x[2] + x[5] + x[8] == 30) x_non_negative = (x >= 0) problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative]) problem.solve(solver='glpk') problem.status print(":") print(x.value) print(" :") print(problem.objective.value()[0]) stop = time.time() print (" :") print(stop - start)
cvxoptを使用してトランスポート問題を解決した結果。
結果：
[0.00e + 00]
[4.50e + 01]
[0.00e + 00]
[0.00e + 00]
[0.00e + 00]
[3.00e + 01]
[2.00e + 01]
[0.00e + 00]
[0.00e + 00]
送料：
215.0
時間：
0.03001546859741211
scipyライブラリを使用した最適化。 最適化する。
トランスポートの問題を解決するためのプログラムのリスト。
from scipy.optimize import linprog import time start = time.time() c = [7, 3, 6,4,8,2,1,5,9] A_ub = [[1,1,1,0,0,0,0,0,0], [0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,1,1,1]] b_ub = [74,40,36] A_eq = [[1,0,0,1,0,0,1,0,0], [0,1,0,0,1,0,0,1,0], [0,0,1,0,0,1,0,0,1]] b_eq = [20,45,30] print(linprog(c, A_ub, b_ub, A_eq, b_eq)) stop = time.time() print (" :") print(stop - start)
scipy最適化を使用して輸送問題を解決した結果。
楽しい：215.0
メッセージ：「最適化は正常に終了しました。」
nit：9
slack：配列（[29.、10.、16.]）
ステータス：0
成功：真
x：配列（[0.、45.、0.、0.、0.、30.、20.、0.、0.]）
時間：
0.009982585906982422
同様の目的の3つのライブラリの助けを借りて、2つの典型的な線形計画問題の解決策を分析しても、scipyライブラリの選択に疑問は生じません。 データ入力のコンパクトさと速度のリーダーとして最適化する。
scipyライブラリを使用するための新機能。 線形計画問題を解くときに最適化する
ソース行列から目標関数のリストを取得し、不等式A_ubおよび等式A_eqの行列をプログラムで入力すると、データ入力の作業が簡素化され、元の行列の次元が増加します。 これにより、実際の最適化問題を解決できます。 完全なコードであると主張しない単純なデモでこれをどのように行うことができるかを見てみましょう。
ネタバレ見出し
import numpy as np from scipy.optimize import linprog b_ub = [74,40,36] b_eq = [20,45,30] A=np.array([[7, 3,6],[4,8,2],[1,5,9]]) m, n = A.shape c=list(np.reshape(A,n*m))# A c. A_ub= np.zeros([m,m*n]) for i in np.arange(0,m,1):# –. for j in np.arange(0,n*m,1): if i*n<=j<=n+i*n-1: A_ub [i,j]=1 A_eq= np.zeros([m,m*n]) for i in np.arange(0,m,1):# –. k=0 for j in np.arange(0,n*m,1): if j==k*n+i: A_eq [i,j]=1 k=k+1 print(linprog(c, A_ub, b_ub, A_eq, b_eq))
これで、マトリックスA自体とb_ub不等式およびb_ub-等式の右側のリストのみが導入されます。
プログラムの結果は予測可能です。
楽しい：215.0
メッセージ：「最適化は正常に終了しました。」
nit：9
slack：配列（[29.、10.、16.]）
ステータス：0
成功：真
x：配列（[0.、45.、0.、0.、0.、30.、20.、0.、0.]）
結論は非公開です
線形計画問題を解決するときは、記事で説明されている手法に従ってscipy.optimizeライブラリを使用し、プログラムで条件マトリックスを入力することをお勧めします。 この場合、最適化の問題を解決する方法に関する特別な知識は必要ありません。
一般的な結論
最近、同様の問題を解決するさまざまなPythonライブラリが登場しました。 特定のライブラリを使用する決定は、多くの場合主観的です。 したがって、タスクの領域についてそれらの比較分析を行うことをお勧めします。