167数学 · 線形計画法

線形計画の頂点と極値

線形計画の頂点と極値

線形計画の頂点と極値. 線形計画の頂点と極値. CMPLX/Deg を使用。F=px+qy+r の p+qi、ax+by≤c の4組 (a+bi,c)、最後に r の計10入力です。≥ は全符号を反転。3制約なら3本目を繰り返します。法線と (p,q) は非零。領域が非空で頂点を持つと事前に分かっている必要があり、空領域・平行帯・全平面は対象外です。通常の記憶は消去します。

  • 242 バイト
  • CMPLX モード
01

例題と解説

例題 1

オリジナル問題. 与えられた値: x,y∈ℝ; x≥0; y≥0; 2x+3y≤18; F=4x+5y+7. 求める量: 最小値 F; 最大値 F. 指定順にすべての量を求めてください。

答え
min F=7; max F=43
標準的な解き方(電卓なし)
  1. 数学モデルを立て、値を代入します。
  2. x≥0,y≥0⇒−x≤0,−y≤0; 2x+3y≤18
  3. V={(0,0),(9,0),(0,6)}
  4. F(0,0)=7; F(9,0)=43; F(0,6)=37
  5. 7≤F≤43; F(0,0)=7; F(9,0)=43
  6. 上の結果を組み合わせて答えを得ます。
電卓で解いてみる

例題 2

オリジナル問題. 与えられた値: x,y∈ℝ; x≥0; y≥0; 4x+3y≤120; 2x+5y≤100; F=30x+28y−40. 求める量: 最小値 F; 最大値 F; max F>900?. 指定順にすべての量を求めてください。

答え
min F=−40; max F=6460/7≈922.8571429>900
標準的な解き方(電卓なし)
  1. 数学モデルを立て、値を代入します。
  2. x≥0,y≥0⇒−x≤0,−y≤0; 4x+3y≤120; 2x+5y≤100
  3. 4x+3y=120; 2x+5y=100⇒(x,y)=(150/7,80/7)
  4. V={(0,0),(30,0),(150/7,80/7),(0,20)}
  5. F(V)={−40,860,6460/7,520}
  6. 6460/7≈922.8571429; 6460/7>900
  7. 上の結果を組み合わせて答えを得ます。
電卓で解いてみる

例題 3

オリジナル問題. 与えられた値: x,y∈ℝ; x≤5; x+y≥4; x−y≤2; F=2x−3y+10. 求める量: 最小値 F; 最大値 F. 指定順にすべての量を求めてください。

答え
inf F=−∞; max F=13; (x,y)=(3,1)
標準的な解き方(電卓なし)
  1. 数学モデルを立て、値を代入します。
  2. x≤5; x+y≥4⇒−x−y≤−4; x−y≤2
  3. y≥max(4−x,x−2)
  4. x≤3⇒F=2x−3y+10≤5x−2≤13
  5. 3≤x≤5⇒F≤16−x≤13; F(3,1)=13
  6. x=3,y≥1⇒F=16−3y→−∞
  7. 上の結果を組み合わせて答えを得ます。
電卓で解いてみる
02

使いどころ

線形計画の頂点と極値. 線形計画の頂点と極値. CMPLX/Deg を使用。F=px+qy+r の p+qi、ax+by≤c の4組 (a+bi,c)、最後に r の計10入力です。≥ は全符号を反転。3制約なら3本目を繰り返します。法線と (p,q) は非零。領域が非空で頂点を持つと事前に分かっている必要があり、空領域・平行帯・全平面は対象外です。通常の記憶は消去します。

入力順

  • X=p+qi
  • (a₁+b₁i,c₁),…,(a₄+b₄i,c₄)
  • X=r
  • 必須値は 0 も毎回入力します。空欄の EXE は記憶を保持し、ゼロではありません。変数と Ans は上書きされます。

出力順

  • min F
  • max F
  • 値を記録し EXE で進みます。
  • プログラムは終了です。AC で戻り、EXE で再実行します。

条件と制限

  • 3≤N≤4; (aⱼ,bⱼ)≠(0,0); (p,q)≠(0,0)
  • F=px+qy+r; ax+by≤c; x,y∈ℝ
  • CMPLX/Deg を使用。F=px+qy+r の p+qi、ax+by≤c の4組 (a+bi,c)、最後に r の計10入力です。≥ は全符号を反転。3制約なら3本目を繰り返します。法線と (p,q) は非零。領域が非空で頂点を持つと事前に分かっている必要があり、空領域・平行帯・全平面は対象外です。通常の記憶は消去します。
  • 最小値、最大値の順です。−1E99/+1E99 は有限の下限/上限がない印で、達成値ではありません。変数は連続実数で、整数最適化、全頂点、最適辺、パラメータ範囲は記述で調べます。極端な尺度や桁落ちは誤差を生み、実行可能性を証明する機能はありません。
  • 必須値は 0 も毎回入力します。空欄の EXE は記憶を保持し、ゼロではありません。変数と Ans は上書きされます。
  • 有限精度により大数の微小差や 0、1 に極めて近い確率は不正確になります。エラー記号は答えではありません。

ログインするとプログラム全体を表示できます

利用権を確認中…

プログラムコードと付録は同時に表示されます。

利用権を確認中…

ログインするとプログラム全体を表示できます

利用権を確認中…

プログラムコードと付録は同時に表示されます。