整数规划精美管理.ppt

整 数 规 划(Integer Programming),第一节.整数规划问题的提出,一、整数规划的一般形式,1、实例：,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表51：,问两种货物各托运多少箱，可使获得的利润为最大？,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),(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步:修改上、下界.,修改下界：每求出一次符合整数条件的可行解时,都要考虑修改下界,选择迄今为止最好的整数可行解,相应的目标函数值作下界,(2)修改上界：每求解完一对分枝,都要考虑修改上界 上界的值应是迄今为止所有未被分枝的问题的目标函数值中最大的一个.,在每解完一对分枝、修改完上、下界 和 后,若已有 此时所有分枝均已查明,即得到了问题 的最优值,求解结束.,若仍有,则说明仍有分枝没查明,需要继续分枝,回到第4步,运算步骤,解松弛问题,满足要求?,结束,分枝,Y,N,选一分支写出并求解松弛问题,判定是否为整数解,初始分支为可行解集，初始界为无穷,判定是否分支集空,Y停止,当前最好解为最优解,N,Y,判定最优值是否优于当前界,判定最优值是否优于当前界,按非整数变量分支并加入分支集,以最优解替代当前最好解最优值替代当前界,Y,Y,N,剪枝,N,N,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，只有少数特殊问题有好的算法。,练习：用分枝定界法求解整数规划问题,x11,x12,x22,x23,x12,x13,例：用割平面法求解整数规划问题,解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：,此题的最优解为：X=(1,3/2)Z=3/2 但不是整数最优解。看x2所在行。,将系数和常数项分解,由于x2，x3，x4为非负整数，等式右端为整数，（）内为正，左端必为负数。所以，有：,这就得出了一个切割方程，将它作为增加约束条件。,现将生成的割平面条件加入松弛变量，然后加到表中：,此时，X1(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：,将生成的割平面条件加入松弛变量，然后加到表中：,至此得到最优表，其最优解为 X=(1,1),Z=1,这也是原问题的最优解。,有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。,把(2)(3)代入(1)并移项得：,例 写出下列问题的切割方程,解：,例：用割平面法求解数规划问题,初始表,最优表,在松弛问题最优解中，x1,x2 均为非整数解，由上表有：,将系数和常数都分解成整数和非负真分数之和,以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：,引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：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 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。,由上表可知，问题的最优解为 X*=(x1=1 x2=0 x3=1)由上表可知：x1=0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x12 x25 x3 5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。,隐枚举法求解0-1整数规划的思路,3、不断更换过滤条件,1、把目标函数的系数按升序排列max，约束条件做相应调整；,2、把所有的整解x按一定的次序排列,例：用隐枚举法求解下列0-1规划问题,解：,目标函数的系数按升序排列,通过试探可行解(x1,x2,x3)=(1,0,0)引入下列过滤条件：,改进过滤条件：,改进过滤条件：,为了选修课程门数最少，应学习哪些课程？,选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课，2门计算机课。,先修课程要求,最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分21,约束条件,x3=1必有x1=x2=1,【模型求解】,（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元素都被圈出和划掉为止。,(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n,则转入下一步。第三步：作最少的直线覆盖所有0元素。(1)对没有的行打号；(2)对已打号的行中所有含元素的列打号；(3)再对打有号的列中含 元素的行打号；,(4)重复(2)，(3)直到得不出新的打号的行、列为止；(5)对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 lm n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。,例一：,2,4,9,7,4,2,有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,例二、,求解过程如下：第一步，变换系数矩阵：,5,第二步，试指派：,找到 3 个独立零元素 但 m=3 n=4,第三步，作最少的直线覆盖所有0元素：,独立零元素的个数m等于最少直线数l，即lm=3n=4；,第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打各行都减去1；打各列都加上1，得如下矩阵，并转第二步进行试指派：,得到4个独立零元素，所以最优解矩阵为：,15,练习：,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,费 工作 用人员,-1,-2,l=m=4 n=5,l=m=4 n=5,此问题有多个最优解,28,用匈牙利法求解下列指派问题，已知效率矩阵分别如下：,