最优化方法-之单纯形法

《最优化方法-之单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、迭代换基：找一个非基变量作为换入变量，同时确定一个基变量为换出变量。依据原则：1)新的基可行解能使目标值减少；2)新的基仍然是可行基。确定换入变量：选取x1为换入变量确定换出变量:迭代（求新的基本可行解）主元素判断代入目标函数得确定进基变量和出基变量换基迭代判断代入目标函数：最优解：x1x212341234l2l1OAB(1,1.5)C可行域（OABC）最优解：X=（11.5)T设(L)有一个初始基初始基本可行解为:考虑xk的取值单纯性法计算步骤初始基为B,初始基本可行解为x(0)=(B-1b0)T是否yk=B-1Pk≤0是x(0)为最优解无界是

3、例1例2表格形式的单纯形方法单纯形表fxBxN右端xBf0ImB-1NB-1b10cBB-1N-cNcBB-1b可省略检验数(判别数)目标函数取值基变量取值用单纯形表求解问题：xBxN右端xBImB-1NB-1b0cBB-1N-cNcBB-1b主元消去法检验数基函数值等的变化----矩阵运算xBxN右端xBImB-1NB-1b0cBB-1N-cNcBB-1bx1x4x51-210001-31001-10101-2002120x1x2x3x4x5x1x2x3x4x5x1x4x51-210001-31001-10101-2002120x1x2x3

4、100-1/25/2010-1/23/2001-1/21/2000-1/2-1/213/25/21/2-3/2x1x2x510-52001-310002-11001-10411-1１２x1x2x3x4x5x4x51131014-101-2-1100640x3x10-111/3-1/31301/32/30601/35/32/314/326/3x4x10-331-114-10107-102248１３单纯形法的进一步讨论无界解Oz→-∞结论：若zj-cj>0,对应的系数列向量≤0，则该LP存在无界解。x1x2x3x4-3101-20111100-312

5、64x3x2-2-31-110-3101x3x424230001无限多个解x1x2l2l1OABCx1x2x3x42710720141400x3x421210017/45-2/4510-2/457/4500-20x2x17/37/3-422/711/7045/70-2/7100-20x2x4315-42745/7结论：若某个非基变量的检验数为零，则该LP存在多个最优解。课外练习第六讲单纯形法之完善两阶段法xa的每个分量称为人工变量.两阶段法第1阶段:用单纯形法把人工变量变为非基变量，求出原问题的一个基可行解。方法：求解下列模型基变量第2阶段:从得

6、到的基本可行解出发,用单纯形法求(L)的最优解.x1x2x3x4x5x6x711-10010-110-100102-1-10001200100x6x7x53184300210-2-110-100120-1101-120-1100-210-1/21/201/2-1/201-1/2-1/201/21/2003/21/21-1/3-1/2000-200-1x6x2x5x1x2x52161232012求解第1阶段问题：开始第2阶段：x1x2x3x4x5x1x2x510-1/21/2001-1/2-1/20003/21/21003/2-1/20123-4x

7、1x2x31002/31/3010-1/31/30011/32/3000-1-1232-73/210-1001-20-3-210-1/211/21/200-10-4-200x2x5x610000101/201/200-5-21210-1001x2x5x1100x1x2x3x4x5x6-121100-44-1010-34-200010-1001x4x5x6240421-5x1x2x3x41002/50012/5000-1/10x2x3x1100-10101/2x1x2x3x4x5x61002/5-1/53/50012/5-1/5-2/50101/2

8、01/200-5-21210-1001x2x3x1x2x5x1100100-50101/201/2第2阶段112退化情形—(自学)x1x