《运筹学03-单纯形法》由会员分享，可在线阅读，更多相关《运筹学03-单纯形法（95页珍藏版）》请在金锄头文库上搜索。
1、第三章 单纯形法,3.1 线性规划问题的标准形式 3.2 线性规划问题的解 3.3 单纯形法 3.4 求初始基的人工变量法,3.1 线性规划问题的标准形式,目标函数,约束条件,(1) 线性规划模型一般形式,价值系数,决策变量,技术系数,右端常数,(2) 线性规划模型标准形式,简记形式,(3) 线性规划模型其它形式,矩阵形式,价值向量,决策向量,系数矩阵,右端向量,价值向量,决策向量,右端向量,向量形式,列向量,对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,(4) 一般型向标准型的转化,目标函数 目标函数为极小化 约束条件 分两种情况：大于和小于 决策变量 可能
2、存在小于零的情况,1.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问题与下面的极大化问题有相同的最优解，即Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Min f - Max z,2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ +ain xn bi可以引进一个新的变量s ，使它等于约束右边与左边之差s = bi (ai1 x1 + ai2 x2 + + ain xn )显然，s 也具有非负约束，即s
3、0，这时新的约束条件成为ai1 x1+ai2 x2+ +ain xn+s = bi变量 s 称为松弛变量,Max Z=40X1+ 50X2X1 +2X2 30 s.t 3X1 +2X2 60 引入松弛变量X3、 X4、X5 2X2 24 X1 , X2 0Max Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 602X2 + X5 24 X1 , X5 0,当约束条件为ai1 x1+ai2 x2+ +ain xn bi 时，类似地令s = (ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负
4、约束，即s0，这时新的约束条件成为ai1 x1+ai2 x2+ +ain xn-s = bi 变量s称为剩余变量,Max Z=2X1+ 5X2+6X3 +8X44X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0 引入剩余变量：X5、X6、X7 Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 142X2+ X3+3X4 - X7 8 X1 , , X7 0,3. 决策变量 如果某个变量的约束条件为,或者,可令,或者,
5、代入原问题,如果某个变量为自由变量，则可令,且,X1+X2 5 s.t -6 X1 10X20令 X1 = X1 +6 -6+6 X1+6 10+60 X1 16X1 +X2 11 s.t X1 16X1 , X2 0,3X1+2X2 8s.t X1 -4X2 14X20, X1 无限制令X1= X1- X1 3 X1 -3 X1 “ +2X2 8s.t X1 - X1 “ - 4X2 14X1 , X1“ ,X2 0,例：将线性规划模型 Min Z = -X1+2X2 -3X3X1+X2 +X3 7s.t X1 -X2 +X3 2X1，X20，X3无限制化为标准型,解： 令X3 =X4 -
6、X5, 加松弛变量X6,加剩余变量X7, 令Z= -Z,Max Z= X1 -2X2 +3X4 -3X5,s.t,3.2 线性规划问题的解,(1) 解的基本概念,定义 在线性规划问题中，约束方程组(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个基阵或基。,基阵,非基阵,基 向 量,非 基 向 量,基变量,非基变量,令,则,定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。,定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。,定义
7、在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。,基本解中最多有m个非零分量。,基本解的数目不超过 个。,非可行解,解的集合：,可行解,基本解,最优解,基本可行解,解空间,例 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,解: (1)首先将原问题转化为标准型引入松弛变量x3和x4,(2) 求基本解 由上式得,可能的基阵,由于所有|B| 0,所以有6个基阵和6个基本解。,对于基阵,令,则,对于基阵,令,则,为基
8、本可行解，B13为可行基,为基本可行解，B12为可行基,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,为基本可行解，B24为可行基,为基本可行解，B34为可行基,0,A,B,C,D,E,1 基本解为边界约束方程的交点； 2 基对应于可行解可行域极点； 3 相邻基本解的脚标有一个相同。,例2 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,解: (1)首先将原问题转化为标准型引入松弛变量x3和x4,(2) 求基本解 由上式得,可能的基阵,由于所有|B| 0，所以有6个基阵和6个基本解。,对于基阵,令,则,对于基阵,令,则,为基本可行解，B12为可行基,为
9、基本可行解，B13为可行基,为退化解,对于基阵,令,则,对于基阵,令,则,为基本可行解，B23为可行基,为退化解,对于基阵,令,则,对于基阵,令,则,为基本可行解，B24为可行基,为基本可行解，B34为可行基,为退化解,0,A,B,C,(2) 解的基本性质,判别可行解为基可行解的准则,定理1 线性规划问题的可行解是基可行解的充要条件是它的非零变量所对应的列向量线性无关.,线性规划问题的基本定理:定理2和定理3,定理2 线性规划问题有可行解,则它必有基可行解.,定理3 若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.,定理2 线性规划问题有可行解,则它必有基可行解.,证:设 为线性规
10、划问题的一个可行解.若 ,则它是一个基可行解,定理成立;若 ,则令 的前k个分量为非零分量：,若上述分量所对应的列向量 线性无关,则它是一个基可行解,定理成立; 若 线性相关，从 出发， 必可找到线性规划问题的一个基可行解。,由于 线性相关，则存在一组不全为零的数 ， 使得,假定,令,若,令,(若,令,),(*),由(*)可知,即,与 相比， 的非零分量减少1个，若对应的k-1个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。,几点结论,若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点); 线性规划问题的每一个基
11、可行解都对应于可行域上的一个顶点(极点); 若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到; 线性规划问题的基可行解(极点)的个数是有限的,不会超过 个.,上述结论说明: 线性规划的最优解可通过有限次运算在基可行解中获得.,3.3 单纯形法,例1,(1)单纯形法的引入,解：(1)、确定初始可行解,B = ( P3 P4 P5 ) = I,令X1 = X2 =0,X(1) =(0, 0, 30, 60, 24)T Z(1) =0,(2)、判定解是否最优,Z=0+40X1+50X2 当 X1 从 0 或 X2 从 0 Z 从 0, X(1) 不是最优解,(3)、由一个基可行解另一个基
12、可行解。, 50 40 选 X2 从 0，X1 =0,X2 = min ( 30/2 , 60/2 , 24/2 ) =12 X2 ：进基变量， X5 ：出基变量。,B2=( P3 P4 P2 ), 1/2 ， 代入 式， ，,令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )TZ(2) = 600,(2) 判断, 400 X(2)不是最优解。,(3) 选X1从0， X5 =0,X1=min( 6/1 , 36/3 , 1 ) =6 X1进基， X3出基。,B3 =(P1 P4 P2 ),令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)T Z(
13、3) =840,(2)“ 150 X(3)不是,(3)“ 选X5从0， X3 =0,X5=min( 18/2 , 12/1/2 ) =9 X5进基， X4出基。,B4=(P1 P5 P2 ),令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975,0,(0,0),X2,X1,X(4),X(1),X(2),X(3),Z=40X1+50X2,单纯形法小结：单纯形法是这样一种迭代算法如下图当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。,X1,Z1,保持单调增,保持可行性,保持可行性,保持可行性,保持可行性,
14、保持单调增,保持单调增,保持单调增,X2,X3,.,Xk,Z2,Z3,.,Zk,当Zk 中非基变量的系数的系数全为负值时，这时的基本可行解Xk 即是线性规划问题的最优解，迭代结束。,(2) 线性规划的典则形式,标准型,上式称为线性规划问题对应于基B的典则形式，简称典式。 约束方程组的系数矩阵中含有一个单位矩阵，并以其为基； 目标函数中不含基变量，只有非基变量。,检 验 数,(3) 最优性判别定理,在线性规划问题的典式中，设X(0)=(x1,x2,xm,0,0) 为对应于基B 的一个基可行解，若有j 0 ( j = m+1 , m+2 , , n ) 则X(0)是线性规划问题的最优解，基B为最优基。,证：设X为线性规划问题的一个可行解，必有X 0 ，当 j 0， 则 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX故X(0)为线性规划问题的最优解。,
