线性规划方法

什么是线性规划方法?

线性规划方法是在第二次世界大战中发展起来的一种重要的数量方法，线性规划方法是企业执行总产能计划时常用的一种定量方法。线性规划是运筹学的一个最重要的分支，理论上最完善，事实应用得最普遍。首要用于研究有限资源的最佳分配困难，即如何对有限的资源做出最佳方式地调配和最有利地运用，以便最充分地发挥资源的效能去获取最佳的经济效益。受于有成熟的计算机应用软件的支持，采取线性规划模型安排生产计划，并没有是一件问题的事情。在总的计划中，用线性规划模型处理困难的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产能计划。该方法的最大优点是值得处理多品种困难。线性规划方法的数学模型

目标函数：

式中，

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行满秩。