最优化方法之单纯形法.pptx

《最优化方法之单纯形法.pptx》由会员分享，可在线阅读，更多相关《最优化方法之单纯形法.pptx（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容 (分2讲)单纯形法 两阶段法 退化情形 处理方法:Bland法则 修正单纯形法 线性规划的最优性条件第1页/共76页单纯形法 The Simplex Method*可行域的极点对应LP问题的基(本)可行解*LP的最优解一定可以在基(本)可行解中找到1.单纯形法的步骤初始基可行解最优性条件最优解换基迭代新的基可行解NYLP基本定理:第2页/共76页2.举例x1x212341234l2l1OAB(1,1.5)C 可行域（OABC）最优解：X=（1 1.5)T第3页/共76页 化成标准形 找初始基可行解 判断是否最优解?能否找到另一个基可行解使目标函数 值下降?第4页/共76页 换基迭代换

2、基：找一个非基变量作为换入变量，同时 确定一个基变量为 换出变量。依据原则：1)新的基可行解能使目标值减少；2)新的基仍然是可行基。确定换入变量：选取x1为换入变量确定换出变量:第5页/共76页 迭代（求新的基本可行解）主元素第6页/共76页 判断代入目标函数得第7页/共76页 确定进基变量和出基变量第8页/共76页 换基迭代第9页/共76页 判断代入目标函数：最优解：第10页/共76页x1x212341234l2l1OAB(1,1.5)C 可行域（OABC）最优解：X=（1 1.5)T第11页/共76页设(L)有一个初始基初始基本可行解为:第12页/共76页考虑xk的取值第13页/共76页第

3、14页/共76页第15页/共76页单纯性法计算步骤初始基为B,初始基本可行解为x(0)=(B-1b 0)T是否yk=B-1Pk0是x(0)为最优解无界是第16页/共76页例1第17页/共76页例2第18页/共76页第19页/共76页第20页/共76页表格形式的单纯形方法第21页/共76页单纯形表f xB xN 右端xBf0 Im B-1N B-1b1 0 cBB-1N-cN cBB-1b可省略检验数(判别数)目标函数取值基变量取值第22页/共76页用单纯形表求解问题：xB xN 右端xBIm B-1N B-1b0 cBB-1N-cN cBB-1b主元消去法第23页/共76页第24页/共76页第

4、25页/共76页第26页/共76页检验数基 函数值等的变化-矩阵运算第27页/共76页第28页/共76页 xB xN 右端xBIm B-1N B-1b0 cBB-1N-cN cBB-1bx1x4x51 -2 1 0 00 1 -3 1 00 1 -1 0 10 1 -2 0 02120 x1 x2 x3 x4 x5第29页/共76页x1 x2 x3 x4 x5x1x4x51 -2 1 0 00 1 -3 1 00 1 -1 0 10 1 -2 0 02120 x1x2x31 0 0 -1/2 5/20 1 0 -1/2 3/20 0 1 -1/2 1/20 0 0 -1/2 -1/213/25

5、/21/2-3/2x1x2x51 0 -5 2 00 1 -3 1 00 0 2 -1 10 0 1 -1 0411-1第30页/共76页第31页/共76页x1 x2 x3 x4 x5x4x51 1 3 1 01 4 -1 0 1-2 -1 1 0 0640 x3x10 -1 1 1/3 -1/31 3 0 1/3 2/30 6 0 1/3 5/32/314/326/3x4x10 -3 3 1 -11 4 -1 0 10 7 -1 0 2248第32页/共76页单纯形法的进一步讨论 无界解Oz-第33页/共76页结论：若zj-cj0,对应的系数列向量0，则该LP存在无界解。x1 x2 x3 x

6、4-3 1 0 1-2 0 1 111 0 0 -31264x3x2-2-31 -1 1 0-3 1 0 1x3x4242 3 0 00 1第34页/共76页 无限多个解x1x2l2l1OABC第35页/共76页x1 x2 x3 x4 2 7 1 07 2 0 14 14 0 0 x3x4212100 1 7/45 -2/451 0 -2/45 7/450 0 -2 0 x2x17/37/3-422/7 1 1/7 045/7 0 -2/7 10 0 -2 0 x2x4315-42745/7结论：若某个非基变量的检验数为零，则该LP存在多个最优解。第36页/共76页 课外练习第37页/共76页

7、第六讲 单纯形法之完善 两阶段法xa的每个分量称为人工变量.第38页/共76页两阶段法第1阶段:用单纯形法把人工变量变为非基变量，求出原问题的一个基可行解。方法：求解下列模型基变量第39页/共76页第2阶段:从得到的基本可行解出发,用单纯形法求(L)的最优解.第40页/共76页第41页/共76页第42页/共76页x1 x2 x3 x4 x5 x6 x71 1 -1 0 0 1 0-1 1 0 -1 0 0 10 2 -1 -1 0 0 0 1 2 0 0 1 0 0 x6x7x531843 0 0 2 1 0 -2-1 1 0 -1 0 0 12 0 -1 1 0 1 -12 0 -1 1 0

8、 0 -21 0 -1/2 1/2 0 1/2 -1/20 1 -1/2 -1/2 0 1/2 1/20 0 3/2 1/2 1 -1/3 -1/20 0 0 -2 0 0 -1x6x2x5x1x2x52161232012求解第1阶段问题：第43页/共76页开始第2阶段：x1 x2 x3 x4 x5x1x2x51 0 -1/2 1/2 00 1 -1/2 -1/2 00 0 3/2 1/2 10 0 3/2 -1/2 0123-4x1x2x31 0 0 2/3 1/30 1 0 -1/3 1/30 0 1 1/3 2/30 0 0 -1 -1232-73/2第44页/共76页第45页/共76页

9、1 0 -1 0 0 1-2 0 -3 -2 1 0-1/2 1 1/2 1/2 0 0-1 0 -4 -2 0 0 x2x5x610000 1 0 1/2 0 1/2 0 0 -5 -2 1 21 0 -1 0 0 1x2x5x1100 x1 x2 x3 x4 x5 x6 -1 2 1 1 0 0-4 4 -1 0 1 0-3 4 -2 0 0 01 0 -1 0 0 1x4x5x6240421-5第46页/共76页x1 x2 x3 x4 1 0 0 2/50 0 1 2/50 0 0 -1/10 x2x3x1100-10 1 0 1/2 x1 x2 x3 x4 x5 x6 1 0 0 2/

10、5 -1/5 3/50 0 1 2/5 -1/5 -2/5 0 1 0 1/2 0 1/2 0 0 -5 -2 1 21 0 -1 0 0 1x2x3x1x2x5x1100100-50 1 0 1/2 0 1/2 第2阶段第47页/共76页第48页/共76页11第49页/共76页2第50页/共76页第51页/共76页退化情形(自学)第52页/共76页x1 x2 x3 x4 x5 x6x4x5x61 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432 0 1.5 0 0 0 x1x5x61 -1 0 1 0 00 2 1 -2 1 00 2 1 -1 0 12010 2 1

11、.5 -2 0 0-401第53页/共76页*在单纯形法的计算过程中，确定出基变量时存在两个或两个以上的最小比值，这时会出现退化解。*有时，退化会造成计算过程的循环，永远达不到最优解。第54页/共76页x1 x2 x3 x4 x5 x6 x71 1/4 -8 -1 90 1 0 1/2 -12 -1/2 30 0 1 0 0 1 00 0 0 3/4 -20 1/2 -64 0 0 1 -32 -4 36-2 1 0 0 4 3/2 -150 0 1 0 0 1 0-3 0 0 0 4 7/2 -33x1x2x3x4x2x300100100-12 8 0 1 0 8 -84-1/2 1/4 0

12、 0 1 3/8 -15/40 0 1 0 0 1 0-1 -1 0 0 0 2 -18x4x5x300011/448第55页/共76页x1 x2 x3 x4 x5 x6 x7-3/2 1 1/8 0 1 -21/21/16 -1/8 0 -3/64 1 0 3/163/2 -1 1 -1/8 0 0 21/22 -3 0 -1/4 0 0 32 -6 0 -5/2 56 1 01/3 -2/3 0 -1/4 16/3 0 1-2 6 1 5/2 -56 0 01 -1 0 1/2 -16 0 0 x6x5x3x6x7x3001001001 -3 0 -5/4 28 1/2 00 1/3 0

13、1/6 -4 -1/6 10 0 1 0 0 1 00 2 0 7/4 -44 -1/2 0 x1x7x300013/1621/3第56页/共76页x1 x2 x3 x4 x5 x6 x71 1/4 -8 -1 90 1 0 1/2 -12 -1/2 30 0 1 0 0 1 00 0 0 3/4 -20 1/2 -6x1x2x30010发生循环的线性规划问题的特点：1.线性规划必然是退化的，即存在某个基变量取值为0。第57页/共76页解决退化的方法有：“摄动法”、“字典序法”、Bland规则等1974年Bland提出Bland法则：第58页/共76页 x1 x2 x3 x4 x5x2x3x5

14、 1 1 0 -4 0-2 0 1 -3 0 3 0 0 a 153d-3 0 0 0 知识应用 讨论题在求解极小化LP问题中，得到如下单纯形表：（无人工变量）1、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；4、当 x4 作为进基变量取代 x5 时，目标值的增量为多少？第59页/共76页修正单纯形法修正单纯形法-(自学自学)基本思想：基本思想：在整个计算过程中，始终保存现行基的逆。第60页/共76页计算步骤第61页/共76页第62页/共76页用修正单纯形法求解下列线性规划问题：第63页/共76页构造初始表第一次迭代:第64页/共76页1主元消去第65页/共76页第二次迭代：第66页/共76页5进行主元消去第67页/共76页第68页/共76页第三次迭代：第69页/共76页线性规划的最优性条件线性规划的最优性条件问题：最优解具有什么特征？第70页/共76页第71页/共76页Farkas引理第72页/共76页第73页/共76页第74页/共76页第75页/共76页感谢您的观看！第76页/共76页