数学模型4

一．实验目的2.合理建立销售代理点，使得供应的大学生数量最大11.合理安排面试时间，使得面试时间最少二．实验内容2.一家出版社准备在某市建立两个销售代理点，向7个区的大学生售书，每个区的大学生数量（单位：千人）已经表示在图1上。每个销售代理点只能向本区和一个相邻区的大学生售书，这两个销售代理点应该建在何处，才能使得所能供应的大学生的数量最大？建立该问题的整数线性规划模型并求解。11.有四名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以在三个阶段的面试时间也不同，如表所示（单位:min）：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4名同学约定他们全部面试完以后一起离开公司，假定现在时间是8:00，问他们最早何时能离开公司？2.解：将大学生数量为34、29、42、21、56、18、71的区分别标号为1、2、3、4、5、6、7区，画出如下区域区之间的相邻关系：记r为第i区的大学生人数，用0-1变量1ijx表示（i，j）区的大学生由一个代售点供应图书（ij，且i，j相邻），否则0ijx，建立该问题的整数线性规划模型。...()..21,0,1ijijijijijijijijijMaxrrXstxxxix相邻即：12132325344546566747ax63767185637739748992Mxxxxxxxxxx121324253445465667121312232425132334244556465667211..11101ijijxxxxxxxxxxxxxxxstxxxxxxxxxxx或编写M文件xxgh2.m如下：modle:max=63*x12+76*x13+71*x23+85*x25+63*x34+77*x45+39x*x46+74*x56+89*x67+92*x47x12+x13+x23+x24+x25+x34+x45+x46+x47+x56+x67=2;x12+x13=1;x12+x23+x24+x25=1;1234567x13+x23+x34=1;x24+x45+x56=1;x46+x56+x67=1;;;@gin(x12);@gin(x13);@gin(x23);@gin(x25);@gin(x34);@gin(x45);@gin(x46);@gin(x47);@gin(x67);End用LINGO得：Globaloptimalsolutionfound.Objectivevalue:184.0000Objectivebound:184.0000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX120.00000011.00000X130.000000-2.000000X230.0000003.000000X250.000000-11.00000X340.00000011.00000X450.000000-3.000000X460.00000035.00000X560.0000000.000000X670.000000-15.00000X472.000000-18.00000X240.00000074.00000RowSlackorSurplusDualPrice1184.00001.00000020.00000074.0000031.0000000.00000041.0000000.00000051.0000000.00000061.0000000.00000071.0000000.000000从上述结果可以得到：最优解2547==1xx(其他的均为0)，最优值为177人.即：第2、5区的大学生由一个销售代理点供应图书，代理点在2区或者5区，第4、7区区的大学生由另一个销售代理点供应图书，代理点在4区或者7区。11.记ijt为第i名同学参加第j阶段面试需要的时间（已知），令ijx表示第i名同学参加第j阶段面试的时刻（令8:00为面试开始的0时刻）（i=1,2,3,4;j=1,2,3）优化目标为inT||ijijMMaxxt约束条件：1）时间先后次序约束（每人只有参加完前一阶段的面试才能进行下一阶段）；,1ijijijxtx（i=1,2,3,4;j=1,2,）2）每个阶段同一时间只能面试1名同学：用0-1变量iky表示第k名同学是否排在第i名同学前面（1表示是，0表示否），则ijijkjijxtxTy（i,k=1,2,3,;j=1,2,3;ik）1kjkjijikxtxTy（）（i,k=1,2,3,;j=1,2,3;ik）将目标函数改写为1313232333334343inTs.t.MTxtTxtTxtTxt编写M文件xxgh3.m如下：model:min=T;x41+8x42;x42+10x43;x31+20x32;x32+16x33;x21+10x22;x22+20x23;x11+13x12;x12+15x13;Tx43+15;Tx33+10;Tx23+18;Tx13+20;x31+20-x41T*y34;x32+16-x42T*y34;x33+10-x43T*y34;x21+10-x31T*y23;x22+20-x32T*y23;x23+18-x33T*y23;x21+10-x41T*y24;x22+20-x42T*y24;x23+18-x43T*y24;x11+13-x21T*y12;x12+15-x22T*y12;x13+20-x23T*y12;x11+13-x31T*y13;x12+15-x32T*y13;x13+20-x33T*y13;x11+13-x41T*y14;x12+15-x42T*y14;x13+20-x43T*y14;x41+8-x31T*(1-y34);x42+10-x32T*(1-y34);x43+15-x33T*(1-y34);x41+8-x21T*(1-y24);x42+10-x22T*(1-y24);x43+15-x23T*(1-y24);x31+20-x21T*(1-y23);x32+16-x22T*(1-y23);x33+10-x23T*(1-y23);x21+10-x11T*(1-y12);x22+20-x12T*(1-y12);x23+18-x13T*(1-y12);x31+20-x11T*(1-y13);x32+16-x12T*(1-y13);x33+10-x13T*(1-y13);x41+8-x11T*(1-y14);x42+10-x12T*(1-y14);x43+15-x13T*(1-y14);@bin(y34);@bin(y12);@bin(y13);@bin(y14);@bin(y23);@bin(y24);加上约束条件1），2），用LINGO求解得Localoptimalsolutionfound.Objectivevalue:84.00000Objectivebound:84.00000Infeasibilities:0.7105427E-14Extendedsolversteps:44Totalsolveriterations:3516VariableValueReducedCostT84.000000.000000X410.0000000.9999970X4211.000000.000000X4321.000000.000000X3131.000000.000000X3256.000000.000000X3374.000000.000000X2121.000000.000000X2236.000000.000000X2356.000000.000000X118.0000000.000000X1221.000000.000000X1336.000000.000000Y341.0000000.000000Y230.000000-83.99950Y241.0000000.000000Y120.000000-83.99950Y130.0000000.000000Y141.00000083.99950RowSlackorSurplusDualPrice184.00000-1.00000023.0000000.00000030.0000000.00000045.0000000.00000052.0000000.00000065.0000000.00000070.0000000.999997080.0000000.999997090.0000000.0000001048.000000.000000110.000000-0.99999701210.000000.0000001328.000000.0000001433.000000.0000001523.000000.0000001621.000000.000000170.0000000.000000180.0000000.000000190.0000000.99999702053.000000.0000002139.000000.0000002231.000000.000000230.0000000.000000240.0000000.9999970250.0000000.0000002610.000000.0000002720.000000.0000002818.000000.0000002963.000000.0000003059.000000.0000003149.000000.0000003223.000000.0000003335.000000.0000003438.000000.0000003513.000000.0000003615.000000.0000003720.000000.0000003854.000000.0000003948.000000.0000004056.000000.0000004161.000000.0000004249.000000.0000004346.000000.0000004441.000000.0000004533.000000.0000004636.000000.000000470.0000000.9999970480.0000000.000000490.0000000.000000由此可得所有面试完成至少需要84分钟。根据y12=0,y13=0,y14=1,y23=0,y24=1,y34=1,可知面试顺序为4-1-2-3，即：丁-甲-乙-丙。