线性规划方法

1、线性规划模型考虑的因素可能不全面，实际中有些情况没有被考虑到，这就使得线性规划模型过于理想化；

2、实际运用线性规划模型时，虽然一些因素或约束条件被考虑到了，但是由于这些因素或约束条件不易量化或求得（如进行总生产计划常需考虑到的能源单耗就不易求得）时，线性规划模型的运用和有效性因而受到了一定的限制；

3、对一些基础管理不善的企业而言，模型中的单位产品资源消耗系数a很难得到；

4、目标函数中的产为成本系数c实际上是个变量，他随计划的数量结构和品种结构而变。这些问题给机械行业应用线性规划模型带来许多困难，如处理不好，求得的结果的可靠性会很低的。

线性规划模型用在原材料单一、生产过程稳定不变、分解型生产类型的企业是十分有效的，如石油化工厂等。对于产品结构简单、工艺路线短、或者零件加工企业，有较大的应用价值。需要注意的是，对于机电类企业用线性规划模型只适用于作年度的总生产计划，而不宜用来做月度计划。这主要与工件在设备上的排序有关，计划期太短，很难安排过来。

线性规划是运筹学的一个最重要的分支，理论上最完善，实际应用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多品种问题。

目标函数：

式中，

xi--i产品的计划产量；

aik--每生产一个i产品所需k种资源的数量；

bk--第k种资源的拥有量；

Ui--i产品的最高需求量；

Li--i产品的最低需求量；

pi--i产品的单价；

ci--i产品的单位成本。

对于一般线性规划问题：

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

前言

第1章 绪论

第2章 线性规划问题的建模方法

第3章 线性规划问题模型的标准型

第4章 用单纯形算法求解线性规划问题

第5章 对偶规划及影子价格

第6章 灵敏度分析

第7章 大系统决策方案优化选择问题

第8章 线性规划方法的基础性概念

参考文献 2100433B

全书共分八章，分别讲解了线性规划问题的建模方法、线性规划问题模型的标准型、用单纯形算法求解线性规划问题、灵敏度分析等内容。

非线性规划法处理在等式约束或不等式约束条件下优化目标函数，其中等式约束、不等式约束和目标函数为非线性函数。简化梯度法、二次规划法、牛顿法以及近几年讨论比较多的内点法都是非线性规划法的一种。由于最优潮流问题中等式约束是典型的非线性等式，因此非线性规划法也就成为解决最优潮流问题的常用方法。

最优潮流简化梯度法

利用牛顿拉夫逊潮流程序，采用梯度法进行搜索，用罚函数处理违约的不等式约束。该方法程序编制简便，所需存储量小，对初始点无特殊要求，曾获得普遍重视，成为第一种有效的优化潮流方法。由于该法仅在控制变量子空间上寻优，故称为简化梯度法。

梯度法实际上等同于无约束问题的最速下降法。最速下降法的基本思想是利用函数值在迭代点下降最快的方向作为寻优方向，以使函数值尽快达到极小。由于函数值下降最快的方向为负梯度方向，因此该法也称为梯度法。OPF的简化梯度法首先利用Lagrange乘子法引入等式约束，得到增广的目标函数L(x )=F (x) wag (x）化为无约束问题求解。独立变量空间为系统的控制变量，用罚函数处理函数不等式约束。

随后PQ解耦法和稀疏技术!、被使用到梯度法上。将梯度法优化分解为两步进行，第一步不加约束进行梯度优化，第二步将结果进行修正后，在目标函数上加上可能的电压越限罚函数。该方法可以处理较大的网络规模，但是计算结果有在可行域之外。使用共骊梯度法改进梯度法的搜索方向，结果显示收敛比常规的简化梯度法快。

简化梯度法的缺点:迭代过程中，尤其是在接近最优点附近会出现锯齿现象，收敛性较差，收敛速度很慢;每次迭代都要重新计算潮流，计算量很大，耗时较多;另外，采用罚函数处理不等式时，罚因子数值的选取对算法的收敛速度影响很大等等。现在对这种方法用于最优潮流的研究己经很少。

最优潮流序列二次规划法

序列二次规划法属于典型的非线性规划算法，其所优化的目标函数为二次实函数，其约束一般为线性。序列二次规划法使用拟牛顿法!m一‘8]作为主算法，使用罚函数处理约束，使用一种按照一定规则更新的矩阵来近似代替二阶海森阵。有约束的拟牛顿法由于加入了Kuhn-Tucke访程的二阶信息，能保证超线性的收敛性。在每一次主要迭代中QP子问题依次被求解，所以这种方法又称为序列二次规划法。SQP法允许有约束的牛顿法转化为无约束的牛顿法，拟牛顿法的收敛性比梯度法要好，但是由于近似海森矩阵不是稀疏的，使得拟牛顿法在大型网络中效率不高，限制了其在大型网络中的使用。

二次规划法是二阶的方法，解决最优潮流问题收敛精度较好，能很好地解决藕合的最优潮流问题，但缺点是计算Lagrange函数的二阶偏导数，计算量大、计算复杂。

最优潮流牛顿法

牛顿法是一种直接求解寻优的方法。以牛顿法为基础的最优潮流用以实现系统无功的优化，这种方法被公认为是牛顿OPF算法实用化的重大飞跃。该法以Lagrange乘子法处理等式约束，以惩罚函数法处理违约的变量不等式约束。该文首次将电力系统的稀疏性与牛顿法结合起来，使得计算量大大减小。对912节点的系统测试，利用解耦的PQ分解牛顿法迭代，效果较好。其缺点是对函数不等式约束处理得不好。

牛顿法的难点在于:在迭代过程中，中间变量是不满足潮流方程的。那么在每一个迭代步变量修正后，无法判断不等式约束是否越界，但是如果不能确定那些越界的不等式袍作用的不等式约束集)就无法形成罚函数，而且引入的罚函数对 Hessian阵的部分对角元素有影响，会明显改变计算结果。因此对违约不等式约束的处理，在牛顿法中多采用试验迭代处理，对违约变量进行修正。

牛顿法中，起作用的不等式约束集通常用试验迭代来确定，增加了计算的难度和复杂性。针对此问题，提出用线性规划技术取代试验迭代来进行起作用的不等式约束集的识别，避免使用试验迭代。不等式约束处理过程中考虑优先级策略，认为变量型约束优先级高，函数型约束优先级低。当高优先级约束逐步稳定后再将低优先级约束引入试验迭代。快速预估起作用不等式约束集方法。而文献 基于有效标准，选择和施加最少数量起作用的等式约束，以少的振荡很快得到优化解。

Newton最优潮流优点在于:利用了二阶导数信息，收敛快，使用稀疏技术节省内存，可用于大规模网络。缺点是:难以有效确定约束集，普遍用试验迭代法，编程实现困难;对应控制变量的Hessian阵对角元易出现小值或零值，造成矩阵奇异;引入的La-grange乘子的初值对迭代计算的稳定性影响大。

最优潮流内点法

内点法最初是作为一种线性规划算法，是为了解决单纯形法计算量随变量规模急剧增加而提出来的。内点法从初始内点出发，沿着可行方向，求出使目标函数值下降的后继内点，沿另一个可行方向求出使目标函数值下降的内点，重复以上步骤，从可行域内部向最优解迭代，得出一个由内点组成的序列，使得目标函数值严格单调下降。其特征是迭代次数和系统规模无关。

最优潮流无限点优化算法

无限点优化算法可以看作内点法的改进，基于原一对偶内点算法的内点法由前面的分析可知具有以下特点:①对于不等式约束的处理是:使用松弛变量将不等式约束变为等式约束;②其所有约束变量的迭代初始值，包括松弛变量，必须在可行域之内;③在原目标函数基础上增加障碍函数份般为对数障碍函数);①使用牛顿法求解KKT条件方程过程中必须使用一种严格的计算方法逐步减小障碍参数份般使用对偶间隙法久需要控制迭代步长以保持解的可行性。由于障碍参数和步长的确定对优化的影响较大，对于它们的确定成为限制内点法的主要因素。