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

《第1章+线性规划与单纯形法-第4节.pdf》由会员分享，可在线阅读，更多相关《第1章+线性规划与单纯形法-第4节.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1章 线性规划与单纯形法章 线性规划与单纯形法第第4节单纯形法的计算步骤节单纯形法的计算步骤4.1 单纯形表 为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似 将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组线性规划的方程组0111111221122111111=+=+=+=+nnmmmmmnmnmmmmnnmmnnmmxcxcxcxczbxaxaxbxaxaxbxaxax?为了便于迭代运算，可将上述方程组写成增广矩阵形式+01000001000010211211,21,211,1121mnmmmnmmnmnmnmmbbbcccccaaaaaabx

2、xxxxz?若将z看作不参与基变换的基变量，它与x1,x2,xm的系数构成一个基这时可采用行初等变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵:=+miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21,211,11210001000001000010?单纯形表表1-2=+=+=+=+miininmimiimmiiimmnmmmmmnmnmnmmBBinmmjaccaccbczaabxcaabxcaabxcxxxxbXCccccc111,111,221,2222111,1111111100100001?=m

3、iijijnjacc1,2,1,?XB列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是表1-2的说明4.2 计算步骤 表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。计算步骤：(1)按数学模型确定初始可行基和初始基可行解，建立初始单纯形表(2)计算各非基变量xj的检验数，检查检验数，若所有检验数则已得到最优解，可停止计算。否则转入下一步。=m

4、iijijjacc1 njj?,2,1,0=计算步骤-确定换入/出变量(3)在j0,j=m+1,n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界，停止计算。否则，转入下一步。(4)根据max(j0)=k，确定xk为换入变量，按规则计算lklikikiabaab=0min xl为换出变量XB的第l元(5)以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量将XB列中的xl换为xk，得到新的单纯形表(6)重复(2)(5)，直到终止行第变换laaaaPmklkkkk=010021?计算步骤-旋转运算用例1的标准型来说明计算步骤(1)取松弛变量x3,x4,x5为基变

5、量，它对应的单位 矩 阵 为 基。这 就 得 到 初 始 基 可 行 解X(0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，见表1-35432100032maxxxxxxz+=5,2,10124164825241321?=+=+=+jxxxxxxxxjcj23000CBXBbx 1x 2x 3x 4x 50 x 38121008/2=40 x 41640010-0 x 5120400112/4=3-z 023000z中的各价值系数基变量1.计算检验数，由它确定为换入变量2.计算，确定换出变量3.确定主元素表 1-3（1）计算非基变量的检验数 各非基变量的检验数为 1=c

6、1-z1=2-(01+04+00)=2 2=c2-z2=3-(02+00+04)=3 填入表1-3的底行对应非基变量处。（2）检验、（3）确定主元素(2)因检验数都大于零，且 P1，P2有正分量存在，转入下一步；(3)max(1,2)=max(2,3)=3，对应的变量 x2为换入变量，计算 341201628022=,minaabminiiii 它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处4称为主元素或枢元素(pivot element)（4）旋转运算以4为主元素进行初等行变换，使P2变换为(0,0,1)T,在XB列中将x2替换x5得到新表1-4.cj23000CBXBbx1x

7、2x3x4x50 x321010-1/220 x4164001043x2301001/4-z -92000-3/4换入变量x1x3换出主元素主元素(5)重复(2)(4)的计算步骤cj23000CBXBbx1x2x3x4x52x121010-1/2-0 x4800-41243x2301001/412-z -1300-201/4换入变量换出变量(6)最优解所有检验数都已为负或零这表示目标函数值已不可能再增大，得到最优解cj23000CBXBbx1x2x3X4x52x141011/400 x5400-21/213x22011/2-1/80-z -1400-3/2-1/80最优解X*=X(3)=(4,2,0,0,4)T目标函数的最大值z*=14第4节 结束