線形計画法

線形計画法（LP）は、意思決定変数について一次式で表した制約条件を全て満たしながら、一次式の目的関数を最大化又は最小化する最適化手法です。生産、輸送、配分などの連続量を扱います。

■ 試験で押さえるポイント

• 変数、目的関数、各制約、不等号、非負条件を実問題から定式化します。目的・制約の係数が変数に依存したり変数同士を掛けたりする問題は線形ではありません。

• 制約を満たす点の集合を実行可能領域といい凸多面体になります。有限の最適解が存在すれば、少なくとも一つの頂点で最適値を取ります。

• 単体法は頂点間を移動し、内点法は領域内部を進みます。実行可能解なし、目的値が際限なく改善する非有界、最適解が複数という場合もあります。

• 変数が整数個でなければならない生産台数などは整数計画法であり、連続LPの解を単純に丸めると制約違反や非最適になる場合があります。

■ 選択肢での判断ポイント

目的関数・制約が全て線形、実行可能領域の頂点で評価することが基本です。整数制約の有無を確認します。

例: $3x+2y$を最大化し、$x+y\le4$、$x\le2$、$x,y\ge0$なら、頂点$(0,0),(2,0),(2,2),(0,4)$の利益は0,6,10,8なので最適解は(2,2)です。