2

GLPK または R で、最適化 (輸送コストの最小化) を使用して典型的な輸送問題を解決しようとしています。

簡単なケース: 2 つの州 (A と B) にある 4 つの生産者が、別の場所にある 2 つの輸出者に製品を配送しています。各ルート プロデューサー - エクスポーターのコスト マトリックスがあります (以下を参照)。解決策は自明です。これは輸送問題の典型的な例です。

例：

production (id, province, tons)
            1  A      300
            2  A      800
            3  B      800
            4  B     1200

    export (id, sourcing_province, tons)
            5  A      400
            5  B      600
            6        2000

    routes (id_orig, id_dest, cost) 
               1  5  5.1
               1  6  3.2
               2  5  6.7
               2  6  7.2
               3  5  2.8
               3  6  4.1
               4  5  6.9
               4  6  5.3

しかし、問題をより複雑にする追加の制限があります。私は、輸出者 (5) が実際に各州から特定の固定量を調達していることを知っています。特に上記の例では、輸出者 (5) は州 A から 400 Tn、州 B から 600 Tn を調達する必要があります。輸出者 (6) には制限がなく、どの州からでも商品を調達できます。これらの制限を表現する方法が見つかりません。

助けてもらえますか？

4

1 に答える 1

2

エッジの観点から問題を考えることができます。1、2、3、4 が生産者で、5、6 が輸出者である場合、e15 が生産者 1 から輸出者 5 へのフローであり、e25 が生産者 2 から輸出者 5 へのフローであるとします。

この表記では、問題は次のようになります。

/* Objective function */
min: 5.1 e15 + 3.2 e16 + 6.7 e25 + 7.2 e26 + 2.8 e35 + 4.1 e36 + 6.9 e45 + 5.3 e46;

/* production limits */
e15 + e16 <= 300;
e25 + e26 <= 800;
e35 + e36 <= 800;
e45 + e46 <= 1200;

/* demand */
e15 + e25 + e35 + e45 >= 1000;
e16 + e26 + e36 + e46 >= 2000;

/* exporter 5 restrictions   */
e15 + e25 >= 400;
e35 + e45 >= 600;

最後の 2 つの不等式は、固定量の制約です。

この問題にはLpSolveを使用できます。このための R パッケージもありますlpsolveAPI。上記の問題の定式化は、すでに LP 形式になっています。

于 2014-02-14T02:46:12.073 に答える