对于一般线性规划问题:
Min z=CX
S.T.
AX =b
X>=0
其中A为一个m*n矩阵。
若A行满秩
则可以找到基矩阵B,并寻找初始基解。
用N表示对应于B的非基矩阵。则规划问题1可化为:
规划问题2:
Min z=CB XB CNXN
S.T.
B XB N XN = b (1)
XB >= 0, XN >= 0 (2)
(1)两边同乘于B-1,得
XB B-1 N XN = B-1 b
同时,由上式得XB = B-1 b - B-1 N XN,也代入目标函数,问题可以继续化为:
规划问题3:
Min z=CB B-1 b ( CN - CB B-1 N ) XN
S.T.
XB B-1N XN = B-1 b (1)
XB >= 0, XN >= 0 (2)
令N:=B-1N,b:= B-1 b,ζ= CB B-1b,σ= CN - CB B-1 N,则上述问题化为规划问题形式4:
Min z= ζ σ XN
S.T.
XB N XN = b (1)
XB >= 0, XN >= 0 (2)
在上述变换中,若能找到规划问题形式4,使得b>=0,称该形式为初始基解形式。
上述的变换相当于对整个扩展矩阵(包含C及A) 乘以增广矩阵。所以重在选择B,从而找出对应的CB。
若存在初始基解
若σ>= 0
则z >=ζ。同时,令XN = 0,XB = b,这是一个可行解,且此时z=ζ,即达到最优值。所以,此时可以得到最优解。
若σ >= 0不成立
可以采用单纯形表变换。
σ中存在分量<0。这些负分量对应的决策变量编号中,最小的为j。N中与j对应的列向量为Pj。
若Pj <=0不成立
则Pj至少存在一个分量ai,j为正。在规划问题4的约束条件(1)的两边乘以矩阵T。
T=
则变换后,决策变量xj成为基变量,替换掉原来的那个基变量。为使得T b >= 0,且T Pj=ei(其中,ei表示第i个单位向量),需要:
l ai,j>0。
l βq βi*(-aq,j/ai,j)>=0,其中q!=i。即βq>=βi/ ai,j * aq,j。
n 若aq,j<=0,上式一定成立。
n 若aq,j>0,则需要βq / aq,j >=βi/ ai,j。因此,要选择i使得βi/ ai,j最小。
如果这种方法确定了多个下标,选择下标最小的一个。
转换后得到规划问题4的形式,继续对σ进行判断。由于基解是有限个,因此,一定可以在有限步跳出该循环。
若对于每一个i,ai,j<=0
最优值无界。
若不能寻找到初始基解
无解。
若A不是行满秩
化简直到A行满秩,转到若A行满秩。2100433B