数学建模课后作业第五章.doc

第五章.图论组合优化实验5.2.基本实验1.最短路问题的应用设备更新问题解：令xi为表示第i年初购买一台新设备，令（xi,xj）为第i年初购买用到第j年初的设备，令xij为第i年到j年所支付的总费用。可得：（x1,x2） x12 =2.5+0.3-2 =0.8；（x1,x3） x13 =2.5+0.3+0.5-1.6 =1.7；（x1,x4） x14 =2.5+0.3+0.5+0.8-1.3 =2.8;（x1,x5） x15=2.5+0.3+0.5+0.8+1.2-1.1 =4.2;（x2,x3） x23=2.6+0.3-2 =0.9;（x2,x4） x24=2.6+0.3+0.5-1.6 =1.8;（x2,x5） x25=2.6+0.3+0.5+0.8-1.3 =2.9;（x3,x4） x34=2.8+0.3-2 =1.1;（x3,x5） x35=2.8+0.3+0.5-1.6 =2.0;（x4,x5） x45=3.1+0.3-2 =1.4;从第一年初到第五年初的费用为：(1) x12+x25 =0.8+2.9=3.7；x12+x24+x45 =0.8+1.8+1.4=4；x12+x23+x35=0.8+0.9+2=3.7；x12+x23+x34+x45 =0.8+0.9+1.1+1.4=4.2；(2) x14+x45=2.8+1.4=4.2； x13+x34+x45=1.7+1.1+1.4=4.2，(3) x13+x35=1.7+2.0=3.7；(4) x15=4.2；由以上的结果可知最少的支出费用为x13+x35=1.7+2.0=3.7万元 ;x12+x23+x35=0.8+0.9+2=3.7万元 ; x12+x25 =0.8+2.9=3.7万元 ;2.生产计划与库存管理解：(1)设x1、x2、x3、x4为第一、二、三、四季度生产量，则可以得出第第一、二、三、四季度支出费用为第一季度费用z1：5*x1+(x1-10);第二季度费用z2：5*x2+(x1+x2-24);第三季度费用z3：6*x3+(x1+x2+x3-44);第四季度费用z4：6*x4+(x1+x2+x3+x4-52);总的支出费用为：Z=z1+z2+z3+z4=9x1+8x2+8x3+7x4-130;约束条件为：x1+x2+x3+x4=52;x1=10;x2= 24;x3= 44;x4= 13;可以得出lingo程序如下：min = 9*x1 + 8*x2 + 8*x3 + 7*x4-130;x1+x2+x3+x4=52;x1=10;x2= 24;x3= 44;x4= 13;运行程序后可得： Global optimal solution found. Objective value: 292.0000 Infeasibilities: 0.000000 Total solver iterations: 0 Model Class: LP Total variables: 4 Nonlinear variables: 0 Integer variables: 0 Total constraints: 9 Nonlinear constraints: 0 Total nonzeros: 18 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 14.00000 0.000000 X2 15.00000 0.000000 X3 15.00000 0.000000 X4 8.000000 0.000000 Row Slack or Surplus Dual Price 1 292.0000 -1.000000 2 0.000000 -7.000000 3 0.000000 0.000000 4 4.000000 0.000000 5 0.000000 1.000000 6 5.000000 0.000000 7 0.000000 1.000000 8 0.000000 -2.000000 9 5.000000 0.000000则可得x1=14,x2=15,x3=15,x4=8;即第一季度生产14万盒，第二季度生产15万盒，第三季度15万盒，第四季度为8万盒。总的支出费用为292万元。（2）由题目可得新的lingo程序：min = 7*x1 + 6*x2 + 6*x3 + 6*x4-31;x1+x2+x3+x4=52;x1=10;x2= 24;x3= 43;x4= 13;运行程序之后可得： Global optimal solution found. Objective value: 294.0000 Infeasibilities: 0.000000 Total solver iterations: 0 Model Class: LP Total variables: 4 Nonlinear variables: 0 Integer variables: 0 Total constraints: 9 Nonlinear constraints: 0 Total nonzeros: 18 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 13.00000 0.000000 X2 15.00000 0.000000 X3 15.00000 0.000000 X4 9.000000 0.000000 Row Slack or Surplus Dual Price 1 294.0000 -1.000000 2 0.000000 -6.000000 3 0.000000 0.000000 4 3.000000 0.000000 5 0.000000 1.000000 6 4.000000 0.000000 7 0.000000 1.000000 8 0.000000 -1.000000 9 4.000000 0.000000可得x1=13,x2=15,x3=15,x4=9;即第一季度生产13万盒，第二季度生产15万盒，第三季度15万盒，第四季度为9万盒。总的支出费用为294万元。（3 ） 设第一季度加班生产的产品为x11盒，第一季度加班生产的产品为x21盒，第一季度加班生产的产品为x31盒，第一季度加班生产的产品为x41盒，则可以得到新的lingo程序：min = 8*x1 +9*x11+ 7*x2 + 8*x21+7*x3 +8.2*x31+ 6*x4+7.2*x41-78;x1+x11+x2+x21+x3+x31+x4+x41=52;x1=10;x2= 24;x3= 44;x4= 13;运行程序可得： Global optimal solution found. Objective value: 292.0000 Infeasibilities: 0.000000 Total solver iterations: 2 Model Class: LP Total variables: 8 Nonlinear variables: 0 Integer variables: 0 Total constraints: 9 Nonlinear constraints: 0 Total nonzeros: 32 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 13.00000 0.000000 X11 0.000000 1.000000 X2 15.00000 0.000000 X21 1.000000 0.000000 X3 15.00000 0.000000 X31 0.000000 0.2000000 X4 8.000000 0.000000 X41 0.000000 1.200000 Row Slack or Surplus Dual Price 1 292.0000 -1.000000 2 0.000000 -6.000000 3 0.000000 0.000000 4 3.000000 0.000000 5 0.000000 1.000000 6 5.000000 0.000000 7 0.000000 1.000000 8 0.000000 -2.000000 9 5.000000 0.000000则可以得出新的生产方案为：则可得x1=13, x21=1,x2=15,x3=15,x4=8;即第一季度生产13万盒，第二季度生产15万盒，第二季度加班生产的产品为1万盒，第三季度15万盒，第四季度为8万盒。（4）设第一季度加班生产的产品为x11盒，第一季度加班生产的产品为x21盒，第一季度加班生产的产品为x31盒，第一季度加班生产的产品为x41盒，可以得到新的lingo程序：min = 8*x1 +9*x11+ 7*x2 + 8*x21+7*x3 +8.2*x31+ 6*x4+7.2*x41-77;x1+x11+x2+x21+x3+x31+x4+x41=52;x1=10;x2= 24;x3= 44;x4= 13; Global optimal solution found. Objective value: 293.0000 Infeasibilities: 0.000000 Total solver iterations: 2 Model Class: LP Total variables: 8 Nonlinear variables: 0 Integer variables: 0 Total constraints: 9 Nonlinear constraints: 0 Total nonzeros: 32 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 13.00000 0.000000 X11 0.000000 1.000000 X2 15.00000 0.000000 X21 1.000000 0.000000 X3 15.00000 0.000000 X31 0.000000 0.2000000 X4 8.000000 0.000000 X41 0.000000 1.200000 Row Slack or Surplus Dual Price 1 293.0000 -1.000000 2 0.000000 -6.000000 3 0.000000 0.000000 4 3.000000 0.000000 5 0.000000 1.000000 6 5.000000 0.000000 7 0.000000 1.000000 8 0.000000 -2.000000 9 5.000000 0.0000003.指派问题解： 由此转换问题的解决方案分别为（1）甲(worker1) (worker5)完成两项任务，乙(worker2)丙(worker3)丁(worker4)各完成一项任务；可以得出如下的lingo程序：model:sets:worker/w1.w5/;job/j1.j5/;links(worker,job):c,x;endsetsdata:c=25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 45 25 29 31 42 37;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: 135.0000 Objective bound: 135.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Model Class: PILP Total variables: 25 Nonlinear variables: 0 Integer variables: 25 Total constraints: 11 Nonlinear constraints: 0 Total nonzeros: 75 Nonlinear nonzeros: 0 Variable Value Reduced Cost C( W1, J1) 25.00000 0.000000 C( W1, J2) 29.00000 0.000000 C( W1, J3) 31.00000 0.000000 C( W1, J4) 42.00000 0.000000 C( W1, J5) 37.00000 0.000000 C( W2, J1) 39.00000 0.000000 C( W2, J2) 38.00000 0.000000 C( W2, J3) 26.00000 0.000000 C( W2, J4) 20.00000 0.000000 C( W2, J5) 33.00000 0.000000 C( W3, J1) 34.00000 0.000000 C( W3, J2) 27.00000 0.000000 C( W3, J3) 28.00000 0.000000 C( W3, J4) 40.00000 0.000000 C( W3, J5) 32.00000 0.000000 C( W4, J1) 24.00000 0.000000 C( W4, J2) 42.00000 0.000000 C( W4, J3) 36.00000 0.000000 C( W4, J4) 23.00000 0.000000 C( W4, J5) 45.00000 0.000000 C( W5, J1) 25.00000 0.000000 C( W5, J2) 29.00000 0.000000 C( W5, J3) 31.00000 0.000000 C( W5, J4) 42.00000 0.000000 C( W5, J5) 37.00000 0.000000 X( W1, J1) 0.000000 25.00000 X( W1, J2) 1.000000 29.00000 X( W1, J3) 0.000000 31.00000 X( W1, J4) 0.000000 42.00000 X( W1, J5) 0.000000 37.00000 X( W2, J1) 0.000000 39.00000 X( W2, J2) 0.000000 38.00000 X( W2, J3) 1.000000 26.00000 X( W2, J4) 0.000000 20.00000 X( W2, J5) 0.000000 33.00000 X( W3, J1) 0.000000 34.00000 X( W3, J2) 0.000000 27.00000 X( W3, J3) 0.000000 28.00000 X( W3, J4) 0.000000 40.00000 X( W3, J5) 1.000000 32.00000 X( W4, J1) 0.000000 24.00000 X( W4, J2) 0.000000 42.00000 X( W4, J3) 0.000000 36.00000 X( W4, J4) 1.000000 23.00000 X( W4, J5) 0.000000 45.00000 X( W5, J1) 1.000000 25.00000 X( W5, J2) 0.000000 29.00000 X( W5, J3) 0.000000 31.00000 X( W5, J4) 0.000000 42.00000 X( W5, J5) 0.000000 37.00000 Row Slack or Surplus Dual Price 1 135.0000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000可以得出：甲完成A、B两个任务，乙完成C任务，丙完成E任务，丁完成D任务，花费的时间最短时间为135。（2）乙(worker2) (worker5)完成两项任务，甲(worker1)丙(worker3)丁(worker4)各完成一项任务；可以得出如下的lingo程序：model:sets:worker/w1.w5/;job/j1.j5/;links(worker,job):c,x;endsetsdata:c=25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 45 39 38 26 20 33;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: 131.0000 Objective bound: 131.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Model Class: PILP Total variables: 25 Nonlinear variables: 0 Integer variables: 25 Total constraints: 11 Nonlinear constraints: 0 Total nonzeros: 75 Nonlinear nonzeros: 0 Variable Value Reduced Cost C( W1, J1) 25.00000 0.000000 C( W1, J2) 29.00000 0.000000 C( W1, J