スポンサーサイト

--年--月--日 --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

シンプレックス法

2008年05月13日 01:07

前回は線形相補性問題に入る前に理解を深めるため、線形計画問題の具体的な例を挙げてみました。

今回はどうやって解いたか?を説明します。
そういうわけなので、前回の例をそのまま使ってみます。


前回の例で挙げられた目的関数は

 3020 + (5 * x1) + (8 * x2) + (6 * x3) + (4 * x4) + (5 * x5) + (2 * x6) -> min

です。

定数項は(当たり前ですが)変化しないので問題に関係していません。ですので、カットしちゃいます。
よって、目的関数の本質は

 (5 * x1) + (8 * x2) + (6 * x3) + (4 * x4) + (5 * x5) + (2 * x6) -> min
 
になります。


次に制約条件は以下になります。

 k1 >= 0 + ( 40 - x1)
 k2 >= k1 + (150 - x2)
 k3 >= k1 + (200 - x3)
 k4 >= k1 + (100 - x4)
 k5 >= k2 + ( 50 - x5)
 k5 >= k3 + ( 50 - x5)
 k6 >= k4 + (100 - x6)
 k6 >= k5 + (100 - x6)
 k6 <= 240
 
 x1 <= 10
 x2 <= 50
 x3 <=150
 x4 <= 50
 x5 <= 40
 x6 <= 60
 
 x1 >= 0
 x2 >= 0
 x3 >= 0
 x4 >= 0
 x5 >= 0
 x6 >= 0
 
左辺式と右辺式を分離しています。


以上が数式です。

数式を挙げて措きながらなんですが、もう一度問題を見直して見ましょう。
この問題の制約条件は、関連性

 企画-+-> プログラム -+-> レベル調整 -+->デバッグ
     +-> デザイン  -+           |
     +-> サウンド ------------------+

と、作業日数・減らせる作業日数から成り立っています。
ならば、一番効率よく減らすにはボトルネックになっている部分を減らすべきでしょう。

まずはじめに、予定日数どおりに(予算を余分にかけずに)プロジェクトを遂行した場合、何日掛かるか調べてみます。
予定日数は

 企画    :  40
 プログラム : 150
 デザイン  : 200
 サウンド  : 100
 レベル調整 :  50
 デバッグ  : 100
  
なのと、関連性を加味すると、

 40 -+-> 150 -+-> 50 -+-> 100
    +-> 200 -+     |
    +-> 100 --------+

になります。
上記のルートで(制約になる関連性を無視して)最大日数になるのはデザインのルートっぽいですよね。
ですので、そこの予定日数を出してみると、

 40 + 200 + 50 + 100 = 390
 
になりました。

制約は 240 日以内ですので、150 日ぐらい減らせば良さそうです。
ちなみに、プログラムのルートでは

 40 + 150 + 50 + 100 = 340
 
同じくサウンドのルートでは、

 40 + 100 + 100 = 240
 
になります。
制約になる関連性を無視すれば、サウンドは既に240日以内ですね。
なので、以降は簡略化のために省きます。


以上、日数を上げてみて気付いたと思うのですが、企画とデバッグの作業日数を短縮できれば全体の作業日数をストレートに減らせそうです。
ですが、どちらを先に減らせばいいのでしょうか?
この問題の目的は費用の最小化を図るためなので、「作業日数を減らすために掛かる費用が少ない方」に対して優先的に予算を割り振ればいいと考えれます。

そこで、作業日数にかかる費用を挙げてみます。
これは目的関数に組み込まれていますね。

 企画    : 5 * x1
 プログラム : 8 * x2
 デザイン  : 6 * x3
 サウンド  : 4 * x4
 レベル調整 : 5 * x5
 デバッグ  : 3 * x6

先ほど言ったように、定数項は問題の本質とは関係ないので除去しています。

さて、デバッグと企画のどちらが掛かる費用が少ないか?は上記を見ればわかります。

企画が 5 でデバッグの方が 3 なので、企画の方が高いです。
ですから、デバッグの方に優先的に費用を割り振ります。
最大限減らせる日数は決まっていますから、最大限まで振っちゃいましょう。
すると 60 日まで減らせます。


すると、それぞれの作業日数の予定は以下のようになります。

 デザイン :40 + 200 + 50 + (100 - 60) = 330
 プログラム:40 + 150 + 50 + (100 - 60) = 280

まだ作業日数が 240 日以内ではないので、今度は企画を減らします。
企画は 10 日減らせますので、こっちも最大限減らします。
すると、、、

 デザイン :(40 - 10) + 200 + 50 + (100 - 60) = 320
 プログラム:(40 - 10) + 150 + 50 + (100 - 60) = 270

になりました。

まだまだ足りません。
次に、デザインルートとプログラムルートで共通な工程のレベル調整を減らして見ましょう。
ここをある程度減らせば、プログラムルートの方は 240 日以内に収まりそうです。
しかし、デザインルートの方は 240 日以内に収まりません。

では、レベル調整の作業日数を何日減らせばいいでしょうか?
ここでも費用の式を見比べます。

デザインルートで今まで減らした工程とこれから選択するレベル調整の工程以外に残った工程はデザインの工程のみです。
ですから、デザインの工程とレベル調整の工程を費用式を見比べて見ましょう。

 デザイン  : 6 * x3
 レベル調整 : 5 * x5

デザインの方が係数が大きいですよね。
ですから、レベル調整の工程を目いっぱい減らした方が費用が安いとなります。
もしここで、デザインの工程の方が安い場合は、レベル調整をプログラムルートが240日以内に収まるように減らした後でデザインの工程を減らした方がいいとなります。

ではレベル調整の工程を最大限まで減らしてみましょう。
最大限減らせる日数は 30 日ですので、、、

 デザイン :(40 - 10) + 200 + (50 - 40) + (100 - 60) = 280
 プログラム:(40 - 10) + 150 + (50 - 40) + (100 - 60) = 230

この時点でプログラムルートは間に合いそうですので、デザインルートだけ考えることにします。

デザインルートで残りの工程はデザインの工程になります。
もう減らせる工程はここしかないので、ここを期間内で終わらせれるように減らしてみましょう。
残りの超過分は 280 - 240 = 40 ですので、40 日減らせば間に合うとなります。
ですので、

 デザイン :(40 - 10) + (200 - 40) + (50 - 40) + (100 - 60) = 240
 
となり、全てのルートで期日内で終わることが保障されました。

最終的に減らした日数を表にすると

 企画   :10
 プログラム: 0
 デザイン :40
 サウンド : 0
 レベル調整:40
 デバッグ :60

となり、費用は、

 企画    : 5 * 10 = 50
 プログラム : 8 * 0 =  0
 デザイン  : 6 * 40 = 240
 サウンド  : 4 * 0 =  0
 レベル調整 : 5 * 40 = 200
 デバッグ  : 3 * 60 = 180

と出て、余分に掛かる費用の総和は

 50 + 0 + 240 + 0 + 200 + 180 = 670
 
となりました。



以上の手順はやってることも単純な比較と式の代入ですし、なんとなく機械的に処理できそうです。
そういうわけで、アルゴリズムとしてまとめたものが「シンプレックス法」となります。

シンプレックス法の概念は説明した手順に若干手を加えたものになります。

目的関数が最大化を目指す場合と最小化を目指す場合で違うのでは?と考えるかもしれませんが、同じアルゴリズムで扱えちゃえます。
というのも、目的関数・制約条件両方にマイナスの値を掛けてやれば、最小化問題を最大化問題として、最大化問題を最小化問題として扱えるからです。
例えば、a -> max にする問題と -a -> min にする問題で a の答えは変わりませんよね?


そんなわけで、最大化する問題のシンプレックス法として以降の説明を書きます。
まずアルゴリズムの簡単な流れは

 ①:制約式の不等号が等式になるような変数(スラック変数といいます)を導入し、等式に直す。
   またこのとき、スラック変数は非負となるようにする。
    例えば、
     a < b → a = b - λ → a + λ = b
     a > b → a = b + λ → a - λ = b
    になる。
 ②:スラック変数を基底に置き、スラック変数の関係式と見る。
 ③:各制約式を同時に満たしながら基底以外の変数がどれだけ最大限まで増やせるのか?を調べる
 ④:最大限まで増やした結果、目的関数がどれぐらい増加するか調べる。
 ⑤:目的関数の増加が一番大きい変数を最大限まで増やしてみる。
 ⑥:⑤の結果、どこかの制約式で必ず基底 = 0 となるので、今度はその変数を基底と置く。
 ⑦:⑥で基底に置いた変数を各制約式と目的関数に代入し、⑥の基底変数を制約式と目的関数から消去する。
 ⑧:目的関数で変数の符号が + のものがある→増加する余地があるので、 + の符号の変数がなくなるまで ③ に戻る。
 
となります。

まぁ、分かり難いですよねw
そんなわけで、前回のゲームプロジェクトとは別の(数式だけの)例を挙げてやってみます。

 制約条件
  2x + 6y < 90
  5x + 4y < 90
  
 目的関数
  25x + 22y -> max
 
 
ステップ : ①
 2x + 6y + λ(1) = 90
 5x + 3y + λ(2) = 90

ステップ : ②
 λ(1) = 90 - 2x - 6y
 λ(2) = 90 - 5x - 3y
 
ステップ : ③
 目的関数のうち、x も y もどちらも、増加したときに目的関数が増加するので、どちらがより多く増やせるか調べる。
 y を無視して考えると x は λ(1) = 90 - 2x より 45、λ(2) = 90 - 5x より 18 よって 18、
 x を無視して考えると y は λ(1) = 90 - 6y より 15、λ(2) = 90 - 3y より 30 よって 15
 
ステップ : ④ - 1
 それぞれの目的関数の増加数は x : 25 * 18 = 450, y : 22 * 15 = 330。
 よって、x を増やしたほうが目的関数が増える。
 
ステップ : ⑤
 ④の結果、λ(2) = 90 - 5x - 3y が λ(2) = 0 になる。
 
ステップ : ⑥
 今度は x を基底にする
  5x = 90 - 3y - λ(2)
  x  = 18 - 0.6y - 0.2λ(2)
  
ステップ : ⑦
 各制約式と目的関数から x を削除する。
  λ(1) = 90 - 2(18 - 0.6y - 0.2λ(2)) - 6y
   = 54 - 4.8y - 0.4λ(2)
  
   25(18 - 0.6y - 0.2λ(2)) + 22y
  = 450 + 7y - 5λ(2)

ステップ : ⑧
 ⑦の結果、目的関数の中でまだ y が + なので、③に戻る
 
ステップ : ③
 目的関数のうち、y が増加したときのみ目的関数が増加するので y が取り得る最大値を求める。
 x = 18 - 0.6y - 0.2λ(2) より 30、λ(1) = 54 - 4.8y - 0.4λ(2) より 11.25
 
ステップ : ④ - 2
 11.25 が y の取り得る最大値。
 
ステップ : ⑤
 ③、④の結果、λ(1) = 54 - 4.8y - 0.4λ(2) = 0 になる。

ステップ : ⑥
 今度は y を基底にする
 4.8y = 54 - λ(1) - 0.4λ(2)
 y  = 11.25 - 0.2083λ(1) - 0.0833λ(2)
 
ステップ : ⑦
 各制約式と目的関数から y を削除する
 450 + 7(11.25 - 0.2083λ(1) - 0.0833λ(2)) - 5λ(2)
 528.75 - 1.4583λ(1) - 5.5833λ(2)
 
ステップ : ⑧
 目的関数の変数の符号に + が含まれなくなったので終了。
 

ということで、シンプレックス法が終了しました。

結果、最大値は 528.75 と出ました。
また、このときの x、y の値は ④-1・④-2より

 x = 18
 y = 11.25
 
になります。


スポンサーサイト


最近の記事


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。