|
|
楼主 |
发表于 2010-9-17 12:21:43
|
显示全部楼层
线性规划的解法
求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。 对于一般线性规划问题： 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行满秩。 |
|
发表于 2010-9-16 20:05:05
沉默卡
变色卡
千斤顶
显身卡
发表于 2010-9-16 21:09:13
发表于 2010-9-24 14:44:18