运筹学ppt课件Ch3整数规划

Ch3 整数规划,Integer,Programming,*,制作与教学,武汉,理工大学,管理学院 熊伟,Page,49,3.1,整数规划数学模型,Mathematical Model of IP,3.2,纯整数规划的求解,Solving Pure Integer Programming,3.3,01规划的求解,Solving Binary,Integer Programming,Chapter 3 整数规划,Integer Programming,运筹学,Operations Research,10/7/2024,3.1 整数规划数学模型,Mathematical Model of IP,10/7/2024,一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。,很多实际规划问题都属于整数规划问题,1. 变量是人数、机器设备台数或产品件数等都要求是整数,2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量,x,，当,x,=1表示投资，,x,=0表示不投资；,3. 人员的合理安排问题，当变量,x,ij,=1表示安排第,i,人去做,j,工作，,x,ij,=0表示不安排第,i,人去做,j,工作。逻辑变量也是只允许取整数值的一类变量。,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,【例3.1 】某人有一背包可以装10公斤重、0.025m,3,的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？,表3-1,【解】设甲、乙两种物品各装,x,1,、,x,2,件，则数学模型为：,(3.1),3.1 整数规划的数学模型,Mathematical Model of IP,物品,重量,（公斤/每件）,体积,（m,3,/每件）,价值,(元/每件),甲,乙,1.2,0.8,0.002,0.0025,4,3,10/7/2024,如果不考虑,x,1,、,x,2,取整数的约束（称为（3.1）的松弛问题），线性规划的可行域如图3-1中的阴影部分所示。,3.1 整数规划的数学模型,Mathematical Model of,IP,图3-1,10/7/2024,用图解法求得点,B,为最优解：,X,(3.57，7.14)，,Z,35.7。由于,x,1，,x,2,必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得,Z,=33,并非最优。实际上问题的最优解是（5，5），,Z,=35。即两种物品各装5件，总价值35元。,由图31知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。,还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,【例3.2 】在例3.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m,3,。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。,（1）所装物品不变；,（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为,【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入01变量（或称逻辑变量）,y,i,，令,i,=1,2分别是采用背包及旅行箱装载。,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,（1）,由于所装物品不变，式(3.1)约束左边不变，整数规划数学模型为,（2）,由于不同载体所装物品不一样，数学模型,为,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,式中,M,为充分大的正数。从上式可知，当使用背包时(,y,1,=1，,y,2,=0)，式(,b,)和(,d,)是多余的；当使用旅行箱时(,y,1,=0，,y,2,=1)，式(,a,)和(,c,)是多余的。上式也可以令：,同样可以讨论对于有,m,个条件互相排斥、有,m,（,m,、,m,）个条件起作用的情形。,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,（1)右端常数是,k,个值中的一个时，类似式(3.2)的约束条件为,（2)对于,m,组,条件中有,k,（,m,）组起作用时，,类似式(3.3)的,约束条件写成,这里,y,i,=1表示第,i,组约束不起作用（如,y,1,=1式(3.3b)、(3.3d)不起作用），,y,i,=0表示第,i,个约束起作用。当约束条件是“,”符号时右端常数项应为,（3) 对于,m,个,条件中有,k,（,m,）个起作用时，约束条件写成,3.1 整数规划的数学模型,Mathematical Model of,IP,10/7/2024,【例3.3】试引入01变量将下列各题分别表达为一般线性约束条件,（1）,x,1,+,x,2,6或4,x,1,+6,x,2,10或2,x,1,+4,x,2,20,（2）若,x,1,5，则,x,2,0，否则,x,2,8,（3）,x,2,取值0，1，3，5，7,【解】 （1）3个约束只有1个起作用,3.1 整数规划的数学模型,Mathematical Model of,IP,或,10/7/2024,（3）右端常数是5个值中的1个,3.1 整数规划的数学模型,Mathematical Model of,IP,（2）两组约束只有一组起作用,10/7/2024,【例3.4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表32所示，怎样安排产品的加工使总成本最小,表32,【解】设,x,j,为采用第,j,（j=1,2,3）种方式生产的产品数量，生产费用为,3.1 整数规划的数学模型,Mathematical Model of,IP,固定成本（元）,变动成本,（元件）,最大加工数,（件）,本企业加工,500,8,1500,外协加工,800,5,2000,外协加工,600,7,不限,10/7/2024,式中,k,j,是固定成本，,c,j,是单位产品成本设01变量,y,j,，令,数学模型为,3.1 整数规划的数学模型,Mathematical Model of,IP,（3.4）,式（3.4）中 是处理,x,j,与,y,j,一对变量之间逻辑关系的特殊约束，当,x,j,0时,y,j,=1, 当,x,j,0时，为使,Z,最小化，有,y,j,=0。,例3.4是混合整数规划问题用WinQSB软件求解得到：,X,(0，2000，2000),T,，,Y,(0，1，1),T,，,Z,=25400.,10/7/2024,作业：教材P75 1, 2，3，4，5，6,1.线性整数规划模型的特征,2.什么是纯（混合）整数规划,3.01规划模型的应用,3.1 整数规划的数学模型,Mathematical Model of,IP,下一节：纯整数规划的求解,10/7/2024,3.2 纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,分枝定界法的步骤：,1. 求整数规划的松弛问题最优解；,2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；,3.任意选一个非整数解的变量,xi,，在松弛问题中加上约束,x,i,x,i,及,x,i,x,i,+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；,4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,求解纯整数规划的分枝定界法,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,【例3.5 】用分枝定界法求解例5.1,【解】先求对应的松弛问题（记为,LP,0）：,用图解法得到最优解,X,（3.57,7.14）,Z,0,=35.7,如下图所示。,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,8.33,10,松弛问题,LP,0的最优解,X,=(3.57,7.14),Z,0,=35.7,x,1,x,2,o,A,B,C,10,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,10,10,x,1,x,2,o,A,B,C,LP,1,LP,2,3,4,LP,1:,X,=(3,7.6),Z,1,=34.8,LP,2:,X,=(4,6.5),Z,2,=35.5,10/7/2024,10,10,x,1,x,2,o,A,B,C,LP,1,LP,3,3,4,LP,3:,X,=(4.33,6),Z,3,=35.33,6,LP,1:,X,=(3,7.6),Z,1,=34.8,10/7/2024,10,10,x,1,x,2,o,A,C,LP,1,3,4,6,LP,4:,X,=(4,6),Z,4,=34,LP,5:,X,=(5,5),Z,5,=35,5,LP,1:,X,=(3,7.6),Z,1,=34.8,LP,3,LP,5,10/7/2024,尽管,LP,1的解中,x,1,不为整数，但Z,5,Z因此LP5的最优解就是原整数规划的最优解。,上述分枝过程可用下图表示,LP,0:,X,=(3.57,7.14),Z,0,=35.7,LP,1:,X,=(3,7.6),Z,1,=34.8,LP,2:,X,=(4,6.5),Z,2,=35.5,x,1,3,x,1,4,LP,3:,X,=(4.33,6),Z,3,=35.33,x,2,6,LP,4:,X,=(4,6),Z,4,=34,LP,5:,X,=(5,5),Z,5,=35,x,1,4,x,1,5,无可行解,x,2,7,10/7/2024,设纯整数规划,松弛问题,的最优解,设,x,i,不为整数，,3.2.2,求解,IP,的割平面法,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,将 分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数并且有,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,加入松弛变量,s,i,得,此式称为以,x,i,行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。,则,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,例如，,x,1,行：,移项：,令,加入松弛变量,s,1,得,同理，对于,x,2,行有：,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,【例3.6】 用割平面法求解下列IP问题,【解】 放宽变量约束，对应的松弛问题是,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,加入松弛变量,x,3,及,x,4,后，用单纯形法求解，得到最优表3-3。,最优解X,(0),(5/2，15/4),不是IP的最优解。选择表3-3的第一行(也可以选第二行)为源行,3.2,纯整数规划的求解,Solving Pure Integer Programming,C,j,4,3,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,4,3,x,1,x,2,1,0,0,1,1/4,1/8,1/2,3/4,5/2,15/4,j,0,0,5/8,1/4,表3-3,10/7/2024,分离系数后改写成,加入松弛变量,x,5,得到高莫雷约束方程,将式(3.8)作为约束条件添加到表33中，用对偶单纯形法计算，如表34所示,3.2,纯整数规划的求解,Solving Pure Integer Programming,10/7/2024,C,j,4,3,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,4,3,0,x,1,x,2,x,5,1,0,0,0,1,0,1/4,1/8,1,1/2,3/4,2,0,0,1,5/2,15/4,2,j,0,0,5/8,1/4,0,4,3,0,x,1,x,2,x,4,1,0,0,0,1,0,1/2,1/2,1/2,0,0,1,1/4,3/8,1/2,3,3,1,j,0,0,1/2,0,1/8,最优解,X,(1),(3，3)，最优值Z21。所有变量为整数，,X,(1),就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。,3.2,纯整数规划的求解,Solving Pure Integer Programming,表34,如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。,10/7/2024,作业：教材P76 T 7，8,1.理解分枝与定界的含义,2.选择合适的“ 枝”生“ 枝”,3.掌握何时停止生“ 枝”,4.领会割平面法的基本原理,5.分离源行，求出Gomory约束,6.在最优表中增加Gomory约束，用 对偶单纯形法迭代,3.2,纯整数规划的求解,Solving Pure Integer Programming,下一节： 01规划的求解,10/7/2024,3.3 01规划的求解,Solving BIP,10/7/2024,3.3.1,求解01整数规划的隐枚举法,隐枚举法的步骤：,1.找出任意一可行解，目标函数值为,Z,0,2.,原问题求最大值时，则增加一个约束,当求最小值时，上式改为小于等于约束,3. 列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值,4. 目标函数值最大（最小）的解就是最优解,3.3 01规划的求解,Solving BIP,10/7/2024,【,例3.7】用隐枚举法求解下列,BIP问题,【解】（1）不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X,0,(1，0，0，1)是一个可行解，目标值Z,0,11是BIP问题的下界，构造一个约束： ，原BIP问题变为,3.3 01规划的求解,Solving BIP,10/7/2024,(2) 列出变量取值0和1的组合，共2,4,16个，分别代入约束条件判断是否可行。首先判断式（3.9,a,）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见表37所示。,3.3 01规划的求解,Solving BIP,10/7/2024,j,X,j,3.9,a,3.9,b,3.9,c,3.9,d,Z,j,j,X,j,3.9,a,3.9,b,3.9,c,3.9,d,Z,j,1,(0,0,0,0),9,(1,0,0,0),2,(0,0,0,1),10,(1,0,0,1),11,3,(0,0,1,0),11,(1,0,1,0),4,(0,0,1,1),12,(1,0,1,1),14,5,(0,1,0,0),13,(1,1,0,0),6,(0,1,0,1),14,(1,1,0,1),13,7,(0,1,1,0),15,(1,1,1,0),8,(0,1,1,1),16,(1,1,1,1),表35,(3) 由表3-5知，BIP问题的最优解：,X,（1，0，1，1），最优值Z14,3.3 01规划的求解,Solving BIP,10/7/2024,选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1，如例3.8。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0。,在表37的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。,3.3.2,分枝隐枚举法求解,BIP,问题,将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下：,（1）将BIP问题的目标函数的系数化为非负，如,3.3 01规划的求解,Solving BIP,10/7/2024,当变量作了代换后，约束条件中的变量也相应作代换。,（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；,（4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。,分枝隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。,3.3 01规划的求解,Solving BIP,(2)变量重新排序：变量依据目标函数系数值按升排序；,10/7/2024,停止分枝和需要继续分枝的原则：,（1）当某一子问题是可行解时则停止分枝并保留；,（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；,（3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝；,（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。,【例3.8】用分枝隐枚举法求解下列BIP问题,3.3 01规划的求解,Solving BIP,10/7/2024,解 （1）目标函数系数全部非负，直接对变量重新排序,（2）求主枝：令X(1，1，1，1)得到主枝1，检查约束条件知(3.10,c,)不满足，则进行分枝。,（3）令,x,2,=0同时令,x,3,=0及,x,3,=1得到分枝2和分枝3，,X,2,和,X,3,是可行解，分枝停止并保留，如表3-8及图3-8所示。,3.3 01规划的求解,Solving BIP,10/7/2024,表3.8,令,x,2,=1同时令,x,3,=0得到分枝4，,X,4,是可行解，分枝停止并保留。令,x,2,=1、,x,3,=1，,x,4,取“0”和“1”得到分枝5和6，分枝5不可行并且Z,5,11小于Z,3,和 Z,4,，分枝停止并剪枝。注意到分枝6，,x,4,1时只有,x,1,0（,x,1,1就是主枝），,X,6,不可行并且Z,6,10小于Z,3,和 Z,4,，分枝停止并剪枝，分枝过程结束。整个计算过程可用图32和表3.8表示。,分枝,(,x,2,x,3,x,4,x,1,),3.10,a,3.10,b,3.10,c,Z,j,可行性,1,(1,1,1,1),16,不可行,2,(0,0,1,1),11,可行,3,(0,1,1,1),14,可行,4,(1,0,1,1),13,可行,5,(1,1,0,1),11,不可行,6,(1,1,1,0),10,不可行,3.3 01规划的求解,Solving BIP,10/7/2024,搜索到3个可行解，3个目标值中Z,3,最大，因此,X,3,是最优解，转换到原问题的最优解为,X,（1，0，1，1），最优值Z14，计算结束。,图32,3.3 01规划的求解,Solving BIP,10/7/2024,【例3.9】用分枝隐枚举法求解下列BIP问题,解 （1）令,x,2,=1,x,2,及,x,5,=1,x,5,，代入模型后整理得,3.3 01规划的求解,Solving BIP,10/7/2024,（2）目标函数系数按升序将对应的变量重新排列得到模型,（3）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解,X,1,（0，0，0，0，0），Z,1,7，检验约束条件知,X,1,不可行，进行分枝。,（4）取,x,1,=1和,x,1,=0，分别其它变量等于“1”和,“0”分枝，判断可行性，计算过程参见表36及图33。,3.3 01规划的求解,Solving BIP,10/7/2024,分枝,j,上一分枝,X,j,=(,x,1,x,4,x,2,x,5,x,3,),3.11,a,3.11,b,Z,j,可行性,1,2,3,4,5,主枝,1,1,1,1,(0,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,0,1,0),(0,0,0,0,1),7,5,4,3,1,不可行,不可行,不可行,不可行,可行,6,7,8,9,10,1,6,6,6,6,(1,0,0,0,0),(1,1,0,0,0),(1,0,1,0,0),(1,0,0,1,0),(1,0,0,0,1),6,4,3,2,0,不可行,不可行,不可行,不可行,可行,表36,3.3 01规划的求解,Solving BIP,10/7/2024,由表36知，分枝5和分枝10两个问题可行，分枝5优于分枝10，其它不可行子问题尽管目标值优于分枝5，由约束(3.11,b,)知，继续分枝不可能得到其它可行解，因此停止分枝，计算结束。分枝5的解,X,5,(,x,1,x,4,x,2,x,5,x,3,)（0，0，0，0，1），原BIP的最优解为,X,(,x,1,x,2,x,3,x,4,x,5,)(0，1，1，0，1),最优值Z1。,图33,3.3 01规划的求解,Solving BIP,10/7/2024,在分枝隐枚举法的计算过程中，由于变量已经按目标函数系数从小到大重新排序，因此在选择子问题分枝的原则是按排序后的变量顺序分枝，但变量较多时搜索可行解的过程可能非常漫长。针对转换后的目标函数特征，极大值问题的解中“1”越多越优，极小值问题的解中“0”越多越优，因此在选择变量分枝时尽可能采用避“0”或“1”的方法，请观察表38及36.,3.3 01规划的求解,Solving BIP,10/7/2024,作业：P76 T 9，10,1.用隐枚举法求0-1规划的最优解,2.用分枝隐枚举法求解0-1规划的最优解,3.3 01规划的求解,Solving BIP,The End of Chapter 3,3.9(1),3.9(2),10/7/2024,