《优化建模与LINGO第5》由会员分享，可在线阅读，更多相关《优化建模与LINGO第5（160页珍藏版）》请在金锄头文库上搜索。
1、 优化建模优化建模生产与服务运作管理中的优化问题生产与服务运作管理中的优化问题优化建模与优化建模与LINDO/LINGOLINDO/LINGO软件软件第第5 5章章巳阀演奄淖钠迪颈蚤伏钻窖娩会乓糠嗽杭驱故箍褐躯读爵略恳域尺乾警猖优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模内容提要内容提要5.1 5.1 生产与销售计划问题生产与销售计划问题5.2 5.2 有瓶颈设备的多级生产计划问题有瓶颈设备的多级生产计划问题5.3 5.3 下料问题下料问题5.4 5.4 面试顺序与消防车调度问题面试顺序与消防车调度问题5.5 5.5 飞机定位和飞行计划问题飞机定位和飞行计划问题鸭孝桨艺谓
2、皂玉喂甘焕窃篓整鸭蝉认娠矮磊遭胁葵涕波畅针东炯彦才甲鸟优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.1 生产与销售计划问题生产与销售计划问题怀技内巷芦疮联代泼潜聚嘘黔褂寺尝势江卿毁袍线拾谨舀蟹威疫垦棠抗但优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.1.15.1.1问题实例问题实例例例5.15.1某公司用两种原油（某公司用两种原油（A A和和B B）混合加工成两种）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油汽油（甲和乙）。甲、乙两种汽油含原油A A的最低的最低比例分别为比例分别为50%50%和和60%60%，每吨售价分别为，每吨售价分别为
3、48004800元和元和56005600元。该公司现有原油元。该公司现有原油A A和和B B的库存量分别为的库存量分别为500500吨和吨和10001000吨，还可以从市场上买到不超过吨，还可以从市场上买到不超过15001500吨吨的原油的原油A A。原油。原油A A的市场价为：购买量不超过的市场价为：购买量不超过500500吨吨时的单价为时的单价为1000010000元元/ /吨；购买量超过吨；购买量超过500500吨但不超吨但不超过过10001000吨时，超过吨时，超过500500吨的部分吨的部分80008000元元/ /吨；购买吨；购买量超过量超过10001000吨时，超过吨时，超过10
4、001000吨的部分吨的部分60006000元元/ /吨。吨。该公司应如何安排原油的采购和加工。该公司应如何安排原油的采购和加工。凄么槐醛芝磨叭象裸颅俏奉熙位闭赖喘浩掷婴亿吧穗秉惟寓春冤幂僚览财优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.1.25.1.2建立模型建立模型问题分析问题分析 安排原油采购、加工的目标是利润最大，题目中给安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油出的是两种汽油的售价和原油A A的采购价，利润为的采购价，利润为销售汽油的收入与购买原油销售汽油的收入与购买原油A A的支出之差。这里的的支出之差。这里的难点在于原油难点在
5、于原油A A的采购价与购买量的关系比较复杂，的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。划模型加以处理是关键所在。癌茫锡攫颤慑旬瓷暇速篷秽凄艇镑够冕勺示扼厅惰粳迅阑千怯漂蓄漏菇询优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模型建立设原油模型建立设原油A A的购买量为的购买量为x x（吨），根据题目所给数据，（吨），根据题目所给数据，采购的支出采购的支出c(x)c(x)可表为如下的分段线性函数（以下价格以可表为如下的分段线性函数（以下价格以千元千元/ /吨为单位）：吨为单位
6、）：(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)瘟涵糜瓮鹅又艘忌严叔桨贴聪橡薛汕耽阿意悟弄蚤伞禄膜烘瑟胸删啊析瑟优化建模与LINGO第5优化建
7、模与LINGO第5 优化建模优化建模约束条件包括加工两种汽油用的原油约束条件包括加工两种汽油用的原油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) )，一般的非线性规划软件也难以输入和求
8、解。能不能想办法一般的非线性规划软件也难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？将该模型化简，从而用现成的软件求解呢？塑考口孩孝叫蟹剿呆房栖柜饥俞冉吝壁瞻选窄幸深彩挪肝帖鲁靴坑帜特佬优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.1.3 求解模型 3 3种解法种解法第第1种解法种解法 将原油将原油A的采购量的采购量x分解为三个量，即用分解为三个量，即用x1，x2，x3分别表示以价格分别表示以价格10、8、6千元千元/吨采购的原油吨采购的原油A的吨的吨数，总支出为数，总支出为c(x) = 10x1+8x2+6x3，且，且(9)这时目标函数（这时目标函
9、数（2）变为线性函数：）变为线性函数：(10)应该注意到，只有当以应该注意到，只有当以10千元千元/吨的价格购买吨的价格购买x1=500（吨）时，才能以（吨）时，才能以8千元千元/吨的价格购买吨的价格购买x2（0），这个条件可以表示为），这个条件可以表示为(11)锻肋慕骗碗阜壶滑靶届萧悉溉驹随蹿马劝庆未卢帮宰姐棒追骑己膛陋裕窿优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模同理，只有当以同理，只有当以8 8千元千元/ /吨的价格购买吨的价格购买x x2 2=500=500（吨）时，（吨）时，才能以才能以6 6千元千元/ /吨的价格购买吨的价格购买x x3 3（00），于是），
10、于是(12)(12)此外，此外，x x1 1，x x2 2，x x3 3的取值范围是的取值范围是(13)(13)冉则杜袁猩糊瞄洱异批汕绸拱跃孕梢瀑心野新蛾糕左茹盟馁蝎蔚抚伞沦附优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模由于有非线性约束由于有非线性约束(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
11、 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坊藤抚趋喷娃畦匝气嫁诧爷是给楷博汉烤乖唇荚佰械伎艇攀亚彰乐枕肄那优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 将文件存储并命名为将文件存储并命名为exam0501a.lg4exam0501a.lg4，执行菜单命令执行菜单命令“LINGO|SolveLINGO|Solve”，运行该程序得到：，运行该程序得到： Local optimal
12、 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素问棘诺同洁峪弟尺撵悟陛睦鲁竭皇恕毒絮旷介乃嫩块诡肮妮鬼努政事
13、咬优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模最优解最优解: : 用库存的用库存的500500吨原油吨原油A A、500500吨原油吨原油B B生产生产10001000吨汽油甲，不购买新的原油吨汽油甲，不购买新的原油A A，利润为，利润为48004800（千元）（千元） 但是此时但是此时LINGOLINGO得到的结果只是一个得到的结果只是一个局部最优解局部最优解可以用菜单命令可以用菜单命令“LINGO|OptionsLINGO|Options”在在“Global Global SolverSolver”选项卡上启动全局优化（选项卡上启动全局优化（Use Global Us
14、e Global SolverSolver）选项，然后重新执行菜单命令）选项，然后重新执行菜单命令“LINGO|SolveLINGO|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
15、: 187乡荔株粹氨悟盖医拼兴祝退炎峨撵幼契痈腻豌斤熔紧办噶凉伍奸包迸瓤冻优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模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得到的结果是一个得到的结果是一个全局最优解
16、全局最优解（Global optimal solutionGlobal optimal solution）：购买）：购买10001000吨原油吨原油A A，与库存的，与库存的500500吨原油吨原油A A和和10001000吨原油吨原油B B一起，共生产一起，共生产25002500吨汽油乙，利润为吨汽油乙，利润为50005000（千元），高于刚刚得（千元），高于刚刚得到的局部最优解对应的利润到的局部最优解对应的利润48004800（千元）。（千元）。阳尊项斜慧曼举刁这昭桑栅瘟吾峙过允融上灼帮罪泛蛮抓丙缆漓蛀瞪箔隔优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模第第2 2种解法
17、种解法: : 引入引入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)客馋仔顾桃撵拨严宇琐胶窃办蛇菊倔醛勉吩炙胸呼掩析摧哦两骗右硬幼朝优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模（3 3） （1010），（），（1313） （1717）构成混合整数线性）构成混合整数线性规划
18、模型，将它输入规划模型，将它输入LINDOLINDO软件：软件：盾符飘焕曳寸扳糖辨其碍辆怕朽赎贫锚偷岭近降静胳创形淡澳耽夫恋桔栓优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模Max 4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3stx-x1-x2-x3=0x11+x12-x500x21+x220 0.4x12-0.6x220 x1-500y10 x2-500y20 x3-500y30x2-500y30 endint y1int y2int y3摄沂迂熄姜障竖戒冉号肛粳抗馋楷劈缓篷边碰驮紫差疾帛哪炭违界糙朋硕优化建模与LINGO第5优化建模与
19、LINGO第5 优化建模优化建模运行该程序得到：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
20、 0.000000 0.400000 X 1000.000000 0.000000这个结果与前面非线性规划模型用全局优化得到的结果相同。这个结果与前面非线性规划模型用全局优化得到的结果相同。鼠忽治追雷倦胃存官冶缮番帚罢粳慑呕目拼估捏褪傲葫吴皱涡练谁展氯踊优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模第第3 3种解法种解法 直接处理分段线性函数c(x)。（1）式表示的函数c(x)如图5-1。c(x)x1200090005000050010001500图图5-1 分段线性函数分段线性函数c(x)图形图形蛰何碗罚疽疏嚏篡篓羞钓证鸦扇糊药兹拿抽耕涅靖燕砒熬信确担硕墒惰蚊优化建模与L
21、INGO第5优化建模与LINGO第5 优化建模优化建模记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)。
22、为了表示x在哪个小区间，引入0-1变量yk(k=1,2,3)，当x在第k个小区间时，yk=1，否则，yk=0。这样, z1, z2, z3, z4, y1, y2, y3应满足(18)(19)(20)手瞎圭培茵洞陪钒武历吠面嘉蜀佃戌贰呛庸斯维拈厨谬碧松眷凡偿骤斥弄优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模此时x和c(x)可以统一地表示为（2）（10），（18）（22）也构成一个混合整数线性规划模型，可以用LINDO求解。不过，我们还是将它输入LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的LINGO模型如下：(22)汽
23、改老所温蛇锐痹竹曳缺胡男募萨倔溢肢洒现轮嚷拴镣诵枢八扰烁阴峙筋优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模输入的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卒旭御栅不韦契荷播仟烩仪底烂掺迁闺盔恢氰勤孺俗央浊养戏偶耘炭闹妆优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模Max= 4.8*x11 + 4.8*x21 + 5.6*x
24、12 + 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.在上述数学符号中，只有在上述数学符号中，只有为为决策决策变变量量; 其余均其余均为为已知的已知的计计划参数。划参数。赌敖缓欠肾痊嘛纤巫骸极络轧桃瑞撮鸳饯尺内司压兑汛缺字腹膝愿烤痞申优化建模与LINGO第5优化建模与LINGO第5 优化建模优化
25、建模酗概溺京草件怀悄断陨蚁妻换答捍臂衰吕际恬恤胖贞五盛锭党站徽车裳羊优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模目标函数目标函数 这个问题的目标是使生产准备费用和库存费用这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项的总和最小。因此，目标函数应该是每个项目在每个时段上的生产准备费用和库存费用目在每个时段上的生产准备费用和库存费用的总和，即的总和，即(28)约束条件约束条件这个问题中的约束有这么几类：每个项目的物流这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生应该守恒、资源能力限制应该满足、每时段生产某项目
26、前必须经过生产准备和非负约束产某项目前必须经过生产准备和非负约束 （对（对Yi,j是是0-1约束）。约束）。氢级透蹭惜塞筑绦钠犯颤梦诞茬轿辜侧址掠灼稚花躯交沿潭街雄革簇肪揪优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模(29)资源能力限制比较容易理解，即资源能力限制比较容易理解，即(30)所谓物流守恒（假设所谓物流守恒（假设Ii,0 =0） 芽蛹巴秉黎价似园虚早晓窒伊败疗篙阐垢播耗佩凶翰疹狰仙累棚酒拎虑泞优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模(31)每时段生产某项目前必须经过生产准备，也就是说当每时段生产某项目前必须经过生产准备，也就是说当Xit
27、=0时时Yit=0；Xit0时时Yit=1。这本来是一个非线性约束，但是。这本来是一个非线性约束，但是通过引入参数通过引入参数M（很大的正数，表示每个项目每个时段（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：的最大产量）可以化成线性约束，即： 总结总结: : 这个问题的优化模型就是在约束这个问题的优化模型就是在约束（2929）（）（3030）（）（3131）下使目标函数（）下使目标函数（2828）达到最）达到最小。小。 呸棋遁寸挠弗纺膏莱诵入故疗舆茸原缝壁沙驶绚则牢漱风汗蹋梨垃荤问跌优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.2.3 5.2.3
28、求解模型求解模型本例生产项目总数本例生产项目总数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
29、可以略去下标可以略去下标k，其数值，其数值就是表就是表5-1中的第中的第3行的数据；而行的数据；而ak,I,t只与项目只与项目i有关，有关，而不随时段而不随时段t变化，所以可以同时略去下标变化，所以可以同时略去下标k和和t，即，即a2=5，a3=8（其他（其他ai为为0）。从图）。从图6-2中容易得到项中容易得到项目目i的直接后继项目集合的直接后继项目集合S(i)和消耗系数。和消耗系数。权夷节钡徘手用柄王抿歼腊拷沸增呐札豪然手胎徒攫谣陈膀止鳃殊注烙价优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模准备以下的数据文件（文本文件准备以下的数据文件（文本文件exam0502.LDT
30、，可，可以看到其中也可以含有注释语句）：以看到其中也可以含有注释语句）：! 项目集合;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踊属粹继棍豆宅杏廉涝舆赁窘束惠当酮括伏张闭嗓陈坝铀苹磋投选捻迸顿优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模! 能力;1000005000 5000 1000 1000! 生产准备费;4005001000 300200400100! 库存费;120.61.00.04 0.03 0.04
31、 0.04! 对能力的消耗系数；0580000牺娘体轿福牧迸脾画憋豺颤坎共连拒郡韩巡寻穿博鼓诽滦孽纠碰赵乱冒报优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模! 项目间的消耗系数: 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! 数据结束;属筑词帆惑忘消威族往忍互拿都徒戍猖缆来健记韧钦袋刑佩括麓撒苗呼傀优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模对本例，对本例，A的外部总需求为的
32、外部总需求为240，所以任何项目的，所以任何项目的产量不会超过产量不会超过24071525000（从图（从图6-2可以可以知道，这里知道，这里715已经是每件产品已经是每件产品A对任意一个对任意一个项目的最大的消耗系数了），所以取项目的最大的消耗系数了），所以取M=25000就已经足够了。就已经足够了。本例中的具体模型可以如下输入本例中的具体模型可以如下输入LINGO软件：软件：MODEL:TITLE 瓶颈设备的多级生产计划;! 从文本文件exam0502.LDT中读取数据;鸽噪拍脐铃瘸翼龙捍煤硒狞诺托套蜕辟红删郎娱尖禄诫略魔阔够壶豪搔拆优化建模与LINGO第5优化建模与LINGO第5 优化建
33、模优化建模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变量，IN
34、V = 库存;PXT( PART, TIME): Demand, X, Y, Inv;ENDSETS妆陡戚践膝傀深母寅卑赤摈军陪暴项颂毯穿诡拐幻透适溃锣磅尉斗迂促俞优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模! 目标函数;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)
35、);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) ); 拐槐捣店潭昭窟番缉虎涩须伺呆篙梯寿窗治疾俞蛛锥障遍虎俭铂蜗骆捣僻优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模! 其他约束;M = 25000;FOR( PXT(i,t): X(i,t) = 50 x2 + 2x4 + x5 + 3x6 =
36、20 x3 + x5 + 2x7 = 15endgin 7磊姻袜山砖策策映狙吱濒吧隅瑰舰章丑讨泽域留假辰暂拷慷泄敌仁炳瘤蛀优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模求解可以得到最优解如下：求解可以得到最优解如下： 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.0000
37、00 1.000000 X7 0.000000 3.000000 躲潜站幌嫂僧破街沿兢赦蓬痛滞阳烈月聊替帅磅蠕三盏程恶迄酵剁伶卷涉优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模即按照模式即按照模式2 2切割切割1212根原料钢管，按照模式根原料钢管，按照模式5 5切切割割1515根原料钢管，共根原料钢管，共2727根，总余料量为根，总余料量为2727米。米。显然，在总余料量最小的目标下，最优解将是显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式使用余料尽可能小的切割模式（模式2 2和和5 5的余的余料为料为1 1米），这会导致切割原料钢管的总根数较米
38、），这会导致切割原料钢管的总根数较多。多。尸傅贮雪踊板筹歌烘颗椭铸胞更贱檀柜参五宫颧趾在靠胚论凉癌斗贰腕嚣优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模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 +
39、 2x7 = 15endgin 7琼枚湘籽霉芜肉睬酋凛茅锡邀佳欧垮虎霜诞烹树当寐绿逢鲤廉挛毕款牢案优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模求解，可以得到最优解如下：求解，可以得到最优解如下：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
40、X7 5.000000 1.000000婴抠做皇拒种仲孟民界幸画拼曹武坎泽凰煮露谬庙遏氖磅秸倒亮胃彪愚塑优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模即按照模式即按照模式2切割切割15根原料钢管，按模式根原料钢管，按模式5切割切割5根，按模根，按模式式7切割切割5根，共根，共27根，可算出总余料量为根，可算出总余料量为35米。与上面得米。与上面得到的结果相比，总余料量增加了到的结果相比，总余料量增加了8米，但是所用的原料钢米，但是所用的原料钢管的总根数减少了管的总根数减少了2根。在余料没有什么用途的情况下，根。在余料没有什么用途的情况下，通常选择总根数最少为目标。通常选择总
41、根数最少为目标。宏狮激炮揩猴蓖诌僳闰款草蛮虽燕金捡婆股迭惧叮柏蓟荒彻表荷汀陕巾箱优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模问题问题2）的求解）的求解问题分析问题分析 按照解问题按照解问题1）的思路，可以通过枚举法首先确）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。性的方法。同同1
42、）类似，一个合理的切割模式的余料不应该大于或等于）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为客户需要的钢管的最小尺寸（本题中为4米），切割计划中米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于以合理的切割模式的余量不能大于3米。此外，这里我们仅米。此外，这里我们仅选择总根数最少为目标进行求解。选择总根数最少为目标进行求解。 锨挪灾凉幂棉剩神汕了千邢黔识虚烧账关铂句诛闻假毋鹃网坷典趣请源落优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模型建立
43、模型建立决策决策变变量量 由于不同切割模式不能超由于不同切割模式不能超过过3种，可以用种，可以用xi 表示表示按照第按照第i种模式（种模式（i=1, 2, 3）切割的原料）切割的原料钢钢管的根数，管的根数，显显然它然它们应们应当是非当是非负负整数。整数。设设所使用的第所使用的第i种切割模式下种切割模式下每根原料每根原料钢钢管生管生产产4米米长长、5米米长长、6米米长长和和8米米长长的的钢钢管数量分管数量分别为别为r1i, r2i, r3i, r4i（非非负负整数整数）。）。 决策目决策目标标 以切割原料以切割原料钢钢管的管的总总根数最少根数最少为为目目标标，即目，即目标为标为（37）谤檀膝闲便
44、面磺二菌遥便焚家祝抛戌喀磕诱钥状舆雅莱邑历饺始潍庸查痔优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模约约束条件束条件 为满为满足客足客户户的需求，的需求，应应有有(38)(39)(40)(41)早痉彪挫币诧行硒搓儿恶利咯乳兽捍谷惟北定泌皂撅鹿晋痘龋讥脚淫妨蹬优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模每一种切割模式必每一种切割模式必须须可行、合理，所以每根原料可行、合理，所以每根原料钢钢管的管的成品量不能超成品量不能超过过19米，也不能少于米，也不能少于16米（余量不能大于米（余量不能大于3米），于是米），于是(42)(43)(44)吼瞧袜曾权掠兆窃嚷
45、零谬堑翠蛙级迎乱叛骇泥捕室畦磋暇碱陨蛹好唬蘸饶优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模型求解模型求解（37）（44）构成）构成这这个个问题问题的的优优化模型。由于在化模型。由于在（38）（41）式中出）式中出现现了决策了决策变变量的乘量的乘积积，所以，所以这这是一是一个整数非个整数非线线性性规规划模型，划模型，虽虽然用然用LINGO软软件可以直接求件可以直接求解，但我解，但我们发现们发现在在较较低版本的低版本的LINGO软软件中需要运行很件中需要运行很长时间长时间也也难难以得到最以得到最优优解。解。为为了减少运行了减少运行时间时间，可以增加，可以增加一些一些显显然的
46、然的约约束条件，从而束条件，从而缩缩小可行解的搜索范小可行解的搜索范围围。例如，由于例如，由于3种切割模式的排列种切割模式的排列顺顺序是无关序是无关紧紧要的，所以不要的，所以不妨增加以下妨增加以下约约束：束：（45）防踩抱挥宴屎姬事三选渊弗晒呼衔完然蕉酸湾瓣职乌植跳砾临芦矗伍衅吐优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模又例如，我又例如，我们们注意到所需原料注意到所需原料钢钢管的管的总总根数有着明根数有着明显显的的上界和下界。首先，无上界和下界。首先，无论论如何，原料如何，原料钢钢管的管的总总根数不根数不可能少于可能少于 （根）（根）其次，考虑一种非常特殊的生产计划：第
47、一种切割模式下只其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产生产4米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成4根根4米钢管，为满足米钢管，为满足50根根4米钢管的需求，需要米钢管的需求，需要13根原料钢管；第二种切割模根原料钢管；第二种切割模式下只生产式下只生产5米、米、6米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成1根根5米米钢管和钢管和2根根6米钢管，为满足米钢管，为满足10根根5米和米和20根根6米钢管的需米钢管的需求，需要求，需要10根原料钢管；根原料钢管；绑胜倘束韩赚处氦户夫察尽卸脆扎咱壁遏著禄何司壤唉玩面阁怀霓瓜箭敖优化建模与LINGO第5优化建模与L
48、INGO第5 优化建模优化建模第三种切割模式下只生产第三种切割模式下只生产8米钢管，一根原料钢管切割成米钢管，一根原料钢管切割成2根根8米钢管，为满足米钢管，为满足15根根8米钢管的需求，需要米钢管的需求，需要8根原料钢管。根原料钢管。于是满足要求的这种生产计划共需于是满足要求的这种生产计划共需13+10+8=31根原料钢根原料钢管，这就得到了最优解的一个上界。所以可增加以下约管，这就得到了最优解的一个上界。所以可增加以下约束：束：(46)将（37）（46）构成的模型输入LINGO如下：访次幽陈弱秦搐客甫毡卤慨晋窘厅缀屡垂寡睹虱悼烩澄虹悍诧癣助儿瓣绍优化建模与LINGO第5优化建模与LINGO
49、第5 优化建模优化建模将（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
50、*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第5优化建模与LINGO第5 优化建模优化建模经过经过LINGO求解，得到求解，得到输输出如下：出如
51、下： Local optimal solution found. Objective value: 28.00000 Extended solver steps: 72 Total solver iterations: 3404 Model Title: 钢钢管下料管下料-最小化最小化钢钢管根数的管根数的LINGO模型模型奋颜属惭仅廉挎激灯凤斗惦频元跺徽高会是复略巷弘峡懂耸涡柠氓咨蛀举优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 Variable Value Reduced CostX1 10.00000 1.000000X2 10.00000 1.000000X3 8.
52、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润藻淋垮俘口辆砰镭闸别香道汾黎剐烦改咬右吸宏调牟亩迸袄畦车谦灵记优
53、化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模即按照模式即按照模式1、2、3分分别别切割切割10、10、8根原料根原料钢钢管，使用管，使用原料原料钢钢管管总总根数根数为为28根。第一种切割模式下一根原料根。第一种切割模式下一根原料钢钢管管切割成切割成3根根4米米钢钢管和管和1根根6米米钢钢管；第二种切割模式下一根管；第二种切割模式下一根原料原料钢钢管切割成管切割成2根根4米米钢钢管、管、1根根5米米钢钢管和管和1根根6米米钢钢管；管；第三种切割模式下一根原料第三种切割模式下一根原料钢钢管切割成管切割成2根根8米米钢钢管。管。 如果充分利用如果充分利用LINGO建模建模语语言的
54、能力，使用集合和属性言的能力，使用集合和属性的概念，可以的概念，可以编编写以下写以下LINGO程序，程序，这这种方法更具有一种方法更具有一般的通用性，并有利于般的通用性，并有利于输输入更大入更大规规模的下料模的下料问题问题的的优优化模化模型：型：误栏嘲月糖害洽堑小床宛民伤晦瞄楚署惫暮沉监粟承阀擅皇虱琐空容夜御优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模model:Title 钢管下料钢管下料 - 最小化钢管根数的最小化钢管根数的LINGO模型模型;SETS: NEEDS/1.4/:LENGTH,NUM; ! 定义基本集合定义基本集合NEEDS及其属性及其属性LENGTH,
55、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) );礁梨捉淘澡姚厄维旱矮密窖东淫伤娄湘伙词尘舒碰痕鸵闲巨归骡贼乞玛犹优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模!目标函数目标函数;FOR(NEEDS(I): SUM(
56、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求解求解这这个模型，得到的个模型，得到的结结果与前
57、面的果与前面的结结果完全相同。果完全相同。豁喝区帮点骆慈涸纠诞愁孝蛔缘业羊学商娇镇靡挠间切桑默社克追怠半主优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.3.2易拉罐下料易拉罐下料问题问题例例5.4 某公司采用一套冲压设备生产一种罐装饮料的某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图5-3）。易拉罐为圆柱形，包括罐身、上盖和下底，罐）。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高身高10厘米，上盖和下底的直径均为厘米，上盖和下底的直径均为5厘米。该公司使厘米。该公司使用两种不同规格的镀
58、锡板原料，规格用两种不同规格的镀锡板原料，规格1的镀锡板为正方的镀锡板为正方形，边长形，边长24厘米；规格厘米；规格2的镀锡板为长方形，长、宽分的镀锡板为长方形，长、宽分别为别为32和和28厘米。由于生产设备和生产工艺的限制，厘米。由于生产设备和生产工艺的限制，对于规格对于规格1的镀镀锡板原料，只可以按照图的镀镀锡板原料，只可以按照图2中的模式中的模式1、2或或3进行冲压；对于规格进行冲压；对于规格2的镀锡板原料只能按照模式的镀锡板原料只能按照模式4进行冲压。使用模式进行冲压。使用模式1、2、3、4进行每次冲压所需要进行每次冲压所需要的时间分别为的时间分别为1.5、2、1、3（秒）。（秒）。邑
59、樱想伐亢收己讨着丘体供税陋辐砚瀑隋兄田刑兔愁典抛壁脯腑眷桔姜姨优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模式1模式2模式3模式4上盖下底罐身图5-3 易拉罐下料模式利奏屈颓嚏案最最版期苑檬吭劲龚腻裙窄咽抵眼运雏滴型荣鸥撇略讥蠕汾优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模该工厂每周工作该工厂每周工作40小时，每周可供使用的规格小时，每周可供使用的规格1、2的镀锡板的镀锡板原料分别为原料分别为5万张和万张和2万张。目前每只易拉罐的利润为万张。目前每只易拉罐的利润为0.10元，元，原料余料损失为原料余料损失为0.001元元 / 厘米厘米2（如果周末有罐
60、身、上盖或（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。下底不能配套组装成易拉罐出售，也看作是原料余料损失）。工厂应如何安排每周的生产？工厂应如何安排每周的生产？已知上盖和下底的直径已知上盖和下底的直径d=5厘米，可得其面积为厘米，可得其面积为 19.6厘米厘米2菇涉择弊叁位讥饺吏歌闽仿绥驶揣脂良胳计汽立滓没胰铬射娜盗醇卑风掠优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模表表5-4 4种冲压模式的特征种冲压模式的特征罐身个数底、盖个数余料损失（厘米2）冲压时间（秒）模式1110222.61.5模式224183.32模式3016261.81模式
61、445169.53问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、盖的配套组装。鞭眩延场几继攒仪庸泊练龋恶摔酒厢扑娘溜凄熊拦赤料垒击斯措表引姚树优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模型建立模型建立决策变量决策变量 用用xi 表示按照第表示按照第i种模式的冲压次数（种模式的冲压次数（i=1, 2, 3, 4），），y1表示表示一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的原料损失，用原料损失，用y2表示不配套的罐身个数，表示不
62、配套的罐身个数，y3表示不配套的底、盖个数。表示不配套的底、盖个数。虽然实际上虽然实际上xi和和y1，y2，y3应该是整数。但是由于生产量相当大，可以应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。把它们看成是实数，从而用线性规划模型处理。决策目标决策目标 假设每周生产的易拉罐能够全部售出，公司每周的销假设每周生产的易拉罐能够全部售出，公司每周的销售利润是售利润是0.1y1。原料余料损失包括两部分：。原料余料损失包括两部分：4种冲压模式下的余种冲压模式下的余料损失，和不配套的罐身和底、盖造成的原料损失。按照前面料损失，和不配套的罐身和底、盖造成的原料损失。按照前
63、面的计算及表的计算及表2的结果，总损失为的结果，总损失为0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。 萝蕴搐芝似离牙瘴敛蠕瘩凹藉陷重墟姿咸嘻颗朔够丫帚幽凄六汹哨茨壕唱优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模于是，决策目标为于是，决策目标为(47)约束条件约束条件 时间约束：每周工作时间不超过时间约束：每周工作时间不超过40小时小时=144000（秒），由表（秒），由表2最后一列得最后一列得(48)原料约束：原料约束：每周可供使用的规格每周可供使用的规格1、2的镀锡板原料分别为的镀锡板原料
64、分别为50000张和张和20000张，即张，即(49)(50)沁新磐烫卸斌蠕粒唯呜碑护什询选得懂滩馁镀施业曾蚌订缺莆彩鹃嗣芍褥优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 配套配套约约束：束： 由表由表2一周生一周生产产的罐身个数的罐身个数为为x1 + 2x2 + 4x4, 一周一周生生产产的底、盖个数的底、盖个数为为10x1 + 4x2 + 16x3+ 5x4，因，因为应为应尽可能尽可能将它将它们们配套配套组组装成易拉罐装成易拉罐销销售。所以售。所以y1满满足足 (51)这时这时不配套的罐身个数不配套的罐身个数y2，和不配套的底、盖个数，和不配套的底、盖个数y3应为应为
65、 (52) (53)尺烫肮疟月狰户垫拂卒历朽彻绣造惟忙捶赣吁粕撼骗督声峰邱慨窑胯蚂韩优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模（47）（53）就是我们得到的模型，其中（）就是我们得到的模型，其中（51）是一个非线性关系，）是一个非线性关系，不易直接处理，不易直接处理， 但是它可以等价为以下两个线性不等式：但是它可以等价为以下两个线性不等式： (54) (55)模型求解模型求解将模型（将模型（47）（50）和（）和（52）（55）直接输入）直接输入LINDO（输入（输入LINGO也可以），求解时也可以），求解时LINDO发出警告信息（程序和警告信发出警告信息（程序和警告信
66、息参见图息参见图5-4）。）。 图中错误编号图中错误编号“66”的含义（参见第的含义（参见第4章的错误章的错误代码表）是：模型中数据不平衡，所以发出警告信息（注意，只代码表）是：模型中数据不平衡，所以发出警告信息（注意，只是警告信息，所以仍然可以继续求解）。求解结果是：是警告信息，所以仍然可以继续求解）。求解结果是：秋碌蒸妮癌伏僳殆逞滁趣能数勘诞凌矾清塌剧烙滔嗜练帐戍毯弥筋披牧捏优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 OBJECTIVE FUNCTION VALUE 1) 4298.337 VARIABLE VALUE REDUCED COST Y1 160250.
67、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缮显迸涵独譬饥锥女光滦滨剩框琅龚憋训甚赣酚吓唐菇呀烂踌喇旷印啄烷优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模图图5-4 模型中数据不平衡的警告信息模型中数据不平衡的警告信息惩参惰容浙镍踢犯烯蔼煮椎零彦按崎小桓借胆岁僚煌冷誊铬扣写蔑蔡贼慑优化建模与LINGO第5优化建模与LI
68、NGO第5 优化建模优化建模这这个个结结果可靠果可靠吗吗？由于？由于LINDO警告模型中数据之警告模型中数据之间间的数的数量量级级差差别别太大，所以我太大，所以我们们可以可以进进行行预处预处理，理，缩缩小数据之小数据之间间的差的差别别。实际实际上，上，约约束（束（48）（50）中右端）中右端项项的数的数值值过过大（与左端的系数相比大（与左端的系数相比较较），），LINDO在在计计算中容易算中容易产产生比生比较较大的大的误误差，所以出差，所以出现现此警告信息。此警告信息。为为了解决了解决这这一一问题问题，可以将所有决策，可以将所有决策变变量量扩扩大大10000倍倍（相当于（相当于xi以万次以万次
69、为单为单位，位，yi以万件以万件为单为单位）。此位）。此时时，目，目标标（47）可以保持不）可以保持不变变（记记住得到的住得到的结结果果单单位位为为万元就万元就可以了），而可以了），而约约束（束（48）（50）改）改为为 (56)(57) (58)剁翠绝寓柱辣沦怔滑澳综砍法涡锑鹅垛褂俱疥檀帐杠昔营缝腋蜗诀募肚蓟优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模将模型（将模型（47）和（）和（52）（58）输入）输入LINDO:! 易拉罐下料：均衡数据易拉罐下料：均衡数据Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x
70、4 - 0.1571y2 - 0.0196y3 s.t.1.5x1 + 2.0x2 + 1.0x3 +3.0x4 = 14.4 x1 + x2 + x3 = 5 x4 =010x1 + 4x2 + 16x3+ 5x4 - 2y1 =0x1 + 2x2 + 4x4 - y1 - y2 =010x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0end馅辫厩亲味书铁子襟荣寐挣真肥乏染赃守叁磐馁避驱掀争旨香先爽雄汞夸优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模求解得到：求解得到： OBJECTIVE FUNCTION VALUE 1) 0.4298337 VARI
71、ABLE 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元。元。攘
72、谣黄掷疆臭技见株母晨懦曳酝扶姑妇备村从周蛰弱磁旭仕森然羞伐孟妒优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模5.4 面试顺序与消防车调度问题面试顺序与消防车调度问题凿省害训庶惶眶躯狄士闺台绥了纽蔽滦王躬磋笆梧爷憎车渣扬藩柏家绕粟优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模面试顺序问题面试顺序问题 例例5.5 有有4名同学到一家公司参加三个阶段的面试：名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不到部门主管处复试，最后到经理处参
73、加面试，并且不允许插队（即在任何一个阶段允许插队（即在任何一个阶段4名同学的顺序是一样名同学的顺序是一样的）。由于的）。由于4名同学的专业背景不同，所以每人在三名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表个阶段的面试时间也不同，如表5-5所示（单位：分所示（单位：分钟）。这钟）。这4名同学约定他们全部面试完以后一起离开名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨公司。假定现在时间是早晨8：00，请问他们最早何，请问他们最早何时能离开公司？时能离开公司？ 侦最夺亭栗茧挨赣蜒究掸奢架虞县囤委挺钉闻皿迄那雏鹃拴傲埋堵蒲烯诡优化建模与LINGO第5优化建模与LINGO
74、第5 优化建模优化建模表表5-5 5-5 面试时间要求面试时间要求秘书初试秘书初试主管复试主管复试经理面试经理面试同学甲同学甲131520同学乙同学乙102018同学丙同学丙201010同学丁同学丁81015豌彬话快妄压你傣迄孩驭侨唆皂鹿绕涉讽康食矿渐拇剿罐逐械葬促镀赫较优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模建立模型建立模型 实际上，这个问题就是要安排实际上，这个问题就是要安排4名同学的面试顺名同学的面试顺序，使完成全部面试所花费的时间最少。序，使完成全部面试所花费的时间最少。 记记tij为第为第i名同学参加第名同学参加第j阶段面试需要的时间阶段面试需要的时间(已已
75、知知)，令，令xij表示第表示第i名同学参加第名同学参加第j阶段面试的开始时刻阶段面试的开始时刻(不妨记早上不妨记早上8：00面试开始为面试开始为0时刻时刻)(i=1, 2, 3, 4；j=1, 2, 3)，T为完成全部面试所花费的最少时间。为完成全部面试所花费的最少时间。 优化目标为优化目标为渴申慕爬酣龋淘晕潘穷荤乔行碎惫诊篷师侵征弟擎囚子酸异孜粉掖帧如弧优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 a. 时间先后次序约束时间先后次序约束(每人只有参加完前一个阶每人只有参加完前一个阶段的面试后才能进入下一个阶段段的面试后才能进入下一个阶段)： xij+ tij xi，j
76、+1 (i=1, 2, 3, 4；j=1, 2) b.每个阶段每个阶段j同一时间只能面试同一时间只能面试1名同学：用名同学：用0-1变变量量yik表示第表示第k名同学是否排在第名同学是否排在第i名同学前面名同学前面(1表示是，表示是，0表示否表示否)，则，则 xij+ tijxkj Tyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxij T(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) 约束条件：约束条件： 惦民玉札倪诉讹续努陈拉遥胜访萨寄街褥楷孙象豢杏拢浚梦束恰仗凤视控优化建模与LINGO第5优化建模与LINGO第5
77、 优化建模优化建模可以将非线性的优化目标改写为如下线性优化目标：可以将非线性的优化目标改写为如下线性优化目标： Min T s.t. T x13+ t13 T x23+ t23 T x33+ t33 T x43+ t43娇劫埂徘粮朴岩脯前肿骂糖重银责犯免窒格吓莽鼻晶肚龚何齐笛洒奢蒂米优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 Min T s.t. xij+ tij xi, j+1 (i=1, 2, 3, 4；j=1, 2) xij+ tijxkj Tyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxij T(1yik) (i,
78、k=1, 2, 3, 4; j=1, 2, 3; i= x13+ t13;T = x23+ t23;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： 酱峡症悠犬栓倾绊套老罩助曼酷伶淘磅晌秩攫秧查嘱哮借婪发洪桂妖刹阵优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模x11+
79、 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 - x13= 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=
80、 T*y14;x41+ t41 - x11= T*(1-y14);x12+ t12 - x42= T*y14;x42+ t42 - x12= T*(1-y14);镰侧惭壹棺尸贸子匪踞酵浸沈躬颇皋页筋熏翼垣佰井互一媳压批熄背荤恬优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模x13+ t13 - x43= T*y14;x43+ t43 - x13= T*(1-y14);x21+ t21 - x31= T*y23;x31+ t31 - x21= T*(1-y23);x22+ t22 - x32= T*y23;x32+ t32 - x32= T*(1-y23);x23+ t23 -
81、 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 - x41= T*y34; x41+ t41 - x31= T*(1-y34);尽杭野挺窃隙洛晌浅辜钎匈逝辩尺暖刊毫育封沛羌媒莽琳权纳唤忿晌谍昨优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模x32+
82、 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):SORT1x(i, j)+t
83、(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第5优化建模与LINGO第5 优化建模优化建模 求解这个模型，得到的结果与前面的完全相同。求解这个模型，得到的结果与前面的完全相同。 可以很清楚地看到，使用可以很清楚地看到，使用LINGO建模语言的集建模语言的集合和属性概念，得到的模型具有非常好的结构性，反合和属性概念，得到的模型具有非常好的结构性，反
84、映了相应的优化模型的本质，目标、决策变量、约束映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是序完全分离，这种优越性是LINDO软件无法与之相比软件无法与之相比的。的。 外踪咐媚硅闺豆帛陨欠粥峪峻醇瓶民诵荚龙睡领铂景獭丽正除摩笑欢钩绪优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模消防车调度问题消防车调度问题 例例5.6 某市消防中心同时接到了三处火警报告。某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要根据当前的火势，三处火警地点分别需要
85、2辆、辆、2辆和辆和3辆消防车前往灭火。三处火警地点的损失将依赖于辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记消防车到达的及时程度：记tij为第为第j辆消防车到达火警辆消防车到达火警地点地点i的时间的时间(分钟分钟)，则三处火警地点的损失分别为，则三处火警地点的损失分别为: 6t11+4t12，7t21+3t22，9t31+8t32+5t33。 目前可供消防中心调度的消防车正好有目前可供消防中心调度的消防车正好有7辆，分辆，分别属于三个消防站别属于三个消防站(可用消防车数量分别为可用消防车数量分别为3辆、辆、2辆、辆、2辆辆)。消防车从三个消防站到三个火警地点所需要的。
86、消防车从三个消防站到三个火警地点所需要的时间如表时间如表5-6所示。该公司应如何调度消防车，才能所示。该公司应如何调度消防车，才能使总损失最小？使总损失最小？ 耗侈招旺褪邪汝撇华疫啃武追蚊颂苑桩隐播谗俘馆访垄茅宅疆盆饶殊温缓优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 如果三处火警地点的损失分别为如果三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？调度方案是否需要改变？消防站到三个火警地点所需要的时间消防站到三个火警地点所需要的时间时间时间(分钟分钟)火警地点火警地点1火警地点火警地点2火警地点火警地点
87、3消防站消防站1679消防站消防站25811消防站消防站36910恼端罩捶柄们韩袍襄邑澎责瑟踞柯额厅帝贰厨肘衬尸孟谣寓冕弯删酗肥裔优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 问题分析问题分析 本题考虑的是为每个火警地点分配消防车的问题，本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。我们下面首先把它变成一个运输问题建模求解。 决策变量决策变量 为了
88、用运输问题建模求解，很自然地把为了用运输问题建模求解，很自然地把3个消防个消防站看成供应点。如果直接把站看成供应点。如果直接把3个火警地点看成需求点，个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把此难以确定损失的大小。下面我们把7辆车的需求分辆车的需求分别看成别看成7个需求点个需求点(分别对应于到达时间分别对应于到达时间t11, t12, t21, t22, t31, t32, t33)。用。用xi j表示消防站表示消防站i是否向第是否向第j个需求点个需求点派车派车(1表示派车，表示派车，0表示
89、不派车表示不派车)，则共有，则共有21个个0-1变变量。量。 限袒遵岭声深淘沸求芽庐饥骨罪饭鸵哑恰来涅全空谗蔼稻箍纫馆结仓赵饶优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 决策目标决策目标 题目中给出的损失函数都是消防车到达时间的线题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果性函数，所以由所给数据进行简单的计算可知，如果消防站消防站1向第向第6个需求点派车个需求点派车(即消防站即消防站1向火警地点向火警地点3派车但该消防车是到达火警地点派车但该消防车是到达火警地点3的第二辆车的第二辆车)，则由，则由此引起的损失为此引起的损失为8
90、*9=72。同理计算，可以得到损失矩。同理计算，可以得到损失矩阵阵(元素分别记为元素分别记为ci j)。 ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=136244921817245消防站消防站i=230205624998855消防站消防站i=336246327908050釜捉职撑爵塘舞纸荔万鼻越耳随爹哀谩钧蔗迭葛帚畜抑惕顶戌倦丰怠寐谷优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模于是，使总损失最小的决策目标为于是，使总损失最小的决策目标为 约束条件约束条件 约束条件有两类：一类是消防站拥有的约束条件
91、有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需消防车的数量限制，另一类是各需求点对消防车的需求量限制。求量限制。 消防站拥有的消防车的数量限制可以表示为消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+x36+x37=2 各需求点对消防车的需求量限制可以表示为各需求点对消防车的需求量限制可以表示为 虞谚馈垮烷刹恋眉倡捌宵虹烧细女抿仍巡鲍朵可讥幢禁否张金肾咯瘩腑焚优化建模与LINGO第5优化建模与LINGO第5 优化建模
92、优化建模模型求解模型求解 将如上构成的线性规划模型输入将如上构成的线性规划模型输入LINDO： ! 消防车问题消防车问题Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30x21+20x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90x35+80x36+50x37 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 x
93、11+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 婚契拷蝴旨傲蚀晌割贬俯蔫憎嚣谆母广卫鞘契躯隶鸦罕萝善承看喉资木洲优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模求解得到如下结果：求解得到如下结果： OBJECTIVE FUNCTION VALUE 1) 329.0000VARIABLE VALUE REDUCED COST X11 0.000000 10.000000 X12 0.000000 8.000
94、000 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.000000 X25 0.000000 14.000000 X26 0.000000 12.000000 X27 0.000000 9.000000 翔代陆予汞掣释折售妹诗舵皆酬陋炕祖骇方摊昔跌拉砰用恤奄纵敲撒
95、釜籍优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模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派派2辆
96、车；辆车；消防站消防站3应向火警地点应向火警地点2、3各派各派1辆车。最小总损失为辆车。最小总损失为329。 戊后蛤撩钥乳指匠熬渊夹僚献庙隧辙恰囤舆啤丈孜椎塘鄙怎范迅抉齿寇拴优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模讨论讨论 1) 这个问题本质上仍然和经典的运输问题类似，这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设点。在上面模型中，我们虽然假设xij为为0-1变量，但求变量，但求解时是采用线性规划求解的，也就是说没有加上解时是采用线性规划求解的，也就是说
97、没有加上xij为为0-1变量或整数变量的限制条件，但求解得到的结果变量或整数变量的限制条件，但求解得到的结果中中xij正好是正好是0-1变量。这一结果不是偶然的，而是运输变量。这一结果不是偶然的，而是运输问题特有的一种性质。问题特有的一种性质。葵符充祭熙厄霹勒噎细豫铝饿耿器冉王矗辫壕凑祷颤颓掠瞎咽防灭习录物优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 2) 在上面模型中，我们没有考虑消防车到达各火在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只
98、的先后次序约束。这一结果却并不总是必然的，而只是巧合。是巧合。 如对例题后半部分的情形，结果就不是这样了。如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵显然，此时只需要修改损失矩阵(元素仍然分别记为元素仍然分别记为cij)ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=124362149457281消防站消防站i=220302456558899消防站消防站i=324362763508090获窜心莫彝戳硬怀凤疲德陆剃懦知杨暇壮血迁贬磕碱两瀑踪玩锁理预芽甸优化建模与LINGO第5优化建模与LINGO第5
99、 优化建模优化建模 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO求解求解, 可以得到新的最优解可以得到新的最优解: x14=x16=x17=x21=x22=x33=x35=1其他变量为其他变量为0(最小总损失仍为最小总损失仍为329)。实际上。实际上, 损失矩损失矩阵中只是阵中只是1、2列交换了位置，列交换了位置，3、4列交换了位置，列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看出列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。以上新的最优解。 但是，以上新的最优解却是不符合实际情况的。但是，以上新的最优解却是不符合实际情况的。例如，例
100、如，x14=x33=1表明火警地点表明火警地点2的第一辆消防车来自的第一辆消防车来自消防站消防站3，第二辆消防车来自消防站，第二辆消防车来自消防站1，但这是不合理，但这是不合理的，因为火警地点的，因为火警地点2与消防站与消防站3有有9分钟的距离，大于分钟的距离，大于与消防站与消防站1的的7分钟的距离。分配给火警地点分钟的距离。分配给火警地点3的消防的消防车也有类似的不合理问题。车也有类似的不合理问题。 杉谱阀僵刮八支尊蕉陕创偿颧校氛广袍危厚聪呼扛头掷癣粟岁扇感脂壕脏优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 为了解决这一问题，我们必须考虑消防车到达各为了解决这一问题，我
101、们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。理问题不再出现。 首先考虑火警地点首先考虑火警地点2。由于消防站。由于消防站1的消防车到达的消防车到达所需时间所需时间(7分钟分钟)小于消防站小于消防站2的消防车到达所需时间的消防车到达所需时间(8分钟分钟)，并都小于消防站，并都小于消防站3的消防车到达所需时间的消防车到达所需时间(9分钟分钟)，因此火警地点，因此火警地点2的第的第2辆消防车如果来自消防辆消防车如果来自消防站
102、站1，则火警地点，则火警地点2的第的第1辆消防车也一定来自消防站辆消防车也一定来自消防站1；火警地点；火警地点2的第的第2辆消防车如果来自消防站辆消防车如果来自消防站2，则火，则火警地点警地点2的第的第1辆消防车一定来自消防站辆消防车一定来自消防站1或或2。因此，。因此，必须增加以下约束：必须增加以下约束：x14 x13x24 x13 +x23菇粤见任喘捶叙寄赐繁盂拌捉虚誉锅奏兹节绑砍恼是攘坟瓣靛熊划峻雕谦优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，对火警地点同理，对火警地点
103、1，必须增加以下约束：，必须增加以下约束：x22 x21对火警地点对火警地点3，必须增加以下约束：，必须增加以下约束：颖憨殷毕驴相此持掏羌咨懈悦挡埂陀桥氏笛镁判检脂娘察秽唤词劲肺舔禾优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO软件软件如下：如下： ! 消防车调度消防车调度Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15 +30x22+20x21+56x24+24x23+99x27+88x26+55x25 +36x32+24x31+63x34+27x33+9
104、0x37+80x36+50x35 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 歉冲县啦止臀怠魂揖凳苔航旱淡健轻柜搞遍碧咯耍戚宦唐惹皖鸵祖轮禄饮优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建
105、模X22 - X21 = 0X14 - X13 =0X24 - X23 - X13 =0X16 - X15 = 0X17 - X16 =0X36 - X15 - X35 =02X37 -X15 -X16 -X35 -X36 tan(cita - sigma) );for(VOR: (xx-x)/(yy-y) tan(cita + sigma) );d4 - sigma4 sqrt(sqr(xx-x4)+sqr(yy-y4) ;END 褥化褥星幢将腹潭宫粕朴凶迭该娃冠纲每甜弓梭要瘦恰局袋冷篓扳拜鞘颂优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 用用LINGO求解上述模型，求
106、解上述模型，LINGO系统返回的信系统返回的信息是这个模型没有可行解。其实这显然是一个不正确息是这个模型没有可行解。其实这显然是一个不正确的信息，可能只是由于求解空间太大，的信息，可能只是由于求解空间太大，LINGO没有没有找到可行解。其实，我们可以想象这个问题的可行解找到可行解。其实，我们可以想象这个问题的可行解大致就该在模型大致就该在模型1中得到的最优解附近，因此可以把中得到的最优解附近，因此可以把这个解作为初始值告诉这个解作为初始值告诉LINGO。例如，在上面程序。例如，在上面程序中增加以下三行：中增加以下三行： INIT:xx, yy = 980.6926, 731.5666;ENDI
107、NIT 真盂纹钠邮袜算孕看鞍殴废登迹沿欧放而忘果层除株澜舷号裂蔗徘旅参平优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 此时求解，马上就得到此时求解，马上就得到XX的最小值为的最小值为974.8424。类似地（只需要换换目标函数就可以了），可得到类似地（只需要换换目标函数就可以了），可得到XX的最大值为的最大值为982.2129，YY的最小值为的最小值为717.1587，YY的最大值为的最大值为733.1944。 因此，最后得到的解是一个比较大的矩形区域，因此，最后得到的解是一个比较大的矩形区域，大致为大致为975，982717，733。 有眉讫纹芝愁兜拿祝估蒋朽绿坷尿幼惦
108、程极挽婉僚廓目营茎苟昼天雪巧萤优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模模型模型3及求解及求解 模型模型2得到的只是一个很大的矩形区域，仍不能得到的只是一个很大的矩形区域，仍不能令人满意。实际上，模型令人满意。实际上，模型2中假设设备的测量误差是中假设设备的测量误差是均匀分布的，这是很不合理的。一般来说，在多次测均匀分布的，这是很不合理的。一般来说，在多次测量中，应该假设设备的测量误差是正态分布的，而且量中，应该假设设备的测量误差是正态分布的，而且均值为均值为0。本例中给出的精度。本例中给出的精度 i可以认为是测量误差可以认为是测量误差的标准差的标准差(也可以是与标准差
109、成比例的一个量，如标也可以是与标准差成比例的一个量，如标准差的准差的3倍或倍或6倍等倍等)。 在这种理解下，用各自的误差限在这种理解下，用各自的误差限 i对测量误差进对测量误差进行无量纲化行无量纲化(也可以看成是一种加权法也可以看成是一种加权法)处理是合理的，处理是合理的，即求解如下的无约束优化问题更合理：即求解如下的无约束优化问题更合理： 堆四单掺簧韧糖好咋疗娘谨欣涡贿附掷辊喇凤蔽雾认敖盘狄滋强疯旗徽勤优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模其中其中i=1, 2, 3, 由于目标函数是平方和的形式，因此这是一个非由于目标函数是平方和的形式，因此这是一个非线性最小二乘
110、拟合问题。相应的线性最小二乘拟合问题。相应的LINGO程序为程序为(仍然仍然将迭代初值告诉将迭代初值告诉LINGO)：讣呐仿侦亿荆惭伎继诸尼纪亡剔瞧磐盈强踪闯睦誓抵哼露蔑乳秤证屎杉柑优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模MODEL:TITLE 飞机定位模型飞机定位模型3;SETS:VOR/1.3/: x, y, cita, sigma;ENDSETSDATA:x, y, cita, sigma =74613932.813470.01406293750.787140.010515712595.393070.0227;x4 y4 d4 sigma4 = 15598786
111、4.3 2.0;ENDDATAINIT:xx, yy = 980.6926, 731.5666;ENDINIT掺钓拯洁借疾苞奖搔嘎糟耀拨均嘴频闯挤谅臀禹灭脉蘑送勺绸坡阿羊绕讼优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模! 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 -
112、(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。 俯岔色图间茅福石爬剐庚蹈生盖捏彝逮擅雁孔屠好课叠踞蓟冻憾猪封涌鲜优化
113、建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 这个误差为什么比模型这个误差为什么比模型1的大很多？这是因为模的大很多？这是因为模型型1中使用的是绝对误差，而这里使用的是相对于精中使用的是绝对误差，而这里使用的是相对于精度度 i的误差。分母的误差。分母 i很小，所以相对误差比绝对误差很小，所以相对误差比绝对误差大，这是可以理解的。其实，可以认为此时的目标函大，这是可以理解的。其实，可以认为此时的目标函数是四个标准正态分布的误差平方和，只要在数是四个标准正态分布的误差平方和，只要在4以内以内都是合理的。都是合理的。 隐侄炕硷诌昔惕爷械岔抛进倘愧培饲蓬呐啮权疚轿琅某闸俞稽踊胜柠医蓟
114、优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 5.5.2飞行计划问题飞行计划问题 例例5.8 这个问题是以第二次世界大战中的一个实这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在甲乙双方的际问题为背景，经过简化而提出来的。在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达一场战争中，一部分甲方部队被乙方部队包围长达4个月。个月。由于乙方封锁了所有水陆交通通道，被包围的由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送甲方部队只能依靠空中交通维持供给。运送4个月的个月的供给分别需要供给分别需要2, 3, 3, 4次飞
115、行，每次飞行编队由次飞行，每次飞行编队由50架架飞机组成飞机组成(每架飞机需要每架飞机需要3名飞行员名飞行员)，可以运送，可以运送10万万吨物资。每架飞机每个月只能飞行一次，每名飞行员吨物资。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回每个月也只能飞行一次。在执行完运输任务后的返回途中有途中有20%的飞机会被乙方部队击落，相应的飞行员的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。也因此牺牲或失踪。琢锦刮肾屈娄癸睦源残稀底斩掏擂甫伐摩壁痔奎辰娘憋虐策轨命归症伟涅优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 在第在第1个月开始时
116、，甲方拥有个月开始时，甲方拥有110架飞机和架飞机和330名名熟练的飞行员。在每个月开始时，甲方可以招聘新飞熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月的检查后行员和购买新飞机。新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。每名熟练飞行员下经过一个月的训练才能投入飞行。每名熟练飞行员可以作为教练每个月指导可以作为教练每个月指导20名飞行员名飞行员(包括他自己在包括他自己在内内)进行训练。每名飞行员在完成一个月的飞行任务进行训练。每名飞行员在完成一个月
117、的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用入飞行。已知各项费用(单位略去单位略去)如下表所示，请你如下表所示，请你为甲方安排一个飞行计划。为甲方安排一个飞行计划。 闻映绞患黑殿灶勃敷辗窃心朴押声舜庐努诊末议儡兽财舔絮构降菩呻龋删优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 如果每名熟练飞行员可以作为教练每个月指导不如果每名熟练飞行员可以作为教练每个月指导不超过超过20名飞行员名飞行员(包括他自己在内包括他自己在内)进行训练，模型和进行训练，模型和结果有哪些改变？结果有哪些改变？ 第第1 1个月
118、个月第第2 2个月个月 第第3 3个月个月 第第4 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憎鹃圾得攫绢党眺蒙脐惦壮峡剖搞灭椽嚏换搓趟拍右衬香疾埋翻寨做俱掇优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 问题分析问题分析 这个问题看起来
119、很复杂，但只要理解了这个例子这个问题看起来很复杂，但只要理解了这个例子中所描述的事实，其实建立优化模型并不困难。首先中所描述的事实，其实建立优化模型并不困难。首先可以看出，执行飞行任务以及执行飞行任务后休假的可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用熟练飞行员数量是常数，所以这部分费用(报酬报酬)是固是固定的，在优化目标中可以不考虑。定的，在优化目标中可以不考虑。 决策变量决策变量 设设4个月开始时甲方新购买的飞机数量分别为个月开始时甲方新购买的飞机数量分别为x1, x2, x3, x4架架, 闲置的飞机数量分别为闲置的飞机数量分别为y1, y2, y3
120、, y4架。架。4个月中个月中, 飞行员中教练和新飞行员数量分别为飞行员中教练和新飞行员数量分别为u1, u2, u3, u4人人, 闲置的的熟练飞行员数量分别为闲置的的熟练飞行员数量分别为 v1, v2, v3, v4人。人。 疽胎名沙缄册嘿己共上拷抗宰协集愧或懊肖语超裔舷依雁滩策骇凳吊断盈优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模目标函数目标函数优化目标是优化目标是: : Min 200x1+195x2 +190x3+185x4+10u1+9.9u2 +9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4 约束条件约束条件需要考虑的约束包括：需要考虑的
121、约束包括： 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茎颗蛆麓豁篮菱氯烫回恋舟腮改札俗广肩惩王盒痈湖墒帚封附童酬限艇季优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模 2）飞行员数量限制
122、飞行员数量限制：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
123、, u1, u2, u3, u4 , v1, v2, v3, v4 0 且为整数。且为整数。 殿变夸挤膛进姐沮婚莱淆诀桩删拴恫缸瓷著哺窥诸朱信腊菌湿寞卢头病泡优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模于是，这个优化模型很容易输入于是，这个优化模型很容易输入LINDO： MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2 +9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4 s.t.y1=10y1+ x1 - y2 =70y2+ x2 - y3 =30y3+ x3 - y4=800.05 u1+ v1=30u1 + v1 - 0
124、.05 u2 - v2 = 450u2 + v2 - 0.05 u3 - v3 = 210u3 + v3 - 0.05 u4 - v4 = 240end GIN 16 府惕萨誓摊酗霸植焦右偷莫产纂讽纺揽阮厂衔凝寡秽钓对皂础轧邵溯诛扶优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模用用LINDO求解得到：求解得到： OBJECTIVE FUNCTION VALUE 1) 42324.40VARIABLE VALUE REDUCED COST X1 60.000000 200.000000 X2 30.000000 195.000000 X3 80.000000 190.0000
125、00 X4 0.0000000 185.000000 U1 460.00000 10.000000 U2 220.00000 9.900000 U3 240.00000 9.800000 U4 0.0000000 9.700000 V1 7.0000000 7.000000 V2 6.0000000 6.900000 V3 4.0000000 6.800000 V4 4.0000000 6.700000 质玲宅春虑辨座心效兽悦呵累匪井培锌起禾证淋解装踪锌阳兑字发壕辙钥优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模VARIABLE VALUE REDUCED COST Y1
126、10.000000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 即最优解为即最优解为x1=60, x2=30, x3=80, x4=0, y1=10, y2= y3= y4 =0, u1=460, u2=220, u3=240, u4=0, v1=7, v2=6, v3=4, v4=4; 目标函数值为目标函数值为42324.40。 衣锗咙绰窜富爸栏芍丧嫁幕晋识忿搓停眼箍佛肺弦间勤龋嗣榜岸艳较剪端优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模问题讨论问题讨论 如果每名熟练飞行员
127、可以作为教练每个月指导不如果每名熟练飞行员可以作为教练每个月指导不超过超过20名飞行员名飞行员(包括他自己在内包括他自己在内)进行训练，则应将进行训练，则应将教练与新飞行员分开：教练与新飞行员分开： 设设4个月飞行员中教练为个月飞行员中教练为u1, u2, u3, u4人，新飞人，新飞行员数量分别为行员数量分别为w1, w2, w3, w4人。其它符号不变。飞人。其它符号不变。飞行员的数量限制约束为行员的数量限制约束为第第1个月：个月：300+u1+v1=330第第2个月：个月：450+u2+v2= u1+v1+w1， w1 20u1第第3个月：个月：450+u3+v3= u2+v2+240+
128、w2， w2 20u2第第4个月：个月：600+u4+v4= u3+v3+360+w3， w3 20u3 派毗碗敖快秧尹众睛砂宙误百县肘沤娇棒敦异芭状按倔随锤湖藐蔬篆叭结优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模优化模型作相应修改，输入优化模型作相应修改，输入LINDO如下：如下： MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2+9.8u3+9.7u4 +7v1+6.9v2+6.8v3+6.7v4+10w1+9.9w2+9.8w3+9.7w4s.t. y1=10 y1+ x1 - y2 =70 y2+ x2 - y3 =30 y3+ x3
129、 - y4=80 u1+ v1=30 u1 + v1 + w1 - u2 - v2 = 450 u2 + v2 + w2 - u3 - v3 = 210 u3 + v3 + w3 - u4 - v4 = 240 w1 - 20u1 =0 w2 - 20u2 =0 w3 - 20u3 =0 endgin 20 涸迷支陵奉吨卧译忽臃腔崩训剐清县步痔天在祭采痒矮铣荧农袋茂嚏养诽优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模用用LINDO求解得到：求解得到： OBJECTIVE FUNCTION VALUE 1) 42185.80 VARIABLE VALUE REDUCED CO
130、ST X1 60.000000 200.000000 X2 30.000000 195.000000 X3 80.000000 190.000000 X4 0.000000 185.000000 U1 22.000000 10.000000 U2 11.000000 9.900000 U3 12.000000 9.800000 U4 0.000000 9.700000 V1 8.000000 7.000000 V2 0.000000 6.900000 V3 0.000000 6.800000 V4 0.000000 6.700000敝奶乔彩盎辗冠闽脯唐燕阐俘种朝蚊蒂亢勒钠词捶厄汪熟配闺嚷谜黑列
131、攫优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模VARIABLE VALUE REDUCED COST W1 431.000000 10.000000 W2 211.000000 9.900000 W3 228.000000 9.800000 W4 0.000000 9.700000 Y1 10.000000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 即最优解为即最优解为u1=22, u2=11, u3=12, u4=0, v1=8, v2=v3=v4 =0, w1=431, w2=211, w3=228, w4=0 (x1x4, y1y4不变不变)；目标函数值为；目标函数值为42185.80。 恼驰傅妮染浩祁锌龚曰去德驻勿货众彻唾维噬货戴亩相晰柯颧固梨杀吝俱优化建模与LINGO第5优化建模与LINGO第5 优化建模优化建模自己练习，或课上布置自己练习，或课上布置布置作业内容布置作业内容Thank you very much!Thank you very much!巨季吵奴劳走斩宴邯忱馁阿肮筏眯棕徘岂酝钦阑窄秤懦郁粤疲疯山伙把肾优化建模与LINGO第5优化建模与LINGO第5
