整数规划精美管理.ppt
《整数规划精美管理.ppt》由会员分享,可在线阅读,更多相关《整数规划精美管理.ppt(99页珍藏版)》请在三一办公上搜索。
1、整 数 规 划(Integer Programming),第一节.整数规划问题的提出,一、整数规划的一般形式,1、实例:,例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表51:,问两种货物各托运多少箱,可使获得的利润为最大?,2、整数规划一般形式,解:设托运甲、乙两种货物x1,x2箱,用数学式可表示为:,整数规划的数学模型,一般形式,依照决策变量取整要求的不同,整数规划可分为纯整数规划、全整数规划、混合整数规划、01整数规划。,纯整数规划:所有决策变量要求取非负整数(这时引进的松弛变量和剩余变量可以不要求取整数)。,全整数规划:除了所有决策变量要求取非负整数
2、外,系数aij和常数bi也要求取整数(这时引进的松弛变量和剩余变量也必须是 整数)。,混合整数规划:只有一部分的决策变量要求取非负整数,另一部分可以取非负实数。,01整数规划:所有决策变量只能取 0 或 1 两个整数。,整数规划与线性规划的关系,从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得倒的解是整数可行解。举例说明。,例:设整数规划问题如下,首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。,用 解法求出最优解x13/
3、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年代初 La
4、nd Doig 和 Dakin 等人提出了分枝定界法.由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一.分枝定界法既可用来解纯整数规划,也可用来解混合整数规划.,分枝定界法的主要思路是首先求解整数规划的伴随规划(整数规划的松弛问题),如果求得的最优解不符合整数条件,则增加新约束缩小可行域;将原整数规划问题分枝分为两个子规划,再解子规划的伴随规划通过求解一系列子规划的伴随规划及不断地定界.最后得到原整数规划问题的整数最优解.,分枝定界法,基本思路,考虑纯整数问题:,整数问题的松弛问题:,例,某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 103m2,乙种每幢地0.41
5、03m2.该公司拥有土地3103m2.计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元,乙种宿舍利润为每幢20万元.问该公司应计划甲、乙两种类型宿舍各建多少幢时,能使公司获利最大?,解 设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题数学模型为:,这是一个纯整数规划问题,称为问题。将(1)中约束条件,的系数全化为整数,改为:,(1),然后去掉整数条件,得到问题 的伴随规划(2),称之为问题,(2),用单纯形法求解问题,得到最优解及最优值:,1.计算原问题 目标函数值的初始上界,因为问题 的最优解不满足整数条件,因此 不是问题 的最优解,又因为 的可行域 问题 的可行域,故
6、问题 的最优值不会超过问题 的最优值.即有,因此可令 作为 的初始上界,即,一般说来,若问题 无可行解,则问题 也无可行解,停止计,算。若问题 的最优解 满足问题 的整数,条件,则 也是问题 的最优解,停止计算.,2.计算原问题 目标函数值的初始下界,若能从问题 的约束条件中观察到一个整数可行解,则可将其目标函数值作为问题 目标函数值的初始下界,否则可令初始下界Z=-.给定下界的目的,是希望在求解过程中寻找比当前 更好的原问题的目标函数值.,对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0.问题 的最优目标函数值决不会比它小,故可令=0.,3.增加约束条件将原问题分枝,当问题 的最
7、优解 不满足整数条件时,在 中任选一个不符合整数条件的变量.如本例选 显然问题 的整数最优解只能是 或,而绝不会在5与6之间.因此当将可行域 切去 部分时,并没有切去 的整数可行解.可以用分别增加约束条件 及 来达到在 切去 部分的目的.切去 后就分为 及 两部分,即问题 分为问题 及问题 两枝子规划.,问题,问题,作出问题 的伴随规划 则问题 的可行域为 见图2(b).以下我们将由同一问题分解出的两个分枝问题称为一对分枝.,4.分别求解一对分枝,在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现以下几种可能:,(a),(b),图2,(1)无可行解,若无可行解,说明该枝情况己查明,不需要
8、由此分枝再继续,分枝,称该分枝为“树叶”,剪枝。,(2)得到整数最优解,若求得整数最优解,则该枝情况己查明,不需要再对此继续分枝,该分枝也是 树叶.,(3)得到非整数最优解,若求得某个分枝问题得到的是不满足整数条件的最优解,,该最优解的目标函数值Z小于当前的下界,则该枝内不可能含有原问题的整数最优解,称为“枯枝”,需剪掉。,该最优解的目标函数值Z大于当前的下界,则仍需对该枝继续分枝,以查明该分枝内是否有目标函数值比当前的 更好的整数最优解。,本例中问题 及问题 的模型及求解结果如下:,还要区分两种情况:,问题,问题,解为:,解为:,问题 的解 是整数最优解,它当然也是问题 的整数可行解,故 的
9、整数最优解,即此时可将 修改为:,同时问题 也被查清,成为“树叶”。,因为,不满足整数条件,故问题 分别增加约束条件:及。分为 与 两枝,建立相应的伴随规划问题 与,问题,问题,它们的可行域分别为,见图3。,图3,因为,问题无可行解,此问题已是树叶,已被查清.,求解问题,得到最优解,5.修改上、下界 与,(l)修改下界,修改下界的时机是:每求出一个整数可行解时,都要作修改,下界 的工作.,修改下界 的原则:在至今所有计算出的整数可行解中,选目标函数值最大的那个作为最新下界。,因此在用分枝定界法的求解全过程中,下界 是不断增大的.,(2)修改上界,上界 的修改时机是:每求解完一对分枝,都要考虑修
10、改上界,修改上界 的原则是:挑选在迄今为止所有未被分枝的问题的目标函数值中最大的一个作为新的上界.新的上界 应该小于原来的上界.,在分枝定界法的整个求解过程中,上界的值在不断减小.,问题,问题,解为:,因为此时 的解为整数解,因此修改下界为=130,而此时所有未被分枝的问题()的目标函数值中最大的为,故修改上界=130.,6.结束准则,当所有分枝均已查明(或无可行解“树叶”,或为整数可行解“树叶”,或其目标函数值不大于下界”枯枝”),且此时,则已得到了原问题的整数最优,解,即目标函数值为下界 的那个整数解.,在本例中,当解完一对分枝 后,得到 又 是树叶,为枯枝,因此所有分枝()均已查明.故已
11、得到问题 的最优解:,或,故该公司应建甲种宿舍7幢乙种宿舍3幢;或甲种5幢、乙种4幢时,获利最大.获利为130万元.,可将本例的求解过程与结果用图5 来描述.,问题,问题,问题,问题,问题,问题,问题,不可行,分枝规则,情况 2,4,5 找到最优解情况 3 在缩减的域上继续分枝定界法情况 6 问题 1 的整数解作为界被保留,用于以后与问题 2 的后续分枝所得到的解进行比较,结论如情况 4 或 5,下面将分枝定界法求解混合型整数规划的计算步骤归纳如下:,第1步:将原整数线性规划问题称为问题.去掉问题的整数条件,得到伴随规划问题,第2步:求解问题,有以下几种可能:,(l)没有可行解,则 也没有可行
12、解,停止计算。,(2)得到 的最优解,且满足问题 的整数条件,则 的最优解也是 的最优解,停止计算.,(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为,这时需要对问题(从而对问题)进行分枝,转下一步。,(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为,这时需要对问题(从而对问题)进行分枝,转下一步.,第3步:确定初始上下界 与.,以 作为上界.观察出问题 的一个整数可行解,将其目标函数值记为下界.若观察不到,则可记=-.转下一步.,第4步:将问题 分枝.,在 的最优解 中,任选一个不符合整数条件的变量,其值为,以 表示小于 的最大整数.构造两,个约束条件:,将这
13、两个约束条件分别加到问题 的约束条件集中,得到 的两个分枝:问题 与,对每个分枝问题求解,得到以下几种可能:,(1)分枝无可行解该分枝是 树叶.,(2)求得该分枝的最优解,且满足 的整数条件.将该最优解的目标函数值作为新的下界,该分枝也是树叶.,(3)求得该分枝的最优解,且不满足 的整数条件,但其目标函数不大于当前下界,则该分枝是“枯枝”需要剪枝.,(4)求得不满足 整数条件的该分枝的最优解,且其目标函数值大于当前下界,则该分枝需要继续进行分枝.,若得到的是前三种情形之一,表明该分枝情况已探明,不需要继续分枝.,若求解一对分枝的结果表明这一对分枝都需要继续分枝,则可先对目标函数值大的那个分校进
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划 精美 管理

链接地址:https://www.31ppt.com/p-5270746.html