优化建模与LINGO第05章.ppt

优化建模优化建模生产与服务运作管理中的优化问题生产与服务运作管理中的优化问题优化建模与优化建模与LINDO/LINGOLINDO/LINGO软件软件第第5 5章章 优化建模优化建模内容提要内容提要5.1 5.1 生产与销售计划问题生产与销售计划问题5.2 5.2 有瓶颈设备的多级生产计划问题有瓶颈设备的多级生产计划问题5.3 5.3 下料问题下料问题5.4 5.4 面试顺序与消防车调度问题面试顺序与消防车调度问题5.5 5.5 飞机定位和飞行计划问题飞机定位和飞行计划问题 优化建模优化建模5.1 生产与销售计划问题生产与销售计划问题 优化建模优化建模问题实例问题实例例例5.15.1某公司用两种原油（某公司用两种原油（A A和和B B）混合加工成两种）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油汽油（甲和乙）。甲、乙两种汽油含原油A A的最低的最低比例分别为比例分别为50%50%和和60%60%，每吨售价分别为，每吨售价分别为48004800元和元和56005600元。该公司现有原油元。该公司现有原油A A和和B B的库存量分别为的库存量分别为500500吨和吨和10001000吨，还可以从市场上买到不超过吨，还可以从市场上买到不超过15001500吨吨的原油的原油A A。原油。原油A A的市场价为：购买量不超过的市场价为：购买量不超过500500吨吨时的单价为时的单价为1000010000元元/吨；购买量超过吨；购买量超过500500吨但不超吨但不超过过10001000吨时，超过吨时，超过500500吨的部分吨的部分80008000元元/吨；购买吨；购买量超过量超过10001000吨时，超过吨时，超过10001000吨的部分吨的部分60006000元元/吨。吨。该公司应如何安排原油的采购和加工。该公司应如何安排原油的采购和加工。优化建模优化建模5.1.25.1.2建立模型建立模型问题分析问题分析 安排原油采购、加工的目标是利润最大，题目中给安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油出的是两种汽油的售价和原油A A的采购价，利润为的采购价，利润为销售汽油的收入与购买原油销售汽油的收入与购买原油A A的支出之差。这里的的支出之差。这里的难点在于原油难点在于原油A A的采购价与购买量的关系比较复杂，的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。划模型加以处理是关键所在。优化建模优化建模模型建立设原油模型建立设原油A A的购买量为的购买量为x x（吨），根据题目所给数据，（吨），根据题目所给数据，采购的支出采购的支出c(x)c(x)可表为如下的分段线性函数（以下价格以可表为如下的分段线性函数（以下价格以千元千元/吨为单位）：吨为单位）：(1)(1)设原油设原油A A用于生产甲、乙两种汽油的数量分别为用于生产甲、乙两种汽油的数量分别为x x1111和和x x1212（吨），（吨），原油原油B B用于生产甲、乙两种汽油的数量分别为用于生产甲、乙两种汽油的数量分别为x x2121和和x x2222（吨），（吨），则总的收入为则总的收入为4.8(4.8(x x1111+x x2121)+5.6()+5.6(x x1212+x x2222)（千元）。（千元）。于是本例的目标函数（利润）为于是本例的目标函数（利润）为(2)(2)优化建模优化建模约束条件包括加工两种汽油用的原油约束条件包括加工两种汽油用的原油A A、原油、原油B B库存量的限制，库存量的限制，和原油和原油A A购买量的限制，以及两种汽油含原油购买量的限制，以及两种汽油含原油A A的比例限制，的比例限制，它们表示为它们表示为（3）（4）（5）（6）（7）（8）由于（由于（1 1）式中的）式中的c c(x x)不是线性函数，（不是线性函数，（1 1）（8 8）给出的是）给出的是一个非线性规划。而且，对于这样用分段函数定义的一个非线性规划。而且，对于这样用分段函数定义的c c(x x)，一般的非线性规划软件也难以输入和求解。能不能想办法一般的非线性规划软件也难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？将该模型化简，从而用现成的软件求解呢？优化建模优化建模5.1.3 求解模型 3 3种解法种解法第第1种解法种解法 将原油将原油A的采购量的采购量x分解为三个量，即用分解为三个量，即用x1，x2，x3分别表示以价格分别表示以价格10、8、6千元千元/吨采购的原油吨采购的原油A的吨的吨数，总支出为数，总支出为c(x)=10 x1+8x2+6x3，且，且(9)这时目标函数（这时目标函数（2）变为线性函数：）变为线性函数：(10)应该注意到，只有当以应该注意到，只有当以10千元千元/吨的价格购买吨的价格购买x1=500（吨）时，才能以（吨）时，才能以8千元千元/吨的价格购买吨的价格购买x2（0），这个条件可以表示为），这个条件可以表示为(11)优化建模优化建模同理，只有当以同理，只有当以8 8千元千元/吨的价格购买吨的价格购买x x2 2=500=500（吨）时，（吨）时，才能以才能以6 6千元千元/吨的价格购买吨的价格购买x x3 3（00），于是），于是(12)(12)此外，此外，x x1 1，x x2 2，x x3 3的取值范围是的取值范围是(13)(13)优化建模优化建模由于有非线性约束由于有非线性约束(11),(12)(11),(12)，(3)(13)(3)(13)构成非线性构成非线性规划模型。规划模型。LINGOLINGO程序：程序：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.lg4exam0501a.lg4，执行菜单命令执行菜单命令“LINGO|Solve”“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 优化建模优化建模最优解最优解:用库存的用库存的500500吨原油吨原油A A、500500吨原油吨原油B B生产生产10001000吨汽油甲，不购买新的原油吨汽油甲，不购买新的原油A A，利润为，利润为48004800（千元）（千元）但是此时但是此时LINGOLINGO得到的结果只是一个得到的结果只是一个局部最优解局部最优解可以用菜单命令可以用菜单命令“LINGO|Options”“LINGO|Options”在在“Global“Global Solver”Solver”选项卡上启动全局优化（选项卡上启动全局优化（Use Global Use Global SolverSolver）选项，然后重新执行菜单命令）选项，然后重新执行菜单命令“LINGO|Solve”,“LINGO|Solve”,得到：得到：Global optimal solution found.Global optimal solution found.Objective value:5000.002 Objective value:5000.002 Extended solver steps:3 Extended solver steps:3 Total solver iterations:187 Total solver iterations:187 优化建模优化建模Variable Value Reduced CostX11 0.000000 0.000000X21 0.000000 0.000000X12 1500.000 0.000000X22 1000.000 0.000000X1 500.0000 0.000000X2 499.9990 0.000000X3 0.9536707E-03 0.000000X 1000.000 0.000000此时此时LINGOLINGO得到的结果是一个得到的结果是一个全局最优解全局最优解（Global optimal solutionGlobal optimal solution）：购买）：购买10001000吨原油吨原油A A，与库存的，与库存的500500吨原油吨原油A A和和10001000吨原油吨原油B B一起，共生产一起，共生产25002500吨汽油乙，利润为吨汽油乙，利润为50005000（千元），高于刚刚得（千元），高于刚刚得到的局部最优解对应的利润到的局部最优解对应的利润48004800（千元）。（千元）。优化建模优化建模第第2 2种解法种解法:引入引入0-10-1变量将（变量将（1111）和（）和（1212）转化为线性约束）转化为线性约束令令y1=1，y2=1，y3=1分别表示以分别表示以10千元千元/吨、吨、8千元千元/吨、吨、6千元千元/吨的价格采购原油吨的价格采购原油A，则约束（，则约束（11）和（和（12）可以替换为）可以替换为(14)(15)(16)y1，y2，y3=0或或1(17)优化建模优化建模（3 3）（1010），（），（1313）（1717）构成混合整数线性）构成混合整数线性规划模型，将它输入规划模型，将它输入LINDOLINDO软件：软件：优化建模优化建模Max 4.8x11+4.8x21+5.6x12+5.6x22-10 x1-8x2-6x3stx-x1-x2-x3=0 x11+x12-x500 x21+x220 0.4x12-0.6x220 x1-500y10 x2-500y20 x3-500y30 x2-500y30 endint y1int y2int 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 3种解法种解法 直接处理分段线性函数c(x)。（1）式表示的函数c(x)如图5-1。c(x)x1200090005000050010001500图图5-1 分段线性函数分段线性函数c(x)图形图形 优化建模优化建模记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+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模型如下：Model:SETS:Points/1.4/:b,c,y,z;!端点数为4，即分段数为3;ENDSETSDATA: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)约束条件约束条件这个问题中的约束有这么几类：每个项目的物流这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束产某项目前必须经过生产准备和非负约束（对（对Yi,j是是0-1约束）。约束）。优化建模优化建模(29)资源能力限制比较容易理解，即资源能力限制比较容易理解，即(30)所谓物流守恒（假设所谓物流守恒（假设Ii,0=0）优化建模优化建模(31)每时段生产某项目前必须经过生产准备，也就是说当每时段生产某项目前必须经过生产准备，也就是说当Xit=0时时Yit=0；Xit0时时Yit=1。这本来是一个非线性约束，但是。这本来是一个非线性约束，但是通过引入参数通过引入参数M（很大的正数，表示每个项目每个时段（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：的最大产量）可以化成线性约束，即：总结总结:这个问题的优化模型就是在约束这个问题的优化模型就是在约束（2929）（）（3030）（）（3131）下使目标函数（）下使目标函数（2828）达到最）达到最小。小。优化建模优化建模5.2.3 5.2.3 求解模型求解模型本例生产项目总数本例生产项目总数N=7(A、B、C、D、E、F、G)，计，计划期长度划期长度T=6（周），瓶颈资源种类数（周），瓶颈资源种类数K=1。只有。只有A有外部需求，所以有外部需求，所以di,t中只有中只有d1,t可以取非零需求，即可以取非零需求，即表表5-1中的第中的第2行的数据，其他全部为零。行的数据，其他全部为零。参数参数si,t、hi,t只与项目只与项目i有关，而不随时段有关，而不随时段t变化，所以可以略去变化，所以可以略去下标下标t，其数值就是表，其数值就是表5-1中的最后两行数据。中的最后两行数据。由于只有一种资源，参数由于只有一种资源，参数Ck,t可以略去下标可以略去下标k，其数值，其数值就是表就是表5-1中的第中的第3行的数据；而行的数据；而ak,I,t只与项目只与项目i有关，有关，而不随时段而不随时段t变化，所以可以同时略去下标变化，所以可以同时略去下标k和和t，即，即a2=5，a3=8（其他（其他ai为为0）。从图）。从图6-2中容易得到项中容易得到项目目i的直接后继项目集合的直接后继项目集合S(i)和消耗系数。和消耗系数。优化建模优化建模准备以下的数据文件（文本文件准备以下的数据文件（文本文件exam0502.LDT，可，可以看到其中也可以含有注释语句）：以看到其中也可以含有注释语句）：!项目集合;ABCDEFG!计划期集合;123456!需求;400100090100 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 优化建模优化建模!能力;1000005000 5000 1000 1000!生产准备费;4005001000 300200400100!库存费;120.61.00.04 0.03 0.04 0.04!对能力的消耗系数；0580000 优化建模优化建模!项目间的消耗系数:req(i,j)表示j用到多少i;0 0 0 0 0 0 05 0 0 0 0 0 07 0 0 0 0 0 00 9 0 0 0 0 00 11 0 0 0 0 00 0 13 0 0 0 00 0 15 0 0 0 0!数据结束;优化建模优化建模对本例，对本例，A的外部总需求为的外部总需求为240，所以任何项目的，所以任何项目的产量不会超过产量不会超过24071525000（从图（从图6-2可以可以知道，这里知道，这里715已经是每件产品已经是每件产品A对任意一个对任意一个项目的最大的消耗系数了），所以取项目的最大的消耗系数了），所以取M=25000就已经足够了。就已经足够了。本例中的具体模型可以如下输入本例中的具体模型可以如下输入LINGO软件：软件：MODEL:TITLE 瓶颈设备的多级生产计划;!从文本文件exam0502.LDT中读取数据;优化建模优化建模SETS:!PART=项目集合,Setup=生产准备费，Hold=单件库存成本，A=对瓶颈资源的消耗系数;PART/FILE(exam0502.LDT)/:Setup,Hold,A;!TIME=计划期集合，Capacity=瓶颈设备的能力;TIME/FILE(exam0502.LDT)/:Capacity;!USES=项目结构关系，Req=项目之间的消耗系数;USES(PART,PART):Req;!PXT=项目与时间的派生集合，Demand=外部需求,X=产量（批量）,Y=0/1变量，INV=库存;PXT(PART,TIME):Demand,X,Y,Inv;ENDSETS 优化建模优化建模!目标函数;OBJ Min=sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t);!物流平衡方程;FOR(PXT(i,t)|t#NE#1:Bal Inv(i,t-1)+X(i,t)-Inv(i,t)=Demand(i,t)+SUM(USES(i,j):Req(i,j)*X(j,t);FOR(PXT(i,t)|t#eq#1:Ba0 X(i,t)-Inv(i,t)=Demand(i,t)+SUM(USES(i,j):Req(i,j)*X(j,t);!能力约束;FOR(TIME(t):Cap SUM(PART(i):A(i)*X(i,t)Capacity(t);优化建模优化建模!其他约束;M=25000;FOR(PXT(i,t):X(i,t)=50 x2+2x4+x5+3x6 =20 x3 +x5 +2x7=15endgin 7 优化建模优化建模求解可以得到最优解如下：求解可以得到最优解如下：OBJECTIVE FUNCTION VALUE 1)27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 优化建模优化建模即按照模式即按照模式2 2切割切割1212根原料钢管，按照模式根原料钢管，按照模式5 5切切割割1515根原料钢管，共根原料钢管，共2727根，总余料量为根，总余料量为2727米。米。显然，在总余料量最小的目标下，最优解将是显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式使用余料尽可能小的切割模式（模式2 2和和5 5的余的余料为料为1 1米），这会导致切割原料钢管的总根数较米），这会导致切割原料钢管的总根数较多。多。优化建模优化建模2.2.将（将（3333）（3636）构成的整数线性规划模型）构成的整数线性规划模型（加上整数约束）输入（加上整数约束）输入LINDOLINDO：Title 钢管下料钢管下料-最小化钢管根数最小化钢管根数Min x1+x2+x3+x4 +x5+x6 +x7 s.t.4x1+3x2+2x3+x4+x5 =50 x2+2x4+x5+3x6 =20 x3 +x5 +2x7=15endgin 7 优化建模优化建模求解，可以得到最优解如下：求解，可以得到最优解如下：OBJECTIVE FUNCTION VALUE 1)25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 优化建模优化建模即按照模式即按照模式2切割切割15根原料钢管，按模式根原料钢管，按模式5切割切割5根，按模根，按模式式7切割切割5根，共根，共27根，可算出总余料量为根，可算出总余料量为35米。与上面得米。与上面得到的结果相比，总余料量增加了到的结果相比，总余料量增加了8米，但是所用的原料钢米，但是所用的原料钢管的总根数减少了管的总根数减少了2根。在余料没有什么用途的情况下，根。在余料没有什么用途的情况下，通常选择总根数最少为目标。通常选择总根数最少为目标。优化建模优化建模问题问题2）的求解）的求解问题分析问题分析 按照解问题按照解问题1）的思路，可以通过枚举法首先确）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。性的方法。同同1）类似，一个合理的切割模式的余料不应该大于或等于）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为客户需要的钢管的最小尺寸（本题中为4米），切割计划中米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于以合理的切割模式的余量不能大于3米。此外，这里我们仅米。此外，这里我们仅选择总根数最少为目标进行求解。选择总根数最少为目标进行求解。优化建模优化建模模型建立模型建立决策决策变变量量 由于不同切割模式不能超由于不同切割模式不能超过过3种，可以用种，可以用xi 表示表示按照第按照第i种模式（种模式（i=1,2,3）切割的原料）切割的原料钢钢管的根数，管的根数，显显然它然它们应们应当是非当是非负负整数。整数。设设所使用的第所使用的第i种切割模式下种切割模式下每根原料每根原料钢钢管生管生产产4米米长长、5米米长长、6米米长长和和8米米长长的的钢钢管数量分管数量分别为别为r1i,r2i,r3i,r4i（非非负负整数整数）。）。决策目决策目标标 以切割原料以切割原料钢钢管的管的总总根数最少根数最少为为目目标标，即目，即目标为标为（37）优化建模优化建模约约束条件束条件 为满为满足客足客户户的需求，的需求，应应有有(38)(39)(40)(41)优化建模优化建模每一种切割模式必每一种切割模式必须须可行、合理，所以每根原料可行、合理，所以每根原料钢钢管的管的成品量不能超成品量不能超过过19米，也不能少于米，也不能少于16米（余量不能大于米（余量不能大于3米），于是米），于是(42)(43)(44)优化建模优化建模模型求解模型求解（37）（44）构成）构成这这个个问题问题的的优优化模型。由于在化模型。由于在（38）（41）式中出）式中出现现了决策了决策变变量的乘量的乘积积，所以，所以这这是一是一个整数非个整数非线线性性规规划模型，划模型，虽虽然用然用LINGO软软件可以直接求件可以直接求解，但我解，但我们发现们发现在在较较低版本的低版本的LINGO软软件中需要运行很件中需要运行很长时间长时间也也难难以得到最以得到最优优解。解。为为了减少运行了减少运行时间时间，可以增加，可以增加一些一些显显然的然的约约束条件，从而束条件，从而缩缩小可行解的搜索范小可行解的搜索范围围。例如，由于例如，由于3种切割模式的排列种切割模式的排列顺顺序是无关序是无关紧紧要的，所以不要的，所以不妨增加以下妨增加以下约约束：束：（45）优化建模优化建模又例如，我又例如，我们们注意到所需原料注意到所需原料钢钢管的管的总总根数有着明根数有着明显显的的上界和下界。首先，无上界和下界。首先，无论论如何，原料如何，原料钢钢管的管的总总根数不根数不可能少于可能少于 （根）（根）其次，考虑一种非常特殊的生产计划：第一种切割模式下只其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产生产4米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成4根根4米钢管，为满足米钢管，为满足50根根4米钢管的需求，需要米钢管的需求，需要13根原料钢管；第二种切割模根原料钢管；第二种切割模式下只生产式下只生产5米、米、6米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成1根根5米米钢管和钢管和2根根6米钢管，为满足米钢管，为满足10根根5米和米和20根根6米钢管的需米钢管的需求，需要求，需要10根原料钢管；根原料钢管；优化建模优化建模第三种切割模式下只生产第三种切割模式下只生产8米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成2根根8米钢管，为满足米钢管，为满足15根根8米钢管的需求，需要米钢管的需求，需要8根原料钢管。根原料钢管。于是满足要求的这种生产计划共需于是满足要求的这种生产计划共需13+10+8=31根原料钢根原料钢管，这就得到了最优解的一个上界。所以可增加以下约管，这就得到了最优解的一个上界。所以可增加以下约束：束：(46)将（37）（46）构成的模型输入LINGO如下：优化建模优化建模将（37）（46）构成的模型输入LINGO如下：model:Title 钢钢管下料管下料-最小化最小化钢钢管根数的管根数的LINGO模型模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13=50;x1*r21+x2*r22+x3*r23=10;x1*r31+x2*r32+x3*r33=20;x1*r41+x2*r42+x3*r43=15;4*r11+5*r21+6*r31+8*r41=19;4*r12+5*r22+6*r32+8*r42=19;4*r13+5*r23+6*r33+8*r43=16;4*r12+5*r22+6*r32+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;x1+x2+x3=26;x1+x2+x3=x2;x2=x3;gin(x1);gin(x2);gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);end 优化建模优化建模经过经过LINGO求解，得到求解，得到输输出如下：出如下：Local optimal solution found.Objective value:28.00000 Extended solver steps:72 Total solver iterations:3404 Model Title:钢钢管下料管下料-最小化最小化钢钢管根数的管根数的LINGO模型模型 优化建模优化建模 Variable Value Reduced CostX1 10.00000 1.000000X2 10.00000 1.000000X3 8.000000 1.000000R11 2.000000 0.000000R12 3.000000 0.000000R13 0.000000 0.000000R21 1.000000 0.000000R22 0.000000 0.000000R23 0.000000 0.000000R31 1.000000 0.000000R32 1.000000 0.000000R33 0.000000 0.000000R41 0.000000 0.000000R42 0.000000 0.000000R43 2.000000 0.000000 优化建模优化建模即按照模式即按照模式1、2、3分分别别切割切割10、10、8根原料根原料钢钢管，使用管，使用原料原料钢钢管管总总根数根数为为28根。第一种切割模式下一根原料根。第一种切割模式下一根原料钢钢管管切割成切割成3根根4米米钢钢管和管和1根根6米米钢钢管；第二种切割模式下一根管；第二种切割模式下一根原料原料钢钢管切割成管切割成2根根4米米钢钢管、管、1根根5米米钢钢管和管和1根根6米米钢钢管；管；第三种切割模式下一根原料第三种切割模式下一根原料钢钢管切割成管切割成2根根8米米钢钢管。管。如果充分利用如果充分利用LINGO建模建模语语言的能力，使用集合和属性言的能力，使用集合和属性的概念，可以的概念，可以编编写以下写以下LINGO程序，程序，这这种方法更具有一种方法更具有一般的通用性，并有利于般的通用性，并有利于输输入更大入更大规规模的下料模的下料问题问题的的优优化模化模型：型：优化建模优化建模model:Title 钢管下料钢管下料-最小化钢管根数的最小化钢管根数的LINGO模型模型;SETS:NEEDS/1.4/:LENGTH,NUM;!定义基本集合定义基本集合NEEDS及其属性及其属性LENGTH,NUM;CUTS/1.3/:X;!定义基本集合定义基本集合CUTS及其属性及其属性X;PATTERNS(NEEDS,CUTS):R;!定义派生集合定义派生集合PATTERNS（这是一个稠密集合）及其属性（这是一个稠密集合）及其属性R;ENDSETSDATA:LENGTH=4 5 6 8;NUM=50 10 20 15;CAPACITY=19;ENDDATAmin=SUM(CUTS(I):X(I);优化建模优化建模!目标函数目标函数;FOR(NEEDS(I):SUM(CUTS(J):X(J)*R(I,J)NUM(I);!满足需求约束满足需求约束;FOR(CUTS(J):SUM(NEEDS(I):LENGTH(I)*R(I,J)CAPACITY -MIN(NEEDS(I):LENGTH(I);!合理切割模式约束合理切割模式约束;SUM(CUTS(I):X(I)26;SUM(CUTS(I):X(I)X(I+1);!人为增加约束人为增加约束;FOR(CUTS(J):GIN(X(J);FOR(PATTERNS(I,J):GIN(R(I,J);end求解求解这这个模型，得到的个模型，得到的结结果与前面的果与前面的结结果完全相同。果完全相同。优化建模优化建模易拉罐下料问题易拉罐下料问题例例5.4 某公司采用一套冲压设备生产一种罐装饮料的某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图5-3）。易拉罐为圆柱形，包括罐身、上盖和下底，罐）。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高身高10厘米，上盖和下底的直径均为厘米，上盖和下底的直径均为5厘米。该公司使厘米。该公司使用两种不同规格的镀锡板原料，规格用两种不同规格的镀锡板原料，规格1的镀锡板为正方的镀锡板为正方形，边长形，边长24厘米；规格厘米；规格2的镀锡板为长方形，长、宽分的镀锡板为长方形，长、宽分别为别为32和和28厘米。由于生产设备和生产工艺的限制，厘米。由于生产设备和生产工艺的限制，对于规格对于规格1的镀镀锡板原料，只可以按照图的镀镀锡板原料，只可以按照图2中的模式中的模式1、2或或3进行冲压；对于规格进行冲压；对于规格2的镀锡板原料只能按照模式的镀锡板原料只能按照模式4进行冲压。使用模式进行冲压。使用模式1、2、3、4进行每次冲压所需要进行每次冲压所需要的时间分别为的时间分别为1.5、2、1、3（秒）。（秒）。优化建模优化建模模式1模式2模式3模式4上盖下底罐身图5-3 易拉罐下料模式 优化建模优化建模该工厂每周工作该工厂每周工作40小时，每周可供使用的规格小时，每周可供使用的规格1、2的镀锡板的镀锡板原料分别为原料分别为5万张和万张和2万张。目前每只易拉罐的利润为万张。目前每只易拉罐的利润为0.10元，元，原料余料损失为原料余料损失为0.001元元/厘米厘米2（如果周末有罐身、上盖或（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。下底不能配套组装成易拉罐出售，也看作是原料余料损失）。工厂应如何安排每周的生产？工厂应如何安排每周的生产？已知上盖和下底的直径已知上盖和下底的直径d=5厘米，可得其面积为厘米，可得其面积为 19.6厘米厘米2 优化建模优化建模表表5-4 4种冲压模式的特征种冲压模式的特征罐身个数底、盖个数余料损失（厘米2）冲压时间（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、盖的配套组装。优化建模优化建模模型建立模型建立决策变量决策变量 用用xi 表示按照第表示按照第i种模式的冲压次数（种模式的冲压次数（i=1,2,3,4），），y1表示表示一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的原料损失，用原料损失，用y2表示不配套的罐身个数，表示不配套的罐身个数，y3表示不配套的底、盖个数。表示不配套的底、盖个数。虽然实际上虽然实际上xi和和y1，y2，y3应该是整数。但是由于生产量相当大，可以应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。把它们看成是实数，从而用线性规划模型处理。决策目标决策目标 假设每周生产的易拉罐能够全部售出，公司每周的销假设每周生产的易拉罐能够全部售出，公司每周的销售利润是售利润是0.1y1。原料余料损失包括两部分：。原料余料损失包括两部分：4种冲压模式下的余种冲压模式下的余料损失，和不配套的罐身和底、盖造成的原料损失。按照前面料损失，和不配套的罐身和底、