查看: 980|回复: 4|关注: 0

[已解决] 关于指派问题的程序

[复制链接]

新手

9 麦片

财富积分


050


3

主题

8

帖子

0

最佳答案
对于指派问题里的程序,我在网上看到这么一个,但是中间有块地方不是很理解(红圈的地方),望解答。
原程序:c=[3,8,2,10,3;8,7,2,9,7;6,4,2,7,5;8,4,2,3,5;9,10,6,9,10];
c=c(:);
a=zeros(10,25);
for i=1:5
    a(i,(i-1)*5+1:5*i)=1;
    a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,fval]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),fval

红圈部分

红圈部分


论坛优秀回答者

中级

799 麦片

财富积分


5001500


2

主题

646

帖子

141

最佳答案
  • 关注者: 46
发表于 2018-6-19 09:14:41 | 显示全部楼层
就是把约束条件写成了矩阵的形式
这个指派问题是五个人分别做五个工作
c矩阵给出每个人做每件工作的耗时/工资,目标函数是求总耗时/总工资最少
不妨设行表示每个人做不同工作的消耗,列表示同一工作不同人完成时的消耗
约束条件每个人只能做一件工作,每个工作只由一个人完成
x是0,1构成的5行5列矩阵,0表示对应行的人不被派去做对应列的工作,1表示去做
显然约束条件,以第一行和第一列为例,有
x11 + x12 + x13 + x14 + x15 = 1
x11 + x21 + x31 + x41 + x51 = 1
如果把x写成向量,上面的约束条件就写成
x1 + x2 + x3 + x4 + x5 = 1
x1 + x6 + x11 + x16 + x21 = 1
把所有约束条件都写出来,写成A*x = b的形式
则A矩阵与代码中的a相同,b与代码中的b相同

新手

9 麦片

财富积分


050


3

主题

8

帖子

0

最佳答案
 楼主| 发表于 2018-6-19 21:30:02 | 显示全部楼层
TouAkira 发表于 2018-6-19 09:14
就是把约束条件写成了矩阵的形式
这个指派问题是五个人分别做五个工作
c矩阵给出每个人做每件工作的耗时/工 ...

老师,我能理解您的意思,但是就是这个意思在转换成matlab里程序的时候,我还是想不通这里面的对应关系,这一小部门的程序能当作一个定性思维吗,就比如六个人做六个工作,七个人做七个工作,是不是只要把里面的数据改成6或者7,所要表达的都是一样的?

论坛优秀回答者

中级

799 麦片

财富积分


5001500


2

主题

646

帖子

141

最佳答案
  • 关注者: 46
发表于 2018-6-19 22:19:40 | 显示全部楼层 |此回复为最佳答案
a2281388230 发表于 2018-6-19 09:30
老师,我能理解您的意思,但是就是这个意思在转换成matlab里程序的时候,我还是想不通这里面的对应关系, ...

N个人N件工作的约束条件,仍以第一行和第一列为例,有
①x11 + x12 + x13 + ... + x1N = 1  (矩阵编号)
②x11 + x21 + x31 + ... + xN1 = 1  (矩阵编号)
如果把x写成含N^2个元素向量,上面的约束条件就写成
①x1 + x2 + x3 + ... + xN = 1  (向量编号)
②x1 + x(N+1) + x(2*N+1) + ... + x( (N-1)*N+1 ) = 1  (向量编号)
①式对第M行的约束为xM1 + xM2 + xM3 + ... + xMN = 1  (矩阵编号)
亦即x( (M-1)*N+1) + x( (M-1)*N+2) + x( (M-1)*N+3) + ... + x( (M-1)*N+N) = 1  (向量编号)
②式对第M列的约束为x1M + x2M + x3M + ... + xNM = 1  (矩阵编号)
亦即xM + x(N+M) + x(2*N+M) + ... + x( (N-1)*N+M ) = 1  (向量编号)
所以①式构成的约束矩阵 A1 = repmat(eye(N),1,N);
②式构成的约束矩阵 A2 = blkdiag(ones(1,N),ones(1,N),...,ones(1,N)); % N个ones(1,N);
整个约束矩阵就是 A = [A1;A2];

新手

9 麦片

财富积分


050


3

主题

8

帖子

0

最佳答案
 楼主| 发表于 2018-6-19 23:02:31 | 显示全部楼层
TouAkira 发表于 2018-6-19 22:19
N个人N件工作的约束条件,仍以第一行和第一列为例,有
①x11 + x12 + x13 + ... + x1N = 1  (矩阵编号)
②x ...

老师您讲得很详细,后生比较愚笨,还是不明白您这些该怎么转换成matlab里的程序,字面意思我能理解,但一换到matlab里就不懂如何下手,想不明白这些和图中画红圈的部分有什么联系,后生需要再看看。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /3 下一条

快速回复 返回顶部 返回列表