《数学建模简明教程》课件第4章.ppt

1、1 1第四章第四章 运筹学模型运筹学模型4.1 线性规划模型线性规划模型4.2 运输问题模型运输问题模型4.3 目标规划模型目标规划模型4.4 01型整数规划模型型整数规划模型4.5 非线性规划问题非线性规划问题2 2运筹学的分支较多，本章我们只介绍线性规划、整数规划、目标规划及非线性规划等方面的内容，重点讲解运筹学模型的分析和建立，模型的求解通常使用LINGO软件来完成.3 31.线性规划模型举例线性规划模型举例例1 某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3.已知单位产品所需原料数量如表4-1所示，试制订出利润最大的生产计划.4.1 线性规划模型线性规划模型4 4 表 4

2、-15 5分析 设产品Qj的产量为xj个单位，j1，2，3，它们受到一些条件的限制.首先，它们不能取负值，即必须有xj0，j1，2，3；其次，根据题设，三种原料的消耗量分别不能超过它们的可用量，即它们又必须满足：(4.1.1)1223123231500248003252000 xxxxxxx6 6 我们希望在以上约束条件下，求出x1，x2，x3，使总利润z3x15x24x3达到最大，故求解该问题的数学模型为：(4.1.2)1231223123max35423150024800s.t.32520000(1,2,3)jzxxxxxxxxxxxj7 7 例例2 某公司长期饲养动物以供出售，已知这些动

3、物的生长对饲料中的蛋白质、矿物质、维生素这三种营养成分特别敏感，每个动物每天至少需要蛋白质70 g、矿物质3 g、维生素10 mg，该公司能买到五种不同的饲料，每种饲料1 kg所含的营养成分如表4-2所示，每种饲料1 kg的成本如表4-3所示，试为公司制定相应的饲料配方，以满足动物生长的营养需要，并使投入的总成本最低.8 8 表 4-29 9表表 4-310 10解解 设xj(j1，2，3，4，5)表示混合饲料中所含第j种饲料的数量(即决策变量)，因为每个动物每天至少需要蛋白质70 g、矿物质3 g、维生素10 mg，所以xj(j1，2，3，4，5)应满足这些约束条件.由上述讨论知，饲料配比问

4、题的线性规划模型为min z0.2x10.7x20.4x30.3x40.5x511 11使如下约束条件成立：(4.1.3)(xj0；j1，2，3，4，5)1234512345123450.32.01.00.61.870s.t.0.10.050.020.20.083 0.050.10.020.20.0810 xxxxxxxxxxxxxxx12 122.线性规划线性规划(LP)问题解的概念问题解的概念一般线性规划问题的数学模型的标准形式为：(目标函数)(约束条件)njjjxcz1minnjijijmibxa1),2,1(s.t.13 13 可行解：满足约束条件的解x(x1，x2，xn)，称为线性规

5、划问题的可行解，而使目标函数达到最小值的可行解叫最优解.可行域:所有可行解构成的集合称为问题的可行域，记为R.14 143.线性规划问题的图解法线性规划问题的图解法例例3 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元.生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时.若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，则该厂应生产甲、乙机床各几台，才能使总利润最大？15 15经分析可建立该问题的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1，x2应

6、满足max z4000 x13000 x2(4.1.4)12122122108s.t.7,0 xxxxxx x16 16 图解法简单直观，有助于了解线性规划问题求解的基本原理.我们先应用图解法来求解例3.如图4-1所示，阴影区域即为LP问题的可行域R.对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一簇平行直线.让等位线沿目标函数值增加的方向移动，直到等位线与可行域有交点的最后位置，此时的交点(一个或多个)即为LP的最优解.17 17图 4-118 18对于例3，显然等位线越趋于右上方，其上的点具有越大的目标函数值.不难看出，本例的最优解为x*(2，

7、6)，最优目标值z*26.19 19从上面的图解过程可以看出并不难证明以下断言：(1)可行域R可能会出现多种情况.R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集(除非遇到空间维数的退化).R既可能是有界区域，也可能是无界区域.(2)在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解(其目标函数值无界).(3)R非空且LP有有限最优解时，最优解可以唯一或有无穷多个.(4)若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”.20204.其它形式的线性规划问题其它形式的线性规划问题除了线性规划问题的标准形式之外，还有其它形式的线性规划问题，

8、但这些问题都可以通过一些简单代换化为标准线性规划问题.1)极大化问题对于目标函数为极大化问题，如 ，可以将其等价地化为极小化问题，因为1maxnjjjzc x11maxminnnjjjjjjc xc x 21 212)不等式约束问题对于形如aj1x1aj2x2ajnxnbj的不等式约束，可以通过引入所谓“松弛变量rj”化为等式约束aj1x1aj2x2ajnxnrjbj(其中rj0)2222而对于形如aj1x1aj2x2ajnxnbj的不等式约束，可以通过引入所谓“剩余变量sj”化为等式约束aj1x1aj2x2ajnxnsjbj(其中sj0)23233)无非负条件问题对于变量xj无非负约束条件问

9、题，可以定义从而将其化为非负约束.212,0,0,jjjxxx 1jjxx24245.线性规划的线性规划的MATLAB解法解法单纯形法是求解线性规划问题最常用、最有效的算法之一.单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念.由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点.基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止.这里我们不再详细介绍单纯形法，有兴趣的读者可以

10、参看其它线性规划书籍.下面我们介绍线性规划的MATLAB解法.2525MATLAB中线性规划的标准型为：min xcTx s.t.Axb基本函数形式为linprog(c，A，b)，它的返回值是向量x的值.还有其它的一些函数调用形式(在MATLAB指令窗口运行helplinprog可以看到所有的函数调用形式)，如：x，fvallinprog(c，A，b，Aeq，beq，LB，UB，x0，OPTIONS)2626这里fval返回目标函数的值，Aeq和beq对应等式约束Aeq*xbeq，LB和UB分别是变量x的下界和上界，x0是x的初始值，OPTIONS是控制参数.2727例例4 求解下列线性规划问

11、题：max z2x13x25x3(4.1.5)解解 编写M文件c2；3；5；a2，5，1；b10；aeq1，1，1；1231231237s.t.2510,0 xxxxxxx x x2828beq7；xlinprog(c，a，b，aeq，beq，zeros(3，1)valuec*x将文件M存盘，并命名为example1.m.在MATLAB指令窗运行example1即可得所求结果.2929例例5 求解线性规划问题:min z2x13x2x312312123428s.t.326,0 xxxxxx x x3030 解解 编写MATLAB程序如下：c2；3；1；a1，4，2；3，2，0；b8；6；x，y

12、linprog(c，a，b，zeros(3，1)31 311.运输问题模型概述运输问题模型概述运输问题是一类特殊的线性规划模型，该模型的建立最初用于解决一个部门的运输网络所要求的最经济的运输路线和产品的调配问题，并取得了成功.然而，在实际问题的应用中，除运输问题外，许多非运输问题的实际问题一样可以建立其相应的运输问题模型，并由此而求出其最优解.下面以“产销平衡模型”为例对运输问题进行简单的概括和描述.4.2 运输问题模型运输问题模型3232某产品的生产有m个产地Ai(i1，2，m)，其生产量分别为ai(i1，2，m)，而该产品的销售有n个销售地Bj(j1，2，n)，其需要量分别为bj(j1，2

13、，n).已知该产品从产地Ai(i1，2，m)到销售地Bj(j1，2，n)的单位运价为cij(i1，2，m；j1，2，n)，试建立该运输问题的线性规划模型.假设从产地Ai(i1，2，m)到销售地Bj(j1，2，n)的运输量为xij.3333我们可把运输量xij(i1，2，m；j1，2，n)汇总于产销平衡表4-4中，而把单位运价cij(i1，2，m；j1，2，n)汇总于单位运价表4-5中.则在该产销平衡表中，第j列的含义为：从各产地Ai(i1，2，m)发往销售地j的部分运输量x1j，x2j，xmj的和应等于销量bj，第i行的含义类同.3434 表表 4-43535 表表 4-53636由以上的讨论

14、，对产销平衡的情形，我们可给出其运输问题的数学模型如下：(4.2.1)11min Z=mnijijijc x11 1,2,s.t.1,2,0mijjinijijijxbjnxaimx3737 当然，在实际问题的应用中，常出现产销不平衡的情形，此时，需要把产销不平衡问题转化为产销平衡问题来进行讨论.例如当产量大于销量时，只需增加一个虚拟的销售地jn1，而该销售地的需要量为即可.销量大于产量的情形类同.1miia1niib11mniiiiab1niib1miia38382.应用实例应用实例例例1 生产时序的安排.(1)问题的提出.北方飞机公司为全球各航空公司制造商用飞机.其生产过程之最后阶段为生产

15、喷射引擎，然后装置于制成的机体，该公司有若干近期必须交付使用的合同，现需安排今后四个月飞机喷射引擎的生产计划，并需于每月末分别提供10、15、25、20台引擎.已知该公司各月的生产能力和生产每台引擎的成本如表4-6所示，又如果生产出来的引擎当月不能交货的，每台引擎每积压一个月需存储和维护费用0.015百万元，试在完成合约的情况下，制定一引擎数量的生产安排方案，以使该公司今后四个月的生产费用最小.3939 表表 4-64040 (2)模型分析与变量的假设.用运输问题模型求该问题最优解的关键在于怎样建立该问题的产销平衡表及元素xij和单位运价表及元素cij.为此，我们假设xij表示第i月生产并用于

16、第j月交货的引擎数，因公司必须完成合同，则xij应满足：(4.2.2)11122213233314243444 10 15 2520 xxxxxxxxxx41 41每月生产的用于当月和以后各月交货的引擎数不可能超过该公司的实际生产能力，xij应满足：11121314222324344444 25 35 (4.2.3)30 10 xxxxxxxxxx4242 下面构造“单位运价表”，它应等价于这里的“成本费用表”.因第i月生产并用于第j月交货的引擎数的实际成本cij应该是其生产单位成本再加上存储、维护费用，从而我们可得其“成本费用表”如表4-7所示.4343表 4-74444 由于这是产销不平衡

17、问题，故增加一虚拟的销售地D，使之能构造为产销平衡模型，并把“产销平衡表和单位运价表”合二为一(见表4-8).在表4-8中，ai表示公司第i月的生产能力，bj表示第j月的合同供应量，cij表示相应的成本费用，因在实际问题中，当ij时，xij0，故令相应的cijM.4545表 4-84646 (3)模型的建立与求解.如上讨论，我们可给出“生产时序的安排”所对应的“运输问题模型”：(4.2.4)4411min=ijijijzc x4141 s.t.0ijijiiijijjjijc xac xbx4747据此，我们可求出其最优解为：x1110，x1215，x235，x3320，x3410，x4410

18、相应的最小生产费用为：今后四个月引擎数量的生产安排如表4-9所示.4411min=77.3ijijijzc x4848 表 4-949494.3.1 目标规划模型概述目标规划模型概述1.相关的几个概念相关的几个概念1)正、负偏差变量d，d正偏差变量d表示决策值xi(i1，2，n)超过目标值的部分；负偏差变量d表示决策值xi(i1，2，n)未达到目标值的部分.一般而言，正负偏差变量d，d的相互关系如下：4.3 目标规划模型目标规划模型5050当决策值xi(i1，2，n)超过规定的目标值时，d0，d0；当决策值xi(i1，2，n)未超过规定的目标值时，d0，d0；当决策值xi(i1，2，n)正好等

19、于规定的目标值时，d0，d0.51 512)绝对约束和目标约束绝对约束是必须严格满足的等式约束或不等式约束，前述线性规划中的约束条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量d、d来实现.52523)优先因子(优先级)与权系数目标规划问题常要求许多目标，在诸多目标中，凡决策者要求第一位达到的目标赋予优先因子P1，要求第二位达到的目标赋予优先因子P2，并规定PkPk1，即Pk1级目标的讨论是在Pk级目标得以实现后才进行的(这里k1，2，n).若要考虑两个优先因子相同的目标的区别，则可通过赋予它们不

20、同的权系数wj来完成.53532.目标规划模型的目标函数目标规划模型的目标函数目标规划的目标函数是根据各目标约束的正、负偏差变量d、d和其优先因子来构造的.一般而言，当每一目标值确定后，我们总要求尽可能地缩小决策值与目标值的偏差，故目标规划的目标函数只能是min zf(d，d)的形式.我们可将其分为以下三种情形：5454(1)当决策值xi(i1，2，n)要求恰好等于规定的目标值时，这时正、负偏差变量d、d+都要尽可能小，即对应的目标函数为:min zf(dd)5555 (2)当决策值xi(i1，2，n)要求不超过规定的目标值时，这时正偏差变量d要尽可能小，即对应的目标函数为:min zf(d)

21、5656 (3)当决策值xi(i1，2，n)要求超过规定的目标值时，这时负偏差变量d要尽可能小，即对应的目标函数为:min zf(d)目标规划数学模型的一般形式为：11min()LKllkklkklkzPw dw d5757 (4.3.1)11,(1,2,)(=,),(1,2,)s.t.0,(1,2,),0,(1,2,)njkjjkkkkjnijjijjkkc xddgkk ga xb imxjnddkK为相应的目标值58584.3.2 目标规划模型举例目标规划模型举例例例1 某工厂的总生产能力为每天500小时，该厂生产A，B两种产品，每生产一件A产品或B产品均需一小时，由于市场需求有限，每天

22、只有300件A产品或400件B产品可卖出去，每出售一件A产品可获利10元，每出售一件B产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产.(1)尽量避免生产能力闲置；(2)尽可能多地卖出产品，但对于能否多卖出A产品更感兴趣；(3)尽量减少加班时间.5959解解 模型的分析与建立：显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的.对于这类问题，必须采用新的方法和手段来建立对应的模型.6060设x1，x2分别表示产品A，B的生产数量，d1表示生产能力闲置的时间，d1表示加班时间，d2表示产品A没能达到销售目标的数目，d3表示产品B没能达到销售目标

23、的数目.因要求尽量避免生产能力闲置及尽量减少加班时间，故有目标约束条件：d1、d1要尽可能小，又要求尽可能多地卖出产品，故有目标约束条件：1211500 xxdd1223300,400 xdxd61 61d2、d3要尽可能小，多卖出A产品的要求可体现在目标函数的权系数中，于是可得到目标规划模型为:满足的约束条件为：(4.3.2)11222331min 2PdPdPdPd12111213121231500300.400,0 xxddxdstxdx x dddd6262 例例2 职工的调资方案问题.(1)问题的提出.某单位领导在考虑本单位职工的升级调资方案时，要求相关部门遵守以下的规定：年工资总额

24、不超过60000元；每级的人数不超过定编规定的人数；、级的升级面尽可能达到现有人数的20%；级不足编制的人数可录用新职工，又级的职工中有10%的人要退休.相关资料汇总于表4-10中，试为单位领导拟定一个满足要求的调资方案.6363 表 4-106464 (2)模型分析与变量假设.显然这是一个多目标规划的决策问题，适于用目标规划模型求解，故需要确定该问题与之对应的决策变量、目标值、优先等级及权系数等.设x1，x2，x3分别表示提升到、级和录用到级的新职工人数，由题设要求可确定各目标的优先因子如下：P1年工资总额不超过60000元；P2每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有

25、人数的20%.6565下面再确定目标约束.因为要求年工资总额不超过60000元，所以有：且正偏差变量d1要尽可能小.又第二目标要求每级的人数不超过定编规定的人数，所以:11223112000(10 10 10%)1500(12)1000(15)60000 xxxxxdd6666对于级，有，且正偏差变量d2要尽可能小；对于级，有，且正偏差变量d3要尽可能小；对于级，有，且正偏差变量d4要尽可能小；对于第三目标，、级的升级面尽可能达到现有人数的20%，我们有下述约束：12210(10.1)12xdd12331215xxdd23441515xxdd15526612 20%15 20%xddxdd67

26、67 (3)模型的建立.由此，我们可得到该问题的目标规划模型为：满足约束条件112234356min()()zPdP dddP dd)6,5,4,3,2,1;3,2,1(0,34.20336000)15(1000)12(1500)9(2000662551443233212211132211jiddxddxddxddxxddxxddxddxxxxxjji6868 求解后可得到该问题的一个多重解，并将这些解汇总于表4-11中，以供领导根据具体情况进行决策.6969表表 4-117070例例3 波德桑小姐是一个小学教师，她刚刚继承了一笔遗产，交纳税金后净得50000美元.波德桑小姐感到她的工资已足够

27、她每年的日常开支，但是还不能满足她暑假旅游的计划.因此，她打算把这笔遗产全部用去投资，利用投资的年息资助她的旅游.她的目标当然是在满足某些限制的条件下进行投资，使这些投资的年息最大.波德桑小姐的目标优先等级是：第一，她希望至少投资20000美元去购买年息为6的政府公债；第二，她打算最少用5000美元，至多用15000美元购买利息为5的信用卡；第三，她打算最多用10000美元购买随时可兑换现款的股票，这些股票的平均利息为8；第四，她希望给她的侄子的新企业至少投资30000美元，她侄子允诺给她7的利息.71 71解解 模型的分析与建立过程如下：设：设：x1购买公债的投资额；x2购买信用卡的投资额；

28、x3购买可兑换股票的投资额；x4对她侄子企业的投资额.7272则得线性规划模型如下：0,30000100001500050002000050000.t.s07.008.005.006.0max43214322143214321xxxxxxxxxxxxxxxxxz7373 如果用线性规划的单纯形法求解这个问题，就会发现这个问题无可行解，或者说这个问题“不可行”.只要检查一下第1、第2、第3和第6个约束，问题的不可行性是一目了然的.简而言之，波德桑小姐没有足够的钱来实现她的愿望.然而，对于波德桑小姐来说，用线性规划得出的这样一个答案是不能使她满意的.而能够使她满意的是，她希望知道即使不可能绝对地满

29、足她的全部愿望，那么怎样才能尽可能地接近于满足她的愿望？在这样一个更为实际的许可条件下，我们假定她的目标优先等级如下：7474P1她的全部投资额不允许超过50000美元，这是一个绝对约束；P2尽可能地满足：用20000美元购买公债，用500015000美元购买信用卡，她认为购买信用卡比购买公债重要2倍；P3尽可能资助她的侄子30000美元；P4尽可能用10000美元购买兑换股票，每年利息的总收入尽可能达到4000美元.那么，可以建立这个问题的目标规划模型：75750)6,2,1(,),4,3,2,1(400007.008.005.006.0300001000015000500020000500

30、00.)()22(max774321664553442332221114321475463432211kddjxddxxxxddxddxddxddxddxddxxxxtsxddPdPdddPdPzkkj7676 求解这个目标规划问题，得到的满意解是：x120000，x25000，x30，x425000 因此，我们得到了一个有意义的解，这个解能够最好地满足(即使不能绝对地满足)波德桑小姐的全部目标.事实上，在实际的决策中，决策者的某些目标不可能完全达到，这本来也是很自然的事情.7777例例4 一个公司需要从两个仓库调拨同一种零部件给下属的三个工厂.每个仓库的供应能力，每个工厂的需求数量以及从每个

31、仓库到每个工厂之间的单位运费如表4-12所示(表中方格内的数字为单位运费).7878表表 4-127979公司提出的目标要求是：P1尽量满足工厂3的全部需求；P2其他两个工厂的需求分别至少满足75；P3总运费要求最少；P4仓库2给工厂1的供应量至少为1000单位；P5工厂1和工厂2的需求量满足程度尽可能平衡.试建立这个问题的目标规划模型.8080解 设xij(i1，2；j1，2，3)表示仓库i调运到工厂j的零部件数量.约束条件与目标函数的建立过程如下：(1)供应与需求约束：400015002000400030005523134422123321112223222111131211ddxxddx

32、xddxxddxxxddxxx81 81(2)满足工厂3的全部需求的目标可以通过将上面的偏差变量d5的最小化列入第一级目标来反映.(3)满足工厂1、2的75的需求，可建立约束：(4)总运费要求最少，可建立约束：11251500772212662111ddxxddxx03108124108232221131211dxxxxxx8282 (5)对工厂1特殊供应量的要求，可建立约束：(6)对工厂1、2的需求满足程度的平衡的要求，可表示为得到约束：10009921ddx1500200022122111xxxx04343101022211211ddxxxx8383 (7)目标函数为:综合以上分析，可得这

33、个问题的目标规划模型为：)()(min10105948376251ddPdPdPddPdPz848410,2,10,32121004343100003108124101125150040001500200040003000.t.s)()(min10102221121199218232221131211772212662111552313442212332111222322211113121110105948376251ldd,jixddxxxxddxdxxxxxxddxxddxxddxxddxxddxxddxxxddxxxddPdPdPddPdPzllij，；，8585 事实上，由于有了、两个

34、约束条件，可以取消、两个约束条件.86864.4.1 01型整数规划模型概述型整数规划模型概述整数规划是决策变量为非负整数值的一类线性规划.在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分支定界解法及割平面解法(这里不作介绍，感兴趣的读者可参考相关书籍).4.4 01型整数规划模型型整数规划模型8787在整数规划问题中，01型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1.在实际问题的讨论中，01型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实.01型整数规划的数学模型为：1 122

35、max(min)nnzc xc xc x8888 (4.4.1)这里，0|1表示0或1.11 11221121 1222221 12212(,)(,)s.t.(,),0|1nnnnmmmnnmna xa xa xba xa xa xba xaxaxbx xx 89894.4.2 01型整数规划模型的解法型整数规划模型的解法01型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量x1，x2，xn的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解.这种方法一般适用于决策变量个数n较小的情况.当n较大时，由于n个0、1的可能组合数为2n，故此时即便用计算机进行穷举来求最优解，

36、也几乎是不可能的.隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但对有些问题并不适用.90904.4.3 应用实例应用实例例例1 工程上马的决策问题.(1)问题的提出.某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用(千元)如表4-13所示.假定每一项已选定的工程要在三年内完成，试确定应该上马哪些工程，方能使该部门可能的期望收益最大.91 91表 4-139292 (2)模型分析与变量的假设.这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别用1、0表示，设：因每一年的投资不超过所能提供的可用资金数，故该01型整数规

37、划问题的约束条件为：0,(1,2,3,4)jjjxj决定不投资第 个项目决定投资第个 项目1，9393由于期望收益尽可能大，故目标函数为:max z20 x140 x220 x330 x412341234123412345438187962281021024,0|1xxxxxxxxxxxxx x x x9494 (3)模型的建立与求解.至此，我们得到该问题的01型整数规划模型为max z20 x140 x220 x330 x4约束条件为:1234123412341234543818 79622 81021024 ,0|1xxxxxxxxxxxxx x x x9595 下面用隐枚举法求其最优解.

38、易知，该01型整数规划模型有一可行解(0，0，0，1)，它对应的目标函数值为z30.自然，该模型的最优解所对应的目标函数值应不小于30，于是，我们增加一过滤条件为：20 x140 x220 x330 x430在此过滤条件(过滤条件可不唯一)下，用隐枚举法求01型整数规划模型的最优解的步骤为：9696先判断第一枚举点所对应的目标函数值是否满足过滤条件，若不满足，则转下一步；若满足，再判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z1(本例中，z130)作为新的目标值，并修改过滤条件为：20 x140 x220 x330 x4z1再转下

39、一步.9797再判断第二枚举点所对应的目标函数值是否满足新的过滤条件，若不满足，则转下一步；若满足，接着判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z2(z2z1)作为新的目标值，并修改过滤条件为：20 x140 x220 x330 x4z2再转下一步.9898重复步骤，直至所有的枚举点均比较结束为止.由隐枚举法的求解步骤我们可给出该问题的求解过程如表4-14所示，并得到最优解为x1，x2，x3，x4(0，1，1，1)，相应的目标值为90(千元).故应上马的工程为2号、3号、4号工程.9999表表 4-14100100续表注：在该

40、表中，表示满足相应条件，表示不满足相应条件.1011014.5.1 非线性规划的实例与定义非线性规划的实例与定义如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题.一般说来，解非线性规划要比解线性规划问题困难得多.非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围.下面通过实例给出非线性规划数学模型的一般形式以及基本概念.4.5 非线性规划问题非线性规划问题102102例例1(投资决策问题)某企业有n个项目可供选择投资，并且至少要对其中一个项目投资.已知该企业拥有总资金A元，投资于第i(i1，n)个项目需花资金ai元，并预计可收益bi元.试选择最佳

41、投资方案.解解 设投资决策变量为：(i1，n)1,0iiix决定投资第 个项目决定不投资第 个项目，103103则投资总额为，投资总收益为.因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，故有限制条件：另外，由于xi(i1，n)只取值0或1，所以还有 xi(1xi)0(i1，n)niiixa1niiixb1niiiAxa10104104 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量(取0或1)的限制条件下，极大化总收益和总投资之比.因此，其数学模型为：(4.5.1)xi(1xi)0(i1，n)niiiniiixaxbQ11ma

42、x1s.t.0niiia xA105105 上面的例题是在一组等式或不等式的约束下，求一个函数的最大值(或最小值)问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题(NP)，可概括为一般形式：minf(x)s.t.hj(x)0(j1，q)(NP)(4.5.2)gi(x)0(i1，p)其中xx1，xnT称为模型(NP)的决策变量，f称为目标函数，gi(i1，p)和hj(j1，q)称为约束函数.另外，gi(x)0(i1，p)称为等式约束，106106hj(x)0(j1，q)称为不等式约束.107107对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：

43、(1)确定供选方案.首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们.(2)提出追求目标.经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标.并且，运用各种科学和技术原理，把它表示成数学关系式.(3)给出价值标准.在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它.108108(4)寻求限制条件.由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示.1091094.5.2 非线性规划的

44、非线性规划的MATLAB解法解法如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到)；而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到.MATLAB中非线性规划的数学模型写成以下形式:(4.5.3)(minxfAeqBeqs.t.()0Ceq()0 xxC xxAB110110其中f(x)是标量函数，A、B、Aeq，Beq是相应维数的矩阵和向量，C(x)、Ceq(x)是非线性向量函数.111111MATLAB中的命令是 XFMINCON(FUN，X0，A，B，Aeq，Beq，LB，UB，NONLCON，OPTIONS)它的返回值是向量x，

45、其中FUN是用M文件定义的函数f(x)；x0是x的初始值；A，B，Aeq，Beq定义了线性约束A*xB，Aeq*xBeq，如果没有等式约束，则A，B，Aeq，Beq；LB和UB是变量x的下界和上界，如果上界和下界没有约束，则LB，UB，如果x无下界，则LBinf，如果x无上界，则UBinf；NONLCON是用M文件定义的非线性向量函数C(x)；Ceq(x)；112112OPTIONS定义了优化参数，可以使用MATLAB缺省的参数设置.113113例例2 求解下列非线性规划问题:.0,0208)(min212212212221xxxxxxxxxf114114 (1)编写M文件fun1.m和M文件

46、fun2.m.functionffun1(x)；fx(1)2x(2)28；functiong，hfun2(x)；gx(1)2x(2)；hx(1)x(2)22；%等式约束115115(2)在MATLAB的命令窗口依次输入下列内容：optionsoptimset；x，yfmincon(fun1，rand(2，1)，zeros(2，1)，.fun2，options)就可以求得当x11，x21时的最小值y10.116116例例3 飞行管理问题.在约10000m高空的某边长160km的正方形区域内，经常有若干架飞机作水平飞行.区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理.当一架欲

47、进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞.如果会碰撞，则应计算如何调整各架飞机(包括新进入的)的飞行方向角，以避免碰撞.现假定条件如下：(1)不碰撞的标准为任意两架飞机的距离大于8 km；(2)飞机飞行方向角调整的幅度不应超过30；117117(3)所有飞机飞行速度均为每小时800 km；(4)进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60 km以上；(5)最多需考虑6架飞机；(6)不必考虑飞机离开此区域后的状况.请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算(方向角误差不超过0.01)，要求飞机飞

48、行方向角调整的幅度尽量小.设该区域4个顶点的坐标为(0，0)，(160，0)，(160，160)，(0，160).记录数据如下：118118 注：方向角指飞行方向与x轴正向的夹角.119119解解(xi(t)xj(t)2(yi(t)yj(t)2641in1，i1jn，0tminTi，Tj其中n为飞机的总架数，(xi(t)，yi(t)为t时刻第i架飞机的坐标，Ti，Tj分别表示第i，j架飞机飞出正方形区域边界的时刻.这里:iiivtxtxcos)0()(iiivtytysin)0()(),2,1(ni120120其中v为飞机的速度，0i，i分别为第i架飞机的初始方向角和调整后的方向角.令：li，

49、j(xi(t)xj(t)2(yi(t)yj(t)264at2btc其中，iii06|i),2,1(ni2sin422jiva121121则两架飞机不碰撞的条件是b24ac0.)sin)(sin0()0()0()0(2jijijiyyxxvb64)0()0()0()0(22jijiyyxxc122122例例4 钢管订购和运输问题.要铺设一条A1A2A15的输送天然气的主管道，如图4-2所示.经筛选后可以生产这种主管道钢管的钢厂有S1，S2，S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数

50、字表示里程(单位km).123123图 4-2124124为方便计，1 km主管道钢管称为1单位钢管.一个钢厂如果承担制造这种钢管，至少需要生产500个单位.钢厂Si在指定期限内能生产该钢管的最大数量为si个单位，钢管出厂销售价为1单位钢管pi万元，如下表：1单位钢管的铁路运输价如下表：125125 1000 km以上每增加1100 km运输价增加5万元.公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算).钢管可由铁路、公路运往铺设地点(不只是运到点A1，A2，A15，而是管道全线).126126(1)请制订一个主管道钢管的订购和运输计划，使总费用最小(给出总费用).(2)