数学实验 9：整数规划

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且1000t部分(t)cost购买原油A所需要的总花销(元)问如何规划投资和生产，实际上就是问如何将利润最大化，根据题目中给出的约束条件建立优化模型的基本形式：其中，约束条件的1、2行为对两种产品含原油A比例的最低限定条件；3、4行的意义是用来制造产品的原料不能大于库存和购买来的原料总量；Cost为总花销；6、7、8行实现了y1、y2、y3的意义。2 程序设计：应用Lingo软件实现以上的程序

3、：max=(a1+b1)*4800+(a2+b2)*5600-cost;0.5*a1-0.5*b10;0.4*a2-0.6*b20;!注意此处需要写成乘法的形势a1+a2-(y1+y2+y3)500;b1+b21000;cost=10000*y1+8000*y2+6000*y3;(y1-500)*y2=0;(y2-500)*y3=0;y1500;y2500;y3500;gin(y1);！整数规划约束，连续规划时不需要gin(y2);gin(y3);gin(a1);gin(a2);gin(b1);gin(b2);gin(cost);end3 运行结果：1）连续规划： Global optimal

4、 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.000000 Y3 0.1490116E-04 0.000000 Row Slack or Surplus Dual Price 1 500

5、0000. 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）整数规划： Global optimal solution found at iteration: 682 Objective val

6、ue: 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 Dual Price 1 5000000. 1.000000 2 0.000000 0.000000 3 0.000000 0.00

7、0000 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的比例混合制造乙产品，最终可以获得最大利润（全局最优解）五百万元。由影子价格Dual Price的数值可以看出约束条件a1+a2-(y1+y2+y3)500;b1+b210

8、00;对结果的影响很大,即原料供应量增长1个单位，理论上可以使得利润增加5600元，实际上，如果把L5约束改为b1+b2=x2=x3=x4,yi为第i种方案是否被采用的零一变量，满足：（2）制造的各种钢管应该至少满足客户的需求：x1*r11+x2*r12+x3*r13+x4*r1415;（3）x1*r21+x2*r22+x3*r23+x4*r2428;x1*r31+x2*r32+x3*r33+x4*r3421;x1*r41+x2*r42+x3*r43+x4*r4430;每一种切割模式必须可行、合理，按题目要求，钢管成品必然不能超过，且余量不能大于，于是有： 1750290*r1i+315*r2

9、i+350*r3i+455*r4i1850;i=1,2,3,4（4）本题还规定了所使用的每种切割模式下最多生产5根产品，有： r1i+r2i+r3i+r4i0,不需要) m=999999;！给出一个充分大的数mx2m*y2;!实现约束条件（2）x3m*y3;x4m*y4;x2x1;x3x2;x4x3;r11+r21+r31+r415;！实现约束条件（5）r12+r22+r32+r425;r13+r23+r33+r435;r14+r24+r34+r445;290*r11+315*r21+350*r31+455*r411850;！实现约束条件(4)，要分开写两个不等式1750290*r11+315

10、*r21+350*r31+455*r41;290*r12+315*r22+350*r32+455*r421850;1750290*r12+315*r22+350*r32+455*r42;290*r13+315*r23+350*r33+455*r431850;1750290*r13+315*r23+350*r33+455*r43;290*r14+315*r24+350*r34+455*r441850;175015;！实现约束条件(3)x1*r21+x2*r22+x3*r23+x4*r2428;x1*r31+x2*r32+x3*r33+x4*r3421;x1*r41+x2*r42+x3*r43+x

11、4*r4430;gin(x1);gin(x2);gin(x3);gin(x4);!非负整数约束gin(r11);gin(r21);gin(r31);gin(r41);gin(r12);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 Re

12、duced Cost X1 9.000000 1.000000 X2 7.000000 1.000000 Y2 1.000000 0.2000000 X3 3.000000 1.000000 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.0000

13、00 0.000000 R32 3.000000 0.000000 R42 1.000000 0.000000 R13 2.000000 0.000000 R23 1.000000 0.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.00

14、0000 3 93.00000 0.000000 4 97.00000 0.000000 5 0.000000 0.4000000E-02 6 2.000000 0.000000 7 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

15、45.00000 0.000000 18 55.00000 0.000000 19 10.00000 0.000000 20 90.00000 0.000000 21 0.000000 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根采用

16、方案二，3根采用方案三，最终可以使得总花销最小为19.6。计算全局最优解所需时间较长，而实际上从计算的过程可以看出，每一步得到的局部最优解都是19.6，因此可以认为以上得到的局部解就是本题的全局最优解。问题：本题设置的0-1变量y2,y3,y4，是通过一个充分大的数M实现和x2,x3,x4之间的关系的。理论上讲，只要M取得足够大，就可以保证：式成立。但事实上，M的取值是会影响到的局部最优解的，比如，M取到900000,得到如下解： Local optimal solution found at iteration: 167527 Objective value: 19.60000 Variab

17、le Value Reduced Cost X1 14.00000 0.3999998 X2 3.000000 0.000000 Y2 1.000000 0.2000000 X3 1.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.0