《运筹学教程》胡云权 第五版 第三章 整数规划.pptx

1、第三章 整数规划,学习目标,整数规划数学模型 分枝定界法 割平面法 01规划 指派问题,整数规划数学模型,部分或全部决策变量是整数的规划，称为整数规划。若模型是线性的，称为整数线性规划。本章只讨论整数线性规划。,纯整数规划：全部决策变量取整数值，又称全整数规划； 混合整数规划：部分决策变量取整数值； 0-1规划：决策变量只能取0或1。,例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数；,2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资；,3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去

2、做j工作。逻辑变量也是只允许取整数值的一类变量。,整数规划数学模型,【例1】企业计划生产2000件某种产品，该种产品可利用、设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。,1、生产安排问题,整数规划数学模型,变量 设xj表示在第 j（j=1,2,3）种设备上加工的产品数量，其生产费用为： 式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设01变量yj，令,1、生产安排问题,整数规划数学模型,当在第 j 种设备上加工，即 xj0 时,当不在第 j 种设备上加工，即 xj

3、=0 时,目标函数,约束条件,1、生产安排问题,整数规划数学模型,式中 是一个特殊的约束条件，显然当 xj0 时，yj=1, 当 xj0时，为使Z极小化，只有 yj=0 才有意义。,整数规划数学模型,2、投资组合问题,证券投资：把一定的资金投入到合适的有价证券上以规避风险并 获得最大的利润。 项目投资：财团或银行把资金投入到若干项目中以获得中长期的 收益最大。,【例2】选择投资场所,使收益最大？ Ai投资Bi元，收益Ci元，总投资B. 【解】设xi x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 B1x1 + B2x2 + + B7x7 B,南区,西区,东区,求解0-1规

4、划的隐枚举法,max z = C1x1 + C2x2 + + C7x7,2、投资组合问题,【例3】某财团 有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一次。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？,整数规划数学模型,2、投资组合问题,变量每个项目是否投资 约束总金额不超过限制 目标总收益最大,整数规划数学模型,3、背包问题,邮递包裹：把形状可变的包裹用尽量少的车辆运走 旅行背包：容量一定的背包里装尽可能的多的物品,【例4】某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据

5、需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,整数规划数学模型,3、背包问题,变量：对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第

6、i个物品是否放在第j个包裹中。,整数规划数学模型,3、背包问题,整数规划数学模型,3、背包问题,约束,包裹容量限制,必带物品限制,选带物品限制,目标函数未带物品购买费用最小,整数规划数学模型,2、背包问题,【例5】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少件，所装物品的总价值最大？,整数规划数学模型解的特点,【解】设甲、乙两种物品 各装x1、x2件，则数 学模型为：,不考虑x1、x2取整数的约束，称为上述规划的松弛问题，可行域如图； B为最优解：X(3.57，7.14)，Z35.7。 由于x1 、 x

7、2必须取整数值，可行解集只是图中可行域内的那些整数点； 凑整法：比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33； 实际问题的最优解是（5，5），Z=35。,整数规划数学模型解的特点,整数规划,松弛问题,可行域是离散集合，任意两个可行解的凸组合不一定为可行解 最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 一般，整数规划的最优解不会优于松弛问题的最优解 整数可行解远多余于顶点，枚举法不可取,整数规划数学模型解的特点,割平面法,纯整数线性规划 松弛问题,设aij(i=1,2,m; j=1,2,，n)和bi (i=1,

8、2,m)皆为整数，若不为整数，可以乘上一个倍数化的整数。,（3.1a）,（3.1b）,（3.1c）,（3.1d）,（3.1a）,（3.1b）,（3.1c）,在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。,割平面法,松弛问题的最优解,其中,若各 皆为整数，则X*为纯整数规划的最优解。, ,若各 不全为整数，则X*不是纯整数规划的可行解，非最优解。, ,割平面法 从X*的非整数分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题，形成一个新的线性规划，再求解。 若新的线性规划最优解满足整数要求，即为纯整数规划的最优解，否则，重复上述步骤，直到获得整

9、数最优解为止。 新加约束条件基本性质 已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，以使原来的非整数最优解不再出现。 凡整数可行解均满足该线性约束条件，以使整数最优解始终被保留在每次形成的线性规划可行域中。,割平面法,割平面法,在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。,m个约束方程可表示为,若其中的 不是整数，则式（3.2）中相应的约束方程为,（3.2）, ,(r),（3.3）,原松弛问题的最优解不可行,整数规划的整数可行解可行,最大整数与非负真分数之和,割平面法,得到新的整数规划,经验表明，若从最有单纯性表中选择具有最大分数部分的

10、非整数分量所在行构造割平面约束，往往可提高“切割”效果，减少“切割”次数。,割平面法,【例】求下列整数规划的最优解,【解】（1）松弛问题的最优表如下（单纯形法）,割平面法,最优解X=(5/2，13/4，0，0)T， x1 、x2不满足整数要求，选择x2行进行分割：,割平面法,（2）建立新约束条件,割平面法,（2）将新约束加入松弛问题最优单纯形表,割平面法,（2）将新约束加入松弛问题最优单纯形表,运用对偶单纯形法，继续计算，得到最优单纯形表,割平面法,aij0时,minj/aij,(-1/4)/(-1/2)=1/2,(-5/4)/(-1/2)=5/2, ,最优解X=(7/2，2，1，0，0)T，

11、 x1 不满足整数要求，进行分割：,割平面法, ,最优解X*=(4,1) Z=14,13/4, 5/2,松弛问题,割平面法,图解法,分支定界法,求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步； 任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整

12、数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,【例】用分支定界法求解下列规划。,分支定界法,【解】先求对应的松弛问题（记为LP0）：,运用图解法求解,10,10,松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,10,10,x1,x2,o,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,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,10,10,x1,x2,o,A,C,L

13、P1,3,4,6,LP4:X=(4,6),Z4=34,LP5:X=(5,5),Z5=35,5,LP3,尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。,上述分枝过程可用下图表示：,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,分支定界法,混合整数规划 只对整数变量分支，对非整数变量不分支 0-1

14、整数规划,作业,P146 5.1 5.2 5.3 5.4,求解0-1规划的隐枚举法,求解0-1规划的隐枚举法,找出任意一可行解，目标函数值为Z0； 原问题求最大值时，则增加一个约束 当原问题求最小值时，上式改为小于等于约束； 列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值； 目标函数值最大（最小）的解就是最优解。,(*),【解】（1）观察一个可行解x1 = 1 x2 = x3 = 0 此时，z = 3,（2）增加一个过滤条件 3x1-2x2+5x33 *,【例】用隐枚举法求解下列规划,求解0-1

15、规划的隐枚举法,max z = 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或1,46,（3）列表计算,求解0-1规划的隐枚举法,3x1-2x2+5x33 （*）,求解0-1规划的隐枚举法,【例】用隐枚举法求解下列规划,【解】容易求得X(1,0,0)是一可行解，Z06。加一个约束,由于3个变量每个变量取0或1，共有8种组合，用列表的方法检验每种组合解是否可行解，满足约束打上记号“”，不满足约束打上记号“ ”，计算如表。,由表知，X（1，0，1）是最优解，最优值Z9。,6,9,求

16、解0-1规划的隐枚举法,0-1规划,0-1变量及其应用 P134例7 例8,指派问题,指派问题的标准形式：有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。 引入n2个0-1变量： 数学模型,指派第i个人做第j件事,不指派第i个人做第j件事,(i,j=1,2,n),(i,j=1,2,n),(j=1,2,n),(i=1,2,n),指派问题,【例】人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。,【解】此工作分配问题可

17、以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！432124种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用01规划模型求解此类分配问题显得非常简单。,目标函数,指派问题,决策变量,2020年9月8日星期二,每项工作只能安排一人，约束条件,变量约束,要求每人做一项工作， 约束条件,指派问题,指派问题求解方法：匈牙利算法,匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于这两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利法。,假设问题求最小值，m个人恰好做m项工作，第i个人做第j项工作的

18、效率为cij，效率矩阵为cij 。,【定理1 】如果从分配问题效率矩阵cij的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵bij，若其中bij=cijuivj,则bij的最优解等价于cij的最优解。这里cij、bij均非负。,指派问题,【定理2 】 若矩阵A的元素可分成“ 0”与非“ 0”两部分，则覆盖“ 0”元素的最少直线数等于位于不同行不同列的“ 0”元素（称为独立元素）的最大个数。,如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理5.1告诉我们如何将效率表中的元素转换为有零元素，定理5.2告诉我们效率表中有多少个独立的“0”元素。,【例 】已知四人分别完成四项工作所需时间如下表，求最优分配方案。,指派问题,【解】最优分配方案是安排四人工作，使完成工作总时间最少，最小值问题。,第一步：找出效率矩阵每行最小元素，每行分别减去其最小元素,Min 3 4 0 8,第二步：找出效率矩阵每列最小元素，每列分别减去其最小元素,Min,指派问题,第三步：用最少的直线覆盖所有“0”，得,第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算。,（