凸最適化-線形計画法

方法論

線形最適化とも呼ばれる線形計画法は、関係が本質的に線形である数学的問題を解決するために使用される手法です。線形計画法の基本的な性質は、最大化または最小化することですobjective function いくつかの対象と constraints。目的関数は、問題の数学モデルから得られる線形関数です。制約は、モデルに課せられる条件であり、線形でもあります。

与えられた質問から、目的関数を見つけます。
制約を見つけます。
グラフに制約を描画します。
すべての制約の交点によって形成される実行可能領域を見つけます。
実行可能領域の頂点を見つけます。
これらの頂点で目的関数の値を見つけます。
（質問に応じて）目的関数を最大化または最小化する頂点が答えです。

例

Step 1 − $ 5x + 3y $を最大化する

$ x + y \ leq 2 $、

$ 3x + y \ leq 3 $、

$ x \ geq 0 \：および\：y \ geq 0 $

Solution −

最初のステップは、グラフ上で実行可能領域を見つけることです。

グラフから明らかなように、実行可能領域の頂点は次のとおりです。

$ \ left（0、0 \ right）\ left（0、2 \ right）\ left（1、0 \ right）\ left（\ frac {1} {2}、\ frac {3} {2} \ right ）$

$ f \ left（x、y \ right）= 5x + 3y $とします

これらの値を目的関数に入れると、次のようになります。

$ f \ left（0、0 \ right）$ = 0

$ f \ left（0、2 \ right）$ = 6

$ f \ left（1、0 \ right）$ = 5

$ f \ left（\ frac {1} {2}、\ frac {3} {2} \ right）$ = 7

したがって、関数は$ \ left（\ frac {1} {2}、\ frac {3} {2} \ right）$で最大になります。

Step 2−時計会社は、デジタル時計と機械式時計を製造しています。長期的な予測では、毎日少なくとも100個のデジタル時計と80個の機械式時計の需要が見込まれています。生産能力に限りがあるため、1日200本のデジタル時計と170本の機械式時計しか製造できません。配送契約を満たすために、毎日合計200個以上の時計が発送されます。

販売された各デジタル時計が$ \ $ 2 $の損失をもたらすが、各機械式時計が$ \ $ 5 $の利益を生み出す場合、純利益を最大化するために、各タイプを1日にいくつ作成する必要がありますか？

Solution −

$ x $を製造されたデジタル時計の数とします

$ y $は生産された機械式時計の数です

質問によると、毎日少なくとも100個のデジタル時計を製造し、最大200個のデジタル時計を製造することができます。

$ \ Rightarrow 100 \ leq \：x \ leq 200 $

同様に、少なくとも80個の機械式時計を毎日製造し、最大170個の機械式時計を製造することができます。

$ \ Rightarrow 80 \ leq \：y \ leq 170 $

毎日少なくとも200個の時計が生産されるためです。

$ \ Rightarrow x + y \ leq 200 $

販売された各デジタル時計は$ \ $ 2 $の損失をもたらしますが、各機械式時計は$ \ $ 5 $の利益を生み出します。

総利益は次のように計算できます