有趣的实用问题：安排任务，用时最短。
有一批加工任务：A零件120件，B零件380件，C零件30件，
有160个工人，能力各不相同（有的擅长A零件，有的擅长B零件，有的擅长C零件），从中挑选出16个人，
完成这批任务，每人只能挑一种零件，要求以最短的时间完成（交货期很紧）。
请问如何安排？用什么算法？
[解决办法]
设每个人员有以下属性,
pid 唯一标识某个人员
ta 加工一个A零件所需要的时间
tb 加工一个B零件所需要的时间
tc 加工一个C零件所需要的时间
对于160人员进行以下操作:
1. 以ta进行排序
2. 以tb进行排序
3. 以tc进行排序
注: 均为升序排序
注, 最优结果可能存在多种, 我们只求一种即可
推论一: 存在某一最优结果, 如果某个人员加工A零件, 则以ta排序排在其前面的人员, 必定出现在所选的16个人中
证明: 如果某一最优结果, 某一人员p1加工A零件, 但以ta排序在其前面有一人员p2不在16人员, 由于p2-> ta <= p1-> ta, 则使用p2代替p1, 肯定仍是最优结果
同理:
推论二:
存在某一最优结果,
如果某个人员加工A零件, 则以ta排序排在其前面的人员, 必定出现在所选的16个人中。
如果某个人员加工B零件, 则以tb排序排在其前面的人员, 必须出现在所选的16个人中。
如果某个人员加工C零件, 则以tc排序排在其前面的人员, 必须出现在所选的16个人中。
由此， 至多在48个人中选16个人了， 情况少了很多了
而且，在以下选择中最优的，也就是问题所求最优
在ta排序中选择最前面的x个，再在tb排序中选择未选的最前面的y个，然后在tc排序中选择未选最前面的z个， （x+y+z=16) （x, y, z > = 0)
一共有： 1 + 2 + 3 + ... + 17 = 17 * 9 = 153 种
然后在这153种中， 求出最短时间
[解决办法]
动态规划问题,列出方程求解就是了.
1. 已经参数, 每个工人加工一个A,B,C零件的时间,可以用矩阵表示
p11, p12, p13
p21, p22, p23
...
p1601, p1602, p1603
2. 设置未知数, 每个工人是否加工一个A,B,C零件的时间,可以用矩阵表示
x11, x12, x13
x21, x22, x23
...
x1601, x1602, x1603
3. 设置未知数, 最终需要的时间y.
4. 列出约束条件
首先xij,y都是非负整数
//每个人最多只能参与一项工作
x11+x12+x13 <=1
x21+x22+x23 <=1
...
x1601+x1602+x1603 <=1
//从中挑选16人参与
x11+x12+x13x21+x22+...+x1601+x1602+x1603=16
//A零件120件，B零件380件，C零件30件
y*x11/p11+y*x21/p21+...+y*x1601/p1601> 120
y*x12/p12+y*x22/p22+...+y*x1602/p1602> 380
y*x13/p13+y*x23/p23+...+y*x1603/p1603> 30
然后两边都除以y,令z=1/y,可以得到
x11/p11+x21/p21+...+x1601/p1601> 120*z
x12/p12+x22/p22+...+x1602/p1602> 380*z
x13/p13+x23/p23+...+x1603/p1603> 30*z
确定目标,最短时间完成,也就是要y最小,也就是要z最大.
所以目标就是max(z)
本来未知数的多的话,matlab可以很快就结束来的,现在多的话可以用matlab或者c变成实现.
求解线性规划问题的方法已经被标准话了的,楼主google就是了.
