欧美日韩一本的免费,欧美精品一区二区播放

這一部分對(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ē)這兩種玩具。生產(chǎn)一個(gè)小人偶需要1單位木材和2單位顏料，產(chǎn)生3單位收益。生產(chǎn)一輛小火車(chē)需要1單位木材和1單位顏料，產(chǎn)生2單位收益。工廠現(xiàn)有80單位木材和100單位顏料，問(wèn)如何分配火車(chē)與人偶的生產(chǎn)量可以使得收益最大？（見(jiàn)下圖左側(cè)）

為方便理解對(duì)偶性而引入的一個(gè)簡(jiǎn)單的例子

先補(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)題中，制造小火車(chē)與制造小人偶就是兩種行為。上圖中， $x_{1}$ 所在的列對(duì)應(yīng)著制造小人偶的行為， $x_{2}$ 所在的列對(duì)應(yīng)著制造小火車(chē)的行為。

回憶上一次在基本概念中講到的基本解與字典的概念，結(jié)合線性代數(shù)的知識(shí)，我們可以將LP問(wèn)題寫(xiě)為：

LP問(wèn)題的矩陣表示

不要被上圖中復(fù)雜的形式迷惑，其實(shí)推導(dǎo)過(guò)程非常簡(jiǎn)單。式中各個(gè)符號(hào)的定義見(jiàn)教材第32頁(yè)。需要強(qiáng)調(diào)的兩點(diǎn)是：

$x_N$ 是由非基本變量構(gòu)成的向量，在具體取值的時(shí)候即為0向量。詳見(jiàn)之前對(duì)非基本變量的定義。注意不要將非基本變量理解為0變量。非基本變量只是在考慮對(duì)應(yīng)基本解時(shí)取值為0。
此處假設(shè) $B$ 是可逆的，但我無(wú)法證明 $B$ 一定是可逆的。但我相信大多數(shù)情況下 $B$ 都是可逆的，因?yàn)樵谧值渲?img class="math-inline" src="https://math.jianshu.com/math?formula=x_%7BB%7D" alt="x_{B}" mathimg="1">可有 $x_{N}$ 表示，而聯(lián)系二者的只有等式 $Ax = b$ 。如果 $B$ 不滿秩的話會(huì)丟失 $x_{B}$ 的信息進(jìn)而使得 $x_{B}$ 無(wú)法被 $x_{N}$ 表示。（直觀感受，未證明）
基本解對(duì)應(yīng)的目標(biāo)函數(shù)的取值為 $c_{B}B^{-1}b$ ，當(dāng) $c_{N} - c_{B}B^{-1}N$ 的各項(xiàng)系數(shù)小于0時(shí)取最優(yōu)解。此時(shí)基本變量的取值為 $B^{-1}b$

目標(biāo)函數(shù)的值( $c_{B}B^{-1}b$ )和判斷最優(yōu)解的條件( $c_{N} - c_{B}B^{-1}N < 0$ )這兩個(gè)矩陣表示非常重要，建議各位同學(xué)自己推導(dǎo)一遍并記下來(lái)。

現(xiàn)在假設(shè)在市場(chǎng)上有以?xún)r(jià)格 $y_{1}$ 與 $y_{2}$ 售賣(mài)的木材與顏料，如上圖右側(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à)格的矩陣表示： $c_{B}B^{-1}$ 。其實(shí)這就是一個(gè)簡(jiǎn)單的求導(dǎo)運(yùn)算。對(duì)比目標(biāo)函數(shù)的值： $c_{B}B^{-1}b$ 可以發(fā)現(xiàn)某種材料的影子價(jià)格恰好就是目標(biāo)函數(shù)關(guān)于該材料的導(dǎo)數(shù)。需要注意的是此時(shí)由于材料可以自由買(mǎi)賣(mài)，所以 $b$ 變成了一個(gè)變向量。在某種意義上，目標(biāo)函數(shù)其實(shí)本來(lái)就是材料的函數(shù)，只不過(guò)材料的多少會(huì)影響函數(shù)的形式（ $B^{-1}$ 也會(huì)隨材料改變。）

影子價(jià)格 $c_{B}B^{-1}$ 是一個(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ēng)生產(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ú)限地買(mǎi)入原材料進(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è)，推得我們想要的理論，之后再?lài)?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)題

左邊為原問(wèn)題，右邊為對(duì)偶問(wèn)題。首先可以注意到的是對(duì)偶問(wèn)題的限制條件即假設(shè)1。此時(shí)有顯然的關(guān)系式： $3x_{1}+2x_{2} \leq (y_{1} + 2 y_{2})x_{1} + (y_{1} + y_{2})x_{2} = y_{1}(x_{1} + x_{2}) + y_{2}(2x_{1}+x_{2}) \leq 80y_{1} + 100y_{2}$ 左邊的不等號(hào)對(duì)應(yīng)于對(duì)偶問(wèn)題的限制條件，右邊的不等號(hào)則對(duì)應(yīng)原問(wèn)題的對(duì)偶條件。因此兩邊目標(biāo)函數(shù)存在關(guān)系： $Max \ 3x_{1}+2x_{2} \leq Min \ 80y_{1} + 100y_{2}$ 是顯然的。這其實(shí)就是待會(huì)要提到的弱對(duì)偶性。

原問(wèn)題與對(duì)偶問(wèn)題的矩陣表示如下圖所示：

原問(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è) $x$ 與 $y$ 分別是原問(wèn)題與對(duì)偶問(wèn)題的可行解，則： $c^{T}x \leq b^{T}y$ 證明：由限制條件可知： $c^{T}x \leq (A^{T}y)^{T}x = (y^{T}A)x = y^{T}(Ax) \leq y^{T}b = b^{T}y$ 證明完畢。

由弱對(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è) $x$ 與 $y$ 分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解，則： $c^{T}x = b^{T}y$ 且滿足 $y^{T}(b-Ax) = x^{T}(A^{T}y - c) = 0$ 其中 $b-Ax$ 與 $A^{T}y - c$ 分別對(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)題中采用的是 $\leq$ -限制條件，則無(wú)符號(hào)限制的對(duì)應(yīng)對(duì)偶變量會(huì)導(dǎo)致弱對(duì)偶性定理失效。因?yàn)樨?fù)號(hào)會(huì)使不等式轉(zhuǎn)向。對(duì)于 $\geq$ -限制條件也一樣?，F(xiàn)考慮例1中木材的限制條件對(duì)應(yīng)的對(duì)偶變量（即木材的價(jià)格 $y_{1}$ ）： $3x_{1}+2x_{2} \leq (y_{1} + 2 y_{2})x_{1} + (y_{1} + y_{2})x_{2} = y_{1}(x_{1} + x_{2}) + y_{2}(2x_{1}+x_{2})$ 如果不要求 $y_1 \geq 0$ 的話顯然無(wú)法推出 $3x_{1}+2x_{2} \leq 80y_{1} + 100y_{2}$ 。
如果原問(wèn)題中的某條限制條件是等號(hào)-限制條件，則稱(chēng)該限制條件為緊(tight)的。這個(gè)概念之后還會(huì)用到。
若原問(wèn)題中某條限制是等號(hào)-限制條件則不論對(duì)應(yīng)的對(duì)偶變量如何取值，弱對(duì)偶性仍然成立。依然考慮例1中的木材，但此時(shí)將其限制條件改為等號(hào)-限制條件，則有： $3x_{1}+2x_{2} \leq (y_{1} + 2 y_{2})x_{1} + (y_{1} + y_{2})x_{2} = y_{1}(x_{1} + x_{2}) + y_{2}(2x_{1}+x_{2}) = 80 y_{1} + y_{2}(2x_{1}+x_{2}) \leq 80 y_{1} + 100 y_{2}$ 即仍滿足弱對(duì)偶性。
類(lèi)比地可以總結(jié)出規(guī)律：對(duì)于一個(gè)求最大值的LP問(wèn)題， $\leq$ -限制條件對(duì)應(yīng)非負(fù)對(duì)偶變量； $\geq$ -限制條件對(duì)應(yīng)非正對(duì)偶變量；等號(hào)-限制條件對(duì)應(yīng)無(wú)符號(hào)限制的對(duì)偶變量。

接下來(lái)介紹互補(bǔ)松弛的概念。

定義1：稱(chēng)向量 $x = (x_{1}, \cdots , x_{n})$ 與 $y = (y_{1}, \cdots , y_{n})$ 是互補(bǔ)的(complementary)，若： $y^{T}(b-Ax) = x^{T}(A^{T}y - c) = 0$

關(guān)于互補(bǔ)，有如下性質(zhì)：

強(qiáng)對(duì)偶性說(shuō)明原問(wèn)題的最優(yōu)解與對(duì)偶問(wèn)題的解是互補(bǔ)的。
對(duì)于互補(bǔ)的向量 $x$ 與 $y$ ，若 $y_{i} > 0$ 則原問(wèn)題的第i個(gè)限制條件為緊的。同理若 $x_{i} > 0$ 則對(duì)偶問(wèn)題的第i個(gè)限制條件是緊的。
對(duì)于任意基本解 $x$ ，由其定義的影子價(jià)格 $\pi$ 與之互補(bǔ)。證明如下：

命題1：對(duì)于LP問(wèn)題的任意基本解 $x$ ，由其定義的影子價(jià)格 $\pi$ 與之互補(bǔ)
證明：明天再說(shuō)！

關(guān)于互補(bǔ)松弛性，有以下幾點(diǎn)重要的性質(zhì)。先不加證明地列出：

設(shè) $x$ 是原問(wèn)題的最優(yōu)解，則：

若 $y$ 是對(duì)偶問(wèn)題的最優(yōu)解，則 $x$ 與 $y$ 互補(bǔ)。（強(qiáng)對(duì)偶性）
若 $y$ 是對(duì)偶問(wèn)題的可行解且 $x$ 與 $y$ 互補(bǔ)，則 $y$ 是對(duì)偶問(wèn)題的最優(yōu)解。
存在對(duì)偶問(wèn)題的可行解 $y$ 使得 $x$ 與 $y$ 互補(bǔ)。

結(jié)合命題1可知：

若 $x$ 是原問(wèn)題的基本可行解， $\pi$ 是其影子價(jià)格，則 $x$ 為最優(yōu)解當(dāng)且僅當(dāng) $\pi$ 是可行解。

如本文開(kāi)頭所言，判斷最優(yōu)性的問(wèn)題被巧妙地轉(zhuǎn)化為了判斷可行性地問(wèn)題。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LP問(wèn)題進(jìn)階 Part 2 | 對(duì)偶理論

LP問(wèn)題進(jìn)階 Part 2 | 對(duì)偶理論