第二次线性规划

第二次线性规划第1页，共91页，2023年，2月20日，星期三第2页，共91页，2023年，2月20日，星期三第3页，共91页，2023年，2月20日，星期三第4页，共91页，2023年，2月20日，星期三多项式时间.vs.指数时间n10205060

0.0001s0.0004s0.0025s0.0036s

0.001s1.0s35.7yrs366ctrs假定计算机一秒钟可以处理次运算计算机更新换代的影响各代计算机1小时内能处理的变量个数n当前计算机速度提高100倍速度提高1000倍

1031.6+6.64+9.97第5页，共91页，2023年，2月20日，星期三第6页，共91页，2023年，2月20日，星期三第7页，共91页，2023年，2月20日，星期三第8页，共91页，2023年，2月20日，星期三第9页，共91页，2023年，2月20日，星期三课堂练习1运输问题：请把上述问题描述成一个线性规划问题。第10页，共91页，2023年，2月20日，星期三课堂练习2机场飞机到达时间问题：请把上述问题描述成一个线性规划问题。第11页，共91页，2023年，2月20日，星期三第12页，共91页，2023年，2月20日，星期三第13页，共91页，2023年，2月20日，星期三第14页，共91页，2023年，2月20日，星期三课堂练习第15页，共91页，2023年，2月20日，星期三第16页，共91页，2023年，2月20日，星期三第17页，共91页，2023年，2月20日，星期三第18页，共91页，2023年，2月20日，星期三第19页，共91页，2023年，2月20日，星期三第20页，共91页，2023年，2月20日，星期三第21页，共91页，2023年，2月20日，星期三2.最优顶点定理2.2.2设线性规划(LP)的可行域非空，则有下列结论：(1)线性规划(LP)存在有限最优解的充要条件是所有为非负数，其中是可行域的极方向。(2)线性规划(LP)存在有限最优解，则目标函数的最优值可在某个极点处达到。第22页，共91页，2023年，2月20日，星期三2.最优基本可行解第23页，共91页，2023年，2月20日，星期三邻接基本解求此问题的两个邻接基本解。第24页，共91页，2023年，2月20日，星期三第25页，共91页，2023年，2月20日，星期三课堂练习(0.5,1,0.5,0,0)第26页，共91页，2023年，2月20日，星期三退化：第27页，共91页，2023年，2月20日，星期三定理：证明：第28页，共91页，2023年，2月20日，星期三第29页，共91页，2023年，2月20日，星期三证明：第30页，共91页，2023年，2月20日，星期三第31页，共91页，2023年，2月20日，星期三第32页，共91页，2023年，2月20日，星期三第33页，共91页，2023年，2月20日，星期三第34页，共91页，2023年，2月20日，星期三第35页，共91页，2023年，2月20日，星期三第36页，共91页，2023年，2月20日，星期三s.t.称为基本可行解的检验数。第37页，共91页，2023年，2月20日，星期三注意到：第38页，共91页，2023年，2月20日，星期三定理3.1.2对于非退化问题，单纯形方法经有限次迭代或达到最优基本可行解，或得出无界的结论。收敛性对于非退化情形，在每次迭代，均有：各次迭代得到的基本可行解互不相同，而基本可行解个数有限，因此有限次迭代必能得到最优解。第39页，共91页，2023年，2月20日，星期三第40页，共91页，2023年，2月20日，星期三第41页，共91页，2023年，2月20日，星期三

第42页，共91页，2023年，2月20日，星期三第43页，共91页，2023年，2月20日，星期三第44页，共91页，2023年，2月20日，星期三-21-1000Min413-1106654-21018200-1/201/24Min407/2-5/41-1/4411-1/21/401/428第45页，共91页，2023年，2月20日，星期三00-1/201/24Min407/2-5/41-1/4411-1/21/401/4282-10018Min451011141434-21018700122225101114314012336第46页，共91页，2023年，2月20日，星期三课堂练习第47页，共91页，2023年，2月20日，星期三-120000Min3101001140101015110013/23/202100111010014010101501-1011/2第48页，共91页，2023年，2月20日，星期三第49页，共91页，2023年，2月20日，星期三第50页，共91页，2023年，2月20日，星期三第51页，共91页，2023年，2月20日，星期三00000110611-10010271-10-10011510001003-2011000-3min611-100102271-10-100111510001003第52页，共91页，2023年，2月20日，星期三-2011000-3min611-100102271-10-10011151000100330-21-1002-1min602-1101-111/211-10-100115010110-12300000110201-1/21/201/2-1/21/2110-1/2-1/201/21/23/25001/21/21-1/2-1/23/2第53页，共91页，2023年，2月20日，星期三00000110201-1/21/201/2-1/21/2110-1/2-1/201/21/23/25001/21/21-1/2-1/23/2-210000201-1/21/201/2110-1/2-1/203/25001/21/213/2第54页，共91页，2023年，2月20日，星期三00-1/2-3/205/2min201-1/21/201/21110-1/2-1/203/25001/21/213/2303-2004min402-1101111-100250-110111010026min4010112110001330-11011第55页，共91页，2023年，2月20日，星期三0000111052-11010046111000164100100027302000110第56页，共91页，2023年，2月20日，星期三-60-40000-20min52-1101004261110010664100100022730200011010/300-46000-8min50-11-2100006011-1010444100100027002-300142第57页，共91页，2023年，2月20日，星期三00-46000-8min50-11-2100006011-1010444100100027002-3001420-40-2400-8min30-11-2100060201-1104241001000270201-20142第58页，共91页，2023年，2月20日，星期三0-40-2400-8min30-11-2100060201-1104241001000270201-2014200002000min3001-3/21/21/20220101/2-1/21/20241001000270000-1-110第59页，共91页，2023年，2月20日，星期三第60页，共91页，2023年，2月20日，星期三第61页，共91页，2023年，2月20日，星期三第62页，共91页，2023年，2月20日，星期三可知原问题无可行解。第63页，共91页，2023年，2月20日，星期三第64页，共91页，2023年，2月20日，星期三第65页，共91页，2023年，2月20日，星期三11-300MM041-21100011621-40-1103710-200011解：初始表格为第66页，共91页，2023年，2月20日，星期三11-300MM041-21100011621-40-1103710-200011解：初始表格为1-3M1-M6M-30M00-4Mmin41-2110001111621-40-11033/2710-2000111第67页，共91页，2023年，2月20日，星期三1-3M1-M6M-30M00-4Mmin41-2110001111621-40-11033/2710-200011101-M-10M03M-1-M-1min40-23100-11060100-11-211110-20001100-101M-1M+1-2min40031-22-512420100-11-21110-200011第68页，共91页，2023年，2月20日，星期三00-101M-1M+1-2min40031-22-512420100-11-21110-2000110001/31/3M-1/3M-2/3230011/3-2/32/3-5/3420100-11-2111002/3-4/34/3-7/39第69页，共91页，2023年，2月20日，星期三第70页，共91页，2023年，2月20日，星期三5.退化的线性规划问题←退化的基本可行解(几何解释)

对于标准形而言，当极点仅对应一个基时，是非退化的；当极点对应多个基时，是退化的。第71页，共91页，2023年，2月20日，星期三退化(degenerate)与循环(cycling)◎退化问题⊙单纯形法可能出现循环！⊙实际中经常碰到退化问题，但很少出现循环⊙避免出现循环的措施：摄动法、Bland法则、字典序法第72页，共91页，2023年，2月20日，星期三0-50-40-100-6021-3020010-1031-100410000200300010-1102010-100010非退化转轴退化的基本可行解与退化转轴

基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！退化转轴指转轴后目标函数没有发生变化！退化转轴！退化基本可行解第73页，共91页，2023年，2月20日，星期三最小系数规则：◎进基变量：最小系数规则◎出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选进基变量和离基变量的明确规则(多个可选时！)第74页，共91页，2023年，2月20日，星期三000-3/420-1/260Min11001/4-8-190020101/2-12-1/23003001001013000-4-7/2330Min44001-32-43602-210043/2-150030010010111000-2180Min4480108-84005-1/21/40013/8-15/400300100101第75页，共91页，2023年，2月20日，星期三-2301/400-30Min63/2101/801-21/2051/16-1/80-3/64103/160033/2-11-1/80021/212/21-110-1/216000Min62-60-5/256100071/3-2/30-1/416/301003-2615/2-560010-20-7/4441/200Min11-30-5/4281/200701/301/6-4-1/61003061001011/6第76页，共91页，2023年，2月20日，星期三

循环！注：循环时，转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表000-3/420-1/260Min11001/4-8-190020101/2-12-1/2300300100101第77页，共91页，2023年，2月20日，星期三避免循环的方法⊙能进基的变量(使目标值减小)中选指标最小者进基◎摄动法(Dantzig，1954年)◎

Bland法则(Bland,1977)－最小指标法则⊙能出基的变量(保持可行)中选指标最小者出基美好愿望：构造某种永远不会产生循环的转轴规则！◎字典序法(Orden和Wolfe，1954年)第78页，共91页，2023年，2月20日，星期三前四张单纯形表相同！第五张单纯形表是利用Bland法则作为转轴规则求解Beale的例子！0-10-5/4320-30Min60-20-1241-6011-20-3/41603030211-24061001/2-3/420061/2Min60010010111011/4-809142011/21/2-12031/21第79页，共91页，2023年，2月20日，星期三03/25/402021/25/460010010151-1/23/40-2015/23/430211-24061最后一张单纯形表/最优单纯形表第80页，共91页，2023年，2月20日，星期三回顾有初始基本可行解的单纯形算法,对于标准ＬＰ:单纯形表为:第81页，共91页，2023年，2月20日，星期三第82页，共91页，2023年，2月20日，星期三-第83页，共91页，2023年，2月20日，星期三-第84页，共91页，2023年，2月20日，星期