数学规划建模

数学规划建模第1页，共115页，2023年，2月20日，星期六内容提要什么是数学规划连续性线性规划整数线性规划非线性规划多目标规划目标规划第2页，共115页，2023年，2月20日，星期六最优化问题的数学模型的一般形式为：（1）（2）三个要素：决策变量decisionvariable，目标函数objectivefunction，约束条件constraints。什么是数学规划？第3页，共115页，2023年，2月20日，星期六（2）所确定的x的范围称为可行域feasibleregion，满足（2）的解x称为可行解feasiblesolution，同时满足（1）（2）的解x称为最优解Optimalsolution，整个可行域上的最优解称为全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为局部最优解localoptimalsolution。最优解所对应的目标函数值称为最优值optimum。什么是数学规划？第4页，共115页，2023年，2月20日，星期六（一）按有无约束条件（2）可分为：1.无约束优化unconstrainedoptimization。2.约束优化constrainedoptimization。大部分实际问题都是约束优化问题。优化模型的分类什么是数学规划？第5页，共115页，2023年，2月20日，星期六（二）按决策变量取值是否连续可分为：1.数学规划或连续优化。可继续划分为线性规划(LP)Linearprogramming和非线性规划(NLP)Nonlinearprogramming。在非线性规划中有一种规划叫做二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。2.离散优化或组合优化。包含：整数规划(IP)Integerprogramming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取0或者1。什么是数学规划？第6页，共115页，2023年，2月20日，星期六（三）按目标的多少可分为：1.单目标规划。2.多目标规划。（四）按模型中参数和变量是否具有不确定性可分为：1.确定性规划。2.不确定性规划。（五）按问题求解的特性可分为：1.目标规划。2.动态规划。3.多层规划。4.网络优化。5.……等等。什么是数学规划？第7页，共115页，2023年，2月20日，星期六LINGO软件和MATLAB软件。

求解优化问题常用的软件什么是数学规划？第8页，共115页，2023年，2月20日，星期六线性规划的一般形式：连续性线性规划第9页，共115页，2023年，2月20日，星期六一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量surplusvariable的方法化为标准形式（约束全是等约束）。线性规划问题的可行域feasibleregion是一个凸集convexset（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解Optimalsolution/point在凸多面体的某个顶点上达到求解方法：单纯形算法simplexmethod。连续性线性规划第10页，共115页，2023年，2月20日，星期六连续性线性规划

例1运输问题第11页，共115页，2023年，2月20日，星期六解设A1,A2调运到三个粮站的大米分别为x1，x2，

x3，

x4，

x5，

x6吨。题设量可总到下表：连续性线性规划

第12页，共115页，2023年，2月20日，星期六结合存量限制和需量限制得数学模型：连续性线性规划

第13页，共115页，2023年，2月20日，星期六程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x3<4;x4+x5+x6<8;x1+x4>2;x2+x5>4;x3+x6>5;end提示：课件中的程序请先粘贴在记事本中再转帖于lingo软件中连续性线性规划

第14页，共115页，2023年，2月20日，星期六运行结果

Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:0VariableValueReducedCostX12.0000000.000000X20.00000028.00000X32.0000000.000000X40.0000002.000000X54.0000000.000000X63.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.00000连续性线性规划

第15页，共115页，2023年，2月20日，星期六模型修改为连续性线性规划

第16页，共115页，2023年，2月20日，星期六程序编写2MODEL:TITLE调运大米的运输问题程序2;!定义集合段;SETS:HANG/1..5/:B;!定义矩阵的行;LIE/1..6/:C,X;!定义矩阵的列以及变量;XISHU(HANG,LIE):A;!定义约束的系数矩阵;ENDSETSDATA:A=111000!系数矩阵赋值;000111-100-1000-100-1000-100-1;连续性线性规划

第17页，共115页，2023年，2月20日，星期六C=12248301224;!目标函数的系数;B=48-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页，2023年，2月20日，星期六84库存量x23x22x21A2542需要量x13x12x11A1B3B2B1粮库粮站距离及运量12122430824变量更换为：连续性线性规划

第19页，共115页，2023年，2月20日，星期六模型:连续性线性规划

第20页，共115页，2023年，2月20日，星期六程序编写3MODEL:TITLE调运大米的运输问题程序3;!定义集合段;SETS:LIANGKU/1..2/:A;!定义粮库的集合;LIANGZHAN/1..3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSDATA:!粮库到粮站的距离;C=12248301224;连续性线性规划

第21页，共115页，2023年，2月20日，星期六!粮库的限量;A=48;!粮站的限量;B=245;ENDDATA[OBJ]MIN=@SUM(YULIANG:C*X);!粮库上限的约束;@FOR(LIANGKU(I):[LK]

@SUM(LIANGZHAN(J):X(I,J))<A(I));!粮站下限的约束;@FOR(LIANGZHAN(J):[LZ]

@SUM(LIANGKU(I):X(I,J))>B(J));END

连续性线性规划

第22页，共115页，2023年，2月20日，星期六程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；连续性线性规划

第23页，共115页，2023年，2月20日，星期六例2阶段生产问题(P31)某公司生产某产品,最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量12347060007270008012000766000求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.连续性线性规划

第24页，共115页，2023年，2月20日，星期六

解假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.连续性线性规划

第25页，共115页，2023年，2月20日，星期六model:title生产计划程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;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:x<a);end

连续性线性规划

第26页，共115页，2023年，2月20日，星期六连续性线性规划

第27页，共115页，2023年，2月20日，星期六Model:Title生产计划程序2;Sets:yuefen/1..4/:c,x,e,d,s;endsetsdata:c=70718076;d=60007000120006000;e=2222;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:x<a);End连续性线性规划

第28页，共115页，2023年，2月20日，星期六月份单位成本(元)销售量12347060007270008012000766000连续性线性规划

第29页，共115页，2023年，2月20日，星期六76827676---80--7472-747270生产月10000100001000010000产量600041200070006000销量4321321需求月费用cij连续性线性规划

第30页，共115页，2023年，2月20日，星期六连续性线性规划

建立模型如下：第31页，共115页，2023年，2月20日，星期六model:title生产计划程序3;sets:yuefen/1..4/:a,d,xx;!定义上三角矩阵;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70727476717375808276;d=60007000120006000;a=10000100001000010000;enddatamin=@sum(link:c*x);@for(yuefen(i):@sum(yuefen(j)|j#ge#i:x(i,j))<a(i););@for(yuefen(j):@sum(yuefen(i)|j#ge#i:x(i,j))>d(j););!得到每个月的生产量;@for(yuefen(i):xx=@sum(yuefen(j)|j#ge#i:x(i,j)));End连续性线性规划

第32页，共115页，2023年，2月20日，星期六ModelTitle::生产计划程序1VariableValueReducedCostA10000.000.000000C(1)70.000000.000000C(2)71.000000.000000C(3)80.000000.000000C(4)76.000000.000000X(1)10000.000.000000X(2)10000.000.000000X(3)5000.0000.000000X(4)6000.0000.000000E(1)2.0000000.000000E(2)2.0000000.000000E(3)2.0000000.000000E(4)2.0000000.000000D(1)6000.0000.000000D(2)7000.0000.000000D(3)12000.000.000000D(4)6000.0000.000000

连续性线性规划

第33页，共115页，2023年，2月20日，星期六连续投资10万元A：从第1年到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大。练习一下吧

连续投资第34页，共115页，2023年，2月20日，星期六

例3生产计划问题某工厂计划安排生产Ⅰ，Ⅱ两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：１）怎么安排生产使得工厂获利最大？２）产品Ⅰ的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？３）产品Ⅱ的单位利润增大到5万元，要不要改变生产计划？４）如果产品Ⅰ，Ⅱ的单位利润同时降低了1万元，要不要改变生产计划？产品Ⅰ产品Ⅱ最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23敏感性分析1

第35页，共115页，2023年，2月20日，星期六敏感性分析1

第36页，共115页，2023年，2月20日，星期六程序编写model:title生产计划问题;[maxf]max=2*x1+3*x2;[TIME]x1+2*x2<8;[A]4*x1<16;[B]4*x2<12;END敏感性分析1

第37页，共115页，2023年，2月20日，星期六运行结果ModelTitle:生产计划问题VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

对问题1，安排是生产产品Ⅰ4单位，产品Ⅱ2单位，最大盈利为14万元。敏感性分析1

第38页，共115页，2023年，2月20日，星期六目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数f斜率的变化，但是只要f的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.

敏感性分析1

第39页，共115页，2023年，2月20日，星期六要使用敏感性分析必须要在这里选择Prices&Ranges然后保存退出路径：LINGO︱Options︱GeneralSolver(通用求解程序)选项卡敏感性分析1

第40页，共115页，2023年，2月20日，星期六要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGO｜Range，敏感性分析1

第41页，共115页，2023年，2月20日，星期六Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

当前变量系数允许增加量允许减少量对问题2，产品Ⅰ的单位利润降低到1.8万元，在（1.5，∞）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，∞）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为19万元.对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到8万元.

敏感性分析1

第42页，共115页，2023年，2月20日，星期六敏感性分析2

第43页，共115页，2023年，2月20日，星期六把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，y的值就是资源的影子价格，影子价格有意义是有范围的。影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量．敏感性分析2

第44页，共115页，2023年，2月20日，星期六Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000

RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

运行结果ModelTitle:生产计划问题VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

敏感性分析2

第45页，共115页，2023年，2月20日，星期六1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：例4加工奶制品的生产计划敏感性分析第46页，共115页，2023年，2月20日，星期六x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)敏感性分析1

第47页，共115页，2023年，2月20日，星期六Max=72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100;

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。敏感性分析第48页，共115页，2023年，2月20日，星期六OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.00000035元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！敏感性分析第49页，共115页，2023年，2月20日，星期六RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE

250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000A1获利增加到30元/千克，应否改变生产计划？不变！35元可买到1桶牛奶，每天最多买多少？最多买10桶！敏感性分析第50页，共115页，2023年，2月20日，星期六问题：如何下料最节省?原料钢管:每根19米4米50根6米20根8米15根客户需求例5下料问题(P71)整数线性规划第51页，共115页，2023年，2月20日，星期六按照客户需要在一根原料钢管上安排切割的一种组合。

余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根整数线性规划第52页，共115页，2023年，2月20日，星期六model:title搜索合理的下料方式;sets:ren:;!用一根原料可下各需求长度的最多根数定义元素个数，最多为4，这里要定义5(0—4有5个数);long(ren,ren,ren):;!有三种需求长度，定义三维数组;endsetsdata:ren=1..5;!为了美观输出一些题头;@text('d:renxinglong.txt')=@write(1*'','下料方式',7*'','余料长度',@newline(1));@text('d:renxinglong.txt')=@write(12*'-',4*'',8*'-',@newline(1));!搜索所有满足过滤条件的i,j,k;@text('d:renxinglong.txt')=@writefor(long(i,j,k)|(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a

!一种下料方式下料长度和不超过总长度,合理模式的余料小于最短需求;

!输出下料方式到文本文件renxinglong.txt，我们需要的数是0--4;

:i-1,4*'',j-1,4*'',k-1,8*'',19-8*(i-1)-6*(j-1)-4*(k-1),@newline(2));!输出计算段计数过的下料方式总数;@text('d:renxinglong.txt')=@write('下料方式总数为：',2*'',n,'种');Enddata整数线性规划第53页，共115页，2023年，2月20日，星期六calc:a=@smin(8,6,4);b=@floor(19/a)+1;n=0;@for(long(i,j,k)|(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a:n=n+1);!下料方式计数;endcalcend整数线性规划第54页，共115页，2023年，2月20日，星期六为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023xi~按第i种模式切割的原料钢管根数(i=1,2,…7)决策变量

整数线性规划第55页，共115页，2023年，2月20日，星期六2.所用原料钢管总根数最少1.原料钢管剩余总余量最小目标函数：（两种标准）整数线性规划第56页，共115页，2023年，2月20日，星期六模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015约束整数约束：xi为整数整数线性规划第57页，共115页，2023年，2月20日，星期六model:Title

钢管下料;

Min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5>50; x2+2*x4+x5+3*x6>20; x3+x5+2*x7>15;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);end程序编写整数线性规划第58页，共115页，2023年，2月20日，星期六按模式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页，2023年，2月20日，星期六练习3某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，现规定应聘者需连续工作5天，试确定聘用方案。练习一下吧

第60页，共115页，2023年，2月20日，星期六例6选址问题0-1规划第61页，共115页，2023年，2月20日，星期六0-1规划

第62页，共115页，2023年，2月20日，星期六某班准备从5名游泳员中选择４人组成接力队，参加学校的4×100m混合泳接力比赛，5名队员4种泳姿的百米平均成绩如表，问如何选拔队员。队员甲乙丙丁戊蝶泳1’06’’857’’21’18’’1’10’’1’07’’4仰泳1’15’’61’06’’1’14’’21’14’’21’11’’蛙泳1’27’’1’06’’41’09’’61’09’’61’23’’8自由泳58’’653’’59’’457’’21’02’’4练习一下吧

第63页，共115页，2023年，2月20日，星期六客户增加需求：由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根例8续例5下料问题(P87)非线性规划第64页，共115页，2023年，2月20日，星期六对大规模问题，用模型的约束条件界定合理模式现有4种需求：4米50根，5米10根，6米20根，8米15根，由搜索算法确定有16种合理切割模式。决策变量

xi~按第i种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量非线性规划

第65页，共115页，2023年，2月20日，星期六满足需求目标函数（总根数）约束条件xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数模式合理：每根余料不超过3米整数约束：非线性规划

第66页，共115页，2023年，2月20日，星期六增加约束，缩小可行域，便于求解原料钢管总根数下界：

需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米非线性规划

第67页，共115页，2023年，2月20日，星期六特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：31模式排列顺序可任定

上下界非线性规划

第68页，共115页，2023年，2月20日，星期六model:Title

钢管下料-最小化钢管根数的LINGO模型;SETS:NEEDS/1..4/:LENGTH,NUM; CUTS/1..3/:X; PATTERNS(NEEDS,CUTS):R;ENDSETSDATA: LENGTH=4568; NUM=50102015; CAPACITY=19;ENDDATA非线性规划

第69页，共115页，2023年，2月20日，星期六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);!合理切割模式约束;@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))<31;!人为增加约束;@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1)); !人为增加约束;@FOR(CUTS(J):@GIN(X(J)));@FOR(PATTERNS(I,J):@GIN(R(I,J)));end非线性规划

第70页，共115页，2023年，2月20日，星期六结果模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。用去原料钢管总根数为28根。

非线性规划

第71页，共115页，2023年，2月20日，星期六

练习料场的建立与运输

建筑工地的位置(用平面坐标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页，2023年，2月20日，星期六线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。多目标规划第73页，共115页，2023年，2月20日，星期六例9重新考虑例6选址问题。(增加投资最少)多目标规划

第74页，共115页，2023年，2月20日，星期六多目标决策问题有许多共同的特点，其中最显著的是：目标的不可公度性，和目标间的矛盾性。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标问题。多目标问题的数学模型多目标规划

第75页，共115页，2023年，2月20日，星期六记可行域为D.MinxMinyxyABCD多目标规划

第76页，共115页，2023年，2月20日，星期六多目标决策的本质问题是：如何根据决策者的主观价值判断，对有效解的好坏做出比较？由于可行域中的一个点，对应目标函数是一个向量，所以问题实际是：如何比较两个向量的大小？ABABBC多目标规划

第77页，共115页，2023年，2月20日，星期六多目标规划

第78页，共115页，2023年，2月20日，星期六

多目标规划的常用解法

思想：转化为单目标问题（1）线性加权法：

权数评价函数单目标:多目标规划

第79页，共115页，2023年，2月20日，星期六（2）变权加权法：

（3）指数加权法：

多目标规划

第80页，共115页，2023年，2月20日，星期六（4）极小极大（min-max）法

多目标规划

第81页，共115页，2023年，2月20日，星期六（5）理想点法

先求解单目标的最优值确定理想点：在找距离理想点最近的点作为最优解：多目标规划

第82页，共115页，2023年，2月20日，星期六（6）加权偏差函数法

多目标规划

第83页，共115页，2023年，2月20日，星期六（7）费效比函数：多目标规划

第84页，共115页，2023年，2月20日，星期六（8）功效系数函数：对不同的性质的目标函数统一量纲，再构造效用函数：比如构造功效系数函数：然后求解规划问题：还可以对功效系数函数进行加权构造效用函数，如多目标规划

第85页，共115页，2023年，2月20日，星期六（9）参考目标法

约束法：在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比期望值坏的情况下，求主要目标的最优值。分层序列法：把多个目标按照重要程度进行排序，先求第一个目标的最有解，在达到此目标的条件下求第二个目标的最优解，依次类推宽容分层序列法：给前面的最优值设置一定的宽容值，和最优值相差宽容值之内的都是可以接受的。多目标规划

第86页，共115页，2023年，2月20日，星期六（10）逼近理想解法正负理想解：计算距离，不妨取为欧式距离：计算测度：求最大测度：多目标规划

第87页，共115页，2023年，2月20日，星期六例10投资问题某企业拟用1000万元投资于A、B两个项目的技术改造.设、分别表示分配给A、B项目的投资（万元）.据估计，投资项目A、B的年收益分别为投资的60%和70%；但投资风险损失，与总投资和单项投资均有关系：

据市场调查显示，A项目的投资前景好于B项目，因此希望A项目的投资额不小B项目.试问应该如何在A、B两个项目之间分配投资，才能既使年利润最大，又使风险损失为最小？多目标规划

第88页，共115页，2023年，2月20日，星期六

解该问题是一个非线性多目标规划问题，将它用数学语言描述出来，就是：求、，使：

而且满足：

多目标规划

第89页，共115页，2023年，2月20日，星期六对于上述多目标规划问题，处理成单目标如下：多目标规划

第90页，共115页，2023年，2月20日，星期六练习72007全国大学生数学建模竞赛B题乘公交，看奥运

第29届奥运会明年8月将在北京举行，大部分人将会乘坐公共交通工具到现场观看奥运比赛，这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线(1)、S3359→S1828(2)、S1557→S0481。。。2、同时考虑公汽与地铁线路，解决以上问题。练习：请给出模型的目标练习一下吧

第91页，共115页，2023年，2月20日，星期六线性规划与目标规划线性规划通常考虑一个目标函数(问题简单)目标规划考虑多个目标函数(问题复杂)线性规划目标规划发展演变目标规划第92页，共115页，2023年，2月20日，星期六某企业生产甲、乙两种产品，需要用到A,B,C三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。

例11生产安排问题问该企业应如何安排生产，使得在计划期内总利润最大？目标规划

第93页，共115页，2023年，2月20日，星期六该例11是一个线性规划问题，直接考虑它的线性规划模型设甲、乙产品的产量分别为x1,x2,建立线性规划模型：用Lingo软件求解,得到最优解目标规划

第94页，共115页，2023年，2月20日，星期六在上例11中，企业的经营目标不仅要考虑利润，还需要考虑多个方面，因此增加下列因素(目标)：力求使利润指标不低于1500元考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2设备A为贵重设备，严格禁止超时使用设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解目标规划

第95页，共115页，2023年，2月20日，星期六线性规划建模局限性线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。目标规划

第96页，共115页，2023年，2月20日，星期六目标规划的数学模型为了克服线性规划的局限性,目标规划采用如下手段：1.设置偏差变量;2.统一处理目标与约束;3.目标的优先级与权系数。目标规划的基本概念目标规划

第97页，共115页，2023年，2月20日，星期六1.设置偏差变量用偏差变量(Deviationalvariables)来表示实际值与目标值之间的差异，令----超出目标的差值，称为正偏差变量----未达到目标的差值，称为负偏差变量其中与至少有一个为0约定如下：当实际值超过目标值时，有当实际值未达到目标值时，有当实际值与目标值一致时，有目标规划

第98页，共115页，2023年，2月20日，星期六2.统一处理目标与约束在目标规划中，约束可分两类，一类是对资源有严格限制的，称为刚性约束(HardConstraint)；例如在用目标规划求解例11中设备A禁止超时使用，则有刚性约束另一类是可以不严格限制的，连同原线性规划的目标,构成柔性约束(SoftConstraint).例如在求解例11中，我们希望利润不低于1500元，则目标可表示为目标规划

第99页，共115页，2023年，2月20日，星期六求解例11中甲、乙两种产品的产量尽量保持1:2的比例，则目标可表示为设备C可以适当加班，但要控制，则目标可表示为设备B既要求充分利用，又尽可能不加班，则目标可表示为从上面的分析可以看到：如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差．目标规划

第100页，共115页，2023年，2月20日，星期六3.目标的优先级与权系数在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1,P2,...表示不同的因子,并规定Pk>>Pk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。目标规划

第101页，共115页，2023年，2月20日，星期六解在例11中设备A是刚性约束，其于是柔性约束．首先，最重要的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备B和C的工作时间要有所控制，列为第三级，设备B的重要性是设备C的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。用目标规划方法求解例11目标规划

第102页，共115页，2023年，2月20日，星期六目标规划的一般模型目标规