Question

运筹学用单纯形法求解线性规划，要步骤，有加分

用单纯形法求解下列线性规划，给出所有最优解：

　　　　　min f = -2x1 - 3x2

s.t. 　x1 + x2 ≤ 2

4 x1+ 6x2 ≤ 9

x1≥0, x2≥0

Answer 1

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4
max z = 2x1+3x2+0x3+0x4
st. x1 + x2 + x3 = 2
4x1 +6x2 + x4 = 9
建立初始单纯形表
cj 2 3 0 0
cB xB b x1 x2 x3 x4 θ
0 x3 2 1 1 1 0
0 x4 9 4 6 0 1
σj 2 3 0 0
将x2作为入基变量，求得θ为2, 3/2写入上表
cj 2 3 0 0
cB xB b x1 x2 x3 x4 θ
0 x3 2 1 1 1 0 2
0 x4 9 4 6 0 1 3/2
σj 2 3 0 0
将x4作为离基变量，重新计算单纯形表
cj 2 3 0 0
cB xB b x1 x2 x3 x4 θ
0 x3 1/2 1/3 0 0 -1/6
3 x4 3/2 2/3 1 0 1/6
σj 0 0 0 -1/2
存在非基变量x1的检验数σj=0，因此该题有无穷多最优解
其中一个最优解是x1=0,x2=3/2
得到max z = 9/2
得到min f = -9/2