《数学规划建模.pptx》由会员分享，可在线阅读，更多相关《数学规划建模.pptx（153页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、（2）所确定的）所确定的x的范围称为的范围称为可行域可行域feasibleregion，满足（，满足（2）的解）的解x称为称为可行可行解解feasiblesolution，同时满足（，同时满足（1）（）（2）的解）的解x称为称为最优解最优解Optimalsolution，整，整个可行域上的最优解称为个可行域上的最优解称为全局最优解全局最优解globaloptimalsolution，可行域中某个领域，可行域中某个领域上的最优解称为上的最优解称为局部最优解局部最优解localoptimalsolution。最优解所对应的目标函数值称。最优解所对应的目标函数值称为为最优值最优值optimum。第1
2、页/共153页优化模型的分类优化模型的分类（一）按有无约束条件（一）按有无约束条件（2）可分为：）可分为：1.无约束优化无约束优化unconstrained optimization。2.约束优化约束优化constrained optimization。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。第2页/共153页（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可分为：1.数学规划或连续优化数学规划或连续优化。可继续划分为可继续划分为线性规划线性规划(LP)Linear programming和和非线性规划非线性规划(NLP)Nonlinear progra
3、mming。在非线性规划中有一种规划叫做。在非线性规划中有一种规划叫做二次规划二次规划(QP)Quadratic programming，目标为二次函数，约束为线性函数。，目标为二次函数，约束为线性函数。2.离散优化或组合优化离散优化或组合优化。包含：包含：整数规划整数规划(IP)Integer programming，整数规划中又包含很重要的一类，整数规划中又包含很重要的一类规划：规划：0-1（整数）规划（整数）规划Zero-one programming，这类规划问题的决策变量只，这类规划问题的决策变量只取取0或者或者1。第3页/共153页（三）（三）按目标的多少按目标的多少可分为：可分为
4、：1.单目标规划。单目标规划。2.多目标规划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不确定性可分为：可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）（五）按问题求解的特性按问题求解的特性可分为：可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。第4页/共153页优化问题求解常用的软件优化问题求解常用的软件LINGO软件和软件和MATLAB软件。软件。对于对于LINGO软件，线性优化求解程序通常使用软件，线性优化求解程序通常使用单纯形法单纯形法simple
5、xmethod，单纯形，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了能解大规模问题，也提供了内点算法内点算法interiorpointmethod备选（备选（LINGO中一般称为障中一般称为障碍法，即碍法，即barrier），非线性优化求解程序采用的是），非线性优化求解程序采用的是顺序线性规划法顺序线性规划法，也可用，也可用顺序二次顺序二次规划法规划法，广义既约梯度法，另外可以使用多初始点（，广义既约梯度法，另外可以使用多初始点（LINGO中称中称multist
6、art）找多个局）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序部最优解增加找全局最优解的可能，还具有全局求解程序分解原问题成一系列的分解原问题成一系列的凸凸规划规划。第5页/共153页软件介绍软件介绍例例1帆船生产计划帆船生产计划SAILCO公司需要决定下四个季度的帆船生公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是产量。下四个季度的帆船需求量分别是40条，条，60条，条，75条，条，25条，条，这些需求必须按时满足。每个季度正常的生产能力是这些需求必须按时满足。每个季度正常的生产能力是40条帆船，条帆船，每条船的生产费用为每条船的生产费用为400美元。如果加班
7、生产，每条船的生产费美元。如果加班生产，每条船的生产费用为用为450美元。每个季度末，每条船的库存费用为美元。每个季度末，每条船的库存费用为20美元。假定美元。假定生产提前期为生产提前期为0，初始库存为，初始库存为10条船。如何安排生产可使总费用条船。如何安排生产可使总费用最小？最小？分析分析:DEM需求量，需求量，RP正常生产的产量，正常生产的产量，OP加班生产的产量，加班生产的产量，INV库存量，库存量，则则DEM,RP,OP,INV对每个季度都应该有一个对应的值，也对每个季度都应该有一个对应的值，也就说他们都应该是一个由就说他们都应该是一个由4个元素组成的个元素组成的数组数组，其中，其中
8、DEM是已是已知的，而知的，而RP,OP,INV是未知数。是未知数。第6页/共153页目标函数：正常生产费加班生产费储存费目标函数：正常生产费加班生产费储存费最小最小约束条件：约束条件：1）能力限制：）能力限制：2）产品数量的平衡方程：）产品数量的平衡方程：4）变量非负）变量非负3）初始库存：）初始库存：引例引例 模型建立模型建立第7页/共153页 记四个季度组成的集合QUARTERS=1，2，3，4，它们就是上面数组的下标集合，而数组DEM,RP,OP,INV对集合QUARTERS中的每个元素1，2，3，4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系，引入了“集合”及其“
9、属性”的概念，把QUARTERS=1，2，3，4称为集合，把DEM,RP,OP,INV称为该集合的属性(即定义在该集合上的属性)。集合与属性集合与属性第8页/共153页QUARTERS集合的属性DEM RPOP INVQUARTERS集合2341 集合与属性集合与属性第9页/共153页集合元素及集合的属性确定的所有集合元素及集合的属性确定的所有变量变量集合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
10、(3)INV(4)集合与属性集合与属性第10页/共153页 程序编写程序编写MODEL:!集合段：定义集合集合段：定义集合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页 展开式展开式LINGOGenerateDi
11、splyModel(Ctrl+G)MIN=SUM(QUARTERS(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页全局最优解全局最优解RP=(40,40,40,25)OP=(0,10,35,0)最小成本最小成本=78450自动生成行号自动生成行号 结果报告结果报告第13页/共153页例例2 2 运输问题运输问题第14页/共153页
12、解：设解：设A1,A2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x11，x12，x13，x21，x22，x23吨。吨。题设量可总到下表：题设量可总到下表：84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824第15页/共153页结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：第16页/共153页程序编写程序编写推荐推荐MODEL:TITLE 调运大米的运输问题程序调运大米的运输问题程序;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库
13、的集合;LIANGZHAN/1.3/:B;!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!粮库到粮站的距离粮库到粮站的距离;C=12 24 8 30 12 24;第17页/共153页!粮库的限量粮库的限量;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 第18页/共153页程序的调试程序的调试1.
14、直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；可以边写程序边运行，保证每行书写都是正确的程序；第19页/共153页料场的建立与运输料场的建立与运输建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，距表示，距离单位：公里离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时料场位下表给出。有两个临时料场位于
15、于P(5,1),Q(2,7),日储量各有日储量各有20吨。吨。(1)从从A,B两料场分别向各两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。工地运送多少吨水泥，使总的吨公里数最小。(2)两个新的料场两个新的料场应建在何处，节省的吨公里数有多大？应建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611 非线性规划引例非线性规划引例第20页/共153页已知为LP模型，未知为NLP模型 引例引例 模型建立模型建立料场向工地的运送量为：料场向工地的运送量为：工地：位置工地：位置水泥日用量：水泥日用量：料场：位置料场：位
16、置日储量：日储量：第21页/共153页利用集合的概念，可以定义需求点利用集合的概念，可以定义需求点DEMAND和供应点和供应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。但决策变量。但决策变量(运送量运送量)cij与集合与集合DEMAND和集合和集合SUPPLY都有关系的。该如都有关系的。该如何定义这样的属性？何定义这样的属性？集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的cij相当于二维数组。它的两个下标分别来自集合相当于二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY，因此可以定义一个由二
17、元对组成的新的集合，然后，因此可以定义一个由二元对组成的新的集合，然后将将cij定义成这个新集合的属性，这个集合称为定义成这个新集合的属性，这个集合称为派生集合派生集合。派生集合派生集合第22页/共153页 程序编写程序编写MODEL:TitleLocationProblem;sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:!locationsforthedemand(需求点的位置需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.
18、5,7.75;!quantitiesofthedemandandsupply（供需量）（供需量）;d=3,5,4,7,6,11;e=20,20;enddata基本集合基本集合primaryset与与派生集合派生集合derivedset（定义多维数组）（定义多维数组）第23页/共153页 程序编写程序编写!初始段：对集合属性定义初值（迭代算法的迭代初值）初始段：对集合属性定义初值（迭代算法的迭代初值）;init:!initiallocationsforthesupply（初始点）（初始点）;x,y=5,1,2,7;endinit!Objectivefunction（目标）（目标）;OBJmin=
19、sum(link(i,j):c(i,j)*(x(j)-a(i)2+(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页第39页/共153页
20、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第40页/共153页月月份份单位成本单位成本(元元)销售量销售量1234 70 6000 72 7000 80 12000 76
21、 6000第41页/共153页76827676-80-7472-747270生产月10000100001000010000产量600041200070006000销量4321321需求月费用cij第42页/共153页第43页/共153页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;end
22、datamin=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页Model Title:生产计划程序生产计划程序1 Variable Value Reduced Cost 第45页/共153页课堂练习课堂练习1:1:转运问题转运问题设有两个工厂设有两个工厂A、B，产量都是，产量都是10万个，工厂有三个仓库万个，工厂有三个仓库x，y，z，产品都先送，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁
23、，需求量分别为到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。工万个。工厂到仓库、仓库到顾客的运费单价（元厂到仓库、仓库到顾客的运费单价（元/个）见下表所示。试求总运费最少的运输方个）见下表所示。试求总运费最少的运输方案以及总运费。案以及总运费。AB甲甲乙乙丙丙丁丁x43571020y2196715z5220674第46页/共153页连续投资连续投资10万元万元A：从第：从第1年年到第到第4年每年初要投资，次年末回收本利年每年初要投资，次年末回收本利B：，最大投资：，最大投资4万元万元C：，最大投资：，最大投资3万元万元D：。：。求：求：5年末总资本最大。年末总资本最
24、大。课堂练习课堂练习2:2:连续投资连续投资第47页/共153页灵敏度分析与影子价格灵敏度分析与影子价格第48页/共153页 例例4 生产计划问题生产计划问题某工厂计划安排生产某工厂计划安排生产，两种产品，已知每两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到万元，要不要改变生产计划，如果降的单位利润降低到万元，要不要改变生产计
25、划，如果降低到低到1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万元，要不要改变生产计划？万元，要不要改变生产计划？）如果产品）如果产品，的单位利润同时降低了的单位利润同时降低了1万元，要不要改变生产万元，要不要改变生产计划？计划？产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23第49页/共153页第50页/共153页程序编写程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END第51页/共153页运行结果运行结果 Model Title:生产计
26、划问题 Variable Value Reduced Cost Row Slack or Surplus Dual Price 对问题1，安排是生产产品4单位，产品2单位，最大盈利为14万元。第52页/共153页 线性模型敏感性理论线性模型敏感性理论1目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.第53页/共153页 线性模型敏感性分析线性模型敏感性分析1要使用敏感性分析要使用敏感性分析必
27、须要在这里选择必须要在这里选择Prices&Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneralSolver(通用求解程序通用求解程序)选项卡选项卡第54页/共153页要调出敏感性分析的结果，要调出敏感性分析的结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange，第55页/共153页Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increas
28、e Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease B 16.00000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到万元，在（，的单位利润降低到万元，在（，）之间，所以不改变生）之间，所以不改变生产计划。如果降低到产计划。如果降低到1万元，不在（，万元，不在（，）内，要改变生产计划。在程序中将）内，要改变生产计划。在程序中将目标函数的系数目标函数的系数“2”改为改为“1”，可得新的计划为，可得新的计划为安排是生产产品安排是生产产品2单位，单位
29、，产品产品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大利润降低到8万元万元.第56页/共153页第57页/共153页把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，在最
30、优情况下，y的值就是资的值就是资源的源的影子价格，影子价格，影子价格有意影子价格有意义是有范围的义是有范围的。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量加一个单位所带来总收益的增加量 第58页/共153页Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrea
31、se Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease B 16.00000 运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost Row Slack or Surplus Dual Price MAXF 14.00000 A 0.000000 B 0.000000 TIME 4.000000 第59页/共153页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时
32、小时至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：例例5加工奶制品的生产计划加工奶制品的生产计划第60页/共153页x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变
33、量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性规线性规划模型划模型(LP)第61页/共153页Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第62页/共153页OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKO
34、RSURPLUSDUALPRICES2)0.0000003)0.0000004)40.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程序编写程序编写第73页/共153页按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；
35、最优值：最优值：25。按模式按模式2切割切割15根，按模式根，按模式5切割切割5根，按模式根，按模式7切割切割5根，共根，共25根，余料根，余料35米米当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 第74页/共153页课堂练习课堂练习3某服务部门一周中每天需要不同数目的雇员，周一到周四每天至某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要少需要50人，周五至少需要人，周五至少需要80人，周六和周日至少需要人，周六和周日至少需要90人，现规定应聘者需人，现规定应聘者需连续工作连续工作5天，试确定聘用方案。天，试确定聘用方案。第75页/共153页0
36、-1规划规划第76页/共153页例例7选址问题选址问题第77页/共153页第78页/共153页 例例8 面试顺序问题面试顺序问题有有4名同学到一家公司参加三个阶段的面试，名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到主管公司要求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由部门处复试，最后到经理处参加免试，并且不允许插队，由于于4名同学的专业背景不同，所以每人在三个阶段的面试时间名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这也不同，如表所示，这4名同学约定他们全部面试完以后一起名同学
37、约定他们全部面试完以后一起离开公司，假定现在时间是早上离开公司，假定现在时间是早上8：00，请问他们最早何时能，请问他们最早何时能离开公司？离开公司？秘书初试秘书初试主管复试主管复试经理面试经理面试同学甲同学甲131520同学乙同学乙102018同学丙同学丙201610同学丁同学丁81015第79页/共153页第80页/共153页优化目标为：约束条件：个人时间先后次序约束：同阶段不同同学时间不相容：（同阶段靠前同学的完成时间小于靠后同学的开始时间）第81页/共153页可将目标改为如下线性优化目标：第82页/共153页程序编写程序编写 model:title:面试问题;sets:student/
38、1.4/:;office/1.3/:;link1(student,office):x,t;link2(student,student)|&1#lt#&2:y;endsetsdata:t=13 15 20 10 20 18 20 16 10 8 10 15;Enddatamin=time;!time大于每名同学最后面试完毕时间;for(student(i):timex(i,3)+t(i,3););第83页/共153页!面试先后次序约束;for(student(i):for(office(j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1););!每个阶段只能面试一个同学,y(i,k)=
39、1表示第k名同学排在第i名同学前面;取M=1000；for(student(i):for(office(j):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);!满足需求满足需求约束约束;FOR(CUTS(J):SUM(NEEDS(I):LENGTH(I)*R(I,J)CAPACITY-MIN(NEEDS(I):LENGTH(I);!合理切割模式约束合理切割模式约束;SUM(CUTS
40、(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第94页/共153页结果结果模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。用去原料钢
41、管总根数为用去原料钢管总根数为28根。根。第95页/共153页课堂练习课堂练习5 下料问题下料问题 （2004全国研究生数学建模竞赛全国研究生数学建模竞赛B题）题）单一原材料的长度为单一原材料的长度为3000mm,需要完成一项有需要完成一项有53种不同种不同长度零件的下料任务长度零件的下料任务.具体数据见表一，在每个切割点处由于具体数据见表一，在每个切割点处由于锯缝所产生的损耗为锯缝所产生的损耗为5mm.据估计，该企业每天最大下料能据估计，该企业每天最大下料能力是力是100块块，要求在，要求在4天内完成的零件标号为天内完成的零件标号为:5,7,9,12,15,18,20,25,28,36,48
42、;要求不迟于要求不迟于6天完成的零件标号天完成的零件标号为为:4,11,24,29,32,38,40,46,50.第96页/共153页课堂练课堂练习习6料场的建立与运输料场的建立与运输建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，距离单位：公里表示，距离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个下表给出。有两个临时料场位于临时料场位于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多
43、大？料场应建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611第97页/共153页多目标规划多目标规划 第98页/共153页 线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规
44、划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。第99页/共153页例例10 重新考虑例重新考虑例6选址问题。选址问题。第100页/共153页 多目标决策问题有许多共同的特点，其中最显著的是：目标的多目标决策问题有许多共同的特点，其中最显著的是：目标的不
45、可公度性不可公度性，和，和目标间的目标间的矛盾性矛盾性。因此不能简单的把多个目标归并为单个目标，并使用单目标决策。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标问题。问题的方法去求解多目标问题。多目标问题的数学模型多目标问题的数学模型 第101页/共153页记可行域为记可行域为D.第102页/共153页多目标决策的本质问题是多目标决策的本质问题是：如何根据决策者的主观价值判断，对有效解的好坏做：如何根据决策者的主观价值判断，对有效解的好坏做出比较？由于可行域中的一个点，对应目标函数是一个向量，所以问题实际是：出比较？由于可行域中的一个点，对应目标函数是一个向量，
46、所以问题实际是：如何比较两个向量的大小？如何比较两个向量的大小？第103页/共153页第104页/共153页 多目标规划的常用解法多目标规划的常用解法 思想：转化为单目标问题思想：转化为单目标问题（1）线性加权法：）线性加权法：权数权数评价函数评价函数 单目标单目标:第105页/共153页（2）变权加权法：）变权加权法：（3）指数加权法：指数加权法：第106页/共153页（4）极小极大（）极小极大（min-max）法）法 第107页/共153页（5）理想点法理想点法 先求解单目标的最优值确定理想点：先求解单目标的最优值确定理想点：在找距离理想点最近的点作为最优解：在找距离理想点最近的点作为最优
47、解：第108页/共153页（6）加权偏差函数法）加权偏差函数法 第109页/共153页（7）费效比函数：）费效比函数：第110页/共153页（8）功效系数函数：）功效系数函数：对不同的性质的目标函数统一量纲，再构造效用函数：对不同的性质的目标函数统一量纲，再构造效用函数：比如构造功效系数函数：比如构造功效系数函数：然后求解规划问题：然后求解规划问题：还可以对功效系数函数进行加权构造效用函数，如还可以对功效系数函数进行加权构造效用函数，如第111页/共153页（9）参考目标法）参考目标法 约束法：约束法：在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在在多个目标中选定一个主要目标，而
48、对其他目标设定一个期望值，在要求结果不比期望值坏的情况下，求主要目标的最优值。要求结果不比期望值坏的情况下，求主要目标的最优值。分层序列法：分层序列法：把多个目标按照重要程度进行排序，先求第一个目标的最有解，把多个目标按照重要程度进行排序，先求第一个目标的最有解，在达到此目标的条件下求第二个目标的最优解，依次类推在达到此目标的条件下求第二个目标的最优解，依次类推 宽容分层序列法：宽容分层序列法：给前面的最优值设置一定的宽容值，和最优值相差宽容值之给前面的最优值设置一定的宽容值，和最优值相差宽容值之内的都是可以接受的。内的都是可以接受的。第112页/共153页（10）逼近理想解法逼近理想解法正负
49、理想解：正负理想解：计算距离，不妨取为欧式距离：计算距离，不妨取为欧式距离：计算测度：计算测度：求最大测度：求最大测度：第113页/共153页例例11 11 投资问题投资问题 某企业拟用某企业拟用1000万元投资于万元投资于A、B两个项目的技术改造两个项目的技术改造.设设、分别表示分别表示分配给分配给A、B项目的投资（万元）项目的投资（万元）.据估计，投资项目据估计，投资项目A、B的年收益分别为投资的年收益分别为投资的的60%和和70%；但投资风险损失，与总投资和单项投资均有关系：；但投资风险损失，与总投资和单项投资均有关系：据市场调查显示，据市场调查显示，A项目的投资前景好于项目的投资前景好
50、于B项目，因此希望项目，因此希望A项目的投资额项目的投资额不小不小B项目项目.试问应该如何在试问应该如何在A、B两个项目之间分配投资，才能既使年利润最大，两个项目之间分配投资，才能既使年利润最大，又使风险损失为最小？又使风险损失为最小？第114页/共153页 该该问问题题是是一一个个非非线线性性多多目目标标规规划划问问题题，将将它它用用数数学学语语言言描描述述出出来来，就就是是：求求 、，使：，使：而且满足：而且满足：第115页/共153页 对于上述多目标规划问题，如果决策者提出的期望目标是：对于上述多目标规划问题，如果决策者提出的期望目标是：（1 1）每一年的总收益不小于）每一年的总收益不小