《数学实验9：整数规划》.doc

实验 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． 模型建立研究该公司原油的采购和加工过程，需要对两个过程中的各个参数设置变量：a1,a2 A原油分别用来制造甲、乙两种产品的质量(t)b1,b2 B原油分别用来制造甲、乙两种产品的质量(t)y1,y2,y3 购买的A原油质量：y1为<500t部分，y2为>500t且<1000t部分,y3 为>1000t部分(t)cost 购买原油A所需要的总花销(元)问如何规划投资和生产，实际上就是问如何将利润最大化，根据题目中给出的约束条件建立优化模型的基本形式：其中，约束条件的1、2行为对两种产品含原油A比例的最低限定条件；3、4行的意义是用来制造产品的原料不能大于库存和购买来的原料总量；Cost为总花销；6、7、8行实现了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);@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.000000 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）整数规划： 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 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的比例混合制造乙产品，最终可以获得最大利润（全局最优解）五百万元。

由影子价格Dual Price的数值可以看出约束条件a1+a2-(y1+y2+y3)<500;b1+b2<1000;对结果的影响很大,即原料供应量增长1个单位，理论上可以使得利润增加5600元，实际上，如果把L5约束改为b1+b2<1001，目标函数的最大值增加为5004800，并不完全符合影子价格，但是其仍然可以很好的反应目标函数对于各个约束条件的敏感性;；Slack or Surplus给出了松弛（或剩余）变量的值，当该值为0时，表示该约束其作用，可以看到本题的约束条件基本上都是有作用的 比较两种规划方式的区别，可以看到整数规划得到全局最优解所需的迭代次数明显的多于连续规划，这是由整数规划的复杂性决定的习题11： 钢管下料问题：某零售商从钢管厂进货，将钢管按照顾客的要求切割后出售，从钢管厂进货时得到的原料钢管长度是1850mm.现有一客户要15根290mm、28根315mm、21根350mm和30根455mm的钢管为了简化生产过程，规定所使用的切割模式种类不能超过4种，使用频率最高的一种切割模式按照一个原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一个原料钢管价值的2/10增加费用，以此类推，且每种切割模式下最多生产5根产品。

此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100mm，为了使得总费用最小，应该如何下料1.模型建立 钢管下料问题，本题由于可能用到的切割模式很多，若采用枚举法工作量很大，因此按照书上9.1.2的普遍性方法建模 设采用了四种模式切割钢管，第j种模式可以制造。