北郵最優(yōu)化課件5對(duì)偶理論與靈敏度分析

最優(yōu)化理論與算法帥天平北京郵電大學(xué)數(shù)學(xué)系§5，對(duì)偶理論與靈敏度分析2023/5/3最優(yōu)化理論2第四章對(duì)偶理論與靈敏度分析對(duì)偶理論對(duì)偶單純形法原始-對(duì)偶算法靈敏度分析2023/5/3最優(yōu)化理論34.對(duì)偶問題

重新考慮食譜問題。以出售奶和蛋給需要維生素的人的食品雜貨商的利益出發(fā)，他知道奶和蛋按其維生素Vc和Vb的含量而有一定的價(jià)值。他的問題是確定出售維生素Vc的價(jià)格x和維生素Vb的價(jià)格y：他不能將價(jià)格訂得高于奶和蛋的市場流行價(jià)，否則將失去他的顧客；他希望商店的總收入為最大。維生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250單價(jià)(US$)32.52023/5/3最優(yōu)化理論44.

對(duì)偶問題（續(xù)一）Max40x+50ys.t.2x+3y34x+2y

2.5

x,y

0.極大化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.極小化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解2023/5/3最優(yōu)化理論54.

對(duì)偶問題（續(xù)二）

對(duì)比一下從消費(fèi)者和供應(yīng)商各自的利益導(dǎo)出的兩個(gè)問題，我們不難發(fā)現(xiàn)兩個(gè)問題可以通過下述簡單的變換，而相互轉(zhuǎn)化：極小化費(fèi)用Min

大于等于約束食品費(fèi)用

極大化利潤Max小于等于約束

價(jià)格約束

當(dāng)你把食譜問題的對(duì)偶問題解出以后（練習(xí)），你會(huì)發(fā)現(xiàn)一個(gè)（重要的）事實(shí)：這兩個(gè)問題的最優(yōu)值是相等的！思考題：在數(shù)學(xué)上，是不是還有一些對(duì)偶的問題和概念？2023/5/3最優(yōu)化理論64.對(duì)偶理論14.1LP的對(duì)偶理論P(yáng)rimalMincx s.t.Axb,(4.1.1)

x0DualMaxwb s.t.wAc,(4.1.2)

w04.1.1對(duì)偶問題的表達(dá)1,對(duì)稱形式的對(duì)偶2,非對(duì)稱形式的對(duì)偶PrimalMincx s.t.Ax=b,

x0DualMaxwb s.t.wAc,

w

無約束(4.1.3)(4.1.4)2023/5/3最優(yōu)化理論74.對(duì)偶理論23,一般形式的對(duì)偶Primal化為等價(jià)的標(biāo)準(zhǔn)形式2023/5/3最優(yōu)化理論84.對(duì)偶理論3寫成矩陣形式按非對(duì)稱對(duì)偶的定義,得上述LP的對(duì)偶問題2023/5/3最優(yōu)化理論94.對(duì)偶理論4于是原LP的對(duì)偶(Dual)2023/5/3最優(yōu)化理論104.對(duì)偶理論5以上分析可知有如下關(guān)系2023/5/3最優(yōu)化理論114.對(duì)偶理論6引理1

對(duì)偶問題的對(duì)偶是原始問題

(Thedualofthedualistheprimal.)2023/5/3最優(yōu)化理論124.對(duì)偶理論7即得原問題2023/5/3最優(yōu)化理論134.對(duì)偶理論9例4.1.2設(shè)原問題2023/5/3最優(yōu)化理論144.對(duì)偶理論10例4.1.2設(shè)原問題2023/5/3最優(yōu)化理論154.對(duì)偶理論11例4.1.3設(shè)原問題2023/5/3最優(yōu)化理論164.對(duì)偶理論12于是可得對(duì)偶問題2023/5/3最優(yōu)化理論174.對(duì)偶理論135.1.2對(duì)偶定理注意到,原問題和對(duì)偶問題是由同一數(shù)據(jù)集(A,b,c)所定義，且對(duì)偶問題的對(duì)偶即是原問題，因此可以選原始-對(duì)偶對(duì)中任一為原問題，而另一則自動(dòng)為對(duì)偶。下面討論兩者間的關(guān)系。2023/5/3最優(yōu)化理論184.對(duì)偶理論14推論2對(duì)偶規(guī)劃(4.1.1)和(4.1.2)有最優(yōu)解的充要條件是它們同時(shí)有可行解。推論3若原問題(4.1.1)的目標(biāo)函數(shù)值在可行域上無下界,則其對(duì)偶問題無可行解;反之,若對(duì)偶(4.1.2)的目標(biāo)函數(shù)值在可行域上無上界,則原問題無可行解.2023/5/3最優(yōu)化理論195.對(duì)偶理論4.對(duì)偶理論15不可行無界有限最優(yōu)解不可行無界有限最優(yōu)解PD定理4.1.2設(shè)(4.1.1)和(4.1.2)中有一個(gè)問題存在最優(yōu)解，則另一個(gè)問題也存在最優(yōu)解，且這兩個(gè)問題的最優(yōu)目標(biāo)函數(shù)值相等。證明：設(shè)(4.1.1)存在最優(yōu)解。引進(jìn)松弛變量，將（4.1.1）寫成等價(jià)形式：2023/5/3最優(yōu)化理論204.對(duì)偶理論16由于(4.1.12)存在最優(yōu)解，因此能用單純形方法求得一個(gè)最優(yōu)基本可行解。不妨設(shè)此最優(yōu)解為相應(yīng)的最優(yōu)基為B.此時(shí)所有判別數(shù)滿足：2023/5/3最優(yōu)化理論214.對(duì)偶理論17即把所有松弛變量在基Ｂ下對(duì)應(yīng)的判別數(shù)所滿足的條件(4.1.13)用矩陣表示,得2023/5/3最優(yōu)化理論224.對(duì)偶理論182023/5/3最優(yōu)化理論234.對(duì)偶理論194.1.3互補(bǔ)松弛性質(zhì)2023/5/3最優(yōu)化理論244.對(duì)偶理論202023/5/3最優(yōu)化理論254.對(duì)偶理論21例4.1.3求解如下LP2023/5/3最優(yōu)化理論264.對(duì)偶理論222023/5/3最優(yōu)化理論274.對(duì)偶理論232023/5/3最優(yōu)化理論284.對(duì)偶理論—對(duì)偶單純形法14.2對(duì)偶單純形法4.2.1對(duì)偶單純形法基本思想2023/5/3最優(yōu)化理論294.對(duì)偶理論—對(duì)偶單純形法2注:對(duì)偶可行的基本解不一定是原問題的可行解.若還是原問題的可行解,則此解即為最優(yōu)解.

回憶(修正)單純形法的基本思路是保持原問題的可行性和互補(bǔ)松弛條件下,在它的最優(yōu)解上尋求對(duì)偶問題的可行性.類似的,對(duì)偶單純形法的基本思路是:在保持對(duì)偶可行性和互補(bǔ)松弛條件下,在它的最優(yōu)解上尋求原問題的可行性.

2023/5/3最優(yōu)化理論304.對(duì)偶理論—對(duì)偶單純形法

32023/5/3最優(yōu)化理論314.對(duì)偶理論—對(duì)偶單純形法

4下面分析如何選取離基變量和進(jìn)基變量.設(shè)在某次迭代中得到如下表:2023/5/3最優(yōu)化理論324.對(duì)偶理論—對(duì)偶單純形法

52023/5/3最優(yōu)化理論334.對(duì)偶理論—對(duì)偶單純形法

62023/5/3最優(yōu)化理論344.對(duì)偶理論—對(duì)偶單純形法

7下面說明上述轉(zhuǎn)換能改進(jìn)對(duì)偶可行的基本解.2)主元消去后仍然保持對(duì)偶可行性,即所有判別數(shù)都小于或等于0(對(duì)極小化問題)2023/5/3最優(yōu)化理論354.對(duì)偶理論—對(duì)偶單純形法

82023/5/3最優(yōu)化理論364.對(duì)偶理論—對(duì)偶單純形法

9即對(duì)偶問題的目標(biāo)函數(shù)值在迭代過程中單調(diào)增(非減).對(duì)偶問題的可行解w越來越接近最優(yōu)解.原問題的對(duì)偶可行的基本解將向著滿足可行性方向轉(zhuǎn)化而接近原問題最優(yōu)解.2023/5/3最優(yōu)化理論374.對(duì)偶理論—對(duì)偶單純形法

102023/5/3最優(yōu)化理論384.對(duì)偶理論—對(duì)偶單純形法

11例12023/5/3最優(yōu)化理論394.對(duì)偶理論—對(duì)偶單純形法12

2023/5/3最優(yōu)化理論404.對(duì)偶理論—對(duì)偶單純形法

132023/5/3最優(yōu)化理論414.對(duì)偶理論—對(duì)偶單純形法

142023/5/3最優(yōu)化理論424.對(duì)偶理論—對(duì)偶單純形法

152023/5/3最優(yōu)化理論434.對(duì)偶理論—對(duì)偶單純形法164.2初始對(duì)偶可行的基本解對(duì)偶單純形法中要求先給出一個(gè)初始的對(duì)偶可行的基本解.這個(gè)解未必直接能求出,因此需要引進(jìn)一個(gè)方法—與單純形法中類似,我們也是通過解一個(gè)輔助問題---擴(kuò)充問題來求解.擴(kuò)充問題的構(gòu)造

擴(kuò)充問題的構(gòu)造:先給出(4.2.1)的一個(gè)基本解(這很容易).不妨設(shè)A的前m列線性無關(guān),由這m列構(gòu)成基矩陣B.于是(4.2.1)可改寫成

2023/5/3最優(yōu)化理論444.對(duì)偶理論—對(duì)偶單純形法17

2023/5/3最優(yōu)化理論454.對(duì)偶理論—對(duì)偶單純形法18

在(4.2.10)中以系數(shù)矩陣的前m列和第n+1列組成的m+1階單位矩陣為基,則得一個(gè)基本解2023/5/3最優(yōu)化理論464.對(duì)偶理論—對(duì)偶單純形法19上述做法是正確的,因?yàn)橹髟ミ\(yùn)算前后判別數(shù)之間有如下關(guān)系:綜上立明2023/5/3最優(yōu)化理論474.對(duì)偶理論—對(duì)偶單純形法20

注意到(4.2.10)的對(duì)偶問題有可行解,故用對(duì)偶單純形方法求解(4.2.10)時(shí),僅有如下兩種情況發(fā)生:(1)擴(kuò)充問題無可行解,則原問題亦無可行解.(反證)2023/5/3最優(yōu)化理論484.對(duì)偶理論—對(duì)偶單純形法21

例2.22023/5/3最優(yōu)化理論494.對(duì)偶理論—對(duì)偶單純形法22

于是得擴(kuò)充問題構(gòu)作單純形表2023/5/3最優(yōu)化理論504.對(duì)偶理論—對(duì)偶單純形法23

2023/5/3最優(yōu)化理論514.對(duì)偶理論—對(duì)偶單純形法24

2023/5/3最優(yōu)化理論524.對(duì)偶理論—對(duì)偶單純形法25

例2.3

2023/5/3最優(yōu)化理論534.對(duì)偶理論—對(duì)偶單純形法

26把約束矩陣置于單純形表中2023/5/3最優(yōu)化理論544.對(duì)偶理論—對(duì)偶單純形法27

2023/5/3最優(yōu)化理論554.對(duì)偶理論—對(duì)偶單純形法28

2023/5/3最優(yōu)化理論564.對(duì)偶理論—對(duì)偶單純形法

292023/5/3最優(yōu)化理論574.3原始對(duì)偶算法1基本思想這一方法實(shí)際上是由某些網(wǎng)絡(luò)問題的一個(gè)特殊算法發(fā)展起來的.構(gòu)造對(duì)偶問題考慮原問題2023/5/3最優(yōu)化理論58互補(bǔ)松弛條件是:如果x和分別是P和D的可行解,則它們是最優(yōu)解的充要條件是對(duì)一切的i和j有由于P是標(biāo)準(zhǔn)形式,故對(duì)任意可行解x,(1)總是成立的4.3原始對(duì)偶算法22023/5/3最優(yōu)化理論59下面我們集中討論關(guān)系式(2)

假定是對(duì)偶問題D的可行解,若能設(shè)法找出

P的一個(gè)可行解x,使得滿足關(guān)系式(2),即則這個(gè)x(及)是最優(yōu)的4.3原始對(duì)偶算法32023/5/3最優(yōu)化理論60對(duì)給定求這樣一個(gè)x的思想,導(dǎo)致了原始對(duì)偶算法.給定,要找這樣一個(gè)x,可以通過解由所確定的輔助問題(稱為限制的原始問題RP)而得到.當(dāng)這樣的x沒有搜索到,那么就得到RP的對(duì)偶信息(RP的對(duì)偶記為DRP),此信息告訴我們?nèi)绾涡薷?于是得到新的.重復(fù)此過程,在有限步內(nèi)就收斂到最優(yōu)解4.3原始對(duì)偶算法4原始P對(duì)偶D限制原始RP限制原始對(duì)偶DRP調(diào)整到2023/5/3最優(yōu)化理論61算法開始時(shí)是D的可行解且始終保持對(duì)偶可行性.在c0時(shí)可直接取=0為初始對(duì)偶可行解.

當(dāng)c不是非負(fù)的時(shí)候,應(yīng)用Beale等人的方法很容易的找出可行解:4.3原始對(duì)偶算法5原始對(duì)偶算法2023/5/3最優(yōu)化理論62顯然增加約束后不會(huì)改變?cè)瓎栴}P的解,此時(shí)新的原始問題的對(duì)偶為4.3原始對(duì)偶算法62023/5/3最優(yōu)化理論63中將有一些取嚴(yán)格不等式,而另一些取等式.設(shè)取等式的約束指標(biāo)集為J:4.3原始對(duì)偶算法7因此不妨設(shè)D有一可行解,則不等式約束2023/5/3最優(yōu)化理論64這即相當(dāng)于求一個(gè)x,使得滿足4.3原始對(duì)偶算法8稱J為允許列集合.為找出這樣的x,構(gòu)造新的LP,稱為限制的原始問題(RP):2023/5/3最優(yōu)化理論65利用單純形法求解此RP:若最優(yōu)值為0則已找到(6)的解,因此也是P的最優(yōu)解.若最優(yōu)值大于0,如何處理?4.3原始對(duì)偶算法92023/5/3最優(yōu)化理論66為解決此問題,需要考察限制的原始問題RP的對(duì)偶DRP4.3原始對(duì)偶算法10現(xiàn)在我們處于這樣的情形:試圖只應(yīng)用允許列來找出一個(gè)可行解x,但由于RP的最優(yōu)值>0,所以努力失敗了2023/5/3最優(yōu)化理論67這就可能考察利用原來的和新得到的來校正4.3原始對(duì)偶算法11因?yàn)镽P和DRP是一對(duì)相互對(duì)偶的規(guī)劃,所以它們的最優(yōu)值相等.因此有但是我們得到了RP的最優(yōu)解及其對(duì)偶的最優(yōu)解,2023/5/3最優(yōu)化理論68所以我們應(yīng)該選取>0,從而改進(jìn)D的費(fèi)用4.3原始對(duì)偶算法122023/5/3最優(yōu)化理論69為維持可行性,只需考察下述不等式4.3原始對(duì)偶算法13此時(shí),可行性準(zhǔn)則變?yōu)橛谑怯?023/5/3最優(yōu)化理論704.3原始對(duì)偶算法14當(dāng)解限制的原始問題并達(dá)到了改進(jìn)D的解的時(shí)候,我們重新定義集合J,然后重復(fù)上述過程直到或者opt=0并因此得到P的最優(yōu)解,或者由定理1知P無可行解.2023/5/3最優(yōu)化理論71Procedureprimal-dual4.3原始對(duì)偶算法15begininfeasible:=‘no’,opt:=‘no’letbefeasibleinD(comment:possibleby(3));

while

infeasible:=‘no’andopt:=‘no’dobeginsetsolveRPbythesimplexalgorithm

if

opt=0then

opt:=‘yes’

elseif

theninfeasible:=‘yes’

else

endend2023/5/3最優(yōu)化理論724.3原始對(duì)偶算法16我們運(yùn)用表格形式進(jìn)行迭代。初始表結(jié)構(gòu)如下：此表中原來變量xj中仍屬于限定問題中.即jJ,則用在上方標(biāo)注.解RP的進(jìn)離基運(yùn)算在標(biāo)的列和y的列進(jìn)行2023/5/3最優(yōu)化理論73限定原始問題達(dá)到最優(yōu)時(shí),若要修改對(duì)偶問題的可行解，只需把第m+1行倍加到第m+2行即可4.3原始對(duì)偶算法17求解每一限定原始問題的過程中除第m+2行外，均作運(yùn)算但只能是屬于限定原始問題的變量才有資格作為進(jìn)基變量。2023/5/3最優(yōu)化理論744.3原始對(duì)偶算法18“限定原始問題達(dá)到最優(yōu)時(shí),若要修改對(duì)偶問題的可行解，只需把第m+1行倍加到第m+2行即可”的理由下面求解上述LP。首先找出對(duì)偶問題的一個(gè)可行解。例4.3.1的對(duì)偶是：2023/5/3最優(yōu)化理論754.3原始對(duì)偶算法19于是得一階段問題顯然w=(0,0)是一個(gè)可行解，此時(shí)有2023/5/3最優(yōu)化理論764.3原始對(duì)偶算法202023/5/3最優(yōu)化理論77變量上方的標(biāo)識(shí)符表示該變量屬于RP4.3原始對(duì)偶算法21按照前述給定的格式，得初表如下2023/5/3最優(yōu)化理論784.3原始對(duì)偶算法222023/5/3最優(yōu)化理論794.3原始對(duì)偶算法23J={2},用單純形法解RP：x2進(jìn)基,y1離基.經(jīng)主元消去得下表(注：解RP時(shí)第4行不變）RP的判別數(shù)均非正,達(dá)到最優(yōu)，Z0=2>0修改對(duì)偶問題的可行解2023/5/3最優(yōu)化理論804.3原始對(duì)偶算法24此時(shí)J={1，2}，再解RP：x1進(jìn)基，y2離基.經(jīng)主元消去得下表2023/5/3最優(yōu)化理論814.3原始對(duì)偶算法25RP問題達(dá)到最優(yōu)，最優(yōu)值Z0=0，因此得原問題的最優(yōu)解

x*=(x1,x2,x3)=(2,1,0)目標(biāo)函數(shù)的最優(yōu)值fmin=5,對(duì)偶問題的最優(yōu)解w=(0,1).2023/5/3最優(yōu)化理論82824.4靈敏度分析1，引入2，改變系數(shù)向量3，改變右端向量4，改變約束矩陣5，增加新的約束2023/5/3最優(yōu)化理論8383前面講的線性規(guī)劃問題中，都假定問題中是已知常數(shù)。但實(shí)際上這些數(shù)往往是一些估計(jì)和預(yù)測的數(shù)字市場條件變化，價(jià)值變量cj就會(huì)變化aij是隨工藝技術(shù)條件的改變而改變而值bi則是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟(jì)效益來決定的一種決策選擇.

在大多數(shù)實(shí)際問題中。不僅要求求出問題的最優(yōu)解，而且還希望知道當(dāng)問題中的某些參數(shù)改變時(shí)最優(yōu)解怎樣變動(dòng)。參數(shù)的變化可分為離散的和連續(xù)的兩種。靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件離散變化顯示出來的敏感程度的分析，即對(duì)最優(yōu)解的影響進(jìn)行分析研究。而參數(shù)規(guī)劃則是研究參數(shù)連續(xù)的變化時(shí)對(duì)最優(yōu)解的影響1引入2023/5/3最優(yōu)化理論8484這就是靈敏度分析所要研究解決的問題。因此就會(huì)提出以下問題：當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題的最優(yōu)解會(huì)有什么變化?這些參數(shù)在一個(gè)多大范圍內(nèi)變化時(shí)，問題的最優(yōu)解變不變?影響最優(yōu)解的參數(shù)有如下幾類：改變費(fèi)用系數(shù)cj改變右端費(fèi)用bi改變約束方程的系數(shù)矩陣A加入新的約束參數(shù)變化后的結(jié)果最優(yōu)解不變：最優(yōu)基及其取值不變基變量不變但取值改變基變量改變，取值亦改變2023/5/3最優(yōu)化理論8585原問題

對(duì)偶問題

結(jié)論或繼續(xù)計(jì)算的步驟

可行解可行解非可行解非可行解

可行解非可行解可行解非可行解

問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解原始/對(duì)偶單純形算法或引進(jìn)人工變量，編制新的單純形表重新計(jì)算

重新解新線性規(guī)劃問題？重新計(jì)算發(fā)生變化的個(gè)別系數(shù),判斷問題現(xiàn)狀,采取如下措置2023/5/3最優(yōu)化理論8686考慮標(biāo)準(zhǔn)LP問題為RHS

0假定得到最優(yōu)單純形表如下(4.4.1)2改變系數(shù)向量c

2023/5/3最優(yōu)化理論8787當(dāng)價(jià)值向量c改變時(shí),在單純形表里受影響的只是檢驗(yàn)數(shù)和目標(biāo)函數(shù)值，其它沒有改變，因而只需計(jì)算新的檢驗(yàn)數(shù)和目標(biāo)函數(shù)值如果檢驗(yàn)數(shù)非正，則原最優(yōu)解依然是最優(yōu)解；否則是基本可行解，以此為初始基可行解按單純形法進(jìn)行迭代就可以求出新問題的解。2023/5/3最優(yōu)化理論88881、情形I:是非基變量改變非基變量的價(jià)值向量：若，由單純形法計(jì)算公式知，只有檢驗(yàn)數(shù)起變化,則原最優(yōu)解依然是最優(yōu)解；否則,由此進(jìn)行單純形迭代。即價(jià)值向量只有一個(gè)分量新的檢驗(yàn)數(shù)2023/5/3最優(yōu)化理論89892、情形II:是基變量基變量對(duì)應(yīng)的約束為第L個(gè),即改變基變量的價(jià)值向量,問題最后一張單純形表中，新檢驗(yàn)數(shù)(因基變量檢驗(yàn)數(shù)要求＝0)新目標(biāo)函數(shù)值把單純形表上的第L行元素乘以加到檢驗(yàn)數(shù)行上，再令得到對(duì)應(yīng)新問題的單純形表?？傊?023/5/3最優(yōu)化理論9090例1最優(yōu)解:(x1,x2,x3,x4,x5,x6)=(5,3,1,0,0,0)2023/5/3最優(yōu)化理論9191檢驗(yàn)數(shù)仍非負(fù),問題原最優(yōu)解仍是此時(shí)最優(yōu)解;更多信息:對(duì)非基變量的價(jià)值系數(shù)在某范圍變化最優(yōu)解都不發(fā)生改變最優(yōu)解都不發(fā)生改變最優(yōu)解都不發(fā)生改變同理最優(yōu)解都不發(fā)生改變非基變量2023/5/3最優(yōu)化理論9292

x1

x2

x3

x4

x5

x6

RHS

z

0

0

0

0

-1

0

-18

x2

0

1

0

1/4

0

-1/4

3

x1

1

0

0

-1/6

1/3

1/2

5

x3

0

0

1

5/12

-1/3

1/4

1

若檢驗(yàn)數(shù)向量非負(fù)數(shù)，而右端向量沒變，故仍最優(yōu)解，否則用單純形算法即可?；兞堪炎顑?yōu)單純形表的第3行乘以[1-(-1)]加到檢驗(yàn)數(shù)行上再令得到對(duì)應(yīng)新問題的單純形表2023/5/3最優(yōu)化理論93931.基本思想RHS

0如果，則已發(fā)現(xiàn)新問題的最優(yōu)解，否則利用對(duì)偶單純形算法求解新問題。3改變右端向量b2023/