数学规划建模

1、最优化问题的数学模型的一般形式为：,（1）,（2）,三个要素：决策变量decision bariable，目标函数objective function，约束条件constraints。,（2）所确定的x的范围称为可行域feasible region，满足（2）的解x称为可行解feasible solution，同时满足（1）（2）的解x称为最优解optimal solution，整个可行域上的最优解称为全局最优解global optimal solution，可行域中某个领域上的最优解称为局部最优解local optimal solution。最优解所对应的目标函数值称为最优值optimum。

2、,优化模型的分类,（一）按有无约束条件（2）可分为： 1.无约束优化unconstrained optimization。 2.约束优化constrained optimization。 大部分实际问题都是约束优化问题。,（二）按决策变量取值是否连续可分为： 1.数学规划或连续优化。 可继续划分为线性规划(lp)linear programming和非线性规划(nlp) nonlinear programming。在非线性规划中有一种规划叫做二次规划(qp)quadratic programming，目标为二次函数，约束为线性函数。 2.离散优化或组合优化。 包含：整数规划(ip)intege

3、r programming，整数规划中又包含很重要的一类规划：0-1（整数）规划zero-one programming，这类规划问题的决策变量只取0或者1。,（三）按目标的多少可分为： 1.单目标规划。 2.多目标规划。 （四）按模型中参数和变量是否具有不确定性可分为： 1.确定性规划。 2.不确定性规划。 （五）按问题求解的特性可分为： 1.目标规划。 2.动态规划。 3.多层规划。 4.网络优化。 5.等等。,优化问题求解常用的软件 lingo软件和matlab软件。 对于lingo软件，线性优化求解程序通常使用单纯形法simplex method，单纯形法虽然在实际应用中是最好最有效的

4、方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interior point method备选（lingo中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（lingo中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序分解原问题成一系列的凸规划。,软件介绍,例1 帆船生产计划 sailco公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的

5、生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元。假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？,分析: dem需求量， rp正常生产的产量， op加班生产的产量， inv库存量， 则dem,rp,op,inv对每个季度都应该有一个对应的值，也就说他们都应该是一个由4个元素组成的数组，其中dem是已知的，而rp,op,inv是未知数。,目标函数：正常生产费加班生产费储存费 最小,约束条件：,1）能力限制：,2）产品数量的平衡方程：,4）变量非负,3）初始库存：,引例 模型建立,记四个季度组成的集合quarters=1

6、，2，3，4，它们就是上面数组的下标集合，而数组dem,rp,op, inv对集合quarters中的每个元素1，2，3，4分别对应于一个值。lingo正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性”的概念，把quarters=1，2，3，4称为集合，把dem,rp,op, inv称为该集合的属性(即定义在该集合上的属性)。,集合与属性,集合与属性,集合元素及集合的属性确定的所有变量,集合与属性,程序编写,model: !集合段：定义集合set，元素member及其属性attribute； sets: quarters/1,2,3,4/:dem,rp,op,inv; endse

7、ts !目标与约束段：没有开始和结束标记，顺序无关； 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); !数据段：对集合的属性输入必要的常数数据； data: dem=40,60,75,25; enddata end,或1.4,或用空格或回车隔开，“属性常数列表”,对“：”前的每个元素求和或循环 遍历下标元素，

8、可省略下标,“”后是过滤条件，逻辑关 系式 i1（greater than）,展开式,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);,全局最优解 rp=(40,40,40,25) op=(0,10,35,0),最小成本=78450,自动生成行

9、号,结果报告,例2 运输问题,解：设a1,a2调运到三个粮站的大米分别为x11， x12， x13， x21， x22， x23吨。,题设量可总到下表：,结合存量限制和需量限制得数学模型：,程序编写 推荐 model: title 调运大米的运输问题程序; !定义集合段; sets: liangku/1.2/:a;!定义粮库的集合; liangzhan/1.3/:b;!定义粮站的集合; yuliang(liangku,liangzhan):x,c;!定义运量和距离; endsets data: !粮库到粮站的距离; c= 12 24 8 30 12 24;,!粮库的限量; a=4 8 ; !粮

10、站的限量; b=2 4 5; enddata objmin=sum(yuliang:c*x); !粮库上限的约束; for(liangku(i):lk sum(liangzhan(j):x(i,j)b(j); end,程序的调试 1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改； 2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围； 3.可以边写程序边运行，保证每行书写都是正确的程序；,料场的建立与运输 建筑工地的位置(用平面坐标a, b表示，距离单位：公里)及水泥日用量d(吨)下表给出。有两个临时料场位于p (5,1), q (2, 7),日储量各有20

11、吨。(1)从a, b两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。(2)两个新的料场应建在何处，节省的吨公里数有多大？,非线性规划引例,引例 模型建立,利用集合的概念，可以定义需求点demand和供应点supply两个集合，分别有6个和2个元素(下标)。但决策变量(运送量)cij与集合demand和集合supply都有关系的。该如何定义这样的属性？,集合的属性相当于以集合的元素为下标的数组。这里的cij相当于二维数组。它的两个下标分别来自集合demand和supply，因此可以定义一个由二元对组成的新的集合，然后将cij定义成这个新集合的属性，这个集合称为派生集合。,派生集合,程序编写

12、,model: title location problem; sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply):c; endsets data: !locations for the demand(需求点的位置); 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与

13、派生集合derived set（定义多维数组）,程序编写, !初始段：对集合属性定义初值（迭代算法的迭代初值）; init: !initial locations for the supply（初始点）; 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);); !suppl

14、y constraints（供应约束）; for(supply(i):supply_con sum(demand(j):c(j,i) =e(i); ); for(supply: bnd(0.5,x,8.75); bnd(0.75,y,7.75); ); end,lingo对数值顺序按列赋值，即：x=5,2;y=1,7;,标号自动在后加下标 *_1 , _2,比free(x);free(y);要好，可减少计算工作量,求解观察,激活全局最优解： lingooptionsglobal solveruse global solver,结果报告,工地与料场运输示意图 : “*”表示料场，“+”表示工地,

15、认识“初始段”, data: !(需求点的位置); a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; !（供需量）; d=3,5,4,7,6,11; e=20,20; enddata init: ! （初始点）; x,y=5,1,2,7; endinit , data: !(需求点的位置); a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; !（供需量）; d=3,5,4,7,6,11; e=20,20; x,y=5,1,2,7; enddata init: !

16、（初始点）; endinit ,求解nlp问题,求解lp问题,只对非线性模型起作用,知识重整,lingo建模语言也称为矩阵生成器（matrix generator）。类似demand 和supply直接把元素列举出来的集合，称为基本集合(primary set),而把link这种基于其它集合而派生出来的二维或多维集合称为派生集合(derived set)。由于是demand 和supply生成了派生集合link，所以demand 和supply 称为link的父集合。 表示集合link中的元素就是集合demand 和supply的元素组合成的有序二元组，从数学上看link是demand 和su

17、pply的笛卡儿积，也就是说 link=（s，t）|sdemand，tsupply 因此，其属性c也就是一个6*2的矩阵（或者说是含有12个元素的二维数组）。,模型构成,一般来说， lingo中建立的优化模型可以由五个部分组成，或称为五“段”（section）：,（1）集合段（sets）：以“ sets:” 开始， “endsets”结束，定义必要的集合变量（set）及其元素（member，含义类似于数组的下标）和属性（attribute，含义类似于数组）。,（2）目标与约束段：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段(都有明确的段标记)外的lingo模型。,（

18、3）数据段(data)：以 “data:” 开始, “enddata”结束， 对集合的属性(数组)输入必要的常数数据。 格式为：“attribute(属性) = value_list(常数列表);”,模型构成,(5) 计算段:在数据段输入完成之后在正式求解模型之前对 原始数据进行处理，语句是顺序执行的，不能更换顺序，只能 直接使用赋值语句，不能包含需要经过解方程或经过求解优化 问题以后才能决定的变量。,calc: t_dem=sum(quarters:dem);!总需求； a_dem=t_dem/size(quarters);!平均需求； endcalc,（4）初始段(init)：以“init

19、: ”开始， “endinit”结束， 对集合的属性(数组)定义初值(因为求解算法一般是迭代算法， 所以用户如果能给出一个比较好的迭代初值，对提高算法的计 算效果是有益的)。 格式为：“attribute（属性） = value_list（常数列表）；”,试一试,使用集合改写下面程序： min=-5*x1-2*x2； 2*x1+x2+x3=8； x1+x4=3； x2+x5=4;, 请动手试一下,model: title 露一小手; sets:!集合段; hang/1.3/:b; lie/1.5/:c,x; xishu(hang,lie):a; endsets data: a= 2 1 1 0

20、 0 1 0 0 1 0 0 1 0 0 1; c=-5 -2 0 0 0; b=8 3 4; enddata objmin=sum(lie:c*x); for(hang(i):yueshu sum(lie(j):a(i,j)*x(j)=b(i); end,sets: hang:b; endsets data: hang=1.3; enddata ,教你一招,线性规划,怎样建立优化模型与lingo软件的使用,线性规划模型的一般形式：,一般线性规划问题都可以通过引入非负的松弛变量slack variable与非负的剩余变量surplus v-ariable的方法化为标准形式（约束全是等约束）。,

21、线性规划问题的可行域feasible region是一个凸集convex set（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解optimal solution/point在凸多面体的某个顶点上达到,求解方法：单纯形算法simplex method。,连续性线性规划,1.比例性：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。 2.可加性：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。 3.连续性：每个决策变量的取值都是连续的。,线性规划问题的性质,例 3 阶段生产问题,某公司生产某产品,最大生产能力为10000单位,每单位 存储

22、费2元,预定的销售量与单位成本如下:,求一生产计划,使 1)满足需求; 2)不超过生产能力; 3)成本(生产成本与存储费之和)最低.,解:假定1月初无库存,4月底买完,当月生产的不库 存,库存量无限制.,第j+1个月的库存量,第j+1个月的库存费,共3个月的库存费,到本月总生产量大于等于销售量,4个月总生产量等于总销售量,4个月总生产成本,model: title 生产计划程序1; sets: yuefen/1.4/:c,x,e,d; endsets data: c=70 71 80 76; d=6000 7000 12000 6000; e=2 2 2 2 ; a=10000; enddat

23、a min=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,model: title 生产计划程序2; sets: yuefen/1.4/:c,x,e,d,s; endsets data: c=70 71 80 76; d=6000 7000 12000 60

24、00; e=2 2 2 2 ; a=10000; enddata min=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,model: title 生产计划程序3; sets: yuefen/1.4/:a,d,xx; !定义上三角矩阵; link(yuefen,yuefen)| end,model title: :生产计划程序1 variable value reduced cost a 10000.00 0.000000

25、 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.

26、000 0.000000 d( 2) 7000.000 0.000000 d( 3) 12000.00 0.000000 d( 4) 6000.000 0.000000,课堂练习1:转运问题,设有两个工厂a、b，产量都是10万个，工厂有三个仓库x，y，z，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。工厂到仓库、仓库到顾客的运费单价（元/个）见下表所示。试求总运费最少的运输方案以及总运费。,连续投资10万元,a：从第1年 到第4年每年初要投资，次年末回收本利1.15,b：第3年初投资，到第5年末回收1.25，最大投资4万元,c：第2年初投资，到第5年末回收

27、1.40，最大投资3万元,d：每年初投资，每年末回收1.11。,求：5年末总资本最大。,课堂练习2:连续投资,灵敏度分析与影子价格,例4 生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及a,b两种原材料的消耗，现有原材料和设备台时的定额如表所示，问： ）怎么安排生产使得工厂获利最大？ ）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？ ）产品的单位利润增大到5万元，要不要改变生产计划？ ）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？,程序编写 model: title 生产计划问题; maxfmax=2*x1+3

28、*x2; ax1+2*x28; b4*x116; time4*x212; end,运行结果 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

29、,目标函数的系数变化的敏感性分析,如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.,线性模型敏感性分析1,要使用敏感性分析 必须要在这里选择prices 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 slac

30、k or surplus dual prices 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 no. iterations= 2,20桶牛奶生产a1, 30桶生产a2，利润3360元。,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

31、3) 0.000000 2.000000 4) 40.000000 0.000000,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,ranges in which the basis is unchanged: obj coefficient ranges variable current allowable allowable coef increase decrease x1 72.000000 24.000000 8.000000 x2 64.000000 8.000000 16.000000 righthand side ran

32、ges row current allowable allowable rhs increase decrease 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 infinity 40.000000,a1获利增加到 30元/千克，应否改变生产计划？,不变！,35元可买到1桶牛奶，每天最多买多少？,最多买10桶！,整数规划,问题： 如何下料最节省 ?,例6 下料问题,按照客户需要在一根原料钢管上安排切割的一种组合。,合理切割模式的余料应小于客户需要钢管的最小尺寸,model: title

33、搜索合理的下料方式; sets: ren:; !用一根原料可下各需求长度的最多根数定义元素个数，最多为4，这里要定义5(04有5个数); long(ren,ren,ren):; !有三种需求长度，定义三维数组; endsets data: 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)=

34、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,种); en

35、ddata,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);!下料方式计数; endcalc end,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),决策变量,2. 所用原料钢管总根数最少,1. 原料钢管剩余总余量最小,目标函数：（两种标准）,约束,整数约束： xi 为整数,程序编写

36、,model: title 钢管下料; min=3*x1 + x2 + 3*x3 + 3*x4 + x5 + x6 + 3*x7; 4*x1 + 3*x2 + 2*x3 + x4 + x550; x2 + 2*x4 + x5 + 3*x6 20; x3 + x5 + 2*x715; gin(x1);gin(x2);gin(x3);gin(x4); gin(x5);gin(x6);gin(x7); end,程序编写,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12, x5=15, 其余为0； 最优值：27,最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：2

37、5。,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,当余料没有用处时，通常以总根数最少为目标,课堂练习3某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，现规定应聘者需连续工作5天，试确定聘用方案。,0-1规划,例7 选址问题,例8 面试顺序问题有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这4名同学约定他们全部面试完以后一起离开

38、公司，假定现在时间是早上8：00，请问他们最早何时能离开公司？,优化目标为：,约束条件：,个人时间先后次序约束：,同阶段不同同学时间不相容：（同阶段靠前同学的完成时间小于靠后同学的开始时间）,可将目标改为如下线性优化目标：,程序编写,model: title:面试问题; sets: student/1.4/:; office/1.3/:; link1(student,office):x,t; link2(student,student)|,!面试先后次序约束; for(student(i): for(office(j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1);); !每个阶段

39、只能面试一个同学,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)1000*(1-y(i,k); !定义0-1变量,最后通过0-1变量可以查看面试顺序; for(link2:bin(y); end,运行结果,model title: :面试问题 variab

40、le value reduced cost time 84.00000 0.000000 （省略） y( 1, 2) 0.000000 -1000.000 y( 1, 3) 0.000000 0.000000 y( 1, 4) 1.000000 1000.000 y( 2, 3) 0.000000 -1000.000 y( 2, 4) 1.000000 0.000000 y( 3, 4) 1.000000 0.000000,所以面试完成至少需要84min，面试顺序为4-1-2-3（丁-甲-乙-丙）,课堂练习4某班准备从5名游泳员中选择人组成接力队，藏家学校的4100m混合泳接力比赛，5名队员4

41、种泳姿的百米平均成绩如表，问如何选拔队员。,非线性规划,客户增加需求：,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,例9 续例5下料问题,对大规模问题，用模型的约束条件界定合理模式,现有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米长的钢管的数量,满足需求,目标函数（总根数）,约束条件,xi ,r1i, r2i, r3i, r4i (i

42、=1,2,3)为整数,模式合理： 每根余料不超过3米,整数约束：,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,特殊生产计划：对每根原料钢管 模式1：切割成4根4米钢管，需13根； 模式2：切割成1根5米和2根6米钢管，需10根； 模式3：切割成2根8米钢管，需8根。 原料钢管总根数上界：31,模式排列顺序可任定,上下界,model: title 钢管下料 - 最小化钢管根数的lingo模型; sets: needs/1.4/:length,num; cuts/1.3/:x; patterns(needs,cu

43、ts):r; endsets data: length=4 5 6 8; num=50 10 20 15; capacity=19; enddata,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+

44、1) );!人为增加约束; for(cuts(j): gin(x(j) ) ; for(patterns(i,j): gin(r(i,j) ); end,结果 模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根； 模式3：每根原料钢管切割成2根8米钢管，共8根。 原料钢管总根数为28根。 用去原料钢管总根数为28根。,课堂练习5 下料问题 （2004全国研究生数学建模竞赛b题）,单一原材料的长度为 3000mm, 需要完成一项有53种不同长度零件的下料任务. 具体数据见表一，在每个切割点处由于锯缝所产生的损耗为5m

45、m. 据估计，该企业每天最大下料能力是100块 ，要求在4天内完成的零件标号为: 5,7,9,12,15,18,20,25, 28,36,48; 要求不迟于6天完成的零件标号为:4,11,24,29,32,38,40,46,50.,课堂练习6 料场的建立与运输 建筑工地的位置(用平面坐标a, b表示，距离单位：公里)及水泥日用量d(吨)下表给出。有两个临时料场位于p (5,1), q (2, 7),日储量各有20吨。从a, b两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？,多目标规划,线性规划致力于某个目标函数的最优解，这个最优解若是超过了

46、实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。 求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。,例10 重新考虑例6选址问题。,多目标决策问题有许多共同的特点，其中最显著的是：目标的不可公度性，和目标间的矛盾性。因此不能简单的把多个目标归并为单个目标，并使用单目标决策问题的方法去求解多目标问题。,多目标问题的数学模型,记可行域为d.,多目标决策的本质问

47、题是：如何根据决策者的主观价值判断，对有效解的好坏做出比较？由于可行域中的一个点，对应目标函数是一个向量，所以问题实际是：如何比较两个向量的大小？,多目标规划的常用解法,思想：转化为单目标问题,（1）线性加权法：,权数,评价函数,单目标:,（2）变权加权法：,（3）指数加权法：,（4）极小极大（min-max）法,（5）理想点法,先求解单目标的最优值确定理想点：,在找距离理想点最近的点作为最优解：,（6）加权偏差函数法,（7）费效比函数：,（8）功效系数函数：,对不同的性质的目标函数统一量纲，再构造效用函数：,比如构造功效系数函数：,然后求解规划问题：,还可以对功效系数函数进行加权构造效用函数

48、，如,（9）参考目标法,约束法：在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比期望值坏的情况下，求主要目标的最优值。,分层序列法：把多个目标按照重要程度进行排序，先求第一个目标的最有解，在达到此目标的条件下求第二个目标的最优解，依次类推,宽容分层序列法：给前面的最优值设置一定的宽容值，和最优值相差宽容值之内的都是可以接受的。,（10）逼近理想解法,正负理想解：,计算距离，不妨取为欧式距离：,计算测度：,求最大测度：,例11 投资问题,某企业拟用1000万元投资于a、b两个项目的技术改造. 设 、 分别表示分配给a、b项目的投资（万元）. 据估计，投资项目a、b的年收益

49、分别为投资的60%和70%；但投资风险损失，与总投资和单项投资均有关系： 据市场调查显示， a 项目的投资前景好于 b 项目，因此希望a项目的投资额不小b项目. 试问应该如何在a、b两个项目之间分配投资，才能既使年利润最大，又使风险损失为最小？,该问题是一个非线性多目标规划问题，将它用数学语言描述出来，就是：求 、 ，使：,而且满足：,对于上述多目标规划问题，如果决策者提出的期望目标是： （1）每一年的总收益不小于600万元； （2）希望投资风险损失不超过800万元； （3）两个目标同等重要. 可以得到一个非劣解方案为：,646.3139万元， 304.1477万元 此方案的投资风险损失为 7

50、99.3082 万元，每一年的总收益为600.6918万元.,课堂练习7 2007全国大学生数学建模竞赛 b题 乘公交，看奥运,第29届奥运会明年8月将在北京举行，大部分人将会乘坐公共交通工具到现场观看奥运比赛，这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线 (1)、s3359s1828 (2)、s1557s0481 。 2、同时考虑公

51、汽与地铁线路，解决以上问题。 练习：请给出模型的目标,课堂练习8 投资组合问题 某三支股票在12年的价格如下：,解决如下问题： （1）如果在1955年你有一笔资金投资这三种股票，并期望年收益率至少达到15%，那么你应当如何投资？分析投资组合与回报率以及风险的关系。 （2）如果还可以投资国库券，年收益率为5%，如果投资呢？ （3）如果幂目前持有的股票比例为：a占50%，b占35%，c占15%，买卖股票按交易额的1%收取交易费，你会怎么办？ （4） 在希望风险小而获利大前提下考虑以上问题。,目标规划模型,线性规划与目标规划,线性规划通常考虑一个目标函数(问题简单),目标规划考虑多个目标函数(问题复

52、杂),线性规划,目标规划,某企业生产甲、乙两种产品，需要用到a,b,c三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。,例12 生产安排问题,问该企业应如何安排生产，使得在计划期内总利润最大？,该例11是一个线性规划问题，直接考虑它的线性规划模型,设甲、乙产品的产量分别为x1, x2,建立线性规划模型：,用lingo软件求解,得到最优解,在上例8.1中，企业的经营目标不仅要考虑利润，还需要考虑多个方面，因此增加下列因素(目标)：,力求使利润指标不低于1500元,考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2,设备a为贵重设备，严格禁止超时使用,设备c可以适当加班，但要控制；设

53、备b既要求充分利用，又尽可能不加班，在重要性上，设备b是设备c的3倍,从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解,某汽车销售公司委托一个广告公司在电视上为其做广告，汽车销售公司提出三个目标：,例13 汽车广告费问题,广告公司必须决定购买两种类型的电视广告展播各多少分钟？,第一个目标，至少有40万高收入的男性公民(记为him)看到这个广告,第二个目标，至少有60万一般收入的公民(记为lip)看到这个广告,第三个目标，至少有35万高收入的女性公民(记为hiw)看到这个广告,广告公司可以从电视台购买两种类型的广告展播：足球赛中插播广告和电视系列剧插播广告。广告

54、公司最多花费60万元的电视广告费。每一类广告展播每一分钟的花费及潜在的观众人数如下表所示,对于例12考虑建立线性规划模型,设x1, x2分别是足球赛和电视系列剧中插播的分钟数，按照要求，可以列出相应的线性规划模型,用lingo软件求解,会发现该问题不可行。,线性规划建模局限性,线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；,线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；,线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标

55、的重要性即有层次上的差别，也有在同一层次上不同权重的差别,线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。,目标规划的数学模型,为了克服线性规划的局限性,目标规划采用如下手段：,1. 设置偏差变量; 2. 统一处理目标与约束; 3. 目标的优先级与权系数。,目标规划的基本概念,1. 设置偏差变量,用偏差变量(deviational variables)来表示实际值与目标值 之间的差异，令 - 超出目标的差值，称为正偏差变量 - 未达到目标的差值，称为负偏差变量 其中 与 至少有一个为0,约定如下： 当实际值超过目标值时，有 当实际值未达到目标值时，有 当实际值与目标值一致时，有,2

56、. 统一处理目标与约束,在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束(hard constraint)；例如在用目标规划 求解例8.1中设备a禁止超时使用，则有刚性约束,另一类是可以不严格限制的，连同原线性规划的目标,构 成柔性约束(soft constraint).例如在求解例8.1中，我们 希望利润不低于1500元，则目标可表示为,求解例8.1中甲、乙两种产品 的产量尽量保持1:2的比例， 则目标可表示为,设备c可以适当加班，但要控制， 则目标可表示为,设备b既要求充分利用，又尽可能 不加班，则目标可表示为,从上面的分析可以看到： 如果希望不等式保持大于等于，则极小

57、化负偏差； 如果希望不等式保持小于等于，则极小化正偏差； 如果希望保持等式，则同时极小化正、负偏差,3.目标的优先级与权系数,在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以p1,p2,.表示不同的因子,并规定pkpk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。,解在例.1中设备a是刚性约束，其于是柔性约束首先，最重要的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备 b和c的工作时间要有所控制，列为第三级，设备b的重要性是设备c的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。,用目标规划方法求解例1 1,目标规划的一般模型,求解目标规划的序贯式算法,根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题对于k=1,2,q,求解单目标问题,求解例8. 3的lingo程序,程序运行说明，分三次求解： 在做第一级目标计算时，p(1),p(2)和p(3)分别输入1,0和0，goal(1)和goal(2)输入两个较大的数，表示这两项约束不起作用； 在做第二级目标计算时，p(1),p(2)和