实验报告-整数规划2

实验序号：数学实验报告实验序号：日期：2012年6月10日班级水文1001，熊元武「学号1101550120~实验名称整数汉规划之指派冋题问题背景描述：有n项不冋的任务，恰好n个人可分别承担这些任务，但由于每人特长不冋，完成各项任务的效率等情况也不同。指派问题现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。实验目的:1.理解指派问题这一特殊整数线性规划问题的特点，体会指派问题求解的匈牙利法；2掌握用Matlab或LINDO求解指派问题的方法和步骤，学会利用Matlab或LINDO求解具体指派问题及其变形问题。3.锻炼应用所学知识解决综合性问题的能力实验原理与数学模型:指派问题是一类常见的特殊0-1整数线性规划，也可看作是特殊的运输问题。指数问题的求解也是一个不断试探、判断、再试探再判断的过程。如果能够很好的理解这中问题求解模式，并根据实际问题的需要加以变通，可以有效提升学生解决实际问题的能力。实验所用软件及版本:LIND09.0主要内容（要点）:复习整数规划的的解法，特别是匈牙利算法掌握lingo的整数规划解法用整数规划的方法解决下面指派问题实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）：例1,公司在各地有4项业务，选定了4位业务员去处理。由于业务能力、经验和其它情况不同，4业务员去处理4项业务的费用（单位：元）各不相同，见下表:业务业务员123111008001000260050030034008001000411001000500应当怎样分派任务，才能使总的费用最小？问题的分析与求解：引入如下变量：设Xij=1(若分配第i个人做第j项业务)或0(若不分配第i个人做第j项业务)。矩阵a(4,4)为指派矩阵，其中a(i,j)为第i个人做第j项业务的业务费。下面是lingo程序：MODEL:SETS：person/1..4/;task/1..4/;assign(person,task):a,x;ENDSETSDATA:a=1100,800,1000,700,600,500,300,800,400,800,1000,900,1100,1000,500,700;ENDDATAmin=@sum(assign:a*x);@for(person(i):@sum(task(j):x(i,j))=1);@for(task(j):@sum(person(i):x(i,j))=1);@for(assign(i,j):@bin(x(i,j)));ENDGlobaloptimalsolutionfound.Objectivevalue: 2100.000Extendedsolversteps: 0Totalsolveriterations: 0VariableValueReducedCostA(1,1)1100.0000.000000A(1,2)800.00000.000000A(1,3)1000.0000.000000A(1,4)700.00000.000000A(2,1)600.00000.000000A(2,2)500.00000.000000A(2,3)300.00000.000000A(2,4)800.00000.000000A(3,1)400.00000.000000A(3,2)800.00000.000000A(3,3)1000.0000.000000A(3,4)900.00000.000000A(4,1)1100.0000.000000A(4,2)1000.0000.000000A(4,3)500.00000.000000转下页）

实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页））A(4,4)700.00000.000000X(1,1)0.0000001100.000X(1,2)0.000000800.0000X(1,3)0.0000001000.000X(1,4)1.000000700.0000X(2,1)0.000000600.0000X(2,2)1.000000500.0000X(2,3)0.000000300.0000X(2,4)0.000000800.0000X(3,1)1.000000400.0000X(3,2)0.000000800.0000X(3,3)0.0000001000.000X(3,4)0.000000900.0000X(4,1)0.0000001100.000X(4,2)0.0000001000.000X(4,3)1.000000500.0000X(4,4)0.000000700.0000RowSlackorSurplusDualPrice12100.000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000得到的结果如下：x(1,1)=0,x(1,2)=0,x(1,3)=0,x(1,4)=1;x(2,1)=0,x(2,2)=1,x(2,3)=0,x(2,4)=0;x(3,1)=1,x(3,2)=0,x(3,3)=0,x(3,4)=0;x(4,1)=0,x(4,2)=0,x(4,3)=1,x(4,4)=0;最小费用为2100元。即第1个业余员做第4项业务，第2个业余员做第2项业务，即第3个业余员做第1项业务,第4第4业余员做第3项业务。总费用达到最小,为2100元。实验结果报告与实验总结:指派问题的特点：有nxn个变量，2n个约束的特殊运输问题，各点的供应和需求都为1；问题高度退化，在2n-1个基变量中只有n个取1,其余n-1个基变量为零。给定一个指派问题时，必须给出效率矩阵(系数矩阵)C=(C),且C>0，因此ijnxn ij必有最优解maxz=戏"Cx>0.ijiji=1j=1指派问题是一种特殊的平衡运输问题。由于模型结构的特殊性(看作每个产地的产量均为1,每个销地的销量均为1),故可用更为简便的匈牙利算法进行求解若从效率矩阵(C)的一行(列)各元素中分别减去该行(列)的最小元素，得ij