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

1、整整 数数 规规 划划(Integer Programming)第一节第一节.整数规划整数规划问题的提出问题的提出一、整数规划的一般形式一、整数规划的一般形式1、实例：、实例：例例1 1 某厂拟用集装箱托运甲乙两种货物，每箱的体某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表积、重量、可获利润以及托运所受限制如表51：货物货物体积体积每箱（米每箱（米3 3）重量重量每箱（百斤）每箱（百斤）利润利润每箱（百元）每箱（百元）甲甲 乙乙 5 4 2 5 20 10托运限制托运限制 24 13问两种货物各托运多少箱，可使获得的利润为最大？问两种货物各托运多少箱，可使获得的

2、利润为最大？，且且为为整整数数，013522445:102021212121xxxxxxSTxxMaxZ 部部分分或或全全部部为为整整数数iiTxxbAXSTXCMaxZ,0:2、整数规划一般形式、整数规划一般形式解：设托运甲、乙两种货物解：设托运甲、乙两种货物x1，x2箱，用箱，用数学式可表示为：数学式可表示为：整数规划的数学模型整数规划的数学模型一般形式一般形式且且部部分分或或全全部部为为整整数数或或 n)1.2(j 0)2.1()min(max11jnjijijnjjjxmibxaxcZZ 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划

3、、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。整数规划。纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要数（这时引进的松弛变量和剩余变量可以不要求取整数）。求取整数）。全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时引也要求取整数（这时引进的松弛变量和剩余变量也必须是进的松弛变量和剩余变量也必须是 整数）。整数）。混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一

4、部分可以取非负实数。求取非负整数，另一部分可以取非负实数。01整数规划：整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数两个整数。整数规划与线性规划的关系整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至

5、不能保证所得倒的解是整数可行解。至不能保证所得倒的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下 且为整数0,13651914max21212121xxxxxxxxZ 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。0,13651914max21212121xxxxxxxxZ用用 解法求出最优解解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可可得到得到4个点即个点即(1，3

6、)(2，3)(1，4)(2，4)。显然，。显然，它们都不可能是整数规它们都不可能是整数规划的最优解。划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图 因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。目前，常用

7、的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。在在20世纪世纪60年代初年代初 Land Doig 和和 Dakin 等人提出等人提出了分了分枝枝定界法定界法.由于该方法灵活且便于用计算机求由于该方法灵活且便于用计算机求解解,所以目前已成为解整数规划的重要方法之一所以目前已成为解整数规划的重要方法之一.分分枝枝定界法既可用来解纯整数规划定界法既可用来解纯整数规划,也可用来解混合也可用来解混合整数规划整数规划.分枝定界法的主要思路是首先求解整数规

8、划的伴分枝定界法的主要思路是首先求解整数规划的伴随规划随规划（整数规划的松弛问题）（整数规划的松弛问题）,如果求得的最如果求得的最优解不符合整数条件优解不符合整数条件,则增加新则增加新约约束束缩小可行缩小可行域域;将原整数规划问题分将原整数规划问题分枝枝分为两个子规划分为两个子规划,再解子规划的伴随规划再解子规划的伴随规划通过求解一系列子规通过求解一系列子规划的伴随规划及不断地定界划的伴随规划及不断地定界.最后得到原整数规最后得到原整数规划问题的整数最优解划问题的整数最优解.分枝定界法分枝定界法基本思路基本思路 且为整数且为整数)2.1(,0)2.1()(max11mjxmibxaIPxcZj

9、njijijnjjj考虑纯整数问题：考虑纯整数问题：)2.1(,0)2.1()(max11mjxmibxaLPxcZjnjijijnjjj整数问题的松弛问题：整数问题的松弛问题：例 某公司计划建筑两种类型的宿舍某公司计划建筑两种类型的宿舍.甲种每幢占地甲种每幢占地0.25 103m2,乙种每幢地乙种每幢地0.4103m2.该公司拥该公司拥有土地有土地3103m2.计计划划甲种宿舍不超过甲种宿舍不超过 8 幢幢,乙乙种宿舍不超过种宿舍不超过4幢幢.甲种宿舍每幢利润为甲种宿舍每幢利润为10万元万元，乙种宿舍利润为每幢乙种宿舍利润为每幢20万元万元.问该公司应计划甲、问该公司应计划甲、乙两种类型宿舍

10、各建多少幢时乙两种类型宿舍各建多少幢时,能使公司获利最能使公司获利最大大?解解 设计划甲种宿舍建设计划甲种宿舍建 幢幢,乙种宿舍建乙种宿舍建 幢幢,则本题则本题数学模型为数学模型为:2x1x211020maxxxZ取整数,0,4834.025.0.212121xxxxxxts这是一个纯整数规划问题这是一个纯整数规划问题,称为问题称为问题 。将将(1)中约中约束条件束条件0A34.025.021xx的系数全化为整数的系数全化为整数,改为改为：608521 xx（1）然后去掉整数条件然后去掉整数条件,得到问题得到问题 的的伴随规划伴随规划 (2),(2),称之为称之为问题问题0A0B211020m

11、axxxf0,486085.212121xxxxxxts（2）用单纯形法求解问题用单纯形法求解问题 ,得到最优解及最优值得到最优解及最优值：0B,6.51x,42x,),(21*0TxxX.136*0f1.计算原问题计算原问题 目标函数值的初始上界目标函数值的初始上界 0AZ因为问题因为问题 的最优解不满足整数条件的最优解不满足整数条件,因此因此 不是问题不是问题 的最优解的最优解,又因为又因为 的可行域的可行域 问题问题 的可行域的可行域 ,故问题故问题 的最优值不会超过问题的最优值不会超过问题 的最优值的最优值.即有即有0B*0X0A0K0B0K0A0B*0*fZ 因此可令因此可令 作为作

12、为 的初始上界的初始上界*0f*ZZ即即.136Z一般说来一般说来,若问题若问题 无可行解无可行解,则问题则问题 也无可行解也无可行解,停止计停止计0B0A算算。若问题若问题 的最优解的最优解 满足问题满足问题 的整数的整数0B*0X0A条件条件,则则 也是问题也是问题 的最优解的最优解,停止计算停止计算.*0X0A2.计算原问题计算原问题 目标函数值的初始下界目标函数值的初始下界0AZ若能从问题若能从问题 的约束条件中观察到一个整数可行解的约束条件中观察到一个整数可行解,则可将则可将其目标函数值作为问其目标函数值作为问题题 目标函数值的初始下界目标函数值的初始下界,否则可令否则可令初始下界初

13、始下界Z=Z=-.给定下界的目的给定下界的目的,是希望在求解过程中寻找是希望在求解过程中寻找比当前比当前 更好的原问题的目标函数值更好的原问题的目标函数值 .0A0AZ对于本例对于本例,很容易得到一个明显的可行解很容易得到一个明显的可行解X=(0,0)X=(0,0)T T,Z=0.,Z=0.问问题题 的最优目标函数值决不会比它小的最优目标函数值决不会比它小,故可令故可令 =0.=0.0AZ3.增加约束条件将原问题分枝增加约束条件将原问题分枝当问题当问题 的最优解的最优解 不满足整数条件时不满足整数条件时,在在 中任选一个中任选一个不符合整数条件的变量不符合整数条件的变量.如本例选如本例选 显然

14、问题显然问题 的的整数最优解只能是整数最优解只能是 或或 ,而绝不会在而绝不会在5 5与与6 6之间之间.因此当将可行域因此当将可行域 切去切去 部分时部分时,并没有切去并没有切去 的的整数可行解整数可行解.可以用分别增加约束条件可以用分别增加约束条件 及及 来达来达到在到在 切去切去 部分的目的部分的目的.切去切去 后就分后就分为为 及及 两部分两部分,即问题即问题 分为问题分为问题 及问题及问题 两枝子两枝子规划规划.*0X0A*0X,6.51x0A51x61x0K651 x0A51x61x651 x651 x0K0K1K2K0A1A2A问题问题 1A问题问题 2A211020maxxxZ

15、取整数,0,5486085.2112121xxxxxxxts211020maxxxZ取整数,0,6486085.2112121xxxxxxxts 作出问题作出问题 的伴随规划的伴随规划 则问题则问题 的可行的可行域域为 见图见图2(b).2(b).以下我们将由同一问题分解出的两以下我们将由同一问题分解出的两个分个分枝枝问题称为问题称为 一对分枝一对分枝.,1A2A,1B,2B,1B,2B,1K,2KOO112234421x2x2x1x468684.分别求解一对分枝分别求解一对分枝在一般情况下在一般情况下,对某个分枝问题对某个分枝问题(伴随规划伴随规划)求解时求解时,可能出现可能出现以下几种可能

16、以下几种可能:(a)(a)(b)图2(1)无可行解无可行解若无可行解若无可行解,说明该枝情况己查明说明该枝情况己查明,不需要由此分枝再继续不需要由此分枝再继续分枝分枝,称该称该分枝为分枝为 “树叶树叶”，剪枝。，剪枝。(2)得到整数最优解得到整数最优解若求得整数最优解，则若求得整数最优解，则该枝情况己查明该枝情况己查明,不需要不需要再对再对此继续此继续分枝分枝，该该分枝也是分枝也是 树叶树叶.(3)得到非整数最优解得到非整数最优解若求得某个若求得某个分枝分枝问题得到的是不满足整数条件的最优解，问题得到的是不满足整数条件的最优解，该最优解的目标函数值该最优解的目标函数值Z Z小于当前的下界小于当

17、前的下界 ，则该，则该枝内不可能含有原问题的整数最优解，称为枝内不可能含有原问题的整数最优解，称为“枯枝枯枝”，需需剪掉。剪掉。Z该最优解的目标函数值该最优解的目标函数值Z Z大于当前的下界大于当前的下界 ，则仍，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的当前的 更好的整数最优解。更好的整数最优解。ZZ本例中问题本例中问题 及问题及问题 的模型及求解结果的模型及求解结果如下：如下：1B2B还要区分两种情况：还要区分两种情况：问题1B问题2B211020maxxxf0,5486085.2112121xxxxxxxts211020

18、maxxxf0,6486085.2112121xxxxxxxts解为:TX)4,5(*1解为:TX)75.3,6(*2130*1f135*2f问题问题 的解的解 是整数最优解是整数最优解,它当然也是问题它当然也是问题 的整数可行解的整数可行解,故故 的整数最优解的整数最优解1BTX)4,5(*10A0A.130*1*fZ即此时可将即此时可将 修改为修改为:Z130*1 fZ同时问题同时问题 也被查清也被查清,成为成为“树叶树叶”。1B因为因为 ,不满足整数条件不满足整数条件,故问题故问题 分别增加约分别增加约束条件束条件：及及 。分为分为 与与 两两枝枝,建立相应的建立相应的伴随规划伴随规划问

19、题问题 与与TX)75.3,6(*20A32x42x3B.4B3A3A问题3B问题4B211020maxxxf0,46486085.21212121xxxxxxxxts211020maxxxf0,36486085.21212121xxxxxxxxts它们的可行域分别为,3K).(4K见图3。O2x1x12324468图3因为因为 ，问题问题无可行解无可行解，此问题此问题已已是是 树叶树叶,已被查清已被查清.4K4B求解问题求解问题 ,得到最优解得到最优解 3BTX)3,2.7(*3132*3f5.修改上、下界修改上、下界 与与ZZ(l)修改下界修改下界 Z修改下界的时机是修改下界的时机是:每求

20、出一个整数可行解时每求出一个整数可行解时,都要作修改都要作修改下界下界 的工作的工作.Z修改下界修改下界 的原则的原则:在至今所有计算出的在至今所有计算出的整数可行解整数可行解中中,选选目标函数值最目标函数值最大大的那个作为最新下界的那个作为最新下界 。ZZ因此在用分枝定界法的求解全过程中因此在用分枝定界法的求解全过程中,下界下界 是不断增大的是不断增大的.(2)修改上界修改上界 Z上界上界 的修改时机是的修改时机是:每求解完一对分枝每求解完一对分枝,都要考虑修改上界都要考虑修改上界Z修改上界修改上界 的原则是的原则是:挑选在迄今为止所有挑选在迄今为止所有未被分枝未被分枝的问题的的问题的目标函

21、数值中最目标函数值中最大大的一个作为新的上界的一个作为新的上界.新的上界新的上界 应该小于应该小于原来的上界原来的上界 .ZZ在分枝定界法的整个求解过程中在分枝定界法的整个求解过程中,上界的值在不断减小上界的值在不断减小.问题6B问题5B211020maxxxf0,46486085.21212121xxxxxxxxts211020maxxxf0,36486085.21212121xxxxxxxxtsO24681x132x24解为解为:TxxX)3,7(21*5130*5fTxxX)5.2,8(21*6130*6f因为此时因为此时 的解为整数解的解为整数解,因此修改下界为因此修改下界为 =130

22、,而此而此时所有未被分枝的问题时所有未被分枝的问题()的目标函数值中最大的的目标函数值中最大的为为 ,故修改上界故修改上界 =130.=130.5BZ,5B,4B6B130*6*5 ffZ6.结束准则结束准则当所有分当所有分枝枝均已查明均已查明(或无可行解或无可行解“树叶树叶”,或为整数可或为整数可行解行解“树叶树叶”,或其目标函数值不大于下界或其目标函数值不大于下界 ”枯枯枝枝”）Z且此时且此时 ，则已得到了原问题的整数最优则已得到了原问题的整数最优 ZZ解，解，即目标函数值为下界即目标函数值为下界 的那个整数解的那个整数解 .Z在本例中在本例中,当解完一对当解完一对分枝分枝 后后,得到得到

23、 又又 是是 树叶树叶,为为 枯枝枯枝,因此所有分枝因此所有分枝()均已查明均已查明.故已得到问题故已得到问题 的最优解的最优解:,5B6B,130 ZZ5B6B,5B6B,4B,1B0A,)3,7(5*TXX.130*Z,)4,5(1*TXX或.130*Z故该公司应建甲种宿舍故该公司应建甲种宿舍7 7幢乙种宿舍幢乙种宿舍3 3幢幢;或甲种或甲种5 5幢、乙幢、乙种种4 4幢时幢时,获利最大获利最大.获利为获利为130130万元万元.可将本例的求解过程与结果用图可将本例的求解过程与结果用图5 5 来描述来描述.问题6.51x0B32x42x1360f136Z0Z问题51x1B42x1301f问

24、题61x2B75.32x1352f问题2.71x3B32x1323f问题4B问题71x5B32x1305f问题81x6B5.22x1306f51x61x135Z130Z42x不可行132Z130Z71x81x130Z130ZX分枝规则情况情况 2,4,5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 5下面将分下面将分枝枝定界法求解混合型整数规划的计算步骤归纳

25、如下定界法求解混合型整数规划的计算步骤归纳如下:第第1 1步步:将原整数线性规划问题称为问题将原整数线性规划问题称为问题 .去掉问题去掉问题的整数条件的整数条件,得到伴随规划问题得到伴随规划问题 0A0A0B第第2 2步步:求解问题求解问题 ,有以下几种可能有以下几种可能:0B(l)(l)没有可行解没有可行解,则则 也没有可行解也没有可行解,停止计算停止计算。0B0A(2)得到得到 的最优解的最优解,且满足问题且满足问题 的整数条件的整数条件,则则 的的最优解也是最优解也是 的最优解的最优解,停止计算停止计算.0B0A0B0A(3)(3)得到不满足问题得到不满足问题 的整数条件的的整数条件的

26、的最优解的最优解,记它的记它的目标函数值为目标函数值为 ,这时需要对问题这时需要对问题 (从而对问题从而对问题 )进进行分枝行分枝,转下一步转下一步。0A0B*0f0A0B(3)得到不满足问题得到不满足问题 的整数条件的的整数条件的 的最优解的最优解,记它的目记它的目标函数值为标函数值为 ,这时需要对问题这时需要对问题 (从而对问题从而对问题 )进行分进行分枝枝,转下一步转下一步.0A0B*0f0A0B第第3 3步步:确定初始上下界确定初始上下界 与与 .ZZ以以 作为上界作为上界 .观察出问题观察出问题 的一个整数可行解的一个整数可行解,将其将其目标函数值记为下界目标函数值记为下界 .若观察

27、不到若观察不到,则可记则可记 =-.转转下一步下一步.第第4 4步步:将问题将问题 分枝分枝.*0fZ0AZZ0B在在 的最优解的最优解 中中,任选一个不符合整数条件的变量任选一个不符合整数条件的变量 ,其值为其值为 ,以以 表示小于表示小于 的最大整数的最大整数.构造两构造两0B0Xjxjajaja个约束条件:1jjaxjjax 将这两个约束条件分别加到问题将这两个约束条件分别加到问题 的约束条件集中的约束条件集中,得到得到 的两个分枝的两个分枝:问题问题 与与 0B0B2B1B对每个分对每个分枝枝问题求解问题求解,得到以下几种可能得到以下几种可能:(1)分枝无可行解分枝无可行解该分枝是该分

28、枝是 树叶树叶.(2)(2)求得该分枝的最优解求得该分枝的最优解,且满足且满足 的整数条件的整数条件.将该最将该最优解的目标函数值作为新的下界优解的目标函数值作为新的下界 ,该分枝也是该分枝也是 树叶树叶.0AZ(3)(3)求得该分枝的最优解求得该分枝的最优解,且不满足且不满足 的整数条件的整数条件,但其目但其目标函数不大于当前下界标函数不大于当前下界 ,则该分枝是则该分枝是“枯枝枯枝”需要剪枝需要剪枝.0AZ(4)4)求得不满足求得不满足 整数条件的该分枝的最优解整数条件的该分枝的最优解,且其目标且其目标函数值大于当前下界函数值大于当前下界 ,则该分枝需要继续进行分枝则该分枝需要继续进行分枝

29、.0AZ若得到的是前三种情形之一若得到的是前三种情形之一,表明该分枝情况已探明表明该分枝情况已探明,不需要不需要继续分枝继续分枝.若求解一对分枝的结果表明这一对分若求解一对分枝的结果表明这一对分枝枝都需要继续分枝都需要继续分枝,则则可先对目标函数值大的那个分校进行分枝计算可先对目标函数值大的那个分校进行分枝计算,且沿着该分且沿着该分枝一直继续进行下去枝一直继续进行下去,直到全部探明情况为止直到全部探明情况为止.再返过来求解再返过来求解目标函数值较小的那个分枝目标函数值较小的那个分枝.第第6 6步步:修改上、下界修改上、下界.(1)(1)修改下界修改下界 ：每求出一次符合整数条件的可行解时每求出

30、一次符合整数条件的可行解时,都要考虑修改下界都要考虑修改下界 ,选择迄今为止最好的整数可行解选择迄今为止最好的整数可行解 ZZ相应的目标函数值作下界相应的目标函数值作下界 Z(2)(2)修改上界修改上界 ：每求解完一对分枝每求解完一对分枝,都要考虑修改上界都要考虑修改上界 上界的值应是迄今为止所有未被分枝的问题的目标函数值上界的值应是迄今为止所有未被分枝的问题的目标函数值中最大的一个中最大的一个.ZZ在每解完一对分枝、修改完上、下界在每解完一对分枝、修改完上、下界 和和 后后,若已有若已有 此时所有分枝均已查明此时所有分枝均已查明,即得到了问题即得到了问题 的最优值的最优值ZZZZ 0AZZZ

31、*求解结束求解结束.若仍有若仍有 ,则说明仍有分枝没查明则说明仍有分枝没查明,需要继续分枝需要继续分枝,回回到第到第4 4步步ZZ 运算步骤运算步骤解松弛问题解松弛问题 满足要求满足要求?结束结束 分枝分枝YN选一分支写出并求解松弛问题判定是否为整数解初始分支为可行解集，初始界为无穷判定是否分支集空 Y停止当前最好解为最优解NY判定最优值是否优于当前界判定最优值是否优于当前界按非整数变量分支并加入分支集以最优解替代当前最好解最优值替代当前界YYN剪枝NN 求解混合整数规划问题，只对整数变量求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。分支，对非整数变量不分支。可能存在两个分枝都是

32、非整数解的情况，可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有广又深，在最坏情况下相当于组合所有可能的整数解可能的整数解 一般整数规划问题属于一类未解决的难一般整数规划问题属于一类未解决的难题，只有少数特殊问题有好的算法。题，只有少数特殊问题有好的算法。且全为整数且全为整数0,13651914max21212121xxxxxxxxZ练习：用分枝定界法求解整数规划问题练习：用分枝定界法

33、求解整数规划问题 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割平面法。割平面法。的解。的整数解即直到得到弛问题。重复这个过程的可行解，得到新的松但不丢失任何不可行，约束使不是整数解，增加一个，若解解松弛问题取整数一、基本思想：)()()()(0.min)(0.min)(AAAxxBXbAXtsXCBxXbAXtsXCATjT例

34、：用割平面法求解整数规划问题例：用割平面法求解整数规划问题 且为整数且为整数0,023623 max2121212xxxxxxxZ解：增加松弛变量解：增加松弛变量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所在行。所在行。2141

35、4143 xx234141432xxx将系数和常数项分解将系数和常数项分解)(43243241412112114141xxxxxx由于由于x2，x3，x4为非负整数，等式右端为整数，（）内为非负整数，等式右端为整数，（）内为正，左端必为负数。所以，有：为正，左端必为负数。所以，有：041412143)(xx这就得出了一个切割方程，将它作为增加约束条件。这就得出了一个切割方程，将它作为增加约束条件。Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛

36、变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：214141143 sxxCBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源为源行生成割平面，其条件为：行生成割平面，其条件为：32323214 sx将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：323232214 ssxCBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320

37、011-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,这这也是原问题的最优解。也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中

38、始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。)3()10()2()10(.2 iiiiikikikikikiffbbffaaab令令负负真真分分数数之之和和。都都分分解解成成整整数数部部分分与与非非和和将将把把(2)(3)代入代入(1)并移项得：并移项得：)4(kkikiikkikixffbxax)(,.11ikkikiibxaxx的的最最终终表表得得到到由由单单纯纯型型表表为为分分数数值值的的一一个个基基变变量量中中是是相相应应线线性性规规划划最最优优解解令令这这就就是是切切割割方方程程。或或所所以以有有而而右右

39、边边等等号号左左边边为为整整数数式式在在ikkkikkkikiifxxfxfff101043,)(.例例 写出下列问题的切割方程写出下列问题的切割方程Cj6400CBxBbx1x2x3x44x22011/3-1/36x15/210-1/62/3-2300-1/3-8/3j 解：解：213265032652154343xxxxx或或切切割割方方程程为为所所以以,253261431 xxx例：用割平面法求解数规划问题例：用割平面法求解数规划问题 且且为为整整数数0,205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40 x3621100 x4204501Z11

40、00CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表在松弛问题最优解中，在松弛问题最优解中，x1,x2 均为非整数解，由上表均为非整数解，由上表有：有：383132356165432431 xxxxxx将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 32231)311(321)651(65432431 xxxxxx 以上式子只须考虑一个即可，解题经验表明，以上式子只须考虑一个即可，解题经验表明，考虑考虑式子右端最大真分数的式子，往往会较快地找到所需式子右端最大真分数的式子，

41、往往会较快地找到所需割平面约束条件割平面约束条件。以上两个式子右端真分数相等，可。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右任选一个考虑。现选第二个式子，并将真分数移到右边得：边得：)(313224332xxxx 32)(3143 xx引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表后得到下式，将此约束条件加到上表中，继续求解。中，继续求解。323131143 sxxCj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CB

42、XBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：有两个最优解：X=(0,4),Z=4,或 X=(2,2),Z=4。且且为为整整数数练练习习：0,421625421411max2121212121xxxxxxxxxxZ 0-1整数规划整数规划 iijAAx不不选选选选解解：设设01一、问题的提出一、问题的提出1、实例实例例例 某公司拟在市东、西某公司拟在市东、西-南三区建立门市部。拟议中南三区建立门市部。拟议中有有7个位置（

43、点）个位置（点）Ai供选择。规定供选择。规定 在东区，由在东区，由A1,A2,A3三个点中至多选两个；三个点中至多选两个；在西区，由在西区，由A4,A5两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由A6,A7两个点中至少选一个。两个点中至少选一个。如选用如选用Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利润估元，每年可获利润估计为计为ci元，但投资总额不能超过元，但投资总额不能超过B元。问应选择那几个元。问应选择那几个点可使年利润为最大？点可使年利润为最大？则则0-10-1规划模型为：规划模型为：),1(,01:njxbAxSTXCMaxZjT或或 )7,1(,011

44、12:7654321772211772211jxxxxxxxxBxbxbxbSTxcxcxcMaxZj或或2、0-1整数规划的一般形式整数规划的一般形式 01 整数规划是一种特殊形式的整数规划，这时的整数规划是一种特殊形式的整数规划，这时的决策变量决策变量xi 只取两个值只取两个值0或或1，一般的解法为隐枚举法，一般的解法为隐枚举法例：求解下列例：求解下列01 规划问题规划问题 10,(4)64 (3)3 (2)44(1)22523max3213221321321321或或xxxxxxxxxxxxxxxxZ 解：对于解：对于01 规划问题，由于每个变量只取规划问题，由于每个变量只取0，1两两个

45、值，一般会用穷举法来解，即将所有的个值，一般会用穷举法来解，即将所有的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

46、(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(

47、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规划问题规划问题 )5(01,)4(64)3(3)2(44)1(22:5233213221321321321或或xxxxxxxxxxxxxSTxxxMaxZ )5(01,)4(

48、64)3(3)2(44)1(22:5323213212312312312或或xxxxxxxxxxxxxSTxxxMaxZ )5(01,)4(64)3(3)2(44)1(22:5233213221321321321或或xxxxxxxxxxxxxSTxxxMaxZ解：解：目标函数的系数按升序排列目标函数的系数按升序排列通过试探可行解(x1,x2,x3)=(1,0,0)引入下列过滤条件：)0(3532312xxx 点(x2,x1,x3)条 件是否满足条件Z值(0)(1)(2)(3)(4)(0,0,0)(0,0,1)0 5 -1 1 0 1 否 是 0 5改进过滤条件：)0(5532312xxx 点(

49、x2,x1,x3)条 件是否满足条件Z值(0)(1)(2)(3)(4)(0,1,0)(0,1,1)3 8 0 2 1 1 否 是 8改进过滤条件：)0(8532 312xxx 点(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微积分微积

50、分5数学数学 2线性代数线性代数4数学数学 3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机 8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数0-1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi=1 选修课号选修课号i 的的课程