线性规划方法

什么是线性规划方法?
　　线性规划方法是在第二次世界大战中发展起来的一种重要的数量方法，线性规划方法是企业进行总产量计划时常用的一种定量方法。线性规划是运筹学的一个最重要的分支，理论上最完善，实际应用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多品种问题。线性规划方法的数学模型
　　目标函数：
　　式中，
　　xi--i产品的计划产量；
　　aik--每生产一个i产品所需k种资源的数量；
　　bk--第k种资源的拥有量；
　　Ui--i产品的最高需求量；
　　Li--i产品的最低需求量；
　　pi--i产品的单价；
　　ci--i产品的单位成本。运用线性规划模型进行总生产计划时的问题
　　1、线性规划模型考虑的因素可能不全面，实际中有些情况没有被考虑到，这就使得线性规划模型过于理想化；
　　2、实际运用线性规划模型时，虽然一些因素或约束条件被考虑到了，但是由于这些因素或约束条件不易量化或求得（如进行总生产计划常需考虑到的能源单耗就不易求得）时，线性规划模型的运用和有效性因而受到了一定的限制；
　　3、对一些基础管理不善的企业而言，模型中的单位产品资源消耗系数a很难得到；
　　4、目标函数中的产为成本系数c实际上是个变量，他随计划的数量结构和品种结构而变。这些问题给机械行业应用线性规划模型带来许多困难，如处理不好，求得的结果的可靠性会很低的。线性规划模型的适用性
　　线性规划模型用在原材料单一、生产过程稳定不变、分解型生产类型的企业是十分有效的，如石油化工厂等。对于产品结构简单、工艺路线短、或者零件加工企业，有较大的应用价值。需要注意的是，对于机电类企业用线性规划模型只适用于作年度的总生产计划，而不宜用来做月度计划。这主要与工件在设备上的排序有关，计划期太短，很难安排过来。线性规划问题的一般解法
　　对于一般线性规划问题：
　　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行满秩。