退化与循环学习教案

1、会计学1退化退化(tuhu)与循环与循环第一页，共50页。为避免循环为避免循环(xnhun)，伯兰特，伯兰特(Bland)规则：规则：1. 当存在多个当存在多个 ，始终选取，始终选取下标值为最下标值为最小小的变量作为进基变量。的变量作为进基变量。0j2.当当 出现两个以上相同的最小比值时，始出现两个以上相同的最小比值时，始终选取终选取下标值为最小下标值为最小的变量为离基变量的变量为离基变量第2页/共49页第二页，共50页。0. .minxbAxtsxcT0 x)(bAx. t . sxcminT12( ).,njjjTnbbpbA是充分小的正数。第3页/共49页第三页，共50页。其摄动问题是非

2、退化的其摄动问题是非退化的时，时，使得当，使得当实数实数存在存在：对于线性规划问题，：对于线性规划问题，定理定理10013.3.1利用利用(lyng)单纯形法求解摄动问单纯形法求解摄动问题时，题时，不会出现循环现象。不会出现循环现象。第4页/共49页第四页，共50页。是原问题的基本可行解是原问题的基本可行解则则解，解，是摄动问题的基本可行是摄动问题的基本可行，设对于充分小的设对于充分小的定理定理)(x )(x :.00233是原问题的最优解。是原问题的最优解。则则是摄动问题的最优解，是摄动问题的最优解，推论：设对于充分小的推论：设对于充分小的)(x)(x00第5页/共49页第五页，共50页。则

3、原问题也没有可行解则原问题也没有可行解解，解，：若摄动问题没有可行：若摄动问题没有可行定理定理3.3.33.3.4:0定理设对于充分小的，摄动问题是无界的，则原问题也是无界的。第6页/共49页第六页，共50页。)(b01bB01)(bB0013213121x,x,xxxxx0013213231x,x,xxxxx基列下标基列下标(xi bio)小于非基小于非基列下标列下标(xi bio)第7页/共49页第七页，共50页。n,.,mi ,xm,.,i ,bxiii101是是若若原原问问题题的的基基本本可可行行解解1,1,.,0,1,.,nijijiij mixbaimximn则摄动问题的基本可行解

4、是第8页/共49页第八页，共50页。1( )nijjiiikikikjbbaaaa决定于低次项。决定于低次项。该多项式值的大小主要该多项式值的大小主要是充分小的正数，是充分小的正数，。不需出现在单纯形表中不需出现在单纯形表中第9页/共49页第九页，共50页。01032112210984162120436376542765417654jxxxxx/xx/xxxxx/x. t . sxx/xx/Zmin例：例：),(),(),(6413413214501010043f,xT第10页/共49页第十页，共50页。第11页/共49页第十一页，共50页。出基出基为主元素，为主元素，llklklikikix

5、aaba|abmin0aaaa, babb:)li ( i)(a/aa,a/bb:)(.xx.ljikijijlikiilkljljlklllk其他行其他行对主行对主行列新的单纯形表列新的单纯形表替换替换用用迭代运算迭代运算2121第12页/共49页第十二页，共50页。第13页/共49页第十三页，共50页。出基出基为主元素，为主元素，llklklikikixaaba|abmin0aaaa, babb:)li ( i)(a/aa,a/bb:)(.xx.ljikijijlikiilkljljlklllk其他行其他行对主行对主行列新的单纯形表列新的单纯形表替换替换用用迭代运算迭代运算2121第14页

6、/共49页第十四页，共50页。Integer Programming (IP)第15页/共49页第十五页，共50页。nqjxqjxmpibxapibxatsxczjjijijnjijijnjnjjj,.,1,.,10,.,1)(,.,1. .min)max(111或中部分或全部取整数jx整数线性规划整数线性规划(xin xn u hu)模型模型第16页/共49页第十六页，共50页。整数整数(zhngsh)线性规划类型线性规划类型1.纯整数(zhngsh)线性规划：2.混合整数(zhngsh)线性规划：3.：取整数中全部全部jx取整数中部分部分jx1 10 0或或只能取值jx第17页/共49页第

7、十七页，共50页。序号时段最少人数安排人数1061060 x12101470 x23141860 x34182250 x45220220 x56020630 x6最少需要多少最少需要多少(dusho)护士？护士？第18页/共49页第十八页，共50页。收益最大。收益最大。第19页/共49页第十九页，共50页。 现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择的投资项目有n个，项个，项目目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j=1,2,.,n）。此外。此外(cwi)， 由于种种原因，有三个附加条件：由于种种原因，有三个附加条件：第一，若选择项目第一，若

8、选择项目1，就必须同时选择项目，就必须同时选择项目2。反之，则。反之，则不一定；不一定；第二，项目第二，项目3和和4中至少选择一个；中至少选择一个；第三，项目第三，项目5，6和和7中恰好选择两个。中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？不投资不投资投资投资jjxj对项目对项目01第20页/共49页第二十页，共50页。特征特征变量整数性要求变量整数性要求(yoqi)来源来源 问题本身的要求问题本身的要求(yoqi) 引入的逻辑变量的需要引入的逻辑变量的需要性质性质可行域是离散集合可行域是离散集合第21页/共49页第二十一页，共50页

9、。整数规划整数规划 0.minxbAxtsxc 放松的线性规划放松的线性规划可行可行(kxng)解是松弛问解是松弛问题的可行题的可行(kxng)解解最优值不会最优值不会(b hu)优于其松弛问题优于其松弛问题的最优值的最优值第22页/共49页第二十二页，共50页。第23页/共49页第二十三页，共50页。7.4 解纯整数解纯整数(zhngsh)规划的规划的割平面法割平面法1958年由R.E.Gomory首先(shuxin)提出第24页/共49页第二十四页，共50页。第25页/共49页第二十五页，共50页。例：例： 为为整整数数212121212121,0,521045323.3maxxxxxxx

10、xxxxtsxxzx2Ox124624解：解：用单纯形算法求解松弛问题的最优解用单纯形算法求解松弛问题的最优解构造构造(guzo)割平面割平面第26页/共49页第二十六页，共50页。BibxaxiNjjiji,cjjTBxTNxBcBxbB1BB1NB1zbBcB1NBccBN1 cB xB xjbcB cN 0 j第27页/共49页第二十七页，共50页。0, 00iNjjjiibxax jijijifaa, 0, 0, 0 jijiaa, 0, 0 000iiifbb 00iibb 非整数非整数(zhngsh) 00, 0, 00iiNjNjjjijjiifbxfxax10, 0 jif10

11、0 if第28页/共49页第二十八页，共50页。 NjjjiiNjijjiixffbxax, 000, 00整数整数(zhngsh)0 10, 0 jif100 if0, 00Njjjiixff0 0, 0)(iNjjjifxf松弛问题松弛问题(wnt)最优解删除最优解删除整数解保留整数解保留0, 0)(iNjjjifsxf第29页/共49页第二十九页，共50页。cjjTBxTNxBcBxbB1BB1NB1zbBcB1NBccBN1 cB xB xjbcB cN 0 jjiiffs,0000 s010第30页/共49页第三十页，共50页。为整数：例212121212121,0,52104532

12、3. .3max 5xxxxxxxxxxtsxxzx2Ox124624第31页/共49页第三十一页，共50页。作作 业业P399 88.用割平面法解整数用割平面法解整数(zhngsh)规划规划第32页/共49页第三十二页，共50页。第33页/共49页第三十三页，共50页。第34页/共49页第三十四页，共50页。取整数2121212121,0,3121451149.maxxxxxxxxxtsxxz123123x1=3/2,分为(fn wi)x11与x12x11x12S2S1第35页/共49页第三十五页，共50页。123123S1S2x11x12x22x23S12S11第36页/共49页第三十六页

13、，共50页。123123S12x11x12x22x23x12x13S121S122第37页/共49页第三十七页，共50页。123123x11x12x22x23x12x13S121S122第38页/共49页第三十八页，共50页。integer,0,45596.58max2121212121xxxxxxxxtsxxzExample 9Subproblem 14/9, 4/15, 4/16521xxzSubproblem 25/9, 4,4121xxzSubproblem 340, 3, 3,3921LBxxzSubproblem 4infeasibleSubproblem 51, 9/40, 9/

14、36521xxzSubproblem 6solution candidate, 0, 5,4021xxzSubproblem 7solution candidate, 1, 4,3721xxz41x31x22x12x51x41xBranchBound第39页/共49页第三十九页，共50页。行解结束。行解结束。第40页/共49页第四十页，共50页。NB1IbBcB1N0bB1Zbxrr 1rrrbxb第41页/共49页第四十一页，共50页。为整数xxbAxtsxc, 0. .min 第42页/共49页第四十二页，共50页。第43页/共49页第四十三页，共50页。第44页/共49页第四十四页，共5

15、0页。第45页/共49页第四十五页，共50页。情况情况 2, 4, 5 找到最优解找到最优解情况情况 3 在缩减的域上继续在缩减的域上继续(jx)分支定界法分支定界法情况情况 6 问题问题 1 的整数解作为界被保留，用于以后与问题的整数解作为界被保留，用于以后与问题 2 的后的后续分支所得到的解进行比较，结论如情况续分支所得到的解进行比较，结论如情况 4或或57非整数解非整数解非整数解非整数解选最优值大的优先分支选最优值大的优先分支第46页/共49页第四十六页，共50页。第47页/共49页第四十七页，共50页。作作 业业P399 88.用分支定界法解整数用分支定界法解整数(zhngsh)规划规划第48页/共49页第四十八页，共50页。感谢您的观看感谢您的观看(gunkn)！第49页/共49页第四十九页，共5