一个最优化问题

[qinjiannet]

观察下面的表格

   B1 B2 B3 B4
A1 9  9  8  3   10
A2 2  6  4  4   40
A3 8  9  3  4   30
A4 3  3  5  2   60
A5 9  9  1  6   90
   50 60 50 70
	

---

上表中 A1~A5 表示 5 家快递公司， B1~B4 表示 4 种商品，矩阵内的值表示快递公司运送某种商品的单价。

矩阵右侧的值表示各家快递公司需要运送的商品总数

矩阵下方的值表示每种商品的总数

求满足上述约束条件的最小运费

[sengxian]

[sengxian]

啊不好意思上面鼠标截下来了

[sengxian]

这个题网络流的点数是 $O(n + m)$，边数是 $O(nm)$ 的，鉴于网络流的复杂度都比较高，所以大概只能跑几百的数据。

[qinjiannet]

@sengxian 图中的(a, b)表示容量为 a ，初始流量为 b 吗？

[sengxian]

容量为 a ，费用为 b 。

[akira]

https://github.com/ericliu859/AcmPaper/blob/master/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/%E6%9D%8E%E5%AE%87%E9%AA%9E/6.%E6%9D%8E%E5%AE%87%E9%AA%9E%E3%80%8A%E6%B5%85%E8%B0%88%E4%BF%A1%E6%81%AF%E5%AD%A6%E7%AB%9E%E8%B5%9B%E4%B8%AD%E7%9A%84%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92%E2%80%94%E2%80%94%E7%AE%80%E6%B4%81%E9%AB%98%E6%95%88%E7%9A%84%E5%8D%95%E7%BA%AF%E5%BD%A2%E6%B3%95%E5%AE%9E%E7%8E%B0%E4%B8%8E%E5%BA%94%E7%94%A8%E3%80%8B.doc

[peihanw]

典型线性规划问题，用 GLPK 写一个 model 定义文件，秒解。

[hannah520]

122

[hannah520]

啊啊啊啊，竟然回答也需要铜币！重新回答一次吧
数学模型：
*******************************并不造如何上传公式或者图片**************************************
matlab 求解：
function [f]=transport(x)
f=0;
C=[7 1 1 6 3 3 7 6 9 7 9 5 4 2 5 8 7 1 3 9];
for i=1:20
f=f+x(i)*C(i);
end
end

lb = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
ub = [Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf];
x0 = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
Aeq = [1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
Beq = [30 90 30 60 70 30 50 40 20];
[x,f] = fmincon(@transport,x0,[],[],Aeq,Beq,lb,ub)

结果如下：
x =

1 至 13 列

0.0000 39.1780 30.0000 0.8220 20.8220 0.0000 0.0000 9.1780 0.0000 0.0000 0.0000 50.0000 9.1780

14 至 20 列

30.8220 0.0000 0.0000 0.0000 20.0000 0.0000 0.0000


f =

560.0000