スポンサーサイト

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

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

線形相補性問題

2008年10月08日 23:45

今まで線形計画問題について利用する事例や解法、グラフ理論との関係などを説明してきました。
以上を踏まえて、線形相補性問題(LCP)に入ります。
線形相補性問題とは目的関数が2次関数で制約条件が1次関数の非線形計画問題のことで、線形制約凸2次計画と同じ意味になります。

実際、ゲーム制作のどんな場面で使用されているか?というと・・・主に物理演算で使用します。
昨今、ミドルウェアとして出回っている物理エンジン(Havok や Open Dynamics Engine など)は制約式を速度や角速度、目的関数を距離などと置き、LCP を解くことで物体間の衝突解決やラグドール処理などを実現しています。
例えば2つの凸体間の最短距離を求めたい場合を考えてみます。
物体上の点をP1・P2とすると平方距離を |P1-P2|^2 と表現できます。これに物体上の点であるという制約式を加えて、最小値を求めるような式を作ればいいわけですね。
また、元になる幾何的な理論はエピポーラ幾何(ステレオビジョンの幾何学)などにも応用できます。
ゲーム分野でも応用範囲の広い分野です。


そもそも非線形計画問題(NLP)とは何でしょう?
線形計画問題が線形に変化する(1次式)問題の最適解を求めていたわけですから、非線形計画問題とは非線形(例えば2次関数とか)に変化する問題の最適解を求める問題なのかな?と推測できます。
その通りですw

非線形計画問題とは2次以上の目的関数および制約条件式の最適解を求める問題全般を指します。
この問題は線形計画問題のように単純に解が求まるか?というと高次関数についてはほぼムリです。
なぜなら4次などの高次関数は部分的な極限を複数含むので、解の探索において部分的な極限に行き着いてしまうとそこが最適解と判断してしまい探索をやめてしまうからです。
ですから、ある一定範囲内での部分的な最適解は求まりますが全体的な最適解を求めるのは極端に難しいわけです。
ただ、3次以上の問題は2次の問題を包括的に含むので、適当な範囲内で区切ってやれば2次問題の組み合わせとして帰結させることが出来ます。
(詳しい人の突っ込み待ってます)


上記の理由から、2次計画問題は非線形計画問題の中でも特別な問題として処理されます。
線形相補性問題はそんな2次計画問題の中で以下の制約で成り立った問題です。
 ・目的関数が2次式
 ・制約条件が1次式
 ・変数(目的関数や制約条件に使用されている未知数)が非負


実際に2次計画問題を解く方法として Lemke 法や内点法というのがあります。
Lemke 法というのは、シンプレックス法を拡張した様な手法で、内点法というのは幾何的な手法で徐々に解に近づけていく方法です。
大規模な(制約式が20以上あるとか)問題に対しては内点法の方が処理が早いですが、小規模な問題に対しては並列化が出来る Lemke 法の方が処理が早いと思われます。
また、内点法は反復的に最適解を求めていくものなので、精度は反復回数と初期値に依存してしまいます。
内点法についてはもう少し詳しく説明できるようになったら補足します。。(内点法自体、概念しか勉強していないんです;)



そんなわけで、Lemke 法に絞って説明します。

Lemke 法。正確には Lemke の相補吐き出し法というらしいです。
やってることはシンプレックス法に非常に良く似ています。
シンプレックス法ではスラック変数を導入し基底を入れ替えていくだけでは解けない問題があるのですが、
そういう場合、人為変数というものを導入して解いていきます(2段階単体法っていうのかな?)
Lemke 法では最初からこの人為変数を導入し、解いていくことになります。
また、相補条件というのが追加されていることと双対条件を利用してること以外は基本的にシンプレックス法の拡張です。



以下説明。
かなり長いかも。


まず適当な凸二次計画法を定義します。
目的関数を T、 制約式を C と記述していきます。

 T:
s_①-1

 C :
s_①-2


まず、目的関数のヘッセ行列(偏微分の係数を対象になるように配置した行列)を作ります。

s_②


ヘッセ行列を利用すれば、2次項の係数を行列として簡単に表せることが出来ます。
よって元の式は、

s_③


と書けます。
ここまでが前段階です。

ちなみに、以前少し書きましたが、ヘッセ行列の特徴として正値対称行列ならばその関数は極限:最小値を持ち、
負値対称行列なら極限:最大値を持ちます。
行列の固有値が全て正(正値対称行列)なのか負(負値対称行列)なのかで最小を持つか最大を持つかが異なるわけですね。

なんでこう言えるのか?ってことを簡単に説明すると、
1:2次式は平行移動で2次項と定数項だけに変換できる(※)
2:定数項を無視すると、1の式はヘッセ行列と各軸の掛け算で表せる。
s_④-1
3:ヘッセ行列は対称行列になるのでハウスホルダー法などで主軸変換が必ず可能、尚且つかける行列は正規直行行列(要するにただの座標変換)
s_④-2
4:正規直行行列が掛かってるだけなので極限の有無には影響しないことを理由に、元の問題は単純に s_④-3 と書ける。
5:ここで、s_④-4 には主軸変換した後のヘッセ行列の固有値が入り、[画像④-5]は x がどんな実数でも必ず正なので、結果的にs_④-4の値に依存する。
  また、極値を持つのは s_④-4が全て同じ符号の時のみ。
  (s_④-4で正負両方が存在する場合は鞍点型になるし、どれか 0 が入ると 0 が入った軸上では一定の値を持つことになるので極値を取る点は無限に存在する)


 
※間単に照明すると、、、
 2次式の一般系s_*1はヘッセ行列s_*2-1を用いて書くと、s_*3になります。(s_*2-2 a s_*2-2 x
 
 これに平行移動量 p を追加すると、以下の様な式になります。
 s_*4-1
 
 ここで①の変形には、s_*4-2s_*4-3 を用いてます。
 
 ①の式にs_*5が成り立つように p を選べば、
 s_*6-1
 のように変形できます。
 ここで、s_*6-2を利用しています。
 
 よって、どんな2次式でも p に適切な値を入れてやれば1次項が消えますので、2次項と定数項のみで表現できるわけです。


 

実際は、固有値を求める必要は必ずしもなくて、シルベスタの定理というのを利用すれば主小行列式を順番に見ていくだけで解ります。
小行列式は一つ大きい小行列式の中でも使われるので、再帰的に行列式を求める割には計算量も掛かりません。
(公式などを使わずに行列のランクだけみて行列式を求める場合、小行列を再帰的に作って行列式を求めていきますから、コスト的にはまったく一緒ですね)

実際、固有値を求めるコストの方が圧倒的に高いです(特異値分解(SVD) だったり QR 法だったり)



閑話休題。
それでは Lemke 法の処理手順を書いていきます。

っと、その前に。
実は制約式も大きな行列に出来ます。
挙げた例の制約条件をよく見てみましょう。
ただの一次式ですよね?
等号が同じ方向なら纏めてしまえそうです。
っていうことで、、、

s_①-2

このような制約式は

s_⑤

と書くことで、

s_⑥

このような行列を利用した形で記述できます。


ここまでで前提条件が揃いました。
では纏めて行きます。
例で挙げた式を解いていきます。

1:目的関数と制約式を洗い出す。

2:目的関数と制約式を纏めた大きな行列を作る。
  s_⑧
  
3:2の行列との関係式を作る。
  s_⑨-1 alpha
  s_⑨-1 beta
  s_⑨-1 c
  s_⑨-1 delta
  s_⑨-1 gamma
  s_⑨-1 tau
  と置き、
  s_⑨-2
  を作る。
  
  αは元の問題の最適解、βは双対問題の最適解で、τは元の問題のスラック変数、σは双対問題のスラック変数になります。
  α、β、σ、τはまだ解らない値なので、不定数に置き換えます。
  
  さらに、これらを以下のように置き換えると、
  s_⑩-1
  s_⑩-2
  s_⑩-3 delta
  s_⑩-3 sdelta
  
  こんな形の一次式の形になります。
  s_⑩-4
  
4:この時点で、s_qi)0.pngが成り立つなら、s_δi=qis_δi と置けば、全ての条件が成り立ちます。
  よって、その場合はここで終了です。
  q の要素に一つでも 0 より小さい値が入ってる場合は 5 へ。
  
5:3の行列を解く為、人為変数[画像(R)]を導入します。
  人為変数を十分大きな値にしておけば、s_artifact.pngs_δi となり、式が成り立ちます。
  なんで、こんな変数を導入できるか?というと、、、一番最後、制約式と目的関数を満たすものが求まったときに、
  人為変数の係数が 0 になっていれば問題ないので OK なんです(結構強引)
  例 :
    s_□1-1
    s_□1-2
    ↓
    s_□2-1
    s_□2-2


6:ここからが本番。
  まず、定数項が一番小さい値を人為変数に置き換えます。
  人為変数は任意の数で、且つ式を成り立たせるためだけに導入した変数です。
  s_qi)0.png(この場合 s1~s6)を成り立たせれば人為変数の目的としては OK なので、
  式を成り立たせるためには一番小さな値を人為変数の値として代入しておけば、s_qi)0.png(この場合x1~x6)でも成り立ちますし、全ての条件を満たします。
  
  よって、一番小さい定数項の式を探し出し、基底を人為変数に置き換えます。
  例 :
    s_□2-1
    s_□2-2
          ↓
    s_□3-1
    s_□3-2

  
7:ここで、人為変数が基底になっているので、基底になっていない変数の対(これを非基底対と称します)が必ず1つだけ存在します。
  逆にこの時点で人為変数が基底になっていなく、人為変数が 0 でも制約式を満たすのならば終了です。

  また、非基底対の片方は直前まで基底になっていた変数です。
  これを基底にしても直前の状態に戻るだけですので、非基底対で直前まで基底になっていなかった変数を新しい基底に選びます。

  次に、この新しい基底を増やしていくと一番早く定数項と等しくなる式を選びます。
  要するに各基底式において、新しく選んだ基底と定数項以外を 0 と見なして、定数項と同じ値になるように新しく選んだ基底に変数を代入して行き、最も小さな値で定数項と同じになる式を選び基底を取り替えるわけです。
  ・・・書いてて意味が解らなくなってるので、例で詳しく書きます。
  
  例 :
    ここで、非基底対は s5, x5。s5 は前回の基底なので x5 を新たな基底に選ぶとします。
    そうすると、基底の部分と定数項以外はとりあえず関係ないので 0 と見なすと、、、
    s_□4-1

    ここで、実際に関係あるのは基底 s1 と基底 s3 の式だけですね。
    よって、この二つの式で x5 を徐々に増やしていくと一番早く定数項と等しくなる式を見つけます。
    まぁ、考えればすぐわかりますが、 s3 の式の方が早いですね。
    x5 に 21 / 5 を代入すれば定数項と同じ 21 になります。

    そんなわけで、今度は s3 の基底式で x5 と s3 を入れ替えます。
    s_□4-2
    s_□4-3
    
    新しい基底式が出来上がったので、これを他の基底式に代入していきます。
    っていっても、今までの流れの中からでもわかりますが関係あるのは s1 の基底式だけですね。

  
8:基底をいくら増やしても基底変数が負にならないときは終了。それ以外は 7を繰り返し行います。

例で挙げた式を繰り返しやっていくのは面倒なので、答えだけ記述します。

答えは
x = 3.8
y = 1.42
z = 2.64
となります。



これで、LCP の問題が解けます。
実際は堂々巡り(退化)したときの処理を追加したりしないといけません。たしかw




2~3が成立する理由ですが、、、LCPの最適解はヘッセ行列を制約式と見立てたLPの最適解と解が
等しいということから来ています。

上が成立する理由は最適解じゃないと仮定して式を変形していくと矛盾した結果になるので解るのが一つと、
LP の場合双対問題が成立するのを利用してさらに式を変形していけば求まります。

んが!かなり長いので割愛します。
時間があれば次回乗っけようと思います。


んで、サンプルソース。

  LCP.txt
  
かなり適当に組んでいるので、まともに動く保障はありません。
それとソースがなかなかに汚いので、参考にすらならないかもしれません。

概念がわかれば、シンプレックス法の延長ですからプログラムに起こすのは簡単だと思います。
例外処理が面倒でしたけど。。
これより解りやすくて見やすくて堅牢なのが出来たら、ぜひご教授くださいw
(僕が作ったソースじゃ遅いと思うし)
スポンサーサイト

線形計画問題の幾何的な意味

2008年09月23日 00:05

久々の更新。。
もうちょっと更新できたら良いんですけど、家につくのは日付が変わってからなので気力が湧きませんでした。
気長に見てくださってる方、ありがとうございます。
忙しいのもやっと落ち着いたのでぼちぼち更新していきます。
次からは矢継ぎ早に更新できるといいなぁ。

ちなみに、ノートPC買いました!
HPのtx2505っていうやつなんですけど、13万ぐらいでタブレットPCのメモリ4GB積んだやつを買えちゃうんですね。すごい安くなったもんだなぁ。

ただ、このノートPC、ものすごい発熱なのがタマに傷ですが・・・。
個人的には結構満足かも。
キーボードも打ちやすいし、画面も見やすいし。いいこと尽くめです。


さて、今回も線形計画法のこと書きます。
本当はそろそろ線形相補性問題に入りたいんだけど。。
もうちょっと理解を深めるということで、違った角度からの話をしたいと思います。


前回までお話した線形計画問題とシンプレックス法。
数学的には、制約を定義しその制約内で最小値(もしくは最大値)を求めるものでした。

ここでの制約というのは ax > b という単純な線形式ですよね。
最大値の場合は不等号が逆(<)になります。

これを具現化してみると。。。
実は多角形の領域に囲まれた部分の問題になります。

制約式の ax > b という部分は ax を x 軸、b を y 軸とみなせば、 ax = b であらわされた直線の上領域に当たるわけです。
ax < b なら下の領域ですね。
ということは、制約式が増えるごとに制約式を満たす領域が限定されていくのがわかります。
もちろん、これは「答えに影響するような制約式」の場合だけの話です。

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
 
になります。


線形計画法

2008年04月27日 23:51

久々に更新!
ってことで、LCP関連のことをやります。

本当はLCP(線形相補性問題)について書きたかったんですけど、前提条件ナシじゃ読めないのでその前の線形計画問題についてから入ります。

いきなりですが、線形計画法の具体的な例を出してみたいと思います。
身近なら話でも結構使われているんですよ。実は。


そんなわけで、ゲーム開発を例にしましょうw
今、ある会社が新作ゲームを作ろうとしています。
問題を単純にするためにゲームの開発には6つの工程があるとします。
その工程は、企画・プログラム・デザイン・サウンド・デバッグ・レベル調整としておきます。
・・・かなり大雑把にしているので、突っ込まないでくださいw

それぞれの工程には関連性があります。
企画がないとプログラムは作れませんよね。
同じようにプログラムがないとデバッグも出来ません。

また、ゲーム開発に良くあることですが、始まる前からプロジェクトの終了期限は決まっています。
ついでに、この会社には凄腕のディレクターがいるので、それぞれの作業に必要な日数はおおむね算出できていて、
さらに余分に費用を掛ければある一定量までなら作業日数を減らせることもわかっています。
(なんという超人的なディレクターw)

もちろん、費用は掛からなければ掛からないほどいいので、費用は最小限に納めたいところです。
どのように人員配置を行えば作業が期限までに終了し尚且つ費用も抑えれるでしょうか?


こういう問題を解くのが線形計画問題といいます。



では、上記の問題を数字を適当にでっち上げて実際に解いて見ましょう。
まず、それぞれの作業日数と費用を表にしてみます。
(この数字は現実のプロジェクトとはかなり差異があると思いますが気にしないでください)

        作業日数  固定費  余分に掛けられる費用の最大値 減らせる作業日数
 企画     :  40    300万       50万                 10
 プログラム  : 150    1200万       400万                50
 デザイン   : 200    1200万       900万               150
 サウンド   : 100    200万       200万                50
 レベル調整 :  50    100万       200万                 40
 デバッグ   : 100     20万       180万                 60
 
またそれぞれの工程には以下の関連性があるとします。

 企画-+-> プログラム -+-> レベル調整 -+->デバッグ
     +-> デザイン  -+           |
     +-> サウンド ------------------+
   
プログラムとデザインが終わらないとレベル調整が出来ない・・・とかですね。
現実では企画が完全に出来ないとプログラムが組めないとかではないので、この限りじゃありませんw
飽く迄、単純に問題化した場合ですので、突っ込まないでくださいw
また、このプロジェクトは 240 日以内という期限があるとします。


以上を踏まえ、これを数式化します。
まず、費用を掛けてどの程度作業日数を減らすか?は、まだ解らないので
それぞれ x1, x2, x3, x4, x5, x6 とします。
例えば、x1 が企画で減らした作業日数です。

この変数を使って企画に掛かる費用を算出してみると、、、

 企画 : 300 + 50 / 10 * x1

同様にして、それぞれの費用を算出します。

 企画   : 300 + 50 / 10 * x1
 プログラム:1200 + 400 / 50 * x2
 デザイン :1200 + 900 / 150 * x3
 サウンド : 200 + 200 / 50 * x4
 レベル調整: 100 + 200 / 30 * x5
 デバッグ : 20 + 180 / 60 * x6
 
次に作業日数の方の問題を数式化します。
それぞれの作業が終わる日を k1, k2, k3, k4, k5, k6 とすると、、、

 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
 
また、最大限減らせる作業日数も決まっているので、以下の制約も加わります。

 0 <= x1 <= 10
 0 <= x2 <= 50
 0 <= x3 <= 150
 0 <= x4 <= 50
 0 <= x5 <= 40
 0 <= x6 <= 60


これで全て数式化できました。
問題としては、作業日数の制約を満たしながら費用の総和を最小化するということになります。

費用の総和を最小化するように人員配置を決めたいので、目的関数は費用の総和ということになります。
ということで、費用の式を直しましょう。

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

よって、総和は

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

になります。



ここまでで全てが数式化できました。
プロジェクト運営が数学の問題になってしまうのが面白いと思いませんか?
要するに、制約条件と目的関数さえ数式化できれば、どんな問題でも数学の問題として扱えてしまうわけです。
(解ける・解けないは別にして)

こういう日程計画問題で有名なものにアメリカがミサイル開発の時に作った PERT というものがあります。
アポロ計画などにも利用されたようです。

他にはロジスティクスの分野で運送費用を最小限にするためにはどのように倉庫を配置すべきか?という問題も
単純なモデル化を施せば線形計画問題になります。



閑話休題。
では、以上のことを踏まえてこの問題を解いてみると、、、

 x1 = 10
 x2 = 0
 x3 = 40
 x4 = 0
 x5 = 40
 x6 = 60
 
 k1 = 30
 k2 = 180
 k3 = 120
 k4 = 200
 k5 = 200
 k6 = 240

となり、このときの余分な費用の総和は「670万」、全体の費用としては「3690万」と出ました。

費用についての最適解が得られたわけです。
もちろん、日数に余裕を持たせたいなら x6 <= 240 の左辺を減らせば費用は増えますが日数は減ります。
工程が一つ増えたり、プログラムの作業期間を限定したいなら、そのように制約条件を増やせば解を求めることが出来ます。


まとめると、線形計画問題とは
 1:目的関数が1次式
 2:制約条件も1次式(不等号・等式、どちらでも可)
の上で、制約条件を満たしつつ目的関数の最適解(最大値や最小値)を求める問題になります。


さて、次回はどんなアルゴリズムでこの問題を解いたか?を説明したいと思います。
・・・これぐらいの関係式ならわざわざプログラムで組む必要もなさそうなもんだけどねw


最近の記事


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