数学规划建模学习教案.pptx

《数学规划建模学习教案.pptx》由会员分享，可在线阅读，更多相关《数学规划建模学习教案.pptx（153页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学数学(shxu)规划建模规划建模第一页，共153页。（2）所确定的）所确定的x的范围称为可行域的范围称为可行域feasibleregion，满足（，满足（2）的解）的解x称为可行解称为可行解feasiblesolution，同时满足（，同时满足（1）（）（2）的解）的解x称为最优解称为最优解Optimalsolution，整个可行域上的最优解称为全局最优解，整个可行域上的最优解称为全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为局部，可行域中某个领域上的最优解称为局部(jb)最优解最优解localoptimalsolution。最优解所对应的目标

2、函数值称为最优值。最优解所对应的目标函数值称为最优值optimum。第1页/共153页第二页，共153页。优化模型优化模型(mxng)的分类的分类（一）按有无约束条件（一）按有无约束条件（2）可分为：）可分为：1.无约束优化无约束优化 unconstrained optimization。2.约束优化约束优化constrained optimization。大部分实际大部分实际(shj)问题都是约束优化问题。问题都是约束优化问题。第2页/共153页第三页，共153页。（二）按决策变量取值是否连续可分为：（二）按决策变量取值是否连续可分为：1.数学规划或连续优化。数学规划或连续优化。可继续划分可

3、继续划分(hu fn)为线性规划为线性规划(LP)Linear programming和非线性规划和非线性规划(NLP)Nonlinear programming。在非线性规划中有一种规划叫做二次规划。在非线性规划中有一种规划叫做二次规划(QP)Quadratic programming，目标为二次函数，约束为线性函数。，目标为二次函数，约束为线性函数。2.离散优化或组合优化。离散优化或组合优化。包含：整数规划包含：整数规划(IP)Integer programming，整数规划中又包含很重要的一类规划：，整数规划中又包含很重要的一类规划：0-1（整数）规划（整数）规划Zero-one pro

4、gramming，这类规划问题的决策变量只取，这类规划问题的决策变量只取0或者或者1。第3页/共153页第四页，共153页。（三）按目标的多少可分为：（三）按目标的多少可分为：1.单目标规划。单目标规划。2.多目标规划。多目标规划。（四）按模型中参数和变量是否具有不确定性可分为：（四）按模型中参数和变量是否具有不确定性可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）按问题（五）按问题(wnt)求解的特性可分为：求解的特性可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。第4页/共153页第五页，共1

5、53页。优化问题求解常用的软件优化问题求解常用的软件LINGO软件和软件和MATLAB软件。软件。对于对于LINGO软件，线性优化求解程序通常使用单纯形法软件，线性优化求解程序通常使用单纯形法simplexmethod，单纯形法虽然在实际应用，单纯形法虽然在实际应用(yngyng)中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interiorpointmethod备选（备选（LINGO中一般称为障碍法，即中一般称为障碍法，即barrier），非线性优化求解程序采

6、用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序分解原问题成一系列的凸规划。分解原问题成一系列的凸规划。第5页/共153页第六页，共153页。软件软件(run jin)介绍介绍例例1帆船生产计划帆船生产计划SAILCO公司需要决定下四个季度的帆船生产量。公司需要决定下四个季度的帆船生产量。下四个季度的

7、帆船需求量分别是下四个季度的帆船需求量分别是40条，条，60条，条，75条，条，25条，这些需求必条，这些需求必须按时满足。每个季度正常的生产能力是须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用条帆船，每条船的生产费用为为400美元。如果加班生产，每条船的生产费用为美元。如果加班生产，每条船的生产费用为450美元。每个季度末，美元。每个季度末，每条船的库存费用为每条船的库存费用为20美元。假定生产提前期为美元。假定生产提前期为0，初始库存为，初始库存为10条船。条船。如何如何(rh)安排生产可使总费用最小？安排生产可使总费用最小？分析分析:DEM需求量，需求量，RP正常生产的

8、产量，正常生产的产量，OP加班生产的产量，加班生产的产量，INV库存量，库存量，则则DEM,RP,OP,INV对每个季度对每个季度(jd)都应该有一个对应都应该有一个对应的值，也就说他们都应该是一个由的值，也就说他们都应该是一个由4个元素组成的数组，其中个元素组成的数组，其中DEM是已知的，而是已知的，而RP,OP,INV是未知数。是未知数。第6页/共153页第七页，共153页。目标函数目标函数(hnsh)：正常生产费加班生产费储存费：正常生产费加班生产费储存费最小最小约束条件：约束条件：1）能力）能力(nngl)限制：限制：2）产品数量的平衡）产品数量的平衡(pnghng)方程：方程：4）变

9、量非负）变量非负3）初始库存：）初始库存：引例引例 模型建立模型建立第7页/共153页第八页，共153页。记四个季度组成的集合QUARTERS=1，2，3，4，它们就是上面数组的下标集合，而数组DEM,RP,OP,INV对集合QUARTERS中的每个元素1，2，3，4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性(shxng)”的概念，把QUARTERS=1，2，3，4称为集合，把DEM,RP,OP,INV称为该集合的属性(shxng)(即定义在该集合上的属性(shxng)。集合集合(jh)与属性与属性第8页/共153页第九页，共153页。QUART

10、ERS集合的属性DEM RPOP INVQUARTERS集合2341 集合集合(jh)与属性与属性第9页/共153页第十页，共153页。集合元素及集合的属性确定的所有集合元素及集合的属性确定的所有(suyu)变量变量集合QUARTERS的元素1234定义在集合QUARTERS上的属性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4)集合集合(jh)与属性与属性第10页/共153页第十一页，共153页。程序程序(chngx)编写编写MODEL:!集合集

11、合(jh)段：定义集合段：定义集合(jh)SET，元素，元素member及其属性及其属性attribute；SETS:QUARTERS/1,2,3,4/:DEM,RP,OP,INV;ENDSETS!目标与约束段：没有开始和结束标记，顺序无关；目标与约束段：没有开始和结束标记，顺序无关；MIN=SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I);FOR(QUARTERS(I):RP(I)1（greaterthan）第11页/共153页第十二页，共153页。展开式展开式LINGOGenerateDisplyModel(Ctrl+G)MIN=SUM(QUART

12、ERS(I):400*RP(I)+450*OP(I)+20*INV(I);FOR(QUARTERS(I):RP(I)40);FOR(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);第12页/共153页第十三页，共153页。全局全局(qunj)最优最优解解RP=(40,40,40,25)OP=(0,10,35,0)最小成本最小成本(chngbn)=78450自动自动(zdng)生成行号生成行号 结果报告结果报告第13页/共153页第十四页，共153页。例例例例2 2 2 2

13、运输运输运输运输(ynsh)(ynsh)(ynsh)(ynsh)问题问题问题问题第14页/共153页第十五页，共153页。解：设解：设A1,A2调运到三个粮站调运到三个粮站(lingzhn)的大米分别为的大米分别为x11，x12，x13，x21，x22，x23吨。吨。题设量可总到下表：题设量可总到下表：84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824第15页/共153页第十六页，共153页。结合结合(jih)存量限制和需量限制得数学模型：存量限制和需量限制得数学模型：第16页/共153页第十七页

14、，共153页。程序编写程序编写推荐推荐MODEL:TITLE调运大米调运大米(dm)的运输问题程序的运输问题程序;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!粮库到粮站的距离粮库到粮站的距离;C=12248301224;第17页/共153页第十八页，共153页。!粮库的限量粮库的限量;A=4 8;!粮站粮站(lingzhn)的限量的限量;B=2 4 5;END

15、DATAOBJMIN=SUM(YULIANG:C*X);!粮库上限的约束粮库上限的约束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 第18页/共153页第十九页，共153页。程序的调试程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找(xnzho)出错的范围；出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；可以边写程序边运行

16、，保证每行书写都是正确的程序；第19页/共153页第二十页，共153页。料场的建立与运输料场的建立与运输建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，表示，距离距离(jl)单位：公里单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个下表给出。有两个临时料场位于临时料场位于P(5,1),Q(2,7),日储量各有日储量各有20吨。吨。(1)从从A,B两料两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。场分别向各工地运送多少吨水泥，使总的吨公里数最小。(2)两两个新的料场应建在何处，节省的吨公里数有多大？个新的料场应建在何处，节省的吨公里数有多大？a1.258.75

17、0.55.7537.25b1.250.754.7556.57.75d3547611 非线性规划非线性规划(guhu)引例引例第20页/共153页第二十一页，共153页。已知为LP模型，未知为NLP模型 引例引例(yn l)模型建立模型建立料场向工地的运送量为：料场向工地的运送量为：工地：位置工地：位置水泥日用量：水泥日用量：料场：位置料场：位置日储量：日储量：第21页/共153页第二十二页，共153页。利用集合的概念利用集合的概念(ginin)，可以定义需求点，可以定义需求点DEMAND和供和供应点应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。但决策变。

18、但决策变量量(运送量运送量)cij与集合与集合DEMAND和集合和集合SUPPLY都有关系的。该都有关系的。该如何定义这样的属性？如何定义这样的属性？集合的属性相当于以集合的元素集合的属性相当于以集合的元素(yuns)为下标的数组。这为下标的数组。这里的里的cij相当于二维数组。它的两个下标分别来自集合相当于二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY，因此可以定义一个由二元对组成的新的集合，然后，因此可以定义一个由二元对组成的新的集合，然后将将cij定义成这个新集合的属性，这个集合称为派生集合。定义成这个新集合的属性，这个集合称为派生集合。派生派生(pishng)集合集合第

19、22页/共153页第二十三页，共153页。程序程序(chngx)编写编写MODEL:TitleLocationProblem;sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:!locationsforthedemand(需求点的位置需求点的位置(wizhi);a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;!quantitiesofthedemandandsupply（供需量）（供需量）;d=3,5,4,7,6,11;e=20,2

20、0;enddata基本集合基本集合(jh)primaryset与与派生集合派生集合(jh)derivedset（定义多维数组）（定义多维数组）第23页/共153页第二十四页，共153页。程序程序(chngx)编写编写!初始段：对集合属性定义初值（迭代初始段：对集合属性定义初值（迭代(didi)算法的迭代算法的迭代(didi)初值）初值）;init:!initiallocationsforthesupply（初始点）（初始点）;x,y=5,1,2,7;endinit!Objectivefunction（目标）（目标）;OBJmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2

21、+(y(j)-b(i)2)(1/2);!demandconstraints（需求约束）（需求约束）;for(demand(i):DEMAND_CONsum(supply(j):c(i,j)=d(i););!supplyconstraints（供应约束）（供应约束）;for(supply(i):SUPPLY_CONsum(demand(j):c(j,i)sum(yuefen(i)|i#le#j:d);sum(yuefen:x)=sum(yuefen:d);for(yuefen:xa);end 第38页/共153页第三十九页，共153页。第39页/共153页第四十页，共153页。Model:Tit

22、le 生产计划生产计划(jhu)程序程序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第40页/共153页第四十一页，共153页。月月份份单位成本单位成本(元元)销售量销售量1234 70 6000 72 7000 80

23、12000 76 6000第41页/共153页第四十二页，共153页。76827676-80-7472-747270生产月10000100001000010000产量600041200070006000销量4321321需求月费用cij第42页/共153页第四十三页，共153页。第43页/共153页第四十四页，共153页。model:title 生产计划程序3;sets:yuefen/1.4/:a,d,xx;!定义上三角矩阵(j zhn);link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d

24、=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):x(i,j);End第44页/共153页第四十五页，共153页。Model Title:生产计划生产计划(jhu)程序程序1 Variable Value Reduced Cost 第45页/共153页第四十六页，共153页。课堂练习课堂练习1:1:转运转运(zhun(zh

25、un yn)yn)问题问题设有两个工厂设有两个工厂(gngchng)A、B，产量都是，产量都是 10万个，工厂万个，工厂(gngchng)有三个仓库有三个仓库 x，y，z，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。工厂万个。工厂(gngchng)到仓库、仓库到顾客的运费单价（元到仓库、仓库到顾客的运费单价（元/个）见下表所示。试求总运费最少的运输方案以及总运费。个）见下表所示。试求总运费最少的运输方案以及总运费。AB甲甲乙乙丙丙丁丁x43571020y2196715z5220674第46

26、页/共153页第四十七页，共153页。连续连续(linx)投资投资10万元万元A：从第：从第1年年到第到第4年每年初要投资，次年末回收年每年初要投资，次年末回收(hushu)本利本利B：，最大投资：，最大投资(tuz)4万元万元C：，最大投资：，最大投资3万元万元D：。：。求：求：5年末总资本最大。年末总资本最大。课堂练习课堂练习课堂练习课堂练习2:2:2:2:连续投资连续投资连续投资连续投资第47页/共153页第四十八页，共153页。灵敏度分析与影子灵敏度分析与影子(yng zi)价格价格第48页/共153页第四十九页，共153页。例例4 生产计划问题某工厂计划安排生产生产计划问题某工厂计划

27、安排生产，两种产品，已知每种单位产品的利两种产品，已知每种单位产品的利润，生产单位产品所需设备润，生产单位产品所需设备(shbi)台时及台时及A,B两种原材料的消耗，现有原材料和两种原材料的消耗，现有原材料和设备设备(shbi)台时的定额如表所示，问：台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到万元，要不要改变生产计划，如果降低到的单位利润降低到万元，要不要改变生产计划，如果降低到1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万元，要不要改变生产计划？万元，要不要改变生产计划？）如果产品）如果产品，的单位

28、利润同时降低了的单位利润同时降低了1万元，要不要改变生产计划？万元，要不要改变生产计划？产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23第49页/共153页第五十页，共153页。第50页/共153页第五十一页，共153页。程序编写程序编写(binxi)model:title生产计划问题生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END第51页/共153页第五十二页，共153页。运行运行(ynxng)结果结果ModelTitle:生产计划问题生产计划问题VariableValueReduced

29、CostRowSlackorSurplusDualPrice对问题1，安排是生产(shngchn)产品4单位，产品2单位，最大盈利为14万元。第52页/共153页第五十三页，共153页。线性模型线性模型(mxng)敏感性理论敏感性理论1目标函数的系数变化目标函数的系数变化(binhu)的敏感性分析的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产(shngchn)计划不会变.第53页/共153页第五十四页，共153页。线性模型线性模型(mxng)敏感性

30、分析敏感性分析1要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择(xunz)Prices&Ranges然后保存退出然后保存退出路径：路径：LINGOOptionsGeneralSolver(通用通用(tngyng)求解程序求解程序)选项卡选项卡第54页/共153页第五十五页，共153页。要调出敏感性分析的结果，必要调出敏感性分析的结果，必须须(bx)先求解后再在程序窗先求解后再在程序窗口下点击口下点击LINGORange，第55页/共153页第五十六页，共153页。Ranges in which the basis is unchanged:Objective Coeffici

31、ent Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease B 16.00000 当前变量(binling)系数允许(ynx)增加量 允许(ynx)减少量对问题对问题2，产品，产品的单位利润降低到万元，在（，的单位利润降低到万元，在（，）之间，所以不改变生产计划。）之间，所以不改变生产计划。如果降低到如果降低到1万元，不在（，万元，不在（，）内，要改

32、变生产计划。在程序中将目标函数的）内，要改变生产计划。在程序中将目标函数的系数系数“2”改为改为“1”，可得新的计划为，可得新的计划为安排是生产产品安排是生产产品2单位，产品单位，产品3单位，最大盈利单位，最大盈利为为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，单位，最大盈利为最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大

33、利润降低到8万元万元.第56页/共153页第五十七页，共153页。第57页/共153页第五十八页，共153页。把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品(chnpn)获得更多利润的前提下的最小利润.在最优情况下，在最优情况下，y的值就是资源的的值就是资源的影子影子(yngzi)价格，影子价格，影子(yngzi)价格有意义是有范围的。价格有意义是有范围的。影子价格经济含义是：在资源得到影子价格经济含义是：在资源得到(d do)最优配最优配置，使总效益最大时，该资源投入量每增加一个单置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量位所带来总收益的增加量 第58

34、页/共153页第五十九页，共153页。Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease B 16.00000 运行运行(ynxng)结果结果ModelTitle:生产计划问题生产计划问题VariableValueReducedC

35、ostRowSlackorSurplusDualPriceMAXF14.00000A0.000000B0.000000TIME4.000000第59页/共153页第六十页，共153页。1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶(nini)时间时间(shjin)480小时小时至多至多(zhdu)加工加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工

36、资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：例例5加工奶制品的生产计划加工奶制品的生产计划第60页/共153页第六十一页，共153页。x1桶牛奶桶牛奶(ni ni)生产生产A1 x2桶牛奶桶牛奶(ni ni)生产生产A2 获利获利(hul)243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性规划模型线性规划模型(LP)第61页/共153页第六十二页，共153页。Max=72*x1+64*x2;x1+x

37、250;12*x1+8*x2480;3*x1100;OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=220桶牛奶生产桶牛奶生产(shngchn)A1,30桶生产桶生产(shngchn)A2，利润，利润3360元。元。第62页/共153页第六十三页，共153页。OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICES2)0.0000003)0.0000004)40.00000035元

38、可买到元可买到1桶牛奶桶牛奶(nini)，要买吗？，要买吗？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程序程序(chngx)编写编写第73页/共153页第七十四页，共153页。按模式按模式(msh)2(msh)2切割切割1212根根,按模式按模式(msh)5(msh)5切割切割1515根，根，余料余料2727米米 最优解：最优解：x2=12,x5=15,x2=12,x5=15,其余其余(qy)(qy)为为0 0；最优值：最优值：2727最优解：最优

39、解：x2=15,x5=5,x7=5,x2=15,x5=5,x7=5,其余其余(qy)(qy)为为0 0；最优值：最优值：2525。按模式按模式2切割切割15根，按模式根，按模式5切割切割5根，按模式根，按模式7切割切割5根，共根，共25根，根，余料余料35米米当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 第74页/共153页第七十五页，共153页。课堂练习课堂练习3某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要50人，周五至少需要人，周五至少需要80人，周六和周日至少需要人，周六和

40、周日至少需要90人，现规定应聘者需连续工作人，现规定应聘者需连续工作(gngzu)5天，试确定聘用方案。天，试确定聘用方案。第75页/共153页第七十六页，共153页。0-1规划规划(guhu)第76页/共153页第七十七页，共153页。例例7选址选址(xunzh)问题问题第77页/共153页第七十八页，共153页。第78页/共153页第七十九页，共153页。例例8 面试顺序问题有面试顺序问题有 4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于名同学到一家公司参加三个阶段的面试，公司要求每个同学都必

41、须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于4名同学的专业名同学的专业(zhuny)背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这4名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上8：00，请问他们最早何时能离开公司？，请问他们最早何时能离开公司？秘书初试秘书初试主管复试主管复试经理面试经理面试同学甲同学甲131520同学乙同学乙102018同学丙同学丙201610同学丁同学丁81015第79页/共153页第八十

42、页，共153页。第80页/共153页第八十一页，共153页。优化目标(mbio)为：约束条件：个人时间(shjin)先后次序约束：同阶段不同(b tn)同学时间不相容：（同阶段靠前同学的完成时间小于靠后同学的开始时间）第81页/共153页第八十二页，共153页。可将目标改为(i wi)如下线性优化目标：第82页/共153页第八十三页，共153页。程序程序(chngx)编写编写 model:title:面试问题;sets:student/1.4/:;office/1.3/:;link1(student,office):x,t;link2(student,student)|&1#lt#&2:y;e

43、ndsetsdata:t=13 15 20 10 20 18 20 16 10 8 10 15;Enddatamin=time;!time大于每名同学最后面试完毕(wnb)时间;for(student(i):timex(i,3)+t(i,3););第83页/共153页第八十四页，共153页。!面试先后次序约束;for(student(i):for(office(j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1););!每个阶段只能面试一个同学,y(i,k)=1表示第k名同学排在第i名同学前面(qin mian);取M=1000；for(student(i):for(office(j

44、):for(student(k)|k#gt#i:x(i,j)+t(i,j)-x(k,j)1000*y(i,k);for(student(i):for(office(j):for(student(k)|k#gt#i:x(k,j)+t(k,j)-x(i,j)NUM(I);!满足需满足需求求(xqi)约束约束;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);!人为增加约束人为增加约束;

45、FOR(CUTS(J):GIN(X(J);FOR(PATTERNS(I,J):GIN(R(I,J);end第94页/共153页第九十五页，共153页。结果结果(jigu)模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。用去原料钢管总根数为用去原料钢管总根数为28根。根。第95页/共153

46、页第九十六页，共153页。课堂练习课堂练习5 下料问题下料问题 （2004 全国全国(qun u)研究生数学建模竞赛研究生数学建模竞赛B题）题）单一原材料的长度为单一原材料的长度为3000mm,需要完成一项有需要完成一项有53种不同长度零件的种不同长度零件的下料任务下料任务.具体数据具体数据(shj)见表一，在每个切割点处由于锯缝所产生的见表一，在每个切割点处由于锯缝所产生的损耗为损耗为5mm.据估计，该企业每天最大下料能力是据估计，该企业每天最大下料能力是100块块，要求在，要求在4天内天内完成的零件标号为完成的零件标号为:5,7,9,12,15,18,20,25,28,36,48;要求不迟

47、于要求不迟于6天完成的天完成的零件标号为零件标号为:4,11,24,29,32,38,40,46,50.第96页/共153页第九十七页，共153页。课堂练习课堂练习6料场的建立料场的建立(jinl)与运输与运输建筑工地的位置建筑工地的位置(用平面坐用平面坐标标a,b表示，距离单位：公里表示，距离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临下表给出。有两个临时料场位于时料场位于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别向各工两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，地运送多少吨水泥，使总的吨公里数最小。

48、两个新的料场应建在何处，节省的吨公里数有多大？节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611第97页/共153页第九十八页，共153页。多目标多目标(mbio)规划规划 第98页/共153页第九十九页，共153页。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价

49、。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续(jx)进行，这将给人们进一步应用线性规划方法带来困难。进行，这将给人们进一步应用线性规划方法带来困难。第99页/共153页第一百页，共153页。例例10 重新考虑例重新考虑例 6选址选址(xun zh)问题。问题。第

50、100页/共153页第一百零一页，共153页。多目标决策问题有许多共同的特点，其中最显著的是：目标的不可公度性，和目标间的矛盾性。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标决策问题有许多共同的特点，其中最显著的是：目标的不可公度性，和目标间的矛盾性。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解(qi ji)多目标问题。多目标问题。多目标多目标(mbio)问题的数学模型问题的数学模型 第101页/共153页第一百零二页，共153页。记可行记可行(kxng)域为域为D.第102页/共153页第一百零三页，共153页。多目标决策的本质问