線性規(guī)劃方法一般解法

對于一般線性規(guī)劃問題：

Min z=CX

S.T.

AX =b

X>=0

其中A為一個m*n矩陣。

若A行滿秩

則可以找到基矩陣B，并尋找初始基解。

用N表示對應于B的非基矩陣。則規(guī)劃問題1可化為：

規(guī)劃問題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，也代入目標函數(shù)，問題可以繼續(xù)化為：

規(guī)劃問題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，則上述問題化為規(guī)劃問題形式4：

Min z= ζ σ XN

S.T.

XB N XN = b (1)

XB >= 0, XN >= 0 (2)

在上述變換中，若能找到規(guī)劃問題形式4，使得b>=0，稱該形式為初始基解形式。

上述的變換相當于對整個擴展矩陣（包含C及A） 乘以增廣矩陣。所以重在選擇B，從而找出對應的CB。

若存在初始基解

若σ>= 0

則z >=ζ。同時，令XN = 0，XB = b，這是一個可行解，且此時z=ζ，即達到最優(yōu)值。所以，此時可以得到最優(yōu)解。

若σ >= 0不成立

可以采用單純形表變換。

σ中存在分量<0。這些負分量對應的決策變量編號中，最小的為j。N中與j對應的列向量為Pj。

若Pj <=0不成立

則Pj至少存在一個分量ai，j為正。在規(guī)劃問題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最小。

如果這種方法確定了多個下標，選擇下標最小的一個。

轉換后得到規(guī)劃問題4的形式，繼續(xù)對σ進行判斷。由于基解是有限個，因此，一定可以在有限步跳出該循環(huán)。

若對于每一個i，ai,j<=0

最優(yōu)值無界。

若不能尋找到初始基解

無解。

若A不是行滿秩

化簡直到A行滿秩，轉到若A行滿秩。2100433B

線性規(guī)劃模型用在原材料單一、生產(chǎn)過程穩(wěn)定不變、分解型生產(chǎn)類型的企業(yè)是十分有效的，如石油化工廠等。對于產(chǎn)品結構簡單、工藝路線短、或者零件加工企業(yè)，有較大的應用價值。需要注意的是，對于機電類企業(yè)用線性規(guī)劃模型只適用于作年度的總生產(chǎn)計劃，而不宜用來做月度計劃。這主要與工件在設備上的排序有關，計劃期太短，很難安排過來。

1、線性規(guī)劃模型考慮的因素可能不全面，實際中有些情況沒有被考慮到，這就使得線性規(guī)劃模型過于理想化；

2、實際運用線性規(guī)劃模型時，雖然一些因素或約束條件被考慮到了，但是由于這些因素或約束條件不易量化或求得（如進行總生產(chǎn)計劃常需考慮到的能源單耗就不易求得）時，線性規(guī)劃模型的運用和有效性因而受到了一定的限制；

3、對一些基礎管理不善的企業(yè)而言，模型中的單位產(chǎn)品資源消耗系數(shù)a很難得到；

4、目標函數(shù)中的產(chǎn)為成本系數(shù)c實際上是個變量，他隨計劃的數(shù)量結構和品種結構而變。這些問題給機械行業(yè)應用線性規(guī)劃模型帶來許多困難，如處理不好，求得的結果的可靠性會很低的。

目標函數(shù)：

式中，

xi--i產(chǎn)品的計劃產(chǎn)量；

aik--每生產(chǎn)一個i產(chǎn)品所需k種資源的數(shù)量；

bk--第k種資源的擁有量；

Ui--i產(chǎn)品的最高需求量；

Li--i產(chǎn)品的最低需求量；

pi--i產(chǎn)品的單價；

ci--i產(chǎn)品的單位成本。

線性規(guī)劃是運籌學的一個最重要的分支，理論上最完善，實際應用得最廣泛。主要用于研究有限資源的最佳分配問題，即如何對有限的資源作出最佳方式地調配和最有利地使用，以便最充分地發(fā)揮資源的效能去獲取最佳的經(jīng)濟效益。由于有成熟的計算機應用軟件的支持，采用線性規(guī)劃模型安排生產(chǎn)計劃，并不是一件困難的事情。在總體計劃中，用線性規(guī)劃模型解決問題的思路是，在有限的生產(chǎn)資源和市場需求條件約束下，求利潤最大的總產(chǎn)量計劃。該方法的最大優(yōu)點是可以處理多品種問題。

前言

第1章 緒論

第2章 線性規(guī)劃問題的建模方法

第3章 線性規(guī)劃問題模型的標準型

第4章 用單純形算法求解線性規(guī)劃問題

第5章 對偶規(guī)劃及影子價格

第6章 靈敏度分析

第7章 大系統(tǒng)決策方案優(yōu)化選擇問題

第8章 線性規(guī)劃方法的基礎性概念

參考文獻 2100433B

全書共分八章，分別講解了線性規(guī)劃問題的建模方法、線性規(guī)劃問題模型的標準型、用單純形算法求解線性規(guī)劃問題、靈敏度分析等內容。

非線性規(guī)劃法處理在等式約束或不等式約束條件下優(yōu)化目標函數(shù)，其中等式約束、不等式約束和目標函數(shù)為非線性函數(shù)。簡化梯度法、二次規(guī)劃法、牛頓法以及近幾年討論比較多的內點法都是非線性規(guī)劃法的一種。由于最優(yōu)潮流問題中等式約束是典型的非線性等式，因此非線性規(guī)劃法也就成為解決最優(yōu)潮流問題的常用方法。

最優(yōu)潮流簡化梯度法

利用牛頓拉夫遜潮流程序，采用梯度法進行搜索，用罰函數(shù)處理違約的不等式約束。該方法程序編制簡便，所需存儲量小，對初始點無特殊要求，曾獲得普遍重視，成為第一種有效的優(yōu)化潮流方法。由于該法僅在控制變量子空間上尋優(yōu)，故稱為簡化梯度法。

梯度法實際上等同于無約束問題的最速下降法。最速下降法的基本思想是利用函數(shù)值在迭代點下降最快的方向作為尋優(yōu)方向，以使函數(shù)值盡快達到極小。由于函數(shù)值下降最快的方向為負梯度方向，因此該法也稱為梯度法。OPF的簡化梯度法首先利用Lagrange乘子法引入等式約束，得到增廣的目標函數(shù)L(x )=F (x) wag (x）化為無約束問題求解。獨立變量空間為系統(tǒng)的控制變量，用罰函數(shù)處理函數(shù)不等式約束。

隨后PQ解耦法和稀疏技術!、被使用到梯度法上。將梯度法優(yōu)化分解為兩步進行，第一步不加約束進行梯度優(yōu)化，第二步將結果進行修正后，在目標函數(shù)上加上可能的電壓越限罰函數(shù)。該方法可以處理較大的網(wǎng)絡規(guī)模，但是計算結果有在可行域之外。使用共驪梯度法改進梯度法的搜索方向，結果顯示收斂比常規(guī)的簡化梯度法快。

簡化梯度法的缺點:迭代過程中，尤其是在接近最優(yōu)點附近會出現(xiàn)鋸齒現(xiàn)象，收斂性較差，收斂速度很慢;每次迭代都要重新計算潮流，計算量很大，耗時較多;另外，采用罰函數(shù)處理不等式時，罰因子數(shù)值的選取對算法的收斂速度影響很大等等。現(xiàn)在對這種方法用于最優(yōu)潮流的研究己經(jīng)很少。

最優(yōu)潮流序列二次規(guī)劃法

序列二次規(guī)劃法屬于典型的非線性規(guī)劃算法，其所優(yōu)化的目標函數(shù)為二次實函數(shù)，其約束一般為線性。序列二次規(guī)劃法使用擬牛頓法!m一‘8]作為主算法，使用罰函數(shù)處理約束，使用一種按照一定規(guī)則更新的矩陣來近似代替二階海森陣。有約束的擬牛頓法由于加入了Kuhn-Tucke訪程的二階信息，能保證超線性的收斂性。在每一次主要迭代中QP子問題依次被求解，所以這種方法又稱為序列二次規(guī)劃法。SQP法允許有約束的牛頓法轉化為無約束的牛頓法，擬牛頓法的收斂性比梯度法要好，但是由于近似海森矩陣不是稀疏的，使得擬牛頓法在大型網(wǎng)絡中效率不高，限制了其在大型網(wǎng)絡中的使用。

二次規(guī)劃法是二階的方法，解決最優(yōu)潮流問題收斂精度較好，能很好地解決藕合的最優(yōu)潮流問題，但缺點是計算Lagrange函數(shù)的二階偏導數(shù)，計算量大、計算復雜。

最優(yōu)潮流牛頓法

牛頓法是一種直接求解尋優(yōu)的方法。以牛頓法為基礎的最優(yōu)潮流用以實現(xiàn)系統(tǒng)無功的優(yōu)化，這種方法被公認為是牛頓OPF算法實用化的重大飛躍。該法以Lagrange乘子法處理等式約束，以懲罰函數(shù)法處理違約的變量不等式約束。該文首次將電力系統(tǒng)的稀疏性與牛頓法結合起來，使得計算量大大減小。對912節(jié)點的系統(tǒng)測試，利用解耦的PQ分解牛頓法迭代，效果較好。其缺點是對函數(shù)不等式約束處理得不好。

牛頓法的難點在于:在迭代過程中，中間變量是不滿足潮流方程的。那么在每一個迭代步變量修正后，無法判斷不等式約束是否越界，但是如果不能確定那些越界的不等式袍作用的不等式約束集)就無法形成罰函數(shù)，而且引入的罰函數(shù)對 Hessian陣的部分對角元素有影響，會明顯改變計算結果。因此對違約不等式約束的處理，在牛頓法中多采用試驗迭代處理，對違約變量進行修正。

牛頓法中，起作用的不等式約束集通常用試驗迭代來確定，增加了計算的難度和復雜性。針對此問題，提出用線性規(guī)劃技術取代試驗迭代來進行起作用的不等式約束集的識別，避免使用試驗迭代。不等式約束處理過程中考慮優(yōu)先級策略，認為變量型約束優(yōu)先級高，函數(shù)型約束優(yōu)先級低。當高優(yōu)先級約束逐步穩(wěn)定后再將低優(yōu)先級約束引入試驗迭代?？焖兕A估起作用不等式約束集方法。而文獻 基于有效標準，選擇和施加最少數(shù)量起作用的等式約束，以少的振蕩很快得到優(yōu)化解。

Newton最優(yōu)潮流優(yōu)點在于:利用了二階導數(shù)信息，收斂快，使用稀疏技術節(jié)省內存，可用于大規(guī)模網(wǎng)絡。缺點是:難以有效確定約束集，普遍用試驗迭代法，編程實現(xiàn)困難;對應控制變量的Hessian陣對角元易出現(xiàn)小值或零值，造成矩陣奇異;引入的La-grange乘子的初值對迭代計算的穩(wěn)定性影響大。

最優(yōu)潮流內點法

內點法最初是作為一種線性規(guī)劃算法，是為了解決單純形法計算量隨變量規(guī)模急劇增加而提出來的。內點法從初始內點出發(fā)，沿著可行方向，求出使目標函數(shù)值下降的后繼內點，沿另一個可行方向求出使目標函數(shù)值下降的內點，重復以上步驟，從可行域內部向最優(yōu)解迭代，得出一個由內點組成的序列，使得目標函數(shù)值嚴格單調下降。其特征是迭代次數(shù)和系統(tǒng)規(guī)模無關。

最優(yōu)潮流無限點優(yōu)化算法

無限點優(yōu)化算法可以看作內點法的改進，基于原一對偶內點算法的內點法由前面的分析可知具有以下特點:①對于不等式約束的處理是:使用松弛變量將不等式約束變?yōu)榈仁郊s束;②其所有約束變量的迭代初始值，包括松弛變量，必須在可行域之內;③在原目標函數(shù)基礎上增加障礙函數(shù)份般為對數(shù)障礙函數(shù));①使用牛頓法求解KKT條件方程過程中必須使用一種嚴格的計算方法逐步減小障礙參數(shù)份般使用對偶間隙法久需要控制迭代步長以保持解的可行性。由于障礙參數(shù)和步長的確定對優(yōu)化的影響較大，對于它們的確定成為限制內點法的主要因素。