造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

线性规划方法一般解法

2022/07/16156 作者:佚名
导读:对于一般线性规划问题: 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

对于一般线性规划问题:

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

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读