サブロウ丸

主にプログラミングと数学

最短路問題を線形計画法で解く (Python)

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、
今回は線形計画法で解いてみたいと思います。(あえてね)

定式化は
f:id:inarizuuuushi:20170702105041p:plain:w700
こうなります。

最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。
ad(j)については、jの隣接ノード集合と書きましたが、有効グラフの場合はノードjを終点とする枝の始点の集合とすれば良いです。

まず、各制約について、今変数dをスタートノードからの最短路長を表すようにしているので、
各dは厳密には以下の式(画像上式)で定まります。 f:id:inarizuuuushi:20170702105506p:plain:w600

上式を言い換えると下式になります。
定式化の制約には不等式しか入っていませんが、目的関数としてd_tの最大化を考えているので、省くことができます。

何故かと言うと、目的関数としてd_tを最大化するので、d_tを上から抑えている制約も同時に最大化されることになりす。
つまりゴールノードtの隣接ノードiに対するd_iも同時に最大化され、 そしてそのd_iの隣接ノードjに対するd_jについても最大化され…と芋づる式に続きます。
(厳密には制約として有効なものに関するd_iについてのみ最大化されます。けれどd_tの値を求めるためだけなら、制約として有効なd_iについて最大化されるだけで十分なのです。)

要するに、d_tの最大化をする上で、最短路を解く上で必要な、画像下式のdj最大という条件は明記しなくても必然的についてくるということですね。


サンプル
f:id:inarizuuuushi:20170702233013p:plain:w400