《【大学竞赛】数学建模辅导 优化部分ppt(P134)》由会员分享，可在线阅读，更多相关《【大学竞赛】数学建模辅导 优化部分ppt(P134)（134页珍藏版）》请在金锄头文库上搜索。
1、数学建模数学建模优化模型介绍引言-数学之重要数学使人周密数学使人周密 - Francis Bacon 数学处于人类智能的中心领域数学处于人类智能的中心领域数学方数学方法渗透、支配着一切自然科学的理论分支法渗透、支配着一切自然科学的理论分支它已愈来愈成为衡量成就的主要标志。它已愈来愈成为衡量成就的主要标志。 - von Neumann 引言-数学之重要 一门科学只有当它达到能够成功地运用一门科学只有当它达到能够成功地运用 数学时，才算真正发展了。数学时，才算真正发展了。 - - Karl MarxGalileo : : 展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在
2、黑暗的迷宫里游荡，什么也认识不清。数学是一种语言，是一切科学的共同语言数学是一种语言，是一切科学的共同语言引言-数学之重要数学是一种技术，是高技术的本质数学是一种技术，是高技术的本质数学技术数学技术-数学方法与计算技术的结合形 成的一种关键性的、可实现的技术二十世纪最伟大的数学家-二十世纪最伟大的物理学家-D.HilbertA.EinsteinGo back诺贝尔诺贝尔奖奖菲尔兹奖菲尔兹奖1.什么是数学模型？什么是数学模型？数学模型数学模型是对于现实世界的一个特定对象特定对象，一个特定目的特定目的，根据特有的内在规律内在规律，做出一些必要的假必要的假设设，运用适当的数学工具数学工具，得到一个数
3、学结构数学结构简单地说：就是系统的某种特征的本质的数学表达式（或是用数学术语对部分现实世界的描述），即用数学式子（如函数、图形、代数方程、微分方程、积分方程、差分方程等）来描述（表述、模拟）所研究的客观对象或系统在某一方面的存在规律2.什么是数学建模什么是数学建模?数学建模数学建模是利用数学方法解决实际问题的一种实践即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的数学方法及计算机技术进行求解观点：观点：“所谓所谓高科技高科技就是一种就是一种数学技术数学技术” 数学建模数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解决实际问题，就
4、一定要用数学的语言、方法去近似地刻画该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎添翼似的得到了飞速的发展，掀起一个高潮数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一.数学建模参考书数学建模参考书1.数学模型姜启源、谢金星、叶俊编高等教育出版社2.数学建模方法及其应用解放军信息工程大学韩中庚编高教社3.数学模型与数学建模刘来福、曾文艺编著北师大出版社4.叶其孝等
5、，大学生数学建模竞赛辅导教材（一）（四），湖南教育出版社5.赵静等，数学建模与数学实验，高等教育出版社，施普林格出版社 规划模型的应用极其广泛，其作用已为越来规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为行为 科学研究的各个方面，为社会节省的财富、科学研究的各个方面，为社会节省的财富、创造的价值无法估量创造的价值无法估量. 特别是在数模竞赛过程中，规划模型是最常特别是在数模竞赛过程中，规划模型是最常见的一类数学模型见的一类数学模型. 从从92-06年全国大学生数模竞年全国大学生数模竞越多的人所重视越多的人所重视.
6、随着计算机的逐渐普及，它越随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出赛试题的解题方法统计结果来看，规划模型共出现了现了15次，占到了次，占到了50%，也就是说每两道竞赛题，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解. 优化问题，一般是指用“最好”的方式，使用或分配有限的资源，即劳动力、原材料、机器、资金等，使得费用最小或者利润最大。优化模型优化模型min min f(x) -目标函数目标函数 s.t. s.t. x S -约束集合，可行集约束集合，可行集其中，其中，S R Rn n，f : :S R R，x S
7、称（称（f S ) )的可行解的可行解n最优解最优解: : x* S，满足满足f (x*) f (x), x S。则称则称 x*为为( (f S) )的全局最优解的全局最优解( (最优解最优解),), 记记 g.opt.( (global optimum),),简记简记 opt.n最优值最优值: : x*为为( (f S) )的最优解的最优解, , 则称则称 f * = f (x*) 为为 ( (f S) )的最优值的最优值( (最优目标函数值最优目标函数值) )数学规划模型的一般形式数学规划模型的一般形式(f S)n局部最优解局部最优解: : x* S， x* 的邻域的邻域 N(x*) ，使
8、满足，使满足 f (x*) f (x), x S N(x*) 。则称则称 x*为为( (f S) )的局部最的局部最优解优解, ,记记 l .opt.( (local optimum) )n在上述定义中，当在上述定义中，当x x* 时有严格不等式成立，时有严格不等式成立，则分别则分别称称 x* 为为( (f S) )的严格全局最优解和严格局部最优解的严格全局最优解和严格局部最优解。严格严格l .opt .严格严格g .opt .l .opt .数学规划模型的一般形式数学规划模型的一般形式函数形式函数形式:f(x), gi(x),hj(x) :RnRminf(x)(fgh)s.t.gi(x)0,
9、i = 1,2,mhj(x) =0,j = 1,2,l矩阵形式矩阵形式: :minf(x) ，f(x) :RnR(fgh)s.t.g(x)0,g(x) :RnRmh(x) =0,h(x) :RnRl当当f(x), gi(x),hj(x)均为线性函数时，称线性均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划规划；若其中有非线性函数时，称非线性规划。优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目
10、标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划问题求解的难度增加 线性规划线性规划LinearProgramming问题一问题一：任务分配问题任务
11、分配问题：某车间有甲、乙两台机床，可用某车间有甲、乙两台机床，可用于加工三种工件于加工三种工件.假定这两台车床的可用台时数分别为假定这两台车床的可用台时数分别为800和和900，三种工件的数量分别为，三种工件的数量分别为400、600和和500，且已知用三种，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如不同车床加工单位数量不同工件所需的台时数和加工费用如下表下表.问怎样分配车床的加工任务，才能既满足加工工件的要问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？求，又使加工费用最低？两个引例两个引例建立线性规划模型的基本步骤建立线性规划模型的基本步骤：（1
12、）设出决策变量设出决策变量（2）确定目标函数确定目标函数（3）确定约束条件确定约束条件找出待定的未知变量（决策变量），并用代数符号表示找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值找出问题的所有的限制或约束，写出未知变量的线性方程或线性不等式解解设在甲车床上加工工件设在甲车床上加工工件1、2、3的数量分别为的数量分别为x1、x2、x3，在乙车床上加工工件，在乙车床上加工工件1、2、3的数量分别为的数量分别为x4、x5、x6,可建立可建立以下线性规划模型：以下线性规划模型：解答问题二：问题二：某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件件.为了进行质量为了
13、进行质量控制，计划聘请两种不同水平的检验员控制，计划聘请两种不同水平的检验员.一级检验员的标准为：一级检验员的标准为：速度速度25件件/小时，正确率小时，正确率98%，计时工资，计时工资4元元/小时；二级检验员小时；二级检验员的标准为：速度的标准为：速度15件件/小时，正确率小时，正确率95%，计时工资，计时工资3元元/小时小时.检检验员每错检一次，工厂要损失验员每错检一次，工厂要损失2元元.为使总检验费用最省，该工为使总检验费用最省，该工厂应聘一级、二级检验员各几名？厂应聘一级、二级检验员各几名？解解设需要一级和二级检验员的人数分别为设需要一级和二级检验员的人数分别为x1、x2人人,则应付检
14、验员的工资为：则应付检验员的工资为：因检验员错检而造成的损失为因检验员错检而造成的损失为：故目标函数为：故目标函数为：约束条件为：线性规划模型：线性规划模型：解答返回模型特点：目标函数模型特点：目标函数(Objectivefunction)与约束条件与约束条件(Constraint)均为线性的；均为线性的；目标函数实现极大化或极小化。目标函数实现极大化或极小化。线性规划问题的一般形式：线性规划问题的一般形式：Max(Min)S=cMax(Min)S=c1 1x x1 1+c+c2 2x x2 2+ +.+c.+cn nx xn ns.t. as.t. a1111x x1 1+a+a1212x
15、x2 2+ +.+a.+a1n1nx xn n (=, (=, )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 0线性规划的线性规划的基本概念基本概念1.可行解可行解(FeasibleSolution)任一满足约束条件的任一满足约束条件的一组决策变量的数值一组决策变量的数值.2.可行域可行域(FeasibleRegion)所
16、有可行解组成的集合，所有可行解组成的集合，也称为可行解集也称为可行解集.3.目标函数等值线目标函数等值线(Objectivefunctionline)为于同一直线上的点，具有相同的目标函数值为于同一直线上的点，具有相同的目标函数值.线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)数学建模中线性规划模型的常用解法数学建模中线性规划模型的常用解法线性规划问题的求解在理在理论上有单纯型法，在实际建模线性规划问题的求解在理在理
17、论上有单纯型法，在实际建模中常用以下解法：中常用以下解法：1.图解法图解法2.LINGO软件包软件包3.Excel中的规划求解中的规划求解4.MATLAB软件包软件包主要介绍线性规划模型的主要介绍线性规划模型的MATlAB软件包和软件包和LINGO软件包解法软件包解法模型求解方法模型求解方法1.图解法图解法例1maxz=50x1+100x2 x1+x23002x1+x2400 x2250 x1、x20该问题的最优解为该问题的最优解为x1=50=50；x2=250=250x2z*=50x1+100x2=27500x1+x2300x1x22502x1+x2400z1=50x1+100x2=0BOA
18、CDz2=14000用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX 1.模型：命令：x=linprog（c, A, b）2.模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.式中：linprog称为调用函数，C,A,b称为输入参数，全部由用户提供，必须按规定的位置放置在原括号内.3.模型：minz=cX VLBXVUB命令：1x=linprog（c，A，b，Aeq, beq, VLB，VUB）2x=linprog（c，A，b，Aeq, beq, VLB，VUB, X0）注意：1若没有等式约束:,则令Ae
19、q=,beq=.2其中X0表示初始点,设置它有些情况下可以减少迭代工作量4.命令：x,fval=linprog()返回最优解及处的目标函数值fval.解解编写编写M文件文件xxgh1.m如下：如下：c=-0.4 -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;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq
20、,vlb,vub)ToMATLAB(xxgh1)解解:编写编写M文件文件xxgh2.m如下：如下：c=6 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)s.t.改写为：例例3问题一的解答问题问题编写编写M文件文件xxgh3.m如下如下:f = 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
21、1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)结果结果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.例例2问题二的解答问题问题改写为：编写编写M文件文件xxgh4.m如下：如下：c = 40 36;A=-5 -3
22、;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9 15; %调用linprog函数：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh4)结果为：结果为：x = 9.0000 0.0000fval =360即只需聘用9个一级检验员.注：注：本问题应还有一个约束条件：本问题应还有一个约束条件：x1、x2取整数取整数.故它是一个整数故它是一个整数线性规划问题线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好这里把它当成一个线性规划来解，求得其最优解刚好是整数：是整数：x1=9，x2=0，故它就是该整数规划
23、的最优解，故它就是该整数规划的最优解.若用线性规划若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解最优解，这样的整数规划应用专门的方法求解.返回用用LINDO、LINGO优化工具箱解线性规划优化工具箱解线性规划LINDO公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司（系统公司（LINDOSystemsInc.），），网址：网址：htt
24、p:/LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V7.0)演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版（求解（求解问题规模问题规模和和选件选件不同）不同）LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能
25、求解的优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)一、一、LINDO软件包软件包下面我们通过一个例题来说明下面我们通过一个例题来说明LINDO软件包的使用方法软件包的使用方法.问题：一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1,A2两种奶制品，一桶两种奶制品，一桶牛奶可以在甲类设备上用牛奶可以在甲类设备上用12小时生产成小时生产成3公斤公斤A1，或者在乙类设备，或者在乙类设备上用上用8小时加工成小时加工成4公斤公斤A2.据市场要求，生产的两种奶制品全部据市场要求，生产的
26、两种奶制品全部能售出，且每公斤能售出，且每公斤A1获利获利24元，每公斤元，每公斤A2获利获利16元，现在每天加元，现在每天加工厂每天能得到工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工小时，并且甲类设备每天至多能加工100公斤公斤A1，乙类设备的，乙类设备的加工能力没有限制加工能力没有限制.试为该厂制定一个生产计划，使每天获利最大，试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下并进一步讨论以下3个附加问题。个附加问题。1）若用）若用35元可以买到元可以买到1桶牛奶，应否作这样的投资？若投资，
27、桶牛奶，应否作这样的投资？若投资，每天最多购买多少桶牛奶每天最多购买多少桶牛奶2）若可以聘用临时工人以增加劳动时间，付给临时工人的）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？工资最多是每小时几元？3）由于市场需求变化，每公斤）由于市场需求变化，每公斤A1的获利增加到的获利增加到30元，应否元，应否改变生产计划？改变生产计划？1桶桶牛奶牛奶3kgA112小时小时8小时小时4kgA2或或获利获利24元元/kg获利获利16元元/kgx1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应劳动时间劳动时间加工能力加工能力
28、决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100kgA150桶牛奶桶牛奶每天每天基本基本模型模型模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 z=0z=2400z=3600z =c (常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最
29、优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 模型求解模型求解 软件实现软件实现 LINDOmax72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000DORANGE(SENSITIVITY)ANALYS
30、IS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧
31、约束（有效约束）剩余为零的约束为紧约束（有效约束）原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量35元可买到元可买到1桶牛奶，要买吗
32、桶牛奶，要买吗?3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元?2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长加工能力增长不不影响利润影响利润影子价格影子价格RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.0000
33、00RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?YesA1获利增加到获利增加到30元元/kg，应否改变生产计划，应否改变生产计划?x1系数由系数由24 3=72增至增至30 3=90”（或（或“=”（或（或“=”）
34、功能相同）功能相同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4.变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键字）中的关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义.行名以行名以“）”结束结束7.行中注有行中注有“!”符号的后面部分为注释符号的后面部分为注释.如如:!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”
35、对模型命名对模型命名（最多（最多72个字符），如：个字符），如：TITLEThisModelisonlyanExample9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简，如表达式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“END”语句后语句后用用“FREEname”将变量将变量name的非负假定取消的非负假定取消13.可
36、在可在“END”后用后用“SUB”或或“SLB”设定变量上下设定变量上下界界例如：例如：“subx110”的作用等价于的作用等价于“x1=345.5 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，其数学模型为：解解此此类类问问题题可可假假想想一一个个销销地地Bn+1，其其需需要要量量为为：bn+1=aai i bbj j；若若用用xi，n+1表表示示从从Ai到到Bn+1的的运运量量，可可令令ci，n+1=0或或等等于于第第Ai产产地地储储存
37、存单单位位物物资资的的费费用用。因因为为xi，n+1实实际际上上表表示示Ai产产地地没没有有运运出出去去而而库库存存的的物物资资数数量量。经经处处理理后后，问问题题变变成成了了产产销销平平衡衡的的运输问题，其数学模型为：运输问题，其数学模型为：这样，这样，m个产地、个产地、n个销地的不平衡运输问题，转化成了个销地的不平衡运输问题，转化成了m个产地、个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。个销地的平衡运输问题，此时可用表上作业法求解。二、销大于产二、销大于产(totaldemandexceedstotalsupply)销大于产的运输问题的特征是ai bj，其数学模型为：解此问
38、题可假想一个产地Am+1，其产量为：am+1= bjai； 若用xm+1，j表示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：此时，可用表上作业法求解。此时，可用表上作业法求解。例例 某公司有某公司有6个供货栈（仓库），库存货物总数分别为个供货栈（仓库），库存货物总数分别为60，55，51，43，41，52，现有，现有8个客户各要一批货数量分别为个客户各要一批货数量分别为35，37，22，32，41，32，43，38，各供货栈道，各供货栈道8个客户的单位货物
39、运输价见表个客户的单位货物运输价见表供货栈到客户的单位货物运价供货栈到客户的单位货物运价客客户货栈V1V2V3V4V5V6V7V8W162674259W249538582W352197433W476739271W523957265W655228143试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。解解 引入决策变量引入决策变量代表从第代表从第个货栈到第个货栈到第个个客户的货物运量客户的货物运量. 设设表示从第表示从第 个货栈个货栈到第 个客户的单位货物运价表示第表示第 个货栈的最大供货量个货栈的最大供货量,表示第表示第个客户的
40、订货量个客户的订货量.目标函数是总运输费用最少目标函数是总运输费用最少.约束条件有三条：约束条件有三条：1. 各货栈运出的货物总量不超过其库存数各货栈运出的货物总量不超过其库存数 2.各客户收到的货物总量等于其订货数量各客户收到的货物总量等于其订货数量3. 决策变量决策变量 非负非负数学模型为数学模型为 前面介绍的前面介绍的LinGO的基本用法，其优点是输入模型较直观，的基本用法，其优点是输入模型较直观，一般的数学表达式无需作大的变换即可直接输入一般的数学表达式无需作大的变换即可直接输入.对于规模较对于规模较小的的规划模型，用直接输入的方法是有利的，如果模型的小的的规划模型，用直接输入的方法是
41、有利的，如果模型的变量和约束的条件个数比较多，若仍然用直接的输入方式，变量和约束的条件个数比较多，若仍然用直接的输入方式，虽然也能求解并得到结果，但这种做法有明显的不足之处。虽然也能求解并得到结果，但这种做法有明显的不足之处。模型的篇幅很长，不便于分析修改和扩展。模型的篇幅很长，不便于分析修改和扩展。 LinGO 建模语言引入集合的概念，为建立大规模的数学规建模语言引入集合的概念，为建立大规模的数学规划模型提供了方便划模型提供了方便. 用用LinGO 语言表达一个实际优化问题，语言表达一个实际优化问题，称之为称之为 LinGO模型。模型。 一、集合定义部分一、集合定义部分 集合是一组相关对象构
42、成的组合，代表模型中的实际事物，并与数学变量与集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与常量联系起来，是实际问题到数学的抽象。例中的常量联系起来，是实际问题到数学的抽象。例中的6个仓库可以看成一个集合，个仓库可以看成一个集合，8个客户可以看成另一个集合。个客户可以看成另一个集合。 每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容：集合集合的名称的名称，集合内的成员（元素）集合内的成员（元素）、集合的属性（可以看成与该集合有关的变量集合的属性（可以看成与该集合有关的变量或常量，相当于数组）或常
43、量，相当于数组）.本例首先定义仓库集合本例首先定义仓库集合：WH/W1.W6/:AI; 其中其中WH是集合的名称，是集合的名称，W1.W6是集合内的成员，是集合内的成员， “.” 是特定的省略号是特定的省略号（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或空格分开空格分开),表明该集合有表明该集合有6个成员，分别对应于个成员，分别对应于6个供货栈，个供货栈，AI是集合的属性，是集合的属性，它可以看成是一个数组，有它可以看成是一个数组，有6个分量，分别表示各货栈现有货物的总数。个分量，分别表示各货栈现有货物的总数。集合、
44、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义的字母数串来表示，式中的字母数串来表示，式中“/ ”和和“/:” 是规定的语法规则是规定的语法规则。本例再定义客户集合本例再定义客户集合：VD/V1.V8/:DJ;该集合有该集合有8个成员，个成员，DJ 是集合的属性（有是集合的属性（有8个分量）表示各客户的需求量个分量）表示各客户的需求量.以上两个集合称为初始集合（或称基本集合、原始集合）初始集合的属性都初始集合（或称基本集合、原始集合）初始集合的属性都相当于一维数组。相当于一维数组。为表示数学模型中从货栈到客户的运输
45、关系以及与此相关的运输单价 和运量再定义一个表示运输关系的集合：LINKS(WH,VD): C,X;该集合以初始集合WH 和 VD 为基础，称为衍生集合（或称派生集合）. C 和X 是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成：1）集合的名称；）集合的名称； (2) 集合的初始集合；集合的初始集合； （3）集合的成员（可以省略不写）；）集合的成员（可以省略不写）；（4）集合的属性（可以没有）集合的属性（可以没有） 定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则定义衍生集合时可以用罗列的方式将衍生集合
46、成员一一列举出来，如果省略不写，则默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合LINKS的定的定以中没有指明成员，则它对应的初始集合以中没有指明成员，则它对应的初始集合WH 有有6个成员，个成员，VD 有有8 个成员，因此个成员，因此 LINKS成员取成员取WH和和VD的所有可能组合，即有的所有可能组合，即有48个成员，个成员，48个成员可以排列成一个矩阵。其个成员可以排列成一个矩阵。其行数与集合行数与集合WH的成员个数相等，列数与集合的成员个数相等，列数与集合VD成员的个数相等成员的个数相等. 相应地，集合相
47、应地，集合LINKS的的属性和都相当于二维数组，各有属性和都相当于二维数组，各有48个分量，表示货栈个分量，表示货栈i 到客户到客户Vj的单位货物运价的单位货物运价 X 表示货栈表示货栈Wi到客户到客户Vj的货物运量的货物运量.本模型完整的集合定义为：SETS:WH/W1.W6/:AI;VD/V1.V8/DJ;LINKS(WH,VD):C,X;ENDSETS注：集合定义部分以语句注：集合定义部分以语句 SETS: 开始，开始，以以ENDSETS语句结束，这两个语句需单独成一行，语句结束，这两个语句需单独成一行，ENDSETS后面不加标点符号后面不加标点符号.二、数据初始化（数据段）二、数据初始
48、化（数据段） 以上集合中属性以上集合中属性X（有（有48个分量）是决策变量，是待求的未知数，属个分量）是决策变量，是待求的未知数，属性性AI、DJ和（分别有和（分别有,8,48个分量）都是已知数，个分量）都是已知数，LINKS 建模语建模语言通过数据初始化部分来实现对已知属性赋以初始值，格式为：言通过数据初始化部分来实现对已知属性赋以初始值，格式为：DATA: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
49、,5,7,2,6,5 5,5,2,2,8,1,4,3;ENDDATA注：数据初始化部分以语句注：数据初始化部分以语句 DATA:开始，以开始，以ENDDATE语句结束，这两个语句需单独成一行，数语句结束，这两个语句需单独成一行，数据之间的逗号和空格可以互换。据之间的逗号和空格可以互换。三、目标函数和约束条件三、目标函数和约束条件目标函数表达式目标函数表达式 用用LINGO语句表示为语句表示为MIN=SUM(LINKS(I,J):C(I,J)*X(I,J); 式中，式中，SUM 是是LINGO提供的内部函数，其作用是对某个集合的所有成员提供的内部函数，其作用是对某个集合的所有成员求制定表达式的和
50、，该函数需要两个参数，第一个参数是求制定表达式的和，该函数需要两个参数，第一个参数是集合名称集合名称，制定对该，制定对该集合的所有成员求和，如果此集合是一个初始集合，它有集合的所有成员求和，如果此集合是一个初始集合，它有m 个成员，则求和运算个成员，则求和运算对对m 个成员进行，相当于求个成员进行，相当于求 ，第二个参数是一个表达式，表示求和运算对该，第二个参数是一个表达式，表示求和运算对该表达式进行，此处，表达式进行，此处， SUM的第一个参数是的第一个参数是 LINKS（I，J），表示求和运算），表示求和运算对对 LINKS进行，进行， 该集合的维数为该集合的维数为2，共有，共有48个成员
51、，运算规则是：先对个成员，运算规则是：先对48个成员个成员分别求表达式分别求表达式 C(I,J) *X(I,J) 的值，然后求和，相当于求的值，然后求和，相当于求 ，表达式中的，表达式中的 C和和 X是集合的两个属性，它们各有是集合的两个属性，它们各有48个分量。个分量。注：如果表达式中参与酸的属性属于同一个集合，则 语句中索引（相当于矩阵或数组的下标可以省略）（隐藏），假如表达式中参与运算的属性属于不同的集合，则不能省略属性的索引.本例的目标函数可以表示成MIN=SUM(LINKS:C*X);约束条件约束条件用INGO 语言描述该约束条件，语句为：FOR(WH(I): SUM(VD(J):X
52、(I,J)=AI(I);语句中的FOR是LINGO提供的内部函数，它的作用是对某个集合的所有成员分别生成一个约束表达式，它有两个参数，第一个参数是集合名，表示对该集合的所有成员生成对应的约束表达式，上式 FOR 的第一个参数为，它表示货栈，共有个成员，故应生成个约束表达式，FOR 的第二个参数是约束表达式的具体内容，此处再调用SUM 函数，表示该约束的左边是求和，是对集合的个成员，并且对表达式(I,J) 中的第二维 J 求和，即约束表达式的右边是集合的属性AI，它有6个分量，与6个约束表达式一一对应，本句中的属性分别属于不同的集合，所以不能省略 I,J.约束条件 表示为 FOR(D(J): S
53、UM(VD(J):X(I,J)=DJ(J);完整的模型MODEL: 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):C(I,J)*X(I,J); !目标函数FOR(WH(I)
54、: 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” )整数规划整数规划-IntegerProgramming,IP整数规划整数规划（IntegerProgramming）主要是指整数线）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量性规划。一个线
55、性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。为整数，则构成一个整数规划问题。所有变量都要求为整数的称为所有变量都要求为整数的称为纯整数规划纯整数规划（PureIntegerProgramming）或称）或称全整数规划全整数规划（AllintegerProgramming）；）；仅有一部分变量要求为整数的称为仅有一部分变量要求为整数的称为混合整数规划混合整数规划（MixedIntegerProgramming）；）；有的变量限制其取值只能为有的变量限制其取值只能为0或或1，这类特殊的整数规，这类特殊的整数规划称为划称为01规划规划(0-1IntegerProgramming)
56、整数规划问题及其数学模型整数规划问题及其数学模型例某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备设备材材料料甲甲乙乙资源限量资源限量材料材料A（kg）2314材料材料B（kg）10.54.5利润（元利润（元/件）件）32解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：Maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数且为整数图41要求该模型的解，不考虑整数约束条件，用图解法要求该模型的解，不考虑整数约束条件，用图解法对相应线性规
57、划求解，其最优解为：对相应线性规划求解，其最优解为：x13.25x22.5maxz14.75-凑整得到的凑整得到的（4，2）不在可行域范围内。不在可行域范围内。-（3，2）点尽管在可行域内，但没有使目标达到极大化。点尽管在可行域内，但没有使目标达到极大化。-（4，1）使目标函数达到最大，即使目标函数达到最大，即z14。IP可用可用LINDO直接求解直接求解max3x1+2x2st2x1+3x214x1+0.5x24.5endgin2“gin2”表示表示“前前2个变量为个变量为整数整数”，等价于：，等价于：ginx1ginx2其中其中“GIN 2”表示表示2个变量都是一般整数变量。个变量都是一般
58、整数变量。 （仍然默认为取值是非负的）（仍然默认为取值是非负的）LINDO可用于求解线性纯整数规划或混合整数规划可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与模型的输入与LP问题类似问题类似, 但需但需在在END标志后定义整型变量标志后定义整型变量。 0/1型的变量可由型的变量可由INTEGER（可简写为（可简写为INT）命令来标识，）命令来标识，有以下两种可能的用法：有以下两种可能的用法： INT vname INT n前者只将决策变量前者只将决策变量vname标识为标识为0/1型型, 后者将当前模型中前后者将当前模型中前n 个变量标识为个变量标识为0/1型（模型中变量顺序由型
59、（模型中变量顺序由模型中输入时出现的先后顺序决定模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的该顺序可由输出结果中的变量顺序查证是否一致）。变量顺序查证是否一致）。 一般的整数变量可用命令一般的整数变量可用命令GIN （是（是GENERAL INTEGER的意的意思）思）,其使用方式及格式与其使用方式及格式与INT 命令相似。命令相似。SETX2TO=4AT2,BND=14.00TWIN=13.0010NEWINTEGERSOLUTIONOF14.0000000ATBRANCH2PIVOT10BOUNDONOPTIMUM:14.00000DELETEX1ATLEVEL2DELETEX
60、2ATLEVEL1ENUMERATIONCOMPLETE.BRANCHES=2PIVOTS=10LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION.OBJECTIVEFUNCTIONVALUE1)14.00000VARIABLEVALUEREDUCEDCOSTX14.000000-3.000000X21.000000-2.000000ROWSLACKORSURPLUSDUALPRICES2)3.0000000.0000003)0.0000000.000000NO.ITERATIONS=10BRANCHES=2DETERM.=1.
61、000E0最优值最优值松弛和剩余变量（松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束的松紧程度，但目前仍然可以表示约束的松紧程度，但目前IP尚无尚无相应完善的敏感性分析理论，因此相应完善的敏感性分析理论，因此REDUCED COST和和DUAL PRICES的结果在整数规划中的结果在整数规划中意义不大。意义不大。 例例2、集装箱运货、集装箱运货货物货物体积体积(米米3/箱箱)重量重量(百公斤百公斤/箱箱)利润利润(千元千元/箱箱)甲甲5220乙乙4510装运限制装运限制2413解：设解：设X1 , X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数5X1+4X2 242
62、X1+5X2 13X1 ,X2 0 0X1 ,X2为整数为整数maxZ = 20 maxZ = 20 X1 + 10 X2例例3、背包问题、背包问题背包可装入背包可装入8单位重量，单位重量，10单位体积物品单位体积物品物品物品名称名称重量重量体积体积价值价值1书书52202摄像机摄像机31303枕头枕头14104休闲食品休闲食品23185衣服衣服4515解：解：Xi为是否带第为是否带第i 种物品种物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi为为0, 1Model:Min=
63、-(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=0（四）布点问题(LocationProblem)例4.9某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表49，请帮助该市制定一个布点最少的计划。表49消防车在各区间行驶时间表单位：min地区地区1地区地区2地区地区3地区地
64、区4地区地区5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140解：引入01变量xi作决策变量，令本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表49可知，在地区1及地区2内设消防站都能达到此要求，即x1x21因此本问题的数学模型为：minzx1x2x3x4x5x6 x1x21x1x2x61x3x41x3x4x51x4x5x61x2x5x61xi1或0（i1，6）（五）指派问题（五）指派问题（Assignmentp
65、roblem）指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种问题：某单位有问题：某单位有m项任务要项任务要m个人去完成（每人只完成一项工作）个人去完成（每人只完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何，在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。引入派问题。引入01变量变量xij案例：福尔市场营销调查指派问题案例：福尔市场营销调查指派问题福尔市场营销调查公司有福尔市场营销调
66、查公司有3个新客户需要进行市场调查，个新客户需要进行市场调查，目前正好有目前正好有3个人没有其他工作，由于他们的对不同市场个人没有其他工作，由于他们的对不同市场的经验和能力不同，估计他们完成不同任务所需时间如的经验和能力不同，估计他们完成不同任务所需时间如下表。公司面临的问题是如何给每个客户指派一个项目下表。公司面临的问题是如何给每个客户指派一个项目主管（代理商），使他们完成市场调查的时间最短主管（代理商），使他们完成市场调查的时间最短。预计完成时间预计完成时间 客户客户项目主管项目主管1231231096151814953设设xij=1表示指派主管表示指派主管i完成第完成第j项市场调查，项市
67、场调查，否则否则xij=0则问题的数学模型为：则问题的数学模型为：minf=10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 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，3MODEL:SETS:SUPERVISOR/S1,S2,S3/;CUSTOMER/C1,C2,C3/;LINKS(SUPERVISOR,CUSTOMER):C,X;ENDSETSDATA:C=10,15,9,9,18,5
68、,6,14,3;ENDDATAMIN=SUM(LINKS:C*X);for(SUPERVISOR(I):SUM(CUSTOMER(J):X(I,J)=1);for(CUSTOMER(J):SUM(SUPERVISOR(I):X(I,j)=1);for(LINKS:bin(X);ENDGlobaloptimalsolutionfound.Objectivevalue:26.00000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostC(S1,C1)10.000000.000000C(S1,C2)15.00000
69、0.000000C(S1,C3)9.0000000.000000C(S2,C1)9.0000000.000000C(S2,C2)18.000000.000000C(S2,C3)5.0000000.000000C(S3,C1)6.0000000.000000C(S3,C2)14.000000.000000C(S3,C3)3.0000000.000000X(S1,C1)0.00000010.00000X(S1,C2)1.00000015.00000X(S1,C3)0.0000009.000000X(S2,C1)0.0000009.000000X(S2,C2)0.00000018.00000X(S2
70、,C3)1.0000005.000000X(S3,C1)1.0000006.000000X(S3,C2)0.00000014.00000X(S3,C3)0.0000003.000000多目标规划多目标规划一、多目标规划问题的提出一、多目标规划问题的提出多目标问题多目标问题多目标问题多目标问题是现实世界中普遍遇到的一类问是现实世界中普遍遇到的一类问题，其中希望（或必须）考虑多个相互矛盾目标题，其中希望（或必须）考虑多个相互矛盾目标的影响。的影响。例如证券投资问题中我们希望利润最大例如证券投资问题中我们希望利润最大而风险最小，生产销售问题中我们希望费用而风险最小，生产销售问题中我们希望费用较少而获
71、利很大，等等。较少而获利很大，等等。主要介绍：主要介绍：如何建立目标规划模型如何建立目标规划模型如何求解、分析结果如何求解、分析结果如何将求解结果与实际问题联系起来如何将求解结果与实际问题联系起来单目标模型只需简单确定一个目标，而将其单目标模型只需简单确定一个目标，而将其余的列为约束；余的列为约束；在构建多目标模型时，则需要对问题有较在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面深的理解，必须考虑更全面虽然费时较多，虽然费时较多，却非常有益，更切合实际。却非常有益，更切合实际。某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，已知有两种产品，已知有关数据如下表所示：
72、关数据如下表所示：拥有量原材料 kg2111设备台时 hr12 10利润 元/件810 解：这是一个单目标规划问题，可用线性规划模解：这是一个单目标规划问题，可用线性规划模型表述为：型表述为：试求获利最大的方案。试求获利最大的方案。例例1 1 利润最大化问题：利润最大化问题：目标函数目标函数maxz=8x1+10x2约束条件约束条件2x1+x211x1+2x210x1,x20可用图解法求得最优决策方案为：可用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62x1+2x2108x1+10x2=c6123452468102x1+x211从线性规划的角度来看，问题似乎已经从线性规划的角度来
73、看，问题似乎已经得到了圆满的解决得到了圆满的解决。但是，如果站在工厂计划人员的立场上对此但是，如果站在工厂计划人员的立场上对此进行评价的话，问题就不是这么简单了。进行评价的话，问题就不是这么简单了。第一第一，这是一个，这是一个单目标单目标最优化问题。但是，最优化问题。但是，一般来说，一个计划问题要满足多方面的要一般来说，一个计划问题要满足多方面的要求。例如求。例如财务部门财务部门利润目标：利润尽可能大利润目标：利润尽可能大物资部门物资部门节约资金：消耗尽可能小节约资金：消耗尽可能小销售部门销售部门适销对路：产品品种多样适销对路：产品品种多样计划部门计划部门安排生产：产品批量尽可能大安排生产：产
74、品批量尽可能大一个计划问题实际上是一个多目标决策问一个计划问题实际上是一个多目标决策问题。只是由于需要用线性规划来处理，计划人题。只是由于需要用线性规划来处理，计划人员才不得不从众多目标要求中硬性选择其一，员才不得不从众多目标要求中硬性选择其一，作为线性规划的目标函数作为线性规划的目标函数。但这样做的结果严重违背了某些部门的愿但这样做的结果严重违背了某些部门的愿望，因而使生产计划的实施受到影响；或者在望，因而使生产计划的实施受到影响；或者在一开始就由于多方面的矛盾而无法从多个目标一开始就由于多方面的矛盾而无法从多个目标中选出一个目标来。中选出一个目标来。例如，由于设备维修、能源供应、其它产品生
75、例如，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时产需要等原因，计划期内可以提供的设备工时不能满足计划产量不能满足计划产量工时工时需要需要。或由于或由于储备资金储备资金的限制，的限制，原材料原材料的最大供应的最大供应量不能满足计划量不能满足计划产量产量的需要的需要第二第二，线性规划有最优解的必要条件是其可行，线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但是，实解集非空，即各约束条件彼此相容。但是，实际问题有时不能满足这样的要求际问题有时不能满足这样的要求。近似性近似性建模时对实际问题的抽象建模时对实际问题的抽象建模时未考虑到的新情况建模时未考
76、虑到的新情况决策者需要计划人员提供的不是严格的数学决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的上的最优解，而是可以帮助做出最优决策的参考性的计划，或是提供多种计划方案参考性的计划，或是提供多种计划方案第三第三，线性规划解的可行性和最优性具有十分，线性规划解的可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言明确的意义，但那都是针对特定数学模型而言的。的。 在实际问题中，决策者在作决策时，往往在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性于数学模型相对
77、于实际问题的近似性1961年，查恩斯年，查恩斯(A.Charnes)和库柏和库柏(W.w.CooPer)提出目标规划提出目标规划(goalprogramming)，得到广泛重视，得到广泛重视和较快发展。和较快发展。目标规划在处理实际决策问题时，承认各项决目标规划在处理实际决策问题时，承认各项决策要求策要求(即使是冲突的即使是冲突的)的存在有其合理性；在作的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。最终决策时，不强调其绝对意义上的最优性。因此，目标规划被认为是一种较之线性规划更因此，目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具接近于实际决策过程的决策工具。现代
78、决策强调现代决策强调定量分析和定性分析定量分析和定性分析相结合，相结合，强调强调硬技术和软技术硬技术和软技术相结合，强调相结合，强调矛盾和冲突矛盾和冲突的合理性的合理性，强调，强调妥协和让步的必要性妥协和让步的必要性。线性规。线性规划无法胜任这些要求。划无法胜任这些要求。1.加权或效用系数法加权或效用系数法2.序列或优先级法序列或优先级法3.有效解（非劣解）法有效解（非劣解）法1.加权法：加权法：加权法加权法加权法加权法把问题中的所有目标用把问题中的所有目标用统一的单位统一的单位来度量（例来度量（例如用钱或效用系数）如用钱或效用系数）v这种方法的这种方法的核心核心是把多目标模型化成单目标模型。
79、是把多目标模型化成单目标模型。优点优点优点优点：适于计算机求解：适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）（例如模型是线性的时候可用一般的单纯形法求解） 缺点缺点缺点缺点：难处在于如何寻到合理的权系数。：难处在于如何寻到合理的权系数。2.序列或优先级法序列或优先级法：序列或优先级法序列或优先级法序列或优先级法序列或优先级法不是对每个目标加权，而是按照目标不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。的轻重缓急，将其分为不同等级再求解。优点优点优点优点：避免了权系数的困扰，绝大多数决策者都能采：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决
80、策中也正是这样做的。用，事实上他们在许多决策中也正是这样做的。例如建设高速公路时，既希望减少开支又希望降低交例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？值呢？例如决定人员的提升时，许多单位是按其工作态度、例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。进行评定的。即没有任何其他方案即没有任何其他方案能在各个方面完全胜能在各个方面完全胜出这个解出这个解 缺点缺点缺点缺点：难处在于如何确切地定出各个
81、目标的优先顺序：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。以获得满意的求解结果。3.有效解（或非劣解）法：有效解（或非劣解）法：有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法“不会产生不会产生”象加权法或优先象加权法或优先级法所具有的局限性，它将找出全部有效解集（即级法所具有的局限性，它将找出全部有效解集（即非非劣解劣解）以供决策者从中挑选。）以供决策者从中挑选。 缺点缺点缺点缺点：难处在于实际问题中非劣解太多，难于一一推：难处在于实际问题中非劣解太多，难于一一推荐给决策者。荐给决策者。二、多目标规划模型的建立及图解法二、多目标规划模型的建
82、立及图解法某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，已知有两种产品，已知有关数据如下表所示：关数据如下表所示：拥有量原材料 kg2111设备台时 hr1210利润 元/件810 解：这是一个单目标规划问题，可用线性规划模解：这是一个单目标规划问题，可用线性规划模型表述为：型表述为：试求获利最大的方案。试求获利最大的方案。例例1 1 利润最大化问题：利润最大化问题：目标函数目标函数maxz=8x1+10x2约束条件约束条件2x1+x211x1+2x210x1,x20可用图解法求得最优决策方案为：可用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62x1+2x210
83、8x1+10x2=c6123452468102x1+x211在实际决策时，还应考虑市场等一系列其他条件，如：在实际决策时，还应考虑市场等一系列其他条件，如：（1）市场调查发现：）市场调查发现：的销量有下降趋势，故应考虑适的销量有下降趋势，故应考虑适当减少当减少的产量增加的产量增加的产量，使的产量，使（2）原材料的价格不断上涨，增加供应会使成本提高。）原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料。故不考虑再购买原材料。（3）为提高效率，应充分利用设备，但不希望加班。）为提高效率，应充分利用设备，但不希望加班。（4）市场虽发生变化，但利润应尽可能达到或超过）市场虽发生变化，但利
84、润应尽可能达到或超过56元。元。此时的决策是此时的决策是多目标决策问题多目标决策问题多目标决策问题多目标决策问题目标规划方法目标规划方法是解决这类决策问题的方法之一是解决这类决策问题的方法之一。1. 1. 正、负偏差变量正、负偏差变量正、负偏差变量正、负偏差变量d d+ +,d,d- - d d+ + : : 决策值超过目标值的部分决策值超过目标值的部分 d d- - ：决策值未达到目标值的部分：决策值未达到目标值的部分 恒有恒有 d d+ +d d- -=0=0例如目标例如目标z=8x1+10x2可以变化为目标约束：可以变化为目标约束：8x1+10x2+d1-d1+56绝对约束绝对约束2x1
85、+x211可以变换为目标约束：可以变换为目标约束：2x1+x2+d2-d2+11一、与建立目标规划模型有关的概念一、与建立目标规划模型有关的概念硬约束硬约束软约束软约束2.绝对约束、目标约束绝对约束、目标约束绝对约束绝对约束绝对约束绝对约束：必须严格满足的等式或不等式约束：必须严格满足的等式或不等式约束目标约束目标约束目标约束目标约束：目标规划所特有的约束，约束右端项看作：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负要追求的目标值，在达到目标值时，允许发生正或负的偏差的偏差例如，原材料的价格不断上涨，增加供应会使成例如，原材料的价格不断上涨，增加供应会使成
86、本提高。故不考虑再购买原材料本提高。故不考虑再购买原材料从而从而2x1+x211是硬约束是硬约束3 . 3 . 优先因子与权系数优先因子与权系数 目标规划问题常常有多个目标，但这些目标的主目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。次或轻重缓急是不同的。 最重要的目标赋予优先因子最重要的目标赋予优先因子P1P1，次一级的目标赋，次一级的目标赋予优先因子予优先因子P2P2，并规定，并规定 P Pk kPPk+1k+1即表示即表示 P Pk k比比P Pk+1k+1有更大的优先权。有更大的优先权。 如果要区别具有相同优先因子的两个目标的差别，如果要区别具有相同优先因子的两个目标
87、的差别，则分别赋予它们不同的权系数则分别赋予它们不同的权系数w wj j。4 .4 .目标规划的目标函数目标规划的目标函数 min min z = = f (d,d)三种基本形式：三种基本形式：目标类型目标类型目标规划格式目标规划格式需要极小化需要极小化的偏差变量的偏差变量fi(x) bifi(x) dd bidfi(x) bifi(x) dd bidfi(x) bifi(x) dd biddd d+ + : : 决策值超过目标值的部分决策值超过目标值的部分2.2.产品产品的产量不低于产品的产量不低于产品的产量的产量1.1.原材料供应受严格限制原材料供应受严格限制2x1+x211硬约束硬约束x
88、1x2d1d10d1x1 x2极小化极小化例例2 2 例例1 1的目标规划模型：的目标规划模型：3.3.充分利用设备有效台时，不加班充分利用设备有效台时，不加班x12x2d2d210d2d2x12x210极小化极小化4.4.利润额不小于利润额不小于5656元元8x110x2d3d356d38x110x256极小化极小化【毕毕】1.建立基础模型建立基础模型2.为每一个为每一个理想目标理想目标确定期望值确定期望值3.对每一个对每一个现实目标现实目标和约束都加上正负偏差和约束都加上正负偏差变量变量4.将目标按其重要性划分优先级，第一优先将目标按其重要性划分优先级，第一优先级为硬约束级为硬约束5.建立
89、目标规划函数建立目标规划函数反映决策者欲望，反映决策者欲望，如如“利润最大利润最大”配上期望值配上期望值的理想目标的理想目标建模步骤小结：建模步骤小结：（一）、模型的一般形式（一）、模型的一般形式目标规划的数学模型目标规划的数学模型x1x2od1+d1-d2+d2-d3+d3-最优解为黄色线段上任一点最优解为黄色线段上任一点一般来说，目标期望值可调整以适应实际情况。一般来说，目标期望值可调整以适应实际情况。硬约束硬约束2x1+x211x1x2d1d10d1极小化极小化二、目标规划的图解法：二、目标规划的图解法：练习：练习：某单位领导在考虑本单位职工的升级调资方案某单位领导在考虑本单位职工的升级
90、调资方案时，依次遵守以下规定：时，依次遵守以下规定：1.不超过年工资总额不超过年工资总额60000元元2.每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数3.二、三级升级面尽可能达到现有人数的二、三级升级面尽可能达到现有人数的20%4.三级不足编制的人数可录用新职工，又一级三级不足编制的人数可录用新职工，又一级的职工中又的职工中又10%要退休要退休试据下表数据建立模型试据下表数据建立模型等级工资额(元/年)现有人数编制人数一20001012二15001215三10001515合计3742设设x1、x2、x3分别表示提升到一、二级和录用到三级的分别表示提升到一、二级和录用到三级的新职
91、工人数。各目标确定的优先因子为：新职工人数。各目标确定的优先因子为：P1不超过年工资总额不超过年工资总额60000元；元；P2每级的人数不超过定编制规定的人数每级的人数不超过定编制规定的人数P3二、三级的升级面尽可能达到现有人二、三级的升级面尽可能达到现有人数的数的20%接下来确定各目标约束接下来确定各目标约束参考模型如下：参考模型如下：年工资总额不超过年工资总额不超过60000元：元：2000(10-10*0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d d1 1 -d -d1 1+ +60000每级的人数不超过定编规定的人数：每级的人数不超过定编规定的人数：1
92、.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.2目标函数：目标函数：minz= P1 d P1 d1 1+ + + P2( d+ P2( d2 2+ + + d+ d3 3+ + + d+ d4 4+ + ) )+ P3( d+ P3( d
93、5 5- - + d+ d6 6- - ) )三、用三、用Lindo求解的方法求解目标规划求解的方法求解目标规划主要思想：化成单目标问题，多阶段求解主要思想：化成单目标问题，多阶段求解用用lindo求解步骤：求解步骤：1.模型中约束不变，只取第一优先级为目标函数模型中约束不变，只取第一优先级为目标函数注：在注：在lindo中输入时，中输入时，d3-可用可用d3minus表示，表示， d3-可用可用d3plus表示。表示。求出最优目标值为求出最优目标值为z d3- =0。2.只取第二优先级为目标函数，将上次求解结果只取第二优先级为目标函数，将上次求解结果的目标值的目标值d3- =0变为约束变为约
94、束求出最优目标值为求出最优目标值为z 2d1+3d2+=12。3.只取第三优先级为目标函数，将上次求解结果只取第三优先级为目标函数，将上次求解结果的目标值的目标值2d1+3d2+=12变为约束变为约束求解出最优目标值求解出最优目标值z=d4+=4，此时，此时x1=4，x2=12。OBJECTIVEFUNCTIONVALUE1)4.000000VARIABLEVALUEREDUCEDCOSTD4PLUS4.0000000.000000X14.0000000.000000X212.0000000.000000D1MINUS0.0000000.800000D1PLUS6.0000000.000000D2MINUS0.0000001.200000D2PLUS0.0000000.000000D3MINUS0.0000000.000000D3PLUS0.0000000.600000D4MINUS0.0000001.000000此时此时lindo求解结果如下：求解结果如下：
