【せんけいけいかくほう】
線形計画法 とは？
最終更新:
💡 線形の条件のもとで、目的値を最適化する
連続値の変数を使い、線形の目的関数を線形制約のもとで最大化・最小化する数理最適化。制約を満たす解がない場合や、目的値に有限の限界がない場合もあります。
📌 このページのポイント
ひよこ どんな数式になるの？
ペンギン先生 例として3x＋2yを最大にし、x＋y≤4、x≤2、x≥0、y≥0という条件を付ける。これは説明用のモデルだよ。実際には資源や費用の関係が線形で表せるかを確認して、変数と式を決めるんだ。
ひよこ その例の答えは？
ペンギン先生 x＝2、y＝2で目的値は10だよ。3x＋2y＝2(x＋y)＋x≤2×4＋2＝10だから、これより大きくできない。図でも制約を満たす領域と、この点を同じ数式で表しているよ。
ひよこ 線形なら必ず最適解がある？
ペンギン先生 例えばx≥2とx≤1を同時に課せば解がない。x≥0だけでxを最大化すれば、いくらでも増やせて有限の最大値がない。最適解が複数になる問題もあるので、必ず一つの答えを返すとは限らないんだ。
ひよこ 人の人数も小数で求めていい？
ペンギン先生 人数など整数でないと困る変数は、整数条件を入れる必要があるよ。式が線形でも整数計画や混合整数計画になり、連続値の線形計画とは解き方や難しさが変わる。単に非線形問題と呼ぶわけではないんだ。
ひよこ ソフトで計算した数字はそのまま使える？
もっと詳しく知りたい人へ
最適解は必ず図の角にある？
図の例は角の一つが最適ですが、辺の上の複数の点が同じ最適値になる場合もあります。OR-Toolsの説明では、シンプレックス法は頂点の解を返す一方、内点法などは必ず頂点を返すとは限りません。「全アルゴリズムが角だけを調べる」とは考えないでください。
まとめ：ざっくりこれだけ覚えればOK！
「線形計画法」って出てきたら「線形の目的関数と制約を使う最適化」と思えばだいたいOK！
📖 おまけ：英語の意味
「Linear Programming」 ＝ 線形計画法
💬 ここでのProgrammingは最適化する計画を表します。コードを書く行為の名称ではありませんが、実際の計算にはソフトウェアのソルバーを利用できます。