ゼミの風景

おそらくお気楽はしのすけゼミの諸風景

Top | ゼミ2016卒 | ゼミ2015卒 | ゼミ2014卒 | イベント | About

最小費用流問題(4年ゼミ)

f:id:okiraku894:20140828130512j:plain
f:id:okiraku894:20140828120651j:plain
一か月の夏休み後,最初の最適化問題ゼミ.
今回から最小費用流問題を取り扱うのだそうだ.
まずはアルゴリズムを二通り紹介.
残余ネットワークに負のサイクルが無ければ最小費用流.
ふ~ん,そうなんだ.
そして,もう一つのアルゴリズムPrimal/Dual法.
こちらも言っていることは「そりゃそうだ」なんだけど,
それで本当に最小か?っと言われると自明な気がしない.
ではこれを証明してみよう,という話になった.