《数学实验 9：整数规划.docx》由会员分享，可在线阅读，更多相关《数学实验 9：整数规划.docx（8页珍藏版）》请在三一文库上搜索。
1、.实验 9：整数规划习题9：（原油采购与加工）某公司用两种原油（A和B）混合加工成两种汽油（甲和乙），甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A 和B的库存量分别为500t和1000t，还可以从市场上买到不超过1500T的原油A。原油A的市场价为：购买量不超过500t时单价为10000元/t；购买量超过500t但是不超过1000t时，超过500t的部分8000元/t；购买量超过1000t时，超过1000t的部分6000元/t。该公司应该如何安排原油的采购和加工？用连续规划和证书规划分别求解这个问题。1 模型建立研究该公司原油的采
2、购和加工过程，需要对两个过程中的各个参数设置变量：a1,a2A原油分别用来制造甲、乙两种产品的质量(t)b1,b2B原油分别用来制造甲、乙两种产品的质量(t)y1,y2,y3购买的A原油质量：y1为<500t部分，y2为>500t且<1000t部分,y3为>1000t部分(t)cost购买原油A所需要的总花销(元)问如何规划投资和生产，实际上就是问如何将利润最大化，根据题目中给出的约束条件建立优化模型的基本形式：其中，约束条件的1、2行为对两种产品含原油A比例的最低限定条件；3、4行的意义是用来制造产品的原料不能大于库存和购买来的原料总量；Cost为总花销；6、7、8行
3、实现了y1、y2、y3的意义。2 程序设计：应用Lingo软件实现以上的程序：max=(a1+b1)*4800+(a2+b2)*5600-cost;0.5*a1-0.5*b1>0;0.4*a2-0.6*b2>0;!注意此处需要写成乘法的形势a1+a2-(y1+y2+y3)<500;b1+b2<1000;cost=10000*y1+8000*y2+6000*y3;(y1-500)*y2=0;(y2-500)*y3=0;y1<500;y2<500;y3<500;gin(y1);！整数规划约束，连续规划时不需要gin(y2);gin(y3);gin(a1);
4、gin(a2);gin(b1);gin(b2);gin(cost);end3 运行结果：1）连续规划： Global optimal solution found at iteration: 178 Objective value: 5000000. Variable Value Reduced Cost A1 0.000000 900.0000 B1 0.000000 0.000000 A2 1500.000 0.000000 B2 1000.000 0.000000 COST 9000000. 0.000000 Y1 500.0000 0.000000 Y2 500.0000 0.0000
5、00 Y3 0.1490116E-04 0.000000 Row Slack or Surplus Dual Price 1 5000000. 1.000000 2 0.000000 -2600.000 3 0.000000 -3500.000 4 0.000000 7000.000 5 0.000000 3500.000 6 0.000000 -1.000000 7 0.000000 -6.000000 8 0.000000 -0.6710886E+08 9 0.000000 0.000000 10 0.1490116E-04 0.000000 11 500.0000 0.0000002）整
6、数规划： Global optimal solution found at iteration: 682 Objective value: 5000000. Variable Value Reduced Cost A1 0.000000 800.0000 B1 0.000000 800.0000 A2 1500.000 0.000000 B2 1000.000 0.000000 COST 9000000. 0.3000000 Y1 500.0000 0.000000 Y2 500.0000 0.000000 Y3 0.000000 -1400.000 Row Slack or Surplus
7、Dual Price 1 5000000. 1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 5600.000 5 0.000000 5600.000 6 0.000000 -0.7000000 7 0.000000 -2.800000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 500.0000 0.000000两种方法最终得到的都是同样的最优解，即：购买1000tA原油，将全部的原料按A:B=3:2的比例混合制造乙产品，最终可以获得最大利
8、润（全局最优解）五百万元。由影子价格Dual Price的数值可以看出约束条件a1+a2-(y1+y2+y3)<500;b1+b2<1000;对结果的影响很大,即原料供应量增长1个单位，理论上可以使得利润增加5600元，实际上，如果把L5约束改为b1+b2<1001，目标函数的最大值增加为5004800，并不完全符合影子价格，但是其仍然可以很好的反应目标函数对于各个约束条件的敏感性;；Slack or Surplus给出了松弛（或剩余）变量的值，当该值为0时，表示该约束其作用，可以看到本题的约束条件基本上都是有作用的。比较两种规划方式的区别，可以看到整数规划得到全局最优解所需
9、的迭代次数明显的多于连续规划，这是由整数规划的复杂性决定的。习题11：钢管下料问题：某零售商从钢管厂进货，将钢管按照顾客的要求切割后出售，从钢管厂进货时得到的原料钢管长度是1850mm.现有一客户要15根290mm、28根315mm、21根350mm和30根455mm的钢管。为了简化生产过程，规定所使用的切割模式种类不能超过4种，使用频率最高的一种切割模式按照一个原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一个原料钢管价值的2/10增加费用，以此类推，且每种切割模式下最多生产5根产品。此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100mm，为了使得总费用最小，应该如何
10、下料。1.模型建立钢管下料问题，本题由于可能用到的切割模式很多，若采用枚举法工作量很大，因此按照书上9.1.2的普遍性方法建模设采用了四种模式切割钢管，第j种模式可以制造第i种钢管(按题目顺序)的数量为rij，xi表示采用第i种模式切割的原料钢管数。以总费用最小为目标，由于没有给出每中方案的具体花费，所以将使用原料钢管总根数等价于花费，并且需要考虑切割模式的花费：min x1+x2+x3+x4+0.1*y1+0.2*y2+0.3*y3+0.4*y4（1）不妨设,x1>=x2>=x3>=x4,yi为第i种方案是否被采用的零一变量，满足：（2）制造的各种钢管应该至少满足客户的需求
11、：x1*r11+x2*r12+x3*r13+x4*r14>15;（3）x1*r21+x2*r22+x3*r23+x4*r24>28;x1*r31+x2*r32+x3*r33+x4*r34>21;x1*r41+x2*r42+x3*r43+x4*r44>30;每一种切割模式必须可行、合理，按题目要求，钢管成品必然不能超过，且余量不能大于，于是有： 1750<290*r1i+315*r2i+350*r3i+455*r4i<1850;i=1,2,3,4（4）本题还规定了所使用的每种切割模式下最多生产5根产品，有： r1i+r2i+r3i+r4i<5;i=1,2
12、,3,4（5）最后，需要对之前用到的所有参数进行非负整数约束。综合1到5式便得到了本题完整的规划模型。2.程序设计min=x1+0.1+x2+0.2*y2+x3+0.3*y3+x4+0.4*y4;bin(y2);bin(y3);bin(y4);!设置0-1变量(x1必然>0,不需要) m=999999;！给出一个充分大的数mx2<m*y2;!实现约束条件（2）x3<m*y3;x4<m*y4;x2<x1;x3<x2;x4<x3;r11+r21+r31+r41<5;！实现约束条件（5）r12+r22+r32+r42<5;r13+r23+r33+
13、r43<5;r14+r24+r34+r44<5;290*r11+315*r21+350*r31+455*r41<1850;！实现约束条件(4)，要分开写两个不等式1750<290*r11+315*r21+350*r31+455*r41;290*r12+315*r22+350*r32+455*r42<1850;1750<290*r12+315*r22+350*r32+455*r42;290*r13+315*r23+350*r33+455*r43<1850;1750<290*r13+315*r23+350*r33+455*r43;290*r14+31
14、5*r24+350*r34+455*r44<1850;1750<290*r14+315*r24+350*r34+455*r44;x1*r11+x2*r12+x3*r13+x4*r14>15;！实现约束条件(3)x1*r21+x2*r22+x3*r23+x4*r24>28;x1*r31+x2*r32+x3*r33+x4*r34>21;x1*r41+x2*r42+x3*r43+x4*r44>30;gin(x1);gin(x2);gin(x3);gin(x4);!非负整数约束gin(r11);gin(r21);gin(r31);gin(r41);gin(r12);
15、gin(r22);gin(r32);gin(r42);gin(r13);gin(r23);gin(r33);gin(r43);gin(r14);gin(r24);gin(r34);gin(r44);end3.运行结果局部最优解： Local optimal solution found at iteration: 138258 Objective value: 19.60000 Variable Value Reduced Cost X1 9.000000 1.000000 X2 7.000000 1.000000 Y2 1.000000 0.2000000 X3 3.000000 1.000
16、000 Y3 1.000000 0.3000000 X4 0.000000 1.004000 Y4 0.000000 0.000000 M 100.0000 0.000000 R11 1.000000 0.000000 R21 2.000000 0.000000 R31 0.000000 0.000000 R41 2.000000 0.000000 R12 0.000000 0.000000 R22 1.000000 0.000000 R32 3.000000 0.000000 R42 1.000000 0.000000 R13 2.000000 0.000000 R23 1.000000 0
17、.000000 R33 0.000000 0.000000 R43 2.000000 0.000000 R14 2.000000 0.000000 R24 0.000000 0.000000 R34 1.000000 0.000000 R44 2.000000 0.000000 Row Slack or Surplus Dual Price 1 19.60000 -1.000000 2 0.000000 0.000000 3 93.00000 0.000000 4 97.00000 0.000000 5 0.000000 0.4000000E-02 6 2.000000 0.000000 7
18、4.000000 0.000000 8 3.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 20.00000 0.000000 14 80.00000 0.000000 15 30.00000 0.000000 16 70.00000 0.000000 17 45.00000 0.000000 18 55.00000 0.000000 19 10.00000 0.000000 20 90.00000 0.000000 21 0.000000
19、 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 1.000000 0.000000以上解的实际意义如下：采用三种切割方案，分别为：方案一：切割290mm、315mm、350mm和455mm种钢管的根数分别为：1，2，0，2方案二：切割四种钢管的根数分别为：0，1，3，1方案三：切割四种钢管的根数分别为：2，1，0，29根原料钢管采用方案一切割，7根采用方案二，3根采用方案三，最终可以使得总花销最小为19.6。计算全局最优解所需时间较长，而实际上从计算的过程可以看出，每一步得到的局部最优解都是19.6，因此可以认为以上得到的局部解就是
20、本题的全局最优解。问题：本题设置的0-1变量y2,y3,y4，是通过一个充分大的数M实现和x2,x3,x4之间的关系的。理论上讲，只要M取得足够大，就可以保证：式成立。但事实上，M的取值是会影响到的局部最优解的，比如，M取到900000,得到如下解： Local optimal solution found at iteration: 167527 Objective value: 19.60000 Variable Value Reduced Cost X1 14.00000 0.3999998 X2 3.000000 0.000000 Y2 1.000000 0.2000000 X3 1.
21、000000 0.1999998 Y3 1.000000 0.3000000 X4 1.000000 0.4450831E-06 Y4 0.1111111E-05 0.000000 M 900000.0 0.000000 R11 1.000000 0.000000 R21 2.000000 2.800000 R31 0.000000 0.000000 R41 2.000000 0.000000 R12 0.000000 0.000000 R22 0.000000 0.5999999 R32 5.000000 0.000000 R42 0.000000 0.000000 R13 0.000000 0.000000 R23 1.000000 0.1999998 R33 3.000000 0.000000 R43 1.000000 0.000000 R14 1.000000 0.000000 R24 0.000000 0.1999998 R34 3.000000 0.000000 R44 1.000000 0.000000最终得到的解仍然是19.6,但是对应的取值办法已经改变，采用了4种切割方案，具体结果不再重复。注意到红色标记的Y4并不满足0-1变量，而是一个非零的微小量，可以看出这个结果最终对结果没有影响，仍然按0计算，但是不理解为什么会得到不满足约束的0-1变量。.;