線型計画問題とは? わかりやすく解説

線型計画問題

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

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

数学的表現

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

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

Optimization computes maxima and minima.
非線形(制約付き)
凸最適化
組合せ最適化
メタヒューリスティクス

線型計画問題

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

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

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

※この「線型計画問題」の解説は、「双対問題」の解説の一部です。
「線型計画問題」を含む「双対問題」の記事については、「双対問題」の概要を参照ください。

ウィキペディア小見出し辞書の「線型計画問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

すべての辞書の索引



Weblioのサービス

「線型計画問題」の関連用語




4
54% |||||



7
16% |||||




線型計画問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



線型計画問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの線型計画問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの双対問題 (改訂履歴)、線型計画法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS