1生产运作管理优化ppt课件

1、消费与效力运作管理中的优化问题优化建模与LINDO/LINGO软件.内容提要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元/吨；购买量超越500吨但不

2、超越1000吨时，超越500吨的部分8000元/吨；购买量超越1000吨时，超越1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工。.5.1.2建立模型问题分析 安排原油采购、加工的目的是利润最大，标题中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处置是关键所在。.模型建立设原油A的购买量为x吨，根据标题所给数据，采购的支出c(x)可表为如下的分段线性函数以下价钱以千元/吨为单位：(1)设原油A用于消费甲、乙两种汽油的数量分别为x11和

3、x12吨，原油B用于消费甲、乙两种汽油的数量分别为x21和x22吨，那么总的收入为4.8(x11+x21)+5.6(x12+x22)千元。于是本例的目的函数利润为(2).约束条件包括加工两种汽油用的原油A、原油B库存量的限制，和原油A购买量的限制，以及两种汽油含原油A的比例限制，它们表示为345678由于1式中的c(x)不是线性函数，18给出的是一个非线性规划。而且，对于这样用分段函数定义的c(x)，普通的非线性规划软件也难以输入和求解。能不能想方法将该模型化简，从而用现成的软件求解呢？.5.1.3 求解模型 3种解法第1种解法 将原油A的采购量x分解为三个量，即用x1，x2，x3分别表示以价

4、钱10、8、6千元/吨采购的原油A的吨数，总支出为c(x) = 10 x1+8x2+6x3，且(9)这时目的函数2变为线性函数：(10)应该留意到，只需当以10千元/吨的价钱购买x1=500吨时，才干以8千元/吨的价钱购买x20，这个条件可以表示为(11).同理，只需当以8千元/吨的价钱购买x2=500吨时，才干以6千元/吨的价钱购买x30，于是(12)此外，x1，x2，x3的取值范围是(13).由于有非线性约束(11),(12)，(3)(13)构成非线性规划模型。LINGO程序：Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1

5、- 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 Varia

6、ble 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

7、 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 CostX11 0.000000 0.000000X21 0.000000 0.000000X12 1500.000 0.000000X22 1000.000 0.000000X1 500.0000

8、0.000000X2 499.9990 0.000000X3 0.9536707E-03 0.000000X 1000.000 0.000000此时LINGO得到的结果是一个全局最优解Global optimal solution：购买1000吨原油A，与库存的500吨原油A和1000吨原油B一同，共消费2500吨汽油乙，利润为5000千元，高于刚刚得到的部分最优解对应的利润4800千元。.第2种解法: 引入0-1变量将11和12转化为线性约束令y1=1，y2=1，y3=1分别表示以10千元/吨、8千元/吨、6千元/吨的价钱采购原油A，那么约束11和12可以交换为(14)(15)(16) y1

9、，y2，y3 =0或1(17).310，1317构成混合整数线性规划模型，将它输入LINDO软件：.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.0000

10、00 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。

11、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

12、(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)可以一致地表示为210，1822也构成一个混合整数线性规划模型，可以用LINDO求解。不过，我们还是将它输入LINGO软件，由于其扩展性更好即当分段函数的分段数更多时，只需求对下面程序作很小的改动。输入的LINGO模型如下：(22).输入的LINGO模型如下：Model:SETS:Points/1.4/: b, c, y, z;! 端点

13、数为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.在上述数学符号

14、中，只需为决策变量; 其他均为知的方案参数。.目的函数 这个问题的目的是使消费预备费用和库存费用的总和最小。因此，目的函数应该是每个工程在每个时段上的消费预备费用和库存费用的总和，即(28)约束条件这个问题中的约束有这么几类：每个工程的物流应该守恒、资源才干限制应该满足、每时段消费某工程前必需经过消费预备和非负约束 对Yi,j是0-1约束。.(29)资源才干限制比较容易了解，即(30)所谓物流守恒假设Ii,0 =0 .(31)每时段消费某工程前必需经过消费预备，也就是说当Xit=0时Yit=0；Xit0时Yit=1。这本来是一个非线性约束，但是经过引入参数M很大的正数，表示每个工程每个时段的最

15、大产量可以化成线性约束，即： 总结: 这个问题的优化模型就是在约束293031下使目的函数28到达最小。 .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，其数值就是表1中的最后两行数据。由于只需一种资源，参数Ck,t可以略去下标k，其数值就是表1中的第3行的数据；而ak,I,t只与工程i有关，而不随时段t变化，所以可以同时略去下标k和t，即a2=

16、5，a3=8其他ai为0。从图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.! 才干;1000005000500010001000! 消费预备费;4005001000300200400100! 库存费;120.61.00.040.030.040.04! 对才干的耗费系数；05800

17、00.! 工程间的耗费系数: 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从图2可以知道，这里715曾经是每件产品A对恣意一个工程的最大的耗费系数了，所以取M=25000就曾经足够了。本例中的详细模型可以如下输入LINGO软件：MODEL:TITLE 瓶颈设备的多级消费方案;! 从文本文件exam0502.LDT中读取数据;

18、.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 = 库存

19、;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

20、( 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

21、.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切割12根原料钢管，按照方式5切割15根原料钢管，共27根，总余料量为27米。显然，在总余料量最小的目的下，最优解将是运用余料尽能够小的切割方式方式2和5的余料为1米，这会导致切割原料钢管的总根数较多。.2. 将3336构成的整数线性规划模型加上整数约束输入LINDO：Title 钢管下料 - 最小化钢管根数Min x1 + x2 + x

22、3 + 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.0

23、00000 1.000000 X7 5.000000 1.000000.即按照方式2切割15根原料钢管，按方式5切割5根，按方式7切割5根，共27根，可算出总余料量为35米。与上面得到的结果相比，总余料量添加了8米，但是所用的原料钢管的总根数减少了2根。在余料没有什么用途的情况下，通常选择总根数最少为目的。.问题2的求解问题分析 按照解问题1的思绪，可以经过枚举法首先确定哪些切割方式是可行的。但由于需求的钢管规格添加到4种，所以枚举法的任务量较大。下面引见的整数非线性规划模型，可以同时确定切割方式和切割方案，是带有普遍性的方法。同1类似，一个合理的切割方式的余料不应该大于或等于客户需求的钢管的

24、最小尺寸此题中为4米，切割方案中只运用合理的切割方式，而由于此题中参数都是整数，所以合理的切割方式的余量不能大于3米。此外，这里我们仅选择总根数最少为目的进展求解。 .模型建立决策变量 由于不同切割方式不能超越3种，可以用xi 表示按照第i种方式i=1, 2, 3切割的原料钢管的根数，显然它们该当是非负整数。设所运用的第i种切割方式下每根原料钢管消费4米长、5米长、6米长和8米长的钢管数量分别为r1i, r2i, r3i, r4i非负整数。 决策目的 以切割原料钢管的总根数最少为目的，即目的为37.约束条件 为满足客户的需求，应有(38)(39)(40)(41).每一种切割方式必需可行、合理，

25、所以每根原料钢管的废品量不能超越19米，也不能少于16米余量不能大于3米，于是(42)(43)(44).模型求解3744构成这个问题的优化模型。由于在3841式中出现了决策变量的乘积，所以这是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发如今较低版本的LINGO软件中需求运转很长时间也难以得到最优解。为了减少运转时间，可以添加一些显然的约束条件，从而减少可行解的搜索范围。例如，由于3种切割方式的陈列顺序是无关紧要的，所以无妨添加以下约束：45.又例如，我们留意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不能够少于 根其次，思索一种非常特殊的消

26、费方案：第一种切割方式下只消费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)将3746构成的模型输入LINGO如下：.将3746构成的模型输入LINGO如下：model:Title

27、钢管下料 - 最小化钢管根数的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 =

28、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: 钢管下料-最小化钢

29、管根数的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.00000

30、0 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

31、模型;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

32、(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.3.2易拉罐下料问题例5.4 某公司采用一套冲压设备消费一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的参见图5-3。易拉

33、罐为圆柱形，包括罐身、上盖和下底，罐身高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元

34、，原料余料损失为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表示一周消

35、费的易拉罐个数。为计算不能配套组装的罐身和底、盖呵斥的原料损失，用y2表示不配套的罐身个数，y3表示不配套的底、盖个数。虽然实践上xi和y1，y2，y3应该是整数。但是由于消费量相当大，可以把它们看成是实数，从而用线性规划模型处置。决策目的 假设每周消费的易拉罐可以全部售出，公司每周的销售利润是0.1y1。原料余料损失包括两部分：4种冲压方式下的余料损失，和不配套的罐身和底、盖呵斥的原料损失。按照前面的计算及表2的结果，总损失为0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。 .于是，决策目的为(47)约束条件 时间

36、约束：每周任务时间不超越40小时=144000秒，由表2最后一列得(48)原料约束：每周可供运用的规格1、2的镀锡板原料分别为50000张和20000张，即(49)(50). 配套约束： 由表2一周消费的罐身个数为x1 + 2x2 + 4x4, 一周消费的底、盖个数为10 x1 + 4x2 + 16x3+ 5x4，由于应尽能够将它们配套组装成易拉罐销售。所以y1满足 (51)这时不配套的罐身个数y2，和不配套的底、盖个数y3应为 (52) (53).4753就是我们得到的模型，其中51是一个非线性关系，不易直接处置， 但是它可以等价为以下两个线性不等式： (54) (55)模型求解将模型475

37、0和5255直接输入LINDO输入LINGO也可以，求解时LINDO发出警告信息程序和警告信息参见图5-4。 图中错误编号“66的含义参见第4章的错误代码表是：模型中数据不平衡，所以发出警告信息留意，只是警告信息，所以依然可以继续求解。求解结果是：. OBJECTIVE FUNCTION VALUE 1) 4298.337 VARIABLE VALUE REDUCED COST Y1 160250.000000 0.000000 X1 0.000000 0.000050 X2 40125.000000 0.000000 X3 3750.000000 0.000000 X4 20000.0000

38、00 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484.图5-4 模型中数据不平衡的警告信息.这个结果可靠吗？由于LINDO警告模型中数据之间的数量级差别太大，所以我们可以进展预处置，减少数据之间的差别。实践上，约束4850中右端项的数值过大与左端的系数相比较，LINDO在计算中容易产生比较大的误差，所以出现此警告信息。为理处理这一问题，可以将一切决策变量扩展10000倍相当于xi以万次为单位，yi以万件为单位。此时，目的47可以坚持不变记住得到的结果单位为万元就可以了，而约束4850改为 (56)(57) (58).将模型47和5258输入

39、LINDO:! 易拉罐下料：平衡数据Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3 s.t.1.5x1 + 2.0 x2 + 1.0 x3 +3.0 x4 = 14.4 x1 + x2 + x3 = 5 x4 =010 x1 + 4x2 + 16x3+ 5x4 - 2y1 =0 x1 + 2x2 + 4x4 - y1 - y2 =010 x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0end.求解得到： OBJECTIVE FUNCTION VALUE 1) 0.42

40、98337 VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484即方式1不运用，方式2运用40125次，方式3运用3750次，方式4运用20000次，可消费易拉罐160250个，罐身和底、盖均无剩余，净利润为4298元。.5.4 面试顺序与消防车调度问题.面试顺序问题 例5.5 有4名同窗到一家公司参

41、与三个阶段的面试：公司要求每个同窗都必需首先找公司秘书初试，然后到部门主管处复试，最后到经理处参与面试，并且不允许插队即在任何一个阶段4名同窗的顺序是一样的。由于4名同窗的专业背景不同，所以每人在三个阶段的面试时间也不同，如表5-5所示单位：分钟。这4名同窗商定他们全部面试完以后一同分开公司。假定如今时间是早晨8：00，请问他们最早何时能分开公司？ .表5-5 面试时间要求秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201010同学丁81015.建立模型 实践上，这个问题就是要安排4名同窗的面试顺序，使完成全部面试所破费的时间最少。 记tij为第i名同窗参与第j阶段面试需

42、求的时间(知)，令xij表示第i名同窗参与第j阶段面试的开场时辰(无妨记早上8：00面试开场为0时辰)(i=1, 2, 3, 4；j=1, 2, 3)，T为完成全部面试所破费的最少时间。 优化目的为. a. 时间先后次序约束(每人只需参与完前一个阶段的面试后才干进入下一个阶段)： xij+ tij xi，j+1 (i=1, 2, 3, 4；j=1, 2) b.每个阶段j同一时间只能面试1名同窗：用0-1变量yik表示第k名同窗能否排在第i名同窗前面(1表示是，0表示否)，那么 xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxi

43、jT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) 约束条件： .可以将非线性的优化目的改写为如下线性优化目的： Min T s.t. T x13+ t13 T x23+ t23 T x33+ t33 T x43+ t43. Min T s.t. xij+ tij xi, j+1 (i=1, 2, 3, 4；j=1, 2) xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxijT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; i= x13+ t13;T = x23+ t23

44、;T = x33+ t33;T = x43+ t43;x11+ t11 = x12;x12+ t12 = x13;x21+ t21 = x22;x22+ t22 = x23;x31+ t31 = x32;x32+ t32 = x33;x41+ t41 = x42;x42+ t42 = x43;求解模型这个模型可以如下输入LINGO： .x11+ t11 - x21= T*y12;x21+ t21 - x11= T*(1-y12);x12+ t12 - x22= T*y12;x22+ t22 - x12= T*(1-y12);x13+ t13 - x23= T*y12;x23+ t23 - x1

45、3= T*(1-y12);x11+ t11 - x31= T*y13;x31+ t31 - x11= T*(1-y13); x12+ t12 - x32= T*y12;x32+ t32 - x12= T*(1-y13);x13+ t13 - x33= T*y13;x33+ t33 - x13= T*(1-y13);x11+ t11 - x41= T*y14;x41+ t41 - x11= T*(1-y14);x12+ t12 - x42= T*y14;x42+ t42 - x12= T*(1-y14);.x13+ t13 - x43= T*y14;x43+ t43 - x13= T*(1-y1

46、4);x21+ t21 - x31= T*y23;x31+ t31 - x21= T*(1-y23);x22+ t22 - x32= T*y23;x32+ t32 - x32= T*(1-y23);x23+ t23 - x33= T*y23;x33+ t33 - x23= T*(1-y23);x21+ t21 - x41= T*y24;x41+ t41 - x21= T*(1-y24);x22+ t22 - x42= T*y24;x42+ t42 - x22= T*(1-y24);x23+ t23 - x43= T*y24;x43+ t43 - x23= T*(1-y24);x31+ t31

47、- x41= T*y34; x41+ t41 - x31= T*(1-y34);.x32+ t32 - x42= T*y34;x42+ t42 - x32= T*(1-y34);x33+ t33 - x43= T*y34;x43+ t43 - x33= max(PXS(i,j)|j#EQ#size(stage): x(i,j)+t(i,j);! 只需参与完前一个阶段的面试后才干进入下一个阶段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);! 同一时间只能面试1名同窗;for(Stage(j): for(PXP(i,k):SOR

48、T1x(i, j)+t(i, j)-x(k,j)MAXT*Y(i,k) ); for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)MAXT*(1-Y(i,k) ););for(PXP: bin(y);End . 求解这个模型，得到的结果与前面的完全一样。 可以很清楚地看到，运用LINGO建模言语的集合和属性概念，得到的模型具有非常好的构造性，反映了相应的优化模型的本质，目的、决策变量、约束一清二楚，容易阅读和了解，而且还可以让数据与程序完全分别，这种优越性是LINDO软件无法与之相比的。 .消防车调度问题 例5.6 某市消防中心同时接到了三处火警报告。根据当前的火势，

49、三处火警地点分别需求2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间(分钟)，那么三处火警地点的损失分别为: 6t11+4t12，7t21+3t22，9t31+8t32+5t33。 目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站(可用消防车数量分别为3辆、2辆、2辆)。消防车从三个消防站到三个火警地点所需求的时间如表5-6所示。该公司应如何调度消防车，才干使总损失最小？ . 假设三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案能否需求改动？消防站到三个火

50、警地点所需求的时间时间(分钟)火警地点1火警地点2火警地点3消防站1679消防站25811消防站36910. 问题分析 此题思索的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。此题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。 决策变量 为了用运输问题建模求解，很自然地把3个消防站看成供应点。假设直接把3个火警地点看成需求点，我们却不能很方便地描画消防车到达的先后次序，因此难以确定损失的大小。下面我们把7辆车的需求分别看成7个需求点(分别对应于到达时间t11, t12, t21, t22, t31, t32, t33)。

51、用xi j表示消防站i能否向第j个需求点派车(1表示派车，0表示不派车)，那么共有21个0-1变量。 . 决策目的 标题中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进展简单的计算可知，假设消防站1向第6个需求点派车(即消防站1向火警地点3派车但该消防车是到达火警地点3的第二辆车)，那么由此引起的损失为8*9=72。同理计算，可以得到损失矩阵(元素分别记为ci j)。 ci j火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=136244921817245消防站i=230205624998855消防站i=336246327908050.于是，使总损

52、失最小的决策目的为 约束条件 约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。 消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+x36+x37=2 各需求点对消防车的需求量限制可以表示为 .模型求解 将如上构成的线性规划模型输入LINDO 0506a： ! 消防车问题Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30 x21+20 x22+56x23+2

53、4x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90 x35+80 x36+50 x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 =1 x12+x22+x32 =1 x13+x23+x33 = 1 x14+x24+x34 =1 x15+x25+x35 =1 x16+x26+x36 = 1 x17+x27+x37 = 1 END .求解得到如下结果： O

54、BJECTIVE FUNCTION VALUE 1) 329.0000VARIABLE VALUE REDUCED COST X11 0.000000 10.000000 X12 0.000000 8.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X15 1.000000 0.000000 X16 1.000000 0.000000 X17 0.000000 3.000000 X21 1.000000 0.000000 X22 1.000000 0.000000 X23 0.000000 3.000000 X24 0.000000 1.0

55、00000 X25 0.000000 14.000000 X26 0.000000 12.000000 X27 0.000000 9.000000 .VARIABLE VALUE REDUCED COST X31 0.000000 2.000000 X32 0.000000 0.000000 X33 0.000000 6.000000 X34 1.000000 0.000000 X35 0.000000 1.000000 X36 0.000000 0.000000 X37 1.000000 0.000000 也就是说，消防站1应向火警地点2派1辆车，向火警地点3派2辆车；消防站2应向火警地点1

56、派2辆车；消防站3应向火警地点2、3各派1辆车。最小总损失为329。 .讨论 1) 这个问题本质上依然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设xij为0-1变量，但求解时是采用线性规划求解的，也就是说没有加上xij为0-1变量或整数变量的限制条件，但求解得到的结果中xij正好是0-1变量。这一结果不是偶尔的，而是运输问题特有的一种性质。. 2) 在上面模型中，我们没有思索消防车到达各火警地点的先后次序约束，但得到的结果正好满足一切的先后次序约束。这一结果却并不总是必然的，而只是巧合。 如对例题后半部分的情形，结果就不是这样了。显然，此时

57、只需求修正损失矩阵(元素依然分别记为cij)ci j火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=124362149457281消防站i=220302456558899消防站i=324362763508090. 此时将重新构成的线性规划模型输入LINDO求解, 可以得到新的最优解: x14=x16=x17=x21=x22=x33=x35=1其他变量为0(最小总损失仍为329)。实践上, 损失矩阵中只是1、2列交换了位置，3、4列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。 但是，以上新的最优解却是不符合实践情况的。例如，x1

58、4=x33=1阐明火警地点2的第一辆消防车来自消防站3，第二辆消防车来自消防站1，但这是不合理的，由于火警地点2与消防站3有9分钟的间隔，大于与消防站1的7分钟的间隔。分配给火警地点3的消防车也有类似的不合理问题。 . 为理处理这一问题，我们必需思索消防车到达各火警地点的先后次序约束，也就是说必需在简单的运输问题模型中添加一些新的约束，以保证以上的不合理问题不再出现。 首先思索火警地点2。由于消防站1的消防车到达所需时间(7分钟)小于消防站2的消防车到达所需时间(8分钟)，并都小于消防站3的消防车到达所需时间(9分钟)，因此火警地点2的第2辆消防车假设来自消防站1，那么火警地点2的第1辆消防车

59、也一定来自消防站1；火警地点2的第2辆消防车假设来自消防站2，那么火警地点2的第1辆消防车一定来自消防站1或2。因此，必需添加以下约束：x14x13x24x13 +x23.x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，对火警地点1，必需添加以下约束：x22x21对火警地点3，必需添加以下约束：. 此时将重新构成的线性规划模型输入LINDO软件如下： 0506b! 消防车调度Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15 +30 x22+20 x21+56x24+24x23+99x27+88x26+5

60、5x25 +36x32+24x31+63x34+27x33+90 x37+80 x36+50 x35 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 x14+x24+x34 = 1 x15+x25+x35 = 1 x16+x26+x36 = 1 x17+x27+x37 = 1 .X22 - X21 = 0X14 - X13 =0X24