数理計画法の種類

学習のポイント

いくつかの制約条件の下で，目的関数を最大（最小）にする解を求める技法の総称です。

キーワード

線形計画法（ＬＰ、リニアプログラミング）、輸送問題，割付問題，ナップザック問題、非線形計画法、ＤＰ（ダイナミックプログラミング）

◎ 線形計画法: 数理計画法で最も基本となるもので，ＬＰ（リニアプログラミング）ともいいます。一次（線形）不等式群の制約条件の下で，一次式の目的関数Ｚを最大（最小）にする変数Ｘ_ｉの値を求める技法です。
制約のある原料や設備能力の下で品質条件を満たし利益最大にする製品構成を求める問題などに用いられます。
●発展→「線形計画法」（lp-intro）
次の輸送問題，割付問題，ナップザック問題は，ＬＰの特殊な形式で，その特徴に合わせた解法があります。
輸送問題: Ｍ個の供給地の供給可能量，Ｎ個の需要地の需要量，各供給地と各需要地までの運賃を与えて，総運賃を最小にする輸送割当をする問題です。
割付問題: Ｎ人の人とＮ個の業務があり，各人が各業務での能力が与えられているとき，全体の能力を最大にするには，誰をどの業務に割り付ければよいかという問題です。
ナップザック問題: 多数の品物の容積と重量などの特性値と効果と，それぞれの特性値の上限値が与えられたとき，効果を最大にするには，どの品物を選べばよいかという問題です。
非線形計画法: 制約式あるいは目的関数が一次式ではない数理計画法の総称です。
動的計画法: ＤＰ（ダイナミックプログラミング）ともいいます。例えば，複数の冷却塔を直列に通して冷却するとき，どの段階でどの程度冷却すればコストが最小になるか。複数の投資案があり，それぞれの投資案の投資レベル（投資額）とそれに応じた利益額，総投資額が与えられたとき，どの投資案にどれだけ配分すればよいかなどの問題に適用されます。

「線形計画法」の目次