运筹学 (第三版)
《运筹学》教材编写组编
清华大学出版社
第1章线性规划与单纯形法
第4节单纯型法的计算步骤
钱颂迪制作
第1章线性规划与单纯形法
第4节单纯型法的计算步骤
第4节单纯型法的计算步骤
根据以上讨论的结果,将求解线性规划问题的单纯形法的计算步骤归纳如下
如利用单纯型表,求解线性规划问题。
单纯型表
为了便于理解计算关系,现设计一种计算表,称为单纯形表,其功能与增广矩阵相似,下面来建立这种计算表。
将(1-22)式与目标函数组成n+1个变量,m+1个方程的方程组。
线性规划的方程组
为了便于迭代运算,可将上述方程组写成增广矩阵形式
若将z看作不参与基变换的基变量,它与x1,x2,…,xm的系数构成一个基,这时可采用行初等变换将c1,c2,…,cm变换为零,使其对应的系数矩阵为单位矩阵。得到
可根据上述增广矩阵设计计算表, 表1-2。
表1-2的说明
XB列中填入基变量,这里是x1,x2,…,xm;
CB列中填入基变量的价值系数,这里是c1,c2,…,cm;它们是与基变量相对应的;
b列中填入约束方程组右端的常数;
cj行中填入基变量的价值系数c1,c2,…,cn;
θi列的数字是在确定换入变量后,按θ规则计算后填入;
最后一行称为检验数行,对应各非基变量xj的检验数是
计算步骤
表1-2称为初始单纯形表,每迭代一步构造一个新单纯形表。
计算步骤:
(1) 按数学模型确定初始可行基和初始基可行解,建立初始单纯形表。
(2) 计算各非基变量xj的检验数,
检查检验数,若所有检验数
则已得到最优解,可停止计算。否则转入下一步。
第1章 线性规划与单纯形法-第4节 来自淘豆网m.daumloan.com转载请标明出处.
