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 となるので、今度はその変数を基底と置く。
�АЛΔ粘霙譴肪屬い進竸瑤魍得�約式と目的関数に代入し、�Δ隆霙貶竸瑤鮴�約式と目的関数から消去する。
�─�目的関数で変数の符号が + のものがある→増加する余地があるので、 + の符号の変数がなくなるまで �� に戻る。
となります。
まぁ、分かり難いですよねｗ
そんなわけで、前回のゲームプロジェクトとは別の（数式だけの）例を挙げてやってみます。
制約条件
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
になります。
今回はどうやって解いたか？を説明します。
そういうわけなので、前回の例をそのまま使ってみます。
前回の例で挙げられた目的関数は
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 となるので、今度はその変数を基底と置く。
�АЛΔ粘霙譴肪屬い進竸瑤魍得�約式と目的関数に代入し、�Δ隆霙貶竸瑤鮴�約式と目的関数から消去する。
�─�目的関数で変数の符号が + のものがある→増加する余地があるので、 + の符号の変数がなくなるまで �� に戻る。
となります。
まぁ、分かり難いですよねｗ
そんなわけで、前回のゲームプロジェクトとは別の（数式だけの）例を挙げてやってみます。
制約条件
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
になります。
最近のコメント