《指派问题(0-1规划 程序)》由会员分享，可在线阅读，更多相关《指派问题(0-1规划 程序)（13页珍藏版）》请在金锄头文库上搜索。
1、指派问题（assignment problem）问题一：今分派 个工人 去从事 项工作 . 工人 从事工作 的工作效率为nnW,21 nJ,21 iWjJ. 试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且jic,总工作效率最大.建模：令 否 则 ， 件 事 ，个 人 做 第指 派 第,01jixij nji,21,则可建立如下数学规划模型：njixitsxczijnijjinijij,21,0,.mi11算例 1 利用 LINGO 软件求解如下指派问题： ， .5n610296478125C模型求解：Lingo 程序：model:sets:Worker/W1.W5/;
2、Job/J1.J5/;links(Worker,Job):c,x;endsetsdata:c=4,8,7,15,12,7,9,17,14,10,6,9,12,8,7,6,7,14,6,10,6,9,12,10,6;enddatamin=sum(links:c*x);for(Worker(i):sum(Job(j):x(i,j)=1);for(Job(j):sum(Worker(i):x(i,j)=1);for(links:bin(x);end注：程序中并没限制 是 0-1 变量，但由其余约束条件足以保证返回的结果中变量的值为 0、1.ijx结果：Global optimal solution
3、found.Objective value: 34.00000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostC( W1, J1) 4.000000 0.000000C( W5, J5) 6.000000 0.000000X( W1, J1) 0.000000 4.000000X( W1, J2) 0.000000 8.000000X( W1, J3) 1.000000 7.000000X( W1, J4) 0.000000 15.00000X( W1, J5) 0.000000 12.0
4、0000X( W2, J1) 0.000000 7.000000X( W2, J2) 1.000000 9.000000X( W2, J3) 0.000000 17.00000X( W2, J4) 0.000000 14.00000X( W2, J5) 0.000000 10.00000X( W3, J1) 1.000000 6.000000X( W3, J2) 0.000000 9.000000X( W3, J3) 0.000000 12.00000X( W3, J4) 0.000000 8.000000X( W3, J5) 0.000000 7.000000X( W4, J1) 0.000
5、000 6.000000X( W4, J2) 0.000000 7.000000X( W4, J3) 0.000000 14.00000X( W4, J4) 1.000000 6.000000X( W4, J5) 0.000000 10.00000X( W5, J1) 0.000000 6.000000X( W5, J2) 0.000000 9.000000X( W5, J3) 0.000000 12.00000X( W5, J4) 0.000000 10.00000X( W5, J5) 1.000000 6.000000算例 2 今分派 5 个工人 去从事 5 项工作 . 工人 从事工作 的
6、时间521,W 521,J iWjJ见下表：),1,(jic1J23J45J1W8 6 10 9 1229 12 7 11 937 4 3 5 84W9 5 8 11 854 6 7 5 11试求一个分派方案，使每个工人都从事一项工作，每项工作都由一个工人承担，且总工作时间最少.建模：令 ，5,1,01jiJWxjiij一一则可建立如下 0-1 规划模型：5,1,0,.ma5151jixitsxczijijjiijij模型求解：Lingo程序如下：model:sets:Worker/W1.W5/;Job/J1.J5/;links(Worker,Job):c,x;endsetsdata:c=8,
7、6,10,9,12,9,12,7,11,9,7,4,3,5,8,9,5,8,11,8,4,6,7,5,11;enddatamin=sum(links:c*x);for(Worker(i):sum(Job(j):x(i,j)=1);for(Job(j):sum(Worker(i):x(i,j)=1);for(links:bin(x);end结果：Global optimal solution found.Objective value: 30.00000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced
8、 CostC( W1, J1) 8.000000 0.000000C( W5, J5) 11.00000 0.000000X( W1, J1) 1.000000 8.000000X( W1, J2) 0.000000 6.000000X( W1, J3) 0.000000 10.00000X( W1, J4) 0.000000 9.000000X( W1, J5) 0.000000 12.00000X( W2, J1) 0.000000 9.000000X( W2, J2) 0.000000 12.00000X( W2, J3) 0.000000 7.000000X( W2, J4) 0.00
9、0000 11.00000X( W2, J5) 1.000000 9.000000X( W3, J1) 0.000000 7.000000X( W3, J2) 0.000000 4.000000X( W3, J3) 1.000000 3.000000X( W3, J4) 0.000000 5.000000X( W3, J5) 0.000000 8.000000X( W4, J1) 0.000000 9.000000X( W4, J2) 1.000000 5.000000X( W4, J3) 0.000000 8.000000X( W4, J4) 0.000000 11.00000X( W4,
10、J5) 0.000000 8.000000X( W5, J1) 0.000000 4.000000X( W5, J2) 0.000000 6.000000X( W5, J3) 0.000000 7.000000X( W5, J4) 1.000000 5.000000X( W5, J5) 0.000000 11.00000Row Slack or Surplus Dual Price1 30.00000 -1.00000011 0.000000 0.000000由上述结果知，问题的最优解为 ，其余 .15423251 xx 0ijx模型说明：（1）另解：化为六个顶点的完全二分图 上的最优匹配问题
11、，利用匈牙利算法（1955，Kuhn）来解.6,K（2）因 MatLab要求决策变量须为单一下标，故不便于利用MatLab来解.（3）Lindo主要用来解线性规划问题，故建议使用Lingo来解数学规划.问题二：某公司拟将8个职员平均分配到4 个办公室.根据直观评估，有些职员在一起时合作得很好，有些则不然.下表给出了8个职员两两之间的相容程度 （由于对称性，只给出了一半数据），数字越小代表相容得ijc越好： 1s23s45s67s8 9 3 4 2 1 5 62s 1 7 3 5 2 13 4 4 2 9 24s 1 5 5 25 8 7 66s 2 37 48s问：应如何分配这些职员，才能是他
12、们相容得最好？建模：令 一一,01jixij 8,1,ji则可建立如下数学规划模型：81,0,.minjixtsxczijikijjjiij或由所给相容程度数据 的对称性，上述模型只针对表中对角线右上方的数据关系而建立；约束条件“ijc”保证了任一职员 仅被分配一次.8,1,ixikjj或 i模型求解：Lingo程序：model:sets:ren/1.8/;links(ren,ren)| endsetsdata:c=9 3 4 2 1 5 61 7 3 5 2 14 4 2 9 21 5 5 28 7 62 34;enddatamin=sum(links:c*x);for(ren(i):sum(links(j,k)| j #EQ# i #or# k #EQ#
