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

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

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

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

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

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

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

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

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

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

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

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

12、在什么范圍內(nèi)變化時，原最優(yōu)解仍保持不變？ 若最優(yōu)解發(fā)生變化，如何用最簡單的方法找到現(xiàn)行的最優(yōu)解？,研究內(nèi)容： 研究線性規(guī)劃中， 的變化對最優(yōu)解的影響。,研究方法： 圖解法 對偶理論分析,僅適用于含2個變量的線性規(guī)劃問題,在單純形表中進行分析,線性規(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 靈敏度問題及其圖解法,結(jié)束,3.2.2 靈敏度分析,一、分析 的變化 二、分析 的變化 三、增加一個變量 的分析 四、增加一個約束條件的分析 五、分析 的變化,研究內(nèi)容： 研究線性規(guī)劃中， 的變化對最優(yōu)解的影響。,常用公式：,

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

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

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

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

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