《整数规划精美管理》PPT课件.ppt

整 数 规 划 (Integer Programming) 第一节.整数规划问题的提出 一、整数规划的一般形式 1、实例： 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体 积、重量、可获利润以及托运所受限制如表51： 货物体积 每箱（米3） 重量 每箱（百斤） 利润 每箱（百元） 甲 乙 5 4 2 5 20 10 托运限制 24 13 问两种货物各托运多少箱，可使获得的利润为最大？ 2、整数规划一般形式 解：设托运甲、乙两种货物x1，x2箱，用 数学式可表示为： 整数规划的数学模型 一般形式 依照决策变量取整要求的不同，整数规划可分为纯整 数规划、全整数规划、混合整数规划、01整数规划 。 纯整数规划：所有决策变量要求取非负整 数（这时引进的松弛变量和剩余变量可以不要 求取整数）。 全整数规划：除了所有决策变量要求取非负 整数外，系数aij和常数bi也要求取整数（这时引 进的松弛变量和剩余变量也必须是 整数）。 混合整数规划：只有一部分的决策变量要 求取非负整数，另一部分可以取非负实数。 01整数规划：所有决策变量只能取 0 或 1 两个整数。 整数规划与线性规划的关系 从数学模型上看整数规划似乎是线 性规划的一种特殊形式，求解只需在线 性规划的基础上，通过舍入取整，寻求 满足整数要求的解即可。但实际上两者 却有很大的不同，通过舍入得到的解（ 整数）也不一定就是最优解，有时甚至 不能保证所得倒的解是整数可行解。 举例说明。 例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称 为松弛问题）。 用 解法求出最优解 x13/2, x2 = 10/3 且有Z = 29/6 x1 x2 3 3 (3/2,10/3) 现求整数解（最优解） ：如用“舍入取整法”可得 到4个点即(1，3) (2， 3)(1，4)(2，4)。显然， 它们都不可能是整数规划 的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题 的可行域内且为整数点。故整数规划问题的可行解集 是一个有限集，如图所示。 图 因此，可将集合内的整数点一一找出，其最 大目标函数的值为最优解，此法为完全枚举法 。 如上例：其中（2，2）（3，1）点为最 大值，Z=4。 目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的01规划问题采用隐枚举法和匈 牙利法。 在20世纪60年代初 Land Doig 和 Dakin 等人提出了 分枝定界法.由于该方法灵活且便于用计算机求解, 所以目前已成为解整数规划的重要方法之一.分枝 定界法既可用来解纯整数规划,也可用来解混合整 数规划. 分枝定界法的主要思路是首先求解整数规划的伴 随规划（整数规划的松弛问题） ,如果求得的最优 解不符合整数条件,则增加新约束缩小可行域 ;将原整数规划问题分枝分为两个子规划,再 解子规划的伴随规划通过求解一系列子规划 的伴随规划及不断地定界 .最后得到原整数规划问 题的整数最优解 . 分枝定界法 基本思路 考虑纯整数问题： 整数问题的松弛问题 ： 例 某公司计划建筑两种类型的宿舍.甲种每幢占地 0.25 103m2, 乙种每幢地0.4103m2.该公司拥有 土地3103m2. 计划甲种宿舍不超过 8 幢,乙种宿 舍不超过4幢.甲种宿舍每幢利润为10万元，乙 种宿舍利润为每幢20万元.问该公司应计划甲、 乙两种类型宿舍各建多少幢时,能使公司获利最 大 ? 解 设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题 数学模型为 : 这是一个纯整数规划问题,称为问题 。将(1)中约束 条件的系数全化为整数,改为： （1） 然后去掉整数条件,得到问题 的伴随规划 (2), 称之为 问题 （2） 用单纯形法求解问题 , 得到最优解及最优值： 1. 计算原问题 目标函数值的初始上界 因为问题 的最优解不满足整数条件,因此 不是问题 的最优解,又因为 的可行域 问题 的可行域 , 故问题 的最优值不会超过问题 的最优值. 即有 因此可令 作为 的初始上界 即 一般说来,若问题 无可行解,则问题 也无可行解,停止计 算。若问题 的最优解 满足问题 的整数 条件,则 也是问题 的最优解,停止计算. 2. 计算原问题 目标函数值的初始下界 若能从问题 的约束条件中观察到一个整数可行解,则可将 其目标函数值作为问题 目标函数值的初始下界,否则可令 初始下界Z=-.给定下界的目的,是希望在求解过程中寻找 比当前 更好的原问题的目标函数值 . 对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0. 问 题 的最优目标函数值决不会比它小,故可令 =0. 3. 增加约束条件将原问题分枝 当问题 的最优解 不满足整数条件时,在 中任选一个 不符合整数条件的变量.如本例选 显然问题 的 整数最优解只能是 或 ,而绝不会在5与6之间. 因此当将可行域 切去 部分时,并没有切去 的 整数可行解.可以用分别增加约束条件 及 来达 到在 切去 部分的目的. 切去 后就分 为 及 两部分,即问题 分为问题 及问题 两枝子 规划. 问题 问题 作出问题 的伴随规划 则问题 的可行 域为 见图2(b). 以下我们将由同一问题分解出的两 个分枝问题称为“一对分枝“. 4. 分别求解一对分枝 在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现 以下几种可能: ( a ) (a)(b) 图2 (1 ) 无可行解 若无可行解,说明该枝情况己查明,不需要由此分枝再继续 分枝,称该分枝为 “树叶”，剪枝。 (2) 得到整数最优解 若求得整数最优解，则该枝情况己查明,不需要再对此继续 分枝，该分枝也是 “树叶“. (3) 得到非整数最优解 若求得某个分枝问题得到的是不满足整数条件的最优解， 该最优解的目标函数值Z小于当前的下界 ，则该 枝内不可能含有原问题的整数最优解，称为“枯枝”，需 剪掉。 该最优解的目标函数值Z大于当前的下界 ，则仍 需对该枝继续分枝，以查明该分枝内是否有目标函数值比 当前的 更好的整数最优解。 本例中问题 及问题 的模型及求解结果 如下： 还要区分两种情况： 问题 问题 解为: 解为: 问题 的解 是整数最优解,它当然也是问题 的整数可行解,故 的整数最优解 即此时可将 修改为: 同时问题 也被查清, 成为“树叶”。 因为 ,不满足整数条件, 故问题 分别增加约 束条件： 及 。分为 与 两枝, 建立相应的 伴随规划问题 与 问题问题 它们的可行域分别为 见图3。 图3 因为 ，问题 无可行解，此问题已 是“树叶“, 已被查清. 求解问题 , 得到最优解 5. 修改上、下界 与 (l) 修改下界 修改下界的时机是:每求出一个整数可行解时,都要作修改 下界 的工作. 修改下界 的原则:在至今所有计算出的整数可行解中,选 目标函数值最大的那个作为最新下界 。 因此在用分枝定界法的求解全过程中,下界 是不断增大的. (2) 修改上界 上界 的修改时机是:每求解完一对分枝,都要考虑修改上界 修改上界 的原则是:挑选在迄今为止所有未被分枝的问题的 目标函数值中最大的一个作为新的上界.新的上界 应该小于 原来的上界 . 在分枝定界法的整个求解过程中,上界的值在不断减小. 问题问题 解为: 因为此时 的解为整数解,因此修改下界为 =130, 而此 时所有未被分枝的问题( )的目标函数值中最大的 为 , 故修改上界 =130. 6. 结束准则 当所有分枝均已查明(或无可行解“树叶”, 或为整数可 行解“树叶”,或其目标函数值不大于下界 ”枯枝” ） 且此时 ，则已得到了原问题的整数最优 解，即目标函数值为下界 的那个整数解 . 在本例中,当解完一对分枝 后, 得到 又 是“树叶“, 为“枯枝“, 因此所有分枝( ) 均已查明.故已得到问题 的最优解: 或 故该公司应建甲种宿舍7幢乙种宿舍3幢; 或甲种5幢、乙 种4幢时,获利最大.获利为130万元. 可将本例的求解过程与结果用图5 来描述. 问题 问题问题 问题问题 问题问题 不可行 分枝规则 情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的解进行比较，结论如情况 4 或 5 下面将分枝定界法求解混合型整数规划的计算步骤归纳如下: 第1步:将原整数线性规划问题称为问题 .去掉问题 的整数条件,得到伴随规划问题 第2步:求解问题 , 有以下几种可能: (l) 没有可行解, 则 也没有可行解, 停止计算。 (2) 得到 的最优解, 且满足问题 的整数条件, 则 的 最优解也是 的最优解, 停止计算. (3) 得到不满足问题 的整数条件的 的最优解,记它的 目标函数值为 , 这时需要对问题 (从而对问题 ) 进 行分枝, 转下一步。 (3) 得到不满足问题 的整数条件的 的最优解, 记它的目 标函数值为 , 这时需要对问题 ( 从而对问题 ) 进行分 枝 , 转下一步 . 第3步:确定初始上下界 与 . 以 作为上界 . 观察出问题 的一个整数可行解,将其 目标函数值记为下界 . 若观察不到,则可记 = -.转 下一步. 第4步: 将问题 分枝. 在 的最优解 中,任选一个不符合整数条件的变量 , 其值为 , 以 表示小于 的最大整数.构造两 个约束条件: 将这两个约束条件分别加到问题 的约束条件集中,得到 的两个分枝:问题 与 对每个分枝问题求解,得到以下几种可能: (1) 分枝无可行解该分枝是 “ 树叶 “. (2) 求得该分枝的最优解, 且满足 的整数条件. 将该最 优解的目标函数值作为新的下界 , 该分枝也是“树叶“. (3) 求得该分枝的最优解,且不满足 的整数条件,但其目 标函数不大于当前下界 , 则该分枝是“枯枝”需要剪枝. (4) 求得不满足 整数条件的该分枝的最优解,且其目标 函数值大于当前下界 ,则该分枝需要继续进行分枝. 若得到的是前三种情形之一,表明该分枝情况已探明,不需要 继续分枝. 若求解一对分枝的结果表明这一对分枝都需要继续分枝,则 可先对目标函数值大的那个分校进行分枝计算,且沿着该分 枝一直继续进行下去,直到全部探明情况为止.再返过来求解 目标函数值较小的那个分枝. 第6步:修改上、下界. (1) 修改下界 ：每求出一次符合整数条件的可行解时, 都要考虑修改下界 , 选择迄今为止最好的整数可行解 相应的目标函数值作下界 (2) 修改上界 ：每求解完一对分枝,都要考虑修改上界 上界的值应是迄今为止所有未被分枝的问题的目标函数值 中最大的一个. 在每解完一对分枝、修改完上、下界 和 后,若已有 此时所有分枝均已查明,即得到了问题 的最优值 求解结束. 若仍有 ,则说明仍有分枝没查明,需要继续分枝, 回 到第4步 运算步骤 解松弛问题 满足要求? 结束 分枝 Y N 选一分支写出并求解松弛问题 判定是否 为整数解 初始分支为可行解集，初始界为无穷 判定是否 分支集空 Y停止 当前最好解为最优解 N Y 判定最优值是否 优于当前界 判定最优值是否 优于当前界 按非整数变量分支并加入分支集 以最优解替代当前最好解最优值替代当前界 Y Y N 剪枝 N N 求解混合整数规划问题，只对整数变量 分支，对非整数变量不分支。 可能存在两个分枝都是非整数解的情况 ，则需要两边同时继续分枝，直到有整 数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即 广又深，在最坏情况下相当于组合所有 可能的整数解 一般整数规划问题属于一类未解决的难 题，只有少数特殊问题有好的算法。 练习：用分枝定界法求解整数规划问题 LP1 x1=1, x2=7/3 Z(1) 10/3 LP x1=3/2, x2=10/3 Z(0) 29/6 LP2 x1=2, x2=23/9 Z(2) 41/9 x11 x12 LP3 x1=33/14, x2=2 Z(3) 61/14 LP4 无可 行解 x22x23 LP7 x1=2, x2=2 Z(7) 4 LP8 x1=3, x2=1 Z(8) 4 x12 x13 例：用割平面法求解整数规划问题 解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和 最优单纯形表： Cj0100 CBXBbx1x2x3x4 0x363210 0x40-3201 Z00100 Cj0100 CBXBbx1x2x3x4 0x11101/6-1/6 1x23/2011/41/4 Z-3/2 00 -1/4 -1/4 此题的最优解为：X =(1 , 3/2) Z = 3/2 但不是 整数最优解。看x2所在行。 将系数和常数项分解 由于x2，x3，x4为非负整数，等式右端为整数，（）内 为正，左端必为负数。所以，有： 这就得出了一个切割方程，将它作为增加约束条件。 Cj01000 CBXBbx1x2x3x4s1 0x11101/6-1/60 1x23/2011/41/40 0s1-1/200-1/4-1/41 Z-3/200-1/4-1/40 现将生成的割平面条件加入松弛变量，然后加到表中 ： CBXBbx1x2x3x4s1 0x12/3100-1/32/3 1x2101001 0x320011-4 Z-10000-1 此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以x1为源 行生成割平面，其条件为： 将生成的割平面条件加入松弛变量，然后加到表中： CBXBbx1x2x3x4s1s2 0x12/3100-1/32/30 1x21010010 0x320011-40 0s2-2/3000-2/3-2/31 Z-10000-10 CBXBbx1x2x3x4s1s2 0x10100-101 1x20010-103/2 0x3600150-6 0s1100011-3/2 Z000010-3/2 CBXB bx1x2x3x4s1s2 0x1110001-1/2 1x21010010 0x310010-53/2 0x4100011-3/2 Z -10000-10 至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这 也是原问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过 程中始终保持对偶可行性，因此，这个算法也称为分 数对偶割平面算法。 把(2)(3)代入(1)并移项得 ： 例 写出下列问题的切割方程 Cj6400 CBxBbx1x2x3x4 4x22011/3-1/3 6x15/210-1/62/3 -2300-1/3-8/3 解： 例：用割平面法求解数规划问题 Cj1100 CBXBbx1x2x3x4 0x362110 0x4204501 Z1100 CBXBbx1x2x3x4 1 x15/3105/61/6 1x28/3012/31/3 Z-13/3001/61/6 初 始 表 最 优 表 在松弛问题最优解中，x1, x2 均为非整数解，由上表 有： 将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，考虑 式子右端最大真分数的式子，往往会较快地找到所需 割平面约束条件。以上两个式子右端真分数相等，可 任选一个考虑。现选第二个式子，并将真分数移到右 边得： 引入松弛变量s1 后得到下式，将此约束条件加到上表 中，继续求解。 Cj 11000 CBXBbx1x2x3x4s1 1 x1 5/3105/61/60 1 x2 8/3012/31/30 0 s1 2/3001/31/31 Z 13/3001/61/60 Cj 11000 CBXBbx1x2x3x4s1 1 x1 010010 1 x2 401012 0 x3 200113 Z 400001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划 有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 0-1整数规划 一、问题的提出 1、实例 例 某公司拟在市东、西-南三区建立门市部。拟议中 有7个位置（点）Ai供选择。规定 在东区，由A1,A2,A3三个点中至多选两个； 在西区，由A4,A5两个点中至少选一个； 在南区，由A6,A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估 计为ci元，但投资总额不能超过B元。问应选择那几个 点可使年利润为最大？ 则0-1规划模型为： 2、0-1整数规划的一般形式 01 整数规划是一种特殊形式的整数规划，这时的 决策变量xi 只取两个值0或1，一般的解法为隐枚举法 例：求解下列01 规划问题 解：对于01 规划问题，由于每个变量只取0，1两个 值，一般会用穷举法来解，即将所有的0，1 组合找出 ，使目标函数达到极值要求就可求得最优解。但此法 太繁琐，工作量相当大。而隐枚举法就是在此基础上 ，通过加入一定的条件，就能较快的求得最优解。 x1 . x2. x3约束条件满足条件Z 值 (1) (2) (3) (4)是 否 ( 0. 0. 0 ) 0 0 0 00 ( 0. 0. 1 ) 1 1 0 15 ( 0. 1. 0 ) 2 4 1 42 ( 1. 0. 0 ) 1 1 1 03 ( 0. 1. 1 ) 1 5 ( 1. 0. 1 ) 0 2 1 18 ( 1. 1. 0 ) 3 ( 1. 1. 1 ) 2 6 由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快 找到最优解，可将3 x12 x25 x3 5 作为一个约束， 凡是目标函数值小于5 的组合不必讨论，如下表。 x1 . x2. x3约束条件满足条件Z 值 (0) (1) (2) (3) (4)是 否 ( 0. 0. 0 ) 0 0 0 0 00 ( 0. 0. 1 ) 5 1 1 0 15 ( 0. 1. 0 )-2 ( 0. 1. 1 ) 3 ( 1. 0. 0 ) 3 ( 1. 0. 1 ) 8 0 2 1 18 ( 1. 1. 0 ) 1 ( 1. 1. 1 ) 4 隐枚举法求解0-1整数规划的思路 3、不断更换过滤条件 1、把目标函数的系数按升序排列max，约束条件做相应调整； 2、把所有的整解x按一定的次序排列 例： 用隐枚举法求解下列0-1规划问题 解： 目标函数的系数按升序排列 通过试探可行解(x1,x2,x3)=(1,0,0) 引入下列过滤条件： 点 (x2,x1,x3 ) 条 件 是否 满足 条件 Z值 (0) (1) (2) (3) (4) (0,0,0) (0,0,1) 0 5 -1 1 0 1 否 是 0 5 改进过滤条件： 点 (x2,x1,x3 ) 条 件 是否 满足 条件 Z值 (0) (1) (2) (3) (4) (0,1,0) (0,1,1) 3 8 0 2 1 1 否 是 8 改进过滤条件： 点 (x2,x1,x3 ) 条 件 是否 满足 条件 Z值 (0) (1) (2) (3) (4) (1,0,0) (1,0,1) (1,1,0) (1,1,1) -2 3 1 6 否 否 否 否 为了选修课程门数最少，应学习哪些课程 ？ 选课策略 要求至少选两门数学课、三门运筹学课和两门计算机课 课号课名学分所属类别先修课要求 1微积分5数学 2线性代数4数学 3最优化方法4数学；运筹学微积分；线性代数 4数据结构3数学；计算机计算机编程 5应用统计4数学；运筹学微积分；线性代数 6计算机模拟3计算机；运筹学计算机编程 7计算机编程2计算机 8预测理论2运筹学应用统计 9数学实验3运筹学；计算机微积分；线性代数 0-1规划模型 决策变量 目标函数 xi=1 选修课号i 的 课程（xi=0 不选） 选修课程总数最少 约束条件 最少2门数学课， 3门运筹学课， 2门计算机课。 课号课名所属类别 1微积分数学 2线性代数数学 3最优化方法数学；运筹学 4数据结构数学；计算机 5应用统计数学；运筹学 6计算机模拟计算机；运筹学 7计算机编程计算机 8预测理论运筹学 9数学实验运筹学；计算机 先修课程要求 最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21 约束条件 x3=1必有x1 = x2 =1 课号课名先修课要求 1微积分 2线性代数 3最优化方法微积分；线性代数 4数据结构计算机编程 5应用统计微积分；线性代数 6计算机模拟 计算机编程 7计算机编程 8预测理论应用统计 9数学实验微积分；线性代数 【模型求解】 （0 . 1 . 1 . 0 . 0） 练习：用隐枚举法求解01规划问题 指派问题 一、问题的提出 1、实例 有四个熟练工人，他们都是多面手，有四项任务要他们完成 。若规定每人必须完成且只完成一项任务，而每人完成每 项任务的工时耗费如下表所示，问如何分配任务使完成四 项任务的总工时耗费最少？ 解：设 则此指派问题的模型为 第一个约束说明第i个人只能完 成一个任务。 第二个约束说明第j项任务只能 由一人完成。 在实际中经常会遇到这样的问题，有n 项不同的任务 ，需要n 个人分别完成其中的一项，但由于任务的性质 和各人的专长不同，因此各人去完成不同的任务的效 率（或花费的时间或费用）也就不同。于是产生了一 个问题，应指派哪个人去完成哪项任务，使完成 n 项 任务的总效率最高（或所需时间最少），这类问题称 为指派问题或分派问题。 （一）、指派问题的数学模型 设n 个人被分配去做n 件工作，规定每个人只做一件 工作，每件工作只有一个人去做。已知第I 个人去做第 j 件工作的的效率（ 时间或费用）为 Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能 使总效率（ 时间或费用）最高？ 设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( I,j=1.2. n ) 其数学模型为： 二、求解指派问题的理论依据 指派问题的一般形式 1、指派问题是一个特殊的运输问题 2、Koing定理：在原指派问题的效益矩阵中同行同列加上某一 常数，所得指派问题与原问题同解。 证明： （二）、解题步骤： 指派问题是0-1 规划的特例，也是运输问题的特例 ，当然可用整数规划，0-1 规划或运输问题的解法去 求解，这就如同用单纯型法求解运输问题一样是不合 算的。利用指派问题的特点可有更简便的解法，这就 是匈牙利法，即系数矩阵中独立 0 元素的最多个数等 于能覆盖所有 0 元素的最少直线数。 第一步：变换指派问题的系数矩阵（cij）为(bij)，使 在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最 小元素。 第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独 立0元素(不同行不同列的零元素），就以这n个独立0元 素对应解矩阵(xij)中的元素为1，其余为0，这就得到最 优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加 圈，记作 。然后划去 所在列(行)的其它0元素，记 作 ；这表示这列所代表的任务已指派完,不必再考虑 别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作 ；然后划去 所在行的0元素，记作 . (3)反复进行(1)，(2)两步，直到尽可能多的0元素都 被圈出和划掉为止。