北京工业大学薛毅老师工程数据建模实验2线性规划和整数规划.docVIP

2. 线性规划和整数规划实验2.1 基本实验1. 生产计划安排某工厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见表2.1所示。表2.1 不同产品的消耗定额资源产 品可用量（单位）ABC劳动力63545材料34530产品利润（元/件）314（1）确定获利最大的生产方案；（2）产品A、B、C的利润分别在什么范围内变动时，上述最优方案不变；（3）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，以购多少为宜？（4）如果生产一种新产品D，单件劳动力消耗8个单位，材料消耗2个单位，每件可获利3元，问该种产品是否值得生产？解答： （1）LINGO中程序：max = 3*x1 +x2+ 4*x3;6*x1 + 3*x2+5*x3 = 45;3*x1 + 4*x2+5*x3 = 30;end程序运行结果如下：Global optimal solution found. Objective value: 27.00000 Total solver iterations: 2 Variable Value Reduced Cost X1 5.000000 0.000000 X2 0.000000 2.000000 X3 3.000000 0.000000 Row Slack or Surplus Dual Price 1 27.00000 1.000000 2 0.000000 0.2000000 3 0.000000 0.6000000获利最大的生产方案为：生产A产品5件，B产品0件，C产品3件，获利为27。（2）产品A利润在2.4-4.8元之间变动,最优生产计划不变。（3）运行程序LINGO中程序：max=3*x1+x2+4*x3;6*x1+3*x2+5*x345;end程序运行结果如下：Global optimal solution found. Objective value: 36.00000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 1.800000 X2 0.000000 1.400000 X3 9.000000 0.000000 Row Slack or Surplus Dual Price 1 36.00000 1.000000 2 0.000000 0.8000000从程序运行结果可得到：当A、B为0，而C 9件时利润最大,最大利润为36元,应该购入原材料扩大生产,购入15个单位。（4）设D产品为x4，则有：max 3x1+x2+4x3+3x4s.t6x1+3x2+5x3+8x445 3x1+4x2+5x3+2x430 X10，x20，x30，x40LINGO中程序：max = 3*x1 +x2+ 4*x3+3*x4;6*x1 + 3*x2+5*x3 +8*x4= 45;3*x1 + 4*x2+5*x3 +2*x4= 30;gin(x1);gin(x2);gin(x3);gin(x4);end程序运行结果如下： Global optimal solution found. Objective value: 27.00000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 5.000000 -3.000000 X2 0.000000 -1.000000 X3 3.000000 -4.000000 X4 0.000000 -3.000000 Row Slack or Surplus Dual Price 1 27.00000 1.000000 2 0.000000 0.000000 3 0.000000 0.000000从上表程序运行结果来看，产品D不值得生产。2. 工程进度问题某城市在未来的五年内将启动四个城市住房改造工程，每项工程有不同的开始时间，工程周期也不一样。表2.2提供这些项目的基本数据。表2.2 项目的基本数据第一年第二年第三年第四年第五年总费用（千万元）年收入（万元）工程1开始结束5.050工程2开始结束8.070工程3开始结束15.0150工程4开始结束1.220预算（千万元）3.06.07.07.07.0过程1和过程4必须在规定的周期内全部完成。必要时，其余的二项工程可以在预算的限制内完成部分。然而，每个工程在它的规定时间内必须至少完成25%。每年底，工程完成的部分立刻入住，并且实现一定比例的收入。例如，如果工程1在第一年完成40%，在第三年完成剩下的60%，在五年计划范围内的相应收入是0.450（第二年）+0.450（第三年）+(0.4+0.6)50（第五年）=(40.4+20.6)50（单位：万元）。试为工程确定最优的时间进度表，使得五年内的总收入达到最大。解答：设某一年某工程的完成量为Xij，i表示工程的代号，i=1，2，3，如第一年工程1完成X11，工程3完成X31，到第二年工程已完成X12，工程3完成X32。另有一个投入与完成的关系，既第一年投入总费用的40%，该工程在年底就完成40%。工程1-4的利润满足以下约束工程1的利润： 50X11+50X11+X12+50X11+X12+X13+50X11+X12+X13工程2的利润： 70X11+70X22+X23+70X22+X23+X24；工程3 的利润：150X31+150X31+X32+150X31+X32+X33+150X31+X32+X33+X34；工程4的利润：20X43+20X43+X44LINGO中程序：max=50*(4*X11+3*X12+2*X13) +70*(3*X22+2*X23+1*X24)+150*(4*X31+3*X32+2*X33+1*X34)+20*(2*X43+1*X44);5000*X11+15000*X31=3000;5000*X12+8000*X22+15000*X32=6000;5000*X13+8000*X23+15000*X33+1200*X43=7000;8000*X24+15000*X34+1200*X44=7000;8000*X25+15000*X35=7000;X11+X12+X13=1;X22+X23+X24+X25=0.25;X31+X32+X33+X34+X35=0.25;X43+X44=1;end程序运行结果如下： Global optimal solution found. Objective value: 523.7500 Total solver iterations: 9 Variable Value Reduced Cost X11 0.000000 0.000000 X12 0.000000 0.000000 X13 1.000000 0.000000 X22 0.000000 20.00000 X23 0.000000 10.00000 X24 0.2250000 0.000000 X31 0.2000000 0.000000 X32 0.4000000 0.000000 X33 0.5333333E-01 0.000000 X34 0.3466667 0.000000 X43 1.000000 0.000000 X44 0.000000 8.000000 X25 0.2500000E-01 0.000000 X35 0.000000 18.75000 Row Slack or Surplus Dual Price 1 523.7500 1.000000 2 0.000000 0.3875000E-01 3 0.000000 0.2875000E-01 4 0.000000 0.1875000E-01 5 0.000000 0.8750000E-02 6 6800.000 0.000000 7 0.000000 6.250000 8 0.7500000 0.000000 9 0.000000 0.000000 10 0.000000 18.75000 11 0.7500000 0.000000 12 0.000000 17.50000程序运行结果分析：第一年投资3000万元在工程3上；第二年在工程3上投入6000万元；第三年在工程1上投资5000万元，工程4上投入1200万元，工程3上投入800万元；第四年投入1800万元在工程1上，投入5200万元在工程3上；第五年工程2投入200万元，剩余6800万元。获得最高收入523.75万元。3. 投资问题假设投资者有如下四个投资机会。（A）在三年内，投资人应在每年的年初投资，每年每元投资可获利息0.2元，每年取息后可重新将本息投入生息。（B）在三年内，投资人应在第一年年初投资，每两年每元投资可获利息0.5元.两年后取息，可重新将本息投入生息.这种投资最多不得超过20万元。（C）在三年内，投资人应在第二年年初投资，两年后每元可获利息0.6元，这种投资最多不得超过15万元。（D）在三年内，投资人应在第三年年初投资，一年内每元可获利息0.4元，这种投资不得超过10万元。假定在这三年为一期的投资中，每期的开始有30万元的资金可供投资，投资人应怎样决定投资计划，才能在第三年底获得最高的收益。解答：分析题意设XiA，XiB，XiC，XiD（i=1,2,3）表示第i年初对投资机会A，B，C，D的投资金额，则max 1.23A+1.62C+1.43Ds.t. X1A+X1B=30 1.2X1A=X2A+X2C X3B+X3A+X3D=1.2X2A+1.5X1B X3B20 X2C15 X3D10LINGO中程序：max=1.2*X3a+1.6*X2c+1.4*X3d; X1a+X1b=30; X2a+X2c-1.2*X1a=0; X3b+X3a+X3d-1.2*X2a-1.5*X1b=0; bnd(0,X1b,20); bnd(0,X2c,15); bnd(0,X3d,10);End程序运行结果如下： Global optimal solution found. Objective value: 57.50000 Total solver iterations: 2 Variable Value Reduced Cost X3A 16.25000 0.000000 X2C 15.00000 -0.1000000 X3D 10.00000 -0.2000000 X1A 12.50000 0.000000 X1B 17.50000 0.000000 X2A 0.000000 0.6000000E-01 X3B 0.000000 1.200000 Row Slack or Surplus Dual Price 1 57.50000 1.000000 2 0.000000 1.800000 3 0.000000 1.500000 4 0.000000 1.200000结果分析：第一年投投资12.5万元在A上，投资17.5万元在B上；第二年投资15万元在机会C上；第三年投资16.25万元在机会A上，投资10万元在机会D上，获得最高收益57.5万元。4. 生产计划与库存问题某产品的制造过程由前后两道工序和组成。表2.3提供了在未来68月份的相关数据。表2.3 未来三个月的相关数据月 份六月七月八月成品的需求（件）500450600工序的能力（小时）800700550工序的能力（小时）1000850700生产一件的产品在工序上花0.6小时，在工序另外花0.8小时。在任何一个月过剩的产品（可以是半成品（工序），也可以是产品（工序）允许在后面的月中使用。相应的贮存成本是每年每月1.00元和2.00元。生产成本随工序和随月份变化。对于工序，单位生产成本在六、七、八月份分别为50元、60元和55元。对于工序，相应的单位生产费用分别为75元、90元和80元。确定这两道工序在未来的三个月内最优的生产进度安排。解答：令X1为工序在六月的生产时间，令X2为工序在七月的生产时间，令X3为工序在八月的生产时间；令Y1为工序在六月的生产时间，令Y2为工序在七月的生产时间，令Y3为工序在八月的生产时间；令Z1为半成品（工序）在七月的储存数量，令Z2为半成品（工序）在八月的储存数量，令Z3为半成品（工序）在七月的储存数量，令Z4为半成品（工序）在八月的储存数量。LINGO中程序：min=x1*50+x2*60+x3*55+y1*75+y2*90+y3*80+z1*1+z2*1+z3*2+z4*2;x1800;x2700;x3550;y11000;y2850;y3=950;x1/0.6+x2/0.6+x3/0.6=1550;y1/0.8=500;z3+y2/0.8=450;z4+y3/0.8=600;z1=x1/0.6-y1/0.8;z3=y1/0.8-500;z2=z1+x2/0.6-y2/0.8;z4=z3+y2/0.8-450;gin(x1);gin(x2);gin(x3);gin(y1);gin(y2);gin(y3);gin(z1);gin(z2);gin(z3);gin(z4);程序运行结果如下： Global optimal solution found. Objective value: 143620.0 Extended solver steps: 0 Total solver iterations: 12 Variable Value Reduced Cost X1 798.0000 50.00000 X2 0.000000 60.00000 X3 132.0000 55.00000 Y1 1000.000 75.00000 Y2 0.000000 90.00000 Y3 240.0000 80.00000 Z1 80.00000 1.000000 Z2 80.00000 1.000000 Z3 750.0000 2.000000 Z4 300.0000 2.000000 Row Slack or Surplus Dual Price 1 143620.0 -1.000000 2 2.000000 0.000000 3 700.0000 0.000000 4 418.0000 0.000000 5 0.000000 0.000000 6 850.0000 0.000000 7 460.0000 0.000000 8 380.0000 0.000000 9 0.000000 0.000000 10 750.0000 0.000000 11 300.0000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000根据上述程序分析，两道工序在未来的三个月内最优的生产进度安排为：工序在六、七、八月的生产时间为：798、0、132，工序在六、七、八月的生产时间为：1000、0、240，半成品（工序）在七月份的储存数量为80，半成品（工序）在七月份的储存数量为80，半成品（工序）在七月份的储存数量为750，半成品（工序）在七月份的储存数量为300。三个月最小生产成本为143620元。5. 职员日程安排问题（1）在一个星期里每天安排一定数量的职员，每天需要的职员数如表2.4所示，每个职员每周连续工作五天，休息两天。每天付给每个职员的工资是200元。公司将如何安排每天开始的工作人数，使得总费用最小。（2）假设公司每天工作8小时，周一需要18名职员，共计144小时，以此类推。公司计划雇用全职人员和兼职人员完成公司的工作，其中全职人员每天工作8小时，兼职人员每天工作4小时，无论是全职人员还是兼职人员，均是每周连续工作5天，休息两天。全职人员每小时工资25元，兼职人员每小时工资15元，并且一周内兼职人员的总工作时间不能超过全职人员总工作时间的25%，试问该公司将如何安排职员的工作时间，使公司的总花费最小？表2.4 一周中每天需要的职员数星期一二三四五六日职员数18151216191412解答：（1）LINGO中程序：min =x1+x2+x3+x4+x5+x6+x7;x1 +x4+x5+x6+x7=18;x1+x2 +x5+x6+x7=15 ;x1+x2+x3 +x6+x7=12;x1+x2+x3+x4 +x7=16;x1+x2+x3+x4+x5 =19;x2+x3+x4+x5+x6 =14;x3+x4+x5+x6+x7=12;gin(x1);gin(y1);gin(x2);gin(y2);gin(x3);gin(y3);gin(x4);gin(y4);gin(x5);gin(y5);gin(x6);gin(y6);gin(x7);gin(y7);程序运行结果如下： Objective value: 22.00000 Extended solver steps: 0 Total solver iterations: 8 Variable Value Reduced Cost X1 7.000000 1.000000 X2 2.000000 1.000000 X3 0.000000 1.000000 X4 6.000000 1.000000 X5 4.000000 1.000000 X6 2.000000 1.000000 X7 1.000000 1.000000 Y1 0.000000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 Y5 0.000000 0.000000 Y6 0.000000 0.000000 Y7 0.000000 0.000000 Row Slack or Surplus Dual Price 1 22.00000 -1.000000 2 2.000000 0.000000 3 1.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 1.000000 0.000000公司按如下表来安排每天开始工作的职员：星期一二三四五六日职员数7206421（2）LINGO中程序：min=1000*x1+300*y1+1000*x2+300*y2+1000*x3+300*y3+1000*x4+300*y4+1000*x5+300*y5+1000*x6+300*y6+1000*x7+300*y7;x4+x5+x6+x7+x1+y4+y5+y6+y7+y118;x5+x6+x7+x1+x2+y5+y6+y7+y1+y215;x6+x7+x1+x2+x3+y6+y7+y1+y2+y312;x7+x1+x2+x3+x4+y7+y1+y2+y3+y416;x1+x2+x3+x4+x5+y1+y2+y3+y4+y519;x2+x3+x4+x5+x6+y2+y3+y4+y5+y614;x3+x4+x5+x6+x7+y3+y4+y5+y6+y712;8*x4+8*x5+8*x6+8*x7+8*x1+4*y4+4*y5+4*y6+4*y7+4*y1144;8*x5+8*x6+8*x7+8*x1+8*x2+4*y5+4*y6+4*y7+4*y1+4*y2120;8*x6+8*x7+8*x1+8*x2+8*x3+4*y6+4*y7+4*y1+4*y2+4*y396;8*x7+8*x1+8*x2+8*x3