整数规划精美管理 .ppt

整整数数规规划划(IntegerProgramming)第一节第一节.整数规划整数规划问题的提出问题的提出一、整数规划的一般形式一、整数规划的一般形式1、实例：、实例：例例1 1 某厂拟用集装箱托运甲乙两种货物，每箱的体某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表积、重量、可获利润以及托运所受限制如表51：货物货物体积体积每箱（米每箱（米3 3）重量重量每箱（百斤）每箱（百斤）利润利润每箱（百元）每箱（百元）甲甲 乙乙54252010托运限制托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？问两种货物各托运多少箱，可使获得的利润为最大？2、整数规划一般形式、整数规划一般形式解：设托运甲、乙两种货物解：设托运甲、乙两种货物x1，x2箱，用箱，用数学式可表示为：数学式可表示为：整数规划的数学模型整数规划的数学模型一般形式一般形式 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。整数规划。纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要数（这时引进的松弛变量和剩余变量可以不要求取整数）。求取整数）。全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时引也要求取整数（这时引进的松弛变量和剩余变量也必须是进的松弛变量和剩余变量也必须是整数）。整数）。混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。01整数规划：整数规划：所有决策变量只能取所有决策变量只能取0或或1两个整数两个整数。整数规划与线性规划的关系整数规划与线性规划的关系从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。至不能保证所得倒的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。用用解法求出最优解解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它。显然，它们都不可能是整数规划的们都不可能是整数规划的最优解。最优解。按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。在在20世纪世纪60年代初年代初LandDoig和和Dakin等人提出了等人提出了分分枝枝定界法定界法.由于该方法灵活且便于用计算机求解由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一所以目前已成为解整数规划的重要方法之一.分分枝枝定界法既可用来解纯整数规划定界法既可用来解纯整数规划,也可用来解混合整也可用来解混合整数规划数规划.分枝定界法的主要思路是首先求解整数规划的伴分枝定界法的主要思路是首先求解整数规划的伴随规划随规划（整数规划的松弛问题）（整数规划的松弛问题）,如果求得的最优如果求得的最优解不符合整数条件解不符合整数条件,则增加新则增加新约约束束缩小可行域缩小可行域;将原整数规划问题分将原整数规划问题分枝枝分为两个子规划分为两个子规划,再再解子规划的伴随规划解子规划的伴随规划通过求解一系列子规划通过求解一系列子规划的伴随规划及不断地定界的伴随规划及不断地定界.最后得到原整数规划问最后得到原整数规划问题的整数最优解题的整数最优解.分枝定界法分枝定界法基本思路基本思路考虑纯整数问题：考虑纯整数问题：整数问题的松弛问题：整数问题的松弛问题：例某公司计划建筑两种类型的宿舍某公司计划建筑两种类型的宿舍.甲种每幢占地甲种每幢占地0.25103m2,乙种每幢地乙种每幢地0.4103m2.该公司拥有该公司拥有土地土地3103m2.计计划划甲种宿舍不超过甲种宿舍不超过8幢幢,乙种宿乙种宿舍不超过舍不超过4幢幢.甲种宿舍每幢利润为甲种宿舍每幢利润为10万元万元，乙乙种宿舍利润为每幢种宿舍利润为每幢20万元万元.问该公司应计划甲、问该公司应计划甲、乙两种类型宿舍各建多少幢时乙两种类型宿舍各建多少幢时,能使公司获利最能使公司获利最大大?解解设计划甲种宿舍建设计划甲种宿舍建幢幢,乙种宿舍建乙种宿舍建幢幢,则本题数则本题数学模型为学模型为:这是一个纯整数规划问题这是一个纯整数规划问题,称为问题称为问题。将将(1)中约束中约束条件条件的系数全化为整数的系数全化为整数,改为改为：（1）然后去掉整数条件然后去掉整数条件,得到问题得到问题 的的伴随规划伴随规划 (2),(2),称之为称之为问题问题（2）用单纯形法求解问题用单纯形法求解问题 ,得到最优解及最优值得到最优解及最优值：1.计算原问题计算原问题 目标函数值的初始上界目标函数值的初始上界 因为问题因为问题 的最优解不满足整数条件的最优解不满足整数条件,因此因此 不是问题不是问题 的最优解的最优解,又因为又因为 的可行域的可行域 问题问题 的可行域的可行域 ,故问题故问题 的最优值不会超过问题的最优值不会超过问题 的最优值的最优值.即有即有因此可令因此可令 作为作为 的初始上界的初始上界即即一般说来一般说来,若问题若问题 无可行解无可行解,则问题则问题 也无可行解也无可行解,停止计停止计算算。若问题若问题 的最优解的最优解 满足问题满足问题 的整数的整数条件条件,则则 也是问题也是问题 的最优解的最优解,停止计算停止计算.2.计算原问题计算原问题 目标函数值的初始下界目标函数值的初始下界若能从问题若能从问题 的约束条件中观察到一个整数可行解的约束条件中观察到一个整数可行解,则可将则可将其目标函数值作为问其目标函数值作为问题题 目标函数值的初始下界目标函数值的初始下界,否则可令否则可令初始下界初始下界Z=Z=-.给定下界的目的给定下界的目的,是希望在求解过程中寻找是希望在求解过程中寻找比当前比当前 更好的原问题的目标函数值更好的原问题的目标函数值 .对于本例对于本例,很容易得到一个明显的可行解很容易得到一个明显的可行解X=(0,0)X=(0,0)T T,Z=0.,Z=0.问问题题 的最优目标函数值决不会比它小的最优目标函数值决不会比它小,故可令故可令 =0.=0.3.增加约束条件将原问题分枝增加约束条件将原问题分枝当问题当问题 的最优解的最优解 不满足整数条件时不满足整数条件时,在在 中任选一个中任选一个不符合整数条件的变量不符合整数条件的变量.如本例选如本例选 显然问题显然问题 的的整数最优解只能是整数最优解只能是 或或 ,而绝不会在而绝不会在5 5与与6 6之间之间.因此当将可行域因此当将可行域 切去切去 部分时部分时,并没有切去并没有切去 的的整数可行解整数可行解.可以用分别增加约束条件可以用分别增加约束条件 及及 来达来达到在到在 切去切去 部分的目的部分的目的.切去切去 后就分后就分为为 及及 两部分两部分,即问题即问题 分为问题分为问题 及问题及问题 两枝子两枝子规划规划.问题问题 问题问题 作出问题作出问题 的伴随规划的伴随规划 则问题则问题 的可行的可行域域为 见图见图2(b).2(b).以下我们将由同一问题分解出的两以下我们将由同一问题分解出的两个分个分枝枝问题称为问题称为 一对分枝一对分枝.4.分别求解一对分枝分别求解一对分枝在一般情况下在一般情况下,对某个分枝问题对某个分枝问题(伴随规划伴随规划)求解时求解时,可能出现可能出现以下几种可能以下几种可能:(a)(a)(b)图2(1)无可行解无可行解若无可行解若无可行解,说明该枝情况己查明说明该枝情况己查明,不需要由此分枝再继续不需要由此分枝再继续分枝分枝,称该称该分枝为分枝为 “树叶树叶”，剪枝。，剪枝。(2)得到整数最优解得到整数最优解若求得整数最优解，则若求得整数最优解，则该枝情况己查明该枝情况己查明,不需要不需要再对再对此继续此继续分枝分枝，该该分枝也是分枝也是 树叶树叶.(3)得到非整数最优解得到非整数最优解若求得某个若求得某个分枝分枝问题得到的是不满足整数条件的最优解，问题得到的是不满足整数条件的最优解，该最优解的目标函数值该最优解的目标函数值Z Z小于当前的下界小于当前的下界 ，则该，则该枝内不可能含有原问题的整数最优解，称为枝内不可能含有原问题的整数最优解，称为“枯枝枯枝”，需需剪掉。剪掉。该最优解的目标函数值该最优解的目标函数值Z Z大于当前的下界大于当前的下界 ，则仍，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的当前的 更好的整数最优解。更好的整数最优解。本例中问题本例中问题 及问题及问题 的模型及求解结果的模型及求解结果如下：如下：还要区分两种情况：还要区分两种情况：问题问题解为:解为:问题问题 的解的解 是整数最优解是整数最优解,它当然也是问题它当然也是问题 的整数可行解的整数可行解,故故 的整数最优解的整数最优解即此时可将即此时可将 修改为修改为:同时问题同时问题 也被查清也被查清,成为成为“树叶树叶”。因为因为 ,不满足整数条件不满足整数条件,故问题故问题 分别增加约分别增加约束条件束条件：及及 。分为分为 与与 两两枝枝,建立相应的建立相应的伴随规划伴随规划问题问题 与与问题问题它们的可行域分别为 见图3。图3因为因为 ，问题问题无可行解无可行解，此问题此问题已已是是 树叶树叶,已被查清已被查清.求解问题求解问题 ,得到最优解得到最优解 5.修改上、下界修改上、下界 与与(l)修改下界修改下界 修改下界的时机是修改下界的时机是:每求出一个整数可行解时每求出一个整数可行解时,都要作修改都要作修改下界下界 的工作的工作.修改下界修改下界 的原则的原则:在至今所有计算出的在至今所有计算出的整数可行解整数可行解中中,选选目标函数值最目标函数值最大大的那个作为最新下界的那个作为最新下界 。因此在用分枝定界法的求解全过程中因此在用分枝定界法的求解全过程中,下界下界 是不断增大的是不断增大的.(2)修改上界修改上界 上界上界 的修改时机是的修改时机是:每求解完一对分枝每求解完一对分枝,都要考虑修改上界都要考虑修改上界修改上界修改上界 的原则是的原则是:挑选在迄今为止所有挑选在迄今为止所有未被分枝未被分枝的问题的的问题的目标函数值中最目标函数值中最大大的一个作为新的上界的一个作为新的上界.新的上界新的上界 应该小于应该小于原来的上界原来的上界 .在分枝定界法的整个求解过程中在分枝定界法的整个求解过程中,上界的值在不断减小上界的值在不断减小.问题问题解为解为:因为此时因为此时 的解为整数解的解为整数解,因此修改下界为因此修改下界为=130,而此而此时所有未被分枝的问题时所有未被分枝的问题()的目标函数值中最大的的目标函数值中最大的为为 ,故修改上界故修改上界 =130.=130.6.结束准则结束准则当所有分当所有分枝枝均已查明均已查明(或无可行解或无可行解“树叶树叶”,或为整数可或为整数可行解行解“树叶树叶”,或其目标函数值不大于下界或其目标函数值不大于下界 ”枯枝枯枝”）且此时且此时 ，则已得到了原问题的整数最优则已得到了原问题的整数最优 解，解，即目标函数值为下界即目标函数值为下界 的那个整数解的那个整数解 .在本例中在本例中,当解完一对当解完一对分枝分枝 后后,得到得到 又又 是是 树叶树叶,为为 枯枝枯枝,因此所有分枝因此所有分枝()均已查明均已查明.故已得到问题故已得到问题 的最优解的最优解:或故该公司应建甲种宿舍故该公司应建甲种宿舍7 7幢乙种宿舍幢乙种宿舍3 3幢幢;或甲种或甲种5 5幢、乙幢、乙种种4 4幢时幢时,获利最大获利最大.获利为获利为130130万元万元.可将本例的求解过程与结果用图可将本例的求解过程与结果用图5 5 来描述来描述.问题问题问题问题问题问题问题不可行分枝规则情况情况2,4,5找到最优解找到最优解情况情况3在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况6问题问题1的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题2的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况4或或5下面将分下面将分枝枝定界法求解混合型整数规划的计算步骤归纳如下定界法求解混合型整数规划的计算步骤归纳如下:第第1 1步步:将原整数线性规划问题称为问题将原整数线性规划问题称为问题 .去掉问题去掉问题的整数条件的整数条件,得到伴随规划问题得到伴随规划问题 第第2 2步步:求解问题求解问题 ,有以下几种可能有以下几种可能:(l)(l)没有可行解没有可行解,则则 也没有可行解也没有可行解,停止计算停止计算。(2)得到得到 的最优解的最优解,且满足问题且满足问题 的整数条件的整数条件,则则 的的最优解也是最优解也是 的最优解的最优解,停止计算停止计算.(3)(3)得到不满足问题得到不满足问题 的整数条件的的整数条件的 的最优解的最优解,记它的记它的目标函数值为目标函数值为 ,这时需要对问题这时需要对问题 (从而对问题从而对问题 )进进行分枝行分枝,转下一步转下一步。(3)得到不满足问题得到不满足问题 的整数条件的的整数条件的 的最优解的最优解,记它的目记它的目标函数值为标函数值为 ,这时需要对问题这时需要对问题 (从而对问题从而对问题 )进行分进行分枝枝,转下一步转下一步.第第3 3步步:确定初始上下界确定初始上下界 与与 .以以 作为上界作为上界 .观察出问题观察出问题 的一个整数可行解的一个整数可行解,将其将其目标函数值记为下界目标函数值记为下界 .若观察不到若观察不到,则可记则可记 =-.转转下一步下一步.第第4 4步步:将问题将问题 分枝分枝.在在 的最优解的最优解 中中,任选一个不符合整数条件的变量任选一个不符合整数条件的变量 ,其值为其值为 ,以以 表示小于表示小于 的最大整数的最大整数.构造两构造两个约束条件:将这两个约束条件分别加到问题将这两个约束条件分别加到问题 的约束条件集中的约束条件集中,得到得到 的两个分枝的两个分枝:问题问题 与与 对每个分对每个分枝枝问题求解问题求解,得到以下几种可能得到以下几种可能:(1)分枝无可行解分枝无可行解该分枝是该分枝是 树叶树叶.(2)(2)求得该分枝的最优解求得该分枝的最优解,且满足且满足 的整数条件的整数条件.将该最将该最优解的目标函数值作为新的下界优解的目标函数值作为新的下界 ,该分枝也是该分枝也是 树叶树叶.(3)(3)求得该分枝的最优解求得该分枝的最优解,且不满足且不满足 的整数条件的整数条件,但其目但其目标函数不大于当前下界标函数不大于当前下界 ,则该分枝是则该分枝是“枯枝枯枝”需要剪枝需要剪枝.(4)4)求得不满足求得不满足 整数条件的该分枝的最优解整数条件的该分枝的最优解,且其目标且其目标函数值大于当前下界函数值大于当前下界 ,则该分枝需要继续进行分枝则该分枝需要继续进行分枝.若得到的是前三种情形之一若得到的是前三种情形之一,表明该分枝情况已探明表明该分枝情况已探明,不需要不需要继续分枝继续分枝.若求解一对分枝的结果表明这一对分若求解一对分枝的结果表明这一对分枝枝都需要继续分枝都需要继续分枝,则则可先对目标函数值大的那个分校进行分枝计算可先对目标函数值大的那个分校进行分枝计算,且沿着该分且沿着该分枝一直继续进行下去枝一直继续进行下去,直到全部探明情况为止直到全部探明情况为止.再返过来求解再返过来求解目标函数值较小的那个分枝目标函数值较小的那个分枝.第第6 6步步:修改上、下界修改上、下界.(1)(1)修改下界修改下界 ：每求出一次符合整数条件的可行解时每求出一次符合整数条件的可行解时,都要考虑修改下界都要考虑修改下界 ,选择迄今为止最好的整数可行解选择迄今为止最好的整数可行解 相应的目标函数值作下界相应的目标函数值作下界(2)(2)修改上界修改上界 ：每求解完一对分枝每求解完一对分枝,都要考虑修改上界都要考虑修改上界 上界的值应是迄今为止所有未被分枝的问题的目标函数值上界的值应是迄今为止所有未被分枝的问题的目标函数值中最大的一个中最大的一个.在每解完一对分枝、修改完上、下界在每解完一对分枝、修改完上、下界 和和 后后,若已有若已有 此时所有分枝均已查明此时所有分枝均已查明,即得到了问题即得到了问题 的最优值的最优值求解结束求解结束.若仍有若仍有 ,则说明仍有分枝没查明则说明仍有分枝没查明,需要继续分枝需要继续分枝,回回到第到第4 4步步运算步骤运算步骤解松弛问题解松弛问题满足要求满足要求?结束结束分枝分枝YN选一分支写出并求解松弛问题判定是否为整数解初始分支为可行解集，初始界为无穷判定是否分支集空 Y停止当前最好解为最优解NY判定最优值是否优于当前界判定最优值是否优于当前界按非整数变量分支并加入分支集以最优解替代当前最好解最优值替代当前界YYN剪枝NN求解混合整数规划问题，只对整数变量求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。分支，对非整数变量不分支。可能存在两个分枝都是非整数解的情况，可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝即当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有广又深，在最坏情况下相当于组合所有可能的整数解可能的整数解一般整数规划问题属于一类未解决的难一般整数规划问题属于一类未解决的难题，只有少数特殊问题有好的算法。题，只有少数特殊问题有好的算法。练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题LP1x1=1,x2=7/3Z(1)10/3LPx1=3/2,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9x11x12LP3x1=33/14,x2=2Z(3)61/14LP4无可无可行解行解x22x23LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x12x13例：用割平面法求解整数规划问题例：用割平面法求解整数规划问题解：增加松弛变量解：增加松弛变量x3和和x4，得到，得到(LP)的初始单纯形表和的初始单纯形表和最优单纯形表：最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00-1/4-1/4此题的最优解为：此题的最优解为：X=(1,3/2)Z=3/2但不是整但不是整数最优解。看数最优解。看x2所在行。所在行。将系数和常数项分解将系数和常数项分解由于由于x2，x3，x4为非负整数，等式右端为整数，（）内为非负整数，等式右端为整数，（）内为正，左端必为负数。所以，有：为正，左端必为负数。所以，有：这就得出了一个切割方程，将它作为增加约束条件。这就得出了一个切割方程，将它作为增加约束条件。Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源为源行生成割平面，其条件为：行生成割平面，其条件为：将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10至此得到最优表，其最优解为至此得到最优表，其最优解为X=(1,1),Z=1,这这也是原问题的最优解。也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。把把(2)(3)代入代入(1)并移项得：并移项得：例例写出下列问题的切割方程写出下列问题的切割方程Cj6400CBxBbx1x2x3x44x22011/3-1/36x15/210-1/62/3-2300-1/3-8/3解：解：例：用割平面法求解数规划问题例：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表在在松松弛弛问问题题最最优优解解中中，x1,x2 均均为为非非整整数数解解，由由上上表表有：有：将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，以上式子只须考虑一个即可，解题经验表明，考虑考虑式子右端最大真分数的式子，往往会较快地找到所需式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件割平面约束条件。以上两个式子右端真分数相等，可。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右任选一个考虑。现选第二个式子，并将真分数移到右边得：边得：引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表后得到下式，将此约束条件加到上表中，继续求解。中，继续求解。Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/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-10-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)00000(0.0.1)11015(0.1.0)24142(1.0.0)11103(0.1.1)15(1.0.1)02118(1.1.0)3(1.1.1)26由上表可知，问题的最优解为由上表可知，问题的最优解为X*=(x1=1 x2=0 x3=1)由上表可知：由上表可知：x1=0 x2=0 x3=1是一个可行解，为尽快是一个可行解，为尽快找到最优解，可将找到最优解，可将3x12 x25x35作为一个约束，作为一个约束，凡是目标函数值小于凡是目标函数值小于5的组合不必讨论，如下表。的组合不必讨论，如下表。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值(0)(1)(2)(3)(4)是是否否(0.0.0)000000(0.0.1)511015(0.1.0)-2(0.1.1)3(1.0.0)3(1.0.1)802118(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)05-1101否是05改进过滤条件：点(x2,x1,x3)条件是否满足条件Z值(0)(1)(2)(3)(4)(0,1,0)(0,1,1)380211否是8改进过滤条件：点(x2,x1,x3)条件是否满足条件Z值(0)(1)(2)(3)(4)(1,0,0)(1,0,1)(1,1,0)(1,1,1)-2316否否否否为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求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）练习：用隐枚举法求解练习：用隐枚举法求解0 01 1规划问题规划问题指派问题指派问题一、问题的提出一、问题的提出1、实例实例有四个熟练工人，他们都是多面手，有四项任务要他们完成。有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的总工时耗费最少？任务的总工时耗费最少？解：设解：设则此指派问题的模型为则此指派问题的模型为第一个约束说明第第一个约束说明第i个人只能完个人只能完成一个任务。成一个任务。第二个约束说明第第二个约束说明第j项任务只能项任务只能由一人完成。由一人完成。在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任务，项不同的任务，需要需要n 个人分别完成其中的一项，但由于任务的性质和个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成问题，应指派哪个人去完成哪项任务，使完成 n 项任项任务的总效率最高（或所需时间最少），这类问题称为务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题或分派问题。（一）、指派问题的数学模型（一）、指派问题的数学模型设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第工作，每件工作只有一个人去做。已知第I 个人去做第个人去做第j 件工作的的效率（件工作的的效率（时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij0。问应如何分配才。问应如何分配才能使总效率（能使总效率（时间或费用）最高？时间或费用）最高？设决策变量设决策变量1分配第分配第i 个人去做第个人去做第j 件工作件工作 xij=0相反相反(I,j=1.2.n)其数学模型为：其数学模型为：二、求解指派问题的理论依据二、求解指派问题的理论依据指派问题的一般形式指派问题的一般形式1、指派问题是一个特殊的运输问题指派问题是一个特殊的运输问题2、KoingKoing定理：在原指派问题的效益矩阵中同行同列加上某一定理：在原指派问题的效益矩阵中同行同列加上某一常数，所得指派问题与原问题同解。常数，所得指派问题与原问题同解。证明：证明：（二）、解题步骤：（二）、解题步骤：指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即匈牙利法，即系数矩阵中独立系数矩阵中独立 0 0 元素的最多个数等于元素的最多个数等于能覆盖所有能覆盖所有 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)对已打对已打号的行中所有含号的