線形計画法(LP; linear programming ）
一次式（1次不等式および1次等式）で表された複数の制約式の範囲の中で目的関数の最大値、最小値を求める計算法です。
最大値、最小値を求めると同時に、制約条件式の変数の最適解を求める事でもあります。
工業、経済、農業、軍事など、さまざまな分野でこの計算法は利用されています。
また、対象の変数が整数型(たとえば人など)の整数でしか表現できない場合、最適解の取り得る範囲を整数に限定した線形計画法は、整数計画法と呼ばれています。
 線形計画法の例
以下に線形計画法の一般式を示す。
簡単の為、変数を2つにして、以下に線形計画問題の例を示す。
 問題
製品Aを1個作るのに、原料Aが3単位、原料Bが2.5単位、原料Cが1単位必要である。
製品Bを1個作るのに、原料Aが1単位、原料Bが2単位、原料Cが2単位必要である。
原料の在庫の状況は原料Aが9単位、原料Bが12.5単位、原料Cが8単位である。
製品Aを1個販売すると、3万円の利益がある。
製品Bを1個販売すると、2万円の利益がある。
この条件の下で利益を最大にするには製品A,製品Bを何個作ればよいか？
製品Aの個数を 製品Bの個数を
とおくと、以下のように定式化する事ができる。
グラフを描くと以下のようになる。グラフより、制約条件の下で利益を最大なる時は、目的関数の傾きをもった直線が実行可能領域に接した時である。
今回の場合は、A製品2個、B製品3個、その時の利益12万円が求まる。
以上のような問題が線形計画問題である。
変数増えるごとに次元が増えることも直感的に分かるであろう。
今回はこの線形計画法を利用してFIRフィルタ設計を行った。
フィルタ設計問題を最大誤差最小化基準で所望特性の近似を行った。
線形計画法を使用するにあたて、双対問題や相補スラック定理などを利用してフィルタ係数を導出する。
計算アルゴリズムについての説明はここでは省略する。 |
東京電機大学
電気工学科
計算機システム研究室
線形計画法とは