第三章對(duì)偶理論及靈敏度分析3ppt課件.ppt

1、第三章 對(duì)偶理論及靈敏度分析,3.1.1 線性規(guī)劃對(duì)偶問(wèn)題 3.1.2 對(duì)偶問(wèn)題的基本性質(zhì) 3.1.3 影子價(jià)格 3.1.4 對(duì)偶單純形法 3.2.1 靈敏度問(wèn)題及其圖解法 3.2.2 靈敏度分析 3.2.3 參數(shù)線性規(guī)劃,返回,繼續(xù),3.1.1 線性規(guī)劃的對(duì)偶問(wèn)題,一、對(duì)偶問(wèn)題的提出 二、原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型 三、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系,實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種 產(chǎn)品， 有關(guān)數(shù)據(jù)如下表：,一、對(duì)偶問(wèn)題的提出,如何安排生產(chǎn)， 使獲利最多？,廠 家,設(shè) 產(chǎn)量 產(chǎn)量,設(shè)：設(shè)備A 元時(shí) 設(shè)備B 元時(shí) 調(diào)試工序 元時(shí),收 購(gòu),付出的代價(jià)最小， 且對(duì)方能接受。,出讓代價(jià)應(yīng)不低于 用

2、同等數(shù)量的資源 自己生產(chǎn)的利潤(rùn)。,廠家能接受的條件： 收購(gòu)方的意愿：,出讓代價(jià)應(yīng)不低于 用同等數(shù)量的資源 自己生產(chǎn)的利潤(rùn)。,廠 家,對(duì) 偶 問(wèn) 題,原 問(wèn) 題,收 購(gòu),廠 家,一對(duì)對(duì)偶問(wèn)題,3個(gè)約束 2個(gè)變量,2個(gè)約束 3個(gè)變量,一般規(guī)律,特點(diǎn)： 1 2限定向量b 價(jià)值向量C （資源向量） 3一個(gè)約束 一個(gè)變量。 4 的LP約束“ ” 的 LP是“ ”的約束。 5變量都是非負(fù)限制。,其它形式 的對(duì)偶 ?,二、原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型,1對(duì)稱形式的對(duì)偶 當(dāng)原問(wèn)題對(duì)偶問(wèn)題只含有不等式約束時(shí)，稱為對(duì)稱形式的對(duì)偶。,情形一：,原問(wèn)題,對(duì)偶問(wèn)題,化為標(biāo)準(zhǔn)對(duì)稱型,情形二：,證明,對(duì)偶,2、 非對(duì)稱形式的

3、對(duì)偶 若原問(wèn)題的約束條件是等式，則,原問(wèn)題,對(duì)偶問(wèn)題,推導(dǎo):,原問(wèn)題,根據(jù)對(duì)稱形式的對(duì)偶模型,可直接寫(xiě)出上述問(wèn)題的對(duì)偶問(wèn)題:,令 ，得對(duì)偶問(wèn)題為：,證畢。,三、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系,例:,對(duì)偶問(wèn)題為,返回,結(jié)束,線性規(guī)劃的對(duì)偶問(wèn)題,返回,繼續(xù),3.1.2 對(duì)偶問(wèn)題的基本性質(zhì),引例 對(duì)稱性 弱對(duì)偶性 最優(yōu)性 對(duì)偶性（強(qiáng)對(duì)偶性） 互補(bǔ)松弛性,對(duì) 偶 問(wèn) 題,原 問(wèn) 題,收 購(gòu),廠 家,引例,原問(wèn)題化為極小問(wèn)題，最終單純形表：,對(duì)偶問(wèn)題用兩階段法求解的最終的單純形表,化為極小問(wèn)題,原問(wèn)題 最優(yōu)解,對(duì)偶問(wèn)題 最優(yōu)解,原問(wèn)題化為極小問(wèn)題，最終單純形表：,兩個(gè)問(wèn)題作一比較: 1.兩者的最優(yōu)值相同 2

4、.變量的解在兩個(gè)單純形表中互相包含 原問(wèn)題最優(yōu)解（決策變量） 對(duì)偶問(wèn)題最優(yōu)解（決策變量）,從引例中可見(jiàn)： 原問(wèn)題與對(duì)偶問(wèn)題在某種意義上來(lái)說(shuō)，實(shí)質(zhì)上是一樣的，因?yàn)榈诙€(gè)問(wèn)題僅僅在第一個(gè)問(wèn)題的另一種表達(dá)而已。,理論證明： 原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系,對(duì)偶問(wèn)題的基本性質(zhì),一、對(duì)稱定理： 定理： 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。,設(shè)原問(wèn)題（1） 對(duì)偶問(wèn)題（2）,二、弱對(duì)偶性定理： 若 和 分別是原問(wèn)題（1）及對(duì)偶問(wèn)題（2）的可行解，則有,證明：,對(duì)偶問(wèn)題的基本性質(zhì),從弱對(duì)偶性可得到以下重要結(jié)論：,（1）極大化問(wèn)題（原問(wèn)題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的下界。 （2）極小化問(wèn)題（對(duì)偶問(wèn)題

5、）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是原問(wèn)題最優(yōu)目標(biāo)函數(shù)值的上界。 （3）若原問(wèn)題可行，但其目標(biāo)函數(shù)值無(wú)界，則對(duì)偶問(wèn)題無(wú)可行解。,（4）若對(duì)偶問(wèn)題可行，但其目標(biāo)函數(shù)值無(wú)界，則原問(wèn)題無(wú)可行解。 （5）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界。 （6）對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。,原問(wèn)題,對(duì)偶問(wèn)題,三、最優(yōu)性定理： 若 和 分別是（1）和（2）的 可行解，且有 則 分別是（1）和（2）的最優(yōu)解 。,則 為（1）的最優(yōu)解， 反過(guò)來(lái)可知： 也是（2）的最優(yōu)解。,證明：因?yàn)椋?）的任一可行解 均滿足,對(duì)偶問(wèn)題的基本性質(zhì),四、對(duì)偶定理（強(qiáng)對(duì)偶性）： 若原

6、問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。,對(duì)偶問(wèn)題的基本性質(zhì),五、互補(bǔ)松弛性： 若 分別是原問(wèn)題（1）與對(duì)偶問(wèn)題（2）的可行解， 分別為（1）、（2）的松弛變量，則： 即：,為最優(yōu)解,原問(wèn)題第i條約束,A的第i行,說(shuō)明：在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件去嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。,另一方面：,對(duì)偶問(wèn)題的第j條約束,互補(bǔ)松弛定理應(yīng)用： （1）從已知的最優(yōu)對(duì)偶解，求原問(wèn)題最優(yōu)解，反之亦然。 （2）證實(shí)原問(wèn)題可行解是否為最優(yōu)解。 （3）從不同假設(shè)來(lái)進(jìn)行試算，從而研究原始、對(duì)

7、偶問(wèn)題最優(yōu)解的一般性質(zhì)。 （4）非線性的方面的應(yīng)用。,以上性質(zhì)同樣適用于非對(duì)稱形式。,返回,結(jié)束,對(duì)偶問(wèn)題的基本性質(zhì),返回,繼續(xù),3.1.3 影子價(jià)格,在單純形法的每步迭代中，目標(biāo)函數(shù)取值 ， 和檢驗(yàn)數(shù) 中都有乘子 ，那么Y的經(jīng)濟(jì)意義是什么？,當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解 時(shí)，其對(duì)偶問(wèn)題也得到最優(yōu)解 ，且代入各自的目標(biāo)函數(shù)后有：,是線性規(guī)劃原問(wèn)題約束條件的 右端項(xiàng)，它代表第 種資源的擁有量；,（3）,對(duì)偶變量 的意義代表在資源最優(yōu)利用條件下對(duì)單位第 種資源的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見(jiàn)，稱為影子價(jià)格（shadow price)。,影子價(jià)格

8、的定義,1資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。,影子價(jià)格的經(jīng)濟(jì)意義,影子價(jià)格的經(jīng)濟(jì)意義,2影子價(jià)格是一種邊際價(jià)格。 在（3）式中， 。 說(shuō)明 的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下， 每增加一個(gè)單位時(shí)目標(biāo)函數(shù) 的增量。,幾何解釋：引例圖解法分析。,影子價(jià)格的經(jīng)濟(jì)意義,3資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本. 在純市場(chǎng)經(jīng)濟(jì)條件下,當(dāng)?shù)?種資源的市場(chǎng)價(jià)格低于1/4時(shí)，可以買(mǎi)進(jìn)這種資源；相反當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就會(huì)賣(mài)出這種資源。隨著資源的買(mǎi)進(jìn)賣(mài)出，它的影子價(jià)格也將隨之發(fā)生變化

9、，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。,4在對(duì)偶問(wèn)題的互補(bǔ)松弛性質(zhì)中有 這表明生產(chǎn)過(guò)程中如果某種資源 未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。,5從影子價(jià)格的含義上考察單純形表的 檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。,（4）,影子價(jià)格的經(jīng)濟(jì)意義,6一般說(shuō)對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及到資源的最有效利用。,經(jīng)濟(jì)學(xué)研究如何管理 自己的稀缺資源,返回,結(jié)束,影子價(jià)格,3.1.4 對(duì)偶單純形法,對(duì)偶單純形法的基本思路 對(duì)偶單純形法的計(jì)算步驟,返回,繼續(xù),對(duì)偶單純

10、形法的基本思路,單純形法的基本思路： 原問(wèn)題基可行解 最優(yōu)解判斷,對(duì)偶問(wèn)題的可行解,對(duì)偶問(wèn)題 最優(yōu)解判斷,對(duì)偶單純形法 基本思路,對(duì)偶單純形法的計(jì)算步驟,線性規(guī)劃問(wèn)題,不妨設(shè) 為對(duì)偶問(wèn)題的 初始可行基，則 。,若 ，即表中原問(wèn)題和 對(duì)偶問(wèn)題均為最優(yōu)解，否則換基。,換基方法：,確定換出基變量 對(duì)應(yīng)變量 為換出基的變量,確定換入基變量 為主元素， 為換入基變量,初始可行基,例、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：,對(duì)偶問(wèn)題的 初始可行基,例、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：,使對(duì)偶問(wèn)題基變量可行,換出,例、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：,最優(yōu)解,例、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：,對(duì)偶單純形法的優(yōu)

11、點(diǎn)： 不需要人工變量； 當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)； 在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。 對(duì)偶單純形法缺點(diǎn)： 在初始單純形表中對(duì)偶問(wèn)題是基可行解，這點(diǎn)對(duì)多數(shù)線性規(guī)劃問(wèn)題很難做到。 因此，對(duì)偶單純形法一般不單獨(dú)使用。,練習(xí),用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：,返回,結(jié)束,對(duì)偶單純形法,3.2.1 靈敏度問(wèn)題及其圖解法,靈敏度問(wèn)題 靈敏度分析圖解法,靈敏度問(wèn)題,背景： 線性規(guī)劃問(wèn)題中， 都是常數(shù)，但這些系數(shù)是估計(jì)值和預(yù)測(cè)值。 市場(chǎng)的變化 值變化； 工藝的變化 值變化； 資源的變化 值變化。,問(wèn)題： 當(dāng)這些系數(shù)中的一個(gè)或多個(gè)發(fā)生變化時(shí)，原最優(yōu)解會(huì)怎樣變化？ 當(dāng)這些系數(shù)

12、在什么范圍內(nèi)變化時(shí)，原最優(yōu)解仍保持不變？ 若最優(yōu)解發(fā)生變化，如何用最簡(jiǎn)單的方法找到現(xiàn)行的最優(yōu)解？,研究?jī)?nèi)容： 研究線性規(guī)劃中， 的變化對(duì)最優(yōu)解的影響。,研究方法： 圖解法 對(duì)偶理論分析,僅適用于含2個(gè)變量的線性規(guī)劃問(wèn)題,在單純形表中進(jìn)行分析,線性規(guī)劃模型,靈敏度分析圖解法,x2,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),最優(yōu)解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,靈敏度分析圖解法,靈敏度分析 圖解法

13、,靈敏度分析 圖解法,若 c1增加（c2 不變）,新的最優(yōu)解,靈敏度分析 圖解法,若 c1減少,新的最優(yōu)解,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E,(斜率 = - 1),(斜率 = - 2/3),靈敏度分析 圖解法,3.2.1 靈敏度問(wèn)題及其圖解法,結(jié)束,3.2.2 靈敏度分析,一、分析 的變化 二、分析 的變化 三、增加一個(gè)變量 的分析 四、增加一個(gè)約束條件的分析 五、分析 的變化,研究?jī)?nèi)容： 研究線性規(guī)劃中， 的變化對(duì)最優(yōu)解的影響。,常用公式：,

14、實(shí)例： 某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：,如何安排生產(chǎn)， 使獲利最多？,廠 家,設(shè) 產(chǎn)量 產(chǎn)量,原問(wèn)題 最優(yōu)解,對(duì)偶問(wèn)題最優(yōu)解 （相差負(fù)號(hào)）,原問(wèn)題的最終單純形表：,一、分析 的變化,的變化僅影響 的變化。,1.5,2,問(wèn)題1：當(dāng) 該公司最優(yōu)生 產(chǎn)計(jì)劃有何變化？,最終單純形表,最終單純形表,換基后單純形表為,最優(yōu)解,問(wèn)題2：設(shè)產(chǎn)品II利潤(rùn)為 ， 求原最優(yōu)解不變時(shí) 的范圍。,產(chǎn)品II利潤(rùn)為 時(shí)的最終單純形表,二、分析 的變化,的變化僅影響 ，即原最優(yōu)解的可行性可能會(huì)變化：,可行性不變，則原最優(yōu)解不變。,可行性改變，則原最優(yōu)解改變， 用對(duì)偶單純形法，找出最優(yōu)解。,問(wèn)題3：設(shè)備B

15、的能力增加到32小時(shí)， 原最優(yōu)計(jì)劃有何變化？,代入單純形表中,可行性改變，用對(duì)偶單純形法換基求解。,主元,新的最優(yōu)解,換基迭代得：,問(wèn)題4：設(shè)調(diào)試工序可用時(shí)間為 小時(shí)，求 ，原最優(yōu)解保持不變。,原最優(yōu)解保持不變，則,三、增加一個(gè)變量 的分析,增加一個(gè)變量相當(dāng)于增加一種產(chǎn)品。 分析步驟： 1、計(jì)算 2、計(jì)算 3、若 ，原最優(yōu)解不變； 若 ，則按單純形表繼續(xù)迭代 計(jì)算找出最優(yōu)解。,問(wèn)題5：設(shè)生產(chǎn)第三種產(chǎn)品，產(chǎn)量為 件， 對(duì)應(yīng)的 求最優(yōu)生產(chǎn)計(jì)劃。,解：,代入最終原單純形表中,主元,換基后有：,四、增加一個(gè)約束條件的分析,增加一個(gè)約束條件相當(dāng)于增添一道工序。,分析方法：,將最優(yōu)解代入新的約束中,（1）

16、若滿足要求，則原最優(yōu)解不變；,（2）若不滿足要求，則原最優(yōu)解改變， 將新增的約束條件添入最終的 單純形表中繼續(xù)分析。,五、分析 的變化,若 對(duì)應(yīng)的 變量 為基變量， B將改變。需引入人工變量求出 可行解，再用單純形法求解。,若 對(duì)應(yīng)的變量 為非基變量， 參見(jiàn)三的分析。,靈敏度分析的步驟歸納如下：,（1）將參數(shù)的改變計(jì)算反映到最終 單純形表上； （2）檢查原問(wèn)題是否仍為可行解； （3）檢查對(duì)偶問(wèn)題是否仍為可行解； （4）按下表所列情況得出結(jié)論和決 定繼續(xù)計(jì)算的步驟。,總之,練習(xí)：,某廠計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品單位利潤(rùn)及生產(chǎn)產(chǎn)品所需材料、勞動(dòng)力如下表：,單位產(chǎn)品 甲 乙 丙 可使用資

17、源量 勞動(dòng)力 1/3 1/3 1/3 1 材料 1/3 4/3 7/3 3 利潤(rùn)（元） 2 3 1,（1）確定最優(yōu)的生產(chǎn)方案； （2）當(dāng) 增大至多少時(shí)，丙產(chǎn)品安排生產(chǎn)； （3）增加3個(gè)勞動(dòng)力，最優(yōu)解是否改變？ （4）勞動(dòng)力在哪個(gè)范圍內(nèi)變化，對(duì)利潤(rùn)值 的改變有利； （5）增加新的產(chǎn)品丁，需1個(gè)勞動(dòng)力，1個(gè) 單位原料，利潤(rùn)3元。確定最優(yōu)的生產(chǎn)方案。 （6）添加新約束： 最優(yōu)解是否改變？,解：初始及最終單純形表為,3.2.2 靈敏度分析,結(jié)束,3.2.3 參數(shù)線性規(guī)劃,參數(shù)線性規(guī)劃概念,當(dāng)參數(shù) 或 沿某一方向連續(xù)變動(dòng)時(shí)，目標(biāo)函數(shù)值z(mì)將隨 或 的變動(dòng)而呈線性變動(dòng)，z是這個(gè)變動(dòng)參數(shù)的線性函數(shù)，因而稱為參

18、數(shù)線性規(guī)劃。,模型,目標(biāo)函數(shù)的系數(shù)含有參數(shù)的線性規(guī)劃模型,約束條件右端的常數(shù)項(xiàng)含有參數(shù)的LP模型,參數(shù)線性規(guī)劃問(wèn)題的分析步驟：,（1）令 求解得最終單純形表； （2）將 或 項(xiàng)反映到最終單純形表中去； （3）隨 值的增大或減小，觀察原問(wèn)題或?qū)ε?問(wèn)題。 （4）重復(fù)第（3）步，一直到 值繼續(xù)增大或減小 時(shí)，表中的解（基）不再出現(xiàn)變化時(shí)為止。,確定現(xiàn)有解（基）允許的 的變動(dòng)范圍；,當(dāng) 的變動(dòng)超出這個(gè)范圍時(shí)，用單純 形法或?qū)ε紗渭冃畏ㄇ笮碌慕狻?舉例分析目標(biāo)函數(shù)的系數(shù) 含有參數(shù)的線性規(guī)劃問(wèn)題,分析 值變化時(shí)，下述參數(shù)線性規(guī)劃 問(wèn)題最優(yōu)解的變化。,先令 求得最優(yōu) 解，然后 將 反映在最終單純形表中，見(jiàn)下表：,最優(yōu)解保持不變的條件,當(dāng) 時(shí),當(dāng) 時(shí)，換基得：,當(dāng) 時(shí)，由原最終單純形表,當(dāng) 時(shí)，最終單純