一个最优化问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2909 天前的主题，其中的信息可能已经有所发展或是发生改变。

观察下面的表格

   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 种商品，矩阵内的值表示快递公司运送某种商品的单价。

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

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

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

第 1 条附言 · 2016-12-15 17:12:18 +08:00

每一家快递公司运送货物的总数必须等于其所在行最右侧的值

每一种货物的运送总数必须等于其所在列最下方的值

矩阵

快递

商品

运送

29 条回复 • 2016-12-23 16:19:15 +08:00

liuzhster

2016-12-15 16:11:59 +08:00

多重背包问题?

goodryb

2016-12-15 16:14:06 +08:00

下表不是从 0 开始，差评

Kilerd

2016-12-15 16:14:41 +08:00

感觉楼上说对了，可以试试。这种就是背包模型嘛。

q397064399

2016-12-15 16:52:51 +08:00

动态规划题，╮(╯▽╰)╭ 先把递归公式写出来吧，写出来就差不多了

q397064399

2016-12-15 16:56:30 +08:00

个人建议不会背包或者背包不熟悉，这种题目直接给它穷举就好了

ArieShout

2016-12-15 18:46:50 +08:00 via iPhone

前面几位回答就像数学答案上面的“易得”，“显然”一样呃

justyy

2016-12-15 19:18:43 +08:00

个人感觉应该是动态规化，可是我写不出来公式。。有大牛教教我么？
如果 A 只有 5 个， B 只有 4 个，完全可以暴力。

qinjiannet

2016-12-15 19:52:00 +08:00

@q397064399 这个问题穷举的复杂度是多少？

wodesuck

2016-12-15 22:21:32 +08:00

为什么这么多人说是背包？
我觉得是个费用流啊。
求背包状态转移方程。

billgreen1

2016-12-15 23:36:14 +08:00

如果商品是整数，那么是整数规划问题，有现成的软件包的

q397064399

2016-12-16 05:32:06 +08:00

@qinjiannet 排列组合就好，自己算吧

q397064399

2016-12-16 05:38:01 +08:00

@ArieShout
不是显然，或者易得，刷 OJ 的人大多都会临时突击各种算法，
目的是啥，不还是套路，既然出了这个题目，就证明这个问题是计算可行性的，那不就是套路了，
万千世界，其实就一个套路就可以解释，万物所有的规律包括牛顿定律啥的都是套路，
这题就算不是 DP 也跟 DP 差的八九不离十，

q397064399

2016-12-16 06:00:21 +08:00

@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

这里 10 40 30 60 90 就是一个限定条件，

显然可以通过枚举计算出 10 40 30 60 90 ，分别由 4 个整数组成的排列组合，

这样就枚举出来所有 A1 快递公司所能运送 4 种商品的条件集合

快递公司的运送不同商品的结果集计算复杂度 O(n4)

貌似还有更优的算法，不过我了解过（如果有知道的可以告知我一声）

A1 计算次数是（ 10 ） 4 次方
A2 计算次数是（ 40 ） 4 次方
..
A5 的计算次数是（ 90 ） 4 次方

依次下来通过过滤
就能得到所有快递公司运送这 4 种商品的可行性集合，
（但是这个可行性集并不满足货物数量的限定条件）

然后再从这个集合中，找出符合（ 50 60 50 70 ）的集合

最终从这个合法的集合当中排序获得最大值即可

q397064399

2016-12-16 06:03:37 +08:00

@wodesuck
这个问题其实只要上过高中就能解，但是通过限定条件穷举出合法集，是一种非常傻逼的行为，
在会算法的程序员来看（我真不会多少算法），这种方法有点 Low 假如问题规模变大了，几乎是很难解的出来

q397064399

2016-12-16 06:09:06 +08:00

DP 的思想其实就是通过转移方程，将一些不必要的计算结果集给排除掉了

q397064399

2016-12-16 06:12:31 +08:00

再次强调，通过 X Y 的限定条件来穷举合法矩阵集的最优解是非常 Low 的行为，

如果有人知道此类问题的算法叫什么名字麻烦请告知我一声，（除了 DP ）

Xs0ul

2016-12-16 07:21:57 +08:00 via Android

看起来像是线性规划（

zouxy

2016-12-16 07:34:27 +08:00 via iPhone

好像叫单纯形法

zouxy

2016-12-16 07:36:52 +08:00 via iPhone

华罗庚主持编写那本绿色封面运筹学上有

BBrother

2016-12-16 09:24:22 +08:00

有种运筹学作业的既视感

sengxian

2016-12-16 13:32:23 +08:00

sengxian

2016-12-16 13:33:29 +08:00

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

sengxian

2016-12-16 13:38:47 +08:00

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

qinjiannet

2016-12-16 13:45:31 +08:00

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

sengxian

2016-12-16 14:05:58 +08:00 via iPhone

容量为 a ，费用为 b 。

akira

2016-12-16 14:34:36 +08:00

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

2016-12-19 10:26:31 +08:00

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

hannah520

2016-12-23 16:17:06 +08:00

122

hannah520

2016-12-23 16:19:15 +08:00

啊啊啊啊，竟然回答也需要铜币！重新回答一次吧
数学模型：
*******************************并不造如何上传公式或者图片**************************************
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