数学规划建模幻灯片.ppt

数学规划建模数学规划建模第1页，共115页，编辑于2022年，星期六内容提要内容提要1什么是数学规划什么是数学规划2连续性线性规划连续性线性规划3整数线性规划整数线性规划4非线性规划非线性规划5多目标规划多目标规划6目标规划目标规划第2页，共115页，编辑于2022年，星期六最优化问题的最优化问题的数学模型的一般形式数学模型的一般形式为：为：（1）（2）三个要素：三个要素：决策变量决策变量decisionvariable，目标函数目标函数objectivefunction，约束条件约束条件constraints。什么是数学规划？什么是数学规划？第3页，共115页，编辑于2022年，星期六（2）所确定的）所确定的x的范围称为的范围称为可行域可行域feasibleregion，满，满足（足（2）的解）的解x称为称为可行解可行解feasiblesolution，同时满足，同时满足（1）（）（2）的解）的解x称为称为最优解最优解Optimalsolution，整个可，整个可行域上的最优解称为行域上的最优解称为全局最优解全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为，可行域中某个领域上的最优解称为局部最优解局部最优解localoptimalsolution。最优解所对应的目标函数值称为。最优解所对应的目标函数值称为最优值最优值optimum。什么是数学规划？什么是数学规划？第4页，共115页，编辑于2022年，星期六（一）（一）按有无约束条件按有无约束条件（2）可分为：）可分为：1.无约束优化无约束优化unconstrainedoptimization。2.约束优化约束优化constrainedoptimization。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。优化模型的分类优化模型的分类什么是数学规划？什么是数学规划？第5页，共115页，编辑于2022年，星期六（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可分为：1.数学规划或连续优化。数学规划或连续优化。可继续划分为可继续划分为线性规划线性规划(LP)Linearprogramming和和非非线性规划线性规划(NLP)Nonlinearprogramming。在非线性规划。在非线性规划中有一种规划叫做中有一种规划叫做二次规划二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。，目标为二次函数，约束为线性函数。2.离散优化或组合优化。离散优化或组合优化。包含：包含：整数规划整数规划(IP)Integerprogramming，整数规，整数规划中又包含很重要的一类规划：划中又包含很重要的一类规划：0-1（整数）规划（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取，这类规划问题的决策变量只取0或者或者1。什么是数学规划？什么是数学规划？第6页，共115页，编辑于2022年，星期六（三）（三）按目标的多少按目标的多少可分为：可分为：1.单目标规划。单目标规划。2.多目标规划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不确定性可分为：可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）（五）按问题求解的特性按问题求解的特性可分为：可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。什么是数学规划？什么是数学规划？第7页，共115页，编辑于2022年，星期六LINGO软件和软件和MATLAB软件。软件。求解优化问题常用的软件求解优化问题常用的软件什么是数学规划？什么是数学规划？第8页，共115页，编辑于2022年，星期六线性规划的一般形式：线性规划的一般形式：连续性线性规划连续性线性规划第9页，共115页，编辑于2022年，星期六一般线性规划问题都可以通过引入非负的松弛变量一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量与非负的剩余变量surplusvariable的方法化为的方法化为标准形标准形式式（约束全是等约束）。（约束全是等约束）。线性规划问题的可行域线性规划问题的可行域feasibleregion是一个凸集是一个凸集convexset（任意两点的连线上的点都在区域内部，可以看（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解作是没有凹坑的凸多面体），所以最优解Optimalsolution/point在凸多面体的某个顶点上达到在凸多面体的某个顶点上达到求解方法：单纯形算法求解方法：单纯形算法simplexmethod。连续性线性规划连续性线性规划 第10页，共115页，编辑于2022年，星期六连续性线性规划连续性线性规划 例例1 运输问题运输问题第11页，共115页，编辑于2022年，星期六解解设设A1,A2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x1，x2，x3，x4，x5，x6吨。吨。题设量可总到下表：题设量可总到下表：连续性线性规划连续性线性规划 第12页，共115页，编辑于2022年，星期六结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：连续性线性规划连续性线性规划 第13页，共115页，编辑于2022年，星期六程序编写程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x34;x4+x5+x62;x2+x54;x3+x65;end提示：课件中的程序提示：课件中的程序请先粘贴在记事本中请先粘贴在记事本中再再转帖于转帖于lingo软件中软件中连续性线性规划连续性线性规划 第14页，共115页，编辑于2022年，星期六运行结果运行结果 Global optimal solution found.Objective value:160.0000 Total solver iterations:0 Variable Value Reduced Cost X1 2.000000 0.000000 X2 0.000000 28.00000 X3 2.000000 0.000000 X4 0.000000 2.000000 X5 4.000000 0.000000 X6 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.00000连续性线性规划连续性线性规划 第15页，共115页，编辑于2022年，星期六模型修改为模型修改为 连续性线性规划连续性线性规划 第16页，共115页，编辑于2022年，星期六程序编写程序编写2MODEL:TITLE 调调运大米的运运大米的运输问题输问题程序程序2;!定义集合段定义集合段;SETS:HANG/1.5/:B;!定义矩阵的行定义矩阵的行;LIE/1.6/:C,X;!定义矩阵的列以及变量定义矩阵的列以及变量;XISHU(HANG,LIE):A;!定义约束的系数矩阵定义约束的系数矩阵;ENDSETSDATA:A=1 1 1 0 0 0!系数矩阵赋值系数矩阵赋值;0 0 0 1 1 1 -1 0 0-1 0 0 0-1 0 0-1 0 0 0-1 0 0-1;连续性线性规划连续性线性规划 第17页，共115页，编辑于2022年，星期六C=12 24 8 30 12 24;!目标函数的系数;B=4 8-2-4-5;!约束的右端项;ENDDATA!标准形式的目标函数的矩阵形式;MIN=SUM(LIE:C*X);FOR(HANG(I):SUM(LIE(J):A(I,J)*X(J)B(I);END连续性线性规划连续性线性规划 第18页，共115页，编辑于2022年，星期六84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824变量更换为：变量更换为：连续性线性规划连续性线性规划 第19页，共115页，编辑于2022年，星期六模型模型:连续性线性规划连续性线性规划 第20页，共115页，编辑于2022年，星期六程序编写程序编写3MODEL:TITLE 调运大米的运输问题程序调运大米的运输问题程序3;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!粮库到粮站的距离粮库到粮站的距离;C=12 24 8 30 12 24;连续性线性规划连续性线性规划 第21页，共115页，编辑于2022年，星期六!粮粮库库的限量的限量;A=4 8;!粮站的限量粮站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!粮粮库库上限的上限的约约束束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 连续性线性规划连续性线性规划 第22页，共115页，编辑于2022年，星期六程序的调试程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；示做相应的修改；2.可以用可以用“！”把约束变成说明语句，而把这条语句把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；可以边写程序边运行，保证每行书写都是正确的程序；连续性线性规划连续性线性规划 第23页，共115页，编辑于2022年，星期六例例2 阶段生产问题阶段生产问题(P31)某公司生产某产品某公司生产某产品,最大生产能力为最大生产能力为10000单位单位,每单每单位存储费位存储费2元元,预定的销售量与单位成本如下预定的销售量与单位成本如下:月份单位成本(元)销售量1234 70 6000 72 7000 80 12000 76 6000求一生产计划求一生产计划,使使1)满足需求满足需求;2)不超过生产能力不超过生产能力;3)成本成本(生产成本与存储费之和生产成本与存储费之和)最低最低.连续性线性规划连续性线性规划 第24页，共115页，编辑于2022年，星期六解解假定假定1月初无库存月初无库存,4月底买完月底买完,当月生产的不库当月生产的不库存存,库存量无限制库存量无限制.连续性线性规划连续性线性规划 第25页，共115页，编辑于2022年，星期六model:title 生产计划程序生产计划程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2;a=10000;enddatamin=sum(yuefen:c*x)+sum(yuefen(j)|j#lt#4:sum(yuefen(i)|i#le#j:x-d)*e(j+1);for(yuefen(j)|j#lt#4:sum(yuefen(i)|i#le#j:x)sum(yuefen(i)|i#le#j:d);sum(yuefen:x)=sum(yuefen:d);for(yuefen:xa);end 连续性线性规划连续性线性规划 第26页，共115页，编辑于2022年，星期六连续性线性规划连续性线性规划 第27页，共115页，编辑于2022年，星期六Model:Title 生生产计产计划程序划程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2;a=10000;enddatamin=sum(yuefen:c*x+e*s);for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i);s(4)+x(4)-d(4)=0;s(1)=0;for(yuefen:xa);End连续性线性规划连续性线性规划 第28页，共115页，编辑于2022年，星期六月份单位成本(元)销售量1234 70 6000 72 7000 80 12000 76 6000连续性线性规划连续性线性规划 第29页，共115页，编辑于2022年，星期六76827676-80-7472-747270生产月10000100001000010000产量产量600041200070006000销量销量4321321需求月费用cij连续性线性规划连续性线性规划 第30页，共115页，编辑于2022年，星期六连续性线性规划连续性线性规划 建立模型如下：建立模型如下：第31页，共115页，编辑于2022年，星期六model:title 生产计划程序生产计划程序3;sets:yuefen/1.4/:a,d,xx;!定义上三角矩阵定义上三角矩阵;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 12000 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x);for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)d(j););!得到每个月的生产量得到每个月的生产量;for(yuefen(i):xx=sum(yuefen(j)|j#ge#i:x(i,j);End连续性线性规划连续性线性规划 第32页，共115页，编辑于2022年，星期六Model Title:生生产计产计划程序划程序1 Variable Value Reduced Cost A 10000.00 0.000000 C(1)70.00000 0.000000 C(2)71.00000 0.000000 C(3)80.00000 0.000000 C(4)76.00000 0.000000 X(1)10000.00 0.000000 X(2)10000.00 0.000000 X(3)5000.000 0.000000 X(4)6000.000 0.000000 E(1)2.000000 0.000000 E(2)2.000000 0.000000 E(3)2.000000 0.000000 E(4)2.000000 0.000000 D(1)6000.000 0.000000 D(2)7000.000 0.000000 D(3)12000.00 0.000000 D(4)6000.000 0.000000 连续性线性规划连续性线性规划 第33页，共115页，编辑于2022年，星期六连续投资连续投资10万元万元A：从第：从第1年年到第到第4年每年初要投资，次年末回收本年每年初要投资，次年末回收本利利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万万元元C：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。年末总资本最大。练习一下吧练习一下吧 连续投资连续投资第34页，共115页，编辑于2022年，星期六 例例3 生产计划问题生产计划问题某工厂计划安排生产某工厂计划安排生产，两种产品，已知每种单位产两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到的单位利润降低到1.8万元，要不要改变生产计划，如果降低到万元，要不要改变生产计划，如果降低到1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万元，要不要改变生产计划？万元，要不要改变生产计划？）如果产品）如果产品，的单位利润同时降低了的单位利润同时降低了1万元，要不要改变生产计划？万元，要不要改变生产计划？产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23敏感性分析敏感性分析1 1 第35页，共115页，编辑于2022年，星期六敏感性分析敏感性分析1 1 第36页，共115页，编辑于2022年，星期六程序编写程序编写model:title 生产计划问题生产计划问题;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x212;END敏感性分析敏感性分析1 1 第37页，共115页，编辑于2022年，星期六运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 对问题对问题1，安排是生产产品，安排是生产产品4单位，产品单位，产品2单位，最大盈单位，最大盈利为利为14万元万元。敏感性分析敏感性分析1 1 第38页，共115页，编辑于2022年，星期六目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.敏感性分析敏感性分析1 1 第39页，共115页，编辑于2022年，星期六要使用敏感性分析必须要在这里选择Prices&Ranges然后保存退出路径：路径：LINGOOptionsGeneralSolver(通用求解程序通用求解程序)选项卡选项卡敏感性分析敏感性分析1 1 第40页，共115页，编辑于2022年，星期六要调出敏感性分析的结果，必须要调出敏感性分析的结果，必须先求解先求解后再后再在程序窗口下在程序窗口下点击点击LINGORange，敏感性分析敏感性分析1 1 第41页，共115页，编辑于2022年，星期六Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，在（万元，在（1.5，）之间，所以不改变生产计划。）之间，所以不改变生产计划。如果降低到如果降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。在程序中将目标函数的系数）内，要改变生产计划。在程序中将目标函数的系数“2”改为改为“1”，可得新的计划为，可得新的计划为安排是生产产品安排是生产产品2单单位，位，产产品品3单位，最大盈利单位，最大盈利为为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈单位，最大盈利为利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到不改变生产计划，但是最大利润降低到8万元万元.敏感性分析敏感性分析1 1 第42页，共115页，编辑于2022年，星期六敏感性分析敏感性分析2 2 第43页，共115页，编辑于2022年，星期六把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，在最优情况下，y的值就是资源的的值就是资源的影影子价格，子价格，影子价格有意义是有范影子价格有意义是有范围的围的。影子价格经济含义是：在资源得到最优配置，影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量位所带来总收益的增加量 敏感性分析敏感性分析2 2 第44页，共115页，编辑于2022年，星期六Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 敏感性分析敏感性分析2 2 第45页，共115页，编辑于2022年，星期六1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：例例4加工奶制品的生产计划加工奶制品的生产计划敏感性分析敏感性分析第46页，共115页，编辑于2022年，星期六x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)敏感性分析敏感性分析1 1 第47页，共115页，编辑于2022年，星期六Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。敏感性分析敏感性分析第48页，共115页，编辑于2022年，星期六OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.00000035元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3550;x2+2*x4+x5+3*x620;x3+x5+2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end程序编写程序编写整数线性规划整数线性规划第58页，共115页，编辑于2022年，星期六按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。按模式按模式2切割切割15根，按模式根，按模式5切割切割5根，按模式根，按模式7切割切割5根，共根，共25根，根，余料余料35米米当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 整数线性规划整数线性规划第59页，共115页，编辑于2022年，星期六练习练习3某服务部门一周中每天需要不同数目的雇员，某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要周一到周四每天至少需要50人，周五至少需要人，周五至少需要80人，人，周六和周日至少需要周六和周日至少需要90人，现规定应聘者需连续工人，现规定应聘者需连续工作作5天，试确定聘用方案。天，试确定聘用方案。练习一下吧练习一下吧 第60页，共115页，编辑于2022年，星期六例例6选址问题选址问题0-10-1规划规划第61页，共115页，编辑于2022年，星期六0-10-1规划规划 第62页，共115页，编辑于2022年，星期六某班准备从某班准备从5名游泳员中选择人组成接力队，名游泳员中选择人组成接力队，参加学校的参加学校的4100m混合泳接力比赛，混合泳接力比赛，5名队员名队员4种泳种泳姿的百米平均成绩如表，问如何选拔队员。姿的百米平均成绩如表，问如何选拔队员。队员甲乙丙丁戊蝶泳10685721181101074仰泳115610611421142111蛙泳1271064109610961238自由泳586535945721024练习一下吧练习一下吧 第63页，共115页，编辑于2022年，星期六客户增加需求：客户增加需求：由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 例例8 续例续例5下料问题下料问题(P87)非线性规划非线性规划第64页，共115页，编辑于2022年，星期六对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，由搜索根，由搜索算法确定有算法确定有1616种合理切割模式。种合理切割模式。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢管生产种切割模式下，每根原料钢管生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量非线性规划非线性规划 第65页，共115页，编辑于2022年，星期六满足需求满足需求目标函数（目标函数（总根数）总根数）约束条件约束条件xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数模式合理：模式合理：每根余料不超过每根余料不超过3米米整数约束：整数约束：非线性规划非线性规划 第66页，共115页，编辑于2022年，星期六增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界：需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米非线性规划非线性规划 第67页，共115页，编辑于2022年，星期六特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：31模式排列顺序可任定模式排列顺序可任定上下界上下界非线性规划非线性规划 第68页，共115页，编辑于2022年，星期六modelmodel:Title钢管下料钢管下料-最小化钢管根数的最小化钢管根数的LINGO模型模型;SETS:NEEDS/1.4/:LENGTH,NUM;CUTS/1.3/:X;PATTERNS(NEEDS,CUTS):R;ENDSETSDATA:LENGTH=4 5 6 8;NUM=50 10 20 15;CAPACITY=19;ENDDATA非线性规划非线性规划 第69页，共115页，编辑于2022年，星期六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非线性规划非线性规划 第70页，共115页，编辑于2022年，星期六结果结果模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢米钢管，共管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。用去原料钢管总根数为用去原料钢管总根数为28根。根。非线性规划非线性规划 第71页，共115页，编辑于2022年，星期六练习练习料场的建立与运输料场的建立与运输建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，距表示，距离单位：公里离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时料场位于下表给出。有两个临时料场位于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别向各工地运送两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611练习一下吧练习一下吧 第72页，共115页，编辑于2022年，星期六 线性规划致力于某个目标函数的最优解，这个最优解若线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。行，这将给人们进一步应用线性规划方法带来困难。多目标规划多目标规划第73页，共115页，编辑于2022年，星期六例例9 重新考虑例重新考虑例6选址问题。选址问题。(增加投资最少增加投资最少)多目标规划多目标规划 第74页，共115页，编辑于2022年，星期六 多目标决策问题有许多共同的特点，其中最显著的是：目多目标决策问题有许多共同的特点，其中最显著的是：目标的标的不可公度性不可公度性，和目标间的，和目标间的矛盾性矛盾性。因此不能简单的。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标问题。方法去求解多目标问题。多目标问题的数学模型多目标问题的数学模型 多目标规划多目标规划 第75页，共115页，编辑于2022年，星期六记可行域为记可行域为D.Min xMin yxyABCD多目标规划多目标规划 第76页，共115页，编辑于2022年，星期六多目标决策的本质问题是多目标决策的本质问题是：如何根据决策者的主观价值：如何根据决策者的主观价值判断，对有效解的好坏做出比较？由于可行域中的一个点，判断，对有效解的好坏做出比较？由于可行域中的一个点，对应目标函数是一个向量，所以问题实际是：如何比较两对应目标函数是一个向量，所以问题实际是：如何比较两个向量的大小？个向量的大小？ABAB BC多目标规划多目标规划 第77页，共115页，编辑于2022年，星期六多目标规划多目标规划 第78页，共115页，编辑于2022年，星期六 多目标规划的常用解法多目标规划的常用解法 思想思想：转化为单目标问题：转化为单目标问题（1）线性加权法线性加权法：权数权数评价函数评价函数 单目标单目标:多目标规划多目标规划 第79页，共115页，编辑于2022年，星期六（2）变权加权法变权加权法：（3）指数加权法指数加权法：多目标规划多目标规划 第80页，共115页，编辑于2022年，星期六（4）极小极大（极小极大（min-max）法）法 多目标规划多目标规划 第81页，共115页，编辑于2022年，星期六（5）理想点法理想点法 先求解单目标的最优值确定理想点：先求解单目标的最优值确定理想点：在找距离理想点最近的点作为最优解：在找距离理想点最近的点作为最优解：多目标规划多目标规划 第82页，共115页，编辑于2022年，星期六（6）加权偏差函数法加权偏差函数法 多目标规划多目标规划 第83页，共115页，编辑于2022年，