第 1.3 节 单纯形法.ppt

第1章 线性规划与单纯形法 第3节 单纯形法 1. 确定初始基可行解 先将线性规划问题化为标准型，再从中寻找基向量，必要时可采取增加人工变量的办法构成初始基向量。 2. 最优性的判断 一般在某步迭代中总可以将基变量写成如下形式(假设当前基变量为 x1, x2, …, xm)： 代入目标函数可得: 最优解的判定：若 ?j ? 0, j = 1, 2, …, n, 则当前基可行解 X? = ( b?1, b?2, …, b?m, 0, …, 0)T 为最优解； 无穷最优解判定：若 ?j ? 0, j = 1, 2, …, n, 且有某一非基变量对应的检验数 ?m+k = 0, 则线性规划问题有无穷多最优解； 无界解判定：若有某个检验数 ?m+k 0, 且非基变量 xm+k 对应的系数列向量 Pm+k ? 0，则线性规划问题有无界解。 3. 基变换(旋转运算) (1)确定换入变量：xk，可选择正检验数中最大的检验数所对应的非基变量作为换入变量； (2)确定换出变量，设某次迭代中以 xi, i = 1, 2, …, m 为基变量，则 计算 根据以上计算，选择对应的 xl 为换出变量； (3)“交换” xk 与 xl，计算新的基可行解 X?，方法是使用行初等变换将 xk 对应的列向量化成 xl 原对应的单位列向量，这样就实现的基变换； *