优化建模与LINGO第05章

优化建模,*,*,第,*,页,生产与服务运作管理中的优化问题,优化建模与LINDO/LINGO软件,第5章,内容提要,5.1 生产与销售计划问题,5.2 有瓶颈设备的多级生产计划问题,5.3 下料问题,5.4 面试顺序与消防车调度问题,5.5 飞机定位和飞行计划问题,5.1 生产与销售计划问题,问题实例,例,5.1,某公司用两种原油（,A,和,B,）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油,A,的最低比例分别为,50%,和,60%,，每吨售价分别为,4800,元和,5600,元。该公司现有原油,A,和,B,的库存量分别为,500,吨和,1000,吨，还可以从市场上买到不超过,1500,吨的原油,A,。原油,A,的市场价为：购买量不超过,500,吨时的单价为,10000,元,/,吨；购买量超过,500,吨但不超过,1000,吨时，超过,500,吨的部分,8000,元,/,吨；购买量超过,1000,吨时，超过,1000,吨的部分,6000,元,/,吨。该公司应如何安排原油的采购和加工。,5.1.2建立模型,问题分析,安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。,模型建立设原油A的购买量为x（吨），根据题目所给数据，,采购的支出c(x)可表为如下的分段线性函数（以下价格以,千元/吨为单位）：,(1),设原油A用于生产甲、乙两种汽油的数量分别为,x,11,和,x,12,（吨），,原油B用于生产甲、乙两种汽油的数量分别为,x,21,和,x,22,（吨），,则总的收入为4.8(,x,11,+,x,21,)+5.6(,x,12,+,x,22,)（千元）。,于是本例的目标函数（利润）为,(2),约束条件包括加工两种汽油用的原油A、原油B库存量的限制，,和原油A购买量的限制，以及两种汽油含原油A的比例限制，,它们表示为,（3）,（4）,（5）,（6）,（7）,（8）,由于（1）式中的,c,(,x,)不是线性函数，（1）（8）给出的是,一个非线性规划。而且，对于这样用分段函数定义的,c,(,x,)，,一般的非线性规划软件也难以输入和求解。能不能想办法,将该模型化简，从而用现成的软件求解呢？,5.1.3 求解模型,3种解法,第1种解法,将原油A的采购量,x,分解为三个量，即用,x,1,，,x,2,，,x,3,分别表示以价格10、8、6千元/吨采购的原油A的吨数，总支出为,c,(,x,)=10,x,1,+8,x,2,+6,x,3,，且,(9),这时目标函数（2）变为线性函数：,(10),应该注意到，只有当以10千元/吨的价格购买,x,1,=500（吨）时，才能以8千元/吨的价格购买,x,2,（0），这个条件可以表示为,(11),同理，只有当以8千元/吨的价格购买,x,2,=500（吨）时，,才能以6千元/吨的价格购买,x,3,（0），于是,(12),此外，,x,1,，,x,2,，,x,3,的取值范围是,(13),由于有非线性约束(11),(12)，(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 x+500;,x21+x22 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 solution found.,Objective value:4800.000,Total solver iterations:26,Variable Value Reduced Cost,X11 500.0000 0.000000,X21 500.0000 0.000000,X12 0.000000 0.000000,X22 0.000000 0.000000,X1 0.000000 0.000000,X2 0.000000 0.000000,X3 0.000000 0.000000,X 0.000000 0.000000,最优解:用库存的500吨原油A、500吨原油B生产1000吨汽油甲，不购买新的原油A，利润为4800（千元）,但是此时LINGO得到的结果只是一个,局部最优解,可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化（Use Global Solver）选项，然后重新执行菜单命令“LINGO|Solve”,得到：,Global optimal solution found.,Objective value:5000.002,Extended solver steps:3,Total solver iterations:187,Variable Value Reduced Cost,X11 0.000000 0.000000,X21 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）和（12）转化为线性约束,令,y,1,=1，,y,2,=1，,y,3,=1分别表示以10千元/吨、8千元/吨、6千元/吨的价格采购原油A，则约束（11）和（12）可以替换为,(14),(15),(16),y,1,，,y,2,，,y,3,=0或1,(17),（3）（10），（13）（17）构成混合整数线性规划模型，将它输入LINDO软件：,Max 4.8x11+4.8x21+5.6x12+5.6x22-10 x1-8x2-6x3,st,x-x1-x2-x3=0,x11+x12-x500,x21+x220,0.4x12-0.6x220,x1-500y10,x2-500y20,x3-500y30,x2-500y30,end,int y1,int y2,int y3,运行该程序得到,：,OBJECTIVE FUNCTION VALUE,1)5000.000,VARIABLE VALUE REDUCED COST,Y1 1.000000 0.000000,Y2 1.000000 2200.000000,Y3 1.000000 1200.000000,X11 0.000000 0.800000,X21 0.000000 0.800000,X12 1500.000000 0.000000,X22 1000.000000 0.000000,X1 500.000000 0.000000,X2 500.000000 0.000000,X3 0.000000 0.400000,X 1000.000000 0.000000,这个结果与前面非线性规划模型用全局优化得到的结果相同。,第3种解法,直接处理分段线性函数,c,(,x,)。,（1）式表示的函数,c,(,x,)如图5-1。,c,(,x,),x,12000,9000,5000,0,500,1000,1500,图5-1 分段线性函数,c,(,x,)图形,记,x,轴上的分点为,b,1,=0,b,2,=500,b,3,=1000,b,4,=1500。当,x,在第1个小区间,b,1,b,2,时，记,x,=,z,1,b,1,+,z,2,b,2,，,z,1,+,z,2,=1，,z,1,z,2,0,因为,c,(,x,)在,b,1,b,2,是线性的，所以,c,(,x,)=,z,1,c,(,b,1,)+,z,2,c,(,b,2,)。同样，当,x,在第2个小区间,b,2,b,3,时，,x,=,z,2,b,2,+,z,3,b,3,，,z,2,+,z,3,=1，,z,2,z,3,0,c,(,x,)=,z,2,c,(,b,2,)+,z,3,c,(,b,3,)。当,x,在第3个小区间,b,3,b,4,时，,x,=,z,3,b,3,+,z,4,b,4,，,z,3,+,z,4,=1，,z,3,z,4,0,c,(,x,)=,z,3,c,(,b,3,)+,z,4,c,(,b,4,)。为了表示,x,在哪个小区间，引入0-1变量,y,k,(,k,=1,2,3)，当,x,在第,k,个小区间时，,y,k,=1，否则，,y,k,=0。这样,z,1,z,2,z,3,z,4,y,1,y,2,y,3,应满足,(18),(19),(20),此时,x,和,c,(,x,)可以统一地表示为,（2）（10），（18）（22）也构成一个混合整数线性规划模型，可以用LINDO求解。不过，我们还是将它输入LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的LINGO模型如下：,(22),输入的LINGO模型如下：,Model:,SETS:,Points/1.4/: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 x+500;,x21+x22 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)|i#ne#1:z(i)0时取值1,否则取值0.,在上述数学符号中，只有,为决策变量,;,其余均为已知的计划参数。,目标函数,这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项目在每个时段上的生产准备费用和库存费用的总和，即,(28),约束条件,这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束（对,Y,i,j,是0-1约束）。,(29),资源能力限制比较容易理解，即,(30),所谓物流守恒（假设,I,i,0,=0）,(31),每时段生产某项目前必须经过生产准备，也就是说当,X,it,=0时,Y,it,=0；,X,it,0时,Y,it,=1。这本来是一个非线性约束，但是通过引入参数,M,（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：,总结:这个问题的优化模型就是在约束（29）（30）（31）下使目标函数（28）达到最小。,5.2.3 求解模型,本例生产项目总数,N,=7(A、B、C、D、E、F、G)，计划期长度,T,=6（周），瓶颈资源种类数,K,=1。只有A有外部需求，所以,d,i,t,中只有,d,1,t,可以取非零需求，即表5-1中的第2行的数据，其他全部为零。参数,s,i,t,、,h,i,t,只与项目,i,有关，而不随时段,t,变化，所以可以略去下标,t,，其数值就是表5-1中的最后两行数据。,由于只有一种资源，参数,C,k,t,可以略去下标,k,，其数值就是表5-1中的第3行的数据；而,a,k,I,t,只与项目