Pythonで直接および双対線形計画問題を解決する

はじめに

線形計画問題を解く方法は、経済学ではなく、数学とコンピューター工学に関係していることに注意してください。 この場合、エコノミストは適切なソフトウェアとの対話に最も快適な条件を提供する必要があります。 また、そのような条件は、そのような問題を解決するために必要な一連のライブラリーを武器として動的に開発するインタラクティブな開発環境によってのみ提供できます。 ソフトウェア開発環境の1つは確かにPythonです。

問題の声明

出版物[1,2]では、直接最適化問題の解決策が線形計画法によって考慮され、scipyソルバーの合理的な選択が提案されました。 最適化する。

ただし、各線形計画法の問題は、いわゆる識別（二重）問題に対応することが知られています[3]。 直接的なタスクと比較して、その中で、行は列に変わり、不等式は最大ではなく符号を変え、最小が求められます（またはその逆で、最小、最大ではなく）。 二重対二重の問題は、元のタスクそのものです。

二重問題の解決策は、リソース使用の分析にとって非常に重要です。 この出版物では、元の問題と双対問題の目的関数の最適値が一致することが証明されます（つまり、元の問題の最大値が双対の最小値と一致する）。

材料と労働のコストの最適値は、目的関数への貢献度によって評価されます。 その結果、市場価格と一致しない原材料と労働の「客観的に決定された推定値」が得られます。

最適な生産プログラムの直接的な問題を解決する

このリソースの大部分のユーザーの数学的準備のレベルが高いことを考えると、上限と下限の制限と平等のための追加変数の導入を伴う均衡方程式を与えません。 したがって、ソリューションで使用される変数の表記をすぐに示します。
Nは、製造された製品のタイプの数です。
m–使用される原材料の種類の数。
b_ubは、次元mの利用可能なリソースのベクトルです。
A_ubは次元m×Nの行列であり、その各要素は、タイプjの製品単位の生産のためのタイプiのリソース消費です。
Cは、各タイプの製品の単位の生産からの利益ベクトルです。
x-最大の利益をもたらす各タイプの製造製品の必要量（最適な生産計画）。

目標関数
maxF（x）= c×x

制限事項
A×x≤b

変数の数値：
N = 5; mは4です。 b_ub = [700,250,600,400]; A_ub = [[1,2,3,2,4]、[5,4,3,2,1]、[3,4,2,5,3]、[4,2,5,3,1] ]; c = [25、35,25,40,30]。

タスク
1.最大の利益を得るためにxを見つける
2.段落1を実行するときに使用されるリソースを見つける
3.段落1を実行するときに残りのリソース（ある場合）を見つけます

scipyライブラリを使用したソリューションの機能。 最適化する
最大値（デフォルトでは最小値が決定されます）を決定するには、目的関数の係数を負符号c = [-25、-35、-25、-40、-30]で記述し、利益の前の負符号を無視する必要があります。

結果の出力で使用される表記法：
xは、目的関数の最小（最大）を提供する変数の値の配列です。
slack-追加変数の値。 各変数は不等式制約に対応しています。 変数のゼロ値は、対応する制限がアクティブであることを意味します。
成功 -関数が最適なソリューションを見つけることができた場合はTrue。
ステータス -決定ステータス：
0-最適なソリューションの検索は正常に完了しました。
1-反復回数の制限に達しました。
2-問題には解決策がありません。
3-目的関数は制限されません。
nitは、実行された反復の数です。


問題解決の結果
nit 3
ステータス0
メッセージ最適化は正常に終了しました。
本当の成功
x [0. 0. 18.18181818 22.72727273 150.]
A_ub * x [700.0、250.0、600.0、309.0909090909090912]
b_ub-A_ub * x [0. 0. 0. 90.90909091]
楽しい-5863.63636364
スラック[0. 0. 0. 90.90909091]

結論

1. 製品の種類に最適な計画が見つかりました[0.0 0. 0 18.182 22.727 150. 0]
2. リソースの実際の使用が見つかりました[700.0、250.0、600.0、309.091]
3. 未使用の4番目のタイプのリソースの残りが見つかりました[0. 0 0.0 0.0 90.909]
4. 同じ結果がスラック変数に出力される必要があるため、請求項3による計算の必要はありません。

最適な生産プログラムの二重の問題の解決策

直接問題の4番目のタイプのリソースは完全には使用されていません。 この場合、企業のこのリソースの価値は、生産量を制限するリソースと比較して低くなり、企業は利益の増加を可能にするリソースの取得に対してより高い価格を支払う用意ができています。

製造された製品の販売からの利益に関連してこのリソースの価値を決定する「シャドウ」価格として、目的の変数xの新しい割り当てを導入します。

さらに、比較分析のために、以前に受け入れられた表記を部分的に保持しますが、新しいコンテンツを使用します。

cは利用可能なリソースのベクトルです。
b_ub-各タイプの製品単位の生産からの利益ベクトル。
A_ub_T –転置行列A_ub。

目標関数
minF（x）= c×x

制限事項
A_ub_T×x≥b_ub

変数の数値と関係：
c = [700,250,600,400]; A_ub_T転置（A_ub）; b_ub = [25、35,25,40,30]。

チャレンジ：
各タイプのリソースのプロデューサーに値を示すxを見つけます。

scipyライブラリを使用したソリューションの機能。 最適化する
上記の制限を下からの制限に置き換えるには、制限の両方の部分にAマイナス1を掛ける必要があります-A_ub_T×x≥b_ub ...これを行うには、次の形式で初期データを記述します。b_ub = [-25、-35、-25、-40、-30]; A_ub_T =-scipy.transpose（A_ub）。


問題解決の結果
nit 7
メッセージ最適化は正常に終了しました。
楽しい5863.63636364
x [2.27272727 1.81818182 6.36363636 0.]
スラック[5.45454545 2.27272727 0. 0. 0.]
ステータス0
本当の成功

結論

3番目のタイプのリソースはメーカーにとって最大の価値があるため、最初にこのタイプのリソースを購入してから、1番目と2番目のタイプを購入する必要があります。 リソースの4番目のタイプは、製造業者にとってゼロの値を持ち、最後に購入されます。

直接問題と二重問題の比較

1. デュアルタスクは、製品計画の可能性を拡張しますが、それはスパイシーです。 最適化は、直接の反復回数の2倍で解決されます。
2. スラック変数は、制約のアクティビティに関する情報を不等式の形式で表示します。これは、たとえば、残留原材料の分析に使用できます。
3. 直接の問題は最大化のタスクであり、二重問題は最小化のタスクであり、逆もまた同様です。
4. 直接問題の目的関数の係数は、二重問題の制約です。
5. 直接問題の制約は、双対の目的関数の係数になります。
6. 制限の不平等の兆候は逆転します。
7. 等式系の行列が転置されます。

参照資料

1. Pythonを使用して追加の条件で閉じたトランスポートの問題を解決します。
2. Pythonを使用して線形計画問題を解決します。
3. 線形計画問題の双対性。