《5.生产与服务运作管理中的优化问题》由会员分享，可在线阅读，更多相关《5.生产与服务运作管理中的优化问题（160页珍藏版）》请在金锄头文库上搜索。
1、生产与服务运作管理中的优化问题,优化建模与LINDO/LINGO软件,第5章,内容提要,5.1 生产与销售计划问题 5.2 有瓶颈设备的多级生产计划问题 5.3 下料问题 5.4 面试顺序与消防车调度问题 5.5 飞机定位和飞行计划问题,5.1 生产与销售计划问题,5.1.1问题实例,例5.1某公司用两种原油（A和B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过500吨时的单价为10000
2、元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工。,5.1.2建立模型,问题分析安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。,模型建立设原油A的购买量为x（吨），根据题目所给数据， 采购的支出c(x)可表为如下的分段线性函数（以下价格以 千元/吨为单位）：,(1),设原
3、油A用于生产甲、乙两种汽油的数量分别为x11和x12（吨）， 原油B用于生产甲、乙两种汽油的数量分别为x21和x22（吨）， 则总的收入为4.8(x11+x21)+5.6(x12+x22)（千元）。 于是本例的目标函数（利润）为,(2),约束条件包括加工两种汽油用的原油A、原油B库存量的限制， 和原油A购买量的限制，以及两种汽油含原油A的比例限制， 它们表示为,（3）,（4）,（5）,（6）,（7）,（8）,由于（1）式中的c(x)不是线性函数，（1）（8）给出的是 一个非线性规划。而且，对于这样用分段函数定义的c(x)， 一般的非线性规划软件也难以输入和求解。能不能想办法 将该模型化简，从而
4、用现成的软件求解呢？,5.1.3 求解模型,3种解法,第1种解法 将原油A的采购量x分解为三个量，即用x1，x2，x3分别表示以价格10、8、6千元/吨采购的原油A的吨数，总支出为c(x) = 10x1+8x2+6x3，且,(9),这时目标函数（2）变为线性函数：,(10),应该注意到，只有当以10千元/吨的价格购买x1=500（吨）时，才能以8千元/吨的价格购买x2（0），这个条件可以表示为,(11),同理，只有当以8千元/吨的价格购买x2=500（吨）时， 才能以6千元/吨的价格购买x3（0），于是,(12),此外，x1，x2，x3的取值范围是,(13),由于有非线性约束(11),(12)
5、，(3)(13)构成非线性规划模型。LINGO程序：,Model: Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3; x11+x12 0; 0.4*x12 - 0.6*x22 0; x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; bnd(0,x1, 500); bnd(0,x2, 500); bnd(0,x3,500); end,将文件存储并命名为exam0501a.lg4， 执行菜单命令“LINGO|Solve”，运行该程序得到：,Local optimal
6、solution found.Objective value: 4800.000Total solver iterations: 26,Variable Value Reduced CostX11 500.0000 0.000000X21 500.0000 0.000000X12 0.000000 0.000000X22 0.000000 0.000000X1 0.000000 0.000000X2 0.000000 0.000000X3 0.000000 0.000000X 0.000000 0.000000,最优解: 用库存的500吨原油A、500吨原油B生产1000吨汽油甲，不购买新的原
7、油A，利润为4800（千元）,但是此时LINGO得到的结果只是一个局部最优解,可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化（Use Global Solver）选项，然后重新执行菜单命令“LINGO|Solve” , 得到：,Global optimal solution found.Objective value: 5000.002Extended solver steps: 3Total solver iterations: 187,Variable Value Reduced Cost X11 0.000000 0.000000 X21
8、 0.000000 0.000000 X12 1500.000 0.000000 X22 1000.000 0.000000 X1 500.0000 0.000000 X2 499.9990 0.000000 X3 0.9536707E-03 0.000000 X 1000.000 0.000000,此时LINGO得到的结果是一个全局最优解（Global optimal solution）：购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，共生产2500吨汽油乙，利润为5000（千元），高于刚刚得到的局部最优解对应的利润4800（千元）。,第2种解法: 引入0-1变量将（11
9、）和（12）转化为线性约束,令y1=1，y2=1，y3=1分别表示以10千元/吨、8千元/吨、6千元/吨的价格采购原油A，则约束（11）和（12）可以替换为,(14),(15),(16),y1，y2，y3 =0或1,(17),（3）（10），（13）（17）构成混合整数线性规划模型，将它输入LINDO软件：,Max 4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3 st x-x1-x2-x3=0 x11+x12-x0 0.4x12-0.6x220 x1-500y10 x2-500y30 end int y1 int y2 int y3,运行该程序得到： OBJE
10、CTIVE FUNCTION VALUE1) 5000.000VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 1.000000 2200.000000Y3 1.000000 1200.000000X11 0.000000 0.800000X21 0.000000 0.800000X12 1500.000000 0.000000X22 1000.000000 0.000000X1 500.000000 0.000000X2 500.000000 0.000000X3 0.000000 0.400000X 1000.000000 0.000000
11、,这个结果与前面非线性规划模型用全局优化得到的结果相同。,第3种解法 直接处理分段线性函数c(x)。 （1）式表示的函数c(x)如图5-1。,记x轴上的分点为b1=0, b2=500, b3=1000, b4=1500。当x在第1个小区间 b1, b2时，记x= z1b1+z2b2，z1+z2=1，z1, z20, 因为c(x)在b1, b2是线性的，所以c(x)= z1c(b1)+z2c(b2)。同样，当x在第2个小区间 b2, b3时，x= z2b2+z3b3，z2+z3=1，z2, z30, c(x)= z2c(b2)+z3c(b3)。当x在第3个小区间 b3, b4时，x= z3b3+
12、z4b4，z3+z4=1，z3, z40, c(x)= z3c(b3)+z4c(b4)。为了表示x在哪个小区间，引入0-1变量yk(k=1,2,3)，当x在第k个小区间时，yk=1，否则，yk=0。这样, z1, z2, z3, z4, y1, y2, y3应满足,(18),(19),(20),此时x和c(x)可以统一地表示为,（2）（10），（18）（22）也构成一个混合整数线性规划模型，可以用LINDO求解。不过，我们还是将它输入LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的LINGO模型如下：,(22),输入的LINGO模型如下：,M
13、odel: SETS: Points/14/: b, c, y, z; ! 端点数为4，即分段数为3; ENDSETS DATA: b=0 500 1000 1500; c=0 5000 9000 12000; y=,0; ! 增加的虚拟变量y(4)=0; ENDDATA,Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - sum(Points: c*z); x11+x12 0; 0.4*x12 - 0.6*x22 0; sum(Points: b*z)=x; for(Points(i)|i#eq#1: z(i) = y(i); for(Points(i)
14、|i#ne#1: z(i) = y(i-1)+y(i); sum(Points: y)=1; sum(Points: z)=1; for(Points: bin(y); end,求解，得到的结果如下（略去已知参数b和c的显示结果）：Global optimal solution found.Objective value: 5000.000Extended solver steps: 0Total solver iterations: 28,Variable Value Reduced CostX11 0.000000 0.000000X21 0.000000 1.600000X12 1500.000 0.000000X22 1000.000 0.000000X 1000.000 0.000000Y( 1) 0.000000 -4600.000Y( 2) 0.000000 -1200.000Y( 3) 1.000000 0.000000Y( 4) 0.000000 0.000000Z( 1) 0.000000 0.000000Z( 2) 0.000000 0.000000Z( 3) 1.000000 0.000000Z( 4) 0.000000 200.0000,
