云南农业大学经济管理学院主讲佘迎红课件.ppt

《云南农业大学经济管理学院主讲佘迎红课件.ppt》由会员分享，可在线阅读，更多相关《云南农业大学经济管理学院主讲佘迎红课件.ppt（66页珍藏版）》请在三一文库上搜索。

1、1,云南农业大学经济管理学院 主讲: 佘迎红,E-mail: Tel: 13888581179,3.1 整数规划数学模型 Mathematical Model of IP 3.2 整数规划的求解 Solving Integer Programming 3.3 01规划的求解 Solving Binary Integer Programming,第3章 整 数 规 划 Integer Programming,3,线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理

2、的。 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资。,3.1 整数规划的数学模型,纯整数规划(IP)：xj全部取整数 混合整数规划(MIP)：xj部分取整数 0-1整数规划(BIP)：整数变量只能取0或1,分类,4,【例3-1 】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，才能使所装物品的总价值最大？,表3-1,【解】设甲、乙两种物品各装x1、x2件，则数学模型为：,(3-1),3.1 整数规划的数学模型,5,【补充例】投资决策问题。某公司有5个项

3、目被列入投资计划，各项目的投资额和期望的投资收益如下表,3.1 整数规划的数学模型,该公司只有600万元资金可用于投资，由于技术上的原因， 投资受到以下约束： （1）在项目1、2和3中必须且只有一项被选中； （2）项目3和项目4最多只能选中一项； （3）项目5被选中的前提是项目1必须被选中。 如何在上述条件下选择一个最好的投资方案，使投资收益最大？,6,【解】设xj 为选择第 j（j=1,2,3,4,5)个项目的决策,3.1 整数规划的数学模型,7,【例3-2 】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模

4、型，使所装物品价值最大。 （1）所装物品不变； （2）如果选择旅行箱，则只能装载丙和丁两种物品，每件物品的重量、体积和价值如下表所示,3.1 整数规划的数学模型,8,【解】（1）引入01变量 yj，令,j=1,2分别是采用背包及旅行箱装载。,3.1 整数规划的数学模型,(3-2),此问题也可以建立两个整数规划模型。,9,（2）由于不同载体所装物品不一样，数学模型为,3.1 整数规划的数学模型,其中M为充分大的正数。 当使用背包时( y1=1, y2=0 )，式(b)和(d)是多余的； 当使用旅行箱时( y1=0, y2=1 )，式(a)和(c)是多余的。,10,（1）右端常数是k个值中的一个时

5、，类似式(3-2)的约束条件为,3.1 整数规划的数学模型,同样可以讨论对于有m个条件互相排斥、有m （m、m）个条件起作用的情形。,11,（2）对于m 个（组）条件中有k（m）个（组）起作用时，类似式(3-3)的约束条件写成,这里yi=1表示第 i 组约束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第 i个约束起作用。当约束条件是“”符号时右端常数项应为,3.1 整数规划的数学模型,12,【例3-3】试引入01变量将下列各题分别表达为一般线性约束条件 （1）x1+x26或4x1+6x210或2x1+4x220 （2）若x15，则x20，否则x28 （3）x2取值0

6、，1，3，5，7,【解】 （1）3个约束只有1个起作用,或,3.1 整数规划的数学模型,如果要求至少一个条件满足，模型如何改变？,13,（3）右端常数是5个值中的1个,（2）两组约束只有一组起作用,3.1 整数规划的数学模型,(1) (2) (3) (4),14,【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产。已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表32所示，怎样安排产品的加工使总成本最小。,表 32,3.1 整数规划的数学模型,15,【解】设xj为采用第 j（j=1,2,3）种方式生产的产品数量，生产费用

7、为,3.1 整数规划的数学模型,其中kj是固定成本，cj是可变成本。 设01变量yj,16,（3-4）,用WinQSB软件求解得到： X(0，2000，2000)T ，Y(0，1，1)T，Z=25400,3.1 整数规划的数学模型,配合目标，使得只有选用第j 种加工方式才产生相应成本，不选用第j 种加工方式就没有成本。,17,整数规划的一般形式：,称线性规划模型,（）,（）,(LP),为（）的松弛问题。,每一个整数规划都对应一个松弛问题，整数规划比它的松弛问题约束得更紧。,部分或全部取整,3.1 整数规划的数学模型,18,3.1 整数规划的数学模型,习题3.4 【解】令运动员甲、乙、丙、丁、戊

8、编号为1、2、3、4、5，项目 高低杠、平衡木、鞍马、自由体操编号为1、2、3、4。 设,19,max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24 +8.8x31 +8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52 +8.2x53+7.7x54 x11+x12+x13+x143 x21+x22+x23+x243 x31+x32+x33+x343 x41+x42+x43+x443 x51+x52+x53+x543 x11+x21+x31+x41+x511 x

9、12+x22+x32+x42+x521 x13+x23+x33+x43+x531 x14+x24+x34+x44+x541 x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43 +x44+x51+x52+x53+x54=10 xij=0 或 1 (i=1,2,3,4,5;j=1,2,3,4),3.1 整数规划的数学模型,20,1. 整数规划模型的特征 2. 什么是纯（混合）整数规划 3. 01规划模型的应用,下一节：纯整数规划的求解,3.1 整数规划的数学模型,21,整数规划解的特点 整数规划（）的可行解集是其松弛问题（）的可行

10、解集的子集。线性规划问题的可行解集是一个凸集（稠密的），但整数规划的可行解集不是凸集（离散型）。 如果松弛问题（）的最优解是整数解，则一定是整数规划（）的最优解。 整数规划（）的最优值不会优于松弛问题（）的最优值。,3.2 整数规划的求解,22,3.2 整数规划的求解,图3-1,点B为最优解 X(3.57，7.14) Z35.7,用图解法求解例3-1的松弛问题,整数规划问题的可行解集是图中可行域内的整数点。,23,松弛问题的最优解 X(3.57，7.14)， Z35.7 “四舍五入”得 X=(4,7) 不是可行解； 用“取整”法来解时，X=(3,7)虽属可行解，但代入目标函数得Z=33, 并非

11、最优。 该整数规划问题的最优解是X=(5,5)，最优值是Z=35 即甲、乙两种物品各装5件，总价值35元。,由图31知，点（5，5）不是LP可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。,3.2 整数规划的求解,24,【例3-5 】用分支定界法求解例3-1,【解】先求对应的松弛问题,用图解法得到最优解X（3.57,7.14）, Z0=35.7,3.2.1 分支定界法,25,8.33,10,松弛问题LP0的最优解X=(3.57, 7.14), Z0=35.7,x1,x2,o,A,B,C,10,3.2.1 分支定界法,10,1

12、0,x1,x2,0,A,B,C,LP1,LP2,3,4,LP1:X=(3, 7.6), Z1=34.8,LP2:X=(4, 6.5), Z2=35.5,10,10,x1,0,A,C,LP1,3,4,LP1:X=(3, 7.6), Z1=34.8,x1,B,6,7,LP3:X=(4.33, 6), Z3=35.33,LP2,x1,x1,LP4:X=(4, 6), Z4=34,LP5:X=(5, 5), Z5=35 此为原IP最优解,5,29,尽管LP1的解中x2不为整数，但Z5Z1，因此LP5的最优解就是原整数规划的最优解。若Z5Z1 ，则要对LP1进行分支。,3.2.1 分支定界法,30,上述

13、分枝过程可用下图表示,LP0: X=(3.57, 7.14),Z0=35.7,LP1: X=(3, 7.6) Z1=34.8,LP2: X=(4, 6.5) Z2=35.5,x13,x14,LP3: X=(4.33, 6) Z3=35.33,x26,LP4: X=(4, 6) Z4=34,LP5: X=(5, 5) Z5=35,x14,x15,无可行解,x27,最优解,3.2.1 分支定界法,31,分支定界法的步骤：,1. 求整数规划的松弛问题最优解； 2. 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；,3.2.1 分支定界法,3. 任意选一个非整数解的变量xi，在松弛

14、问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分支。新的松弛问题具有特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题是求最小值时，目标值是分支问题的下界；,32,4. 检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于（max）等于其它分支的目标值，则将其它分支剪去不再计算, 若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分支，再检查，直到得到最优解。 分支原则：始终选Z值大的，且xi中有分数的LP进行分支。 定界原则：满足取整要求，且目标函数值较已定的 “界”更优，则用该目标函数值替换，重新定界。,3.2.1 分支定界法,说明：

15、分支定界法适用于求解纯整数规划和混合整数规划,33,设纯整数规划,松弛问题的最优解,3.2.2 割平面法,设xi= 不为整数，,34,将 分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数, 并且有,3.2.2 割平面法,35,加入松弛变量si得,此式称为以xi行为源行（来源行）的割平面方程，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部变量为整数。,则,3.2.2 割平面法,36,例如，,x1行：,移项：,加入松弛变量s1得割平面方程,同理，对于x2行有：,3.2

16、.2 割平面法,37,【例3-6】 用割平面法求解下列IP问题,【解】 对应的松弛问题是,3.2.2 割平面法,38,加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。,最优解X(0)(5/2，15/4), 不是IP的最优解。 选择表中的第一行(也可以选第二行)为源行,表3-3,3.2.2 割平面法,39,分离系数后改写成,加入松弛变量x5得到高莫雷约束方程,将此式作为约束条件添加到表33中，用对偶单纯形法计算，如表34所示,3.2.2 割平面法,40,最优解X(1)(3，3)，最优值Z21。,表34,3.2.2 割平面法,41,几何意义 由约束条件得： x3=30-6x1-4x2

17、, x4=10-x1-2x2 代入割平面方程 -x3-2x4-2，得 x1+x26,说明：利用割平面法求解整数规划问题时,若从最优单纯形表中选择具有最大小（分）数部分的非整分量所在行构造割平面方程，往往可以提高“切割”效率，减少“切割”次数。,3.2.2 割平面法,不含任何 整数解,42,思考： 对于两个变量的纯整数规划问题是否可采用图解法。,最优解 x1=0, x2=5,3.2.3 整数规划的图解法,43,步骤： 1.作出松弛问题的可行域。 2.在可行域内作出所有的整数网格。 3.作目标函数等值线，将等值线平行移动，最后接触到的网格点（或平行移动到松弛问题的最优解点再往回移，首先接触到的网格

18、点），就是整数规划的最优解。,3.2.3 整数规划的图解法,44,1. 理解分支与定界的含义 2. 选择合适的“ 枝”生“ 枝” 3. 掌握何时停止生“枝” 4. 领会割平面法的基本原理 5. 分离源行，求出Gomory约束 6. 在最优表中增加Gomory约束，用对偶单纯形法迭代,下一节： 01规划的求解,3.2 整数规划的求解,45,3.3.1 求解01整数规划的隐枚举法,隐枚举法的步骤：,1. 找出任意一可行解，目标函数值为Z0 2. 原问题求最大值时，则增加一个约束,作为过滤条件。 当求最小值时，上式改为小于等于约束。 列出所有可能解，对每个可能解先检验是否满足过滤条件，若满足再检验其

19、它约束，若不满足约束，则不可行，若所有约束都满足，且目标值超过Z0 ,则应更换过滤条件。 4. 目标函数值最大（最小）的解就是最优解。,3.3 01规划的求解,46,【例3-7】用隐枚举法求解下列BIP问题,3.3 01规划的求解,(1) (2) (3) (4),47,表35,最优解：X(1, 0, 1, 1)T，最优值Z14,3.3 01规划的求解,8,z8,48,3.3.2 分枝隐枚举法求解BIP问题,将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下： （1）将BIP问题的目标函数的系数化为非负，如,3.3 01规划的求解,49,当变量作了代换后，约束条件中的变量也相应作代

20、换。,（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步； （4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。 分枝隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。,(2)变量重新排序：变量依据目标函数系数值按升排序；,3.3 01规划的求解,50,停止分枝和需要继续分枝的原则： （1）当某

21、一子问题是可行解时则停止分枝并保留； （2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝； （3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝； （4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。,3.3 01规划的求解,51,【例3-8】用分枝隐枚举法求解下列BIP问题,3.3 01规划的求解,52,【解】（1）目标函数系数全部非负，直接对变量重新排序,（2）求主枝：令X(1，1，1，1)得到主枝1，检查约束条件知(3-10c)不满足，则进行分枝。 （3）令x2=0同时令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝

22、停止并保留，如表3-8及图3-8所示。,3.3 01规划的求解,表3-8,令x2=1同时令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z511小于Z3和 Z4，分枝停止并剪枝。注意到分枝6，x41时只有x10（x11就是主枝），X6不可行并且Z610小于Z3和 Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图32和表3-8表示。,54,搜索到3个可行解，3个目标值中Z3最大，因此X3是最优解，转换到原问题的最优解为X（1，0，1，1），最优值Z14，计算结束。,图32,3.3 01规划的求解,55,【例3-9

23、】用分枝隐枚举法求解下列BIP问题,【解】 （1）令x2=1x2及x5=1x5，代入模型后整理得,3.3 01规划的求解,56,（2）目标函数系数按升序将对应的变量重新排列得到模型,（3）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解X1（0，0，0，0，0），Z17，检验约束条件知X1不可行，进行分枝。 （4）取x1=1和x1=0，分别其它变量等于“1”和 “0”分枝，判断可行性，计算过程参见表36及图33。,3.3 01规划的求解,57,表36,3.3 01规划的求解,58,由表36知，分枝5和分枝10两个问题可行，分枝5优于分枝10，其它不可行子问题尽管目标值优于分枝5，由

24、约束(3-11b)知，继续分枝不可能得到其它可行解，因此停止分枝，计算结束。分枝5的解X5(x1, x4, x2, x5, x3)（0，0，0，0，1），原BIP的最优解为X(x1, x2, x3, x4, x5)(0，1，1，0，1),最优值Z1。,图33,3.3 01规划的求解,59,在分枝隐枚举法的计算过程中，由于变量已经按目标函数系数从小到大重新排序，因此在选择子问题分枝的原则是按排序后的变量顺序分枝，但变量较多时搜索可行解的过程可能非常漫长。针对转换后的目标函数特征，极大值问题的解中“1”越多越优，极小值问题的解中“0”越多越优，因此在选择变量分枝时尽可能采用避“0”或“1”的方法，

25、请观察表38及36.,3.3 01规划的求解,60,长江综合商场有5000m2营业面积招租，拟吸引以下5类商店入租。已知各类商店开设一个店铺占用的面积，在该商场内最多与最少开设的个数，以及每类商店开设不同个数时每个商店的每月预计利润见表。商场除按租用面积每月收取100元/m2租金外，还按利润的10%按月收取屋业管理费。问该商场应招租上述各类商店各多少个，使预期收入为最大？,思 考 商 场 招 租,61,思 考 商 场 招 租,maxZ=100(250y1+350y2+600y3+300y4+400y5)+10%(9x11+82x12 +73x13+10x21+92x22+12 3x53) x1

26、1+2x12+3x13=y1 x21+2x22+3x23=y2 x31+2x32+3x33=y3 x41+2x42+3x43=y4 x51+2x52+3x53=y5 x11+x12+x13=1 x21+x22+x23=1 x31+x32+x33=1 x41+x42+x431 x51+x52+x53=1 x23=0 x43=0 250y1+350y2+600y3+300y4+400y55000 xij=0 或 1（i=1,2,3,4,5; j=1,2,3), yi0 (i=1,，5）,63,用LINDO软件计算，得最优解 x12=x22=x33=x42=x53=1，其余 xij=0 最优值 Z=63（万元） 最优方案： 招租服装店2个，鞋帽店2个，百货店3个，书店2个，餐饮店3个，预期收入最大，为63万元,思 考 商场招租,64,1. 用隐枚举法求0-1规划的最优解 2. 用分枝隐枚举法求解0-1规划的最优解,The End of Chapter 3,3.3 01规划的求解,65,【案例C-3】证券营业网点设置问题,【解】引入01变量,令bj表示在第j号城市建一家网点的平均投资额，rj表示第j号城市每一家网点的平均市场占有率，cj表示第j号城市每一家网点的平均利润额。,