第七讲 运筹学建模

1、,第七讲 运筹学模型,7.1 线性规划模型 (运输问题模型) 7.2 01型整数规划模型 7.3 目标规划模型 7.4 非线性规划问题,运筹学的分支较多，本章我们只介绍线性规划、整数规划、目标规划及非线性规划等方面的内容，重点讲解运筹学模型的分析和建立，模型的求解通常使用LINGO软件来完成., 1.运输问题模型概述 运输问题是一类特殊的线性规划模型，该模型的建立最初用于解决一个部门的运输网络所要求的最经济的运输路线和产品的调配问题，并取得了成功.然而，在实际问题的应用中，除运输问题外，许多非运输问题的实际问题一样可以建立其相应的运输问题模型，并由此而求出其最优解.下面以“产销平衡模型”为例对

2、运输问题进行简单的概括和描述.,7.1 运输问题模型,某产品的生产有m个产地Ai(i1，2，m)，其生产量分别为ai(i1，2，m)，而该产品的销售有n个销售地Bj(j1，2，n)，其需要量分别为bj(j1，2，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.,我们可把运输量xij(i1，2，m；j1，2，n)汇总于产销平衡表7-1中，而把单位运价cij(i1，2，m；j1，2，n)汇总于单位运价表7-2中.则在该

3、产销平衡表中，第j列的含义为：从各产地Ai(i1，2，m)发往销售地j的部分运输量x1j，x2j，xmj的和应等于销量bj，第i行的含义类同.,表 7-1,表 7-2,由以上的讨论，对产销平衡的情形，我们可给出其运输问题的数学模型如下： (7.1.1), 当然，在实际问题的应用中，常出现产销不平衡的情形，此时，需要把产销不平衡问题转化为产销平衡问题来进行讨论.例如当产量 大于销量 时，只需增加一个虚拟的销售地jn1，而该销售地的需要量为 即可.销量 大于产量 的情形类同.,2.应用实例 例1 生产时序的安排. (1)问题的提出. 北方飞机公司为全球各航空公司制造商用飞机.其生产过程之最后阶段为

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

5、引擎数，因公司必须完成合同，则xij应满足： (7.1.2),每月生产的用于当月和以后各月交货的引擎数不可能超过该公司的实际生产能力，xij应满足：, 下面构造“单位运价表”，它应等价于这里的“成本费用表”.因第i月生产并用于第j月交货的引擎数的实际成本cij应该是其生产单位成本再加上存储、维护费用，从而我们可得其“成本费用表”如表7-4所示.,表 7-4,由于这是产销不平衡问题，故增加一虚拟的销售地D，使之能构造为产销平衡模型，并把“产销平衡表和单位运价表”合二为一(见表7-5).在表7-5中，ai表示公司第i月的生产能力，bj表示第j月的合同供应量，cij表示相应的成本费用，因在实际问题中

6、，当ij时，xij0，故令相应的cijM.,表 7-5,(3)模型的建立与求解. 如上讨论，我们可给出“生产时序的安排”所对应的“运输问题模型”： (7.1.4),据此，我们可求出其最优解为： x1110， x1215， x235， x3320， x3410， x4410 相应的最小生产费用为： 今后四个月引擎数量的生产安排如表7-6所示.,表 7-6,7.2.1整数规划的定义和模型 1.整数规划的定义 在求解线性规划问题时,得到的最优解可能是分数或小数,但许多实际一要求得到的解为整数才行。这种要求线性规划有整数解的问题，称为整数规划（Integer programming)或简称IP。,7.

7、2 01型整数规划模型,2. 整数规划的分类 如不中特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为三类： 变量全限制为整数时，称纯（完全）整数规划。 变量部分限制为整数的，称混合整数规划。 变量只能取0或1时，称之为0-1整数规划。 本节重点介绍0-1整数规划。,3.整数规划的实例 例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如表7-7所示，问两种货物各装多少箱，可使获得利润最大？,解：设甲、乙两种货物装运箱数分别为X1和X2，显然X1和X2都要求为整数，最大利润为Z于是可建立整数规划模型如下： 注：是不是可通过把不考虑整数要求求得的最优

8、解经过“化整”得到满足整数要求的最优解呢？,此例可解得X1=8,X2=0,凑整为X1=5,X2=0,这就破坏了条件（1），因而不是可行解：如截断小数变为X1=4,X2=0,这当然满足所有约束条件，但不是最优解，因为对X1=4,X2=0有Z=80，而对X1=4,X2=1(也是可行解)有Z=90.因此这就要专门研究整数规划的解法。,4.整数规划的求解方法 （1）分枝定界法可求纯或混合整数线性规划。 （2）割平面法可求纯或混合整数线性规划 （3）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。 （4）匈牙利法解决指派问题（“0-1”规划特殊情形） （5）蒙特卡洛法求解各种类型规划。 这里

9、不一一介绍，感兴趣的同学再去查找相关资料。,7.2.2 01型整数规划问题 1. 01型整数规划模型概念 0-1型整数规划是整数规划中的特殊情形，它的变量仅取值0或1.这时称为0-1变量，或称二进制变量。仅取值0或1这个条件可由约束条件“且为整数”所代替，这是和一般整数规划的约束条件形式一致的。在一些问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。 在实际问题的讨论中，01型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实.,01型整数规划的数学模型为： 这里，0|1表示0或1.,2 . 01型整数规划模

10、型的解法 01型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量x1，x2，xn的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解.这种方法一般适用于决策变量个数n较小的情况.当n较大时，由于n个0、1的可能组合数为2n，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的.隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但对有些问题并不适用.,3. 应用实例 例1：选址问题 某公司拟在市东、南、西三区建立门市部。拟议中有7个位置（i=1,2,7）可供选择。规定：由A1、A2、A3三个点中至多选两个；在西区A4、A5两个点中至多选一个；在南区A6、A7两

11、个点中至多选一个。如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？,解：引入0-1变量， 令 于是建立下列模型：,例2：指派问题 有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们的将说明书译成不同文字所需的时间如表7-8所示。问应指派哪个人完成哪项工作，使所需的总时间最少？,解：一般地，有n项任务，n个完成人，第i人完成第j项任务的代价为 （i,j=1,2,，n).为了求得总代价最小的指派方案，引入0-1变量 ， 令 数学模型为：,例3 工程上马的决策问题. (1)问题的提出. 某部门三年内有四项工程可以考虑上

12、马，每项工程的期望收益和年度费用(千元)如表7-9所示.假定每一项已选定的工程要在三年内完成，试确定应该上马哪些工程，方能使该部门可能的期望收益最大.,表 7-9,(2)模型分析与变量的假设. 这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别用1、0表示，设： 因每一年的投资不超过所能提供的可用资金数，故该01型整数规划问题的约束条件为：,由于期望收益尽可能大，故目标函数为: max z20 x140 x220 x330 x4, (3)模型的建立与求解. 至此，我们得到该问题的01型整数规划模型为 max z20 x140 x220 x330

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

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

15、表 7-10,续表,注：在该表中，表示满足相应条件，表示不满足相应条件.,7.3.1 目标规划模型概述 1.相关的几个概念 1)正、负偏差变量d，d 正偏差变量d表示决策值xi(i1，2，n)超过目标值的部分；负偏差变量d表示决策值xi(i1，2，n)未达到目标值的部分.一般而言，正负偏差变量d，d的相互关系如下：,7.3 目标规划模型,当决策值xi(i1，2，n)超过规定的目标值时，d0，d0；当决策值xi(i1，2，n)未超过规定的目标值时，d0，d0；当决策值xi(i1，2，n)正好等于规定的目标值时，d0，d0.,2)绝对约束和目标约束 绝对约束是必须严格满足的等式约束或不等式约束，前

16、述线性规划中的约束条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量d、d来实现.,3)优先因子(优先级)与权系数 目标规划问题常要求许多目标，在诸多目标中，凡决策者要求第一位达到的目标赋予优先因子P1，要求第二位达到的目标赋予优先因子P2，并规定PkPk1，即Pk1级目标的讨论是在Pk级目标得以实现后才进行的(这里k1，2，n).若要考虑两个优先因子相同的目标的区别，则可通过赋予它们不同的权系数wj来完成.,2.目标规划模型的目标函数 目标规划的目标函数是根据各目标约束的正、负偏差变量d、d和其优

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

18、的一般形式为：,(7.3.1),7.3.2 目标规划模型举例 例1 某工厂的总生产能力为每天500小时，该厂生产A，B两种产品，每生产一件A产品或B产品均需一小时，由于市场需求有限，每天只有300件A产品或400件B产品可卖出去，每出售一件A产品可获利10元，每出售一件B产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产. (1)尽量避免生产能力闲置； (2)尽可能多地卖出产品，但对于能否多卖出A产品更感兴趣； (3)尽量减少加班时间.,解 模型的分析与建立： 显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的.对于这类问题，必须采用新的方法和

19、手段来建立对应的模型.,设x1，x2分别表示产品A，B的生产数量，d1表示生产能力闲置的时间，d1表示加班时间，d2表示产品A没能达到销售目标的数目，d3表示产品B没能达到销售目标的数目.因要求尽量避免生产能力闲置及尽量减少加班时间，故有目标约束条件： d1、d1要尽可能小，又要求尽可能多地卖出产品，故有目标约束条件：,d2、d3要尽可能小，多卖出A产品的要求可体现在目标函数的权系数中，于是可得到目标规划模型为: 满足的约束条件为： (7.3.2), 例2 职工的调资方案问题. (1)问题的提出. 某单位领导在考虑本单位职工的升级调资方案时，要求相关部门遵守以下的规定： 年工资总额不超过600

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

21、,下面再确定目标约束. 因为要求年工资总额不超过60000元，所以有： 且正偏差变量d1要尽可能小.又第二目标要求每级的人数不超过定编规定的人数，所以:,对于级，有 ，且正偏差变量d2要尽可能小； 对于级，有 ，且正偏差变量d3要尽可能小； 对于级，有 ，且正偏差变量d4要尽可能小； 对于第三目标，、级的升级面尽可能达到现有人数的20%，我们有下述约束：, (3)模型的建立. 由此，我们可得到该问题的目标规划模型为： 满足约束条件, 求解后可得到该问题的一个多重解，并将这些解汇总于表7-12中，以供领导根据具体情况进行决策.,表 7-12,例3 波德桑小姐是一个小学教师，她刚刚继承了一笔遗产，

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

23、： x1购买公债的投资额； x2购买信用卡的投资额； x3购买可兑换股票的投资额； x4对她侄子企业的投资额.,则得线性规划模型如下： , 如果用线性规划的单纯形法求解这个问题，就会发现这个问题无可行解，或者说这个问题“不可行”.只要检查一下第1、第2、第3和第6个约束，问题的不可行性是一目了然的.简而言之，波德桑小姐没有足够的钱来实现她的愿望. 然而，对于波德桑小姐来说，用线性规划得出的这样一个答案是不能使她满意的.而能够使她满意的是，她希望知道即使不可能绝对地满足她的全部愿望，那么怎样才能尽可能地接近于满足她的愿望？在这样一个更为实际的许可条件下，我们假定她的目标优先等级如下：,P1她的全

24、部投资额不允许超过50000美元，这是一个绝对约束； P2尽可能地满足：用20000美元购买公债，用500015000美元购买信用卡，她认为购买信用卡比购买公债重要2倍； P3尽可能资助她的侄子30000美元； P4尽可能用10000美元购买兑换股票，每年利息的总收入尽可能达到4000美元. 那么，可以建立这个问题的目标规划模型：, 求解这个目标规划问题，得到的满意解是： x120000， x25000， x30， x425000 因此，我们得到了一个有意义的解，这个解能够最好地满足(即使不能绝对地满足)波德桑小姐的全部目标.事实上，在实际的决策中，决策者的某些目标不可能完全达到，这本来也是很

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

26、(2)满足工厂3的全部需求的目标可以通过将上面的偏差变量d5的最小化列入第一级目标来反映. (3)满足工厂1、2的75的需求，可建立约束： (4)总运费要求最少，可建立约束：, (5)对工厂1特殊供应量的要求，可建立约束： (6)对工厂1、2的需求满足程度的平衡的要求，可表示为 得到约束： , (7)目标函数为: 综合以上分析，可得这个问题的目标规划模型为：, , 事实上，由于有了、两个约束条件，可以取消、两个约束条件.,7.4.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题.一般说来，解非线性规划要比解线性规划问题困难得多.非线性规划目前

27、还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围.下面通过实例给出非线性规划数学模型的一般形式以及基本概念.,7.4 非线性规划问题,例1 (投资决策问题)某企业有n个项目可供选择投资，并且至少要对其中一个项目投资.已知该企业拥有总资金A元，投资于第i(i1，n)个项目需花资金ai元，并预计可收益bi元.试选择最佳投资方案. 解 设投资决策变量为： (i1，n),则投资总额为 ，投资总收益为 .因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，故有限制条件： 另外，由于xi(i1，n)只取值0或1，所以还有 xi(1xi)0 (i1，n), 最佳投资方案应是投资额最

28、小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量(取0或1)的限制条件下，极大化总收益和总投资之比.因此，其数学模型为： (7.4.1) xi(1xi)0 (i1，n), 上面的例题是在一组等式或不等式的约束下，求一个函数的最大值(或最小值)问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题(NP)，可概括为一般形式： minf(x) s.t.hj(x)0 (j1，q) (NP) (6.4.2) gi(x)0 (i1，p) 其中xx1，xnT称为模型(NP)的决策变量，f称为目标函数，gi(i1，p)和hj(j1，q)称为约束函数.另外，gi

29、(x)0(i1，p)称为等式约束，,hj(x)0(j1，q)称为不等式约束.,对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： (1)确定供选方案.首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们. (2)提出追求目标.经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标.并且，运用各种科学和技术原理，把它表示成数学关系式. (3)给出价值标准.在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它.,(4)寻求限制条件.由于所追求的目标一般都要在一定的条件下取

30、得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示.,7.4.2 非线性规划的MATLAB解法 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到)；而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到. MATLAB中非线性规划的数学模型写成以下形式: (7.4.3),其中f(x)是标量函数，A、B、Aeq，Beq是相应维数的矩阵和向量，C(x)、Ceq(x)是非线性向量函数.,MATLAB中的命令是 XFMINCON(FUN，X0，A，B，Aeq，Beq，LB，UB，NONLCON，OPTIONS) 它的返回值是向量x，其中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无上界，则