線性規(guī)劃方法

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

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

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

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

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

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

目標(biāo)函數(shù)：

式中，

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

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

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

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

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

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

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

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

Min z=CX

S.T.

AX =b

X>=0

其中A為一個(gè)m*n矩陣。

若A行滿秩

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

用N表示對(duì)應(yīng)于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

同時(shí)，由上式得XB = B-1 b - B-1 N XN，也代入目標(biāo)函數(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，稱該形式為初始基解形式。

上述的變換相當(dāng)于對(duì)整個(gè)擴(kuò)展矩陣（包含C及A） 乘以增廣矩陣。所以重在選擇B，從而找出對(duì)應(yīng)的CB。

若存在初始基解

若σ>= 0

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

若σ >= 0不成立

可以采用單純形表變換。

σ中存在分量<0。這些負(fù)分量對(duì)應(yīng)的決策變量編號(hào)中，最小的為j。N中與j對(duì)應(yīng)的列向量為Pj。

若Pj <=0不成立

則Pj至少存在一個(gè)分量ai，j為正。在規(guī)劃問題4的約束條件（1）的兩邊乘以矩陣T。

T=

則變換后，決策變量xj成為基變量，替換掉原來(lái)的那個(gè)基變量。為使得T b >= 0，且T Pj=ei（其中，ei表示第i個(gè)單位向量），需要：

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最小。

如果這種方法確定了多個(gè)下標(biāo)，選擇下標(biāo)最小的一個(gè)。

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

若對(duì)于每一個(gè)i，ai,j<=0

最優(yōu)值無(wú)界。

若不能尋找到初始基解

無(wú)解。

若A不是行滿秩

化簡(jiǎn)直到A行滿秩，轉(zhuǎn)到若A行滿秩。2100433B

前言

第1章 緒論

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

第3章 線性規(guī)劃問題模型的標(biāo)準(zhǔn)型

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

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

第6章 靈敏度分析

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

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

參考文獻(xiàn) 2100433B

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最優(yōu)潮流內(nèi)點(diǎn)法

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

最優(yōu)潮流無(wú)限點(diǎn)優(yōu)化算法

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