第1章 线性规划与单纯形法-第4节

运筹学（ 第三版） 运筹学 教材编写组 编清华大学出版社第 1章 线性规划与单纯形法第 4节 单纯型法的计算步骤钱颂迪 制作第 1章 线性规划与单纯形法第 4节 单纯型法的计算步骤第 4节 单纯型法的计算步骤 根据以上讨论的结果，将求解线性规划问题的单纯形法的计算步骤归纳如下 如利用单纯型表，求解线性规划问题。 4.1 单纯型表 为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。 将 (1-22)式与目标函数组成 n+1个变量，m+1个方程的方程组。 线性规划的方程组为了便于迭代运算，可将上述方程组写成增广矩阵形式若将 z看作不参与基变换的基变量，它与x1,x2, xm的系数构成一个基，这时可采用行初等变换将 c1,c2,c m变换为零，使其对应的系数矩阵为单位矩阵。得到可根据上述增广矩阵设计计算表，表 1-2。 表 1-2的说明 XB列中填入基变量，这里是 x1， x2, ， xm； CB列中填入基变量的价值系数，这里是c1,c2,c m； 它们是与基变量相对应的； b列中填入约束方程组右端的常数； cj行中填入基变量的价值系数 c1,c2, cn； i列的数字是在确定换入变量后，按 规则计算后填入； 最后一行称为检验数行，对应各非基变量 xj的检验数是4.2 计算步骤 表 1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。 计算步骤： (1) 按数学模型确定 初始可行基 和 初始基可行解，建立初始 单纯 形表。 (2) 计算 各非基 变 量 xj的 检验 数 ，检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。 (3) 在 j 0,j=m+1,n 中，若有某个 k对应 xk的系数列向量 Pk0 ， 则此问题是无界，停止计算。 否则，转入下一步。 (4) 根据 max( j 0)= k， 确定 xk为换入变量，按 规则计算 (5) 以 alk为主元素进行迭代 (即用高斯消去法或称为旋转运算 )，把 xk所对应的列向量 将 XB列中的 xl换为 xk， 得到新的 单纯 形表。重复(2) (5)，直到 终 止。现用例 1的标准型来说明上述计算步骤。 (1) 取松弛变量 x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解 X(0)=(0,0,8,16,12)T 将有关数字填入表中，得到初始单纯形表，见表 1-3。表中左上角的 cj是表示目标函数中各变量的价值系数。在 CB列填入初始基变量的价值系数，它们都为零。 目标函数中各变量的价值系数 。1.计算检验数，由它确定为换人变量2.计算 ， 由它确定为换出变量3.确定主元素表 1-3基变量计算非基变量的检验数 各非基变量的检验数为 1=c1-z1=2-(01+04+00)=2 2=c2-z2=3-(02+00+04)=3 填入表 1-3的底行对应非基变量处。进行（ 2），（ 3）它所在行对应的 x5为换出变量， x2所在列和 x5所在行的交叉处4称为主元素或枢元素 (pivot element)(4) 以 4为主元素进行旋转运算或迭代运算 ， 即初等行变换，使 P2变换为（ 0,0,1） T,在 XB 列中将x2 替换 x5 ,于是得到新表 1-4. 换人变量换出变量主元素(5) 检查表 1-4的所有 cj-zj,这时有 c1-z1=2； 说明 x1应为换入变量。重复 (2) (4)的计算步骤，得表 1-5。 还存在检验数 0，继续进行。换人变量换 出变量主元素(6) 表 1-6最后一行的所