《【大学课件】数学建模 优化模型介绍p134》由会员分享，可在线阅读，更多相关《【大学课件】数学建模 优化模型介绍p134（134页珍藏版）》请在金锄头文库上搜索。
1、数学建模数学建模优化模型介绍http:/ - Francis Bacon 数学处于人类智能的中心领域数学处于人类智能的中心领域数学方数学方法渗透、支配着一切自然科学的理论分支法渗透、支配着一切自然科学的理论分支它已愈来愈成为衡量成就的主要标志。它已愈来愈成为衡量成就的主要标志。 - von Neumann http:/ 一门科学只有当它达到能够成功地运用一门科学只有当它达到能够成功地运用 数学时，才算真正发展了。数学时，才算真正发展了。 - - Karl MarxGalileo : : 展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在黑暗的迷宫里游荡，什么也认识不清
2、。数学是一种语言，是一切科学的共同语言数学是一种语言，是一切科学的共同语言http:/ 成的一种关键性的、可实现的技术二十世纪最伟大的数学家-二十世纪最伟大的物理学家-D.HilbertA.EinsteinGo back诺贝尔诺贝尔奖奖菲尔兹奖菲尔兹奖http:/ 数学建模数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解决实际问题，就一定要用数学的语言、方法去近似地刻画该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎
3、添翼似的得到了飞速的发展，掀起一个高潮数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一.http:/ 规划模型的应用极其广泛，其作用已为越来规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为行为 科学研究的各个方面，为社会节省的财富、科学研究的各个方面，为社会节省的财富、创造的价值无法估量创造的价值无法估量. 特别是在数模竞赛过程中，规划模型是最常特别是在数模竞赛过程中，规划模型是最常见的一类数学模型见的一类数学模型. 从从92-06年全国大学生数模竞年全
4、国大学生数模竞越多的人所重视越多的人所重视. 随着计算机的逐渐普及，它越随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出赛试题的解题方法统计结果来看，规划模型共出现了现了15次，占到了次，占到了50%，也就是说每两道竞赛题，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解. http:/ min f(x) -目标函数目标函数 s.t. s.t. x S -约束集合，可行集约束集合，可行集其中，其中，S R Rn n，f : :S R R，x S称（称（f S ) )的可行解的可行解n最优解最优解: : x* S，满足满足f
5、 (x*) f (x), x S。则称则称 x*为为( (f S) )的全局最优解的全局最优解( (最优解最优解),), 记记 g.opt.( (global optimum),),简记简记 opt.n最优值最优值: : x*为为( (f S) )的最优解的最优解, , 则称则称 f * = f (x*) 为为 ( (f S) )的最优值的最优值( (最优目标函数值最优目标函数值) )数学规划模型的一般形式数学规划模型的一般形式(f S)http:/ : x* S， x* 的邻域的邻域 N(x*) ，使满足，使满足 f (x*) f (x), x S N(x*) 。则称则称 x*为为( (f
6、S) )的局部最的局部最优解优解, ,记记 l .opt.( (local optimum) )n在上述定义中，当在上述定义中，当x x* 时有严格不等式成立，时有严格不等式成立，则分别则分别称称 x* 为为( (f S) )的严格全局最优解和严格局部最优解的严格全局最优解和严格局部最优解。严格严格l .opt .严格严格g .opt .l .opt .http:/ gi(x),hj(x) :RnRminf(x)(fgh)s.t.gi(x)0,i = 1,2,mhj(x) =0,j = 1,2,l矩阵形式矩阵形式: :minf(x) ，f(x) :RnR(fgh)s.t.g(x)0,g(x)
7、:RnRmh(x) =0,h(x) :RnRl当当f(x), gi(x),hj(x)均为线性函数时，称线性均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划规划；若其中有非线性函数时，称非线性规划。http:/ 优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划问题求解的难度增加http:/ 线性规划线性规划LinearProgramminghttp:/ 1x x1 1+c+c2 2x x2 2+ +.+c.+cn nx xn ns.t. as.t. a1111x x1 1+a+a1212x x2 2+ +.+a.+a1n1nx xn n
8、(=, (=, )b)b1 1 a a2121x x1 1+a+a2222x x2 2+ +.+a.+a2n2nx xn n (=, (=, )b)b2 2 . . a am1m1x x1 1+a+am2m2x x2 2+ +.+a.+amnmnx xn n (=, (=, )b)bm m x x1,1,x x2 2.x.xn n 0 0http:/ 线性规划问题线性规划问题有可行解有可行解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)http:/ x1+x23002x1+x2400 x2250 x1、x20
9、该问题的最优解为该问题的最优解为x1=50=50；x2=250=250x2z*=50x1+100x2=27500x1+x2300x1x22502x1+x2400z1=50x1+100x2=0BOACDz2=14000http:/ 1.模型：命令：x=linprog（c, A, b）2.模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.式中：linprog称为调用函数，C,A,b称为输入参数，全部由用户提供，必须按规定的位置放置在原括号内.http:/ VLBXVUB命令：1x=linprog（c，A，b，Aeq, beq, V
10、LB，VUB）2x=linprog（c，A，b，Aeq, beq, VLB，VUB, X0）注意：1若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点,设置它有些情况下可以减少迭代工作量4.命令：x,fval=linprog()返回最优解及处的目标函数值fval.http:/ -0.28 -0.32 -0.72 -0.64 -0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=; beq=;vlb=0;0;0;0
11、;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh1)http:/ 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)http:/ = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=
12、400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)http:/ = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.http:/ = 40 36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9 15; %调用linprog
13、函数：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh4)http:/ = 9.0000 0.0000fval =360即只需聘用9个一级检验员.注：注：本问题应还有一个约束条件：本问题应还有一个约束条件：x1、x2取整数取整数.故它是一个整数故它是一个整数线性规划问题线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好这里把它当成一个线性规划来解，求得其最优解刚好是整数：是整数：x1=9，x2=0，故它就是该整数规划的最优解，故它就是该整数规划的最优解.若用线性规划若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数
14、规划的解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解最优解，这样的整数规划应用专门的方法求解.返回http:/ x2原料供应原料供应劳动时间劳动时间加工能力加工能力决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100kgA150桶牛奶桶牛奶每天每天基本基本模型模型http:/ 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 z=0z=2400z=3600z =c (常数常数)等值线等值线c在在B(
15、20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 http:/ 软件实现软件实现 LINDOmax72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSL
16、ACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。http:/ OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0
17、000002.0000004)40.0000000.000000max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40http:/ OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000004
18、8.0000003)0.0000002.0000004)40.0000000.000000最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元?2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长加工能力增长不不影响利润影响利润影子价格影子价格http:/ 3=72增至增至30 3=90”（或（或“=”（或（或“=”）功能相同）功能相同2.变量与系数间可有空格变
19、量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4.变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键字）中的关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义.行名以行名以“）”结束结束7.行中注有行中注有“!”符号的后面部分为注释符号的后面部分为注释.如如:!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名（最多（最多72个字符）
20、，如：个字符），如：TITLEThisModelisonlyanExamplehttp:/ x1+x2=345.5; ; x1=98; x1=98; 2*x1+x2=600 2*x1+x2=345.5 x1+x2=345.5 x1=98 x1=98 2*x1+x2=600 2*x1+x2bj，其数学模型为：http:/ i bbj j；若若用用xi，n+1表表示示从从Ai到到Bn+1的的运运量量，可可令令ci，n+1=0或或等等于于第第Ai产产地地储储存存单单位位物物资资的的费费用用。因因为为xi，n+1实实际际上上表表示示Ai产产地地没没有有运运出出去去而而库库存存的的物物资资数数量量。经经
21、处处理理后后，问问题题变变成成了了产产销销平平衡衡的的运输问题，其数学模型为：运输问题，其数学模型为：这样，这样，m个产地、个产地、n个销地的不平衡运输问题，转化成了个销地的不平衡运输问题，转化成了m个产地、个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。个销地的平衡运输问题，此时可用表上作业法求解。http:/ bj，其数学模型为：http:/ bjai； 若用xm+1，j表示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：此时，可用表上作业法求
22、解。此时，可用表上作业法求解。http:/ 某公司有某公司有6个供货栈（仓库），库存货物总数分别为个供货栈（仓库），库存货物总数分别为60，55，51，43，41，52，现有，现有8个客户各要一批货数量分别为个客户各要一批货数量分别为35，37，22，32，41，32，43，38，各供货栈道，各供货栈道8个客户的单位货物运输价见表个客户的单位货物运输价见表供货栈到客户的单位货物运价供货栈到客户的单位货物运价客客户货栈V1V2V3V4V5V6V7V8W162674259W249538582W352197433W476739271W523957265W655228143试确定各货栈到各客户处的货物
23、调运数量，使总的运输费用最小。试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。http:/ 引入决策变量引入决策变量代表从第代表从第个货栈到第个货栈到第个个客户的货物运量客户的货物运量. 设设表示从第表示从第 个货栈个货栈到第 个客户的单位货物运价表示第表示第 个货栈的最大供货量个货栈的最大供货量,表示第表示第个客户的订货量个客户的订货量.目标函数是总运输费用最少目标函数是总运输费用最少.约束条件有三条：约束条件有三条：1. 各货栈运出的货物总量不超过其库存数各货栈运出的货物总量不超过其库存数 2.各客户收到的货物总量等于其订货数量各客户收到的货物总量等于其订货数量3. 决策变量决策
24、变量 非负非负数学模型为数学模型为http:/ 前面介绍的前面介绍的LinGO的基本用法，其优点是输入模型较直观，的基本用法，其优点是输入模型较直观，一般的数学表达式无需作大的变换即可直接输入一般的数学表达式无需作大的变换即可直接输入.对于规模较对于规模较小的的规划模型，用直接输入的方法是有利的，如果模型的小的的规划模型，用直接输入的方法是有利的，如果模型的变量和约束的条件个数比较多，若仍然用直接的输入方式，变量和约束的条件个数比较多，若仍然用直接的输入方式，虽然也能求解并得到结果，但这种做法有明显的不足之处。虽然也能求解并得到结果，但这种做法有明显的不足之处。模型的篇幅很长，不便于分析修改和
25、扩展。模型的篇幅很长，不便于分析修改和扩展。 LinGO 建模语言引入集合的概念，为建立大规模的数学规建模语言引入集合的概念，为建立大规模的数学规划模型提供了方便划模型提供了方便. 用用LinGO 语言表达一个实际优化问题，语言表达一个实际优化问题，称之为称之为 LinGO模型。模型。 一、集合定义部分一、集合定义部分 集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与常量联系起来，是实际问题到数学的抽象。例中的常量联系起来，是实际问题到数学的抽象。例中的6个仓库可以看成一个集合，个仓库可以看成一个集合，8个客户
26、可以看成另一个集合。个客户可以看成另一个集合。http:/ 每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容：集合集合的名称的名称，集合内的成员（元素）集合内的成员（元素）、集合的属性（可以看成与该集合有关的变量集合的属性（可以看成与该集合有关的变量或常量，相当于数组）或常量，相当于数组）.本例首先定义仓库集合本例首先定义仓库集合：WH/W1.W6/:AI; 其中其中WH是集合的名称，是集合的名称，W1.W6是集合内的成员，是集合内的成员， “.” 是特定的省略号是特定的省略号（如果不用该省略号，也可以把成员一一罗
27、列出来，成员之间用逗号或（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或空格分开空格分开),表明该集合有表明该集合有6个成员，分别对应于个成员，分别对应于6个供货栈，个供货栈，AI是集合的属性，是集合的属性，它可以看成是一个数组，有它可以看成是一个数组，有6个分量，分别表示各货栈现有货物的总数。个分量，分别表示各货栈现有货物的总数。集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义的字母数串来表示，式中的字母数串来表示，式中“/ ”和和“/:” 是规定的语法规则是规定的语法规则。本例再定义客户集合本
28、例再定义客户集合：VD/V1.V8/:DJ;该集合有该集合有8个成员，个成员，DJ 是集合的属性（有是集合的属性（有8个分量）表示各客户的需求量个分量）表示各客户的需求量.以上两个集合称为初始集合（或称基本集合、原始集合）初始集合的属性都初始集合（或称基本集合、原始集合）初始集合的属性都相当于一维数组。相当于一维数组。http:/ 和运量再定义一个表示运输关系的集合：LINKS(WH,VD): C,X;该集合以初始集合WH 和 VD 为基础，称为衍生集合（或称派生集合）. C 和X 是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成
29、：1）集合的名称；）集合的名称； (2) 集合的初始集合；集合的初始集合； （3）集合的成员（可以省略不写）；）集合的成员（可以省略不写）；（4）集合的属性（可以没有）集合的属性（可以没有） 定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合LINKS的定的定以中没有指明成员，则它对应的初始集合以中没有指明成员，则它对应的初始集合WH 有有6个成员，个成员，VD 有有8
30、个成员，因此个成员，因此 LINKS成员取成员取WH和和VD的所有可能组合，即有的所有可能组合，即有48个成员，个成员，48个成员可以排列成一个矩阵。其个成员可以排列成一个矩阵。其行数与集合行数与集合WH的成员个数相等，列数与集合的成员个数相等，列数与集合VD成员的个数相等成员的个数相等. 相应地，集合相应地，集合LINKS的的属性和都相当于二维数组，各有属性和都相当于二维数组，各有48个分量，表示货栈个分量，表示货栈i 到客户到客户Vj的单位货物运价的单位货物运价 X 表示货栈表示货栈Wi到客户到客户Vj的货物运量的货物运量.http:/ SETS: 开始，开始，以以ENDSETS语句结束，
31、这两个语句需单独成一行，语句结束，这两个语句需单独成一行，ENDSETS后面不加标点符号后面不加标点符号.二、数据初始化（数据段）二、数据初始化（数据段） 以上集合中属性以上集合中属性X（有（有48个分量）是决策变量，是待求的未知数，属个分量）是决策变量，是待求的未知数，属性性AI、DJ和（分别有和（分别有,8,48个分量）都是已知数，个分量）都是已知数，LINKS 建模语建模语言通过数据初始化部分来实现对已知属性赋以初始值，格式为：言通过数据初始化部分来实现对已知属性赋以初始值，格式为：DATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;
32、C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3;ENDDATA注：数据初始化部分以语句注：数据初始化部分以语句 DATA:开始，以开始，以ENDDATE语句结束，这两个语句需单独成一行，数语句结束，这两个语句需单独成一行，数据之间的逗号和空格可以互换。据之间的逗号和空格可以互换。http:/ 用用LINGO语句表示为语句表示为MIN=SUM(LINKS(I,J):C(I,J)*X(I,J); 式中，式中，SUM 是是LINGO提供的内部函数，其作用
33、是对某个集合的所有成员提供的内部函数，其作用是对某个集合的所有成员求制定表达式的和，该函数需要两个参数，第一个参数是求制定表达式的和，该函数需要两个参数，第一个参数是集合名称集合名称，制定对该，制定对该集合的所有成员求和，如果此集合是一个初始集合，它有集合的所有成员求和，如果此集合是一个初始集合，它有m 个成员，则求和运算个成员，则求和运算对对m 个成员进行，相当于求个成员进行，相当于求 ，第二个参数是一个表达式，表示求和运算对该，第二个参数是一个表达式，表示求和运算对该表达式进行，此处，表达式进行，此处， SUM的第一个参数是的第一个参数是 LINKS（I，J），表示求和运算），表示求和运算
34、对对 LINKS进行，进行， 该集合的维数为该集合的维数为2，共有，共有48个成员，运算规则是：先对个成员，运算规则是：先对48个成员个成员分别求表达式分别求表达式 C(I,J) *X(I,J) 的值，然后求和，相当于求的值，然后求和，相当于求 ，表达式中的，表达式中的 C和和 X是集合的两个属性，它们各有是集合的两个属性，它们各有48个分量。个分量。注：如果表达式中参与酸的属性属于同一个集合，则 语句中索引（相当于矩阵或数组的下标可以省略）（隐藏），假如表达式中参与运算的属性属于不同的集合，则不能省略属性的索引.本例的目标函数可以表示成MIN=SUM(LINKS:C*X);http:/ 语言
35、描述该约束条件，语句为：FOR(WH(I): SUM(VD(J):X(I,J)=AI(I);语句中的FOR是LINGO提供的内部函数，它的作用是对某个集合的所有成员分别生成一个约束表达式，它有两个参数，第一个参数是集合名，表示对该集合的所有成员生成对应的约束表达式，上式 FOR 的第一个参数为，它表示货栈，共有个成员，故应生成个约束表达式，FOR 的第二个参数是约束表达式的具体内容，此处再调用SUM 函数，表示该约束的左边是求和，是对集合的个成员，并且对表达式(I,J) 中的第二维 J 求和，即约束表达式的右边是集合的属性AI，它有6个分量，与6个约束表达式一一对应，本句中的属性分别属于不同的
36、集合，所以不能省略 I,J.约束条件 表示为 FOR(D(J): SUM(VD(J):X(I,J)=DJ(J);http:/ SETS: WH/W1.W6/:AI; VD/V1.V8/:DJ; LINKS(WH,VD):C,X; ENDSETSDATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3;ENDDATAMIN=SUM(LINKS (I,J):
37、C(I,J)*X(I,J); !目标函数FOR(WH(I): SUM(VD(J):X(I,J)=AI(I); !约束条件FOR(VD(J):SUM(VD(J):X(I,J)=DJ(J);END以以“MODEL：”开始开始集合定义部分从集合定义部分从(“SETS：”到到“ENDSETS”)：定：定义集合及其属性义集合及其属性以以“END”结结束束给出优化目标给出优化目标和约束和约束集合定义部分从集合定义部分从(“DATA：”到到“ENDDATA” )http:/ 2”表示表示2个变量都是一般整数变量。个变量都是一般整数变量。 （仍然默认为取值是非负的）（仍然默认为取值是非负的）http:/ 但需
38、但需在在END标志后定义整型变量标志后定义整型变量。 0/1型的变量可由型的变量可由INTEGER（可简写为（可简写为INT）命令来标识，）命令来标识，有以下两种可能的用法：有以下两种可能的用法： INT vname INT n前者只将决策变量前者只将决策变量vname标识为标识为0/1型型, 后者将当前模型中前后者将当前模型中前n 个变量标识为个变量标识为0/1型（模型中变量顺序由型（模型中变量顺序由模型中输入时出现的先后顺序决定模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的该顺序可由输出结果中的变量顺序查证是否一致）。变量顺序查证是否一致）。 一般的整数变量可用命令一般的整数变量
39、可用命令GIN （是（是GENERAL INTEGER的意的意思）思）,其使用方式及格式与其使用方式及格式与INT 命令相似。命令相似。http:/ OR SURPLUS）仍然可以表示约束的松紧程度，但目前仍然可以表示约束的松紧程度，但目前IP尚无尚无相应完善的敏感性分析理论，因此相应完善的敏感性分析理论，因此REDUCED COST和和DUAL PRICES的结果在整数规划中的结果在整数规划中意义不大。意义不大。 http:/ , X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数5X1+4X2 242X1+5X2 13X1 ,X2 0 0X1 ,X2为整数为整数maxZ = 20 ma
40、xZ = 20 X1 + 10 X2http:/ 种物品种物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi为为0, 1Model:Min=-(20*x1+30*x2+10*x3+18*x4+15*x5);5*x1+3*x2+x3+2*x4+4*x58;2*x1+x2+4*x3+2*x4+5*x50xj0时，为使时，为使Z Z 极大化，极大化，应有应有Yj=0Yj=0http:/ x1x21x1x2x61x3x41x3x4x51x4x5x61x2x5x61xi1或0（i1，6）
41、http:/ 客户客户项目主管项目主管1231231096151814953http:/ x11+x12+x13=1 x21+x22+x23=1 x31+x32+x33=1 x11+x21+x31=1 x12+x22+x32=1 x13+x23+x33=1xij0，i=1，2，3；j=1，2，3http:/ kg2111设备台时 hr12 10利润 元/件810 解：这是一个单目标规划问题，可用线性规划模解：这是一个单目标规划问题，可用线性规划模型表述为：型表述为：试求获利最大的方案。试求获利最大的方案。例例1 1 利润最大化问题：利润最大化问题：http:/ 在实际问题中，决策者在作决策时，
42、往往在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性于数学模型相对于实际问题的近似性http:/ 缺点缺点缺点缺点：难处在于如何寻到合理的权系数。：难处在于如何寻到合理的权系数。2.序列或优先级法序列或优先级法：序列或优先级法序列或优先级法序列或优先级法序列或优先级法不是对每个目标加权，而是按照目标不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。的轻重缓急，将其分为不同等级再求解。优点优点优点优点：避免了权系数的困扰，绝大多数决策者都能采：避免了权系数的困扰，绝大多数决策者都
43、能采用，事实上他们在许多决策中也正是这样做的。用，事实上他们在许多决策中也正是这样做的。例如建设高速公路时，既希望减少开支又希望降低交例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？值呢？例如决定人员的提升时，许多单位是按其工作态度、例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。进行评定的。http:/ 缺点缺点缺点缺点：难处在于如何确切地定出各个目标的优先顺序：难处在于如何确切地定出各个目标的优
44、先顺序以获得满意的求解结果。以获得满意的求解结果。3.有效解（或非劣解）法：有效解（或非劣解）法：有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法“不会产生不会产生”象加权法或优先象加权法或优先级法所具有的局限性，它将找出全部有效解集（即级法所具有的局限性，它将找出全部有效解集（即非非劣解劣解）以供决策者从中挑选。）以供决策者从中挑选。 缺点缺点缺点缺点：难处在于实际问题中非劣解太多，难于一一推：难处在于实际问题中非劣解太多，难于一一推荐给决策者。荐给决策者。http:/ kg2111设备台时 hr1210利润 元/件810 解：这是一个单目标规划问题，可用线性
45、规划模解：这是一个单目标规划问题，可用线性规划模型表述为：型表述为：试求获利最大的方案。试求获利最大的方案。例例1 1 利润最大化问题：利润最大化问题：http:/ 1. 正、负偏差变量正、负偏差变量正、负偏差变量正、负偏差变量d d+ +,d,d- - d d+ + : : 决策值超过目标值的部分决策值超过目标值的部分 d d- - ：决策值未达到目标值的部分：决策值未达到目标值的部分 恒有恒有 d d+ +d d- -=0=0例如目标例如目标z=8x1+10x2可以变化为目标约束：可以变化为目标约束：8x1+10x2+d1-d1+56绝对约束绝对约束2x1+x211可以变换为目标约束：可以
46、变换为目标约束：2x1+x2+d2-d2+11一、与建立目标规划模型有关的概念一、与建立目标规划模型有关的概念http:/ . 3 . 优先因子与权系数优先因子与权系数 目标规划问题常常有多个目标，但这些目标的主目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。次或轻重缓急是不同的。 最重要的目标赋予优先因子最重要的目标赋予优先因子P1P1，次一级的目标赋，次一级的目标赋予优先因子予优先因子P2P2，并规定，并规定 P Pk kPPk+1k+1即表示即表示 P Pk k比比P Pk+1k+1有更大的优先权。有更大的优先权。 如果要区别具有相同优先因子的两个目标的差别，如果要区别具
47、有相同优先因子的两个目标的差别，则分别赋予它们不同的权系数则分别赋予它们不同的权系数w wj j。http:/ .4 .目标规划的目标函数目标规划的目标函数 min min z = = f (d,d)三种基本形式：三种基本形式：目标类型目标类型目标规划格式目标规划格式需要极小化需要极小化的偏差变量的偏差变量fi(x) bifi(x) dd bidfi(x) bifi(x) dd bidfi(x) bifi(x) dd biddd d+ + : : 决策值超过目标值的部分决策值超过目标值的部分http:/ x2极小化极小化例例2 2 例例1 1的目标规划模型：的目标规划模型：http:/ d1
48、1 -d -d1 1+ +60000每级的人数不超过定编规定的人数：每级的人数不超过定编规定的人数：1.10-10*0.1+x1+d d2 2 -d -d2 2+ +122.12-x1+x2+d d3 3 -d -d3 3+ +153.15-x2+x3+d d4 4 -d -d4 4+ +15二、三级的升级面尽可能提升到现有人数的二、三级的升级面尽可能提升到现有人数的20%：二级、二级、x1+d d5 5 -d -d5 5+ +12*0.2三级、三级、x2+d d6 6 -d -d6 6+ +15*0.2http:/ P1 d P1 d1 1+ + + P2( d+ P2( d2 2+ + + d+ d3 3+ + + d+ d4 4+ + ) )+ P3( d+ P3( d5 5- - + d+ d6 6- - ) )三、用三、用Lindo求解的方法求解目标规划求解的方法求解目标规划http:/ d3-可用可用d3plus表示。表示。求出最优目标值为求出最优目标值为z d3- =0。http:/ =0变为约束变为约束求出最优目标值为求出最优目标值为z 2d1+3d2+=12。http:/
