這一部分對(duì)應(yīng)書(shū)上第七章(P45-P51),難度和第四章差不多首繁。由于引用了一些非數(shù)學(xué)的概念夯膀,所以學(xué)習(xí)的時(shí)候難免會(huì)遇到一些看似無(wú)所根據(jù)的概念或者假設(shè)。建議大家不要在各種花里胡哨的假設(shè)上浪費(fèi)時(shí)間日裙,要把精力留給數(shù)學(xué)。
雖然線性規(guī)劃的對(duì)偶理論在線性代數(shù)和數(shù)學(xué)模型中都沒(méi)怎么被提到惰蜜,但其理論本身有趣而且有用昂拂。對(duì)偶理論將原LP問(wèn)題轉(zhuǎn)化為其對(duì)偶LP問(wèn)題,從而使與原問(wèn)題相關(guān)的一些復(fù)雜的性質(zhì)(如解是否為最優(yōu))變?yōu)閷?duì)偶問(wèn)題中較為簡(jiǎn)單的性質(zhì)(對(duì)應(yīng)地抛猖,解是否可行)格侯。
第五章和第六章暫時(shí)沒(méi)有講。 第五章主要是線性代數(shù)的內(nèi)容财著,在此默認(rèn)大家都學(xué)過(guò)联四。需要看一眼的是最后提到的用矩陣表示LP問(wèn)題的方法。第六章是敏感性分析撑教,我打算留到最后和算法復(fù)雜度一起講朝墩。
為方便查閱,再link一下教材伟姐。
基本概念
為方便理解我們引入一個(gè)例子:
例1: 現(xiàn)有一工廠可以生產(chǎn)小人偶和小火車這兩種玩具收苏。生產(chǎn)一個(gè)小人偶需要1單位木材和2單位顏料亿卤,產(chǎn)生3單位收益。生產(chǎn)一輛小火車需要1單位木材和1單位顏料鹿霸,產(chǎn)生2單位收益排吴。工廠現(xiàn)有80單位木材和100單位顏料,問(wèn)如何分配火車與人偶的生產(chǎn)量可以使得收益最大懦鼠?(見(jiàn)下圖左側(cè))
先補(bǔ)充幾個(gè)前幾章出現(xiàn)過(guò)但我沒(méi)有提到的簡(jiǎn)單概念钻哩。由于沒(méi)有了解過(guò)中文版教材所以翻譯可能不太準(zhǔn)確。
- 對(duì)象(Item)是LP問(wèn)題中的“名詞”肛冶,即收益和材料憋槐。在此問(wèn)題中,對(duì)象有三個(gè)淑趾,即:收益阳仔、木材、顏料扣泊。對(duì)象對(duì)應(yīng)著LP問(wèn)題中的行近范。在此問(wèn)題中,收益延蟹、木材與顏料分別對(duì)應(yīng)著第一到第三行评矩。
-
行為(Activity)是LP問(wèn)題中的“動(dòng)詞”,對(duì)應(yīng)著標(biāo)準(zhǔn)表示中的列阱飘。通俗地講斥杜,行為就是將材料轉(zhuǎn)化為產(chǎn)品(收益)的過(guò)程。在本問(wèn)題中沥匈,制造小火車與制造小人偶就是兩種行為蔗喂。上圖中,
所在的列對(duì)應(yīng)著制造小人偶的行為高帖,
所在的列對(duì)應(yīng)著制造小火車的行為缰儿。
回憶上一次在基本概念中講到的基本解與字典的概念,結(jié)合線性代數(shù)的知識(shí)散址,我們可以將LP問(wèn)題寫為:
不要被上圖中復(fù)雜的形式迷惑乖阵,其實(shí)推導(dǎo)過(guò)程非常簡(jiǎn)單。式中各個(gè)符號(hào)的定義見(jiàn)教材第32頁(yè)预麸。需要強(qiáng)調(diào)的兩點(diǎn)是:
-
是由非基本變量構(gòu)成的向量瞪浸,在具體取值的時(shí)候即為0向量。詳見(jiàn)之前對(duì)非基本變量的定義吏祸。注意不要將非基本變量理解為0變量对蒲。非基本變量只是在考慮對(duì)應(yīng)基本解時(shí)取值為0。
- 此處假設(shè)
是可逆的,但我無(wú)法證明
一定是可逆的齐蔽。但我相信大多數(shù)情況下
都是可逆的两疚,因?yàn)樵谧值渲?img class="math-inline" src="https://math.jianshu.com/math?formula=x_%7BB%7D" alt="x_{B}" mathimg="1">可有
表示,而聯(lián)系二者的只有等式
含滴。如果
不滿秩的話會(huì)丟失
的信息進(jìn)而使得
無(wú)法被
表示诱渤。(直觀感受,未證明)
- 基本解對(duì)應(yīng)的目標(biāo)函數(shù)的取值為
谈况,當(dāng)
的各項(xiàng)系數(shù)小于0時(shí)取最優(yōu)解勺美。此時(shí)基本變量的取值為
目標(biāo)函數(shù)的值(
)和判斷最優(yōu)解的條件(
)這兩個(gè)矩陣表示非常重要,建議各位同學(xué)自己推導(dǎo)一遍并記下來(lái)碑韵。
現(xiàn)在假設(shè)在市場(chǎng)上有以價(jià)格與
售賣的木材與顏料赡茸,如上圖右側(cè)所示。市場(chǎng)是一個(gè)很有趣的概念祝闻,可惜我不怎么懂占卧,只知道本章許多內(nèi)容都與之多多少少地相關(guān)。接下來(lái)介紹一個(gè)比較重要的概念联喘。
-
影子價(jià)格(百度百科): 某種材料的影子價(jià)格通俗地講就是該種材料增加1單位所帶來(lái)的額外的收益华蜒。
當(dāng)某種材料過(guò)剩時(shí),其影子價(jià)格即為0豁遭,因?yàn)樵摬牧媳緛?lái)就多于所需叭喜,所以它的增加不帶來(lái)額外收益。 關(guān)于影子價(jià)格蓖谢,需要注意以下兩點(diǎn):- 影子價(jià)格的定義嚴(yán)格地講是收益關(guān)于某種材料的變化率捂蕴,但由于我們考慮的是線性問(wèn)題所以干脆說(shuō)成是“由于增添1單位某材料所帶來(lái)的額外收益”。影子價(jià)格是一個(gè)局部的概念闪幽,不要鉆牛角尖啥辨。
- 書(shū)上沒(méi)有任何解釋地給出了影子價(jià)格的矩陣表示:
。其實(shí)這就是一個(gè)簡(jiǎn)單的求導(dǎo)運(yùn)算沟使。對(duì)比目標(biāo)函數(shù)的值:
可以發(fā)現(xiàn)某種材料的影子價(jià)格恰好就是目標(biāo)函數(shù)關(guān)于該材料的導(dǎo)數(shù)委可。需要注意的是此時(shí)由于材料可以自由買賣,所以
變成了一個(gè)變向量腊嗡。在某種意義上,目標(biāo)函數(shù)其實(shí)本來(lái)就是材料的函數(shù)拾酝,只不過(guò)材料的多少會(huì)影響函數(shù)的形式(
也會(huì)隨材料改變燕少。)
影子價(jià)格
是一個(gè)向量,其每個(gè)元素對(duì)應(yīng)一種材料蒿囤。
基本概念大概就是這些客们,接下來(lái)就是神奇的部分了。
對(duì)偶性理論
這一部分有許多條件并不是一般的,比如我們只討論了最大值問(wèn)題而沒(méi)研究最小值問(wèn)題底挫。不過(guò)方法的本質(zhì)都是一樣的恒傻。
1. 基本假設(shè)與直觀理解
對(duì)偶(Dual)不論是單詞還是翻譯都和泛函分析中函數(shù)空間的那種對(duì)偶一樣。事實(shí)上對(duì)偶是數(shù)學(xué)中一種非常常見(jiàn)的思想方法建邓。通過(guò)配合地研究原問(wèn)題(Primal)和對(duì)偶問(wèn)題(Dual)我們可以得到很多性質(zhì)頗好的結(jié)論盈厘。首先,我們引入一個(gè)假設(shè):
假設(shè)1: 生產(chǎn)一件產(chǎn)品所需的材料的價(jià)格不小于出售該件產(chǎn)品所帶來(lái)的收益官边。
之后我們簡(jiǎn)稱生產(chǎn)某件產(chǎn)品所需的材料的價(jià)格為該產(chǎn)品的材料成本沸手。對(duì)于該假設(shè)我們可以作如下理解:
- 首先,我們引入的所有假設(shè)的目的都是為了解原LP問(wèn)題注簿,故引入新的變量不能改變?cè)璍P問(wèn)題的最大值契吉。只對(duì)數(shù)學(xué)模型感興趣的同學(xué)可以直接跳過(guò)之后的三點(diǎn)。
- 假設(shè)在此問(wèn)題中诡渴,工廠本來(lái)就有一定數(shù)量的各種材料捐晶。生產(chǎn)一件產(chǎn)品的成本不包括材料成本。
- 在此假設(shè)下妄辩,購(gòu)入更多的原材料只會(huì)使總收益變少惑灵,所以原LP問(wèn)題的最大值不變。
- 如果該假設(shè)不成立恩袱,那么該工廠就可以從市場(chǎng)中無(wú)限地買入原材料進(jìn)而獲得無(wú)限的利益泣棋。由于市場(chǎng)存在競(jìng)爭(zhēng),這種情況是不允許出現(xiàn)的畔塔。
其實(shí)在思考本假設(shè)的意義時(shí)我也有很多疑問(wèn)潭辈,當(dāng)然可能我現(xiàn)在對(duì)于此問(wèn)題的理解仍然是錯(cuò)誤的细移。我們不妨先默認(rèn)這些看似不合理直觀的假設(shè)屉佳,推得我們想要的理論,之后再嚴(yán)謹(jǐn)?shù)赜脭?shù)學(xué)方法證明理論的合理性即可蜈亩。當(dāng)然谅辣,感興趣的同學(xué)也可以參考經(jīng)濟(jì)學(xué)領(lǐng)域的相關(guān)書(shū)籍修赞。
不論如何,我們不應(yīng)在直觀理解上浪費(fèi)太多時(shí)間桑阶。我們現(xiàn)在引出原問(wèn)題與對(duì)偶問(wèn)題的形式:
左邊為原問(wèn)題柏副,右邊為對(duì)偶問(wèn)題。首先可以注意到的是對(duì)偶問(wèn)題的限制條件即假設(shè)1蚣录。此時(shí)有顯然的關(guān)系式:左邊的不等號(hào)對(duì)應(yīng)于對(duì)偶問(wèn)題的限制條件割择,右邊的不等號(hào)則對(duì)應(yīng)原問(wèn)題的對(duì)偶條件。因此兩邊目標(biāo)函數(shù)存在關(guān)系:
是顯然的萎河。這其實(shí)就是待會(huì)要提到的弱對(duì)偶性荔泳。
原問(wèn)題與對(duì)偶問(wèn)題的矩陣表示如下圖所示:
由此可知對(duì)偶問(wèn)題的對(duì)偶問(wèn)題就是原問(wèn)題蕉饼。即兩問(wèn)題互為對(duì)偶。
2. 弱對(duì)偶性與強(qiáng)對(duì)偶性定理
關(guān)于對(duì)偶性玛歌,最關(guān)鍵的理論就是以下兩個(gè)重要的定理:
定理1 (弱對(duì)偶性) 假設(shè)
與
分別是原問(wèn)題與對(duì)偶問(wèn)題的可行解昧港,則:
證明:由限制條件可知:
證明完畢。
由弱對(duì)偶性可知:
- 若原問(wèn)題的目標(biāo)函數(shù)無(wú)界支子,則對(duì)偶問(wèn)題必?zé)o可行解创肥;同理若對(duì)偶問(wèn)題的目標(biāo)函數(shù)無(wú)界,則原問(wèn)題必?zé)o可行解译荞。注意前者的無(wú)界是無(wú)上界而后者的無(wú)界是無(wú)下界瓤的。若產(chǎn)品的收益都為正,則目標(biāo)函數(shù)無(wú)界等價(jià)于可行域無(wú)界吞歼。
- 書(shū)上說(shuō)原問(wèn)題和對(duì)偶問(wèn)題都無(wú)可行解的情況是存在的圈膏。不過(guò)我還沒(méi)有想到這樣的例子。
定理2 (強(qiáng)對(duì)偶性) 假設(shè)
與
分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解篙骡,則:
且滿足
其中
與
分別對(duì)應(yīng)著原問(wèn)題與對(duì)偶問(wèn)題中的松弛變量稽坤。
我們現(xiàn)在還無(wú)法證明這個(gè)定理。
3. 原問(wèn)題與對(duì)偶問(wèn)題的性質(zhì)
為了證明強(qiáng)對(duì)偶性定理并得到一些我們需要的性質(zhì)糯俗,在此先敘述一些相對(duì)簡(jiǎn)單的概念與結(jié)論尿褪。由于原問(wèn)題與對(duì)偶問(wèn)題實(shí)際上互為對(duì)偶,故不失一般性地可以只敘述原問(wèn)題的性質(zhì)得湘。
性質(zhì)1: 原問(wèn)題中每一個(gè)等號(hào)-限制條件都對(duì)應(yīng)一個(gè)無(wú)符號(hào)限制的對(duì)偶變量杖玲。
此處“等號(hào)-限制條件”的含義應(yīng)該是清晰的。原問(wèn)題中的每一條限制條件都對(duì)應(yīng)著一個(gè)對(duì)偶變量淘正,這一點(diǎn)大家也需要牢記摆马。強(qiáng)調(diào)以下幾點(diǎn):
- 如果原問(wèn)題中采用的是
-限制條件,則無(wú)符號(hào)限制的對(duì)應(yīng)對(duì)偶變量會(huì)導(dǎo)致弱對(duì)偶性定理失效鸿吆。因?yàn)樨?fù)號(hào)會(huì)使不等式轉(zhuǎn)向囤采。對(duì)于
-限制條件也一樣。現(xiàn)考慮例1中木材的限制條件對(duì)應(yīng)的對(duì)偶變量(即木材的價(jià)格
):
如果不要求
的話顯然無(wú)法推出
惩淳。
- 如果原問(wèn)題中的某條限制條件是等號(hào)-限制條件蕉毯,則稱該限制條件為緊(tight)的。這個(gè)概念之后還會(huì)用到思犁。
- 若原問(wèn)題中某條限制是等號(hào)-限制條件則不論對(duì)應(yīng)的對(duì)偶變量如何取值代虾,弱對(duì)偶性仍然成立。依然考慮例1中的木材激蹲,但此時(shí)將其限制條件改為等號(hào)-限制條件褐着,則有:
即仍滿足弱對(duì)偶性。
- 類比地可以總結(jié)出規(guī)律:對(duì)于一個(gè)求最大值的LP問(wèn)題托呕,
-限制條件對(duì)應(yīng)非負(fù)對(duì)偶變量含蓉;
-限制條件對(duì)應(yīng)非正對(duì)偶變量;等號(hào)-限制條件對(duì)應(yīng)無(wú)符號(hào)限制的對(duì)偶變量项郊。
接下來(lái)介紹互補(bǔ)松弛的概念馅扣。
定義1:稱向量
與
是互補(bǔ)的(complementary),若:
關(guān)于互補(bǔ)着降,有如下性質(zhì):
- 強(qiáng)對(duì)偶性說(shuō)明原問(wèn)題的最優(yōu)解與對(duì)偶問(wèn)題的解是互補(bǔ)的差油。
- 對(duì)于互補(bǔ)的向量
與
,若
則原問(wèn)題的第i個(gè)限制條件為緊的任洞。同理若
則對(duì)偶問(wèn)題的第i個(gè)限制條件是緊的蓄喇。
-
對(duì)于任意基本解
,由其定義的影子價(jià)格
與之互補(bǔ)交掏。證明如下:
命題1:對(duì)于LP問(wèn)題的任意基本解
妆偏,由其定義的影子價(jià)格
與之互補(bǔ)
證明:明天再說(shuō)!
關(guān)于互補(bǔ)松弛性盅弛,有以下幾點(diǎn)重要的性質(zhì)钱骂。先不加證明地列出:
設(shè)
是原問(wèn)題的最優(yōu)解,則:
- 若
是對(duì)偶問(wèn)題的最優(yōu)解挪鹏,則
與
互補(bǔ)见秽。(強(qiáng)對(duì)偶性)
- 若
是對(duì)偶問(wèn)題的可行解且
與
互補(bǔ),則
是對(duì)偶問(wèn)題的最優(yōu)解讨盒。
- 存在對(duì)偶問(wèn)題的可行解
使得
與
互補(bǔ)解取。
結(jié)合命題1可知:
若
是原問(wèn)題的基本可行解,
是其影子價(jià)格返顺,則
為最優(yōu)解當(dāng)且僅當(dāng)
是可行解禀苦。
如本文開(kāi)頭所言,判斷最優(yōu)性的問(wèn)題被巧妙地轉(zhuǎn)化為了判斷可行性地問(wèn)題创南。