最優(yōu)化理論與算法完整版課件陳寶林課件

可編輯1最優(yōu)化理論與算法2023/8/19可編輯1最優(yōu)化理論與算法2023/8/5可編輯2提綱1.

線性規(guī)劃

對偶定理2.非線性規(guī)劃K-K-T定理3.組合最優(yōu)化

算法設(shè)計技巧使用教材：最優(yōu)化理論與算法陳寶林參考書：數(shù)學(xué)規(guī)劃黃紅選，韓繼業(yè)

清華大學(xué)出版社2023/8/19可編輯2提綱1.線性規(guī)劃對偶定理使用教材：2023/可編輯3其他參考書目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.2023/8/19可編輯3其他參考書目NonlinearProgrammin可編輯4LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.運籌學(xué)基礎(chǔ)手冊徐光輝、劉彥佩、程侃科學(xué)出版社，1999組合最優(yōu)化算法和復(fù)雜性CombinatorialOptimization

蔡茂誠、劉振宏 AlgorithmsandComplexity清華大學(xué)出版社，1988

Printice-HallInc.,1982/1998

其他參考書目2023/8/19可編輯4LinearProgrammingandNet可編輯51,緒論----學(xué)科概述最優(yōu)化是從所有可能的方案中選擇最合理的一種方案,以達到最佳目標的科學(xué).達到最佳目標的方案是最優(yōu)方案,尋找最優(yōu)方案的方法----最優(yōu)化方法(算法)這種方法的數(shù)學(xué)理論即為最優(yōu)化理論.是運籌學(xué)的方法論之一.是其重要組成部分.運籌學(xué)的“三個代表”模型理論算法最優(yōu)化首先是一種理念,其次才是一種方法.2023/8/19可編輯51,緒論----學(xué)科概述最優(yōu)化是從所有可能的方案中選可編輯6緒論---運籌學(xué)（OperationsResearch-OR）運籌學(xué)方法隨機過程方法統(tǒng)計學(xué)方法最優(yōu)化/數(shù)學(xué)規(guī)劃方法連續(xù)優(yōu)化：線性規(guī)劃、非線性規(guī)劃、非光滑優(yōu)化、全局優(yōu)化、變分法、二次規(guī)劃、分式規(guī)劃等離散優(yōu)化：組合優(yōu)化、網(wǎng)絡(luò)優(yōu)化、整數(shù)規(guī)劃等幾何規(guī)劃動態(tài)規(guī)劃不確定規(guī)劃：隨機規(guī)劃、模糊規(guī)劃等多目標規(guī)劃對策論等統(tǒng)計決策理論馬氏過程排隊論更新理論仿真方法可靠性理論等回歸分析群分析模式識別實驗設(shè)計因子分析等2023/8/19可編輯6緒論---運籌學(xué)（OperationsResear可編輯7優(yōu)化樹2023/8/19可編輯7優(yōu)化樹2023/8/5可編輯8最優(yōu)化的發(fā)展歷程費馬:1638;牛頓,1670歐拉,1755Minf(x1x2···xn)

f(x)=02023/8/19可編輯8最優(yōu)化的發(fā)展歷程費馬:1638;牛頓,1670歐拉,可編輯9歐拉，拉格朗日：無窮維問題，變分學(xué)柯西：最早應(yīng)用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m2023/8/19可編輯9歐拉，拉格朗日：無窮維問題，變分學(xué)拉格朗日，1797可編輯101930年代，康托諾維奇：線性規(guī)劃1940年代，Dantzig：單純形方法，馮諾依曼：對策論1950年代，Bellman：動態(tài)規(guī)劃，最優(yōu)性原理；

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

6-70年代：Cook等復(fù)雜性理論，組合優(yōu)化迅速發(fā)展

電子計算機----------

最優(yōu)化2023/8/19可編輯101930年代，康托諾維奇：線性規(guī)劃電子計算機---可編輯11最優(yōu)化應(yīng)用舉例具有廣泛的實用性運輸問題，車輛調(diào)度，員工安排，空運控制等工程設(shè)計，結(jié)構(gòu)設(shè)計等資源分配，生產(chǎn)計劃等通信：光網(wǎng)絡(luò)、無線網(wǎng)絡(luò)，adhoc等.制造業(yè)：鋼鐵生產(chǎn)，車間調(diào)度等醫(yī)藥生產(chǎn)，化工處理等電子工程，集成電路VLSIetc.排版（TEX,Latex,etc.）2023/8/19可編輯11最優(yōu)化應(yīng)用舉例具有廣泛的實用性2023/8/5可編輯121.

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

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

403x+2y

50

x,y

0.極小化目標函數(shù)可行區(qū)域（單純形）可行解2023/8/19可編輯131.食譜問題（續(xù)）令x表示要買的奶的量，y為要買可編輯142

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

運輸問題（續(xù)）2023/8/19可編輯15令xij表示由產(chǎn)地Ai運往銷地Bj的物品數(shù)量，則產(chǎn)可編輯16以價格qi

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

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

稅下投資問題2023/8/19可編輯16以價格qi購買了si份股票i,i=1,2,…,n可編輯17我們的目標是要使預(yù)期收益最大。Xi：當(dāng)前拋出股票i的數(shù)量。3

稅下投資問題（續(xù)）2023/8/19可編輯17我們的目標是要使預(yù)期收益最大。3稅下投資問題（續(xù)可編輯184

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

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

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

選址問題（2）2023/8/19可編輯194選址問題（2）2023/8/5可編輯204選址問題（3）2023/8/19可編輯204選址問題（3）2023/8/5可編輯215負載平衡(1)實例:網(wǎng)絡(luò)G(V,E)

及一組m

個數(shù)的集合{

s,d>0}，表示

連接源點

s與匯點d

之間的流量解:{

s,d>0}的一組路由,即G(V,E)

中m

條s

與

d間的路,

表示連接s與d

的負載流量的路徑。目標:極小化網(wǎng)絡(luò)負載2023/8/19可編輯215負載平衡(1)實例:網(wǎng)絡(luò)G(V,E)及一組m可編輯225

負載平衡(2)2023/8/19可編輯225負載平衡(2)2023/8/5可編輯236.結(jié)構(gòu)設(shè)計問題兩桿桁架的最優(yōu)設(shè)計問題。由兩根空心圓桿組成對稱的兩桿桁架，其頂點承受負載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性模量為E，屈吸強度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。2023/8/19可編輯236.結(jié)構(gòu)設(shè)計問題兩桿桁架的最優(yōu)設(shè)計問題。2023/可編輯24

受力分析圖圓桿截面圖桁桿示意圖6.結(jié)構(gòu)設(shè)計問題2023/8/19可編輯24受力分析圖圓桿截可編輯256.結(jié)構(gòu)設(shè)計問題此應(yīng)力要求小于材料的屈吸極限，即解：桁桿的截面積為：桁桿的總重量為：負載2p在每個桿上的分力為：于是桿截面的應(yīng)力為：2023/8/19可編輯256.結(jié)構(gòu)設(shè)計問題此應(yīng)力要求小于材料的屈吸極限，即解

圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由材料力學(xué)知：壓桿穩(wěn)定的臨界應(yīng)力為

由此得穩(wěn)定約束：6.結(jié)構(gòu)設(shè)計問題2023/8/19TPSHUAI26圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由此得穩(wěn)定約束

另外還要考慮到設(shè)計變量d和h有界。從而得到兩桿桁架最優(yōu)設(shè)計問題的數(shù)學(xué)模型：6.結(jié)構(gòu)設(shè)計問題2023/8/19TPSHUAI27另外還要考慮到設(shè)計變量d和h有界。6.結(jié)構(gòu)設(shè)計問題20可編輯28基本概念在上述例子中,有的目標函數(shù)和約束函數(shù)都是線性的,稱之為線性規(guī)劃問題,而有的模型中含有非線性函數(shù),稱之為非線性規(guī)劃.在線性與非線性規(guī)劃中,滿足約束條件的點稱為可行點,全體可行點組成的集合稱為可行集或可行域.如果一個問題的可行域是整個空間,則稱此問題為無約束問題.2023/8/19可編輯28基本概念在上述例子中,有的目標函數(shù)和約束函數(shù)202可編輯29基本概念最優(yōu)化問題可寫成如下形式:2023/8/19可編輯29基本概念最優(yōu)化問題可寫成如下形式:2023/8/5可編輯30基本概念Df1.1

設(shè)f(x)為目標函數(shù)，S為可行域，x0

S,若對每一個x

S,成立f(x)f(x0),則稱x0為極小化問題min

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

f(x),xS的局部最優(yōu)解Df1.2設(shè)f(x)為目標函數(shù)，S為可行域，2023/8/19可編輯30基本概念Df1.1設(shè)f(x)為目標函數(shù)，S為可編輯31Thankyouverymuchforyourattendance!優(yōu)化軟件

/

/neos/solvers/index.html2023/8/19可編輯31ThankyouverymuchforyTPSHUAI32最優(yōu)化理論與算法帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@,Tel:62281308,Rm:主樓814§1預(yù)備知識2023/8/19TPSHUAI32TPSHUAI32最優(yōu)化理論與算法帥天平2023/8/5TTPSHUAI331，預(yù)備知識1.線性空間2.范數(shù)3.集合與序列4.矩陣的分解與校正2023/8/19TPSHUAI33TPSHUAI331，預(yù)備知識1.線性空間2023/8/TPSHUAI341.線性空間Df1.3:給定一非空集合G以及在G上的一種代數(shù)運算+:G×G→G(稱為加法),若下述條件成立:則<G,+>稱為一個群.若還滿足對任意的a,b∈G,有a+b=b+a,則<G,+>稱為一個阿貝爾群(&交換群)2023/8/19TPSHUAI34TPSHUAI341.線性空間Df1.3:給定一非空集合TPSHUAI351.線性空間Df1.4:給定一非空集合V和一個域F,并定義兩種運算加法+:V×V→V以及數(shù)乘

:F×V→V.若<V,+>構(gòu)成一交換群,且兩種運算滿足下面性質(zhì):則稱V在域F上關(guān)于加法和數(shù)乘

運算構(gòu)成一線性空間,簡稱V為F上的線性空間.記為V(F).若V的非空子集合S關(guān)于加法和數(shù)乘運算在F上也構(gòu)成一線性空間,則S稱為F上的線性子空間.2023/8/19TPSHUAI35TPSHUAI351.線性空間Df1.4:給定一非空集合TPSHUAI361.線性空間例子2023/8/19TPSHUAI36TPSHUAI361.線性空間例子2023/8/5TPSTPSHUAI371.線性空間2023/8/19TPSHUAI37TPSHUAI371.線性空間2023/8/5TPSHUTPSHUAI381.線性空間Th1.1

線性空間V(F)的非空子集S的線性擴張L(S)是V中包含S的最小子空間.2023/8/19TPSHUAI38TPSHUAI381.線性空間Th1.1線性空間V(F)TPSHUAI391.線性空間2023/8/19TPSHUAI39TPSHUAI391.線性空間2023/8/5TPSHUTPSHUAI401.線性空間2023/8/19TPSHUAI40TPSHUAI401.線性空間2023/8/5TPSHUTPSHUAI412.范數(shù)2023/8/19TPSHUAI41TPSHUAI412.范數(shù)2023/8/5TPSHUAITPSHUAI422.范數(shù)2023/8/19TPSHUAI42TPSHUAI422.范數(shù)2023/8/5TPSHUAITPSHUAI432.范數(shù)2023/8/19TPSHUAI43TPSHUAI432.范數(shù)2023/8/5TPSHUAITPSHUAI443.集合與序列2023/8/19TPSHUAI44TPSHUAI443.集合與序列2023/8/5TPSHTPSHUAI453，集合與序列2023/8/19TPSHUAI45TPSHUAI453，集合與序列2023/8/5TPSHTPSHUAI463.集合與序列2023/8/19TPSHUAI46TPSHUAI463.集合與序列2023/8/5TPSHTPSHUAI473.集合與序列2023/8/19TPSHUAI47TPSHUAI473.集合與序列2023/8/5TPSHTPSHUAI484.矩陣的分解與校正Th1.5

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

設(shè)A為對稱正定矩陣，則（1）矩陣A可唯一的分解成A=LDLT,其中L為單位下三角矩陣，D為對角矩陣（2）存在可逆的下三角矩陣L，使得A=LLT.當(dāng)L的對角元素為正時，分解是唯一的。(Cholesky分解)2023/8/19TPSHUAI49TPSHUAI494.矩陣的分解與校正Th1.6設(shè)A為對TPSHUAI504.矩陣的分解與校正2023/8/19TPSHUAI50TPSHUAI504.矩陣的分解與校正2023/8/5TPTPSHUAI514.矩陣的分解與校正2023/8/19TPSHUAI51TPSHUAI514.矩陣的分解與校正2023/8/5TPTPSHUAI525.函數(shù)的可微性與展開2023/8/19TPSHUAI52TPSHUAI525.函數(shù)的可微性與展開2023/8/5TTPSHUAI535.函數(shù)的可微性與展開當(dāng)f(x)在x點存在二階偏導(dǎo)時,函數(shù)f在點x的Hesse矩陣定義為2023/8/19TPSHUAI53TPSHUAI535.函數(shù)的可微性與展開當(dāng)f(x)在x點存TPSHUAI545.函數(shù)的可微性與展開2023/8/19TPSHUAI54TPSHUAI545.函數(shù)的可微性與展開2023/8/5TTPSHUAI555.函數(shù)的可微性與展開2023/8/19TPSHUAI55TPSHUAI555.函數(shù)的可微性與展開2023/8/5TTPSHUAI565.函數(shù)的可微性與展開2023/8/19TPSHUAI56TPSHUAI565.函數(shù)的可微性與展開2023/8/5TTPSHUAI57最優(yōu)化理論與算法帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@,Tel:62281308,Rm:主樓814§2，凸分析與凸函數(shù)2023/8/19TPSHUAI57TPSHUAI57最優(yōu)化理論與算法帥天平2023/8/5TTPSHUAI582.

凸集與凸函數(shù)2.1凸集與錐2023/8/19TPSHUAI58TPSHUAI582.凸集與凸函數(shù)2.1凸集與錐202TPSHUAI592.

凸集與凸函數(shù)2023/8/19TPSHUAI59TPSHUAI592.凸集與凸函數(shù)2023/8/5TPTPSHUAI602.

凸集與凸函數(shù)x0xx-x0px0xx-x0p2023/8/19TPSHUAI60TPSHUAI602.凸集與凸函數(shù)x0xx-x0px0xTPSHUAI612.

凸集與凸函數(shù)2023/8/19TPSHUAI61TPSHUAI612.凸集與凸函數(shù)2023/8/5TPTPSHUAI62運用定義不難驗證如下命題：2.

凸集與凸函數(shù)2023/8/19TPSHUAI62TPSHUAI62運用定義不難驗證如下命題：2.凸集與凸TPSHUAI632.

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

b).x4x3x2x1x5xy2023/8/19TPSHUAI63TPSHUAI632.凸集與凸函數(shù)多面體(polyhedTPSHUAI642.

凸集與凸函數(shù)2023/8/19TPSHUAI64TPSHUAI642.凸集與凸函數(shù)2023/8/5TPTPSHUAI65多面集{x|Ax

0}也是凸錐，稱為多面錐。2.

凸集與凸函數(shù)由定義可知,錐關(guān)于正的數(shù)乘運算封閉,凸錐關(guān)于加法和正的數(shù)乘封閉,一般的,對于凸集S,集合K(S)={λx|λ>0,x

S}是包含S的最小凸錐.錐C稱為尖錐,若0

S.尖錐稱為突出的,若它不包含一維子空間.約定:非空集合S生成的凸錐,是指可以表示成S中有限個元素的非負線性組合(稱為凸錐組合)的所有點所構(gòu)成的集合,記為coneS.若S凸,則coneS=K(S)∪{0}2023/8/19TPSHUAI65TPSHUAI65多面集{x|Ax0}也是凸錐，稱為多TPSHUAI662.

凸集與凸函數(shù)Df2.5

非空凸集中的點x

稱為極點,若x=

x1+(1-

)x2,

(0,1),x1,x2

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

凸集與凸函數(shù)Def2.6.設(shè)非空凸集S

Rn,Rn中向量d0

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

若對每一x

S,

R(x.d)={x+

d|

0

}

S.S的所有方向構(gòu)成的尖錐稱為S的回收錐,記為0+S

方向d1和d2

稱為S的兩個不同的方向,若對任意

>0,都有

d1

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

d1+(1-

)d2,

(0,1),d1

,d2

是S的兩個方向,則有

d=d1=d2.換言之d不能表成它的兩個不同方向的凸錐組合x0x0ddd2023/8/19TPSHUAI67TPSHUAI672.凸集與凸函數(shù)Def2.6.設(shè)非TPSHUAI682.

凸集與凸函數(shù)2023/8/19TPSHUAI68TPSHUAI682.凸集與凸函數(shù)2023/8/5TPTPSHUAI692.

凸集與凸函數(shù)表示定理Th2.4

若多面體P={x

Rn|Ax

b},r(A)=n則:(1)P的極點集是非空的有限集合,記為{x}kkK則j(2)記P的極方向集為aek73wejJ(約定P不存在極方向時J=)(3)指標集J是空集當(dāng)且僅當(dāng)P是有界集合,即多胞形.2023/8/19TPSHUAI69TPSHUAI692.凸集與凸函數(shù)表示定理Th2.4若TPSHUAI702.

凸集與凸函數(shù)表示定理直觀描述:設(shè)X

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

當(dāng)且僅當(dāng)X

無界.進而,x

X

的充要條件是x

可以表為

x1,…,xk

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

若多面體S={x|Ax=b,x≥0}非空,則S必有極點.2023/8/19TPSHUAI70TPSHUAI702.凸集與凸函數(shù)表示定理直觀描述:設(shè)TPSHUAI712.2凸集分離定理2.

凸集與凸函數(shù)2023/8/19TPSHUAI71TPSHUAI712.2凸集分離定理2.凸集與凸函數(shù)TPSHUAI722.

凸集與凸函數(shù)2023/8/19TPSHUAI72TPSHUAI722.凸集與凸函數(shù)2023/8/5TPTPSHUAI73證明：令2.

凸集與凸函數(shù)2023/8/19TPSHUAI73TPSHUAI73證明：令2.凸集與凸函數(shù)2023/8/TPSHUAI74所以為柯西列，必有極限,且由S為閉集知。此極限點必在S中。2.

凸集與凸函數(shù)下證明唯一性2023/8/19TPSHUAI74TPSHUAI74所以為柯西列，必有極限,且由S為閉集知。TPSHUAI752.

凸集與凸函數(shù)2023/8/19TPSHUAI75TPSHUAI752.凸集與凸函數(shù)2023/8/5TPTPSHUAI762.

凸集與凸函數(shù)2023/8/19TPSHUAI76TPSHUAI762.凸集與凸函數(shù)2023/8/5TPTPSHUAI772.

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

)0

對任意x

X.(ii)令p=y-

，

=pp.

Txxxyx

證明提綱2023/8/19TPSHUAI77TPSHUAI772.凸集與凸函數(shù)xpXTxxxyx證TPSHUAI78由此可得2.

凸集與凸函數(shù)2023/8/19TPSHUAI78TPSHUAI78由此可得2.凸集與凸函數(shù)2023/8/TPSHUAI792.

凸集與凸函數(shù)Th2.7表明，S為閉凸集，yS，則y與S可分離。若令clS表示非空集合S的閉包，則當(dāng)yclS時，定理結(jié)論也真。實際上我們有下述定理2023/8/19TPSHUAI79TPSHUAI792.凸集與凸函數(shù)Th2.7表明，S為閉TPSHUAI80證明2.

凸集與凸函數(shù)2023/8/19TPSHUAI80TPSHUAI80證明2.凸集與凸函數(shù)2023/8/5TTPSHUAI81推論2.2：設(shè)S為Rn

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

(x-y)02.

凸集與凸函數(shù)2023/8/19TPSHUAI81TPSHUAI81推論2.2：設(shè)S為Rn中的非空集合，yTPSHUAI822.

凸集與凸函數(shù)2023/8/19TPSHUAI82TPSHUAI822.凸集與凸函數(shù)2023/8/5TPTPSHUAI832.

凸集與凸函數(shù)2023/8/19TPSHUAI83TPSHUAI832.凸集與凸函數(shù)2023/8/5TPTPSHUAI84

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

凸集與凸函數(shù)2.3擇一定理2023/8/19TPSHUAI84TPSHUAI84作為凸集分離定理的應(yīng)用，下面介紹兩個TPSHUAI852.

凸集與凸函數(shù)2023/8/19TPSHUAI85TPSHUAI852.凸集與凸函數(shù)2023/8/5TPTPSHUAI862.

凸集與凸函數(shù)2023/8/19TPSHUAI86TPSHUAI862.凸集與凸函數(shù)2023/8/5TPTPSHUAI872.

凸集與凸函數(shù)2023/8/19TPSHUAI87TPSHUAI872.凸集與凸函數(shù)2023/8/5TPTPSHUAI882.

凸集與凸函數(shù)2023/8/19TPSHUAI88TPSHUAI882.凸集與凸函數(shù)2023/8/5TPTPSHUAI892.

凸集與凸函數(shù)2023/8/19TPSHUAI89TPSHUAI892.凸集與凸函數(shù)2023/8/5TPTPSHUAI902.

凸集與凸函數(shù)2023/8/19TPSHUAI90TPSHUAI902.凸集與凸函數(shù)2023/8/5TPTPSHUAI912.

凸集與凸函數(shù)2023/8/19TPSHUAI91TPSHUAI912.凸集與凸函數(shù)2023/8/5TPTPSHUAI922.

凸集與凸函數(shù)2023/8/19TPSHUAI92TPSHUAI922.凸集與凸函數(shù)2023/8/5TPTPSHUAI932.

凸集與凸函數(shù)2.4凸函數(shù)Df2.10設(shè)S

Rn是非空凸集,函數(shù)f:SR,若對任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)則稱f是S上的凸函數(shù).若上面的不等式對于x

y嚴格成立,則稱f是S上的嚴格凸函數(shù).

若-f是S上的凸函數(shù),則稱f是S上的凹函數(shù).若-f是S上的嚴格凸函數(shù),則稱f是S上的嚴格凹函數(shù).2.4.1基本性質(zhì)2023/8/19TPSHUAI93TPSHUAI932.凸集與凸函數(shù)2.4凸函數(shù)Df2.TPSHUAI942.

凸集與凸函數(shù)2023/8/19TPSHUAI94TPSHUAI942.凸集與凸函數(shù)2023/8/5TPTPSHUAI95Th2.13設(shè)f是一凸函數(shù)，則對任意的xRn

和d(0)Rn，f在x處沿方向d的方向?qū)?shù)存在。2.

凸集與凸函數(shù)2023/8/19TPSHUAI95TPSHUAI95Th2.13設(shè)f是一凸函數(shù)，則對任TPSHUAI962.

凸集與凸函數(shù)2023/8/19TPSHUAI96TPSHUAI962.凸集與凸函數(shù)2023/8/5TPTPSHUAI972.凸集與凸函數(shù)2023/8/19TPSHUAI97TPSHUAI972.凸集與凸函數(shù)2023/8/5TPSTPSHUAI98命題2.3設(shè)f是定義在凸集S上的凸函數(shù)，則(1)所有凸函數(shù)f的集合關(guān)于凸錐組合運算是封閉的,即(a)實數(shù)

0，則

f也是定義在S上的凸函數(shù)(b)設(shè)f1和f2是定義在凸集S上的凸函數(shù)，則f1+f2也是定義在S上的凸函數(shù)2.

凸集與凸函數(shù)(2)函數(shù)f在開集intS內(nèi)是連續(xù)的.(3)函數(shù)f的水平集L(f,

)={x|xS,f(x)

≤

},

R

和上鏡圖epi(f)={(x,y)|xS,y

R,y≥f(x)}都是凸集2023/8/19TPSHUAI98TPSHUAI98命題2.3設(shè)f是定義在凸集S上的凸函TPSHUAI992.

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

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

凸集與凸函數(shù)2023/8/19TPSHUAI100TPSHUAI1002.凸集與凸函數(shù)2023/8/5TPTPSHUAI101定理2.14設(shè)SRn為一非空凸集，f是定義在S上的凸函數(shù)，則f在S上的局部極小點是整體極小點，且極小點的集合為凸集。2.

凸集與凸函數(shù)2023/8/19TPSHUAI101TPSHUAI101定理2.14設(shè)SRn為一非空凸集，TPSHUAI1022.

凸集與凸函數(shù)2023/8/19TPSHUAI102TPSHUAI1022.凸集與凸函數(shù)2023/8/5TPTPSHUAI1032.

凸集與凸函數(shù)2023/8/19TPSHUAI103TPSHUAI1032.凸集與凸函數(shù)2023/8/5TPTPSHUAI1042.

凸集與凸函數(shù)2.5.2凸函數(shù)的判別Th2.16.設(shè)S是Rn

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

是可微的函數(shù)則

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)對任意的x*

S,我們有f(x)

f(x*)+

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

任意

x

S.

類似的,f(x)

嚴格凸當(dāng)且僅當(dāng)對每一x*

S,f(x)>

f(x*)+

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

任意

x

S.2.4.2凸函數(shù)的判別2023/8/19TPSHUAI104TPSHUAI1042.凸集與凸函數(shù)2.5.2凸函數(shù)的TPSHUAI1052.

凸集與凸函數(shù)2023/8/19TPSHUAI105TPSHUAI1052.凸集與凸函數(shù)2023/8/5TPTPSHUAI1062.

凸集與凸函數(shù)Th2.16*.設(shè)S是

Rn

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

到R上的可微函數(shù).則

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)任意的x1,x2

S,有

(f(x2)-

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

嚴格凸當(dāng)且僅當(dāng)對任意相異的x1,x2

S,(f(x2)-

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

2023/8/19TPSHUAI106TPSHUAI1062.凸集與凸函數(shù)Th2.16*.TPSHUAI1072.

凸集與凸函數(shù)2023/8/19TPSHUAI107TPSHUAI1072.凸集與凸函數(shù)2023/8/5TPTPSHUAI1082.

凸集與凸函數(shù)Def2.11.設(shè)S是Rn

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

的函數(shù)則

f(x)

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

f(x*),和

n

n

(Hessian)矩陣

H(x*),及函數(shù)

:Rn

R

使得對所有的

x

S,f(x)=f(x*)+

f(x*)(x-x*)+0.5(x-x*)H(x*)(x-x*)+||x-x*||

(x-x*)其中l(wèi)im

(x-x*)=0.2x*x*x

x*Th2.17設(shè)S是

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

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

f(x)

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

是嚴格凸函數(shù)當(dāng)且僅當(dāng)S上每一點的Hessian矩陣是正定的.2023/8/19TPSHUAI108TPSHUAI1082.凸集與凸函數(shù)Def2.11.TPSHUAI109凸規(guī)劃2.

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

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

403x+2y

50

x,y

0.極小化目標函數(shù)可行區(qū)域（單純形）可行解2.線性規(guī)劃-

例子-食譜問題2023/8/19TPSHUAI113TPSHUAI113令x表示要買的奶的量，y為要買的蛋的量TPSHUAI1141標準形式矩陣表示其中A是m

n矩陣，c是n維行向量，b是m維列向量。注：為計算需要，一般假設(shè)b

0.否則，可在方程兩端乘以(-1)即可化為非負。2.線性規(guī)劃-形式2023/8/19TPSHUAI114TPSHUAI1141標準形式矩陣表示其中A是mn矩陣，TPSHUAI115任意非標準形式均可化為標準形式，如引入松弛變量xn+1，xn+2,…xn+m.2.線性規(guī)劃-形式2023/8/19TPSHUAI115TPSHUAI115任意非標準形式均可化為標準形式，如引入TPSHUAI116則有2.線性規(guī)劃-形式2023/8/19TPSHUAI116TPSHUAI116則有2.線性規(guī)劃-形式2023/8/5TPSHUAI117Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.例如，考慮食譜問題2.圖解法當(dāng)自變量個數(shù)少于3時,可以用較簡便的方法求解.2.線性規(guī)劃-圖解法2023/8/19TPSHUAI117TPSHUAI117Min3x+2.5y例如，考慮食TPSHUAI11830104020501020304050yx03x+2.5y2x+4y

403x+2y

50(15,2.5)可行區(qū)域的極點：(0,25)(15,2.5)最優(yōu)解(20,0)Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.2.線性規(guī)劃-圖解法2023/8/19TPSHUAI118TPSHUAI1183010402050102030405TPSHUAI1193基本性質(zhì)3.1線性規(guī)劃的可行域定理

2.2

線性規(guī)劃的可行域是凸集.3.2最優(yōu)極點觀察上例，最優(yōu)解在極點(15,2.5)達到，我們有如下事實:線性規(guī)劃若存在最優(yōu)解,則最優(yōu)解一定可在某極點上達到.2.線性規(guī)劃-性質(zhì)12023/8/19TPSHUAI119TPSHUAI1193基本性質(zhì)定理2.2線性規(guī)劃的TPSHUAI120考察線性規(guī)劃的標準形式(2.2)根據(jù)表示定理，任意可行點x可表示為2.線性規(guī)劃-性質(zhì)22023/8/19TPSHUAI120TPSHUAI120考察線性規(guī)劃的標準形式(2.2)根據(jù)TPSHUAI121把x的表達式代入(2.2),得等價的線性規(guī)劃:2.線性規(guī)劃-性質(zhì)32023/8/19TPSHUAI121TPSHUAI121把x的表達式代入(2.2),得等價的TPSHUAI122于是,問題簡化成在(2.6)中令顯然,當(dāng)時目標函數(shù)取極小值.2.線性規(guī)劃-性質(zhì)42023/8/19TPSHUAI122TPSHUAI122于是,問題簡化成在(2.6)中令顯然,TPSHUAI123因此極點x(p)是問題(2.2)的最優(yōu)解.即(2.5)和(2.8)是(2.4)的最優(yōu)解,此時2.線性規(guī)劃-性質(zhì)52023/8/19TPSHUAI123TPSHUAI123因此極點x(p)是問題(2.2)的最優(yōu)TPSHUAI1242,若(2.2)存在有限最優(yōu)解,則目標數(shù)的最優(yōu)值可在某極點達到.定理2.3設(shè)線性規(guī)劃(2.2)的可行域非空,則1,(2.2)存在最優(yōu)解的充要條件是所有(j)cd非負,其中是可行域的極方向d(j)2.線性規(guī)劃-性質(zhì)62023/8/19TPSHUAI124TPSHUAI1242,若(2.2)存在有限最優(yōu)解,則目TPSHUAI1254最優(yōu)基本可行解前面討論知道們最優(yōu)解可在極點達到，而極點是一幾何概念，下面從代數(shù)的角度來考慮。不失一般性,設(shè)rank(A)=m,A=[B,N],B是m階可逆的.2.線性規(guī)劃-性質(zhì)72023/8/19TPSHUAI125TPSHUAI1254最優(yōu)基本可行解前面討論知道們最優(yōu)解可TPSHUAI126于是,Ax=b可寫為于是特別的令Nx=0,則2.線性規(guī)劃-性質(zhì)82023/8/19TPSHUAI126TPSHUAI126于是,Ax=b可寫為于是特別的令Nx=TPSHUAI127稱為方程組Ax=b的一個基本解.定義2.6B稱為基矩陣,的各分量稱為基變量.xB基變量的全體稱為一組基.的各分量稱為非基變量.xN為約束條件Ax=b,x0的一個基本可行解.B稱為可行基矩陣稱為一組可行基.2.線性規(guī)劃-性質(zhì)92023/8/19TPSHUAI127TPSHUAI127稱為方程組Ax=b的一個基本解.定義2TPSHUAI128Bb>0,稱基本可行解是非退化的,若-1若Bb

0,-1且至少有一個分量為0,稱基本可行解是退化的.2.線性規(guī)劃-性質(zhì)102023/8/19TPSHUAI128TPSHUAI128Bb>0,稱基本可行解是非退化的TPSHUAI1292.線性規(guī)劃-性質(zhì)112023/8/19TPSHUAI129TPSHUAI1292.線性規(guī)劃-性質(zhì)112023/8/5TPSHUAI1302.線性規(guī)劃-性質(zhì)122023/8/19TPSHUAI130TPSHUAI1302.線性規(guī)劃-性質(zhì)122023/8/5TPSHUAI1312.線性規(guī)劃-性質(zhì)132023/8/19TPSHUAI131TPSHUAI1312.線性規(guī)劃-性質(zhì)132023/8/5TPSHUAI132容易知道,基矩陣的個數(shù)是有限的,因此基本解從而基本可行解的個數(shù)也是有限的,不超過2.線性規(guī)劃-性質(zhì)142023/8/19TPSHUAI132TPSHUAI132容易知道,基矩陣的個數(shù)是有限的,因此基TPSHUAI133定理2.4令K={x|Ax=b,x

0},A是m×n矩陣,r(A)=m則K的極點集與Ax=b,x

0的基本可行解集合等價.證明:(提綱)1)設(shè)x是K的極點,則x是Ax=b,x

0的基本可行解.2)設(shè)x是Ax=b,x

0的基本可行解,則x是K的極點.2.線性規(guī)劃-性質(zhì)152023/8/19TPSHUAI133TPSHUAI133定理2.4令K={x|Ax=b,TPSHUAI1341),先證極點x的正分量所對應(yīng)的A的列線性無關(guān).2.線性規(guī)劃-性質(zhì)162023/8/19TPSHUAI134TPSHUAI1341),先證極點x的正分量所對應(yīng)的A的列TPSHUAI1352.線性規(guī)劃-性質(zhì)172023/8/19TPSHUAI135TPSHUAI1352.線性規(guī)劃-性質(zhì)172023/8/5TPSHUAI1362.線性規(guī)劃-性質(zhì)182023/8/19TPSHUAI136TPSHUAI1362.線性規(guī)劃-性質(zhì)182023/8/5TPSHUAI1372)設(shè)x是Ax=b,x

0的基本可行解,記2.線性規(guī)劃-性質(zhì)192023/8/19TPSHUAI137TPSHUAI1372)設(shè)x是Ax=b,x0的基本可行解TPSHUAI138即2.線性規(guī)劃-性質(zhì)202023/8/19TPSHUAI138TPSHUAI138即2.線性規(guī)劃-性質(zhì)202023/8/TPSHUAI139總結(jié),線性規(guī)劃存在最優(yōu)解,目標函數(shù)的最優(yōu)值一定能在某極點上達到.可行域K={x|Ax=b,x

0}的極點就是其基本可行解.

從而,求線性規(guī)劃的最優(yōu)解,只需要求出最優(yōu)基本可行解即可.2.線性規(guī)劃-性質(zhì)212023/8/19TPSHUAI139TPSHUAI139總結(jié),線性規(guī)劃存在最優(yōu)解,目標函數(shù)的最TPSHUAI1405基本可行解的存在問題定理2.5

若Ax=b,x

0有可行解,則一定存在基本可行解,其中A是秩為m的m

n矩陣.2.線性規(guī)劃-性質(zhì)222023/8/19TPSHUAI140TPSHUAI1405基本可行解的存在問題定理2.5TPSHUAI141否則,我們通過如下步驟構(gòu)造出一基本可行解2.線性規(guī)劃-性質(zhì)232023/8/19TPSHUAI141TPSHUAI141否則,我們通過如下步驟構(gòu)造出一基本可行TPSHUAI1422.線性規(guī)劃-性質(zhì)242023/8/19TPSHUAI142TPSHUAI1422.線性規(guī)劃-性質(zhì)242023/8/5最優(yōu)化理論與算法帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@,Tel:62281308,Rm:主樓814§4，線性規(guī)劃的單純形方法2023/8/19TPSHUAI143最優(yōu)化理論與算法帥天平2023/8/5TPSHUAI143第三章單純形方法1，單純形方法原理2，兩階段法和大Mf法3，退化情形4，修正單純形方法2023/8/19TPSHUAI144第三章單純形方法1，單純形方法原理2023/8/5TPS單純形法的基本思路

是有選擇地?。ǘ皇敲杜e所有的）基本可行解，即是從可行域的一個頂點出發(fā)，沿著可行域的邊界移到另一個相鄰的頂點，要求新頂點的目標函數(shù)值不比原目標函數(shù)值差，如此迭代，直至找到最優(yōu)解，或判定問題無界。

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

3.1線性規(guī)劃-單純形方法1怎么判斷達到最優(yōu)解?如何給出初始基可行解?迭代如何進行?2023/8/19TPSHUAI145單純形法的基本思路是有選擇地?。ǘ皇敲杜e所有的）基本可行

3.1線性規(guī)劃-單純形方法2給定標準形式的LP利用分塊矩陣2023/8/19TPSHUAI1463.1線性規(guī)劃-單純形方法2給定標準形式的LP利用分塊矩陣3.1線性規(guī)劃-單純形方法3于是目標函數(shù)于是有

基本可行解x與基B關(guān)聯(lián);2023/8/19TPSHUAI1473.1線性規(guī)劃-單純形方法3于是目標函數(shù)于是有基本可行解x3.線性規(guī)劃-單純形方法4于是我們有如下定理：2023/8/19TPSHUAI1483.線性規(guī)劃-單純形方法4于是我們有如下定理：2023/8/3.1.線性規(guī)劃-單純形方法5由上知,要減少費用,只有當(dāng)C0時才可能，即2023/8/19TPSHUAI1493.1.線性規(guī)劃-單純形方法5由上知,要減少費用,只有當(dāng)3.1線性規(guī)劃-單純形方法6令y=x+

d,>0,我們能降低費用嗎？2023/8/19TPSHUAI1503.1線性規(guī)劃-單純形方法6令y=x+d,>0,3.1線性規(guī)劃-單純形方法72023/8/19TPSHUAI1513.1線性規(guī)劃-單純形方法72023/8/5TPSHUAI3.1線性規(guī)劃-單純形方法82023/8/19TPSHUAI1523.1線性規(guī)劃-單純形方法82023/8/5TPSHUAI3.1線性規(guī)劃-單純形方法9正確性如何？顯然按上述取法，是可以保證y≥0的。y還是基本可行解嗎？2023/8/19TPSHUAI1533.1線性規(guī)劃-單純形方法9正確性如何？2023/8/5TP3.1線性規(guī)劃-單純形方法102023/8/19TPSHUAI1543.1線性規(guī)劃-單純形方法102023/8/5TPSHUA3.1線性規(guī)劃-單純形方法11單純形法2023/8/19TPSHUAI1553.1線性規(guī)劃-單純形方法11單純形法2023/8/5TP3.1線性規(guī)劃-單純形方法12Th3.4(單純形法的收斂性）對于相容的非退化(每個基可行解都是非退的)LP問題，那么經(jīng)過有限次迭代后，單純形法或者得到最優(yōu)的BFS(最優(yōu)可行基B）或有一個方向d:且最優(yōu)的費用為-∞.2023/8/19TPSHUAI1563.1線性規(guī)劃-單純形方法12Th3.4(單純形法的收斂性）3.1線性規(guī)劃-單純形方法13例12023/8/19TPSHUAI1573.1線性規(guī)劃-單純形方法13例12023/8/5TPSH3.1線性規(guī)劃-單純形方法142023/8/19TPSHUAI1583.1線性規(guī)劃-單純形方法142023/8/5TPSHUA3.1線性規(guī)劃-單純形方法15Tc

=(0702-300)2023/8/19TPSHUAI1593.1線性規(guī)劃-單純形方法15Tc=(07023.1線性規(guī)劃-單純形方法162023/8/19TPSHUAI1603.1線性規(guī)劃-單純形方法162023/8/5TPSHUA3.1線性規(guī)劃-單純形方法172023/8/19TPSHUAI1613.1線性規(guī)劃-單純形方法172023/8/5TPSHUA3.1線性規(guī)劃-單純形方法182023/8/19TPSHUAI1623.1線性規(guī)劃-單純形方法182023/8/5TPSHUA3.1線性規(guī)劃-單純形方法19新的基為B=(A1,A3,A4,A7)2023/8/19TPSHUAI1633.1線性規(guī)劃-單純形方法19新的基為B=(A1,A3,3.1線性規(guī)劃-單純形方法202023/8/19TPSHUAI1643.1線性規(guī)劃-單純形方法202023/8/5TPSHUA3.1線性規(guī)劃-單純形方法21新的基為B=(A3,A4,A5,A7)2023/8/19TPSHUAI1653.1線性規(guī)劃-單純形方法21新的基為B=(A3,A4,

3.1線性規(guī)劃-單純形方法22利用分塊矩陣表格形式的單純形方法2023/8/19TPSHUAI1663.1線性規(guī)劃-單純形方法22利用分塊矩陣表格形式的單純形

3.1線性規(guī)劃-單純形方法232023/8/19TPSHUAI1673.1線性規(guī)劃-單純形方法232023/8/5TPSHU3.1線性規(guī)劃-單純形方法240

Im

10ff右端2023/8/19TPSHUAI1683.1線性規(guī)劃-單純形方法240Im3.1線性規(guī)劃-單純形方法25進基變量離基變量旋轉(zhuǎn)元右端向量返回單純形表2023/8/19TPSHUAI1693.1線性規(guī)劃-單純形方法25進基變量離基變量旋轉(zhuǎn)元右端向量例2：求解線性規(guī)劃問題化成標準化形式

3.1線性規(guī)劃-單純形方法26

2023/8/19TPSHUAI170例2：求解線性規(guī)劃問題化成標準化形式

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

3.1線性規(guī)劃-單純形方法282023/8/19TPSHUAI1720-4-2-2-1-860102-1101-11141100例3：求解線性規(guī)劃問題3.1線性規(guī)劃-單純形方法292023/8/19TPSHUAI173例3：求解線性規(guī)劃問題3.1線性規(guī)劃-單純形方法292023.1線性規(guī)劃-單純形方法302023/8/19TPSHUAI1743.1線性規(guī)劃-單純形方法302023/8/5TPSHUAx3進基，x6離基3.1單純形方法312023/8/19TPSHUAI175x3進基，x6離基3.1單純形方法312023/8/5TP初始單純型表最優(yōu)單純型表2023/8/19TPSHUAI176初始單純型表最優(yōu)單純型表2023/8/5TPSHUAI173.2兩階段法&大M法1單純形法三要素：初始基本可行解，解的迭代，最優(yōu)性檢驗后兩個已解決,現(xiàn)考慮如何獲得一個初始基可行解.（一）兩階段法設(shè)標準LP為2023/8/19TPSHUAI1773.2兩階段法&大M法1單純形法三要素：（一）兩階段法設(shè)標3.2兩階段法&大M法2若系數(shù)矩陣中有一個單位矩陣，則容易得到初始基可行解.所以我們希望幸運的碰到這種矩陣.沒有的話，硬性加一個？2023/8/19TPSHUAI1783.2兩階段法&大M法2若系數(shù)矩陣中有一個單位矩陣，則容易3.2兩階段法&大M法3問題是如何由(3.2.3)的初始可行解獲得原來LP的一個初始可行解？為此，考慮如下輔助LP(第一階段)2023/8/19TPSHUAI1793.2兩階段法&大M法3問題是如何由(3.2.3)的初始可如果原問題有可行解，則輔助問題的最優(yōu)值為0，反之亦然。就可以得到輔助問題的初始基可行解2．由于，所以以為基變量，,同時所以一定有最小值.3.2兩階段法&大M法4關(guān)系?2023/8/19TPSHUAI180如果原問題有可行解，則輔助問題的最優(yōu)值為0，反之亦然。就可以3.2兩階段法&大M法5利用單純形法求得一個最優(yōu)可行解.這個解將會給我們帶來什么？2023/8/19TPSHUAI1813.2兩階段法&大M法5利用單純形法求得一個最優(yōu)可行解.這3.2兩階段法&大M法6于是我們獲得一個初始基可行解,從而可以以此基可行解出發(fā)利用單純形法求出最優(yōu)解.第一階段：不考慮原LP問題是否有基可行解，添加人工變量，構(gòu)造僅含人工變量的目標函數(shù)，得輔助規(guī)劃(3.2.4)單純型法求解上述模型，若有目標函數(shù)=0，說明原問題存在初始基本可行解，轉(zhuǎn)入第二階段。否則，原問題無可行解，計算停止。

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

階段首先引入人工變量，構(gòu)造輔助規(guī)劃問題如果以為基變量，則可以得到該問題的BFS,其對應(yīng)的單純形表為2023/8/19TPSHUAI1843.2兩階段法&大M法8第1

階段首先引入人工變量，構(gòu)造3.2兩階段法&大M法9-50-210000000000-1-101-16-101021120-1011RHS-50-2100000208-1-10031-16-101021120-1011gzgz2023/8/19TPSHUAI1853.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/21