2

我正在尝试使用 GLPK 或 R 中的优化（最小化运输成本）来解决典型的运输问题。

一个简单的案例：位于 2 个省（A 和 B）的 4 家生产商正在向位于其他地方的两个出口商提供产品。我有每个路线生产者-出口者的成本矩阵（见下文）。解决方案将是微不足道的，这是运输问题的典型示例。

例子：

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;

最后两个不等式是固定数量约束。

您可以使用LpSolve解决此问题。为此还有一个 R 包lpsolveAPI。上面的问题公式已经是 LP 格式。

于 2014-02-14T02:46:12.073 回答