数学规划建模

1、数数 学学 建建 模模华中农业大学数学建模基地系列课件华中农业大学数学建模基地系列课件编辑课件1编辑课件2最优化问题的最优化问题的数学模型的一般形式数学模型的一般形式为：为： xfzopt skjiRDxnkxtmjxglixhts , 1, 0 , 1, 0 , 1, 0 .（1）（2）三个要素：决策变量三个要素：决策变量decision bariable，目标函数，目标函数objective function，约束条件，约束条件constraints。 编辑课件3 （2）所确定的）所确定的x的范围称为的范围称为可行域可行域feasible region，满足（，满足（2）的解）的解x称为称

2、为可行解可行解feasible solution，同时满足（同时满足（1）（）（2）的解）的解x称为称为最优解最优解Optimal solution，整个可行域上的最优解称为，整个可行域上的最优解称为全局最优解全局最优解global optimal solution，可行域中某个领域上的最，可行域中某个领域上的最优解称为优解称为局部最优解局部最优解local optimal solution。最优解。最优解所对应的目标函数值称为所对应的目标函数值称为最优值最优值optimum。 编辑课件4优化模型的分类优化模型的分类 （一）按有无约束条件（一）按有无约束条件（2）可分为：）可分为：1.无约束优

3、化无约束优化unconstrained optimization。2.约束优化约束优化constrained optimization。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。 编辑课件5（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可分为：1.数学规划或连续优化数学规划或连续优化。可继续划分为可继续划分为线性规划线性规划(LP)Linear programming和和非线性规划非线性规划(NLP) Nonlinear programming。在。在非线性规划中有一种规划叫做非线性规划中有一种规划叫做二次规划二次规划(QP)Quadratic prog

4、ramming，目标为二次函数，目标为二次函数，约束为线性函数。约束为线性函数。2.离散优化或组合优化离散优化或组合优化。包含：包含：整数规划整数规划(IP)Integer programming，整数，整数规划中又包含很重要的一类规划：规划中又包含很重要的一类规划：0-1（整数）规划（整数）规划Zero-one programming，这类规划问题的决策变，这类规划问题的决策变量只取量只取0或者或者1。编辑课件6（三）（三）按目标的多少按目标的多少可分为：可分为：1.单目标规划。单目标规划。2.多目标规划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不

5、确定性可分为：可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）（五）按问题求解的特性按问题求解的特性可分为：可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。编辑课件7优化问题求解常用的软件优化问题求解常用的软件 LINGO软件和软件和MATLAB软件。软件。 对于对于LINGO软件，线性优化求解程序通常使用软件，线性优化求解程序通常使用单单纯形法纯形法simplex method，单纯形法虽然在实际应用中是，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，最好最有效的方

6、法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了为了能解大规模问题，也提供了内点算法内点算法interior point method备选（备选（LINGO中一般称为障碍法，即中一般称为障碍法，即barrier），），非线性优化求解程序采用的是非线性优化求解程序采用的是顺序线性规划法顺序线性规划法，也可用，也可用顺序二次规划法顺序二次规划法，广义既约梯度法，另外可以使用多初，广义既约梯度法，另外可以使用多初始点（始点（LINGO中称中称multistart）找多个局部最优解增加）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序找全局最优解的可能，还具有全局求解程序分解

7、原问分解原问题成一系列的题成一系列的凸规划凸规划。编辑课件8软件介绍软件介绍 例例1 帆船生产计划帆船生产计划 SAILCO公司需要决定下四个季度的帆船生公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是产量。下四个季度的帆船需求量分别是40条，条，60条，条，75条，条，25条，条，这些需求必须按时满足。每个季度正常的生产能力是这些需求必须按时满足。每个季度正常的生产能力是40条帆船，条帆船，每条船的生产费用为每条船的生产费用为400美元。如果加班生产，每条船的生产费美元。如果加班生产，每条船的生产费用为用为450美元。每个季度末，每条船的库存费用为美元。每个季度末，每条船的库

8、存费用为20美元。假定美元。假定生产提前期为生产提前期为0，初始库存为，初始库存为10条船。如何安排生产可使总费用条船。如何安排生产可使总费用最小？最小？ 分析分析: DEM需求量，需求量， RP正常生产的产量，正常生产的产量， OP加班生产的产量，加班生产的产量， INV库存量，库存量， 则则DEM,RP,OP,INV对每个季度都应该有一个对应的值，也对每个季度都应该有一个对应的值，也就说他们都应该是一个由就说他们都应该是一个由4个元素组成的个元素组成的数组数组，其中，其中DEM是已是已知的，而知的，而RP,OP,INV是未知数。是未知数。 编辑课件9目标函数：正常生产费加班生产费储存费目标

9、函数：正常生产费加班生产费储存费 最小最小4, 3 , 2, 1)(20)(450)(400MINIIINVIOPIRP 约束条件：约束条件：1）能力限制：）能力限制：4 , 3 , 2 , 1,40)(RPII2）产品数量的平衡方程：）产品数量的平衡方程：4 , 3 , 2 , 1),()()() 1()(IIDEMIOPIRPIINVIINV10)0(INV4）变量非负）变量非负3）初始库存：）初始库存： 引例 模型建立编辑课件10 记四个季度组成的集合QUARTERS=1，2，3，4，它们就是上面数组的下标集合，而数组DEM,RP,OP, INV对集合QUARTERS中的每个元素1，2，

10、3，4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性”的概念，把QUARTERS=1，2，3，4称为集合，把DEM,RP,OP, INV称为该集合的属性(即定义在该集合上的属性)。 集合与属性编辑课件11 QUARTERS集合的属性DEM RPOP INV QUARTERS集合2341 集合与属性编辑课件12集合元素及集合的属性确定的所有集合元素及集合的属性确定的所有变量变量集合QUARTERS的元素1234定义在集合QUARTERS上的属性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1

11、)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4) 集合与属性编辑课件13 程序编写 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（greater than）编辑课

12、件14 展开式LINGOGenerateDisply Model(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);编辑课件15全局最优解全局最优解RP=(40,40,40,25)OP=(0,10,35,0) 最小成本最小成本=78450 自动生成行号自动生成行号 结果报告编辑课件16例例2 2 运

13、输问题运输问题。问问如如何何调调运运使使运运费费最最低低如如下下公公里里单单位位距距离离两两个个粮粮库库到到三三个个粮粮站站的的吨吨大大米米分分别别为为三三个个粮粮站站至至少少需需要要吨吨吨吨为为两两个个粮粮库库现现存存大大米米分分别别调调运运大大米米向向三三个个粮粮站站有有两两个个粮粮库库,):(,5 , 4 , 2,8 ,4, 32121BBBAA编辑课件17解：设解：设A1,A2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x11，x12， x13， x21， x22， x23吨。吨。题设量可总到下表：题设量可总到下表：84库库存存量量x23x22x21A2542需要量需要量x13

14、x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824编辑课件18结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：23222113121124123082412xxxxxxf min 054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,.编辑课件19程序编写程序编写 推荐推荐MODEL:TITLE 调运大米的运输问题程序调运大米的运输问题程序;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库的集合;LIANGZHAN/1.3/:B;

15、!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!粮库到粮站的距离粮库到粮站的距离;C= 12 24 8 30 12 24;编辑课件20!粮库的限量粮库的限量;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 编辑课件21程序的调试程序的调试1.直接点击运行，如果出错会弹出错误提示，根直接点击运行，

16、如果出错会弹出错误提示，根据提示做相应的修改；据提示做相应的修改；2.可以用可以用“！”把约束变成说明语句，而把这条把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确可以边写程序边运行，保证每行书写都是正确的程序；的程序；编辑课件22 料场的建立与运输料场的建立与运输 建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a, b表示，距表示，距离单位：公里离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时料场位下表给出。有两个临时料场位于于P (5,1), Q (2, 7),日储量各有日储量各

17、有20吨。吨。(1)从从A, B两料场分别向各工两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。地运送多少吨水泥，使总的吨公里数最小。(2)两个新的料场应两个新的料场应建在何处，节省的吨公里数有多大？建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611 非线性规划引例非线性规划引例编辑课件23 2622112161MIN1s.t.,1,2,62,1,23ijjijijiijijijjifcxayacdicejb),(iiba已知为LP模型，未知为NLP模型 引例 模型建立料场向工地的运送量为：料场向工地的运送

18、量为：),(iiba6, 1,idi),(jjyx2 , 1,jejijc工地：位置工地：位置水泥日用量：水泥日用量：料场：位置料场：位置日储量：日储量：编辑课件24 利用集合的概念，可以定义需求点利用集合的概念，可以定义需求点DEMAND和供应点和供应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。但决策变量。但决策变量(运送量运送量)cij与集合与集合DEMAND和集合和集合SUPPLY都有关系的。该如都有关系的。该如何定义这样的属性？何定义这样的属性？ 集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的ci

19、j相当于二维数组。它的两个下标分别来自集合相当于二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY，因此可以定义一个由二元对组成的新的集合，然后，因此可以定义一个由二元对组成的新的集合，然后将将cij定义成这个新集合的属性，这个集合称为定义成这个新集合的属性，这个集合称为派生集合派生集合。 派生集合编辑课件25 程序编写MODEL:Title Location Problem;sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply):c;endsetsdata:!locations for the demand(

20、需求点的位置需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;!quantities of the demand and supply（供需量）（供需量）;d=3,5,4,7,6,11; e=20,20;enddata基本集合基本集合primary set与与派生集合派生集合derived set（定义多维数组）（定义多维数组）编辑课件26 程序编写!初始段：对集合属性定义初值（迭代算法的迭代初值）初始段：对集合属性定义初值（迭代算法的迭代初值）;init:!initial locations for the sup

21、ply（初始点）（初始点）;x,y=5,1,2,7;endinit!Objective function（目标）（目标）;OBJ min=sum(link(i,j): c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2) );!demand constraints（需求约束）（需求约束）;for(demand(i):DEMAND_CON sum(supply(j):c(i,j) =d(i););!supply constraints（供应约束）（供应约束）;for(supply(i):SUPPLY_CON sum(demand(j):c(j,i) sum(yuefen(i)

22、|i#le#j:d);sum(yuefen:x)= sum(yuefen:d);for(yuefen:xa);end 编辑课件41.iiiiisicedix月月初初的的库库存存量量为为为为单单位位成成本本，设设第第为为存存储储费费，为为销销售售量量，月月产产量量，为为第第：设设模模型型 4141miniiiiiisexcf.ts 1is, iiidxs 4 , 3 , 2 , 1 i0051 ss432104321100000， isixii编辑课件42Model:Title 生产计划程序生产计划程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 7

23、1 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编辑课件43.,月月的的销销售售量量第第表表示示的的费费之之和和出出时时的的生生产产成成本本与与存存储储月月卖卖月月生生产产的的产产品品在在第第表表示示第第数数量量月月卖卖出出的的月月生生产产的的产产品品在在第第表表示示第第设设化化为为运运输输问问题题解解法法jdji

24、cjixjijij 月月份份单位成本单位成本(元元) 销售量销售量1234 70 6000 72 7000 80 12000 76 6000编辑课件4476827676-80-7472-747270生产月10000100001000010000产量600041200070006000销量4321321需求月费用cij编辑课件45且且为为整整数数010000.min41,411 ijijijjijijjjiijijxxdxtsxcf编辑课件46model:title 生产计划程序3;sets:yuefen/1.4/:a,d,xx;!定义上三角矩阵;link(yuefen,yuefen)|&

25、;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):x(i,j);End编辑课件47Model Title: :生产计划程序生产计划程序1 Variable Value Reduced Cost A 1

26、0000.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.00

27、0000 D( 1) 6000.000 0.000000 D( 2) 7000.000 0.000000 D( 3) 12000.00 0.000000 D( 4) 6000.000 0.000000 编辑课件48课堂练习课堂练习1:1:转运问题转运问题 设有两个工厂设有两个工厂A、B，产量都是，产量都是10万个，工厂有三万个，工厂有三个仓库个仓库x，y，z，产品都先送到仓库。现有四个顾客分，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。万个。工厂到仓库、仓库到顾客的运费单价（元工厂到仓库、仓库到顾客的运费单价（元/个）见下

28、表个）见下表所示。试求总运费最少的运输方案以及总运费。所示。试求总运费最少的运输方案以及总运费。 AB甲甲乙乙丙丙丁丁x43571020y2196715z5220674编辑课件49连续投资连续投资10万元万元A：从第：从第1年年 到第到第4年每年初要投资，次年末回收年每年初要投资，次年末回收本利本利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万元万元C：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。年末总资本最大。课堂

29、练习课堂练习2:2:连续投资连续投资编辑课件50灵敏度分析与影子价格灵敏度分析与影子价格编辑课件51 例例4 生产计划问题生产计划问题某工厂计划安排生产某工厂计划安排生产，两种产品，已知每两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到的单位利润降低到1.8万元，要不要改变生产计划，如果万元，要不要改变生产计划，如果降低到降低到

30、1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万元，要不要改变生产计划？万元，要不要改变生产计划？）如果产品）如果产品，的单位利润同时降低了的单位利润同时降低了1万元，要不要改变生产万元，要不要改变生产计划？计划？ 产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23编辑课件52编辑课件53程序编写程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END编辑课件54运行结果运行结果 Model Title: 生产计划问题 Variable Value

31、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万元 。编辑课件55 线性模型敏感性理论1目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1

32、/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变. 编辑课件56 线性模型敏感性分析1要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices & Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)选项卡选项卡编辑课件57要调出敏感性分析的结果，要调出敏感性分析的结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange， 编辑课件58Ranges in which the basis is unchanged

33、: 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

34、.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，在（万元，在（1.5，）之间，所以不）之间，所以不改变生产计划。如果降低到改变生产计划。如果降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。在）内，要改变生产计划。在程序中将目标函数的系数程序中将目标函数的系数“2”改为改为“1”，可得新的计划为，可得新的计划为安排是生产产品安排是生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划

35、，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大利润降低到8万元万元. 编辑课件59编辑课件6012121112max2328416. .412,0fxxxxxstxx x0,34224.12168min3213221321yyyyyyytsyyyg把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润. 在最优情

36、况下，在最优情况下，y的值就是资的值就是资源的源的影子价格，影子价格，影子价格有意影子价格有意义是有范围的义是有范围的。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量加一个单位所带来总收益的增加量 编辑课件61Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decr

37、ease 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

38、 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 编辑课件621桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶

39、，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？ 每天：每天：例例5 加工奶制品的生产计划加工奶制品的生产计划编辑课件63x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束

40、0,21xx线性线性规划规划模型模型(LP)编辑课件64Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 22

41、0桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 编辑课件65 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 50; x2 + 2*x4 +

42、x5 + 3*x6 20; x3 + x5 + 2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end程序编写程序编写编辑课件76按模式按模式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米米

43、当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 编辑课件77 课堂练习课堂练习3某服务部门一周中每天需要不同数某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要目的雇员，周一到周四每天至少需要50人，周五至人，周五至少需要少需要80人，周六和周日至少需要人，周六和周日至少需要90人，现规定应人，现规定应聘者需连续工作聘者需连续工作5天，试确定聘用方案。天，试确定聘用方案。编辑课件780-1规划规划编辑课件79?,1,2:),(),(),(),(),(),(),(:7, 7654321的的年年利利润润最最大大问问如如何何选选择择地地址址使使公公司司元

44、元总总投投资资不不超超过过元元每每年年可可获获利利元元投投资资若若选选个个汉汉口口汉汉阳阳至至少少个个武武昌昌至至多多并并规规定定汉汉商商二二十十一一世世纪纪行行街街步步武武广广司司门门口口亚亚贸贸中中商商个个地地址址有有拟拟议议中中汉汉阳阳建建立立专专卖卖店店汉汉口口某某公公司司拟拟定定在在在在武武昌昌bcbAAAAAAAAiii例例7 选址问题选址问题编辑课件80 否否则则选选择择解解, 0, 1:iiAx 71maxiiixcf 7,.,2 , 110112.765432171ixxxxxxxxbxbtsiiii或或编辑课件81 例例8 面试顺序问题面试顺序问题有有4名同学到一家公司参加

45、三个名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于许插队，由于4名同学的专业背景不同，所以每人在三个阶段名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这的面试时间也不同，如表所示，这4名同学约定他们全部面试名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上完以后一起离开公司，假定现在时间是早上8：00，请问他们，请问他们最早何时能离开公司？最早何时能离开公司？ 秘

46、书初试秘书初试主管复试主管复试经理面试经理面试同学甲同学甲131520同学乙同学乙102018同学丙同学丙201610同学丁同学丁81015编辑课件82编辑课件83优化目标为： 33minmaxiiiTxt约束条件： 个人时间先后次序约束： .1,1,2,3,4;1,2.ijiji jxtxij同阶段不同同学时间不相容：（同阶段靠前同学的完成时间小于靠后同学的开始时间） ,ijijkjikxtxMy1,kjkjijikxtxMy01ikyor编辑课件84可将目标改为如下线性优化目标： 1313232333334343min. .,.TstTxtTxtTxtTxt编辑课件85程序编写程序编写 m

47、odel:title:面试问题;sets:student/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););编辑课件86!面试先后次序约束;for(student(i): for(office(j)|j#lt#3:x(i,j)+t(i

48、,j)x(i,j+1););!每个阶段只能面试一个同学,y(i,k)=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-

49、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编辑课件97结果结果 模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，米钢管，共共10根；根； 模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根； 模式

50、模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。 用去原料钢管总根数为用去原料钢管总根数为28根。根。 编辑课件98课堂练习课堂练习5 下料问题下料问题 （2004全国研究生数学建模竞赛全国研究生数学建模竞赛B题）题） 单一原材料的长度为单一原材料的长度为 3000mm, 需要完成一项有需要完成一项有53种不同种不同长度零件的下料任务长度零件的下料任务. 具体数据见表一，在每个切割点处由于具体数据见表一，在每个切割点处由于锯缝所产生的损耗为锯缝所产生的损耗为5mm. 据估计，该企业每天最大下料能据估计，该企业每天最

51、大下料能力是力是100块块 ，要求在，要求在4天内完成的零件标号为天内完成的零件标号为: 5,7,9,12,15,18,20,25, 28,36,48; 要求不迟于要求不迟于6天完成的零件标号天完成的零件标号为为:4,11,24,29,32,38,40,46,50. 编辑课件99 课堂练课堂练习习6 料场的建立与运输料场的建立与运输 建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a, b表示，距离单位：公里表示，距离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个下表给出。有两个临时料场位于临时料场位于P (5,1), Q (2, 7),日储量各有日储量各有20吨。从吨。从A

52、, B两料场分两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？料场应建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611编辑课件100多目标规划多目标规划 编辑课件101 线性规划致力于某个目标函数的最优解，这个最线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个了约束条件中的某些资

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

54、问题。选址问题。 71maxiiifc x71miniiixbg7112345672. .11011,2,.,7iiiib xbxxxstxxxxxi或编辑课件103 多目标决策问题有许多共同的特点，其中最显著多目标决策问题有许多共同的特点，其中最显著的是：目标的的是：目标的不可公度性不可公度性，和目标间的，和目标间的矛盾性矛盾性。因此。因此不能简单的把多个目标归并为单个目标，并使用单目不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标问题。标决策问题的方法去求解多目标问题。 多目标问题的数学模型多目标问题的数学模型 xfxfxfxfpRxn,min21 lkxhmjx

55、gtskj, 2 , 1, 0)(,. 2 , 1, 0)(.编辑课件104记可行域为记可行域为D. 编辑课件105多目标决策的本质问题是多目标决策的本质问题是：如何根据决策者的主观价：如何根据决策者的主观价值判断，对有效解的好坏做出比较？由于可行域中的值判断，对有效解的好坏做出比较？由于可行域中的一个点，对应目标函数是一个向量，所以问题实际是：一个点，对应目标函数是一个向量，所以问题实际是：如何比较两个向量的大小？如何比较两个向量的大小？ 编辑课件106编辑课件107 多目标规划的常用解法多目标规划的常用解法 思想：转化为单目标问题思想：转化为单目标问题（1）线性加权法：）线性加权法： p,

56、211, 01piii权数权数评价函数评价函数 piiixfxfu1 xfuDxmin单目标单目标:编辑课件108（2）变权加权法：）变权加权法： piiiiDxDxxfxfxfu1minmin（3）指数加权法：指数加权法： piiDxDxixfxfu1minmin编辑课件109（4）极小极大（）极小极大（min-max）法）法 xfxfuipiDxDx1maxminmin编辑课件110（5）理想点法理想点法 先求解单目标的最优值确定理想点：先求解单目标的最优值确定理想点： pixffiDxi1,min*在找距离理想点最近的点作为最优解：在找距离理想点最近的点作为最优解： piiiDxDxfx

57、fxfu12*minmin编辑课件111（6）加权偏差函数法）加权偏差函数法 编辑课件112（7）费效比函数：）费效比函数： pkiikiiDxDxxfxfxfu11minmin编辑课件113（8）功效系数函数：）功效系数函数： pixffiDxi1,minmin, pixffiDxi1,maxmax, 1 , 0min,max,max,iiiiiffxffxd 或或 piiDxxd1 max piiDxxd1max piiipiiixfdxu111 对不同的性质的目标函数统一量纲，再构造效用函数：对不同的性质的目标函数统一量纲，再构造效用函数：比如构造功效系数函数：比如构造功效系数函数：然后

58、求解规划问题：然后求解规划问题：还可以对功效系数函数进行加权构造效用函数，如还可以对功效系数函数进行加权构造效用函数，如编辑课件114（9）参考目标法）参考目标法 约束法：约束法：在多个目标中选定一个主要目标，而对其在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比期望值坏他目标设定一个期望值，在要求结果不比期望值坏的情况下，求主要目标的最优值。的情况下，求主要目标的最优值。 分层序列法：分层序列法：把多个目标按照重要程度进行排序，把多个目标按照重要程度进行排序，先求第一个目标的最有解，在达到此目标的条件下先求第一个目标的最有解，在达到此目标的条件下求第二个目标的最优解，

59、依次类推求第二个目标的最优解，依次类推 宽容分层序列法：宽容分层序列法：给前面的最优值设置一定的宽容给前面的最优值设置一定的宽容值，和最优值相差宽容值之内的都是可以接受的。值，和最优值相差宽容值之内的都是可以接受的。 编辑课件115（10）逼近理想解法逼近理想解法正负理想解：正负理想解： xffiDxi min xffiDxi max计算距离，不妨取为欧式距离：计算距离，不妨取为欧式距离： 2112piiixffxd 2112piiifxfxd计算测度：计算测度： xdxdxdxc求最大测度：求最大测度： xcDxmax编辑课件116例例11 11 投资问题投资问题 某企业拟用某企业拟用100

60、0万元投资于万元投资于A、B两个项目的技两个项目的技术改造术改造. 设设 、 分别表示分配给分别表示分配给A、B项目的投资项目的投资（万元）（万元）. 据估计，投资项目据估计，投资项目A、B的年收益分别为的年收益分别为投资的投资的60%和和70%；但投资风险损失，与总投资和；但投资风险损失，与总投资和单项投资均有关系：单项投资均有关系： 据市场调查显示，据市场调查显示， A 项目的投资前景好于项目的投资前景好于 B 项项目，因此希望目，因此希望A项目的投资额不小项目的投资额不小B项目项目. 试问应该试问应该如何在如何在A、B两个项目之间分配投资，才能既使年利两个项目之间分配投资，才能既使年利润最大，又使风险损失为最小？润最大，又