stackoverflow と google を検索しましたが、まったく同じタイプの問題を抱えている人は見つかりませんでした。
都市に発電所を最適に配置することは、この問題に対する最も近い解決策のように思えましたが、私の問題はそこでの質問よりも単純であり、したがって、ブルートフォースよりも優れた解決策があると思います。
問題はこれです: 私には 9 つの都市があり、それぞれが電力を生産し、電力を使用しています。各都市は他の 8 つの都市に接続されています。余剰電力を必要とする都市に最小限の電力量で送る最良の方法を決定するにはどうすればよいですか?
複数のソースとシンクを利用してネットワーク フローでこの問題を解決しようとしましたが、正しく機能します。
ありがとう！
この記事を見てください。これが、問題を min-cost max-flow に減らす方法です。
すべての都市について、需要dを次のように計算しusage - productionます。d=0、d<0および で都市をグループ化しd>0ます。すべての接続に無限の容量を持たせます。次に、sink と source という 2 つの新しいノードを追加します。d<0capacity を使用して、ソースとノードの間にエッジを追加します|d|。d>0capacity で、 と シンク ノードの間にエッジを追加しますd。これで、単一ソース、単一シンクのネットワークができ、任意の min-cost max-flow アルゴリズムを適用してソリューションを見つけることができます。
これは、標準の配布ネットワーク最適化問題です。2 セットの決定変数を定義 Xi : i 番目の都市で生産された電力、Yij : i 番目の都市で消費された電力 j は供給都市
ある都市から別の都市への送電の送電コストを定義する
目的 : min ∑ Cij * すべての i,j の Yij
制約 : 需要制約 : Xi + ∑Yij (すべての js に対して) <= 都市 i の総電力要求 同様に供給制約
これがうまくいくことを願っています