線形計画法せんけいけいかくほう

線形せんけい計画けいかく法ほうとは、1 次じ不等式ふとうしきの連立れんりつで表あらわされた領域りょういき（実行じっこう可能かのう領域りょういき）の中なかで、目的もくてき関数かんすう（1 次つぎ式しき）を最大さいだい・最小さいしょう化かする手法しゅほうです。

手順てじゅん	内容ないよう
① 領域りょういきを描えがく	制約せいやくの連立不等式の領域れんりつふとうしきのりょういきを図示ずし
② 目的もくてき関数かんすうを直線ちょくせんに	$k=ax+by$ を $k$ を動うごかす直線ちょくせんとみる
③ 端はじを探さがす	直線ちょくせんを平行へいこう移動いどうして領域りょういきと交まじわる端はじを見みつける

たとえば「$x+y$ を最大さいだいにせよ」なら、直線ちょくせん$x+y=k$ を平行へいこう移動いどうし、領域りょういきから離はなれる直前ちょくぜんの頂点ちょうてんで最大さいだいになります。

ポイント 最適さいてき解かいは必かならず領域りょういきの頂点ちょうてん（端点たんてん）で取とられる。目的もくてき関数かんすうを「$k=ax+by$ という傾かたむき一定いっていの直線ちょくせん群ぐん」と見みて、$k$ を最大さいだい・最小さいしょうにする頂点ちょうてんを探さがすのが定石じょうせき。各かく頂点ちょうてんの座標ざひょうを代入だいにゅうして比くらべてもよい。