LP

AOJ2230: How to Create a Good Game

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230LP双対の問題。似たような問題でLongest Shortest Pathがあるのでそれの解説スライドを見ながら考察した。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2736 まず最長距離の双…

最短距離問題の双対について

LP

次のグラフの最短距離問題のLP考えよう。 辺は(辺番号)/(辺のコスト)となっている。 LPは次のようになる。min(y1+3(y2)+y3+3(y4)+y5) s.t. y1+y2=1 y1-y3-y4=0 y2+y3-y5=0 y4+y5=1 y1,y2,y3,y4,y5>=0行列を使うと、 min{yb|y>=0, yA>=c}となる。ただし A= {{…