Clever Geek Handbook

Scipyライブラリを使用したPythonでの線形プログラミング

私の最初の出版物では、すばらしいscipyライブラリを使用して、線形プログラミングの問題をすばやく簡単に解決する方法についてお話したいと思います。 pythonでの同様のタスクにはpulpもありますが、 scipyの初心者には構文がより理解しやすいです。



なぜ実際には線形計画法が必要なのでしょうか？ 原則として、関数f（x）を最小化する問題（または-f（x）の逆最大化問題）を解決します。



ここでは、理論的な計算は行いませんが（ ここで確認できます ）、特定の例を検討します。



だから挑戦。



毎週一定量の製品を生産する8つの工場があります。 収益を最大化するように13店舗で製品を配布する必要がありますが、不採算店舗を閉鎖することは許可されています。



私たちは知っています：



  1. 工場の生産性（週あたりの製品kg単位の供給場）、それらの座標（X、Y） 



    fact x y supply 0 F_01 59.250276 59.871183 389 1 F_02 84.739320 14.179336 409 2 F_03 42.397937 42.474530 124 3 F_04 19.539202 13.714643 70 4 F_05 41.280669 37.860993 386 5 F_06 37.159066 41.353602 196 6 F_07 96.890453 64.420010 394 7 F_08 86.267499 81.662811 365


  2. 店舗の生産性（1週間あたりの製品kg単位の需要フィールド）、その座標（X、Y） 



      shop x y demand 0 S_01 13.490869 73.269974 200 1 S_02 85.435435 66.637250 20 2 S_03 28.578297 8.997380 320 3 S_04 31.324145 91.839907 360 4 S_05 40.338575 15.487028 360 5 S_06 41.642451 42.121572 120 6 S_07 53.983692 20.950457 360 7 S_08 75.761895 87.067552 60 8 S_09 81.836739 36.799647 80 9 S_10 54.260517 25.920108 100 10 S_11 67.918105 68.108601 340 11 S_12 92.200710 10.898110 360 12 S_13 19.966539 39.046271 60


  3. お菓子の製造コスト：200ルーブル/ kg; チョコレートの販売による収入：800ルーブル/ kg; お菓子の配達費用：20ルーブル/ kg / km; 週ごとの店舗費用：10,000ルーブル。



次に、最初の論理的な制限を課します。



  1. 総供給<=総需要、つまり、工場は販売できる量より多くの製品をストアに出荷できません。


次の表記法を紹介します。



  1. costkg =製造コスト。
  2. revkg =生産による収益（kgあたりの販売価格）;
  3. devkg =物流コスト。
  4. costweek =店舗のメンテナンス費用。


データを処理するために、供給のすべての組み合わせ（ファクトリー-ストア）を取得するために、ストアとのクロス結合ファクトリーを作成します。



この種のテーブルを取得します。 



  fact supply shop demand distance cost_kg rev_kg del_kg cost_week 99 F_08 365 S_09 80 44.863164 200 800 20 10000 100 F_08 365 S_10 100 55.742703 200 800 20 10000 101 F_08 365 S_11 340 13.554211 200 800 20 10000 102 F_08 365 S_12 360 70.764701 200 800 20 10000 103 F_08 365 S_13 60 42.616540 200 800 20 10000


次に、最適化する機能を見てみましょう（これまでのところ、ストアのコンテンツを考慮せずに）。



利益=ボリューム∗（revkg−costkg−devkg∗距離）



ここで、利益は特定の店舗への出荷からのルーブルの利益であり、量はこの店舗への工場出荷の量です。



合計で104の利益の条件があります（工場と店舗の組み合わせが104あるため）。



関数の最終形式は次のようになります。



利益=合計（prof_1_1 ... profit_n）-13 * 10000



13 * 10000は店舗の維持費用です。



次に、最も線形のプログラミングに進みます。 scipy.optimizeモジュールの説明はここにあります 。 一般的な形式： 



 res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds), options={"disp": True})


ここに：



  1. cはボリュームの係数（つまり、コスト）です。 私たちの国では、彼らは否定的です、なぜなら 最大化問題を解きます（最小化-f（x））。
  2. A_ub-これらは私たちによって課せられた条件のボリュームの値です。b_ub-制限の値。
  3. ボリュームのx0_boundsおよびx1_boundsの下限と上限


制限は次のとおりです。



  1. テーブルの各行のボリュームは供給を超えません。
  2. 工場のラインごとの量が供給量を超えていない。
  3. 行ごとのストアのボリューム量は需要を超えません。
  4. volumeは、特定の工場のゼロから最大（供給）の値を取ります。


以下のコード： 



 ## ff - table with factories and shops coefs = [] for f in ff.iterrows(): coefs.append((f[1]['rev_kg'] - f[1]['cost_kg'] - f[1]['del_kg']*f[1]['distance'])*(-1)) A = [] b = [] for f in ff['fact'].values: A.append((ff['fact'] == f)*1) b.append(ff[ff['fact'] ==f]['supply'].max()) for f in ff['shop'].values: A.append((ff['shop'] == f)*1) b.append(ff[ff['shop'] ==f]['demand'].max()) x0_bounds = [] x1_bounds = [] for f in ff.iterrows(): x0_bounds.append(0) x1_bounds.append(f[1]['demand']) x0_bounds = tuple(x0_bounds) x1_bounds = tuple(x1_bounds) A.append(coefs) b.append(-10000*13) res = linprog(coefs, A_ub=A, b_ub=b, bounds=list(zip(x0_bounds, x1_bounds)), options={"disp": True, 'maxiter' : 50000} )


出力：



最適化は正常に終了しました。

現在の関数値：-948302.914122

繰り返し：20



純利益を計算し、各工場がどれだけ供給し、どの店舗を閉鎖する価値があるかを確認します。 



 ff['supply_best'] = res.x ff['stay_opened'] = (ff['supply_best'] > 0)*1 ff['profit'] = (ff['supply_best']*(ff['rev_kg']- ff['cost_kg'] - ff['distance'] * ff['del_kg']))*ff['stay_opened'] net_profit = ff['profit'].sum() - ff[ff['stay_opened']==1]['shop'].nunique()*10000 grouped = ff.groupby(['fact', 'shop'])['supply_best'].sum().reset_index() f = {'supply_best': 'sum', 'supply': 'max'} ff.groupby('fact')['supply_best', 'supply'].agg(f)


読書利益-828302.9141220199ルーブル



各工場の備品： 



  fact shop supply_best 0 F_01 S_01 166.0 17 F_02 S_05 360.0 24 F_02 S_12 49.0 31 F_03 S_06 120.0 38 F_03 S_13 4.0 50 F_04 S_12 70.0 58 F_05 S_07 346.0 61 F_05 S_10 40.0 73 F_06 S_09 80.0 74 F_06 S_10 60.0 77 F_06 S_13 56.0 78 F_07 S_01 34.0 79 F_07 S_02 20.0 88 F_07 S_11 340.0 94 F_08 S_04 305.0 98 F_08 S_08 60.0


店舗への配達： 



 supply_best demand shop S_01 200.0 200 S_02 20.0 20 S_03 0.0 320 S_04 305.0 360 S_05 360.0 360 S_06 120.0 120 S_07 346.0 360 S_08 60.0 60 S_09 80.0 80 S_10 100.0 100 S_11 340.0 340 S_12 119.0 360 S_13 60.0 60


S_03はクローズする価値があり、需要の約30％がS_12に供給されることがわかります。



このように、簡単な操作の助けを借りて、基本的かつ非常に単純化されたものを解決しましたが、実際にはサプライチェーンの最適化という問題にしばしば遭遇しました。



ご質問やご意見がありましたら、お気軽にお答えします。


More articles:


All Articles