13 单纯形法原理.pptVIP

§1.3 单纯形法原理 一、基本概念 二、凸集和顶点 三、几个基本定理 总结几个基本定理 定理1 若线性规划问题存在可行解，则问题的可行域是凸集。 引理 线性规划问题的可行解X＝(x1,x2,……xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。 定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点。 定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解。 问题： 4 基变换 换出变量的确定 ？ 最终选择哪一个基变量出基？ 当然X2的增加量越多越好，但其增加量受到约束条件的约束。 我们需要考虑将哪个基变量换出，可以使得X2的增加量最大并同时满足约束条件。 4 基变换 换出变量的确定 X1仍为非基变量，令X1 =0 X3 =100- X1- X2 X4 =190- 3X1- 2X2 X5 =240- 2X1- 3X2 X3 =100- X2 ≥0 X4 =190- 2X2 ≥0 X5 =240- 3X2 ≥0 三个约束方程均必须满足 4 基变换 换出变量的确定 X3 =100- X2 ≥0 X4 =190- 2X2 ≥0 X5 =240- 3X2 ≥0 选择X2=min(100/1,190/2,240/3)=80方能同时满足以上三个约束 这时X5=0决定了应该用X2去换X5 4 基变换 换出变量的确定 xi = bi ’ - aij ’ xj (i=1,2, …,m) Xk被选为入基变量 xi = bi ’ - aik ’ xk (i=1,2, …,m) 4 基变换 换出变量的确定 xi = bi ’ - aik ’ xk (i=1,2, …,m) xi = bi ’ - aik ’ xk ≥0 xi是什么变量？ X3 =100- X2 ≥0 X4 =190- 2X2 ≥0 X5 =240- 3X2 ≥0 aik ’ ≤ 0，显然对xk无增加限制 aik ’ 0，显然要求xk ≤ bi ’ / aik ’ 4 基变换 换出变量的确定 aik ’ 0，显然要求xk ≤ bi ’ / aik ’ min(bi ’ / aik ’ | aik ’ 0) = bl ’ / alk ’ i 确定xl为换出变量，可使xk获得最大的增加量的同时，满足上述要求。 最小比值判断法 5迭代 迭代的基本思想 确定换入变量和换出变量后，要将原非基变量所对应的列向量变成单位向量（使用初等行变换）。 5迭代 迭代的步骤 入基变量xk和出基变量xl 对应的列向量 Pk=(a1k , a2k , … , amk)T Pl =(0 , … , 1 , … , 0)T 第l 个分量 变成单位向量 5迭代 迭代的步骤 x1 … xl … xm xm+1 … … xk … … xn b 1 a1,m+1 … …a1k … …a1n b1 1 al ,m+1 … …al k … …al n bl … … … … … … … … … … … … … … … … … … … … … … … … … … 1 am,m+1 … …amk … …amn bm 变成单位向量 主元 变成1 其余变成0 5迭代 举 例 x1 x2 x3 x4 x5 b 1 1 1 0 0 100 3 2 0 1 0 190 2 3 0 0 1 240 入基变量x2 出基变量x5 主元? 主元 5迭代 迭代的步骤 x1 x2 x3 x4 x5 b 1 1 1 0 0 100 3 2 0 1 0 190 2 3 0 0 1 240 x1 x2 x3 x4 x5 b 1 1 1 0 0 100 3 2 0 1 0 190 2/3 1 0 0 1/3 80 5迭代 迭代的步骤 x1 x2 x3 x4 x5 b 1