文档介绍：运筹学
耿修林
7/14/2018
1
五、单纯形方法
(一)单纯形方法的初步讨论
1、单纯形方法的基本思想
从可行域中的一个基本可行解出发,判断它是否已是最优解,若不是,寻找下一个基本可行解,并使目标函数得到改进,如此迭代下去,直到找出最优解或判定问题无界为止。
从另一个角度说,就是从可行域的某一个极点出发,迭代到另一个极点,并使目标函数的值有所改善,直到找出有无最优解时为止。
7/14/2018
2
五、单纯形方法
(一)单纯形方法的初步讨论
2、单纯形方法:消去法
[例]求解线性规划模型
解:第一步,将线性规划模型标准化:
Max Z=50x1+30x2+0x3+0x4
s·t· 4x1+3x2+x3 =120
2x1+x2+ +x4 =50
x1 , x2 , x3 , ,x4≥0
7/14/2018
3
2、单纯形方法:消去法
第二步,寻找初始可行解。变量x3 、,x4对应的列
向量A3、A4 可作为初始可行基,那么X3、X4为基
变量,X1、X2为非基变量,用非基量表示基变量, 则有:
Max Z=50x1+30x2+0x3+0x4
s·t· x3 =120- 4x1-3x2
x4 =50 -2x1-x2
x1 , x2 , x3 , ,x4≥0
令x1 、 x2 =0,得到基本可行解 X=(0,0,120,50)。
文本
文本
文本
文本
文本
文本
文本
文本
7/14/2018
4
五、单纯形方法
2、单纯形方法:消去法
第三步,判断目标函数是否达到了最优。
第四步,选取入基变量。确定x1 为基变量, x2仍为非基变量。
第五步,选取出基变量。
x3 =120- 4x1-3x2≥0
x4 =50 -2x1-x2≥0
解不等式得:x1≤25 ,只有当x1=25时, x4恰好等于0,所以x4确定为出基变量。于是新的典则方程为:
x1 =25 - - x4
x3 =20 - x2 + 2 x4
7/14/2018
5
五、单纯形方法
(二)单纯形方法的矩阵描述
1、线性规划的典则形式:
Max Z=CBB-1b+(CN-CBB-1N)XN
S·t· XB=B-1b-B-1NXN
XB , XN ≥0
2、判别向量与判别数:
(a)- CBB-1A为对应基B的所有X的判别向量,其中任一分量λj=cj-CBB-1Aj
为变量xj关于基B的判别数,j=1,2, -------, n。
7/14/2018
7
五、单纯形方法
2、判别向量与判别数:
(b)-CBB-1N为对应基B的所有非基变量XN的判别向量,其中任一分量λj=cj-CBB-1Aj
为非基变量xj关于基B的判别数,j=m+1,m+2, ----------, n。
(c)所有基变量的判别向量是零向量,所有基变量的判别数是0(为什么?)。
3、最优解的判定:
(a)如果所有的检验数都小于0,则当前解为最优解。
7/14/2018
8
五、单纯形方法
3、最优解的判定:
(b)如果至少存在一个检验数大于0,且该检验数对应的列向量中至少有一个正分量,则需要继续进行迭代寻找最优解。
(c)如果至少存在一个检验数大于0,且该检验数对应的列向量的所有分量都小于0,则线性规划问题不存在有界最优解。
7/14/2018
9
五、单纯形方法
(三)单纯形方法:表上作业法
1、单纯形表的构造
方法1:C-CBB-1A=()-CBB-1(B,N)
=(-CBB-1N)
两边同乘上X得:
(C-CBB-1A)X= (-CBB-1N)X,化简得:
Z=CBB-1b+(CN-CBB-1N) XN
构造联立方程:
Z+(CBB-1A- C) X =CBB-1b
B-1AX =B-1b
7/14/2018
10