TPSHUAI1最優化理論與算法TPSHUAI1最優化理論與算法TPSHUAI2提綱1.

線性規劃

對偶定理2.

非線性規劃

K-K-T定理3.組合最優化

算法設計技巧使用教材：最優化理論與算法陳寶林參考書：數學規劃黃紅選，韓繼業

清華大學出版社TPSHUAI2提綱1.線性規劃對偶定理使用教材：TPSHUAI3其他參考書目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.TPSHUAI3其他參考書目NonlinearProgrTPSHUAI4LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.運籌學基礎手冊徐光輝、劉彥佩、程侃科學出版社，1999組合最優化算法和復雜性CombinatorialOptimization

蔡茂誠、劉振宏

AlgorithmsandComplexity清華大學出版社，1988

Printice-HallInc.,1982/1998

其他參考書目TPSHUAI4LinearProgramminganTPSHUAI51,緒論----學科概述最優化是從所有可能的方案中選擇最合理的一種方案,以達到最佳目標的科學.達到最佳目標的方案是最優方案,尋找最優方案的方法----最優化方法(算法)這種方法的數學理論即為最優化理論.是運籌學的方法論之一.是其重要組成部分.運籌學的“三個代表”模型理論算法最優化首先是一種理念,其次才是一種方法.TPSHUAI51,緒論----學科概述最優化是從所有可能TPSHUAI6緒論---運籌學（OperationsResearch-OR）運籌學方法隨機過程方法統計學方法最優化/數學規劃方法連續優化：線性規劃、非線性規劃、非光滑優化、全局優化、變分法、二次規劃、分式規劃等離散優化：組合優化、網絡優化、整數規劃等幾何規劃動態規劃不確定規劃：隨機規劃、模糊規劃等多目標規劃對策論等統計決策理論馬氏過程排隊論更新理論仿真方法可靠性理論等回歸分析群分析模式識別實驗設計因子分析等TPSHUAI6緒論---運籌學（OperationsRTPSHUAI7優化樹TPSHUAI7優化樹TPSHUAI8最優化的發展歷程費馬:1638;牛頓,1670歐拉,1755Minf(x1x2···xn)

f(x)=0TPSHUAI8最優化的發展歷程費馬:1638;牛頓,16TPSHUAI9歐拉，拉格朗日：無窮維問題，變分學柯西：最早應用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,mTPSHUAI9歐拉，拉格朗日：無窮維問題，變分學拉格朗日TPSHUAI101930年代，康托諾維奇：線性規劃1940年代，Dantzig：單純形方法，馮諾依曼：對策論1950年代，Bellman：動態規劃，最優性原理；

KKT條件；1960年代：Zoutendijk,Rosen,Carroll,etc.非線性規劃算法，Duffin，Zener等幾何規劃，Gomory，整數規劃,Dantzig等隨機規劃

6-70年代：Cook等復雜性理論，組合優化迅速發展

電子計算機----------最優化TPSHUAI101930年代，康托諾維奇：線性規劃電子計TPSHUAI11最優化應用舉例具有廣泛的實用性運輸問題，車輛調度，員工安排，空運控制等工程設計，結構設計等資源分配，生產計劃等通信：光網絡、無線網絡，adhoc等.制造業：鋼鐵生產，車間調度等醫藥生產，化工處理等電子工程，集成電路VLSIetc.排版（TEX,Latex,etc.）TPSHUAI11最優化應用舉例具有廣泛的實用性TPSHUAI121.

食譜問題我每天要求一定量的兩種維生素，Vc和Vb。假設這些維生素可以分別從牛奶和雞蛋中得到。維生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250單價(US$)32.5需要確定每天喝奶和吃蛋的量，目標以便以最低可能的花費購買這些食物，而滿足最低限度的維生素需求量。TPSHUAI121.食譜問題我每天要求一定量的兩種維生TPSHUAI131.

食譜問題（續）令x表示要買的奶的量，y為要買的蛋的量。食譜問題可以寫成如下的數學形式：運籌學工作者參與建立關于何時出現最小費用（或者最大利潤）的排序，或者計劃，早期被標示為programs。求最優安排或計劃的問題，稱作programming問題。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.極小化目標函數可行區域（單純形）可行解TPSHUAI131.食譜問題（續）令x表示要買的奶的量TPSHUAI142

運輸問題設某種物資有m個產地A1,A2,…Am,各產地的產量是a1,a2,…,am;有n個銷地B1,B2,…,Bn.各銷地的銷量是b1,b2,…,bn.假定從產地Ai(i=1,2,…,m)到銷地Bj(j=1,2,…,n)運輸單位物品的運價是cij問怎樣調運這些物品才能使總運費最小？如果運輸問題的總產量等于總銷量，即有則稱該運輸問題為產銷平衡問題；反之，稱產銷不平衡問題。TPSHUAI142運輸問題設某種物資有m個產地A1,ATPSHUAI15令xij表示由產地Ai運往銷地Bj的物品數量，則產銷平衡問題的數學模型為：2

運輸問題（續）TPSHUAI15令xij表示由產地Ai運往銷地Bj的物品TPSHUAI16以價格qi

購買了si份股票i,i=1,2,…,n股票i的現價是pi你預期一年后股票的價格為ri

在出售股票時需要支付的稅金=資本收益×30%扣除稅金后，你的現金仍然比購買股票前增多支付1%的交易費用例如：將原先以每股30元的價格買入1000股股票，以每股50元的價格出售，則凈現金為：50×1000-0.3(50-30)1000-0.1×50×1000=390003

稅下投資問題TPSHUAI16以價格qi購買了si份股票i,i=1,TPSHUAI17我們的目標是要使預期收益最大。Xi：當前拋出股票i的數量。3

稅下投資問題（續）TPSHUAI17我們的目標是要使預期收益最大。3稅下投TPSHUAI184

選址問題（1）實例:一組潛在位置（地址）,一組顧客集合及相應的利潤和費用數據；解:

設施開放(使用)的數目，他們的位置，以及顧客

被哪個設施服務的具體安排方案；目標：總的利潤最大化。數據與約束J={1,2,…,n}:放置設施的可能的潛在位置集合I={1,2,…,m}:顧客集合,其要求的服務需要某設施所提供.TPSHUAI184選址問題（1）實例:一組潛在位置（地TPSHUAI194

選址問題（2）TPSHUAI194選址問題（2）TPSHUAI204選址問題（3）TPSHUAI204選址問題（3）TPSHUAI215負載平衡(1)實例:網絡G(V,E)

及一組m

個數的集合{s,d>0}，表示

連接源點

s與匯點d

之間的流量解:{s,d>0}的一組路由,即G(V,E)

中m

條s

與

d間的路,

表示連接s與d

的負載流量的路徑。目標:極小化網絡負載TPSHUAI215負載平衡(1)實例:網絡G(V,E)TPSHUAI225

負載平衡(2)TPSHUAI225負載平衡(2)TPSHUAI236.結構設計問題兩桿桁架的最優設計問題。由兩根空心圓桿組成對稱的兩桿桁架，其頂點承受負載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性模量為E，屈吸強度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。TPSHUAI236.結構設計問題兩桿桁架的最優設計問題。TPSHUAI24

受力分析圖圓桿截面圖桁桿示意圖6.結構設計問題TPSHUAI24受力分TPSHUAI256.結構設計問題此應力要求小于材料的屈吸極限，即解：桁桿的截面積為：桁桿的總重量為：負載2p在每個桿上的分力為：于是桿截面的應力為：TPSHUAI256.結構設計問題此應力要求小于材料的屈吸

圓桿中應力小于等于壓桿穩定的臨界應力。由材料力學知：壓桿穩定的臨界應力為

由此得穩定約束：6.結構設計問題圓桿中應力小于等于壓桿穩定的臨界應力。由此得穩定約束

另外還要考慮到設計變量d和h有界。從而得到兩桿桁架最優設計問題的數學模型：6.結構設計問題另外還要考慮到設計變量d和h有界。6.結構設計問題TPSHUAI28基本概念在上述例子中,有的目標函數和約束函數都是線性的,稱之為線性規劃問題,而有的模型中含有非線性函數,稱之為非線性規劃.在線性與非線性規劃中,滿足約束條件的點稱為可行點,全體可行點組成的集合稱為可行集或可行域.如果一個問題的可行域是整個空間,則稱此問題為無約束問題.TPSHUAI28基本概念在上述例子中,有的目標函數和約束TPSHUAI29基本概念最優化問題可寫成如下形式:TPSHUAI29基本概念最優化問題可寫成如下形式:TPSHUAI30基本概念Df1.1

設f(x)為目標函數，S為可行域，x0S,若對每一個xS,成立f(x)f(x0),則稱x0為極小化問題min

f(x),xS的最優解（整體最優解）則稱x0為極小化問題min

f(x),xS的局部最優解Df1.2設f(x)為目標函數，S為可行域，TPSHUAI30基本概念Df1.1設f(x)為目標TPSHUAI31Thankyouverymuchforyourattendance!優化軟件

/

/neos/solvers/index.htmlTPSHUAI31ThankyouverymuchTPSHUAI32最優化理論與算法帥天平北京郵電大學數學系Email:tpshuai@,Tel:62281308,Rm:主樓814§1預備知識TPSHUAI32最優化理論與算法帥天平TPSHUAI331，預備知識1.線性空間2.范數3.集合與序列4.矩陣的分解與校正TPSHUAI331，預備知識1.線性空間TPSHUAI341.線性空間Df1.3:給定一非空集合G以及在G上的一種代數運算+:G×G→G(稱為加法),若下述條件成立:則<G,+>稱為一個群.若還滿足對任意的a,b∈G,有a+b=b+a,則<G,+>稱為一個阿貝爾群(&交換群)TPSHUAI341.線性空間Df1.3:給定一非空集合TPSHUAI351.線性空間Df1.4:給定一非空集合V和一個域F,并定義兩種運算加法+:V×V→V以及數乘:F×V→V.若<V,+>構成一交換群,且兩種運算滿足下面性質:則稱V在域F上關于加法和數乘運算構成一線性空間,簡稱V為F上的線性空間.記為V(F).若V的非空子集合S關于加法和數乘運算在F上也構成一線性空間,則S稱為F上的線性子空間.TPSHUAI351.線性空間Df1.4:給定一非空集合TPSHUAI361.線性空間例子TPSHUAI361.線性空間例子TPSHUAI371.線性空間TPSHUAI371.線性空間TPSHUAI381.線性空間Th1.1

線性空間V(F)的非空子集S的線性擴張L(S)是V中包含S的最小子空間.TPSHUAI381.線性空間Th1.1線性空間V(F)TPSHUAI391.線性空間TPSHUAI391.線性空間TPSHUAI401.線性空間TPSHUAI401.線性空間TPSHUAI412.范數TPSHUAI412.范數TPSHUAI422.范數TPSHUAI422.范數TPSHUAI432.范數TPSHUAI432.范數TPSHUAI443.集合與序列TPSHUAI443.集合與序列TPSHUAI453，集合與序列TPSHUAI453，集合與序列TPSHUAI463.集合與序列TPSHUAI463.集合與序列TPSHUAI473.集合與序列TPSHUAI473.集合與序列TPSHUAI484.矩陣的分解與校正Th1.5

若n階矩陣A可逆，則存在一個排列矩陣P,單位下三角矩陣L和上三角矩陣U，使得PA=LUTPSHUAI484.矩陣的分解與校正Th1.5若n階矩TPSHUAI494.矩陣的分解與校正Th1.6

設A為對稱正定矩陣，則（1）矩陣A可唯一的分解成A=LDLT,其中L為單位下三角矩陣，D為對角矩陣（2）存在可逆的下三角矩陣L，使得A=LLT.當L的對角元素為正時，分解是唯一的。(Cholesky分解)TPSHUAI494.矩陣的分解與校正Th1.6設A為對TPSHUAI504.矩陣的分解與校正TPSHUAI504.矩陣的分解與校正TPSHUAI514.矩陣的分解與校正TPSHUAI514.矩陣的分解與校正TPSHUAI525.函數的可微性與展開TPSHUAI525.函數的可微性與展開TPSHUAI535.函數的可微性與展開當f(x)在x點存在二階偏導時,函數f在點x的Hesse矩陣定義為TPSHUAI535.函數的可微性與展開當f(x)在x點存TPSHUAI545.函數的可微性與展開TPSHUAI545.函數的可微性與展開TPSHUAI555.函數的可微性與展開TPSHUAI555.函數的可微性與展開TPSHUAI565.函數的可微性與展開TPSHUAI565.函數的可微性與展開TPSHUAI57最優化理論與算法帥天平北京郵電大學數學系Email:tpshuai@,Tel:62281308,Rm:主樓814§2，凸分析與凸函數TPSHUAI57最優化理論與算法帥天平TPSHUAI582.

凸集與凸函數2.1凸集與錐TPSHUAI582.凸集與凸函數2.1凸集與錐TPSHUAI592.

凸集與凸函數TPSHUAI592.凸集與凸函數TPSHUAI602.

凸集與凸函數x0xx-x0px0xx-x0pTPSHUAI602.凸集與凸函數x0xx-x0px0xTPSHUAI612.

凸集與凸函數TPSHUAI612.凸集與凸函數TPSHUAI62運用定義不難驗證如下命題：2.

凸集與凸函數TPSHUAI62運用定義不難驗證如下命題：2.凸集與凸TPSHUAI632.

凸集與凸函數多面體(polyhedralset)是有限閉半空間的交.(可表為

Axb).x4x3x2x1x5xyTPSHUAI632.凸集與凸函數多面體(polyhedTPSHUAI642.

凸集與凸函數TPSHUAI642.凸集與凸函數TPSHUAI65多面集

{x|Ax0}也是凸錐，稱為多面錐。2.

凸集與凸函數由定義可知,錐關于正的數乘運算封閉,凸錐關于加法和正的數乘封閉,一般的,對于凸集S,集合K(S)={λx|λ>0,xS}是包含S的最小凸錐.錐C稱為尖錐,若0S.尖錐稱為突出的,若它不包含一維子空間.約定:非空集合S生成的凸錐,是指可以表示成S中有限個元素的非負線性組合(稱為凸錐組合)的所有點所構成的集合,記為coneS.若S凸,則coneS=K(S)∪{0}TPSHUAI65多面集{x|Ax0}也是凸錐，稱為多TPSHUAI662.

凸集與凸函數Df2.5

非空凸集中的點

x

稱為極點,若

x=x1+(1-)x2,(0,1),x1,x2

S,則x=x1=x2.換言之,x不能表示成S中兩個不同點的凸組合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一點都可表成極點的凸組合.TPSHUAI662.凸集與凸函數Df2.5非空凸TPSHUAI672.

凸集與凸函數Def2.6.設非空凸集SRn,Rn中向量d0

稱為S的一個回收方向(方向),

若對每一

xS,

R(x.d)={x+d|0

}S.S的所有方向構成的尖錐稱為S的回收錐,記為0+S

方向d1和d2

稱為S的兩個不同的方向,若對任意>0,都有

d1d2；方向d稱為S的極方向extremedirection,若

d=d1+(1-)d2,(0,1),d1

,d2

是S的兩個方向,則有

d=d1=d2.換言之d不能表成它的兩個不同方向的凸錐組合x0x0dddTPSHUAI672.凸集與凸函數Def2.6.設非TPSHUAI682.

凸集與凸函數TPSHUAI682.凸集與凸函數TPSHUAI692.

凸集與凸函數表示定理Th2.4

若多面體P={xRn|Axb},r(A)=n則:(1)P的極點集是非空的有限集合,記為{x}kkK則j(2)記P的極方向集為46e1sixjJ(約定P不存在極方向時J=)(3)指標集J是空集當且僅當P是有界集合,即多胞形.TPSHUAI692.凸集與凸函數表示定理Th2.4若TPSHUAI702.

凸集與凸函數表示定理直觀描述:設X

為非空多面體.則存在有限個極點x1,…,xk,k>0.進一步,存在有限個極方向d1,…,dl,l>0

當且僅當X

無界.進而,xX

的充要條件是x

可以表為

x1,…,xk

的凸組合和d1,…,dl的非負線性組合(凸錐組合).xyx1x2x3d1d20推論2.1

若多面體S={x|Ax=b,x≥0}非空,則S必有極點.TPSHUAI702.凸集與凸函數表示定理直觀描述:設TPSHUAI712.2凸集分離定理2.

凸集與凸函數TPSHUAI712.2凸集分離定理2.凸集與凸函數TPSHUAI722.

凸集與凸函數TPSHUAI722.凸集與凸函數TPSHUAI73證明：令2.

凸集與凸函數TPSHUAI73證明：令2.凸集與凸函數TPSHUAI74所以為柯西列，必有極限,且由S為閉集知。此極限點必在S中。2.

凸集與凸函數下證明唯一性TPSHUAI74所以為柯西列，必有極限,且由S為閉集知。TPSHUAI752.

凸集與凸函數TPSHUAI752.凸集與凸函數TPSHUAI762.

凸集與凸函數TPSHUAI762.凸集與凸函數TPSHUAI772.

凸集與凸函數xpX(i)(x-)(y-

)0

對任意xX.(ii)令p=y-

，

=pp.

Txxxyx

證明提綱TPSHUAI772.凸集與凸函數xpXTxxxyx證TPSHUAI78由此可得2.

凸集與凸函數TPSHUAI78由此可得2.凸集與凸函數TPSHUAI792.

凸集與凸函數Th2.7表明，S為閉凸集，yS，則y與S可分離。若令clS表示非空集合S的閉包，則當yclS時，定理結論也真。實際上我們有下述定理TPSHUAI792.凸集與凸函數Th2.7表明，S為閉TPSHUAI80證明2.

凸集與凸函數TPSHUAI80證明2.凸集與凸函數TPSHUAI81推論2.2：設S為Rn

中的非空集合，yS,則存在非零向量p，使對xclS,pT

(x-y)02.

凸集與凸函數TPSHUAI81推論2.2：設S為Rn中的非空集合，yTPSHUAI822.

凸集與凸函數TPSHUAI822.凸集與凸函數TPSHUAI832.

凸集與凸函數TPSHUAI832.凸集與凸函數TPSHUAI84

作為凸集分離定理的應用，下面介紹兩個擇一定理：Farkas定理和Gordan定理，它們在最優化理論中是很有用的。2.

凸集與凸函數2.3擇一定理TPSHUAI84作為凸集分離定理的應用，下面介紹兩個TPSHUAI852.

凸集與凸函數TPSHUAI852.凸集與凸函數TPSHUAI862.

凸集與凸函數TPSHUAI862.凸集與凸函數TPSHUAI872.

凸集與凸函數TPSHUAI872.凸集與凸函數TPSHUAI882.

凸集與凸函數TPSHUAI882.凸集與凸函數TPSHUAI892.

凸集與凸函數TPSHUAI892.凸集與凸函數TPSHUAI902.

凸集與凸函數TPSHUAI902.凸集與凸函數TPSHUAI912.

凸集與凸函數TPSHUAI912.凸集與凸函數TPSHUAI922.

凸集與凸函數TPSHUAI922.凸集與凸函數TPSHUAI932.

凸集與凸函數2.4凸函數Df2.10設SRn是非空凸集,函數f:SR,若對任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)則稱f是S上的凸函數.若上面的不等式對于xy嚴格成立,則稱f是S上的嚴格凸函數.

若-f是S上的凸函數,則稱f是S上的凹函數.若-f是S上的嚴格凸函數,則稱f是S上的嚴格凹函數.2.4.1基本性質TPSHUAI932.凸集與凸函數2.4凸函數Df2.TPSHUAI942.

凸集與凸函數TPSHUAI942.凸集與凸函數TPSHUAI95Th2.13設f是一凸函數，則對任意的xRn

和d(0)Rn，f在x處沿方向d的方向導數存在。2.

凸集與凸函數TPSHUAI95Th2.13設f是一凸函數，則對任TPSHUAI962.

凸集與凸函數TPSHUAI962.凸集與凸函數TPSHUAI972.凸集與凸函數TPSHUAI972.凸集與凸函數TPSHUAI98命題2.3設f是定義在凸集S上的凸函數，則(1)所有凸函數f的集合關于凸錐組合運算是封閉的,即(a)實數0，則f也是定義在S上的凸函數(b)設f1和f2是定義在凸集S上的凸函數，則f1+f2也是定義在S上的凸函數2.

凸集與凸函數(2)函數f在開集intS內是連續的.(3)函數f的水平集L(f,)={x|xS,f(x)

≤},R

和上鏡圖epi(f)={(x,y)|xS,yR,y≥f(x)}都是凸集TPSHUAI98命題2.3設f是定義在凸集S上的凸函TPSHUAI992.

凸集與凸函數設S為Rn中的非空凸集,則f(x)是凸的當且僅當上鏡圖

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集對上鏡圖事實上我們有如下定理TPSHUAI992.凸集與凸函數設S為Rn中的非空凸TPSHUAI1002.

凸集與凸函數TPSHUAI1002.凸集與凸函數TPSHUAI101定理2.14設SRn為一非空凸集，f是定義在S上的凸函數，則f在S上的局部極小點是整體極小點，且極小點的集合為凸集。2.

凸集與凸函數TPSHUAI101定理2.14設SRn為一非空凸集，TPSHUAI1022.

凸集與凸函數TPSHUAI1022.凸集與凸函數TPSHUAI1032.

凸集與凸函數TPSHUAI1032.凸集與凸函數TPSHUAI1042.

凸集與凸函數2.5.2凸函數的判別Th2.16.設S是Rn

中的非空開凸集,f(x):SR

是可微的函數則

f(x)

是凸函數當且僅當對任意的x*S,我們有f(x)f(x*)+f(x*)(x-x*),

任意

xS.

類似的,f(x)

嚴格凸當且僅當對每一x*S,f(x)>

f(x*)+f(x*)(x-x*),

任意

xS.2.4.2凸函數的判別TPSHUAI1042.凸集與凸函數2.5.2凸函數的TPSHUAI1052.

凸集與凸函數TPSHUAI1052.凸集與凸函數TPSHUAI1062.

凸集與凸函數Th2.16*.設S是

Rn

上的非空開凸集,f(x)為S

到R上的可微函數.則

f(x)

是凸函數當且僅當任意的x1,x2

S,有

(f(x2)-f(x1))(x2-x1)0.類似的,f

嚴格凸當且僅當對任意相異的x1,x2

S,(f(x2)-f(x1))(x2-x1)>0.

TPSHUAI1062.凸集與凸函數Th2.16*.TPSHUAI1072.

凸集與凸函數TPSHUAI1072.凸集與凸函數TPSHUAI1082.

凸集與凸函數Def2.11.設S是Rn

上的非空開集,f(x)f(x):SR

的函數則

f(x)

在點x*int(S)稱為二次可微的,若存在向量f(x*),和

nn

(Hessian)矩陣

H(x*),及函數:Rn

R

使得對所有的

xS,f(x)=f(x*)+f(x*)(x-x*)+0.5(x-x*)H(x*)(x-x*)+||x-x*||

(x-x*)其中lim

(x-x*)=0.2x*x*xx*Th2.17設S是

Rna上的非空開凸集,f(x)為S

到R上的二次可微函數.則(1)

f(x)

是凸函數當且僅當S上每一點的Hessian矩陣是半正定的.(2)f(x)

是嚴格凸函數當且僅當S上每一點的Hessian矩陣是正定的.TPSHUAI1082.凸集與凸函數Def2.11.TPSHUAI109凸規劃2.

凸集與凸函數TPSHUAI109凸規劃2.凸集與凸函數TPSHUAI110最優化理論與算法帥天平北京郵電大學數學系Email:tpshuai@,Tel:62281308,Rm:主樓814§3，線性規劃的基本性質TPSHUAI110最優化理論與算法帥天平TPSHUAI111第二章線性規劃的基本性質標準形式與圖解法基本性質TPSHUAI111第二章線性規劃的基本性質標準形式與圖TPSHUAI112我每天要求一定量的兩種維生素，Vc和Vb。假設這些維生素可以分別從牛奶和雞蛋中得到。維生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250單價(US$)32.5需要確定每天喝奶和吃蛋的量，目標以便以最低可能的花費購買這些食物，而滿足最低限度的維生素需求量。2.線性規劃-

例子-食譜問題TPSHUAI112我每天要求一定量的兩種維生素，Vc和VTPSHUAI113令x表示要買的奶的量，y為要買的蛋的量。食譜問題可以寫成如下的數學形式：Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.極小化目標函數可行區域（單純形）可行解2.線性規劃-

例子-食譜問題TPSHUAI113令x表示要買的奶的量，y為要買的蛋的量TPSHUAI1141標準形式矩陣表示其中A是mn矩陣，c是n維行向量，b是m維列向量。注：為計算需要，一般假設b0.否則，可在方程兩端乘以(-1)即可化為非負。2.線性規劃-形式TPSHUAI1141標準形式矩陣表示其中A是mn矩陣，TPSHUAI115任意非標準形式均可化為標準形式，如引入松弛變量xn+1，xn+2,…xn+m.2.線性規劃-形式TPSHUAI115任意非標準形式均可化為標準形式，如引入TPSHUAI116則有2.線性規劃-形式TPSHUAI116則有2.線性規劃-形式TPSHUAI117Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.例如，考慮食譜問題2.圖解法當自變量個數少于3時,可以用較簡便的方法求解.2.線性規劃-圖解法TPSHUAI117Min3x+2.5y例如，考慮食TPSHUAI11830104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行區域的極點：(0,25)(15,2.5)最優解(20,0)Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.2.線性規劃-圖解法TPSHUAI1183010402050102030405TPSHUAI1193基本性質3.1線性規劃的可行域定理

2.2

線性規劃的可行域是凸集.3.2最優極點觀察上例，最優解在極點(15,2.5)達到，我們有如下事實:線性規劃若存在最優解,則最優解一定可在某極點上達到.2.線性規劃-性質1TPSHUAI1193基本性質定理2.2線性規劃的TPSHUAI120考察線性規劃的標準形式(2.2)根據表示定理，任意可行點x可表示為2.線性規劃-性質2TPSHUAI120考察線性規劃的標準形式(2.2)根據TPSHUAI121把x的表達式代入(2.2),得等價的線性規劃:2.線性規劃-性質3TPSHUAI121把x的表達式代入(2.2),得等價的TPSHUAI122于是,問題簡化成在(2.6)中令顯然,當時目標函數取極小值.2.線性規劃-性質4TPSHUAI122于是,問題簡化成在(2.6)中令顯然,TPSHUAI123因此極點x(p)是問題(2.2)的最優解.即(2.5)和(2.8)是(2.4)的最優解,此時2.線性規劃-性質5TPSHUAI123因此極點x(p)是問題(2.2)的最優TPSHUAI1242,若(2.2)存在有限最優解,則目標數的最優值可在某極點達到.定理2.3設線性規劃(2.2)的可行域非空,則1,(2.2)存在最優解的充要條件是所有(j)cd非負,其中是可行域的極方向d(j)2.線性規劃-性質6TPSHUAI1242,若(2.2)存在有限最優解,則目TPSHUAI1254最優基本可行解前面討論知道們最優解可在極點達到，而極點是一幾何概念，下面從代數的角度來考慮。不失一般性,設rank(A)=m,A=[B,N],B是m階可逆的.2.線性規劃-性質7TPSHUAI1254最優基本可行解前面討論知道們最優解可TPSHUAI126于是,Ax=b可寫為于是特別的令Nx=0,則2.線性規劃-性質8TPSHUAI126于是,Ax=b可寫為于是特別的令Nx=TPSHUAI127稱為方程組Ax=b的一個基本解.定義2.6B稱為基矩陣,的各分量稱為基變量.xB基變量的全體稱為一組基.的各分量稱為非基變量.xN為約束條件Ax=b,x0的一個基本可行解.B稱為可行基矩陣稱為一組可行基.2.線性規劃-性質9TPSHUAI127稱為方程組Ax=b的一個基本解.定義2TPSHUAI128Bb>0,稱基本可行解是非退化的,若-1若Bb0,-1且至少有一個分量為0,稱基本可行解是退化的.2.線性規劃-性質10TPSHUAI128Bb>0,稱基本可行解是非退化的TPSHUAI1292.線性規劃-性質11TPSHUAI1292.線性規劃-性質11TPSHUAI1302.線性規劃-性質12TPSHUAI1302.線性規劃-性質12TPSHUAI1312.線性規劃-性質13TPSHUAI1312.線性規劃-性質13TPSHUAI132容易知道,基矩陣的個數是有限的,因此基本解從而基本可行解的個數也是有限的,不超過2.線性規劃-性質14TPSHUAI132容易知道,基矩陣的個數是有限的,因此基TPSHUAI133定理2.4令K={x|Ax=b,x0},A是m×n矩陣,r(A)=m則K的極點集與Ax=b,x0的基本可行解集合等價.證明:(提綱)1)設x是K的極點,則x是Ax=b,x0的基本可行解.2)設x是Ax=b,x0的基本可行解,則x是K的極點.2.線性規劃-性質15TPSHUAI133定理2.4令K={x|Ax=b,TPSHUAI1341),先證極點x的正分量所對應的A的列線性無關.2.線性規劃-性質16TPSHUAI1341),先證極點x的正分量所對應的A的列TPSHUAI1352.線性規劃-性質17TPSHUAI1352.線性規劃-性質17TPSHUAI1362.線性規劃-性質18TPSHUAI1362.線性規劃-性質18TPSHUAI1372)設x是Ax=b,x0的基本可行解,記2.線性規劃-性質19TPSHUAI1372)設x是Ax=b,x0的基本可行解TPSHUAI138即2.線性規劃-性質20TPSHUAI138即2.線性規劃-性質20TPSHUAI139總結,線性規劃存在最優解,目標函數的最優值一定能在某極點上達到.可行域K={x|Ax=b,x0}的極點就是其基本可行解.

從而,求線性規劃的最優解,只需要求出最優基本可行解即可.2.線性規劃-性質21TPSHUAI139總結,線性規劃存在最優解,目標函數的最TPSHUAI1405基本可行解的存在問題定理2.5

若Ax=b,x0有可行解,則一定存在基本可行解,其中A是秩為m的mn矩陣.2.線性規劃-性質22TPSHUAI1405基本可行解的存在問題定理2.5TPSHUAI141否則,我們通過如下步驟構造出一基本可行解2.線性規劃-性質23TPSHUAI141否則,我們通過如下步驟構造出一基本可行TPSHUAI1422.線性規劃-性質24TPSHUAI1422.線性規劃-性質24最優化理論與算法帥天平北京郵電大學數學系Email:tpshuai@,Tel:62281308,Rm:主樓814§4，線性規劃的單純形方法最優化理論與算法帥天平第三章單純形方法1，單純形方法原理2，兩階段法和大Mf法3，退化情形4，修正單純形方法第三章單純形方法1，單純形方法原理單純形法的基本思路

是有選擇地取（而不是枚舉所有的）基本可行解，即是從可行域的一個頂點出發，沿著可行域的邊界移到另一個相鄰的頂點，要求新頂點的目標函數值不比原目標函數值差，如此迭代，直至找到最優解，或判定問題無界。

初始基本可行解是否最優解或無界解?結束沿邊界找新的基本可行解NY單純形法的基本過程

3.1線性規劃-單純形方法1怎么判斷達到最優解?如何給出初始基可行解?迭代如何進行?單純形法的基本思路是有選擇地取（而不是枚舉所有的）基本可行

3.1線性規劃-單純形方法2給定標準形式的LP利用分塊矩陣3.1線性規劃-單純形方法2給定標準形式的LP利用分塊矩陣3.1線性規劃-單純形方法3于是目標函數于是有

基本可行解x與基B關聯;3.1線性規劃-單純形方法3于是目標函數于是有基本可行解x3.線性規劃-單純形方法4于是我們有如下定理：3.線性規劃-單純形方法4于是我們有如下定理：3.1.線性規劃-單純形方法5由上知,要減少費用,只有當C0時才可能，即3.1.線性規劃-單純形方法5由上知,要減少費用,只有當3.1線性規劃-單純形方法6令y=x+d,>0,我們能降低費用嗎？3.1線性規劃-單純形方法6令y=x+d,>0,3.1線性規劃-單純形方法73.1線性規劃-單純形方法73.1線性規劃-單純形方法83.1線性規劃-單純形方法83.1線性規劃-單純形方法9正確性如何？顯然按上述取法，是可以保證y≥0的。y還是基本可行解嗎？3.1線性規劃-單純形方法9正確性如何？3.1線性規劃-單純形方法103.1線性規劃-單純形方法103.1線性規劃-單純形方法11單純形法3.1線性規劃-單純形方法11單純形法3.1線性規劃-單純形方法12Th3.4(單純形法的收斂性）對于相容的非退化(每個基可行解都是非退的)LP問題，那么經過有限次迭代后，單純形法或者得到最優的BFS(最優可行基B）或有一個方向d:且最優的費用為-∞.3.1線性規劃-單純形方法12Th3.4(單純形法的收斂性）3.1線性規劃-單純形方法13例13.1線性規劃-單純形方法13例13.1線性規劃-單純形方法143.1線性規劃-單純形方法143.1線性規劃-單純形方法15Tc

=(0702-300)3.1線性規劃-單純形方法15Tc=(07023.1線性規劃-單純形方法163.1線性規劃-單純形方法163.1線性規劃-單純形方法173.1線性規劃-單純形方法173.1線性規劃-單純形方法183.1線性規劃-單純形方法183.1線性規劃-單純形方法19新的基為B=(A1,A3,A4,A7)3.1線性規劃-單純形方法19新的基為B=(A1,A3,3.1線性規劃-單純形方法203.1線性規劃-單純形方法203.1線性規劃-單純形方法21新的基為B=(A3,A4,A5,A7)3.1線性規劃-單純形方法21新的基為B=(A3,A4,

3.1線性規劃-單純形方法22利用分塊矩陣表格形式的單純形方法3.1線性規劃-單純形方法22利用分塊矩陣表格形式的單純形

3.1線性規劃-單純形方法233.1線性規劃-單純形方法233.1線性規劃-單純形方法240

Im

10ff右端3.1線性規劃-單純形方法240Im3.1線性規劃-單純形方法25進基變量離基變量旋轉元右端向量返回單純形表3.1線性規劃-單純形方法25進基變量離基變量旋轉元右端向量例2：求解線性規劃問題化成標準化形式

3.1線性規劃-單純形方法26

例2：求解線性規劃問題化成標準化形式

3.1線性規劃-單純寫出單純形表25/136/20-3-20-2-7201/201-1/27/0.511/2101/218/0.5x271811/21/2x5x6離基，x2進基，x5離基，x1進基，3.1線性規劃-單純形方法27寫出單純形表25/136/20-3-20-2-7201/200-4-2-2-1-860102-1101-11141100得到最優解，最優解為：（x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）minz’=-86，maxz=861

3.1線性規劃-單純形方法280-4-2-2-1-860102-1101-11141100例3：求解線性規劃問題3.1線性規劃-單純形方法29例3：求解線性規劃問題3.1線性規劃-單純形方法293.1線性規劃-單純形方法303.1線性規劃-單純形方法30x3進基，x6離基3.1單純形方法31x3進基，x6離基3.1單純形方法31初始單純型表最優單純型表初始單純型表最優單純型表3.2兩階段法&大M法1單純形法三要素：初始基本可行解，解的迭代，最優性檢驗后兩個已解決,現考慮如何獲得一個初始基可行解.（一）兩階段法設標準LP為3.2兩階段法&大M法1單純形法三要素：（一）兩階段法設標3.2兩階段法&大M法2若系數矩陣中有一個單位矩陣，則容易得到初始基可行解.所以我們希望幸運的碰到這種矩陣.沒有的話，硬性加一個？3.2兩階段法&大M法2若系數矩陣中有一個單位矩陣，則容易3.2兩階段法&大M法3問題是如何由(3.2.3)的初始可行解獲得原來LP的一個初始可行解？為此，考慮如下輔助LP(第一階段)3.2兩階段法&大M法3問題是如何由(3.2.3)的初始可如果原問題有可行解，則輔助問題的最優值為0，反之亦然。就可以得到輔助問題的初始基可行解2．由于，所以以為基變量，,同時所以一定有最小值.3.2兩階段法&大M法4關系?如果原問題有可行解，則輔助問題的最優值為0，反之亦然。就可以3.2兩階段法&大M法5利用單純形法求得一個最優可行解.這個解將會給我們帶來什么？3.2兩階段法&大M法5利用單純形法求得一個最優可行解.這3.2兩階段法&大M法6于是我們獲得一個初始基可行解,從而可以以此基可行解出發利用單純形法求出最優解.第一階段：不考慮原LP問題是否有基可行解，添加人工變量，構造僅含人工變量的目標函數，得輔助規劃(3.2.4)單純型法求解上述模型，若有目標函數=0，說明原問題存在初始基本可行解，轉入第二階段。否則，原問題無可行解，計算停止。

第二階段：將第一階段計算得到的最終表，除去人工變量，從該初始基本可行解開始，用單純形法求原問題的最優解或判定原問題無界。3.2兩階段法&大M法6于是我們獲得一個初始基可行解,從而3.2兩階段法&大M法7寫成標準化形式例1求解3.2兩階段法&大M法7寫成標準化形式例1求解3.2兩階段法&大M法8第1

階段首先引入人工變量，構造輔助規劃問題如果以為基變量，則可以得到該問題的BFS,其對應的單純形表為3.2兩階段法&大M法8第1

階段首先引入人工變量，構造3.2兩階段法&大M法9-50-210000000000-1-101-16-101021120-1011RHS-50-2100000208-1-10031-16-101021120-1011gzgz3.2兩階段法&大M法9-50-23.2兩階段法&大M法10-3/2-7/20-7/207/20-72/34/301/3-1-4/301/31/6-1/61-1/601/601/32/34/301/3-1-1/311/3RHSgz1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgz3.2兩階段法&大M法10-3/2-7/201/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgz第一階段結束，得到輔助問題的一個最優解同時得到原問題的一個初始基本可行解3.2兩階段法&大M法111/400-21/8去掉人工變量對應的行、列，得到原問題的初始典式，直接開始第二階段運算第

2

階

段1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgzRHS0-1/20-11/4-9/431/4

0-1/21-1/41/41/41201/2-3/21/2z原問題的最優解其最優值為去掉人工變量對應的行、列，得到原問題的初始典式，直接開始第二3.2兩階段法&大M法12例2求解3.2兩階段法&大M法12例2求解3.2兩階段法&大M法13解：引進人工變量進行第一階段3.2兩階段法&大M法13解：引進人工變量進行第一階段3.2兩階段法&大M法14單純形法求解：3.2兩階段法&大M法14單純形法求解：3.2兩階段法&大M法15011-10104002-300140-11-21000004-600083.2兩階段法&大M法150113.2兩階段法&大M法160201-20140201-11040402-400833.2兩階段法&大M法160203.2兩階段法&大M法17010?-??020000-1-110001-3/2??020000-2-20823.2兩階段法&大M法170103.2兩階段法&大M法18第二階段：

3.2兩階段法&大M法18第二階段：3.2兩階段法&大M法19第二階段初始單純形表：3.2兩階段法&大M法19第二階段初始單純形表：3.2兩階段法&大M法20前面所說的兩階段法分成兩步走。能不能把這兩步合并？如何合并？（二）大M法設原問題為引入m個人工變量3.2兩階段法&大M法20前面所說的兩階段法分成兩步走。能3.2兩階段法&大M法21現在關鍵是如何選取目標函數，因要包含原問題,所以必須包含原目標。聯系到兩階段法，我們要強迫人工變量取值為0，于是加上一個懲罰因子，因為是極小化，所以希望這個懲罰因子越大越好！！在目標函數中增加3.2兩階段法&大M法21現在關鍵是如何選取目標函數，因要3.2兩階段法&大M法22可行嗎？直觀上，因M為足夠大的正數，新問題最優解對應的人工變量取值應滿足，（除非原問題不可行）從而新LP問題的最優解對應于原問題的（基本）可行解，容易知道此時兩個問題的目標函數值滿足3.2兩階段法&大M法22可行嗎？直觀上，因M為足夠大的正3.2兩階段法&大M法23因此只需求解輔助問題就可求得原問題的最優解。另一方面，原問題的任意可行解x對應于輔助問題的可行解，也對應新問題的可行解且兩個規劃目標值相等，故原問題的最優解綜合3.2兩階段法&大M法23因此只需求解輔助問題就可求得原問3.2兩階段法&大M法24例3求解如下LP解：3.2兩階段法&大M法24例3求解如下LP解：

得到最優解：(25/3，10/3，0，11)T

最優目標值：max=112/33.2兩階段法&大M法25得到最優解：(25/3，10/3，0，11)T3.3.2.3單個人工變量技巧1前述方法引入多個人工變量，能否只引入一個變量而達到目標？考慮LP3.2.3單個人工變量技巧1前述方法引入多個人工變量，能否3.2.3單個人工變量技巧23.2.3單個人工變量技巧23.2.3單個人工變量技巧3例子：3.2.3單個人工變量技巧3例子：3.2.3單個人工變量技巧4利用表格形式求解一個(3.2.17)的BFS：3.2.3單個人工變量技巧4利用表格形式求解一個(3.2.3.2.3單個人工變量技巧5于是得到(3.2.17)的一個BFS，下面再用兩階段(或大M)法求解之.3.2.3單個人工變量技巧5于是得到(3.2.17)的一個3.2.3單個人工變量技巧63.2.3單個人工變量技巧63.2.3單個人工變量技巧7于是得到進行第二階段時的初始表。由上知道這是最優單純形表。3.2.3單個人工變量技巧7于是得到進行第二階段時的初始表3.3退化情形1單純形法收斂定理要求BFS非退化，這個限制可以去掉嗎？試看下例。例(3.3.1)：用單純形法求解下面的LP注意到該LP有一個明顯的BFS

x=(0，0，1，0，0，0，0)3.3退化情形1單純形法收斂定理要求BFS非退化，這個限制3.3退化情形2其單純形法迭代過程如下：3.3退化情形2其單純形法迭代過程如下：3.3退化情形33.3退化情形33.3退化情形43.3退化情形43.3退化情形53.3退化情形53.3退化情形6前例表明算法會無限循環下去，能否找到一種辦法避免出現這種情況？(a)攝動法3.3退化情形6前例表明算法會無限循環下去，能否找到一種辦3.3退化情形7下面討論這種辦法的可行性。對右端向量b作如下攝動。令于是得（3.3.1）的攝動問題：3.3退化情形7下面討論這種辦法的可行性。對右端向量b作3.3退化情形8下面我們將證明當適當對取值時，LP(3.3.3)非退化，且可以通過求解LP(3.3.3)來確定原LP(3.3.1)的最優解或得出其他結論。3.3退化情形8下面我們將證明當適當對取值時，LP(3.33.3退化情形9前面分析表明攝動問題當>0充分小時非退化，因此可以避免循環，并且通過求解攝動問題一定能夠給出線性規劃

(3.3.1)的解答。下一個問題是如何求解攝動問題？此時需要處理兩個問題：（1）初始可行解；（2）迭代過程中如何處理b().(a)初始可行解的確定思想：是由原LP(3.3.1)的BFS來找LP(3.3.3)的BFS.3.3退化情形9前面分析表明攝動問題當>0充分小時非退化3.3退化情形10對應的攝動問題約束為幸運的是我們可以通過將變量下標進行適當調整，使得上述情況不出現。改變標號，使得(3.3.8)為如下等價約束:3.3退化情形10對應的攝動問題約束為幸運的是我們可以通過3.3退化情形11一般地，若已知LP(3.3.1)的一個BFS，則進行列調換，把基列排在非基列的左邊，并相應地改變變量的下標，使其從1開始按遞增順序排列，這樣x1,x2,..,xm是基變量，然后再建立攝動問題(3.3.3).這時，若(3.3.1)的現行BFS是3.3退化情形11一般地，若已知LP(3.3.1)的一個B3.3退化情形12于是可以用單純形法求解下去。但右端向量含有參數，這對計算有影響嗎？實際上我們可以不必讓取具體數字。注意到：3.3退化情形12于是可以用單純形法求