第二次线性规划

1、第二次线性规划第1页，共91页，2022年，5月20日，8点43分，星期一第2页，共91页，2022年，5月20日，8点43分，星期一第3页，共91页，2022年，5月20日，8点43分，星期一第4页，共91页，2022年，5月20日，8点43分，星期一多项式时间 .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年，5月20日，8点43分，星期一第6页，共91页，2022年，5月20日，8点43分，星期一第7页，共91页，2022年，5月20日，8点43分，星期一第8页，共91页，2022年，5月20日，8点43分，星期一第9页，共91页，2022年，5月20日，8点43分，星期一课堂练习1运输问题：请把上述问题描述成一个线性规划问题。第10页，共91页，2022年，5月20日，8点43分，星期一课堂练习2机场飞机到达时间问题：请把上述问题描述成一个线性规划问题。第11页，共91页，2022年，5月20日，8点43分，星期一第12页，共91页，2022年，5月20日，8点43分，

3、星期一第13页，共91页，2022年，5月20日，8点43分，星期一第14页，共91页，2022年，5月20日，8点43分，星期一课堂练习第15页，共91页，2022年，5月20日，8点43分，星期一第16页，共91页，2022年，5月20日，8点43分，星期一第17页，共91页，2022年，5月20日，8点43分，星期一第18页，共91页，2022年，5月20日，8点43分，星期一第19页，共91页，2022年，5月20日，8点43分，星期一第20页，共91页，2022年，5月20日，8点43分，星期一第21页，共91页，2022年，5月20日，8点43分，星期一2.最优顶点定理2.2.2设

4、线性规划(LP)的可行域非空，则有下列结论：(1)线性规划(LP)存在有限最优解的充要条件是所有 为非负数，其中 是可行域的极方向。(2)线性规划(LP)存在有限最优解，则目标函数的最优值可在某个极点处达到。第22页，共91页，2022年，5月20日，8点43分，星期一2.最优基本可行解第23页，共91页，2022年，5月20日，8点43分，星期一邻接基本解求此问题的两个邻接基本解。第24页，共91页，2022年，5月20日，8点43分，星期一第25页，共91页，2022年，5月20日，8点43分，星期一课堂练习(0.5,1, 0.5,0,0)第26页，共91页，2022年，5月20日，8点4

5、3分，星期一退化：第27页，共91页，2022年，5月20日，8点43分，星期一定理：证明：第28页，共91页，2022年，5月20日，8点43分，星期一第29页，共91页，2022年，5月20日，8点43分，星期一证明：第30页，共91页，2022年，5月20日，8点43分，星期一第31页，共91页，2022年，5月20日，8点43分，星期一第32页，共91页，2022年，5月20日，8点43分，星期一第33页，共91页，2022年，5月20日，8点43分，星期一第34页，共91页，2022年，5月20日，8点43分，星期一第35页，共91页，2022年，5月20日，8点43分，星期一第36

6、页，共91页，2022年，5月20日，8点43分，星期一s.t.称为基本可行解 的检验数。第37页，共91页，2022年，5月20日，8点43分，星期一注意到：第38页，共91页，2022年，5月20日，8点43分，星期一定理3.1.2 对于非退化问题，单纯形方法经有限次迭代或达到最优基本可行解，或得出无界的结论。收敛性对于非退化情形，在每次迭代，均有：各次迭代得到的基本可行解互不相同，而基本可行解个数有限，因此有限次迭代必能得到最优解。第39页，共91页，2022年，5月20日，8点43分，星期一第40页，共91页，2022年，5月20日，8点43分，星期一第41页，共91页，2022年，5

7、月20日，8点43分，星期一 第42页，共91页，2022年，5月20日，8点43分，星期一第43页，共91页，2022年，5月20日，8点43分，星期一第44页，共91页，2022年，5月20日，8点43分，星期一-21-1000Min413-1106654-21018200-1/201/24Min407/2-5/41-1/4411-1/21/401/428第45页，共91页，2022年，5月20日，8点43分，星期一00-1/201/24Min407/2-5/41-1/4411-1/21/401/4282-10018Min451011141434-210187001222251011143

8、14012336第46页，共91页，2022年，5月20日，8点43分，星期一课堂练习第47页，共91页，2022年，5月20日，8点43分，星期一-120000Min3101001140101015110013/23/202100111010014010101501-1011/2第48页，共91页，2022年，5月20日，8点43分，星期一第49页，共91页，2022年，5月20日，8点43分，星期一第50页，共91页，2022年，5月20日，8点43分，星期一第51页，共91页，2022年，5月20日，8点43分，星期一00000110611-10010271-10-10011510001

93min611-100102271-10-100111510001003第52页，共91页，2022年，5月20日，8点43分，星期一-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页，2022年，5月20日，8点43分，星期一00000110201-1/21/201/2-

10、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页，2022年，5月20日，8点43分，星期一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页，2022年，5月20日，8点43分，星期一0000111052-110

11、10046111000164100100027302000110第56页，共91页，2022年，5月20日，8点43分，星期一-60-40000-20min52-1101004261110010664100100022730200011010/300-46000-8min50-11-2100006011-1010444100100027002-300142第57页，共91页，2022年，5月20日，8点43分，星期一00-46000-8min50-11-2100006011-1010444100100027002-3001420-40-2400-8min30-11-2100060201-110

12、4241001000270201-20142第58页，共91页，2022年，5月20日，8点43分，星期一0-40-2400-8min30-11-2100060201-1104241001000270201-2014200002000min3001-3/21/21/20220101/2-1/21/20241001000270000-1-110第59页，共91页，2022年，5月20日，8点43分，星期一第60页，共91页，2022年，5月20日，8点43分，星期一第61页，共91页，2022年，5月20日，8点43分，星期一第62页，共91页，2022年，5月20日，8点43分，星期一可知原问

13、题无可行解。第63页，共91页，2022年，5月20日，8点43分，星期一第64页，共91页，2022年，5月20日，8点43分，星期一第65页，共91页，2022年，5月20日，8点43分，星期一11-300MM041-21100011621-40-1103710-200011解：初始表格为第66页，共91页，2022年，5月20日，8点43分，星期一11-300MM041-21100011621-40-1103710-200011解：初始表格为1-3M1-M6M-30M00-4Mmin41-2110001111621-40-11033/2710-2000111第67页，共91页，2022年

14、，5月20日，8点43分，星期一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页，2022年，5月20日，8点43分，星期一00-101M-1M+1-2min40031-22-512420100-11-21110-2000110001/31/3M-1/3M-2/3230011/3-2/32/3-5/3

15、420100-11-2111002/3-4/34/3-7/39第69页，共91页，2022年，5月20日，8点43分，星期一第70页，共91页，2022年，5月20日，8点43分，星期一5.退化的线性规划问题退化的基本可行解(几何解释) 对于标准形而言，当极点仅对应一个基时，是非退化的；当极点对应多个基时，是退化的。第71页，共91页，2022年，5月20日，8点43分，星期一退化(degenerate)与循环(cycling)退化问题 单纯形法可能出现循环！ 实际中经常碰到退化问题，但很少出现循环 避免出现循环的措施：摄动法、Bland法则、字典序法第72页，共91页，2022年，5月20日

16、，8点43分，星期一0-50-40-100-6021-3020010-1031-100410000200300010-1102010-100010非退化转轴退化的基本可行解与退化转轴 基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！退化转轴指转轴后目标函数没有发生变化！退化转轴！退化基本可行解第73页，共91页，2022年，5月20日，8点43分，星期一最小系数规则： 进基变量：最小系数规则 出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选进基变量和离基变量的明确规则(多个可选时！)第74页，共91页，2022年，5月20

17、日，8点43分，星期一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页，2022年，5月20日，8点43分，星期一-2301/400-30Min63/2101/801-21/2051/16-1/80-3/64103/160033/2-11-1/80021/212/21-110-1/216000Mi

18、n62-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页，2022年，5月20日，8点43分，星期一循环！注：循环时，转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表000-3/420-1/260Min11001/4-8-190020101/2-12-1/2300300100101第77页，共91页，2022年，5月20日，8点43分，星期一避免循环的方法能进基的变量(使目标值减小)中选指标

19、最小者进基 摄动法(Dantzig，1954年) Bland法则(Bland, 1977)最小指标法则能出基的变量(保持可行)中选指标最小者出基美好愿望：构造某种永远不会产生循环的转轴规则！ 字典序法(Orden和Wolfe，1954年)第78页，共91页，2022年，5月20日，8点43分，星期一前四张单纯形表相同！第五张单纯形表是利用Bland法则作为转轴规则求解Beale的例子！0-10-5/4320-30Min60-20-1241-6011-20-3/41603030211-24061001/2-3/420061/2Min60010010111011/4-809142011/21/2-

20、12031/21第79页，共91页，2022年，5月20日，8点43分，星期一03/25/402021/25/460010010151-1/23/40-2015/23/430211-24061最后一张单纯形表/最优单纯形表第80页，共91页，2022年，5月20日，8点43分，星期一回顾有初始基本可行解的单纯形算法,对于标准:单纯形表为:第81页，共91页，2022年，5月20日，8点43分，星期一第82页，共91页，2022年，5月20日，8点43分，星期一-第83页，共91页，2022年，5月20日，8点43分，星期一-第84页，共91页，2022年，5月20日，8点43分，星期一第85页，共91页，2022年，5月20日，8点43分，星期一第86页，共91页，2022年，5月20日，8点43分，星期一K