北京工业大学-数学建模3-线性规划

线性规划 一、 基本实验 1.生产安排 NWAC电力公司为军事承包生产4种类型的电缆。每种电缆必须经过4种相继的操作；拼接、焊接、套管和检查。表3-1给出了该问题相关的数据。承包商保证对于四种电缆的每一种最低产量是100个单位。 表3.1 不同产品的生产时间及收入 电缆 单位分钟数 单位收入（$） 拼接 焊接 套管 检查 SC320 10.5 20.4 3.2 5.0 9.4 SC325 9.3 24.6 2.5 5.0 10.80 SC340 11.6 17.7 3.6 5.0 8.75 SC370 8.2 26.5 5.5 5.0 7.80 日能力（分钟） 4800 9600 4700 4500               （1） 将问题建立成一个线性规划模型，并确定最优的产品进度表。 （2） 基于对偶价格（Dual Price）,你会推荐增加四种操作中的哪一种操作的 能力？试解释。 （3） 对于四种电缆的最低产量要求对NWAC电力公司有利还是不利？试分 析。 解：（1）令x1,x2,x3,x4分别代表四种电缆的产量，目标函数为： Max z = 9.4*x1+10.8*x2+8.75*x3+7.8*x4, 约束条件(s.t)： 10.5*x1+  9.3*x2+11.6*x3+  8.2*x4≤4800, 20.4*x1+ 24.6*x2 +17.7*x3+ 26.5*x4≤9600, 3.2*x1+  2.5*x2+  3.6*x3+ 5.5*x4≤4700, 5.0*x1+  5.0*x2+  5.0*x3+ 5.0*x4≤4500, X1≥100,x2≥100，x3≥100，x4≥100. 相应的LINGO程序为： max =  9.4*x1  +  10.8*x2  +  8.75*x3  +  7.8*x4; 10.5*x1  +  9.3*x2  +  11.6*x3  + 8.2*x4  <=  4800; 20.4*x1  + 24.6*x2 +  17.7*x3  + 26.5*x4  <=  9600; 3.2*x1  +   2.5*x2  +    3.6*x3  + 5.5*x4  <=  4700; 5.0*x1  +  5.0*x2  +    5.0*x3  + 5.0*x4  <=  4500; X1>=100; x2>0; x3>=100; x4>=100; @gin(x1); @gin(x2); @gin(x3); @gin(x4); 所以当SC320生产100根，SC325生产101根，SC340生产137根，SC370生产100根时，产生最大利润，利润为4009.55$。 (2)取消整数限制 从影子价格看到，第三行对应的影子价格为0.494，其他为0或者负数，第三行的限制条件为焊接技术的限制，提高焊接技术能够提高总体收益。提高焊接技术。 （3）从问题（2）中的影子价格可见，6、7、9行对应负值，数量限制制约总收益。如果去掉数量的限制，重新运行LINGO: 分析结果看出，去掉数量限制后，利润提高到4447.7$。因此，对于四种电缆的最低产量要求对NWAC电力公司是不利的。建议去掉最低产量限制。 2.工程进度问题 某城市在未来的五年内将启动四个城市住房改造工程。每项工程有不同的开始时间，工程周期也不一样。表3.2提供这些项目的基本数据。工程1和工程4必须在规定的周期全部完成。必要时，其余的二项工程可以在预算的限制内完成部分。然而，每个工程在它的规定时间内必须至少完成25%。每年底，工程完成的部分立刻入住，并且实现一定比例的收入。例如，如果工程1在第一年完成40%，在第三年完成剩下的60%,在五年计划范围内的相应收入是0.4×50（第二年）+0.4×50（第三年）+（0.4+0.6）×50（第四年）+（0.4+0.6）×50（第五年）=（4×0.4+2×0.6）×50（单位：万元）。试为工程确定最优的时间进度表，使得五年内的总收入达到最大。 表3.2 项目的基本数据   第一年 第二年 第三年 第四年 第五年 总费用 （千万元） 年收入（万元） 工程1 开始   结束     5.0 50 工程2   开始     结束 8.0 70 工程3 开始       结束 15.0 150 工程4     开始 结束   1.2 20 预算（千万元） 3.0 6.0 7.0 7.0 7.0                     解：令xij,i=1,2,3,4,j=1,2,3,4,5,为工程i在j年完成的比例。 则工程1的收益为： 50×x11+50×（x11+x12）+50×（x11+x12+x13）+50×（x11+x12+x13） 工程2的收入： 70×x22+70×（x22+x23）+70×（x22+x23 +x24） 工程3的收入： 150×x31+150×(x31+x32)+150×(x31+x32+x33)+150×（x31+x32+x33+x34） 工程4的收入 20×x43+20×（x43+x44） 目标函数为： Max z=50×x11+50×（x11+x12）+50×（x11+x12+x13）+50×（x11+x12+x13）+70×x22+70×（x22+x23）+70×（x22+x23+x24）+150×x31+150×(x31+x32)+150×(x31+x32+x33)+150×（x31+x32+x33+x34）+20×x43+20×（x43+x44） 约束调教（s.t）: 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， X22+x23+x24+x25≤1， X31+x32+x33+x34+x35≥0.25, X31+x32+x33+x34+x35≤0.25, X43+x44    =1, Xij≥0，i=1,2,3,4,j=1,2,3,4,5. 写成相应的LINGO程序： max= 50*x11+50*(x11+x12)+50*(x11+x12+x13)+50*(x11+x12+x13)+70*x22+ 70*(x22+x23)+70*(x22+x23 +x24)+150*x31+150*(x31+x32) + 150*(x31+x32+x33)+150*(x31+x32+x33+x34)+20*x43+20*(x43+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; X22+x23+x24+x25<=1; X31+x32+x33+x34+x35>=0.25; X31+x32+x33+x34+x35<=0.25; X43+x44    =1; Lingo程序： 运行结果： 由运行结果容易看出第一年应将所有预算投入工程3中（xi1中，只有x31=0.2>0），第二年应将全部预算投入工程3中，第三年应将5000万投入工程1中，1200万投入工程4中,800万投入工程3中，第四年应将1800万投入工程2中，5200万投入工程，第五年应将200万投入工程2中，剩余6800万。 3.投资问题 一个商业主管在两个计划中有投资选择权：计划A保证每1美元的投在在一年后能赚0.70美元，而计划B保证每1美元的投资在两年后能赚3美元。对于计划A，可以按年制定投资规划，而对于计划B，只允许以两年为周期制定投资规划。主管应如何投资100,000美元，使得在3年末的收入达到最大？ 解：                  表 项目A,B投资数额表 项目 第一年投资 第二年投资 第三年初投资 A X11 X12 X13 B X21 X22=0 X23=0         投资计划如上表,xij,i=1,2,j=1,2,3表示项目A,B在第j年的投资数额。 对于第一年投资，需要将所有的资金都投出去（因为第一年只要投出去就有收益）满足：x11 +x21=100,000 第二年的投资资金为：1.7*x1,故1.7*x1=x12+x22, 由于B两年有收益，第二年不应再投资，故1.7*x1=x12。 第三年的投资资金为：1.7*x12+4*x21，由于B两年有收益，第三年初不应再投入，即x23=0。A再投资也收不回，故第三年不再投资。X13=0,x23=0. 第三年末收益为：1.7*x12+4*x21 整理上述得到线性规划问题： Max z= 1.7*x12+4*x21, s.t.        x11 +x21=100,000, 1.7*x11-x12=0, x11≥0，x12≥0,x21≥0. 编写LINGO程序： Max = 1.7*x12+4*x21; x11 +x21=100000; 1.7*x11-x12=0; 有分析结果可知，在第一年将所有数额100,000美金投入到项目B,三年末的收益最大，收益300,000美金，总额达到400,000美元。 4.生产计划与库存问题 某公司已签订了在未来的六、七、八月份生产A、B两种产品的。总的生产能力（用小时表示）每月不同。表3.3给出了本问题的基本数据。对于产品A和产品B，每小时的单位生产率分别是1.25和1.所有的需求必须被满足。然而，后面月份的需求可以从前面的月份的生产来填补。对于任何从本月转到下一月的产品，每件产品A和产品B每月分别发生0.90美元和0.75美元的储存成本。A、B两种产品的单位生产成本分别是30美元和28美元。试为两种产品确定最优的生产计划安排。