Web教材一覧>
オペレーションズ・リサーチ>
線形計画法(LP)
数理計画法の種類
学習のポイント
キーワード
線形計画法(LP、リニアプログラミング)、輸送問題,割付問題,ナップザック問題、非線形計画法、DP(ダイナミックプログラミング)
いくつかの制約条件の下で,目的関数を最大(最小)にする解を求める技法の総称を数理計画法といいます。線形計画法は、数理計画法の代表的な技法です。
数理計画法
線形計画法(制約条件、目的関数が一次式
輸送問題、割付問題など(制約式に特殊な条件)
整数計画法(変数が整数のもの。大規模問題に適切なアルゴリズムは未発見)
ナップザック問題、巡回セールスマン問題など(特殊な条件)
非線形計画法(制約条件、目的関数が一次式以外。多様な解法がある)
動的計画法(多段階での最適化)
- 輸送問題
- M個の供給地の供給可能量,N個の需要地の需要量,各供給地と各需要地までの運賃を与えて,総運賃を最小にする輸送割当をする問題です。
- 割付問題
- N人の人とN個の業務があり,各人が各業務での能力が与えられているとき,全体の能力を最大にするには,誰をどの業務に割り付ければよいかという問題です。
- ナップザック問題
- 多数の品物の容積と重量などの特性値と効果と,それぞれの特性値の上限値が与えられたとき,効果を最大にするには,どの品物を選べばよいかという問題です。
- 非線形計画法
- 制約式あるいは目的関数が一次式ではない数理計画法の総称です。
- 動的計画法
- DP(ダイナミックプログラミング)ともいいます。例えば,複数の冷却塔を直列に通して冷却するとき,どの段階でどの程度冷却すればコストが最小になるか。複数の投資案があり,それぞれの投資案の投資レベル(投資額)とそれに応じた利益額,総投資額が与えられたとき,どの投資案にどれだけ配分すればよいかなどの問題に適用されます。