線型計画問題

ウィキペディア

線型計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/12 01:03 UTC 版)

線型計画問題 (せんけいけいかくもんだい、英: 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}}$

Optimization computes maxima and minima.

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア

ウィキペディア小見出し辞書

線型計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/28 18:23 UTC 版)

「双対問題」の記事における「線型計画問題」の解説

線型計画問題は、目的関数と制約条件が全て線型性を有する最適化問題である。 主問題では、目的関数は n 個の変数を線型に組み合わせたものである。m 個の制約条件があり、それぞれが n 個の変数の線型な組合せの上限を定めている。問題は、制約条件を満たしつつ、目的関数の値を最小化する変数の値の組合せを求めることである。解は n 個の値のベクトル（リスト）であり、それらの値を目的関数に入力することで最小値が得られる。 双対問題では、目的関数は m 個の値の線型な組合せであり、これらは主問題の m 個の制約条件（上限値）それぞれに対応している。n 個の双対制約条件（dual constraints）があり、それぞれが m 個の双対変数（dual variables）の線型な組合せの下限を定めている。この場合、目的関数の値を最大化する双対変数の値の組合せを求める。