第一讲线性规划与非线性规划

1、第一部分：优化模型第一部分：优化模型1、线性规划模型（算法：单纯形法）2、整数规划模型（算法：分枝定界法）3、非线性规划模型（化为线性规划求解）4、动态规划模型（算法：递归算法）5、多目标规划模型（化为线性规划求解）一、线性规划模型一、线性规划模型线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？用线性规划方法解决问题一般按下列步骤进行第一步：建立线性规划模型；第二步：用单纯形算法进行求解；第三步：对求解结果进行检验；第四步：将求解结果形成优化方案，付诸实施；线性规划模型一般包括

2、三个要素： （1）决策变量 （2）目标函数 （3）约束条件线性规划的一般形式为：线性规划的一般形式为： max(或或min)z=c1x1+c2x2+cnxn 0,),(),(),(.2122212222222111212211nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats （1.1) （1.2)（1.3)或紧缩形式max(或min)z=njjjxc10),.,2 , 1(),(.1jnjijjxmibxats或矩阵形式或向量形式： max(或min)z=cx),.,2 , 1(0),(.1njXbxptsjnjjj其中c=(c1,c2,cn)，称为价值系数向量；aa

3、aaaaaaamn2m1mn22221n11211A称为技术系数矩阵(也称消耗系数矩阵) 0Xb),(AXt . scxzmin)max( 或m21bbbb称为资源限制向量, X=(x1,x2,xn)T称为决策变量向量下面我们来看几个实际例子。案例1课本P60 例25（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年

4、的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？ 解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3; j=1,2,3,4年份 一 二 三 四 x11 1.15x11 x12 1.45x12 x21 1.15x21 x23 1.65x23 x31 1.15x31 x34 1.35x34（2）确定目标函数：第三年年未的本利和为 maxz=1.65x23+1.15x31+1.35x34 （3）确定约束条件：每一年的投资额应等于当年公司拥有的

5、资金数：x11+x12=3x21+x23=1.15x11 x31+x34=1.45x12+1.15x21 每个方案投资额的限制：x122x231.5 非负约束：xij0,i=1,2,3;j=1,2,3,4 x341案例案例5 （合理下料问题）要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？ 解：问题分析：一根长度为7.4米的园钢，要裁出2.9米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示： 下料 方案 根数 一 二 三

6、 四 五 六 七 八 长度米 2.9 1 1 1 2 0 0 0 0 2.1 2 0 1 0 1 2 3 0 1.5 0 3 1 1 3 2 0 4 合计 7.1 7.4 6.5 7.3 6.6 7.2 6.3 6 料头（米） 0.3 0 0.9 0.1 0.8 0.2 1.1 1.4 （1） 确定决策变量：设xj表示按第j种方案所用的园钢的数量（2） 确定目标函数：问题要求所用原料最省，所用原料为： minz=x1+x2+x3+x4+x5+x6+x7+x8（3） 确定约束条件： 2.9米园钢的数量限制 x1+x2+x3+2x4100 2.1米园钢的数量限制 2x1+x3+x5+2x6+3x7

7、100 1.5米园钢的数量限制 3x2+x3+x4+3x5+2x6+4x3100 非负限制 xj0，且为整数， j=1,2,8 建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。案例案例6一个木材储运公司有很大的仓库用以储运出售木一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为已知该公司仓库的最大储存量为2000万米万米3，储存费用为，储

8、存费用为（70+100u）千元）千元/万米万米3，u为存储时间（季度数）。已知为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。每季度的买进卖出价及预计的销售量如下表所示。 季度季度买进价（万元买进价（万元/万米万米3） 卖出价（万元卖出价（万元/万米万米3） 预计销售量（万米预计销售量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋4504551600由于木材不宜久贮，所有库存木材应于每年秋末售完。为由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。使售后利润最大，试建立这个问题的线性规划

9、模型。 设设yi分别表示冬、春、夏、秋四个季度采购的木材数，分别表示冬、春、夏、秋四个季度采购的木材数，xij代代表第表第i季度采购的用于第季度采购的用于第j季度销售的木材数。季度销售的木材数。1600 xxxx0 xy2000yxxx2000 xxx0 xxy2000yxxxx1400 xx0 xxxy2000yxxx1000 x0 xxxxy2000y)y450 x455()y460 x438x465()y430 x428x448x440()y410 x438x423x425(max443424144444342414332313343333242314132212242322221413

10、121114131211114443343322423221131211季季度度买进价买进价（万元（万元/万万米米3）卖出价卖出价（万元（万元/万万米米3）预计销售预计销售量（万米量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋4504551600案例案例7、有一艘货轮，分前、中、后三个舱位，它们的容积有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表与最大允许载重量如表1所示。现有三种货物待运，已知有所示。现有三种货物待运，已知有关数据列于表关数据列于表2。为了航运安全，要求前、中、后舱在实际。为了航运安全，要求前、中、后舱在实际载重量上

11、大体保持各舱最大允许载重量的比例关系，具体载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过，前、后舱之间不超过10%。问该货轮应装载。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线性规各多少件，运费收入为最大？试建立这个问题的线性规划模型。划模型。 前舱前舱中舱中舱后舱后舱最大允许载重量（吨）最大允许载重量（吨）200030001500容积（立方米）容积（立方米）400054001500表1商品商品数量（件）数量（件）每件体积（立方米每件体积（立方米

12、/件）件）每件重量（吨每件重量（吨/件）件） 运价（元运价（元/件）件）A6001081000B100056700C80075600设表示设表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数量种商品的数量)10.01 (34x5x6x8x5x6x8)10.01 (34)15.01 (21x5x6x8x5x6x8)15.01 (21)15.01 (32x5x6x8x5x6x8)15.01 (32800 xxx1000 xxx600 xxx1500 x7x5x105400 x7x5x104000 x7x5x101500 x5x6x83000 x5x6x8200

13、0 x5x6x8)xxx(600)xxx(700)xxx(1000zmax332313312111322212332313322212312111333231232221131211332313322212312111332313322212312111333231232221131211舱位载重限制舱位体积限制商品数量限制平衡条件前舱前舱 中舱中舱 后舱后舱重重量量200030001500容容积积400054001500商商品品数量数量 体体积积重重量量运运价价A6001081000B100056700C80075600案例案例8 . (仓库租用问题仓库租用问题)捷运公司拟在下一年度的捷运公

14、司拟在下一年度的1-4月的月的4个月内需租用仓库堆放物资个月内需租用仓库堆放物资.已知各月份所需仓库面积数列已知各月份所需仓库面积数列于表于表1.仓库租借费用随合同期而定仓库租借费用随合同期而定,期限越长期限越长,折扣越大折扣越大,具体具体数字见表数字见表2.租借仓库的合同每月初都可办理租借仓库的合同每月初都可办理,每份合同具体每份合同具体规定租用面积数和期限规定租用面积数和期限.因此该厂可根据需要因此该厂可根据需要,在任何一个月在任何一个月初办理租借合同初办理租借合同.每次办理时可签一份每次办理时可签一份,也可签若干份租用面也可签若干份租用面积和租借期限不同的合同积和租借期限不同的合同,试确

15、定该公司签订租借合同的最试确定该公司签订租借合同的最优决策优决策,目的是使所付租借费用最小目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012表表1合同租借期限1个月2个月3个月 4个月仓库借费用(元/100m2)2800450060007300表表2解解:1)设决策变量设决策变量xij表示捷运公司在第表示捷运公司在第i(I=1,2,3,4)个月初签个月初签订的租借期为订的租借期为j(j=1,2,3,4)个月的仓库面积的合同个月的仓库面积的合同(单位为单位为100m2).因因5月份起该公司不需要租借仓库月份起该公司不需要租借仓库,故故x24,x33,x34,x42,

16、x43,x44均为零均为零2)目标函数目标函数:使总的租借费用最小使总的租借费用最小xxxxxxxxxxZ142313322212413121117300)(600)(4500)(2800min3)约束条件约束条件:每个月份所需仓库面积的限制每个月份所需仓库面积的限制)4 , 3 , 2 , 1; 4 , 3 , 2 , 1(0122010154132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxij二、二、 整数规划模型整数规划模型例题例题1 P72 某单位有某单位有5个拟选择的投资项目，其所需投资个拟选择的投资项目，其

17、所需投资额与期望收益如下表。由于各项目之间有一定联系，额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；之间必须选择一项且仅需选择一项；B和和D之间需选之间需选择也仅需选择一项；又由于择也仅需选择一项；又由于C和和D两项目密切相关，两项目密切相关，C的实的实施必须以施必须以D的实施为前提条件，该单位共筹集资金的实施为前提条件，该单位共筹集资金15万元万元，问应该选择哪些项目投资，使期望收益最大？，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E59解：决策变量：设)5 , 4 , 3 , 2 , 1

18、j (j1j0 xj被选中表示项目不被选中表示项目目标函数：期望收益最大xxxxx54321967810zmax约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件： x3 x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：10111554246967810zmaxxxxxxxxxxxxxxxxxxxj43423215432154321或例题例题2 某服务部门各时段（每某服务部门各时段（每2小时为一时段）需要的服务小时为一时段）需要的服务员人数如下表，按规定

19、，服务员连续工作员人数如下表，按规定，服务员连续工作8小时（即四个时小时（即四个时段）为一班，现要求安排服务员的工作时间，使服务部门段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。服务员总数最小。时段时段12345678服务员最少数目服务员最少数目10891113853解：设在第解：设在第j时段开始时上班的时段开始时上班的服务员人数为服务员人数为xj，由于第，由于第j时段时段开始时上班的服务员将在第开始时上班的服务员将在第(j+3)时段结束时下班，故决策时段结束时下班，故决策变量只需考虑变量只需考虑x1,x2,x3,x4,x5，此问此问题的数学模型为：题的数学模型为：且为整数

20、0,35813119810min543215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZ例题例题3 （固定费用问题）有三种资源被用于生产三种产品（固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单件耗量及组成，资源量、产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制定一个生产计划三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。，使总收益最大。 产产品品 单件耗量单件耗量资源资源123资源量资源量A248500B234300C123100单件可变费用单件可

21、变费用456固定费用固定费用100150200单件售价单件售价81012解：总收益等于销售收入减去生产上述产品的固定费用和解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助生。下面借助0-1变量解决这个困难变量解决这个困难设设xj是第是第j种产品的产量，种产品的产量，j=1,2,3,再设再设)0(0)0(1xjxjyjjj种产品若不生产第种产品若生产第则问题的整数规划模型为：则问题的整

22、数规划模型为：10,010032300432500842200150100654max332211321321321321321或且为整数 yxyMxyMxyMxxxxxxxxxxyyyxxxZjjM为很大为很大的正数的正数案例案例4 （工件排序问题）用（工件排序问题）用4台机床加工台机床加工3件产品。各产品件产品。各产品的机床加工顺序，以及产品的机床加工顺序，以及产品i在机床在机床j上的加工工时上的加工工时aij如下表如下表。由于某种原因，产品。由于某种原因，产品2的加工总时间不得超过的加工总时间不得超过d，现要求，现要求确定各件产品在机床上的加工方案，使在最短的时间内加确定各件产品在机床上

23、的加工方案，使在最短的时间内加工完全部产品。工完全部产品。产品产品1a11 a13 a14 机床机床1 机床机床3 机床机床4 产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3 a32 a33 机床机床2 机床机床3解：设解：设xij表示产品表示产品i在机床在机床j上开始加工的时间上开始加工的时间(i=1,2,3;j=1,2,3,4)下面将逐步列出问题的整数规划模型下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在对于同一件产品，在下一台机床上加工的开始

24、时间不得早于在上一台机床上加工的约束时间，故应有：上一台机床上加工的约束时间，故应有：产品产品1：及及xax141313xax131111产品产品2：及及xax242222xax222121产品产品3：xax3332322、每一台机床对不同产品的加工顺序约束、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床开始另一件产品的加工。对于机床1，有两种加工顺序。或，有两种加工顺序。或先加工产品先加工产品1，后加工产品，后加工产品2；或反之。对于其它；或反之。对于其它3台机床，台机床，情

25、况也类似。为了容纳两种相互排斥的约束条件，对于每情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入台机床，分别引入0-1变量变量)4 , 3 , 2 , 1(10jyj先加工另一件产品先加工某件产品各各yj的意义是明显的。如当的意义是明显的。如当yj=0时，表示机床时，表示机床1先加工产品先加工产品1，后加工产品，后加工产品2，当，当yj=1时，表示机床时，表示机床1先加工产品先加工产品2，后加，后加工产品工产品1。机床机床1：及及)1 (1112121yMxaxyMxax1211111机床机床2：及及)1 (2223232yMxaxyMxax2322222机床机床3：及及)1

26、 (3133333yMxaxyMxax3331313机床机床4：及及)1 (4142424yMxaxyMxax4241414那么，每台机床上的加工产品的顺序可用下列四组约束那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证条件来保证3、产品、产品2的加工时间约束的加工时间约束产品产品2的开始加工时间是的开始加工时间是x21，结束加工时间是，结束加工时间是x24+a24，故应，故应有：有：dxax2124244、目标函数的建立、目标函数的建立设全部产品加工完毕的结束时间为设全部产品加工完毕的结束时间为W，由于三件产品的加，由于三件产品的加工结束时间分别为工结束时间分别为x14+a14，

27、x24+a24， x33+a33，故全部产品的故全部产品的实际加工结束时间为：实际加工结束时间为：),max(333324241414axaxaxW转化为线性表达式：转化为线性表达式：axWaxWaxWWZ333324241414min案例案例5：产品配送问题：产品配送问题某公司准备建K个配送中心，负责配送它的产品。该公司把它的所有客户按地理位置分成n个客户群，每个客户群由一个配送中心向它配送产品。现有m个备选点可建立配送中心(mk)。如果第i个备选点建配送中心，那么它的建设成本为bi，它向第j个客户群配送产品的成本是cij。现在该公司的问题是要从m个备选点中选择K个点建立配送中心，使得总成本

28、最低。请建立该问题的运筹学模型。 案例案例6：水资源利用问题：水资源利用问题某地区现有耕地可分为两种类型，第一类耕地各种水利设施配套，土地平整，排灌便利；第二类耕地则未具备以上条件。其中，第一类耕地有2.5万亩，第二类耕地有8.2万亩，此外尚有宜垦荒地3.5万亩。该地区主要作物是小麦，完全靠地表水进行灌溉。由于地表水的供应量随季节波动，在小麦扬花需水时恰值枯水季节，往往由于缺水使一部分麦田无法灌溉，影响产量。而由于第二类耕地高，进一步合理利用水资源的措施有二：其一是进行农田建设，把一部分第二类耕地改造为第一类耕地，以节约用水，提高单产；其二是修建一座水库，闲水期蓄水，到小麦扬花需水的枯水期放水

29、，从而调节全年不同季节的水量。目前该地区在整个小麦生长期的地表水资源可利用量为96.5百万方，其中小麦扬花需水季节可供水量为7.5百万方，水库建成后在小麦扬花需水季节可供水量为6.5百万方，修建水库需投资5.5百万元，将第二类耕地改为第一类耕地每亩需投资20元，将荒地开垦为第二类耕地每亩需投资85元，将荒地开垦并改造为第一类耕地每亩需投资100元，规划期内，计划总投资额为9百万元，该地区对小麦的需求及国家征购指标共计2万吨，超额向国家交售商品粮每吨可加价100元。各种条件下水的灌溉定额及收益的情况如表所示 类别全生长期浇水量（百万方/亩）扬花时浇水量（百万方/亩）单产（吨/亩）净产值（百元/亩

30、）扬花时浇水的第一类耕地7.51.40.250.52扬花时不浇水的第一类耕地6.10.00.20.43扬花时浇水的第二类耕地9.01.650.230.47扬花时不浇水的第二类耕地7.350.00.1850.39现在需要我们论证的问题是：为了充分利用水资源，发挥最大的经济效益，规划期内应该将多少亩第二类耕地改造为第一类耕地，应该开垦多少亩荒地，水库有没有必要建？ 解：设x1为规划年份第类耕地中小麦扬花时可以灌溉的耕地面积（万亩）；设x2为规划年份第类耕地中小麦扬花时不能灌溉的耕地面积（万亩）； 设x3为规划年份第类耕地中小麦扬花时可以灌溉的耕地面积（万亩）；设x4为规划年份第类耕地中小麦扬花时不

31、能灌溉的耕地面积（万亩）；设x5为规划年份该地区超额向国家交售的商品粮数量（万吨）；设 x1为规划期内由荒地直接开垦并改造为第类耕地的面积（万亩）；设 x2为规划期内由荒地直接开垦为第类耕地的面积（万亩）；设 x3为规划期内由第类耕地改造为第类耕地的面积（万亩）；1.土地资源约束对第类耕地有:5 . 23121xxxx对第类耕地有:2 . 83243xxxx对宜垦荒地有:5 . 321xx2.水资源约束对小麦扬花季节有:5 . 75 . 665. 14 . 131yxx对整个生长期有:5 .9635. 70 . 91 . 65 . 74321xxxx3.投资资金限制:0 . 95 . 52 .

32、 085. 00 . 1321yxxx4.社会对小麦的需求约束:0 . 2185. 023. 02 . 025. 054321xxxxxy为表示规划期内水库是否兴建的指示变量，它的取值只能是0和1。若y=0，表示该水库不建;y=1,表示该水库存兴建，本模型的目标函数应选为规划年份的净收益最大.由于表中所列规划年各种条件下的净收益数字并未包括规划期内各项投资的资本回收成本,也未包括超额交售商品粮的加价收益,所以在目标函数中,这两项尚需要单独处理.在本模型中,我们取年利息率i=0.06,投资回收年限n=20年,则资本回收因子CRF=0.087.在目标函数中,相应于各工程项目的资本回收成本系数即为CRF乘以各