« Carley and Lin(1997) | Main | ツール観戦in hub »

July 20, 2004

ORメモ(4)

ハイ，寝るよ．

■max-flow problem with arc-chain formulation and revised simplex method

1. arc-chain formulationによる定式化を行い，Dを決定する(行がノード間の枝arc，列が経路chain)
2. arc-chain formulationによるmax-flow problemの表現を行う Min z=c(hat)f(hat) s.t. D(hat)f(hat)=b , f(hat) >= 0
3. c_j=-1からc(bar)_j=c_j-π^tD_j=-1-π^tD_j
4. c_j=1より，c(bar)_j=c_j-π^tA_j=1-π^tA_jでrevised simplex methodを行う．
5. for all j, c_j>=0ならば最適であるとして，revised simplex methodにより解く．

以上M戸センセの講義レジュメ(2004/4/30)を要約

明日は復習の続行と残りの課題を片付けたいところだ．

Posted by ysk5 at July 20, 2004 10:42 PM