<p><a href="http://tokoharu.github.io/tokoharupage/docs/formularization.pdf">LPとグラフと定式化</a> <a href="/ja/tokoharu">tokoharu</a></p>
<ul>
<li><a href="/ja/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF">最短経路</a>問題と LP<ul>
<li>最小費用流の特殊ケース<ul>
<li>辺に十分な容量があって、距離を費用にしたら、1流した時の費用と元のグラフでの最短経路での距離が一致する</li>
</ul>
</li>
<li><a href="/ja/%E5%B7%AE%E5%88%86%E5%88%B6%E7%B4%84">差分制約</a>，俗に<a href="/ja/%E7%89%9B%E3%82%B2%E3%83%BC">牛ゲー</a>(POJ3169(Layout))</li>
</ul>
</li>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E6%B5%81">最大流</a>問題と LP<ul>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E6%B5%81%E6%9C%80%E5%B0%8F%E3%82%AB%E3%83%83%E3%83%88%E5%AE%9A%E7%90%86">最大流最小カット定理</a></li>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E5%BE%AA%E7%92%B0%E6%B5%81">最大循環流</a>問題</li>
</ul>
</li>
<li><a href="/ja/%E6%9C%80%E5%B0%8F%E8%B2%BB%E7%94%A8%E6%B5%81">最小費用流</a>と LP<ul>
<li>最小流量制約付き<a href="/ja/%E6%9C%80%E5%B0%8F%E8%B2%BB%E7%94%A8%E5%BE%AA%E7%92%B0%E6%B5%81">最小費用循環流</a>問題</li>
<li>差分制約のもとでのポテンシャル差最大化問題</li>
<li><a href="/ja/Project%20Selection%20Problem">Project Selection Problem</a></li>
</ul>
</li>
</ul>
<p><a href="/ja/%E5%8F%8C%E5%AF%BE%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E5%95%8F%E9%A1%8C">双対線形計画問題</a></p>
