最优化课件lecture3单纯形法

1、最优化方法最优化方法 Optimization第三章第三章 单纯形法单纯形法主要内容主要内容 单纯形法单纯形法 两阶段法两阶段法线性规划的最优性条件线性规划的最优性条件单纯形法单纯形法* *可行域的极点对应可行域的极点对应LPLP问题的基本可行解问题的基本可行解* *LPLP的最优解一定可以在基本可行解中找到的最优解一定可以在基本可行解中找到1. 1. 单纯形法的步骤单纯形法的步骤初始基可行解初始基可行解最优性条件最优性条件最优解最优解换基迭代换基迭代新的基可行解新的基可行解NYLPLP基本定理基本定理: : 12min. .00,m nnfxcxLPstAxbAr AmbxAP PP设设(L

2、)有一个初始基有一个初始基12,mBP PPAB N初始基本可行解为初始基本可行解为: 010TxB b 01()Bf xc B b 01,0jjjRzcx对任意的有，则为最优解。考虑考虑xk的取值的取值 1011120.max0,0,0,0,jjkkj RjjTNkBNkkkjkkjjRzczczcxxxB bB Nxby xbB bfyBxfzcxPx存在使得令取则其中而单纯型法计算步骤单纯型法计算步骤初始基为初始基为B,初始基本可行解为初始基本可行解为x(0)=(B-1b 0)T是否是否yk=B-1Pk001jjBcPBc是否所有的为进基变量。为离基变量，换基，即代替以kBBkxxPPr

3、r是是x(0)为最优解为最优解max0kkjjzczcmin|0riikrkikbbyyy取无界无界是是1bB b121231241234min . 321 25 ,0zxxstxxxxxxx xxx1jjBjjzcc B Pc123432102101AP P P P解：系数矩阵113412111111222211221010115,0 00 0 ,01010201TTTTBNBBBBBxB bx xxx xcfc B bzcwPczcwcwBycPB P 令称为单纯形乘第 次迭代：原子问题无界。例例1 11212312412512345min4 . 24 2312 3 ,0 xxs t xx

4、xxxxxxxxxxxx1jjBjjzcc B Pc1234512 1 0 0423 0 1 01211 0 0 13( 4, 1,0,0,0)AP P P P Pbc ：，解解例例2 2表格形式的单纯形方法表格形式的单纯形方法 11min2. .,0BBNNBNBNBNfxc xc xstBxNxbxB bB Nxxx min1. .001BBNNfxcxstAxbbxxAB Nxcc cx等价于 1111min3. .1,0BNNNBNBNfxcB bB Nxc xstxB NxB bxx等价于 1111min. .040,0mBNBBNNBBNfxstfxI xB NxB bfxxc B

5、 Ncxc B bxx单纯形表单纯形表f xB xN 右端右端xBf0 Im B-1N B-1b1 0 cBB-1N-cN cBB-1b可省略可省略检验数检验数(判别数判别数)目标函数取值目标函数取值基变量基变量取值取值 12121211111n mn mn mNNNNNNNNNB NBPPPB PB PB Pyyy112mB bb bb 12121212112211n mn mn mn mn mn mBNBNNNNNNNNNNNNNNNNNNc B Ncc BPPPccczzzccczczczc用单纯形表求解极小化问题：用单纯形表求解极小化问题： xB xN 右端右端xBIm B-1N B-

6、1b0 cBB-1N-cN cBB-1b 110BNc B Nc若，则现行基本可行解为最优解。110,0BNbB bxB bxx假设有一基本可行解主元消去法主元消去法 120.Bjjc B Pc若存在，用求改进的基本可行解 11100,0,min|00,0,0,0,0.irikkikikrkTrrmkrkkrkkbbci yxyyyxxxxxxbfxfxzcfxy若取进基变量x得的值则新解取且在非退化情况下在非退化情况下()rjjjjjkkrkkkrrrkyzczczcjryzczcy 在新基下，检验数的变化：在新基下，检验数的变化：在新基下，目标函数值的变化：在新基下，目标函数值的变化：()

7、rkkrkbffzcy xB xN 右端右端xBIm B-1N B-1b0 cBB-1N-cN cBB-1b2312323423512345min2 s.t 2 2 312 ,0 xxxxxxxxxxxx xxxxx1x4x51 -2 1 0 00 1 -3 1 00 1 -1 0 10 1 -2 0 02120 x1 x2 x3 x4 x5x1 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/2

8、13/25/21/2-3/2x1x2x51 0 -5 2 00 1 -3 1 00 0 2 -1 10 0 1 -1 0411-1min1351*22232Txf 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 2248max142*033263Txf单纯形法的进一步讨论单纯形法的进一步讨论 无界解无界解1212311242j min23 s.t 2 -3 4

9、0 1,2,3,4zxxxxxlxxxlxj 例：O1x2x2l1lz-1312312126, 34620,430 xxxxxxxx11,xxz 对 无约束结论：结论：若若zj-cj0,对应的系数列向量对应的系数列向量0，则该，则该LP存在无界解。存在无界解。x1 x2 x3 x4-3 1 0 1-2 0 1 111 0 0 31264x3x2-2-31 -1 1 0-3 1 0 1x3x4242 3 0 002 3 0 01 多个解多个解12121122 min414 2721 7221 zxx s.txxlxxl 例：x1x2l2l1OABCx1 x2 x3 x4 2 7 1 07 2 0

10、 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(1)(2)*770 3 0 15, 0 04233TTxxz 结论：结论：若某个非基变量的检验数为零，则该若某个非基变量的检验数为零，则该LPLP存在多个最优解存在多个最优解。Ex 陈宝林书陈宝林书 P118 1. (1)两阶段法两阶段法 min. .00m nf xcxLstAxbAr Ambx *1,00*aaaaAxxbxmx xxxb 为的基本可行解。

11、xa的每个分量称为的每个分量称为人工变量人工变量.两阶段法两阶段法第第1 1阶段阶段: :用单纯形法把人工变量变为非基变量，求出原用单纯形法把人工变量变为非基变量，求出原 问题的一个基本可行解。问题的一个基本可行解。 方法：求解下列模型方法：求解下列模型min. .111,0,TaTaaTTTTaae xstAxxbex xxxe x最优解为：最优值. 10axL若，则无可行解；第第2阶段阶段: 从得到的基本可行解出发从得到的基本可行解出发, 用单纯形法求用单纯形法求(L)的最优解的最优解. 20axxL 而且所有的人工变量都是非基变量，则 是的基本可行解； 30jjaaaaxxxx 但 的某

12、个分量为基变量，则设法将从基变量中去掉。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 01 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 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 -1x6x2x5x1x2x521612320min12 0 030Txg得基可行解：12求解第求解第1

13、阶段问题：阶段问题：开始第开始第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/2min*2 3 2 0 07Txz 最优解为：111122112,1, 00, 0223122312212,1, 0243BNBc B Ncc B b 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

14、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-5min010 00Txg得基本可行解：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/5 -1/5 3/50 0 1 2/5 -1/5 -2/5 0 1 0 1/2 0 1/2

15、 0 0 -5 -2 1 21 0 -1 0 0 1x2x3x1x2x5x1100100 -50 1 0 1/2 0 1/2 第第2阶段阶段min*0101Txz 最优解为：1234456756767152110100411100106100100023020001106040000200112100001110104100100020023001400460008xxxxxxxxxxxxxxx11561234313217677011210000201110410010002020120140402400831100102222111010022221001000200001110000022

16、00 xxxxxxxxxxxxxxx22220T初 始 基可 行 解 ：（， ， ， ）Ex 陈宝林书陈宝林书 P118 2. (1)Homework陈宝林书陈宝林书 P118 1. (3) (5) 2. (7) (9) 6. 退化情形退化情形131213123123 max21.5 . 2 2 4 3 ,0zxxstxxxxxxxx xx例：x1 x2 x3 x4 x5 x6x4x5x6 -1 0 1 0 0 0 1 0 1 01 1 1 0 0 12432 0 1.5 0 0 0 x1x5x6 -1 0 1 0 00 2 1 -2 1 00 2 1 -1 0 12010 2 1.5 -2

17、0 0-401* *在单纯形法的计算过程中，确定出基变量时存在两在单纯形法的计算过程中，确定出基变量时存在两 个或两个或两个以上的最小比值，这时会出现退化解个以上的最小比值，这时会出现退化解。* *有时，退化会造成计算过程的循环，永远达不到最优解有时，退化会造成计算过程的循环，永远达不到最优解。4567145672456736j.631min206421 s.t 890411 123022 1 0 1,2,.,7E Bealezxxxxxxxxxxxxxxxxxj 由给出的循环例子：（迭代 次后又回到初始解）x1 x2 x3 x4 x5 x6 x71 1/4 -8 -1 90 1 0 1/2

18、-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 0 1 3/8 -15/40 0 1 0 0 1 0-1 -1 0 0 0 2 -18x4x5x300011/448x1 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 2

19、1/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 1/6 -4 -1/6 10 0 1 0 0 1 00 2 0 7/4 -44 -1/2 0 x1x7x300013/1621/3x1 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 -6x1

20、x2x30010发生循环的线性规划问题的特点：发生循环的线性规划问题的特点：1. 线性规划必然是退化的，即存在某个基变量取值为线性规划必然是退化的，即存在某个基变量取值为0。2.(0, 0,1, 0, 0, 0, 0)0T在迭代过程中，即使基变量 可行基矩阵 是不同的，但是它们对应着同一个极点，因而目标函数值始终为 。13.(0,0,0)( 3,0,0)( 1, 1,0)(2, 3,0)(1, 1,0)(0,2,0)(0,0,0)TTTTBTTTc B 在迭代过程中，可行基变量对应的单纯形乘子序列：。解决退化的方法有：解决退化的方法有：“摄动法摄动法”、“字典序法字典序法”、 Bland规规则

21、等则等1974年年Bland提出提出Bland法则：法则：(1)min |0,-2jjkkkj zczc则选取所对应的变量为进基变量。（ ）当按最小规则计算存在两个和两个以上的最小比值时，选取下标最小的基变量为换出变量。123423453653613614,x x xx x xx x xx x xx x xx x x3*, 0, 0,1, 0,1, 04Tx x1 x2 x3 x4 x5x2x3x5 1 1 0 -4 0 -2 0 1 -3 0 3 0 0 a 153d -3 0 0 0 讨论题讨论题在求解极小化在求解极小化LP问题中，得到如下单纯形表：（无人工变量）问题中，得到如下单纯形表：

22、（无人工变量）1、当前解为最优解时，各参数应满足的条件；、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；、原问题存在多个解时，各参数应满足的条件；4、当、当 x4 作为进基变量取代作为进基变量取代 x5 时，目标值的增量为多少？时，目标值的增量为多少？修正单纯形法修正单纯形法 基本思想：基本思想：他运算。法的其的逆，进而完成单纯形来获得新基，通过修改旧基的逆给定初始基本可行解后11BB在整个计算过程中，始终保存现行基的逆。在整个计算过程中，始终保存现行基的逆。计算步骤计算步骤2.max03jjjjkkjjkkzcwPc