線形計画問題とは？わかりやすく解説

線型計画問題 (せんけいけいかくもんだい、英: linear programming problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。この問題を解く手法を線型計画法という。

数学的表現

行列やベクトルを用いて表現すると、行列Aとベクトルb,cが与えられたとき、制約条件Ax≤b, x≥0をみたしつつc^Txを最大化するベクトルxを求める問題のことである。

線型計画問題は次のように記述できる。

{\begin{matrix}{\text{maximize}}&c^{T}x\\{\text{subject to}}&Ax\leq b\\&x\geq 0\end{matrix}}

$\mbox{max.} \,$	$f(x) \ ( \,$ あるいは, $\min. \ f(x)) \,$
$\mbox{s.t.} \,$	$x = (x_1,x_2,\ldots,x_n) \in F, \,$

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ関数法逐次二次計画法逐次線形計画法


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの線型計画問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。