《退化与循环幻灯片.ppt》由会员分享，可在线阅读，更多相关《退化与循环幻灯片.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、退化与循环第1页，共50页，编辑于2022年，星期三例：例：第2页，共50页，编辑于2022年，星期三退化与循环的问题退化与循环的问题在在非退化非退化情形下，用单纯形方法经过有限次迭代情形下，用单纯形方法经过有限次迭代一定一定可达到最优解。可达到最优解。在在退化退化情形下，用单纯形方法进行迭代情形下，用单纯形方法进行迭代可能可能得不得不到最优解。到最优解。基迭代经过若干次后又回到先前的可行基基迭代经过若干次后又回到先前的可行基B1 B2 .B1循环循环循环循环第3页，共50页，编辑于2022年，星期三为避免循环，伯兰特为避免循环，伯兰特(Bland)规则：规则：1.当存在多个当存在多个 ，始终
2、选取，始终选取下标值为最小下标值为最小的变量作为进基变量。的变量作为进基变量。2.当当 出现两个以上相同的最小比值时，始出现两个以上相同的最小比值时，始终选取终选取下标值为最小下标值为最小的变量为离基变量的变量为离基变量第4页，共50页，编辑于2022年，星期三3.3.2 摄动法摄动法第5页，共50页，编辑于2022年，星期三四个定理四个定理利用单纯形法求解摄动问题时，利用单纯形法求解摄动问题时，不会出现循环现象。不会出现循环现象。第6页，共50页，编辑于2022年，星期三判别数相同判别数相同第7页，共50页，编辑于2022年，星期三通过求解摄动问题，能通过求解摄动问题，能给出原问题的解。给出
3、原问题的解。第8页，共50页，编辑于2022年，星期三两个问题：两个问题：1.怎样找到摄动问题的初始基本怎样找到摄动问题的初始基本可行解可行解?2.如何处理如何处理?基列下标小于非基列下标基列下标小于非基列下标第9页，共50页，编辑于2022年，星期三进行列调换，把基列排在非基列的左边，并进行列调换，把基列排在非基列的左边，并相应地改变变量的下标，使其从相应地改变变量的下标，使其从1开始按递增开始按递增顺序排列。顺序排列。问题问题1的解决方案：的解决方案：第10页，共50页，编辑于2022年，星期三问题问题2的解决方案的解决方案(确定主行确定主行)：摄动法与一般单纯形法的差别主摄动法与一般单纯
4、形法的差别主要在于主行的选择。要在于主行的选择。第11页，共50页，编辑于2022年，星期三第12页，共50页，编辑于2022年，星期三单纯形法小结找出初始基本可行解找出初始基本可行解找出初始基本可行解找出初始基本可行解列初始单纯形表列初始单纯形表列初始单纯形表列初始单纯形表计算检验数计算检验数计算检验数计算检验数 j j所有所有所有所有 j j00基变量中含非基变量中含非基变量中含非基变量中含非零的人工变量零的人工变量零的人工变量零的人工变量存在非基变量存在非基变量存在非基变量存在非基变量检验数为检验数为检验数为检验数为0 0唯一最优解唯一最优解唯一最优解唯一最优解否否是是无可行解无可行解无
5、可行解无可行解是是否否对某一个对某一个对某一个对某一个 j j0,0,有有有有p pj j 00无界解无界解无界解无界解无穷多最优解无穷多最优解无穷多最优解无穷多最优解否否是是是是否否第13页，共50页，编辑于2022年，星期三 k k=max=max j j,x,xk k进基进基进基进基计算检验数计算检验数计算检验数计算检验数 j j第14页，共50页，编辑于2022年，星期三单纯形法小结找出初始基本可行解找出初始基本可行解找出初始基本可行解找出初始基本可行解列初始单纯形表列初始单纯形表列初始单纯形表列初始单纯形表计算检验数计算检验数计算检验数计算检验数 j j所有所有所有所有 j j00基
6、变量中含非零基变量中含非零基变量中含非零基变量中含非零的人工变量的人工变量的人工变量的人工变量存在非基变存在非基变存在非基变存在非基变量检验数为量检验数为量检验数为量检验数为0 0唯一最优解唯一最优解唯一最优解唯一最优解否否是是无可行解无可行解无可行解无可行解是是否否对某一个对某一个对某一个对某一个 j j0,0,有有有有p pj j 00无界解无界解无界解无界解无穷多最优解无穷多最优解无穷多最优解无穷多最优解否否是是是是否否第15页，共50页，编辑于2022年，星期三 k k=max=max j j,x,xk k进基进基进基进基计算检验数计算检验数计算检验数计算检验数 j j第16页，共50
7、页，编辑于2022年，星期三Integer Programming (IP)第第7 7章章 整数规划整数规划第17页，共50页，编辑于2022年，星期三松弛问题松弛问题松弛问题松弛问题整数整数线性规划线性规划模型模型第18页，共50页，编辑于2022年，星期三整数线性规划类型整数线性规划类型1.纯整数线性规划纯整数线性规划纯整数线性规划纯整数线性规划：2.混合整数线性规划混合整数线性规划混合整数线性规划混合整数线性规划：3.0 01 1型整数线性规划型整数线性规划型整数线性规划型整数线性规划：人员安排问题人员安排问题投资组合问题投资组合问题物资运输问题物资运输问题第19页，共50页，编辑于20
8、22年，星期三人员安排问题人员安排问题l l医院护士医院护士24小时值班，每次值班小时值班，每次值班8小时。不小时。不同时段需要的护士人数不等。据统计：同时段需要的护士人数不等。据统计：序号时段最少人数安排人数1061060 x12101470 x23141860 x34182250 x45220220 x56020630 x6最少需要多少护士？最少需要多少护士？第20页，共50页，编辑于2022年，星期三l证券投资：把一定的资金投入到合适的有证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。价证券上以规避风险并获得最大的利润。l项目投资：财团或银行把资金投入到若干项目投
9、资：财团或银行把资金投入到若干项目中以获得中长期的收益最大项目中以获得中长期的收益最大。投资组合问题投资组合问题第21页，共50页，编辑于2022年，星期三 现有资金总额为现有资金总额为现有资金总额为现有资金总额为B B。可供选择的投资项目有。可供选择的投资项目有。可供选择的投资项目有。可供选择的投资项目有n n个，项目个，项目个，项目个，项目j j所所所所需投资额和预期收益分别为需投资额和预期收益分别为需投资额和预期收益分别为需投资额和预期收益分别为a aj j和和和和c cj j（j=1,2,.,nj=1,2,.,n）。此外，）。此外，）。此外，）。此外，由于种由于种由于种由于种种原因，有
10、三个附加条件：种原因，有三个附加条件：种原因，有三个附加条件：种原因，有三个附加条件：第一，若选择项目第一，若选择项目第一，若选择项目第一，若选择项目1 1，就必须同时选择项目，就必须同时选择项目，就必须同时选择项目，就必须同时选择项目2 2。反之，则不一定；。反之，则不一定；。反之，则不一定；。反之，则不一定；第二，项目第二，项目第二，项目第二，项目3 3和和和和4 4中至少选择一个；中至少选择一个；中至少选择一个；中至少选择一个；第三，项目第三，项目第三，项目第三，项目5 5，6 6和和和和7 7中恰好选择两个。中恰好选择两个。中恰好选择两个。中恰好选择两个。应当怎样选择投资项目，才能使总
11、预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？第22页，共50页，编辑于2022年，星期三特征特征变量整数性要求变量整数性要求来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要性质性质可行域是离散集合可行域是离散集合第23页，共50页，编辑于2022年，星期三与线性规划的关系整数规划整数规划放松的线性规划放松的线性规划可行解是松弛问题的可行解可行解是松弛问题的可行解最优值不会优于其松弛问题的最优值最优值不会优于其松弛问题的最优值第24页，共50页，编辑于2022年，
12、星期三注注 释释l最优解不一定在顶点上达到最优解不一定在顶点上达到l最优解不一定是松弛问题最优解的邻近整数解最优解不一定是松弛问题最优解的邻近整数解l整数可行解远多于顶点，枚举法不可取整数可行解远多于顶点，枚举法不可取第25页，共50页，编辑于2022年，星期三7.4 解纯整数规划的解纯整数规划的割平面法割平面法1958年由R.E.Gomory首先提出第26页，共50页，编辑于2022年，星期三算算 法法 思思 想想l由松弛问题的可行域向整数由松弛问题的可行域向整数规划的可行域规划的可行域逼近逼近l方法方法利用利用超平面超平面切除切除l要求要求l松弛问题最优解松弛问题最优解删除删除l整数解整数
13、解保留保留 第27页，共50页，编辑于2022年，星期三例：例：x2Ox124624解：解：1.用单纯形算法求解松弛问题的最优解用单纯形算法求解松弛问题的最优解2.构造割平面构造割平面第28页，共50页，编辑于2022年，星期三cj cB xB xjbcB cN 0 第29页，共50页，编辑于2022年，星期三非整数非整数第30页，共50页，编辑于2022年，星期三整数整数松弛问题最优解删除松弛问题最优解删除整数解保留整数解保留第31页，共50页，编辑于2022年，星期三cj cB xB xjbcB cN 0 第32页，共50页，编辑于2022年，星期三x2Ox124624第33页，共50页，
14、编辑于2022年，星期三作作 业业P399 88.用割平面法解整数规划用割平面法解整数规划第34页，共50页，编辑于2022年，星期三第三节第三节 分支分支定界定界法法整数线性规划的整数线性规划的求解方法求解方法第35页，共50页，编辑于2022年，星期三“大事化小，小事化了大事化小，小事化了”把一个规模较大的问题把一个规模较大的问题分解分解成若成若干个干个分支分支，逐支逐支求解，然后找出求解，然后找出原问题的解。原问题的解。第36页，共50页，编辑于2022年，星期三例例123123(3/2,10/3)(3/2,10/3)x1=3/2,分为x11与x12SS2S1x11x12S2S1分别解之
15、分别解之先放弃先放弃“整数整数”要要求求求出一个最优解。求出一个最优解。第37页，共50页，编辑于2022年，星期三123123S1S2n n解解S S1 1,求出一个最优解求出一个最优解(2,23/9),max(2,23/9),maxz=41/9n n解解S S2 2,求出一个最优解求出一个最优解(1,7/3),max(1,7/3),maxz=10/3S SS S2 2S S1 1x11x12(2,23/9)(2,23/9)(2,23/9)(2,23/9)x x2 2=23/9=23/9,分为分为分为分为x x2 222与与与与x x2 233S S1212S S1111x22x23可可可可
16、行行行行域域域域为为为为空空空空S12S11第38页，共50页，编辑于2022年，星期三123123S12(33/14,2)(33/14,2)(33/14,2)(33/14,2)n n解解S S1212,求出一个最优解求出一个最优解(33/14,2),max(33/14,2),maxz=61/14S SS S2 2S S1 1x11x12S S1212S S1111x22x23可可可可行行行行域域域域为为为为空空空空10/310/361/1461/14S S122122S S121121x12x13x x1 1=33/14=33/14,分为分为分为分为x x1 122与与与与x x1 133S
17、121S122第39页，共50页，编辑于2022年，星期三123123S SS S2 2S S1 1x11x12S S1212S S1111x22x23可可可可行行行行域域域域为为为为空空空空10/310/3S S122122S S121121x12x13S121S122n n解解S S121121,求出一个最优解求出一个最优解(3,1),max(3,1),maxz=4n n解解S S122122,求出一个最优解求出一个最优解(2,2),max(2,2),maxz=4(2,2)(2,2)(2,2)(2,2)(3,1)(3,1)(3,1)(3,1)44最优整数最优整数最优整数最优整数解解解解为为
18、为为(3,1)(3,1)和和和和(2,2)(2,2)最优最优最优最优值值值值为为为为4 4第40页，共50页，编辑于2022年，星期三Example9Subproblem1Subproblem2Subproblem3Subproblem4Subproblem5Subproblem6Subproblem7BranchBound第41页，共50页，编辑于2022年，星期三算法思想算法思想先先放弃放弃“整数整数”要求求出一个最优解要求求出一个最优解,如是如是整整数，结束。数，结束。否则否则,以一个变量的取整值以一个变量的取整值“分支分支”，分为两，分为两个个(分别添加一个约束分别添加一个约束),),
19、再各求出其最优解。再各求出其最优解。如得如得一整数解，将其目标函数的值添加为以后一整数解，将其目标函数的值添加为以后诸分支的约束诸分支的约束 定界定界。如此反复直到找到整数。如此反复直到找到整数解，而且其余分支无可行解结束。解，而且其余分支无可行解结束。第42页，共50页，编辑于2022年，星期三分支的方法分支的方法第43页，共50页，编辑于2022年，星期三第44页，共50页，编辑于2022年，星期三第45页，共50页，编辑于2022年，星期三定定 界界n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分支后计算松弛的线性规划的最优解分支后计算松弛的线性规划的最优解n整数解
20、整数解 目标值目标值 优于优于原有最好解的值则替代原有最好解原有最好解的值则替代原有最好解 劣于劣于原有最好解的值则删除该分支原有最好解的值则删除该分支 等于等于原有最好解的值则终止该分支原有最好解的值则终止该分支n非整数解非整数解 目标值目标值 优于优于原有最好解的值则继续分支原有最好解的值则继续分支 劣于劣于或等于原有最好解的值则删除该分支或等于原有最好解的值则删除该分支第46页，共50页，编辑于2022年，星期三n n只解松弛问题只解松弛问题1、在全部可行域上解松弛问题、在全部可行域上解松弛问题n n若松弛问题最优解为整数解，则其也是整数规若松弛问题最优解为整数解，则其也是整数规若松弛问
21、题最优解为整数解，则其也是整数规若松弛问题最优解为整数解，则其也是整数规划的最优解划的最优解划的最优解划的最优解2、分支过程分支过程分支过程分支过程n n若松弛问题最优解中某个若松弛问题最优解中某个若松弛问题最优解中某个若松弛问题最优解中某个 x xk=b=bk k 不是整数，令不是整数，令不是整数，令不是整数，令 b bk k 为为为为 b bk k 的整数部分的整数部分的整数部分的整数部分n n构造两个新的约束条件构造两个新的约束条件构造两个新的约束条件构造两个新的约束条件 x xk k bk k 和和和和 xk k b bk k +1，分别加于原松弛问题，形成，分别加于原松弛问题，形成，
22、分别加于原松弛问题，形成，分别加于原松弛问题，形成两个新的两个新的整数规整数规划划3 3、求解分、求解分、求解分、求解分支支支支的松弛问题的松弛问题 定界过程定界过程定界过程定界过程n n设两个设两个设两个设两个分分分分支支支支的松弛问题分别为问题的松弛问题分别为问题的松弛问题分别为问题的松弛问题分别为问题 1 1 和问题和问题和问题和问题 2 2，它们的最优解有如下情况，它们的最优解有如下情况，它们的最优解有如下情况，它们的最优解有如下情况 第47页，共50页，编辑于2022年，星期三分分支支问题解可能出现的情况表问题解可能出现的情况表情况情况 2,4,5 找到最优解找到最优解情况情况 3
23、在缩减的域上继续分在缩减的域上继续分支支定界法定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后续分的后续分支支所得到的解进行比较，结论如情况所得到的解进行比较，结论如情况 4或或57非整数解非整数解非整数解非整数解选最优值大的优先分支选最优值大的优先分支第48页，共50页，编辑于2022年，星期三注注 意意求解混合整数规划问题，求解混合整数规划问题，只对整数变量分支只对整数变量分支，对非整数变量不分支。对非整数变量不分支。第49页，共50页，编辑于2022年，星期三作作 业业P399 88.用分支定界法解整数规划用分支定界法解整数规划第50页，共50页，编辑于2022年，星期三