線形計画問題 の履歴(No.2)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 線形計画問題 へ行く。
  • 1 (2012-09-14 (金) 21:02:30)
  • 2 (2012-09-14 (金) 22:22:29)

線形計画問題とは†

変数の１次の等式または不等式で与えられた制約条件のもとで、変数の1次関数で与えられた目的関数を最大化する問題

example
目的変数：
　70x+120y+30z→最大化
制約条件：
　5x +6z ≦80
　2x +8z ≦50
　7x +15z≦100
　3x+11y ≦70
　x≧0,y≧0,z≧0

シンプレックス法†

効率的に基底解の中から最適基底解を探索するアルゴリズム。

多項式時間アルゴリズム†

アルゴリズムの計算量が変数の数、制約条件の数など問題の規模を表すパラメータの多項式で表せれるとき、多項式アルゴリズムという。一般的に効率的なアルゴリズム。


Back to 数理計画問題