実際問題の定式化(1)

実際問題を定式化するにはちょっと頭を使う必要があります.
ここでは,そのような実際問題を定式化(モデル化)するための,ちょっとしたパズルをご紹介します.

こんな問題を考えます.

大型,中型,小型のトラックを,3種類のバースで荷捌きしています.
バースは大型用,中型用,小型用の3種類があって,大型トラックは大型用のみ,中型トラックは大型用と中型用で,小型トラックはどのバースでも荷捌きができます.

バースの数が大型は5台分,中型は2台分,小型は4台分しかないとき,時間帯別に到着するトラックの台数の上限を表す制約をどのように表現するかを考えます.

トラックをどのバースに割り当てるのかを表す0-1変数を用いるのが普通の考え方ですが,大規模な問題の一部としてそのような表現で定式化するのは,あまり効率が良くありません.

トラックのサイズによるバースへの割り当てが入れ子構造になっていることを着目すると,以下のように定式化すれば良いことが分かります.

大型トラックの台数 ≦ 5
大型トラックの台数+中型トラックの台数 ≦ 5+2=7
大型トラックの台数+中型トラックの台数 +小型トラックの台数 ≦ 5+2+4=11

大型のバース(5台分)には大型車のみなので5以下ですが,もし大型トラックが1台しかこないときには,中型は大型バースに4台入れることができるので,合計5台入れることになります.

このように,入れ子構造を利用して無駄な0-1変数を入れずに定式化することで,格段に大きな問題を解くことができるようになります.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>