《运筹学线性规划单纯形法》由会员分享，可在线阅读，更多相关《运筹学线性规划单纯形法（59页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学第五讲第五讲元培学院元培学院0505级级7/21/20242解LP问题单纯形法vLP问题的最优解问题的最优解唯一解唯一解无穷多解无穷多解有解有解无解无解无可行解无可行解无有限最优解无有限最优解7/21/2024是若干个半平面之交是一个凸集。是若干个半平面之交是一个凸集。LP的可行解集：的可行解集： 7/21/2024D是是n维欧氏空间维欧氏空间Rn的一个集合的一个集合: 对对任意任意两点：两点：X(1), X(2)D, D, 任任,若满足若满足 0 , 1, +=1则则总有总有 X= X(1)+X(2) DD；或；或任任一个一个若满足若满足 0 1则总有则总有 X= X(1)+(1
2、- ) X(2) DD。XX是连结是连结X(1), X(2)的线段上任意一点的线段上任意一点 则称则称D D是一个凸集。是一个凸集。定义定义3：凸集：凸集7/21/2024定理：定理：n n维欧氏空间维欧氏空间R Rn n的任两个凸集合的任两个凸集合A A、B B之之交交也是一个凸也是一个凸集合集合 : : 证明：对任意证明：对任意X(1), X(2)AB,AB,则：则： X(1), X(2)A,A,X(1), X(2)B, B, 任任,若满足若满足 0 , 1, +=1则总有则总有 X= X(1)+X(2)AAAA凸凸,同理同理X= X(1)+X(2)B,B,即即XAB,XAB,ABAB是一
3、个凸集。是一个凸集。凸集的性质：凸集的性质：凸集之并必凸吗？凸集之并必凸吗？7/21/2024LPLP问题的标准型问题的标准型LP问题标准化：问题标准化：矩阵形式矩阵形式目标函数是求最大目标函数是求最大：Max Z=CX可能有的不等式约束可能有的不等式约束通过引入松弛变量或通过引入松弛变量或剩余变量剩余变量全化为等式约束全化为等式约束：AX =b决策变量全有非负约束：决策变量全有非负约束：X 0 0 m为约束个数为约束个数,n为决策变量个数为决策变量个数,A Amn满秩满秩。 X = (x1 , , xn)T ，每个分量有非负约束每个分量有非负约束。7/21/2024标准型标准型LPLP问题的
4、解问题的解标准化了的标准化了的LP问题：问题：Max Z=CX AX =b（全为等式约束全为等式约束）s.t. X 0 0 （决策变量全有非负约束决策变量全有非负约束）A Amn 满秩满秩,m为约束个数为约束个数,n为决策变量个数。为决策变量个数。 X = (x1 , , xn)T ，每个分量有非负约束每个分量有非负约束。注：通常说：注：通常说：m n m 0,它它,则则z ,它可以大到多少它可以大到多少?50x1与与x3换位，做初等变换：换位，做初等变换：1 0 1 0 -1 502 0 0 1 -1 1500 1 0 0 1 250x1进进基基x3出出基。基。1 0 1 0 -1 502
5、0 0 1 -1 1500 1 0 0 1 250 1 0 1 0 -1 50 0 0 -2 1 1 50 0 1 0 0 1 250目标函数目标函数 z = 50x1+100x2 =27500-50x3-50x57/21/2024此线性规划问题图解法此线性规划问题图解法2x1+x2=400最优解最优解(50,250)目标函数目标函数 f = 50x1+100x2 =27500x1+x2=300x2=250可行解区域可行解区域 x1+ x23002x1+x2400 x2250 x10 , x20max f=50x1+100x27/21/2024LPLP问题的代数解法问题的代数解法实际上这是在可
6、行域的顶点中搜索最优解：实际上这是在可行域的顶点中搜索最优解：从一个顶点开始，是否好？不好如何寻找出更从一个顶点开始，是否好？不好如何寻找出更好的一个？好的一个？1.第一个可行域的顶点第一个可行域的顶点初始基可行解初始基可行解；2.一个基可行解是否是最优的判断一个基可行解是否是最优的判断判优判优；3.不是最优解时如何寻找出更好的一个不是最优解时如何寻找出更好的一个迭代迭代。Dantzig在在20世纪世纪40年代，把上述想法归纳成年代，把上述想法归纳成“单纯形法单纯形法(Simplex Method)”。它被公认为。它被公认为20世纪十大算法之一。可操作性强，可以方便世纪十大算法之一。可操作性强
7、，可以方便地编制相应的计算机程序。是地编制相应的计算机程序。是本课程的重点本课程的重点。7/21/2024解解LPLP的单纯形法的单纯形法此法的证明不作要求。此法的证明不作要求。先标准化先标准化,列表操作列表操作,借助借助Excel 实现。实现。1.第一个可行域的顶点第一个可行域的顶点初始基可行解初始基可行解，列列初始表初始表；基、基变量、非基变量基、基变量、非基变量2.一个基可行解是否是最优的判断一个基可行解是否是最优的判断判优判优，求非基变量的，求非基变量的检验数，是否有正的；，是否有正的；3.不是最优解时如何寻找出更好的一个不是最优解时如何寻找出更好的一个迭迭代代，确定，确定进基进基变量
8、，求比值，确定变量，求比值，确定出基出基变量，然后用行初等变换迭代。变量，然后用行初等变换迭代。ExcelExcel7/21/2024、分离系数列成表；、分离系数列成表；、用类似矩阵初等变换的操作；、用类似矩阵初等变换的操作；、找出、找出第一个可行基第一个可行基；、判断判断可行基可行基是否是否是是最优最优基？是基？是则结束。则结束。、还不、还不是最优基，是最优基，决定进基变量、决定进基变量、出基变量出基变量 迭代迭代 ；、找到好一点的可行基，回、找到好一点的可行基，回。 单纯形法算法单纯形法算法7/21/2024、定初始基，初始基本可行解、定初始基，初始基本可行解、对应于非基变量检验数、对应于
9、非基变量检验数 j全全 0？若是，若是，停，得到最优解；若否，转停，得到最优解；若否，转(3)。、若有若有 k 0 0，Pk全全 0，停，停， 没有有限最优解；没有有限最优解； 否则转否则转(4)、求解资源有约束求求解资源有约束求Max的的LP问题问题单纯形法基本步骤单纯形法基本步骤= = min ai m+k 0 =0 =biAi m+kbrar m+k定定x xr为换出变量，为换出变量，a ar m+k为主元。为主元。由最小由最小比值法求：比值法求：maxmax j = m+kXm+k 换入变量换入变量 j007/21/2024例例: :Max Z = Max Z = x1 + 2x2x1
10、 4x2 3x1+2x2 8 x1 , x2 00 x1-x3 = = 4x2 -x4 = = 3x1+2x2 -x5= = 8 x1 , x5 00几点说明：几点说明：(P(P3 3P P4 4P P5 5) )是基，但不是可行基是基，但不是可行基。第一个可行基如何找？。第一个可行基如何找？7/21/20241 1、LPLP问题问题 约束的常数项约束的常数项b0,b0,全是全是“”“”的约束的约束 标准标准化；化；2 2、列出初始单纯形表；、列出初始单纯形表；3 3、查检验数看是否有正的，、查检验数看是否有正的，若有迭代，然后再查；若有迭代，然后再查；4 4、检验数非正得最优解。、检验数非正
11、得最优解。单单纯纯形形法法7/21/2024单纯形法单纯形法有基，但不有基，但不是可行基是可行基, ,找第一个可找第一个可行基？最优行基？最优判断判断, ,迭代迭代. .无可行基、无最优基无可行基、无最优基. .大大M M法，两阶段法法，两阶段法StartStartStartStart有可行基？有可行基？Y YN N找进基、出找进基、出基变量迭代基变量迭代求出更好的求出更好的可行基可行基最优？最优？Y YN N输出最优解输出最优解EndEndEndEnd7/21/20241 1、拟进基的变量所在列的系、拟进基的变量所在列的系数非正，无有限最优解；数非正，无有限最优解；2 2、找不到初始基可行解则无、找不到初始基可行解则无可行解；可行解；3 3、最优基可行解中有检验数、最优基可行解中有检验数为为0 0的非基变量。的非基变量。单纯形法几种单纯形法几种可能情况可能情况7/21/2024P.97P.97第五章习题第五章习题4 4, , 5 5 (1) (1)预习：运输问题预习：运输问题作作 业业7/21/2024
