最優(yōu)化理論與方法1(2014簡版)

1、最優(yōu)化理論與方法講義（上）第一章緒論1.1學科簡介最優(yōu)化這一數(shù)學分支，為這些問題的解決提供了理論基礎(chǔ)和求解方法。最優(yōu)化就是在一切可能的方案中選擇一個最好的方案以達到最優(yōu)目標的學科。1.1.1優(yōu)化的含義優(yōu)化是從處理各種事物的一切可能的方案中，尋求最優(yōu)的方案。（1）來源：優(yōu)化一語來自英文Optimization,其本意是尋優(yōu)的過程；（2）優(yōu)化過程：是尋找約束空間下給定函數(shù)取極大值（以max表示）或極小（以min表示）的過程。1.2發(fā)展概況第一階段人類智能優(yōu)化第二階段數(shù)學規(guī)劃方法優(yōu)化第三階段工程優(yōu)化第四階段現(xiàn)代優(yōu)化方法1.3研究意義研究意義：最優(yōu)化在本質(zhì)上是一門交叉學科，它對許多學科產(chǎn)生了重大影響，

2、并已成為不同領(lǐng)域中很多工作都不可或缺的工具。應用范圍：信息工程及設(shè)計、經(jīng)濟規(guī)劃、生產(chǎn)管理、交通運輸、國防工業(yè)以及科學研究等諸多領(lǐng)域?？傊?，它是一門應用性相當廣泛的學科，討論決策的問題具有最佳選擇之特性。它尋找最佳的計算方法，研究這些計算方法的理論性質(zhì)及其實際計算表現(xiàn)。1.4示例例1資源分配問題某工廠生產(chǎn)A和B兩種產(chǎn)品，A產(chǎn)品單位價格為P萬元，B產(chǎn)A品單位價格為P萬元。每生產(chǎn)一個單位A產(chǎn)品需消耗煤a噸，電aBCE度,人工a個人日；每生產(chǎn)一個單位B產(chǎn)品需消耗煤b噸，電b度,LCE人工b個人日。現(xiàn)有可利用生產(chǎn)資源煤C噸，電E度，勞動力L個L人日，欲找出其最優(yōu)分配方案，使產(chǎn)值最大。分析：（1）產(chǎn)值的表

3、達式；（2）優(yōu)化變量確定：A產(chǎn)品x，B產(chǎn)品x；優(yōu)化約束條件:AB生產(chǎn)資源煤約束;生產(chǎn)資源電約束；生產(chǎn)資源勞動力約束。優(yōu)化蠻矍：兀生產(chǎn)資源電約束；生產(chǎn)資源勞動力約束。目標函mnxP聲R+巴鼻：約東親件；十瓦耳C十叭心匚例2指派問題設(shè)有四項任務B、B、12B、B派四個人A、A設(shè)有四項任務B、B、12341234每個人都可以承擔四項任務中的任何一項，但所消耗的資金不同。設(shè)A完成B所需資金為c。如何分配任務，使總支出最少?ij分析：設(shè)變量x分析：設(shè)變量xij1指派A完成B任務,1j0,不指派A完成B任務則總支出可表示為：s=cxijiji=1j=1數(shù)學模型:minS=44cxijiji=1j=1s.t

4、.x=1,i=1,2,3,4ijj=1x=1,j=1,2,3,4iji=1x,1i,j=1,2,3,4ij1.5最優(yōu)化的數(shù)學模型最優(yōu)化的數(shù)學模型是描述實際優(yōu)化問題目標函數(shù)、變量關(guān)系、有關(guān)約束條件和意圖的數(shù)學表達式，并能反映物理現(xiàn)象各主要因素的內(nèi)在聯(lián)系，是進行最優(yōu)化的基礎(chǔ)。1.5.1基本概念1、決策變量(Decisionvariables)問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制，也稱優(yōu)化變量。決策變量或優(yōu)化變量的全體實際上是一組變量，可用一個列向量表示。優(yōu)化變量的數(shù)目稱為優(yōu)化問題的維數(shù)，如n個優(yōu)化變量，則稱為n維優(yōu)化問題。優(yōu)化問題的維數(shù)表征優(yōu)化的自由度。優(yōu)

5、化變量愈多，則問題的自由度愈大、可供選擇的方案愈多，但難度亦愈大、求解亦愈復雜。通常，小型優(yōu)化問題：一般含有210個優(yōu)化變量；中型優(yōu)化問題：1050個優(yōu)化變量；大型優(yōu)化問題：50個以上的優(yōu)化變量。如何選定優(yōu)化變量？確定優(yōu)化變量時應注意以下幾點：抓主要，舍次要。根據(jù)要解決問題的特殊性來選擇優(yōu)化變量。2、約束條件(Constraintconditions)一指決策變量取值時受到的各種資源條件的限制。約束又可按其數(shù)學表達形式分成等式約束和不等式約束兩種類型：等式約束：h(x)=0不等式約束：gx)0根據(jù)約束的性質(zhì)可以把它們區(qū)分成：性能約束一針對性能要求而提出的限制條件稱作性能約束。邊界約束一只是對設(shè)

6、計變量的取值范圍加以限制的約束稱作邊界約束。圖1-2優(yōu)化問題中的約束面或約束線)(a)、二變量問題的約束線(b)三變量問題的約束面可行域：在優(yōu)化問題中，滿足所有約束條件的點所構(gòu)成的集合。如約束條件g(X)=x2x2-16，0和gX)=2-x，0的維設(shè)計問11222題的可行域D。圖約束條件規(guī)定的可行域D般情況下，可行域可表示為：Dg(xDg(x,0)u=1,2,lh(jc)=0,j=1,2,，mjf不可行域：Df可行點和不可行點：約束邊界上的可行點為邊界點，其余可行點為內(nèi)點。f起作用的約束與不起作用的約束：滿足g(X*)=0的約束為起作用約u束，否則為不起作用的約束。(等式約束一定是起作用約束)

7、3、目標函數(shù)(Objectivefunction)一它是決策變量的函數(shù)。為了對優(yōu)化進行定量評價，必須構(gòu)造包含優(yōu)化變量的評價函數(shù)，它是優(yōu)化的目標，稱為目標函數(shù)，以f(x)表示。f(X)=f(x,x,x)12n在優(yōu)化過程中，通過優(yōu)化變量的不斷向f(x)值改善的方向自動調(diào)整，最后求得f(x)值最好或最滿意的X值。在構(gòu)造目標函數(shù)時，目標函數(shù)的最優(yōu)值可能是最大值，也可能是最小值。在優(yōu)化問題中，可以只有一個目標函數(shù)，稱為單目標函數(shù)。當在同一設(shè)計中要提出多個目標函數(shù)時，這種問題稱為多目標函數(shù)的最優(yōu)化問題。31目標函數(shù)等值(線)面定義：在高維空間(n,3)中，使目標函數(shù)值取同一常數(shù)的點集&/f(X)=c,c為

8、常數(shù)，稱為f(X)的等值線(或等值面)。(或定義：對于具有相等目標函數(shù)值的自變量構(gòu)成的平面曲線或曲面稱為等值線或等值面。)數(shù)學表達式f&)=cc為一系列常數(shù)，代表一族n維超曲面。對于具有相等目標函數(shù)值的自變量構(gòu)成的平面曲線或曲面稱為等值線或等值面。性質(zhì)在通常情況下，若目標函數(shù)f(X)是連續(xù)的單值函數(shù)，則其等值線具有以下性質(zhì)：不同值的等值線不相交；除極值點所在的等值線外，等值線不會中斷；等值線稠密的地方，目標函數(shù)值變化較快，而稀疏的地方,目標函數(shù)值變化較慢；在極值點附近，等值線近似地呈現(xiàn)為同心橢球面族(橢圓族)。4、可行域(Feasibleregion)滿足約束條件的決策變量的取值范圍。5、最優(yōu)

9、解(Optimalsolution)一可行域中使目標函數(shù)達到最優(yōu)的決策變量的值。優(yōu)化問題一般數(shù)學形式設(shè)優(yōu)化變量向量X，lx,x，,x112n求目標函數(shù)f(X)tmin滿足約束條件:g(X0,j，1,2,mjh(X)，0,k，1,2,lk即minf(X，f(x,x，xXeRn12nS.t.g(X0,j，1,2,mjh(X)，0,k，1,2,lk建模實例建立優(yōu)化問題的數(shù)學模型一般步驟：根據(jù)問題要求，應用專業(yè)范圍內(nèi)的現(xiàn)行理論和經(jīng)驗等，對優(yōu)化對象進行分析。對諸參數(shù)進行分析，以確定問題的原始參數(shù)、優(yōu)化常數(shù)和優(yōu)化變量。根據(jù)問題要求，確定并構(gòu)造目標函數(shù)和相應的約束條件，有時要構(gòu)造多目標函數(shù)。必要時對數(shù)學模型

10、進行規(guī)范化，以消除諸組成項間由于量綱不同等原因?qū)е碌臄?shù)量懸殊的影響。例混合飼料配合以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。設(shè)每天需要混合飼料的批量為100磅，這份飼料必須含:至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為：配料每鑄配料中的營養(yǎng)含量每務成*（元）鈣蛋白質(zhì)纖維石灰石大豆粉0.3800.00OJQO0.0010.090.020*0020*500.01640.1250解：設(shè)x,x,x是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的TOC o 1-5 h z123量（磅）。minZ=0.016

11、4x+0.0463x+0.1250 x123st.x+x+x=1001230380 x+0.001x+0.002x0.012100123，0.380 x+0.001x+0.002x0.0081001230.09x+0.50 x0.22100230.02x+0.08x012解：畫出等式約束曲線x+x25x=0的圖形。這是一條拋物線;122畫出不等式約束區(qū)域：x+x-50和x,x0；1212畫出目標函數(shù)等值線，以及等值線與可行集的切點。可見可行域為曲線段ABCD。d點是使目標函數(shù)值最小的可行點，其坐標可通過解方程組:得出:x+得出:x+x2-5x=0122x+x5=0121.6.2優(yōu)化問題的基本解

12、法求解優(yōu)化問題的基本解法有：解析法和數(shù)值解法。1.6.2.1解析法利用數(shù)學分析(微分、變分等)的方法，根據(jù)函數(shù)(泛函)極值的必要條件和充分條件求出其最優(yōu)解析解的求解方法。局限性：工程優(yōu)化問題的目標函數(shù)和約束條件往往比較復雜，有時甚至還無法用數(shù)學方程描述，在這種情況下應用數(shù)學分析方法就會帶來麻煩。1.6.2.2數(shù)值解法這是一種數(shù)值近似計算方法，又稱為數(shù)值迭代方法。它是根據(jù)目標函數(shù)的變化規(guī)律，以適當?shù)牟介L沿著能使目標函數(shù)值下降的方向，逐步向目標函數(shù)值的最優(yōu)點進行探索，逐步逼近到目標函數(shù)的最優(yōu)點或直至達到最優(yōu)點。數(shù)值解法(迭代法)是優(yōu)化設(shè)計問題的基本解法。其中也可能用到解析法，如最速下降方向的選取、

13、最優(yōu)步長的確定等。數(shù)值計算的迭代方法具有以下特點：是數(shù)值計算而不是數(shù)學分析方法；具有簡單的邏輯結(jié)構(gòu)并能反復進行同樣的數(shù)值計算；最后得出的是逼近精確解的近似解。這些特點正與計算機的工作特點相一致。在數(shù)學規(guī)劃中，采用Xk+1，Xk+dk進行迭代運算時，求n維函數(shù)f(X,f(x,x,x)的極k12n值點的具體算法如下圖所示。一、求解步驟：數(shù)值迭代法的基本思路：是進行反復的數(shù)值計算，尋求目標函數(shù)值不斷下降的可行計算點，直到最后獲得足夠精度的最優(yōu)點。這種方法的求優(yōu)過程大致可歸納為以下步驟：（1）首先初選一個盡可能靠近最小點的初始點X（0），從X（0）出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步

14、達到X1）點；（2）得到新點X1）后再選擇一個新的使函數(shù)值迅速下降的方向及適當?shù)牟介L，從XG）點出發(fā)再跨出一步，達到X（2）點，并依此類推，一步一步地向前探索并重復數(shù)值計算，最終達到目標函數(shù)的最優(yōu)點。在中間過程中每一步的迭代形式為：X(kX(k+1)X(k)+，(k)s(k)上式中：x）一第k步迭代計算所得到的點,稱第k步迭代點，亦為第k步設(shè)計方案;,k）一第k步迭代計算的步長;圖迭代計算機逐步逼近最優(yōu)點過程示意圖sCt）一第k步迭代計算的探索方向。用迭代法逐步逼近最優(yōu)點的探索過程如右圖所示。運用迭代法，每次迭代所得新的點的目標函數(shù)都應滿足函數(shù)值下降的要求:fx（k+i）0，都存在一個只與有關(guān)

15、而與咒無關(guān)的自然數(shù)N,使得當兩自然數(shù)m,pN時,滿足Xm-XPmmXP人8iii=1或（二）迭代終止準則（1）點距準則XkXk+1Xk|8或Xk+1Xk8Xk2其中8、8是事先給定的要求精度。12（2）函數(shù)值下降量準則fkfk+1fk8JJ3fk+1fk1503510130235120余料長度（cm）56235246235上述下料問題的數(shù)學模型為：minf&)=5x+6x+23x+5x+24x+6x+23x+5xTOC o 1-5 h z2345678St.2x+x+x+x=1001234x+x+3x+2x+x15023567x+x+3x+2x+3x+5x120134678x0=1,2,8i2

16、.1.2基本特點丄線性規(guī)劃問題的共同特征：一組決策變量X表示一個方案，一般X大于等于零。約束條件是線性等式或不等式。目標函數(shù)是線性的，且求目標函數(shù)最大化或最小化。丄線性規(guī)劃模型的一般形式：minf=exexex1122nnTOC o 1-5 h zax+axax1111221nnax+axax2112222nnax+axaxm11m22mnnx,x，x0 x,x匕力q+1n線性規(guī)劃問題的標準形式(1)標準形式為一目標函數(shù)最小、約束條件等式、決策變量非負。minf=ex+ex+ex1122nnax+ax+ax+ax1111221nnax+ax+ax2112222nn(2)簡寫形式(3)向量形式a

17、x+a(2)簡寫形式(3)向量形式ax+ax+axm11m22mnnx,x,x0V12nminf(X)=工j=1工ax=b,i=1,2,mijjij=1x0,j=1,2,njminf&)=exs.t.工AX=bjjj=1x0,s.t.工AX=bjjj=1x0,j=1,2,nvj其中C（c1，X2,XnAu,a，aj1j2jtnj（4）矩陣形式st.AX=bXO其中TOC o 1-5 h zaa其中=VA,A,A)12naam1mn丄一般線性規(guī)劃問題的標準化目標函數(shù)最小;maxf（X）=CX等價于（X）約束條件等式；約束條件16改為minf*=-2x一3x一0 x約束條件16改為minf*=-2

18、x一3x一0 x一0 x一0 x“2345=83+x=1x1242+x=1250 x+2x+x124x14x2x,x,x,x,x12345“”約束：減去非負剩余變量,即x可正可負k（即無約束）。x+x+x+(xx)+x=712456xx+(xx)x=2124573x+x+2(xx)=7minf=一叮一/J一叮OX0 x71245例2：minf=-x+2x一3xTOC o 1-5 h z123x+x+x7123x一x+x21233x+x+2x=7123x,x0,x無約束123其中2.2線性規(guī)劃的圖解法maxf=2maxf=2x+3x12x+2x8124x1614x012目標函數(shù)約束條件如上述例1

19、目標函數(shù)約束條件222圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向;平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。223線性規(guī)劃問題求解的幾種可能結(jié)果(A)唯一最優(yōu)解;(B)無窮多最優(yōu)解;(A)(B)(A)(B)(C)無界解；(D)無可行解。其可行域為空集224由圖解法得到的啟示可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。2.3線性規(guī)劃解的性質(zhì)2.3.1線性規(guī)劃解的概念標準型minfCTXs.t.A

20、XbG）X，0其中AL,設(shè)ra）m，即約束方程組AXb中沒有多余的方程，jmxn則應有n,m。如果用P表示矩陣A的第j列，則AXb也可記為j工xPb。jjj1基：若B=（P,P，,P）可逆，則B稱為線性規(guī)劃式G）的基。12mP（j1,2,m）稱為基向量。有時也稱向量組P,P,P為G的基，j12m而將B稱為基矩陣（或稱基陣）基（描述二）：若B是矩陣A中mXm階非奇異子矩陣（囘工0，即可逆），則B可逆），則B是線性規(guī)劃問題的一個基矩陣或稱基陣）。不妨設(shè)：TOC o 1-5 h z(a,.,aBB(P1,.,P)a,.,am1mmP,j1,2,m基向量其中x,j1,2,m基變量x,jj+1,n-非基

21、變量j求解AXb，貝【Jr、(c、aa111r、(c、aa111mx+.+x1m,a丿m1、a丿mm(b)1(a1m+1lb丿mx-m+1(a1nw丿mm+1w丿mn基變量X(x,X,x，令Xm+1Xm+2Xn0B12m可求出：X(b,b,b,0,0,0)12mnn解為X=XB解為X=XBXN。這樣AX二b變?yōu)閄BXN=BX+NX=bBN特別地,若B=(P,P，P)N=(P，,P)，則A=(B,N)，相應地將X特別地,m,m,1nnnnnB-ib0AX=AX=(B,N:B-ib0nnnn右令B-ib=(x,x,x，則,0,0,0,x，x12m是上述標準型線性規(guī)劃問題的一個基本解?；窘猓簩τ诨?/p>

22、b,令非基變量為零，求得滿足AX=b的解，稱為B對應的基本解（或稱基解）。基本可行解：非負的基本解X稱為基本可行解。可行基：對應基本可行解的基稱為可行基。最優(yōu)解：使f=CX達到最小值的可行解稱為最優(yōu)解。線性規(guī)劃解的關(guān)系圖nnnn由于A是mn矩陣，故線性規(guī)劃問題的不同的基最多有Cm個。而一個基最多對應一個基本可行解，故此線性規(guī)劃問題最多有Cm個n基本可行解。上述分析可知，基本可行解中非零分量的個數(shù)不會超過m，若基本可行解中非零分量的個數(shù)恰為m，稱此基本可行解為非退化的基本可行解，否則稱為退化的基本可行解。若一個線性規(guī)劃的所有基本可行解都是非退化的，稱此線性規(guī)劃是非退化的。例：求基陣、基本可行解。

23、minz一2x-3x+0 x+0 x+0 xTOC o 1-5 h z12345x+2x8124x+x16，144x+x1225x,x,x,x,x01234512100A=40010，A的秩是3。、04001丿根據(jù)定義100、根據(jù)定義B=01011001丿是一個基陣，它對應的基本解為X=(0,0,8,16,12顯然它是基本可行解。另根據(jù)定義200、另根據(jù)定義B=01021401丿也是一個基陣，它對應的基本解為X也是一個基陣，它對應的基本解為X=(0,4,0,16,-4它不是基本可行解。2.3.2線性規(guī)劃問題的幾何意義2.3.2.1基本概念一、凸集設(shè)K是n維歐式空間的一點集，對VXG),K，XG

24、),K連線上的一切點aXG+(1-a)x(2),K，0a1則k為凸集。二、頂點若k是凸集，X,K；若X不能用不同的兩點XG),K，XG),K的線性組合表示為：aXG+G-a)XG),K，0a1則X為頂點。三、凸組合設(shè)XG,.,XQ是n維向量空間中的k個點，若存在卩，,卩，且1k0卩1,i=1,k，工P=1，使ii=1X二卩XG+PXc)+卩X(k)12k則X為XG),X(k)的凸組合。2322基本定理定理1：若線性規(guī)劃問題存在可行域，則其可行域：D二&/AX二b,X，0是凸集。證明：設(shè)XGwD，XG）wD，XGhXG），則有AXG=b,XG,0，AXG）=b,XG,0令X為XG）和xG）連線上

25、的任意一點貝lj:X二aXG+（1-a）xG（0a1）（只要驗證X在D中即可!）顯然，X,0，將X代入約束條件，有AX=A（aX（1）+（1-a）X）=aAX（1）+（1a）AX（2）=ab+（1a）b=b因此，XeD，D是凸集。引理1：可行解X為基本可行解X的正分量（非零分量）在A中所對應的列向量線性無關(guān)。定理2：線性規(guī)劃問題的基本可行解X對應于可行域D的頂點。定理3：若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。2.3.2.3幾點結(jié)論線性規(guī)劃問題的可行域D=x/AX=b，X,0是凸集。基本可行解與可行域的頂點一一對應。若線性規(guī)劃有最優(yōu)解，則必在其可行域的頂點處取得

26、。528可彳亍城為凸集528可彳亍城為凸集貝標禹數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生4七0如果已知一個可行基B是一個m階單位矩陣，不妨設(shè)B剛好位于矩陣A的前m列。這是，約束方程axb的形式為：x+axaxb1l,m+lm+11nn10,(i1,2,m)。此時，與B相對應的基本可行解是iX0(b，,b,0,0。1m設(shè)A(I,N)，I(P,P,P)為單位矩陣，N(P,P,P)TOC o 1-5 h z12mm+1m+2nX(x,x，,xI12mX(x,x,x)TNm+1m+2nC(c,c,c)TI12mC(c,c,c)TNm+1m+2n則有CCICN于是，線性規(guī)劃問題可記為minf(X)=Ct

27、X+CtXIINN0,X0IN顯然，X0二是此線性規(guī)劃的一個基本可行解。顯然，X0二數(shù)值為f(X0)=(CtCt)b由IX由IX+NX=b可得,INX二b-NXINf(X)=Ct(b-NX)+CtXf(X)=Ct(b-NX)+CtXINNNINN由于X0，故當CtNCtfOo)NIN即此時fQ0)是線性規(guī)劃的最優(yōu)值。定理1(最優(yōu)解判別準則):對于上述線性規(guī)劃問題，當CtN-CT0IN時，X時，X0二此線性規(guī)劃的最優(yōu)解。用分量的形式來表示，令=Ct=CtPcIjj(j=m+1,n)則當0時，x0=0,是其最優(yōu)解。又當j=I,.,m時，若令=CtPcjIjj則因P=(0,0,1,0,.,0，1是第

28、j個分量，所以=c-c=0jjjj因此稱(j=1,n)為P或x的判別數(shù)，由以上討論可知，基向量或基jjj變量的判別數(shù)必定為零。可見，定理1又可敘述為:定理I：若線性規(guī)劃各判別數(shù)03（j，J.,4）j解：1-2解：1-20151001為基，即1001為基，即x,x13為基變量，則X0，（4,0,5,0）T是與I對應的基本Ct，Ct，G,2,3,-2），Ct，（1,3）。貝【J判別數(shù)為0（j，1,-,4）j可行解。又可見，因此，X0，（4,0,5,0是其最優(yōu)解。定理2：若線性規(guī)劃的某個判別數(shù)0，而相應的列向量P0,X0BN由B可逆，則可得X，B-ib-B-1NXBN于是Ct-ib-B-iNX)+C

29、tXBNNNBN)T-CTB-iNXNBN，CtB-ib-BN)T-CTB-iNXNBNBBNNN，CtB-ib+B若B-1b0，則B-ib是一個基本可行解。如果進一步，CT如果進一步，CT-CTB-iN0NB或CtB-iN-CtCtB-ibBB-ib為式(*)的最優(yōu)解。綜上，可將CtB-iN-Ct非正作為式(*)的最優(yōu)解的判別條件。BN又由于CTB-iA-CTB，CtB-iB,N)-(C,C，CtB-iB,CtB-iN)-(C,C，Ct,CtCTB-iA-CTBBB)BN，QCtB-iN-Ct丿BN所以，CtB一1NCt0與CtB-1A-Ct0是完全等價的。BNB令CtB-iPc(j1,n)

30、(*)jBjj仍稱為P或x的判別數(shù)。jjj顯然，前面定義的判別數(shù)是式(*)中B=I時的一種特殊情形。2、換基運算所謂換基運算就是從一個基本可行解迭代出一個新的基本可行解的方法。由于只考慮基本可行解之間的迭代問題，暫不涉及目標函數(shù)，這里先考慮以下這一組特殊的約束。xaxaxb11,m1m+11nn1VxVx0jmnnmj1,n)用矩陣表示，即A=G,N)，b(b,b，,b12m于是X=(b,b，,b,0,012m是一個基本可行解?，F(xiàn)在從X出發(fā)，尋找新的基本可行解。對于矩陣1a，a，ab1,m11l1n1(Ab)=1a，abklknk1a，a，ab1m,m0，則X、就是一個基本可行解。而X0就是b

31、0。于是,ibb-,b0kakkl可知，必有akl0時，為使b0，應有ilb0ibb()aailkl故當a符合條件klmin丄/a0(探)aki逶ma江此時，可取a為主元對(Ab)進行換基運算，得到新基:ilI=(P，,P,P,P，,P)1k-1lk+1m及新的基本可行解：X=(b0bb、00b00)1k，1k+1mk換基運算的步驟：(1)在進基列P中按式(探探)選取主元a；lkl按式徑)按式徑)計算b、kb，得到上述所示的新的基本可行解。i舉例：給定約束條件x+3x一x+3x=21456x+2x一2x+x=12456x一2x一x+2x=33/450 x0j=1,6丿j顯然，X0=(2,l,3

32、,0,0,0是一個初始基本可行解。顯然，如果要將P引入基中41003-132（Ab）=0102-211001-2-123則主元a應滿足k4TOC o 1-5 h zbb/0.211b匚=min/a“0=min,=-aIai4I13212ak4i424于是（Ab）中的元a=2就是主元。按照式（探）作換基運算，得到24新的基本可行解是新的基本可行解是11-TX1=2,0,4,2,0,0”130023丄一2220101一1112220110一334同理可將P引入基中，則主元a應滿足TOC o 1-5 h z6k6bb/0212baIai6I131J3ak6i616則a=3為主元。以a為主元對（Ab）

33、按照式（探）作換基運算，得到16161313一1-3一2-3001-11-33521010-3301-4-10533新的基本可行解為應當注意：并不是A的任何一列都可以引入基中。如上例中p就5不能入基，因為P0導致b二佇0，故在確定進基列的時候，應保證該列至少有一個正分量。3、進基列的選擇以上換基運算分析可知，對進基列的要求是至少有一個正分量。然而滿足這個條件的列向量可能很多。那么，挑選哪一個作為進基列更好呢？這需要與目標函數(shù)聯(lián)系起來。如果在上例的約束條件上加上一個目標函數(shù)：f(X)=x一2x3x一4xx于是12346于是CT二U,-則在X則在X0、X1和X2處相應的目標函數(shù)值為fGo)=CtX

34、0二1“2(-2“13“3二9f&1)=CtX1=1“1+3“4+C4“1=21222f(X2丿=CtX2=C2)x1+3x5+1“-=5333同Xo相比，X1處目標函數(shù)值上升，X2處目標函數(shù)值下降，則此時應該選取P作進基列。然而，對于一般的線性規(guī)劃來說，選擇什么樣的6列作進基列可以使目標函數(shù)值下降呢？定理3：設(shè)線性規(guī)劃minf（X）=CtX+CtXs.t.BX+NX=bX0,X0滿足以下條件：(1)基本可行解X(1)基本可行解X0=B-ib0非退化；P的判斷數(shù)0；(3)p的分量中至少有一個為正。則用p作進基列將得到使目標函數(shù)值下降的基本可行解。定理3的證明詳見傅英定等主編最優(yōu)化理論與方法P6

35、0-P61)。但一般的線性規(guī)劃符合進基列條件的列通常不止一個，那么，選取哪一列作進基列最好呢？由于由于所以，當最大時，目標函數(shù)值下降最快?？梢娕c進基列的選擇有關(guān)。如果對每一個可供選擇的進基列p都計算一次，再比較各個jjjl的大小，則當可供選擇的進基列數(shù)目較大時，相應的計算量也較大。所以，通常情況下，若有多個列滿足進基列的條件，則選取判別數(shù)最大的那一列作進基列，這時目標函數(shù)值獲得較大的下降。舉例：對于線性規(guī)劃mins.t.fX)=-2x-x12x+x+x123-x+x+x1246x+2x+x=5=1=210(j=1,5)111005(Ab)=-1101016200121=(P1,P2,P3,P4

36、,P5,取I=(P,P,P)為基，貝U345=CtP一c=0一c=20I111=CtP一c=0一c=10I222由于P、P均有正分量，故P、P都可作進基列但,故選取P為1212121將使目標函數(shù)值得到較大下降。2.4.3單純形算法1、初始單純形表的建立對于線性規(guī)劃minf(X)=CtX+CtXBBNNs.tBX+NX=bBNX0,X0BN其中B是可逆矩陣，可作為這個線性規(guī)劃的基，并建立以下矩陣:B-1AB-1bCtB-1A-CCtB-1bBB由上述討論可知：x0=B-1b是線性規(guī)劃的一個基本可行解。0CtB-1A-C的各分量就是判別數(shù)。BCtB-1b=f(X0)是對應于基本可行解X0的目標函數(shù)

37、值。B因此，矩陣式()記錄著我們所關(guān)心的關(guān)于線性規(guī)劃的全部信息。我們將這個矩陣稱為線性規(guī)劃的初始單純形表。特別地，若基BI是單位矩陣，則初始單純形表變?yōu)?)CtA-CCTbII如果將A用(in)來表示，則基向量的判斷數(shù)為零，且將目標函數(shù)值CTbI用f來表示，則式()又可記為0_INb_0tatfN0其中OT(0,0)aT(a,a)N(m+l、nlmffX0CTbX0(b,b,0,lm此時，線性規(guī)劃對應的初始單純形表的一般形式即為下表所示。P1PkPmPm+1plpnb1aaab1,m11l1n11aaabk,m1klknk1aaabm,m1k,m1k,nm000aaafm1ln0初始單純形表記

38、錄著以下信息：(l)等式約束AX=b的有關(guān)數(shù)據(jù)；各列向量的判別數(shù)a(j1,n)；初始基本可行解X0，(b，,b,0,0；1m對應于X0的目標函數(shù)值f。0對于基B=I的線性規(guī)劃，建立初始單純形表需要計算非基變量的判別數(shù)c,，以及相應的目標函數(shù)值f。m1n02、換基運算后的新單純形表在初始單純形表上對線性規(guī)劃作換基運算。首先確定主元a，然klaGaGkjcjjalkl注意，此時c，ckic，0)llalklbf二f亠c0alkl于是，初始單純形表變?yōu)樾聠渭冃伪砣缦聢D所示P1PkPmPm1P/Pnb1aa0ab.1k1,m+1:1n1aa1abkkk,m+1knka1a0abmkm,m+1mnm0c

39、0c0cfkm+1n上表中：(1)c是新單純形表中P判別數(shù)；jj(2)f是新基本可行解Xi所對應的目標函數(shù)值。其中Xi=1b0bb00b00)1k1k1mk在新單純形表中，(1)若c0j=1,6丿j解：取I=P,p,p）為初始基。則146Xo二（7,0,0,12,0,10）t為初始基本可行集。Ct二（0,0,0）I由q=CtPc計算出：=-1,二3，a=2jIjj235a、a、a為基變量所對應的判別數(shù)，必有a=q=q=0146146f=CTb=00I因此，初始單純形表如下所示。P1P2P3P4P5P6b13-102070-2Q100120-43081100-130-200在非零判別數(shù)中，只有a

40、=30，且P有正分量，故應將P引入基底。TOC o 1-5 h z333由性=罰仝/a。=殳巴!=12，可知，應選a=4為主元作換基a1i6a13JI43J423k3il運算得到如下新單純形表。P1P2P3P4P5P6b12/501/420100-1/211/40030-5/20-3/481101/20-3/4-20-9上表中只有,=120，且P有正分量，故應以a=25為主元作換基222125運算得到如下新單純形表。PPPPPPb1234562/5101/104/5041/5013/102/505100-1/210111-1/500-4/5-12/50-11上表中各判別數(shù),0j，1,2,n,n

41、+1,n+mj求解上述線性規(guī)劃問題就是從最小化角度迫使人工變量取零，以達到求原問題最優(yōu)解的目的。此時X(o)=(O,O,b，b可作為一個基本可1m行解，對上述線性規(guī)劃問題可以用單純形方法求解。容易理解，若X*，C,x*)為輔助線性規(guī)劃問題的最優(yōu)解，當1n+m*n+1-，x*，0日寸，n+mX*，C,x*)即為原問題的最優(yōu)解；否則，原問1n題無可行解。舉例：求解線性規(guī)劃問題f一31+x2+x3x一2x+x3st0123解：(1)加入松弛變量和剩余變量進行標準化,加入人工變量構(gòu)造初始可行基。x一2x+x+x，111234一4x+x+2xx+x，312356一2x+x+x，113x0(j，1,2,7

42、)7minf，-3x+x+x+0 x+0 x+Mx+Mx1234567j(2)用單純形法求解300-M-MbXiX2x3兀1耘耘X-g11311-21-412亠11o0-100001001113/21f03-6MM-13M-10-M00表初始單純形表)其最優(yōu)解為x4,x1,x9，目標函數(shù)值f-2。123(3)求解結(jié)果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量，則無可行解；否則，有最優(yōu)解。41兩階段法由于在大M法中引入一個很大的正數(shù)，可能產(chǎn)生較大的舍入誤差，且在計算機上處理困難，故在實際問題中常用兩階段法。所謂兩階段法，就是將線性規(guī)劃問題的求解過程分成兩階段，即先求初始基，再求解。兩階段法與大M法

43、的不同之處在于其輔助問題中的目標函數(shù)僅為各人工變量之和，即輔助問題minfminfxLKxn+ii=1工ax+x=bi=1,2,ms.t.jjn+ij=1x0j=1,2,n,n+1,n+mij當輔助線性規(guī)劃問題的最優(yōu)解f=0時，若X*=(*,X*)為其最優(yōu)TOC o 1-5 h z1n+m解，則當X*=X*=0時，X*=C*,X*）必為原問題的最優(yōu)解；否n+1n+m1n第一階段：構(gòu)造如下的線性規(guī)劃問題=b1第一階段：構(gòu)造如下的線性規(guī)劃問題=b1=b2何棚函數(shù)僅含人齊#晟憂解的tI標陽敕伯平為嘰IU中杏f步的人丄甸問虺?？捎喰浮癕inf=x+x+.+xn+1n+2n+max+ax+ax+x111

44、1221nnn+1ax+ax+ax+x2112222nnn+2s.t.+x=bn+mmax+x=bn+mmm11m22mnnx,x，,x,x.,x012nn+1,n+m用單純形法求解上述問題，若f=0，進入第二階段；否則，原問題無可行解。第二階段：去掉人工變量，還原目標函數(shù)系數(shù)，做出初始單純形表,然后利用單純形法求解即可(下面舉例說明，仍用大M法的例)。舉例：求解線性規(guī)劃問題x一2x+x0123解：(1)構(gòu)造第一階段問題并求解。x一2xx一2x+x+x=111234一4x+x+2x一x+x=312356一2x+x+x=11/3x0j=12.,7)7j利用單純形法求解G00U0-1二1bxiXj

45、1123111-4-2-2101ft00-100100ni113/21廠4-610-100表100000-1-1XBbXiXj召愍x7x4121x211x3/I30-2010001100-2-10210-5-2I4fo00000-1-1衣頭最終單純形表表3中不含人工變量且f0,轉(zhuǎn)入第二階段。表4：去掉人工變量后的初始單純形表表5：最終單純形表單純形法計算中的幾個問題：1、目標函數(shù)極小化時解的最優(yōu)性判斷只需用檢驗數(shù),0作為最優(yōu)性的標志。j2、無可行解的判斷當求解結(jié)果出現(xiàn)所有,0時，如基變量仍含有非零的人工變量j（兩階段法求解時第一階段目標函數(shù)值不等于0）,則原線性規(guī)劃問題無可行解。單純形法有三種

46、形式：方程組形式；表格形式；矩陣形式。一、方程組形式的單純形法1、思路由一個基本可行解轉(zhuǎn)化為另一個基本可行解。例:minf-3x-5x12s.t.x+x=813minf-3x-5x12s.t.x+x=8132x+x=120V1234512f+3x+5x=012x+x=8132x+x=120v12345Y1=30F2=5aof+1V1+Sr2+0-v3+0.t4血o81236-一華曲tl）當前基：in冷排列陣目標方程中:切戛至呈的系議F尸Df囲|M寸jJHF.sijgprihi-IjfJ十F一HJa-初始基本可廳解樣列臨毎行每列有且僅有一于元素*1-其余元麥全為。的方眸Xft(0?0.8,12,

47、36)tz0-0當前解Xo非憂匚LbXfl轉(zhuǎn)化沖另-個某本呵令解X1亠思路匕LDh中的一個韭基變量進基去替換原來的一個基菠量（離基o-00-s-Ml=12+x5-36進覽最大檢驗數(shù)規(guī)則）:庭正檢藝赴申選擇養(yǎng)丸的進基匕皿瑞/j|/j：0-rk瓦進Mmax3,5-5-rj也進卑蠱基葢小比值規(guī)則）:屯菟min,122,36.4-6耳=iniii12.2,364-6悶仍為非皐變簾，具怕為九由（D有12斗為韶基愛呂X1=(0,6,&0,12)T2、單純形法的幾何意義3、單純形法的計算步驟5*5*確鬼主元5*5*確鬼主元maxZjIZj0=yk確運進基變量耳和主列去：.再按最小比值規(guī)則minI站ikA0=

48、確定主元叭上刖時也就確定第丁行的基變就芯離基.6以紬“為主元對當前表格送行-次換基運算.得到一牛新單純形表，返3，送代步陳二、單純形表從上述單純形法迭代原理中可知，每一次迭代計算只要表示出當前的約束方程組及目標函數(shù)即可。按定義，化為當前基對應的典式。fcxcxcxcx011mmm+1m+1nnx+ax+axb11m+1m+11nn1，x+ax+axb22m+1m+12nn2x+ax+axbmmm+1m+1mnnm例2：用單純形表求解LP問題解：化標準型maxf2x+x125x1526x+2x2412x+x0V12minf-2x-x+0 x+0 x+0 x123455x+x15236x+2x+x

49、240表1：列初始單純形表（單位矩陣對應的變量為基變量）XbXX500X45100500I6正檢驗數(shù)中最大者對應的列為主列XbXX500X45100500I6正檢驗數(shù)中最大者對應的列為主列主元化為1主列單位向量尤.換出X換入表2：換基（初等行變換，主列化為單位向量，主元為1）表3：換基（初等行變換，主列化為單位向量，主元為1）步驟：1、初始基可行解的確定觀察法：直接觀察得到初始可行基。丄W約束條件：加入松弛變量即形成可行基。上約束條件：加入非負人工變量。2、最優(yōu)性檢驗與解的判別最優(yōu)解判別定理：若x(o)，C,b,b,0,0,0)為基可行解，且全部12m0,j，m+1,n，則X(0)為最優(yōu)解。i

50、唯一最優(yōu)解判別定理：若所有丫0，并且對應的m+km+k非基變量的系數(shù)a0,i，1,2,m，則具有無界解。i,m+k令x，,x為基變量，x,x為非基變量，則X(0)，(0,0,b,b)是n+1n+m1n1m一初始基可行解。5、對偶線性規(guī)劃5.1問題提出假設(shè)某工廠有m種設(shè)備：B、B、B，一年內(nèi)各設(shè)備的生產(chǎn)能力TOC o 1-5 h z12m(有效臺時數(shù))為b、b、b。利用這些設(shè)備可以加工n種產(chǎn)品：12mA、A、A，單位產(chǎn)品的利潤分別為c、c、c。第j種產(chǎn)品需要在第i12n12n種設(shè)備上加工的臺時數(shù)為a。問在設(shè)備能力允許的條件下怎樣安排生產(chǎn)計劃，使全年總收入最多？設(shè)x,x,x為各產(chǎn)品的計劃年產(chǎn)量，s

51、為全年總收入，則該問題12n的數(shù)學模型為maxS=工cxjjj=1s.t.工ax，bi=1,2,，m(P)ijjij=1x0j=1,2,nj換個角度(從經(jīng)濟問題角度)：假設(shè)工廠將所有的設(shè)備用于出租，需要給各種設(shè)備制定出租價格。定價原則有兩條：一是出租后得到的單位利潤不得少于直接生產(chǎn)時的收入；二是出租價格盡量的低，以利于市場競爭。設(shè)第i種設(shè)備B的單位臺時的出租價格為y，全年總收入為,ii則得到另一個線性規(guī)劃問題的數(shù)學模型為min=byiii=1s.t.aycj=1,2,n(D)ijiji=1y0i=1,2,mi如果將式(P)的線性規(guī)劃問題稱作原問題，則式(D)為其對偶問題。5.2對稱形式的對偶線

52、性規(guī)劃定義(從數(shù)學問題角度)：線性規(guī)劃問題(P)maxS=工cxjjj=1s.t工ax，bi=1,2,mijjij=1x0j=1,2,nj為對稱形式的線性規(guī)劃問題，其對偶規(guī)劃(D)定義為minW=,byiii=1s.t.,aycj=1,2,，njiji=1y0i=1,2,mi原始線性規(guī)劃atnixs=/可以看出，原2、藝切丸切，f=J,2,-,w/=:始規(guī)劃與對偶規(guī)劃是同一組數(shù)據(jù)叫工0,7=1,231243x+x+x+x61234x+x234x+x2x0j=1,4）ij_120138311166b=C=001123101026A=令W=(y1，與與y4)T，則其對偶線性規(guī)劃為maxbrWs.t

53、.AtWCmaxg（W）2y1y+3y122y+ys.ts.t.+y33.0i由對稱形式的線性規(guī)劃問題構(gòu)造其對偶問題的一般規(guī)則是:原規(guī)劃問題是求目標函數(shù)最大，其約束條件統(tǒng)一是“W”則其對偶問題是目標函數(shù)最小，其約束條件統(tǒng)一為“上”原規(guī)劃問題中與b相應的每個約束條件，對應著對偶問題的一i個決策變量y；i原規(guī)劃問題的一個決策變量x，對應著對偶問題的一個約束條j件ay+ayHFayc1j12j2mjmj5.3非對稱形式的對偶線性規(guī)劃在討論線性規(guī)劃的標準形式時，需將不等式約束都轉(zhuǎn)化為等式約束，而得到下面形式的線性規(guī)劃minCTXAXb(P)s.t.,X0然而線性規(guī)劃(P)的對偶規(guī)劃應該是什么形式呢？主

54、要思想：將非對稱形式的線性規(guī)劃問題轉(zhuǎn)化為對稱形式的線性規(guī)劃問題，再寫出其對偶問題，也可由其對應關(guān)系表直接寫出。分析思路：線性規(guī)劃AXb等價于AXbAXb則線性規(guī)劃(P)可變?yōu)開A-X_A-X-b-A-bminCTXs.t.(P)因此式(P”)的對偶規(guī)劃為_b-TW1_-bW2maxA-ATW1W2W1_W20C(P)令W*=A-ATW1W2W1_W20C(P)令W*=W1-W2,則式(P)變?yōu)閎TW*(D)s.t.AtW*C由W*的表達式可知，這里不能再要求W*0。這就是式(P)的對偶規(guī)劃。舉例：寫出下面線性規(guī)劃的對偶規(guī)劃mins.t.f(X)=12x+8x+16x+12x12342x+x+x

55、=21232x+2x+4x=31x0j解：-2140-2A=b=22043Ct=(12,8,16,12)令W=(y,y12，則得到原規(guī)劃的對偶規(guī)劃為maxs.t.g)=2y+3y122y+2y1212y+2y8,124y1614y122通常，非對稱形式的線性規(guī)劃問題轉(zhuǎn)化為對稱形式的線性規(guī)劃問題的步驟如下：第1步目標函數(shù)：對最大化問題轉(zhuǎn)化為最小化問題，即;maxz=maxz=excx11nnmin一z=-exex11nn第2步約束條件：對“”不等式方程兩邊同乘以“-1”；對“=”等式方程ax+axax=bi11i22inn可寫成兩個“”式，即axax+axbi11i22inn-ax-axax一b

56、i11i22inn第3步?jīng)Q策變量：若x0，可令x=-x，使x0；若x無約束,jjjjj令x=x-x，使x,x0。jjjjj舉例：試求下述線性規(guī)劃問題的對偶問題minZ=2x3x-5xxTOC o 1-5 h z1234xx-3xx51234s.t.2x2x-xs.t.134xxx=6234x0；x,x0；x無約束1234解：設(shè)對應于三個約束條件的對偶變量分別為W=(y,y,y，按照原123問題與對偶問題的對應關(guān)系，則其對偶問題為maxW=5y4y6y123y2y212yy313-3y2yy-5123yy+y=1123y0；y0；y無約束1235.4對偶定理上節(jié)著重討論了怎樣從一個已知的線性規(guī)劃

57、寫出其對偶規(guī)劃。原規(guī)劃與對偶規(guī)劃的最優(yōu)解之間，很自然地有著密切的關(guān)系。本節(jié)將主要討論對稱形式的對偶定理。設(shè)線性規(guī)劃min(LP)min(LP),s.t.AXbX0其可行集為R=x/AXb,Xo，以及其對偶規(guī)劃PmaxbTW(DP(DP),s.t.AtWCW0及其可行集為R二W/AtWC,WO。D定理1VXeR,WeR，必有PDCTXbTW證明：由于VXeR,WeR，貝UDCtXAtW)XWT0,Y0匕，0t1YminX0,Y0設(shè)x0為上式的一個最優(yōu)基本可行解，B是X0所對應的最優(yōu)基，X0是BXo中基變量所組成的向量，貝U由最優(yōu)解判別準則可知令W0，(CtB-1(A,-1Qt,0t)BCtB-J

58、，則由上式可知BWo)(A,-1)Ct,0t)即AtW0c,W00故W0是(DP)的可行解。由因為bTWo由因為bTWo，bTB，CtB-ib，CtXo，CtXoBBB因此由定理2的推論可知，W0是(DP)的最優(yōu)解。此時，CtX0與bTW0分別是(LP)與(DP)的最優(yōu)值，即minCtminCtXo，maxbTW證畢兩個互為對偶的線性規(guī)劃的解之間關(guān)系：兩個規(guī)劃都有可行解(或都有可行解)兩個規(guī)劃都沒有最優(yōu)解(或都沒有可行解)；一個有可行解，但目標函數(shù)在可行集上無界，則另一個沒有可行解。從上述證明還可以看出，如果B是(LP)的最優(yōu)基，則CtB一1)就是B(DP)的最優(yōu)解。這樣一來就可以直接從(LP)的最終單純形表中求得(DP)的最優(yōu)解。下面以對稱形式為例，討論如何直接地從原規(guī)劃的最終單純形表求其對偶規(guī)劃的最優(yōu)解的問題。定理4設(shè)X與W分別為對稱形式的原規(guī)劃(LP)與對偶規(guī)劃(DP)的可行解，則X與W同時也分別是(LP)與(