運(yùn)籌學(xué)OR1-Ch3-LP對偶課件

1、第三章 線性規(guī)劃對偶理論3-1 對偶問題的提出3-2 寫對偶問題3-3 對偶問題的性質(zhì)3-4 對偶單純形方法3-1 對偶問題的提出從經(jīng)濟(jì)意義上提出對偶問題仍以第一章的例1-1為例，假若企業(yè)的決策者除了生產(chǎn)產(chǎn)品甲、乙之外，還有其它可選方案來利用其設(shè)備資源。例如，承接外加工或租賃設(shè)備，作為決策者就要考慮設(shè)備臺時定價的問題，即在何種臺時價格的前提下接受外加工或租賃設(shè)備以取代生產(chǎn)甲乙兩種產(chǎn)品。若以 分別表示設(shè)備A、B、C每臺時的價格（加工費(fèi)或租金），這時就要與自己生產(chǎn)產(chǎn)品甲乙作一比較，因?yàn)槊可a(chǎn)1件產(chǎn)品甲可得2元的利潤，每生產(chǎn)1件產(chǎn)品乙可得利潤3元，那么，如果用于生產(chǎn)一件產(chǎn)品甲的各設(shè)備臺時用于外加工所

2、得的收益不低于2元，同樣，用于生產(chǎn)一件產(chǎn)品乙的各設(shè)備臺時用于外加工所得的收益不低于3元，則將設(shè)備用于外加工（或租賃）；否則，就用于生產(chǎn)甲乙兩種產(chǎn)品。根據(jù)以上分析和第一章例1-1的條件，我們得到關(guān)系式： *Page 2 of 28 3-1 對偶問題的提出從經(jīng)濟(jì)上提出從經(jīng)濟(jì)意義上提出對偶問題（續(xù)）則設(shè)備用于外加工的總收入為：設(shè)備臺時價格越大，總收入就越大，我們當(dāng)然希望總收入越大越好。但是，價格問題不是一個企業(yè)能完全確定的，它是一種社會價格。因此，我們希望知道最低的總收入是多少，或者說，最低的設(shè)備臺時價格是多少時就和自己生產(chǎn)產(chǎn)品甲乙所得的收入是一樣的。因此，這個問題的數(shù)學(xué)模型為：很顯然，當(dāng)時 ，決策

3、者認(rèn)為設(shè)備用于外加工和用于生產(chǎn)產(chǎn)品甲乙這兩種方案的效果是一樣的。 *Page 3 of 28 3-1 對偶問題的提出從數(shù)學(xué)模型上提出從數(shù)學(xué)模型上提出對偶問題在上述矩陣表示的單純形表中，若問題達(dá)到了最優(yōu)解，則其檢驗(yàn)數(shù)行均小于等于零，即：對其討論如下：用 ，稱之為單純形乘子，對于最優(yōu)解而言，顯然有 。對于包含基變量在內(nèi)的檢驗(yàn)數(shù)，在最優(yōu)解的情況下可以表示為：因?yàn)?在約束 的條件下無上界，所以它只存在最小值，它與常向量b的乘積也只存在最小值。記 作為： *Page 4 of 28 3-1 對偶問題的提出從數(shù)學(xué)模型上提出定義新的LP模型為原模型的對偶模型且注意到：原模型 在約束 條件下的最優(yōu)解為： 所以

4、有：對偶模型*Page 5 of 28 3-2 寫對偶問題將上一節(jié)中原問題與對偶問題的矩陣式展開：對偶式*Page 6 of 28 3-2 寫對偶問題表格形式為便于敘述和記憶對偶問題，通常規(guī)定一個標(biāo)準(zhǔn)形式，一般規(guī)定原規(guī)劃為“”約束，對偶規(guī)劃為“”約束，變量均0的對偶問題為標(biāo)準(zhǔn)形式。把它們之間的關(guān)系用表格形式表示出來 ：*Page 7 of 28 3-2 寫對偶問題非標(biāo)準(zhǔn)型的處理在實(shí)際問題中常常會有非標(biāo)準(zhǔn)形式，如有等式約束，或某變量無非負(fù)約束等等。如果某個約束為等式約束，可以把它變?yōu)閮蓚€不等式約束如下：等價變換寫對偶*Page 8 of 28 3-2 寫對偶問題對偶關(guān)系表注意：助記法：標(biāo)準(zhǔn)型應(yīng)是

5、，應(yīng)是，這是對于對偶變量0而言；若對偶變量0，則符號方向相反；等式對應(yīng)無約束。 *Page 9 of 28 3-2 寫對偶問題例題例3-1：寫出下面線性規(guī)劃問題的對偶問題。 解：根據(jù)對偶問題變換規(guī)則，其對偶問題如下： *Page 10 of 28 3-3 對偶問題的性質(zhì)對稱性：對偶問題的對偶是原問題。證明：設(shè)原問題是： 對偶問題是： 對偶再對偶此即原模型證閉*Page 11 of 28 3-3 對偶問題的性質(zhì)弱對偶性弱對偶性若 是原問題的可行解， 是對偶問題的可行解，則存在 證明：設(shè)原規(guī)劃問題是 若 又是其對偶問題的可行解， 用 左乘式兩側(cè)得： 是原問題的可行解，滿足約束條件 用 右乘式兩側(cè)得

6、： 得到結(jié)論： 命題得證 *Page 12 of 28 3-3 對偶問題的性質(zhì)等值最優(yōu)性等值最優(yōu)性設(shè) 是原問題的可行解， 是對偶問題的可行解，當(dāng)時 ， 分別是原問題和對偶問題的最優(yōu)解。 證明： 據(jù)性質(zhì)2，有 （對偶問題的任一可行解不小于原問題的任一個可行解） 又 由 的任意性可知， 是對偶問題可行解中最小的一個，故是最優(yōu)解。 同理， 由 的任意性可知， 是原問題可行解中最大的一個，故是最優(yōu)解。 證畢*Page 13 of 28 3-3 對偶問題的性質(zhì)對偶定理對偶定理若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。 證明：設(shè) 是原問題的最優(yōu)解，則必有 即 這時的是對偶問題的可行解，所

7、以得到對偶問題的目標(biāo)值 是原問題的最優(yōu)解，它使目標(biāo)函數(shù)取值為 由定理3的等值最優(yōu)性可知， 是對偶問題的最優(yōu)解。命題得證 *Page 14 of 28 3-3 對偶問題的性質(zhì)互補(bǔ)松弛定理互補(bǔ)松弛定理（松緊定理）若 分別是原問題和對偶問題的可行解， 分別是原問題和對偶問題的松弛變量，那么，當(dāng)且僅當(dāng) 與 為最優(yōu)解時，有關(guān)系式： 證明：設(shè)原問題和對偶問題的標(biāo)準(zhǔn)型分別為： 原問題中的目標(biāo)函數(shù)中的系數(shù)向量 C 用 代替后得到： 將對偶問題的目標(biāo)函數(shù) b 中系數(shù)列向量用 代替后得到： 若 分別為原問題和對偶問題的最優(yōu)解，將 代入、式得： *Page 15 of 28 3-3 對偶問題的性質(zhì)互補(bǔ)松弛定理互補(bǔ)松

8、弛定理 (續(xù))根據(jù)等值最優(yōu)性定理有： 又 具有非負(fù)性 必有 同樣，將可行解 代入、式，若有 ，則一定有 ，根據(jù)等值最優(yōu)性定理， 必為原問題和對偶問題的最優(yōu)解。 證畢 *Page 16 of 28 3-3 對偶問題的性質(zhì)互補(bǔ)松弛定理例題例3-2 已知下面線性規(guī)劃模型對偶問題的最優(yōu)解 為 試用對偶理論找出原問題的最優(yōu)解。解：先寫出它的對偶模型*Page 17 of 28 3-3 對偶問題的性質(zhì)互補(bǔ)松弛定理例題例3-2（續(xù)）設(shè)原問題的最優(yōu)解為：對偶問題的最優(yōu)解為：原問題加入松弛變量：對偶問題加入松弛變量：根據(jù)互補(bǔ)松弛定理有：變量的對應(yīng)關(guān)系為：即原問題的兩個約束均為等式約束。*Page 18 of 2

9、8 3-3 對偶問題的性質(zhì)互補(bǔ)松弛定理例題例3-2（續(xù)）將Y*代入對偶問題約束，知道為嚴(yán)格不等式，則其對應(yīng)的松弛變量 均不等于零。因此，原問題的約束變成為：求解此二元一次方程組得到：故原問題的最優(yōu)解為：*Page 19 of 28 3-3 對偶問題的性質(zhì)解與檢驗(yàn)數(shù)原問題的檢驗(yàn)數(shù)對應(yīng)對偶問題的一個解。證明：設(shè)原問題為： 對偶問題為： 設(shè)B是原問題的一個可行基，則有： 原問題和對偶問題可以寫成： 注：這里 ，其中 是對應(yīng)于原問題中基變量 的剩余變量， 是對應(yīng)于原問題中非基變量 的剩余變量。 *Page 20 of 28 3-3 對偶問題的性質(zhì)解與檢驗(yàn)數(shù)性質(zhì)6（續(xù)）當(dāng)求得了原問題的一個基本可行解 ，

10、并得到相應(yīng)的檢驗(yàn)數(shù)： 令 ，并代入到上述對偶問題的模型中得到： 即對偶問題的解： ，它們恰好是原問題基本可行解所對應(yīng)的檢驗(yàn)數(shù)的負(fù)值。 證畢 *Page 21 of 28 3-3 對偶問題的性質(zhì)解與檢驗(yàn)數(shù)性質(zhì)6的討論：由性質(zhì)6可知，用單純形表求解原問題的迭代過程中，在檢驗(yàn)數(shù)行的各檢驗(yàn)數(shù)對應(yīng)于對偶問題的一個可行解，它們的關(guān)系是： 注：單純形表中的檢驗(yàn)數(shù)與對偶問題解之間僅差一個負(fù)號 由此可見，在求解原問題的單純形表中，每迭代一次，得到原問題的一個基本可行解，所得的一組檢驗(yàn)數(shù)，對應(yīng)于對偶問題的一個解。要說明的是，若原問題未達(dá)最優(yōu)，則檢驗(yàn)數(shù)所對應(yīng)的對偶問題的這個解是基本非可行解，當(dāng)原問題達(dá)到最優(yōu)解時，則

11、這個解是基本且可行解，而且也達(dá)到最優(yōu)解；當(dāng)原問題為無界解（無最優(yōu)解）時，對偶問題無可行解。 *Page 22 of 28 3-4 對偶單純形法對偶單純形法思想對偶單純形法并非將原問題寫成對偶問題，再用單純形表求解，而是利用對偶問題的性質(zhì)求解線性規(guī)劃模型，它提供了單純形表的另一種用法。 在單純形表中，b 列對應(yīng)于原問題的一個基本可行解，而檢驗(yàn)數(shù)行則對應(yīng)其對偶問題的一個基本解。在前面我們進(jìn)行單純形表的迭代中，始終保持原問題為基本可行解（即 b 列大于等于零），而對偶問題為基本非可行解（即檢驗(yàn)數(shù)行含有正值），一旦檢驗(yàn)數(shù)行有基本非可行解變?yōu)榛究尚薪?，則原問題和對偶問題同時達(dá)到最優(yōu)解。 根據(jù)對偶問題的

12、對稱性，單純形表的迭代過程也可以反過來進(jìn)行，即保持對偶問題始終是基本可行解（即保持 ），而使原問題從基本非可行解逐步迭代到基本可行解，從而使原問題和對偶問題同時得到最優(yōu)解。這種單純形表的應(yīng)用方法稱為對偶單純形法。 *Page 23 of 28 3-4 對偶單純形法對偶單純形法流程對偶單純形法流程*Page 24 of 28 3-4 對偶單純形法例題例3-3：用對偶單純形法求解下列線性規(guī)劃模型。 解：首先將模型標(biāo)準(zhǔn)化。令 ，并加入松弛變量 得到標(biāo)準(zhǔn)模型： *Page 25 of 28 3-4 對偶單純形法例題（續(xù)）列單純形表如下 Cj 8 16 12 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 x4 x5 1 4 0 1 0 2 0 4 0 1 2 3 cjzj 8 16 12 0 0 0 4 3 Cj 8 16 12 0 0 CBXB x1 x2 x3 x4 x5 b 012 x4 x3 1 4 0 1 0 1 /2 0 1 0 1 /4 2 3/4 cjzj 2 16 0 0 3 9 2 4 *Page 26 of 28 3-4 對偶單純形法例題（續(xù)）最小化問題的最優(yōu)解為 完 Cj 8 16 12 0 0 CBXB x1 x2 x3