Convex-optimization-linear-programming
凸最適化-線形計画法
方法論
線形最適化とも呼ばれる線形計画法は、関係が本質的に線形である数学的問題を解決するために使用される手法です。 線形計画法の基本的な性質は、*制約*を条件として、*目的関数*を最大化または最小化することです。 目的関数は、問題の数学モデルから取得される線形関数です。 制約は、モデルに課せられる条件であり、線形でもあります。
- 与えられた質問から、目的関数を見つけます。
- 制約を見つけます。
- グラフに制約を描きます。
- すべての制約の交差によって形成される実行可能領域を見つけます。
- 実行可能領域の頂点を見つけます。
- これらの頂点で目的関数の値を見つけます。
- (質問に応じて)目的関数を最大化または最小化する頂点が答えです。
例
- ステップ1 *-$ 5x + 3y $を最大化する
$ x + y \ leq 2 $、
$ 3x + y \ leq 3 $、
$ x \ geq 0 \:および\:y \ geq 0 $
ソリューション-
最初のステップは、グラフ上の実行可能領域を見つけることです。
グラフから明らかなように、実行可能領域の頂点は
$ \ 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)$で最大化します
- ステップ2 *-時計会社がデジタル時計と機械式時計を製造しています。 長期予測では、毎日少なくとも100台のデジタル時計と80台の機械式時計の需要が予想されています。 生産能力には限界があるため、毎日200個を超えるデジタル時計と170個を超える機械式時計を製造することはできません。 出荷契約を満たすために、毎日少なくとも合計200個の時計が出荷されます。
各デジタル時計の販売で$ \ $ 2 $の損失が発生し、各機械式時計で$ \ $ 5 $の利益が生じる場合、純利益を最大化するために各タイプを毎日何個作る必要がありますか?
ソリューション-
生成されるデジタル時計の数を$ x $とする
$ y $は、生産される機械式時計の数です
質問によれば、少なくとも100台のデジタル時計を毎日作成し、最大200台のデジタル時計を作成できます。
$ \ Rightarrow 100 \ leq \:x \ leq 200 $
同様に、少なくとも80個の機械式時計を毎日作成し、最大170個の機械式時計を作成できます。
$ \ Rightarrow 80 \ leq \:y \ leq 170 $
毎日少なくとも200個の時計が製造されるためです。
$ \右矢印x + y \ leq 200 $
デジタル時計を販売するたびに$ \ $ 2 $の損失が生じるが、各機械式時計は$ \ $ 5 $の利益を生み出すため、
総利益は次のように計算できます。
$利益= -2x + 5年$
そして、我々は利益を最大化する必要があります、したがって、質問は次のように定式化できます-
$ -2x + 5y $を最大化する
$ 100 \:\ leq x \:\ leq 200 $
$ 80 \:\ leq y \:\ leq 170 $
$ x + y \:\ leq 200 $
上記の方程式をグラフにプロットすると、
実行可能領域の頂点は
$ \ left(100、170 \ right)\ left(200、170 \ right)\ left(200、180 \ right)\ left(120、80 \ right)および\ left(100、100 \ right)$
目的関数の最大値は$ \ left(100、170 \ right)$で取得されます。したがって、純利益を最大化するには、100単位のデジタル時計と170単位の機械式時計を生産する必要があります。