线性规划模型_线性规划模型解的步骤_线性规划三大常用题型(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行满秩。

发展

法国数学家J.- B.- J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提

出线性规划的想法，但未引起注意。

1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。

1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。

1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。

1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。

50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。

线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。