管理運(yùn)籌學(xué) 課件 03線性規(guī)劃的對(duì)偶理論

1運(yùn)籌學(xué)

OPERATIONSRESEARCH

第二章線性規(guī)劃的對(duì)偶理論2第二章線性規(guī)劃的對(duì)偶理論

(DualLinearProgramming,DLP)對(duì)偶問題的提出原問題與對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃3例甲方生產(chǎn)計(jì)劃問題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?§2.1對(duì)偶問題的提出設(shè)有原問題乙方租借設(shè)備：甲方以何種價(jià)格將設(shè)備A、B、C租借給乙方比較合理？請(qǐng)為其定價(jià)。假設(shè)A、B、C的單位租金分別為。思路：就甲方而言，租金收入應(yīng)不低于將設(shè)備用于自己生產(chǎn)時(shí)的利潤(rùn)。4所以：生產(chǎn)產(chǎn)品Ⅰ的資源用于出租時(shí)，租金收入應(yīng)滿足：類似的，生產(chǎn)產(chǎn)品Ⅱ的資源用于出租時(shí)，租金收入應(yīng)滿足：總的租金收入：5原問題對(duì)偶問題用矩陣將上述原問題對(duì)偶問題寫出6原問題對(duì)偶問題矩陣形式的原問題與對(duì)偶問題7原問題對(duì)偶問題目標(biāo)函數(shù)：MAX約束條件：m個(gè)約束變量：n個(gè)變量目標(biāo)函數(shù)：MIN約束條件：n個(gè)約束變量：m個(gè)變量§2.2

原問題與對(duì)偶問題8例寫出下述規(guī)劃的對(duì)偶問題互為對(duì)偶如何寫出非規(guī)范的原問題相應(yīng)的對(duì)偶問題：目標(biāo)函數(shù)MINMAX約束條件約束條件=?4.變量?

對(duì)偶問題與原問題的關(guān)系：原問題對(duì)偶問題目標(biāo)函數(shù)：MAX約束條件：m個(gè)約束變量：n個(gè)變量目標(biāo)函數(shù)：MIN約束條件：n個(gè)約束變量：m個(gè)變量約束條件右端項(xiàng)價(jià)值系數(shù)價(jià)值系數(shù)約束條件右端項(xiàng)例寫出下述規(guī)劃的對(duì)偶問題目標(biāo)函數(shù)MAXMIN約束條件變量3.變量約束例寫出下述規(guī)劃的對(duì)偶問題目標(biāo)函數(shù)MINMAX約束條件變量3.變量約束12原問題對(duì)偶問題§2.3

對(duì)偶問題的基本性質(zhì)假定線性規(guī)劃的原問題與對(duì)偶問題分別為：13例甲方生產(chǎn)計(jì)劃問題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?乙方租借設(shè)備，租金如何確定？原問題對(duì)偶問題14§2.3

對(duì)偶問題的基本性質(zhì)1、弱對(duì)偶性 如果分別是原問題和對(duì)偶問題的可行解，則恒有15§2.3

對(duì)偶問題的基本性質(zhì)2、最優(yōu)性 如果分別是原問題和對(duì)偶問題的可行解，且有則分別是原問題和對(duì)偶問題的最優(yōu)解。164、強(qiáng)對(duì)偶性 如果原問題有最優(yōu)解，則其對(duì)偶問題也必有最優(yōu)解，且兩者最優(yōu)目標(biāo)函數(shù)值相等，即。3、無界性:如果原問題（對(duì)偶問題）有無界解，則其對(duì)偶問題（原問題）無可行解。5、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)偶變量一定為零。即若若§2.4

對(duì)偶問題的基本性質(zhì)例：1、寫出其對(duì)偶問題。2、已知原問題的最優(yōu)解為用對(duì)偶理論直接求對(duì)偶問題的最優(yōu)解。練習(xí)：1、寫出其對(duì)偶問題。2、已知原問題的最優(yōu)解為用對(duì)偶理論直接求對(duì)偶問題的最優(yōu)解。196、單純形法的雙層含義（1）用單純形法求解LP問題時(shí)，迭代的每一步在得到該問題的一個(gè)基可行解的同時(shí)，其檢驗(yàn)數(shù)的相反數(shù)就構(gòu)成對(duì)偶問題的一個(gè)基本解。206、單純形法的雙層含義（2）在單純形表中，原問題的松

馳變量對(duì)應(yīng)對(duì)偶問題的變量，

對(duì)偶問題的剩余變量對(duì)應(yīng)原問

題的變量。216、單純形法的雙層含義（3）這些互相對(duì)應(yīng)的變量，如果在一個(gè)問題的解中是基變量，則在另一個(gè)問題的解中是非基變量。6、單純形法的雙層含義（4）將這兩個(gè)解代入各自的

目標(biāo)函數(shù)，有Z=W236、單純形法的雙層含義（4）將這兩個(gè)解代入各自的

目標(biāo)函數(shù)，有Z=W24對(duì)偶變量可理解為對(duì)一個(gè)單位第種資源的估價(jià)，稱為影子價(jià)格。§2.4

影子價(jià)格1、定義：假設(shè)有原問題和對(duì)偶問題如下25例甲方生產(chǎn)計(jì)劃問題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?乙方租借設(shè)備，租金如何確定？原問題對(duì)偶問題原問題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問題產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）剩余的資源（噸）消耗的資源單位產(chǎn)品消耗的資源（噸/件）§2.4影子價(jià)格比較對(duì)偶問題資源限量（噸）資源價(jià)格（元/噸）總租金（元）對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解w1、w2、...、wm稱為m種資源的影子價(jià)格?！?.4影子價(jià)格（1）資源市場(chǎng)價(jià)格受供求變化影響，影子價(jià)格則依賴于資源

利用情況?！?.4影子價(jià)格2、對(duì)影子價(jià)格的理解§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（2）影子價(jià)格是一種邊際價(jià)格：表示資源增加一個(gè)單位時(shí)，

最優(yōu)解及目標(biāo)函數(shù)值的變化。Z=17/2Z=35/4Z=9§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（3）影子價(jià)格是一種機(jī)會(huì)成本。

當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，應(yīng)買進(jìn)這種資源；否則，應(yīng)賣出這種資源。Z=17/2Z=35/4Z=9§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解(4)由互補(bǔ)松馳性理解影子價(jià)格：如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0。影子價(jià)格不為零時(shí)，表明資源已用完?！?.4影子價(jià)格2、對(duì)影子價(jià)格的理解(5)從影子價(jià)格的含義考察單純形法的計(jì)算生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格總和——隱含成本第j種產(chǎn)品的產(chǎn)值§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（6）求解線性規(guī)劃問題及對(duì)偶問題的目的34§2.5

對(duì)偶單純形法單純形法：找一個(gè)初始基可行解，保持b列為正，通過迭代找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)檢驗(yàn)數(shù)行全部小于等于零時(shí)，達(dá)到最優(yōu)解。35§2.5

對(duì)偶單純形法在單純形表中，列對(duì)應(yīng)原問題的基可行解，行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解；當(dāng)時(shí)，在檢驗(yàn)數(shù)行就得到對(duì)偶問題的基可行解，

此時(shí)兩個(gè)問題的目標(biāo)函數(shù)值相等；由最優(yōu)性條件知，兩個(gè)問題都達(dá)到了最優(yōu)解。36一、對(duì)偶單純形法思想§2.5

對(duì)偶單純形法換個(gè)角度考慮LP求解過程：保持對(duì)偶問題可行的前提下，通過逐步迭代實(shí)現(xiàn)原問題可行。374、檢查是否達(dá)最優(yōu)：b列非負(fù)時(shí)達(dá)最優(yōu)，否則繼續(xù)2、3。1、建立初始單純形表，使表中的檢驗(yàn)數(shù)都小于等于0。2、確定出基變量：選擇b列中負(fù)值最小者對(duì)應(yīng)變量出基，即對(duì)應(yīng)的為出基變量。3、確定入基變量：最小比值規(guī)則，即以對(duì)應(yīng)的為進(jìn)基變量，為主元素進(jìn)行迭代。二、對(duì)偶單純形法計(jì)算步驟：§2.5

對(duì)偶單純形法38例：用對(duì)偶單純形法求解下述問題§2.5

對(duì)偶單純形法對(duì)偶單純形法的使用條件：

①檢驗(yàn)數(shù)全部≤0；②b列至少一個(gè)元素<0；39§2.5

對(duì)偶單純形法40原問題無可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問題存在可行解時(shí)，若有某個(gè)，而所有，則原問題無可行解，對(duì)偶問題目標(biāo)值無界。§2.5

對(duì)偶單純形法41§2.6

靈敏度分析、含義：對(duì)系統(tǒng)因周圍條件變化顯示出來的敏

感程度的分析。可能變化的條件：利潤(rùn)

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建?！?.6

靈敏度分析43§2.6

靈敏度分析二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無需從頭計(jì)算。已知線性規(guī)劃問題：將參數(shù)的改變計(jì)算反映到最終表45§2.6

靈敏度分析二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無需從頭計(jì)算。已知線性規(guī)劃問題：將參數(shù)的改變計(jì)算反映到最終表46§2.6

靈敏度分析已知線性規(guī)劃問題：將參數(shù)的改變計(jì)算反映到最終表2.檢查原問題是否仍為可行解3.檢查對(duì)偶問題是否仍為可行解4.得到最優(yōu)解或繼續(xù)計(jì)算二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無需從頭計(jì)算。47§2.6

靈敏度分析原問題對(duì)偶問題結(jié)論或計(jì)算步驟可行解可行解仍是最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解非可行解引入人工變量，重新編單純形表，重新計(jì)算三、判斷得出結(jié)論或決定繼續(xù)計(jì)算的依據(jù)：（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)。四、各個(gè)參數(shù)變化后的討論50（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)。四、各個(gè)參數(shù)變化后的討論例：設(shè)有如下的線性規(guī)劃模型51用單純形法求得最終單純形表如下所示：（a）當(dāng)目標(biāo)函數(shù)變?yōu)闀r(shí)，最優(yōu)解會(huì)出現(xiàn)什么變化;52解：將目標(biāo)函數(shù)的變化直接反映到最終單純形表中：53Cj

的變化對(duì)最優(yōu)解的影響：54（b）目標(biāo)函數(shù)變?yōu)闀r(shí)在什么范圍內(nèi)變化，最優(yōu)解不變？將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中：解：由已知求得最終單純形表：55（b）目標(biāo)函數(shù)變?yōu)闀r(shí)在什么范圍內(nèi)變化，最優(yōu)解不變？解：將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中：56（二）分析bi變化影響：反映在最終單純形表上只引起

基變量列數(shù)字變化例、設(shè)有如下的線性規(guī)劃模型57用單純形法求得最終單純形表如表所示：（a）第2個(gè)約束條件的右端項(xiàng)增大到32，分析最優(yōu)解變化。58變換后的結(jié)果及迭代如下：bi

的變化對(duì)最優(yōu)解的影響：60（b）第2個(gè)約束條件變?yōu)闀r(shí)在什么范圍內(nèi)變化，表中基為最優(yōu)基？已求得最終單純形表如下：解：將b的變化反映到基變量b這一列數(shù)字上，得表62（三）增加一個(gè)變量的分析：即增加一種新產(chǎn)品，A增加一列，C增加一個(gè)相應(yīng)的分量。63（三）增加一個(gè)變量的分析：

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模64（三）增加一個(gè)變量的分析：65例:設(shè)有如下的線性規(guī)劃模型以上模型中，若增加一個(gè)變量，有,分析最優(yōu)解變化。（三）增加一個(gè)變量的分析：66用單純形法求得最終單純形表如表所示：67將變化反映到最終單純形表中:68增加一個(gè)變量對(duì)最優(yōu)解的影響：69§2.6

靈敏度分析、含義二、方法及步驟

三、判斷或計(jì)算依據(jù)（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)四、各個(gè)參數(shù)變化后的討論（二）分析bi變化影響——只引起基變量列數(shù)字變化（三）增加一個(gè)變量的分析人工變量法70（四）分析變化的影響1、變化的兩種情況72例：設(shè)有如下的線性規(guī)劃模型四、各個(gè)參數(shù)變化后的討論（四）分析變化的影響上述問題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。已用單純形法求得最終單純形表：上述問題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。74迭代，此時(shí)換出變量必為將變化反映到最終單純形表，得：引入人工變量，將原問題轉(zhuǎn)化為可行解。變化對(duì)最優(yōu)解的影響：上述問題中，的系數(shù)向量變?yōu)?7四、各個(gè)參數(shù)變化后的討論（四）分析變化的影響78例:設(shè)有如下的線性規(guī)劃模型,求得最終單純形表如下：上述問題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。79（五）增加一個(gè)約束條件的分析四、各個(gè)參數(shù)變化后的討論1、含義：相當(dāng)于增加一道工序，可能使可行域變小2、方法：將原最優(yōu)解取值代入新增的約束條件，如滿足說明新增約束未起限制作用，原最優(yōu)解不變，否則將新增約束直接反映到最終表再進(jìn)行分析。80（五）增加一個(gè)約束條件的分析四、各個(gè)參數(shù)變化后的討論例：設(shè)有如下的線性規(guī)劃模型上述問題中，增加一個(gè)約束條件分析最優(yōu)解變化。81用單純形法求得最終單純形表如表2.8所示：增加一個(gè)約束條件82將約束條件寫成取為基變量，直接反映到最終表：83將約束條件寫成取為基變量，直接反映到最終表：84上表中由基變量對(duì)應(yīng)向量構(gòu)成的矩陣不是單位陣，故進(jìn)行線性變換，85用對(duì)偶單純形法求解，結(jié)果見下表增加一個(gè)約束條件對(duì)最優(yōu)解的影響：增加一個(gè)約束條件：87§2.6

靈敏度分析、含義二、方法及步驟

三、判斷或計(jì)算依據(jù)（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)四、各個(gè)參數(shù)變化后的討論（二）分析bi變化影響——只引起基變量列數(shù)字變化（三）增加一個(gè)變量的分析（四）分析變化的影響（五）增加一個(gè)約束條件的分析2024/6/1388§2.7

參數(shù)線性規(guī)劃一、定義：2024/6/1389§2.7

參數(shù)線性規(guī)劃二、求解的步驟：1、令=0求解得最終單純形表；2、將參數(shù)的變化反映到最終單純形表中；3、找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點(diǎn)處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標(biāo)函數(shù)值隨參數(shù)變化的情況。2024/6/13901、（p60例11）本章例6中，約束條件3右端項(xiàng)不斷增大時(shí)，最優(yōu)解如何變化？三、舉例2024/6/13911、（p60例11）本章例6中，約束條件3右端項(xiàng)不斷增大時(shí)，最優(yōu)解如何變化？三、舉例2024/6/1392解：（1）先令，求得最終單純形表

如表所示：2024/6/1393（2）將參數(shù)的變化反映到最終單純形表中；（3）讓?duì)酥抵饾u增大，觀察原問題或?qū)ε紗栴}的變化，看哪一個(gè)先出現(xiàn)非可行解。2024/6/1394（2）將參數(shù)的變化反映到最終單純形表中；（3）讓?duì)酥抵饾u增大，觀察原問題或?qū)ε紗栴}的變化，看哪一個(gè)先出現(xiàn)非可行解。λ=1時(shí)，基變量x3=0，λ>1時(shí)，x3將取負(fù)值，因此最優(yōu)解的條件是，

當(dāng)時(shí)，用對(duì)偶單純表法求解：2024/6/1395迭代過程96迭代結(jié)果λ值繼續(xù)增大時(shí)，原問題和對(duì)偶問題都保持可行解，計(jì)算結(jié)束。2024/6/1397迭代結(jié)果2024/6/13982、（p61例12）求解下述參數(shù)線性規(guī)劃問題三、舉例2024/6/1399解：先令求得最優(yōu)解，并將Cj的變化值反映到最終單純形表中，2024/6/13100解：先令求得最優(yōu)解，并將Cj的變化值反映到最終單純形表中，2024/6/13101解：先令求得最優(yōu)解，并將Cj的變化值反映到最終單純形表中，由上表可知，當(dāng)時(shí)，表中解為最優(yōu)解。當(dāng)時(shí)，有正的檢驗(yàn)數(shù)。2024/6/13102繼續(xù)迭代得：2024/6/131032024/6/131043、（p62例13）：某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習(xí)本三種產(chǎn)品，該廠現(xiàn)有工人100人，每天白坯紙供應(yīng)量限制是30000kg，如果單獨(dú)生產(chǎn)各種產(chǎn)品時(shí)，每人每天生產(chǎn)原稿紙30捆、日記本30打、練習(xí)本30箱。已知原材料消耗為每捆原稿紙用白坯紙公斤，每打日記本用白坯紙公斤，每箱練習(xí)本用白坯紙公斤。又知每捆原稿紙可盈利2元，每打筆記本盈利3元，每箱練習(xí)本盈利1元。試決定（1）在現(xiàn)有生產(chǎn)條件下，工廠盈利最大的生產(chǎn)方案；2024/6/13105例：設(shè)該廠每天生產(chǎn)原稿紙、日記本、練習(xí)本的數(shù)量分別是，2024/6/131062310032000017/31/10-102100010-4/3-1/104000-10/3-1/10-50迭代求解：2024/6/131073、某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習(xí)本三種產(chǎn)品，該廠現(xiàn)有工人100人，每天白坯紙供應(yīng)量