Follow

私が知ってる双対問題で、役に立つのはもう一つあります。グラフ理論で、”最大流最小コスト問題”という有名な物流問題がありますが、実世界では”最大流”制約だけではなくて追加で”最少流”制約という問題もあります。つまり
”最大流最少流最小コスト問題”です。PythonのPuLPなどの最適化パッケージを使えばどっちも簡単に書けますが、それが使えない場合(例えば普通のPythonだけで解く)には超難解です。そこで指定されたネットワークの双対問題のネットワークを作ってやれば、通常言語でも解けます。実際、私もそれを読みながらPrologで解きました。

よくわかるネットワークのアルゴリズム
P107
amazon.co.jp/よくわかるネットワークのアルゴリズ

· · Web · 2 · 1 · 3

最大流最少流って分かりにくいですね。
$x$が流量で、指定の箇所を
$1≤x≤5$の範囲で流れる
みたいな制約の事です。
(流れが$0$でも良いなら簡単なんですが、$1$以上だと難しくなります)

ロジックの本を読んでいて「射影幾何の双対定理」を読みました。私が見つけた2つ、そのまんまです。

Sign in to participate in the conversation
Mathtodon

A Mastodon instance named Mathtodon, where you can post toots with beautiful mathematical formulae in TeX/LaTeX style.