スポンサーサイト

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

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

線形計画法

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
スポンサーサイト


コメント

    コメントの投稿

    (コメント編集・削除に必要)
    (管理者にだけ表示を許可する)

    トラックバック

    この記事のトラックバックURL
    http://angra.blog31.fc2.com/tb.php/120-0b4b7fce
    この記事へのトラックバック


    最近の記事


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