运筹学课件1-4单纯形法计算步骤

《运筹学课件1-4单纯形法计算步骤》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§1.4单纯形法计算步骤1.将非标准型线性规划化为标准型2.确定初始基可行解：一般设松弛变量为初时基可行解3.判断：若所有的非基变量的检验数σj≤0，则此解为LP的最优解，若存在某一非基变量的检验数σj>0，则问题还没有达到最优解，需进行改进4.迭代：选换入变量max{cj-zj/cj-zj>0}假设xk为换入变量；选换出变量θ＝min{bi/aik，aik＞0}，假设选取xl为换出变量；然后迭代，使得alk＝1，其余aik为0单纯形表求解线性规划问题maxZ=6x1+5x2x1+3x2≤902x1+x2≤75

2、2x1+2x2≤80x1,x2≥0maxZ=6x1+5x2x1+3x2+x3＝902x1+x2+x4＝752x1+2x2+x5＝80xi≥0,i=1,...,5例cj65000CBXBbx1x2x3x4x5θ0x390131000x475210100x58022001cj65000CBXBbx1x2x3x4x5θ0x390131000x475210100x58022001cj-zj65000x1为换入变量即新的基变量。cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x47521010

3、75/20x5802200180/2cj-zj65000所以把x4换出基变量，作为非基变量，。cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650006x175/211/201/20cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/20cj65000CBXB

4、bx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/200x55010-11cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/200x55010-11cj-zj020-30cj65000CBXBbx1x2x3x4

5、x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-30所以把x5换出为非基变量，x2为换入变量即新的基变量。cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x5

6、5010-115cj-zj020-305x25010-11cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-300x3400012-5/25x25010-11cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj6

7、50000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-300x3400012-5/26x1351001-1/25x25010-11cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-300x3400012-5/26x1351001-

8、1/25x25010-11cj-zj000-1-2此时所有的检验数都小于等于0，所以该解为最优解。最优解为X＝（35，5，40，0，0）T，Z*＝235Step0获得一个初始的单纯形表，确定基变量和非基变量Step1检查基变量在目标函数中的系数是否等于0，在约束条中的系数是否是一个单位矩阵。Step2如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且