《第二次线性规划PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二次线性规划PPT讲稿.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二次线性规划第1页，共91页，编辑于2022年，星期三第2页，共91页，编辑于2022年，星期三第3页，共91页，编辑于2022年，星期三第4页，共91页，编辑于2022年，星期三多项式时间多项式时间.vs.指数时间指数时间 n 10 20 50 60 0.0001s 0.0004s0.0025s0.0036s 0.001s1.0s35.7yrs366ctrs假定计算机一秒钟可以处理 次运算计算机更新换代的影响计算机更新换代的影响各代计算机各代计算机1小时内能处理的变量个数小时内能处理的变量个数 n当前计算机 速度提高100倍速度提高1000倍 10 31.6 +6.64 +9.97第5页，
2、共91页，编辑于2022年，星期三第6页，共91页，编辑于2022年，星期三第7页，共91页，编辑于2022年，星期三第8页，共91页，编辑于2022年，星期三第9页，共91页，编辑于2022年，星期三课堂练习课堂练习1运输问题：运输问题：请把上述问题描述成一个线性规划问题。请把上述问题描述成一个线性规划问题。第10页，共91页，编辑于2022年，星期三课堂练习课堂练习2机场飞机到达时间问题：机场飞机到达时间问题：请把上述问题描述成一个线性规划问题。请把上述问题描述成一个线性规划问题。第11页，共91页，编辑于2022年，星期三第12页，共91页，编辑于2022年，星期三第13页，共91页，编
3、辑于2022年，星期三第14页，共91页，编辑于2022年，星期三课堂练习课堂练习第15页，共91页，编辑于2022年，星期三第16页，共91页，编辑于2022年，星期三第17页，共91页，编辑于2022年，星期三第18页，共91页，编辑于2022年，星期三第19页，共91页，编辑于2022年，星期三第20页，共91页，编辑于2022年，星期三第21页，共91页，编辑于2022年，星期三2.最优顶点最优顶点定理定理2.2.2设线性规划设线性规划(LP)的可行域非空，则有下列结论：的可行域非空，则有下列结论：(1)线性规划线性规划(LP)存在有限最优解的充要条件是所有存在有限最优解的充要条件是所
4、有 为为非负数，其中非负数，其中 是可行域的极方向。是可行域的极方向。(2)线性规划线性规划(LP)存在有限最优解，则目标函数的最优值可存在有限最优解，则目标函数的最优值可在某个极点处达到。在某个极点处达到。第22页，共91页，编辑于2022年，星期三2.最优基本可行解最优基本可行解第23页，共91页，编辑于2022年，星期三邻接基本解邻接基本解求此问题的两个邻接基本解。求此问题的两个邻接基本解。第24页，共91页，编辑于2022年，星期三第25页，共91页，编辑于2022年，星期三课堂练习课堂练习(0.5,1,0.5,0,0)第26页，共91页，编辑于2022年，星期三退化退化：第27页，共
5、91页，编辑于2022年，星期三定理：定理：证明：证明：第28页，共91页，编辑于2022年，星期三第29页，共91页，编辑于2022年，星期三证明：证明：第30页，共91页，编辑于2022年，星期三第31页，共91页，编辑于2022年，星期三第32页，共91页，编辑于2022年，星期三第33页，共91页，编辑于2022年，星期三第34页，共91页，编辑于2022年，星期三第35页，共91页，编辑于2022年，星期三第36页，共91页，编辑于2022年，星期三s.t.s.t.称为基本可行解 的检验数。第37页，共91页，编辑于2022年，星期三注意到：注意到：第38页，共91页，编辑于2022
6、年，星期三定理定理3.1.2 对于非退化问题，单纯形方法经有限次迭代或对于非退化问题，单纯形方法经有限次迭代或达到最优基本可行解，或得出无界的结论。达到最优基本可行解，或得出无界的结论。收敛性收敛性对于非退化情形，在每次迭代，均有：对于非退化情形，在每次迭代，均有：各次迭代得到的基本可行解互不相同，而基本可行解个数有限，各次迭代得到的基本可行解互不相同，而基本可行解个数有限，因此有限次迭代必能得到最优解。因此有限次迭代必能得到最优解。第39页，共91页，编辑于2022年，星期三第40页，共91页，编辑于2022年，星期三第41页，共91页，编辑于2022年，星期三 第42页，共91页，编辑于2
7、022年，星期三第43页，共91页，编辑于2022年，星期三第44页，共91页，编辑于2022年，星期三-21-1000 Min413-1106 654-21018 200-1/2 01/24 Min407/2-5/4 1-1/4411-1/21/401/42 8第45页，共91页，编辑于2022年，星期三00-1/2 01/24 Min407/2-5/4 1-1/4411-1/21/401/42 82-10018Min45101114 1434-21018700122225101114314012336第46页，共91页，编辑于2022年，星期三课堂练习课堂练习第47页，共91页，编辑于20
8、22年，星期三-120000Min3101001140101015110013/2 3/202100111010014010101501-1 011/2第48页，共91页，编辑于2022年，星期三第49页，共91页，编辑于2022年，星期三第50页，共91页，编辑于2022年，星期三第51页，共91页，编辑于2022年，星期三00000110611-10010271-10-10011510001003-2011000-3min611-100102271-10-100111510001003第52页，共91页，编辑于2022年，星期三-2011000-3min611-100102271-10-1
9、0011151000100330-21-1002-1min602-1101-111/211-10-100115010110-12300 000110201-1/21/201/2-1/2 1/2110-1/2-1/201/21/23/2500 1/21/21-1/2-1/2 3/2第53页，共91页，编辑于2022年，星期三00 000110201-1/21/201/2-1/2 1/2110-1/2-1/201/21/23/2500 1/21/21-1/2-1/2 3/2-21 0000201-1/21/201/2110-1/2-1/203/2500 1/21/213/2第54页，共91页，编辑
10、于2022年，星期三00-1/2-3/205/2min201-1/21/201/21110-1/2-1/203/2500 1/21/213/2303-2004min402-1101111-100250-110111010026min4010112110001330-11011第55页，共91页，编辑于2022年，星期三0000111052-11010046111000164100100027302000110第56页，共91页，编辑于2022年，星期三-60-40000-20 min52-1101004261110010664100100022730200011010/300-46000-8m
11、in50-11-2100006011-1010444100100027002-300142第57页，共91页，编辑于2022年，星期三00-46000-8min50-11-2100006011-1010444100100027002-3001420-40-2400-8min30-11-2100060201-1104241001000270201-20142第58页，共91页，编辑于2022年，星期三0-40-2400-8min30-11-2100060201-1104241001000270201-2014200002000min3001-3/2 1/21/20220101/2-1/2 1/2
12、0241001000270000-1-110第59页，共91页，编辑于2022年，星期三第60页，共91页，编辑于2022年，星期三第61页，共91页，编辑于2022年，星期三第62页，共91页，编辑于2022年，星期三可知原问题无可行解。可知原问题无可行解。第63页，共91页，编辑于2022年，星期三第64页，共91页，编辑于2022年，星期三第65页，共91页，编辑于2022年，星期三11-300M M041-2 1100011621-40-1 103710-200011解：初始表格为解：初始表格为第66页，共91页，编辑于2022年，星期三11-300M M041-2 110001162
13、1-40-1 103710-200011解：初始表格为解：初始表格为1-3M1-M 6M-3 0 M00-4Mmin41-211 0001111621-40-1 1033/2710-20 00111第67页，共91页，编辑于2022年，星期三1-3M1-M 6M-3 0 M00-4Mmin41-211 0001111621-40-1 1033/2710-20 001110 1-M-10M03M-1-M-1min40-23100-11060 100-11-21111 0-2000110 0-1 01M-1M+1-2min40 031-22-512420 100-11-2111 0-2 00011
14、第68页，共91页，编辑于2022年，星期三0 0-1 01M-1M+1-2min40 031-22-512420 100-11-2111 0-2 000110 001/3 1/3M-1/3M-2/3230 011/3-2/3 2/3-5/3420 100-11-2111 002/3-4/3 4/3-7/39第69页，共91页，编辑于2022年，星期三第70页，共91页，编辑于2022年，星期三5.退化的线性规划问题退化的线性规划问题退化的基本可行解退化的基本可行解(几何解释几何解释)对于标准形而言，当极点仅对应一个基时，是非退化的；当极对于标准形而言，当极点仅对应一个基时，是非退化的；当极点
15、对应多个基时，是退化的。点对应多个基时，是退化的。第71页，共91页，编辑于2022年，星期三退化退化(degenerate)与循环与循环(cycling)退化问题退化问题 单纯形法单纯形法可能出现可能出现循环！循环！实际中经常碰到退化问题，但实际中经常碰到退化问题，但很少出现很少出现循环循环 避免出现循环的措施：避免出现循环的措施：摄动法、摄动法、Bland法则、字典序法法则、字典序法第72页，共91页，编辑于2022年，星期三0-50-40-100-6021-3020010-1031-100410000200300010-1102010-100010非退化非退化转轴转轴退化的基本可行解与退
16、化转轴退化的基本可行解与退化转轴 基本可行解是退化基本可行解是退化的当且仅当单纯形表最后一列有一的当且仅当单纯形表最后一列有一个或者多个零！个或者多个零！退化转轴退化转轴指转轴后目标函数没有发生变化！指转轴后目标函数没有发生变化！退化退化转轴！转轴！退化退化基本可行解基本可行解第73页，共91页，编辑于2022年，星期三最小系数规则最小系数规则：进基变量：最小系数规则进基变量：最小系数规则 出基变量：最小指标规则出基变量：最小指标规则循环的例子循环的例子Beale循环循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选进基变量和离
17、基变量的明确规则转轴规则：选进基变量和离基变量的明确规则(多个可选时！多个可选时！)第74页，共91页，编辑于2022年，星期三0 00-3/4 20-1/2 60Min1 1 00 1/4-8-19002 0 10 1/2-12-1/2 3003 0 01 00101300 0-4-7/2 330Min4 400 1-32-43602-2 10 043/2-15003 001 00101110 0 0-2180 Min4 480 1 08-840 05-1/2 1/4 0 0 13/8-15/4 0 03 001 0 0101第75页，共91页，编辑于2022年，星期三-230 1/400-
18、30Min6 3/210 1/801-21/205 1/16-1/8 0-3/64103/16003 3/2-11-1/80021/212/21-110-1/216000 Min6 2-60-5/256100 07 1/3-2/3 0-1/416/3 010 03-2615/2-560010-20-7/4 441/200 Min1 1-30-5/4 281/2007 0 1/30 1/6-4-1/610 03 0 61 00101 1/6第76页，共91页，编辑于2022年，星期三循环！循环！注：注：循环时，转轴序列中所有循环时，转轴序列中所有BFS都是退化的！是都是退化的！是同一个同一个BF
19、S！第七张单纯形表第七张单纯形表0 00-3/4 20-1/2 60Min1 1 00 1/4-8-19002 0 10 1/2-12-1/2 3003 0 01 00101第77页，共91页，编辑于2022年，星期三避免循环的方法避免循环的方法 能进基的变量能进基的变量(使目标值减小使目标值减小)中选指标最小者进基中选指标最小者进基 摄动法摄动法(Dantzig，1954年年)Bland法则法则(Bland,1977)最小指标法则最小指标法则 能出基的变量能出基的变量(保持可行保持可行)中选指标最小者出基中选指标最小者出基美好愿望：构造某种美好愿望：构造某种永远不会产生循环的永远不会产生循环
20、的转轴规则！转轴规则！字典序法字典序法(Orden和和Wolfe，1954年年)第78页，共91页，编辑于2022年，星期三前四张前四张单纯形表相同！第五张单纯形表是单纯形表相同！第五张单纯形表是利用利用Bland法则法则作为转轴规则求解作为转轴规则求解Beale的例子！的例子！0-1 0-5/4320-30Min6 0-2 0-1241-601 1-2 0-3/4160303 0 211-2406100 1/2-3/4 20061/2Min6 00 1001011 10 11/4-809142 01 1/2 1/2-12031/21第79页，共91页，编辑于2022年，星期三03/25/4
21、02021/25/46 001001015 1-1/23/4 0-2015/23/43 0211-24061最后一张单纯形表最后一张单纯形表/最优单纯形表最优单纯形表第80页，共91页，编辑于2022年，星期三回顾有初始基本可行解的单纯形算法回顾有初始基本可行解的单纯形算法,对于标准对于标准:单纯形表为单纯形表为:第81页，共91页，编辑于2022年，星期三第82页，共91页，编辑于2022年，星期三-第83页，共91页，编辑于2022年，星期三-第84页，共91页，编辑于2022年，星期三第85页，共91页，编辑于2022年，星期三第86页，共91页，编辑于2022年，星期三Klee-Min
22、ty问题问题(1972)n=3时：第87页，共91页，编辑于2022年，星期三扭曲的立方体扭曲的立方体(A distorted Cube)约束集是如下立方体的约束集是如下立方体的稍微稍微(minor)扭曲：扭曲：n=3时：时：9608第88页，共91页，编辑于2022年，星期三指数指数(Exponential)Klee-Minty的问题说明：的问题说明：当求解具有当求解具有 n 个变量和约束的问题时，个变量和约束的问题时，最小系数最小系数规则有可能需规则有可能需要要 2n-1 次转轴次转轴(因此因此遍历遍历了扭曲立方体的了扭曲立方体的 2n 个顶点个顶点)当当 n=70 时，时，假设假设1秒钟
23、迭代秒钟迭代1000次，求解这个问题需要次，求解这个问题需要400亿年；亿年；宇宙的估计年龄是宇宙的估计年龄是137亿年亿年.然而每天求解的问题中，变量在然而每天求解的问题中，变量在10,000到到100,000之间的很普遍之间的很普遍.Worst case analysis is just that:worst case.第89页，共91页，编辑于2022年，星期三复杂度复杂度(Complexity)排序：排序：O(nlogn)矩阵乘以向量：矩阵乘以向量：O(n2)矩阵乘以矩阵：矩阵乘以矩阵：O(n3)解线性方程组：解线性方程组：O(n3)单纯形法：单纯形法：最坏情况：最坏情况：O(n22n)平均情况：平均情况：O(n3)问题：问题：是否存在求解线性规划的方法，它是否存在求解线性规划的方法，它的最坏性能分析是多项式的的最坏性能分析是多项式的?第90页，共91页，编辑于2022年，星期三1.1.用用LingoLingo软件求解软件求解Klee-Minty问题问题(n=3),P119,1.(4),2.(10)2.用某种你熟悉的高级语言编写单纯形算法求解用某种你熟悉的高级语言编写单纯形算法求解以上问题，与以上问题，与Lingo软件求解过程作比较。软件求解过程作比较。第一次作业第一次作业第91页，共91页，编辑于2022年，星期三