生产运作-生产与服务运作管理中的优化问题概述(ppt 160页)

优化建模 生产与服务运作管理中的优化问题 优化建模与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元/吨；购买量超过500吨但不超 过1000吨时，超过500吨的部分8000元/吨；购买 量超过1000吨时，超过1000吨的部分6000元/吨。 该公司应如何安排原油的采购和加工。 优化建模 5.1.2建立模型 问题分析 安排原油采购、加工的目标是利润最大，题目中给 出的是两种汽油的售价和原油A的采购价，利润为 销售汽油的收入与购买原油A的支出之差。这里的 难点在于原油A的采购价与购买量的关系比较复杂 ，是分段函数关系，能否及如何用线性规划、整数 规划模型加以处理是关键所在。 优化建模 模型建立设原油A的购买量为x（吨），根据题目所给数据， 采购的支出c(x)可表为如下的分段线性函数（以下价格以 千元/吨为单位）： (1) 设原油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)， 一般的非线性规划软件也难以输入和求解。能不能想办法 将该模型化简，从而用现成的软件求解呢？ 优化建模 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)，(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 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）转化为线性约束 令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 优化建模 运行该程序得到： 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轴上的分点为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/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) 0时取值1, 否则取值0. 在上述数学符号中，只有 为为决策变变量; 其余均为为已知的计计划参数。 优化建模 优化建模 目标函数 这个问题的目标是使生产准备费用和库存费用 的总和最小。因此，目标函数应该是每个项 目在每个时段上的生产准备费用和库存费用 的总和，即 (28) 约束条件 这个问题中的约束有这么几类：每个项目的物流 应该守恒、资源能力限制应该满足、每时段生 产某项目前必须经过生产准备和非负约束 （ 对Yi,j是0-1约束）。 优化建模 (29) 资源能力限制比较容易理解，即 (30) 所谓物流守恒（假设Ii,0 =0） 优化建模 (31) 每时段生产某项目前必须经过生产准备，也就是说当Xit=0 时Yit=0；Xit0时Yit=1。这本来是一个非线性约束，但是 通过引入参数M（很大的正数，表示每个项目每个时段 的最大产量）可以化成线性约束，即： 总结: 这个问题的优化模型就是在约束（29）（30 ）（31）下使目标函数（28）达到最小。 优化建模 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 ! 需求; 40010009010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 5 0 0 0 0 0 0 7 0 0 0 0 0 0 0 9 0 0 0 0 0 0 11 0 0 0 0 0 0 0 13 0 0 0 0 0 0 15 0 0 0 0 ! 数据结束; 优化建模 对本例，A的外部总需求为240，所以任何项目 的产量不会超过240715= 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 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切割12根原料钢管，按照模式5切 割15根原料钢管，共27根，总余料量为27米。 显然，在总余料量最小的目标下，最优解将是 使用余料尽可能小的切割模式（模式2和5的余 料为1米），这会导致切割原料钢管的总根数较 多。 优化建模 2. 将（33）（36）构成的整数线性规划模型（ 加上整数约束）输入LINDO： 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 = 15 end gin 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 =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 Cost X1 10.00000 1.000000 X2 10.00000 1.000000 X3 8.000000 1.000000 R11 2.000000 0.000000 R12 3.000000 0.000000 R13 0.000000 0.000000 R21 1.000000 0.000000 R22 0.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 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/14/:LENGTH,NUM; ! 定义基本集合NEEDS及其属性LENGTH,NUM; CUTS/13/:X; ! 定义基本集合CUTS及其属性X; PATTERNS(NEEDS,CUTS):R; ! 定义派生集合PATTERNS（这是一个稠密集合）及其属性R; ENDSETS DATA: LENGTH=4 5 6 8; NUM=50 10 20 15; CAPACITY=19; ENDDATA min=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.3.2易拉罐下料问题 例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种冲压模式下的余 料损失，和不配套的罐身和底、盖造成的原料损失。按照前面 的计算及表2的结果，总损失为0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。 优化建模 于是，决策目标为 (47) 约束条件 时间约束：每周工作时间不超过40小时=144000（秒），由表2最后一列得 (48) 原料约束： 每周可供使用的规格1、2的镀锡板原料分别为50000张和20000张，即 (49) (50) 优化建模 配套约约束： 由表2一周生产产的罐身个数为为x1 + 2x2 + 4x4, 一周 生产产的底、盖个数为为10x1 + 4x2 + 16x3+ 5x4，因为应为应 尽可 能将它们们配套组组装成易拉罐销销售。所以y1满满足 (51) 这时这时 不配套的罐身个数y2，和不配套的底、盖个数y3应为应为 (52) (53) 优化建模 （47）（53）就是我们得到的模型，其中（51）是一个非线性关系， 不易直接处理， 但是它可以等价为以下两个线性不等式： (54) (55) 模型求解 将模型（47）（50）和（52）（55）直接输入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.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 优化建模 图图5-4 模型中数据不平衡的警告信息 优化建模 这这个结结果可靠吗吗？由于LINDO警告模型中数据之间间的数 量级级差别别太大，所以我们们可以进进行预处预处 理，缩缩小数据之 间间的差别别。实际实际 上，约约束（48）（50）中右端项项的数 值过值过 大（与左端的系数相比较较），LINDO在计计算中容易 产产生比较较大的误误差，所以出现现此警告信息。 为为了解决这这一问题问题 ，可以将所有决策变变量扩扩大10000倍 （相当于xi以万次为单为单 位，yi以万件为单为单 位）。此时时，目 标标（47）可以保持不变变（记记住得到的结结果单单位为为万元就 可以了），而约约束（48）（50）改为为 (56) (57) (58) 优化建模 将模型（47）和（52）（58）输入LINDO: ! 易拉罐下料：均衡数据 Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3 s.t. 1.5x1 + 2.0x2 + 1.0x3 +3.0x4 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 =0 x1 + 2x2 + 4x4 - y1 - y2 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0 end 优化建模 求解得到： OBJECTIVE FUNCTION VALUE 1) 0.4298337 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名同学到一家公司参加三个阶段的面试 ：公司要求每个同学都必须首先找公司秘书初试，然 后到部门主管处复试，最后到经理处参加面试，并且 不允许插队（即在任何一个阶段4名同学的顺序是一 样的）。由于4名同学的专业背景不同，所以每人在 三个阶段的面试时间也不同，如表5-5所示（单位： 分钟）。这4名同学约定他们全部面试完以后一起离 开公司。假定现在时间是早晨8：00，请问他们最早 何时能离开公司？ 优化建模 表5-5 面试时间要求 秘书书初试试主管复试试经经理面试试 同学甲131520 同学乙102018 同学丙201010 同学丁81015 优化建模 建立模型 实际上，这个问题就是要安排4名同学的面试顺 序，使完成全部面试所花费的时间最少。 记tij为第i名同学参加第j阶段面试需要的时间(已 知)，令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; i= x13+ t13; T = x23+ t23; T = x33+ t33; T = x43+ t43; x11+ t11 = 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) tan(cita - sigma) ); for(VOR: (xx-x)/(yy-y) sqrt(sqr(xx-x4)+sqr(yy-y4) ; END 优化建模 用LINGO求解上述模型，LINGO系统返回的信 息是这个模型没有可行解。其实这显然是一个不正确 的信息，可能只是由于求解空间太大，LINGO没有 找到可行解。其实，我们可以想象这个问题的可行解 大致就该在模型1中得到的最优解附近，因此可以把 这个解作为初始值告诉LINGO。例如，在上面程序 中增加以下三行： INIT: xx, yy = 980.6926, 731.5666; ENDINIT 优化建模 此时求解，马上就得到XX的最小值为974.8424。 类似地（只需要换换目标函数就可以了），可得到 XX的最大值为982.2129，YY的最小值为717.1587， YY的最大值为733.1944。 因此，最后得到的解是一个比较大的矩形区域， 大致为975，982717，733。 优化建模 模型3及求解 模型2得到的只是一个很大的矩形区域，仍不能 令人满意。实际上，模型2中假设设备的测量误差是 均匀分布的，这是很不合理的。一般来说，在多次测 量中，应该假设设备的测量误差是正态分布的，而且 均值为0。本例中给出的精度i可以认为是测量误差 的标准差(也可以是与标准差成比例的一个量，如标 准差的3倍或6倍等)。 在这种理解下，用各自的误差限i对测量误差进 行无量纲化(也可以看成是一种加权法)处理是合理的 ，即求解如下的无约束优化问题更合理： 优化建模 其中 i=1, 2, 3, 由于目标函数是平方和的形式，因此这是一个非 线性最小二乘拟合问题。相应的LINGO程序为(仍然 将迭代初值告诉LINGO)： 优化建模 MODEL: TITLE 飞机定位模型3; SETS: VOR/13/: x, y, cita, sigma; ENDSETS DATA: x, y, cita, sigma = 74613932.813470.0140 6293750.787140.0105 15712595.393070.0227; x4 y4 d4 sigma4 = 155987864.3 2.0; ENDDATA INIT: xx, yy = 980.6926, 731.5666; ENDINIT 优化建模 ! XX,YY表示飞机坐标; !min = sum(VOR: sqr(xx-x)/(yy-y) - tan(cita)/sigma) ) + sqr(d4 - sqrt(sqr(xx-x4)+sqr(yy-y4)/sigma4 ); min = sum(VOR: (xx-x)/(yy-y) - tan(cita)/sigma)2 ) + (d4 - (xx-x4)2+(yy-y4)2).5 )/sigma4 )2; END Global optimal solution found. Objective value: 2.600539 Model Title: 飞机定位模型3 Variable Value Reduced Cost XX 980.2106 0.000000 YY 727.3056 0.000000 计算结果为： 即飞机坐标为(980.21, 727.31)，这个解对应的目标函 数值大约为2.6。 优化建模 这个误差为什么比模型1的大很多？这是因为模 型1中使用的是绝对误差，而这里使用的是相对于精 度i的误差。分母i很小，所以相对误差比绝对误差 大，这是可以理解的。其实，可以认为此时的目标函 数是四个标准正态分布的误差平方和，只要在4以内 都是合理的。 优化建模 5.5.2飞行计划问题 例5.8 这个问题是以第二次世界大战中的一个实 际问题为背景，经过简化而提出来的。在甲乙双方的 一场战争中，一部分甲方部队被乙方部队包围长达4 个月。由于乙方封锁了所有水陆交通通道，被包围的 甲方部队只能依靠空中交通维持供给。运送4个月的 供给分别需要2, 3, 3, 4次飞行，每次飞行编队由50架 飞机组成(每架飞机需要3名飞行员)，可以运送10万吨 物资。每架飞机每个月只能飞行一次，每名飞行员每 个月也只能飞行一次。在执行完运输任务后的返回途 中有20%的飞机会被乙方部队击落，相应的飞行员也 因此牺牲或失踪。 优化建模 在第1个月开始时，甲方拥有110架飞机和330名 熟练的飞行员。在每个月开始时，甲方可以招聘新飞 行员和购买新飞机。新飞机必须经过一个月的检查后 才可以投入使用，新飞行员必须在熟练飞行员的指导 下经过一个月的训练才能投入飞行。每名熟练飞行员 可以作为教练每个月指导20名飞行员(包括他自己在 内)进行训练。每名飞行员在完成一个月的飞行任务 后，必须有一个月的带薪假期，假期结束后才能再投 入飞行。已知各项费用(单位略去)如下表所示，请你 为甲方安排一个飞行计划。 优化建模 如果每名熟练飞行员可以作为教练每个月指导不 超过20名飞行员(包括他自己在内)进行训练，模型和 结果有哪些改变？ 第1个月第2个月 第3个月 第4个月 新飞飞机价格 200.0195.0190.0185.0 闲闲置的熟练飞练飞 行员报员报 酬 7.06.96.86.7 教练练和新飞飞行员报员报 酬(包括培训费训费 用 ) 10.09.99.89.7 执执行飞飞行任务务的熟练飞练飞 行员报员报 酬 9.08.99.89.7 休假期间间的熟练飞练飞 行员报员报 酬 5.04.94.84.7 优化建模 问题分析 这个问题看起来很复杂，但只要理解了这个例子 中所描述的事实，其实建立优化模型并不困难。首先 可以看出，执行飞行任务以及执行飞行任务后休假的 熟练飞行员数量是常数，所以这部分费用(报酬)是固 定的，在优化目标中可以不考虑。 决策变量 设4个月开始时甲方新购买的飞机数量分别为x1, x2, x3, x4架, 闲置的飞机数量分别为y1, y2, y3, y4架。4个 月中, 飞行员中教练和新飞行员数量分别为u1, u2, u3, u4人, 闲置的的熟练飞行员数量分别为 v1, v2, v3, v4人。 优化建模 目标函数 优化目标是: Min 200x1+195x2 +190x3+185x4+10u1+9.9u2 +9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4 约束条件 需要考虑的约束包括： 1）飞机数量限制：4个月中执行飞行任务的飞机 分别为100, 150, 150, 200架，但只有80, 120, 120, 160 架能够返回供下个月使用。 第1个月：100+ y1=110 第2个月：150+ y2=80+ y1+ x1 第3个月：150+ y3=120+ y2+ x2 第4个月：200+ y4=120+ y3+ x3 优化建模 2）飞行员数量限制：4个月中执行飞行任务的熟 练飞行员分别为300, 450, 450, 600人，但只有240, 360 ，360, 480人能够返回(下个月一定休假)。 第1个月：300 +0.05 u1+ v1=330 第2个月：450 +0.05 u2+ v2= u1+ v1 第3个月：450 +0.05 u3+ v3= u2+ v2+240 第4个月：600 +0.05 u4+ v4= u3+ v3+360 最后，自然要求x1, x2, x3, x4 , y1, y2, y3, y4, u1, u2, u3, u4 , v1, v2, v3, v4 0 且为整数。 优化建模 于是，这个优化模型很容易输入LINDO： MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2 +9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4 s.t.y1=10 y1+ x1 - y2 =70 y2+ x2 - y3 =30 y3+ x3 - y4=80 0.05 u1+ v1=30 u1 + v1 - 0.05 u2 - v2 = 450 u2 + v2 - 0.05 u3 - v3 = 210 u3 + v3 - 0.05 u4 - v4 = 240 end GIN 16 优化建模 用LINDO求解得到： OBJECTIVE FUNCTION VALUE 1) 42324.40 VARIABLE VALUE REDUCED COST X1 60.00