求线性规划问题的最优解
求线性规划问题的最优解:
maxz2x13x22x12x212
4x1 16 s.t.
5x2 15x,x,x0
231
方法1:图解法。(P15 图1-3)
方法2:求出所有的基可行解,然后比较目标值的大小得到最优解。(P14表1-1)
方法3:单纯形法。
第一步,将模型转化为标准型。
maxz2x13x20x30x40x5
2x12x2x3 12 (1)24x1 x4 16 (2) A4s.t.0
5x2 x515 (3)
x,x,x,x,x012345
205
100
010
0
秩A=3 01
第二步,求初始基可行解。
100
010
0
0作为初始基矩阵,x3, x4, x5为基变量,x1, x2为非基变量, 1
(0)
取BP3 P4 P5
令x1=x20,得到初始基可行解X第三步,对初始基可行解X 基可行解X
(0)
(0)
0,0,12,16,15,目标值z
(0)
0.
0,0,12,16,15进行最优性检验。
(0)
0,0,12,16,15对应的目标值为z
(0)
0,因为z02x13x2,只要x1>0或
者 x20,目标值都会比z解X
(0)
0大,即x1or x2之一作为基变量,目标值都会增大,故初始基可行
0,0,12,16,15不是最优解。
(0)
第四步,作基变换,求目标值比z0更大的基可行解。
① 确定换入基变量。由第三步可知,x1, x2都可作为换入基变量,一般地,
z02x13x201x12x2, 10,20. max1,22。
x2作为换入基变量。这里1,2称为基可行解X
(0)
非基变量x1, x2的检验数。
② 确定换出基变量。 x2作为换入基变量,x1仍为非基变量,下面确定另一个非基变量,由方程组(1)(2)(3)得到
x3 122x12x2
x3 122x20
x 164x 41
令x10,且x3,x4,x50得到 x4 16 0,解不等式
x515 5x2
x5155x20x,x,x,x,x0
12345
1512
得到x2min,R,3。
52
当x23时,x3,x4,x50,x3,x4,x5都不能作为非基变量,但x3,x4,x5中必须有一个被换出来作为非基变量,我们注意到当x23时,x30,x40,x50,说明x5可以作为非基变量。
③ 求目标值更大的基可行解。
由①②知,新的基可行解中(3)中
x2,x3,x4是基变量,x1,x5是非基变量,注意方程组(1)(2)
x3,x4的系数列向量已经是单位矩阵的第一列和第二列,x2的系数列向量应变换为单位矩
15
,然后让第三个方程
阵的第三列,而方程组只能是恒等变形,所以让第三个方程一各方程上,可得到下列与(1)(2)(3)等价的方程组
maxz02x13x2
2再加到第
22x x x56 (1)31
5
4x1 x4 16 (2)
x 1x3 (3)
25
5
x1,x2,x3,x4,x50
令
x1x50,得到新的基可行解X(1)0,3,6,16,0,目标值z(1)
(1)
20339
第五步,对基可行解X将目标函数用非基变量
0,3,6,16,0进行最优性检验。
x1,x5表示,
133
z3x22x133x592x1x591x15x5, 120,50
555
因为
x5的检验数5
35
0,故
x5从非基变量取0变为大于0,不会使得目标函数值增大,反而
x1从非基变量取0变为大于0,目标函数值还可以增大,故
更小,但是基可行解X
x1的检验数1
(1)
20,故
0,3,6,16,0仍然不是最优解。
(1)
第六步,作基变换,求目标值比z9更大的基可行解。
① 确定换入基变量。由第五步可知,只有120,即x1是换入基变量,
② 确定换出基变量。 x1作为换入基变量,x5仍为非基变量,下面确定另一个非基变量,由方程组
(1)(2)(3)得到
2
x 62xx5 13
5
x3 62x10 x 164x 41
令x50,且x3,x4,x20得到 x4 162x10,解不等式
x3 1x
25 x23 05
x1,x2,x3,x4,x50
616
得到x1min,,R3。
24
当x13时,x3,x4,x20,x3,x4,x2都不能作为非基变量,但x3,x4,x2中必须有一个被换出来作为非基变量,我们注意到当x13时,x30,x40,x20,说明x3可以作为非基变量。
③ 求目标值更大的基可行解。 由①②知,新的基可行解中中
x1x2,x4是基变量,x3,x5是非基变量,注意方程组(1)(2)(3)
x2,x4的系数列向量已经是单位矩阵的第三列和第二列,x1的系数列向量应变换为单位矩阵的第
12
,然后让第一个方程
一列,而方程组只能是恒等变形,所以让第一个方程程,可得到下列与(1)(2)(3)等价的方程组
maxz92x1
35x5
4再加到第二个方
11
x x x53 (1)1325
4
2x3x4 x54 (2)
5
1
x2 x53 (3)
5
x1,x2,x3,x4,x50
令
x3x50,得到新的基可行解X(2)3,3,0,4,0,目标值z(2)
(2)
233315
第七步,对基可行解X将目标函数用非基变量
3,3,0,4,0进行最优性检验。
x3,x5表示,
z2x13x2
111
23x3x533x5
255 15x3
15x5
150
153x35x5, 310,5
因为
x3,x5的检验数都小于0,故x1或者x5从非基变量取0变为大于0,都不会使得目标函数
(2)
值增大,反而更小,故基可行解X
3,3,0,4,0是最优解。