运筹学单纯形法过程稿.PPTVIP

第三章 单纯形法 3.1 线性规划问题的标准形式 3.2 线性规划问题的基本解 3.3 单纯形法 3.4 求初始基的人工变量法 3.1 线性规划问题的标准形式 3.2 线性规划问题的基本解 3.3 单纯形法 3.4 求初始基的人工变量法 例1、Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 s.t X1+2X2 +X3 = 30 3X1+2X2 +X4 =60 2X2 +X5 = 24 X1 – X5 ?0 s.t C 40 50 0 0 0 θ CB XB B X1 X2 X3 X4 X5 0 X3 30 1 2 1 0 0 15 0 X4 60 3 2 0 1 0 30 0 X5 24 0 2 0 0 1 12 Z 0 40 50 0 0 0 ? CB XB B X1 X2 X3 X4 X5 θ 0 X3 30 1 2 1 0 0 ? 0 X4 60 3 2 0 1 0 ? 50 X2 24 0 2 0 0 1 ? Z ? ? ? ? ? ? ? CB XB B X1 X2 X3 X4 X5 θ 0 X3 6 1 0 1 0 -1 6 0 X4 36 3 0 0 1 -1 12 50 X2 12 0 1 0 0 1/2 ? Z 600 40 0 0 0 -25 ? C 40 50 0 0 0 θ CB XB B X1 X2 X3 X4 X5 40 X1 6 1 0 1 0 -1 0 X4 18 0 0 -3 1 2 9 50 X2 12 0 1 0 0 1/2 24 Z 840 0 0 -40 0 15 ? CB XB B X1 X2 X3 X4 X5 θ 40 X1 15 1 0 1/2 -1/2 0 ? 0 X5 9 0 0 3/2 -1/2 0 ? 50 X2 15/2 975 0 1 -3/4 1/4 1 ? Z ? ?0 ?0 -35/2 -15/2 ?0 ? 例1、Max Z=40X1+ 80X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 s.t X1+2X2 +X3 = 30 3X1+2X2 +X4 =60 2X2 +X5 = 24 X1 – X5 ?0 s.t 可能的基阵 由于所有|B|≠ 0，所以有6个基阵和6个基本解。 对于基阵 令 则 对于基阵 令 则 为基本可行解，B12为可行基 为基本可行解，B13为可行基,为退化解 对于基阵 令 则 对于基阵 令 则 为基本可行解，B23为可行基,为退化解 对于基阵 令 则 对于基阵 令 则 为基本可行解，B24为可行基 为基本可行解，B34为可行基,为退化解 0 A B C (2) 解的基本性质 判别可行解为基可行解的准则 定理1 线性规划问题的可行解是基可行解得充要条件是它的非零向量所对应的列向量线性无关. 线性规划问题的基本定理:定理2和定理3 定理2 线性规划问题有可行解,则它必有基可行解. 定理3 若线性规划问题有最优解,则一定存在一个基可行解是它的最优解. 定理2 线性规划问题有可行解,则它必有基可行解. 证:设 为线性规划问题的一个可行解. 若 ,则它是一个基可行解,定理成立; 若 ,则令 的前k个分量为非零分量： 若上述分量所对应的列向量 线性无关,则它是一个基可行解,定理成立; 若 线性相关，从 出发， 必可找到线性规划问题的一个基可行解。 由于 线性相关，则存在一组不全为零的数 ， 使得 假定 令 若 令 (若 令 ) (*) 由(*)可知 即 与 相比， 的非零分量减少1个，若对应的k-1个列向量线性无关，则即为基可行解；否则继