第3章對偶問題與對偶理論(2015917)

1、OROR課件課件LP對于所有的線性規(guī)劃問題基本可以求解；可以獲得的信息、的信息以及的信息等，如生產(chǎn)計劃問題。：有沒有什么方法可以有沒有什么方法可以因因“構(gòu)造基構(gòu)造基”，給給LP問題求解帶來的繁瑣？問題求解帶來的繁瑣？ 導(dǎo)導(dǎo) 學(xué)學(xué)-回顧回顧OROR課件課件運 籌 帷 幄 之 中決 勝 千 里 之 外OROR課件課件LP3.1 對偶問題及其數(shù)學(xué)模型3.2 對偶問題的性質(zhì)3.3 原問題與對偶問題的對應(yīng)關(guān)系3.4 對偶問題的經(jīng)濟解釋3.5 對偶單純形法3.6 對偶單純形法的應(yīng)用 導(dǎo)導(dǎo) 學(xué)學(xué)-主要內(nèi)容主要內(nèi)容對偶問題的性質(zhì)，對偶模型的建立和對偶單純形法迭代原理。原問題與對偶問題在模型和解方面的對應(yīng)關(guān)系。

2、OROR課件課件 導(dǎo)導(dǎo) 學(xué)學(xué)-重點與難點重點與難點OROR課件課件LPOROR課件課件LP常識： 方形中：周長一定，面積最大；面積一定，周長最短。引例：OROR課件課件LP引例：有一機械廠在年度內(nèi)計劃生產(chǎn)甲乙兩種產(chǎn)品，兩種產(chǎn)品分別需要在A,B,C,D四種不同機床上加工。各產(chǎn)品在各機床上所需的加工工時及每種機床在年內(nèi)可以提供的機器臺時、單位產(chǎn)品獲利如下表。問如何確定甲、乙產(chǎn)品的產(chǎn)量，才能使工廠總利潤最大？ A B C D 單 位 利 潤（ 元 ） 甲 乙 2 2 1 2 4 0 0 4 2 3 可 供 臺 時 1200 800 1600 1200 機 器 工 時 產(chǎn) 品 OROR課件課件LP首先

3、站在廠商的角度，如何安排生產(chǎn)，使利潤達最大？然后站在承租人的角度，如何安排，使成本達最??？OROR課件課件LP解：設(shè)x1和x2分別表示甲乙兩種產(chǎn)品的年產(chǎn)量，則有:0,12004160048002120022322121212121xxxxxxxxxxMaxZOROR課件課件LP解：設(shè)y1, y2 , y3 , y4分別表示A, B, C, D四種機床每臺時出租價格，則:：出租生產(chǎn)1單位甲所耗機床臺時所得的收入不能低于生產(chǎn)1單位甲所得到的收入：20424321yyyy同理，對于乙產(chǎn)品，有：340224321yyyy出租設(shè)備的總收入：4321120016008001200yyyySOROR課件課件

4、LP歸納起來為:20424321yyyy340224321yyyy4321120016008001200yyyyMinS0,4321yyyyOROR課件課件LPOROR課件課件LP原”與“對”模型對應(yīng)關(guān)系：OROR課件課件LP兩模型的對應(yīng)關(guān)系：OROR課件課件LP方法一： 按程序先化為“一致性”形式，再寫對偶問題 例 3.2OROR課件課件LP例 3.2 解解：調(diào)整后，原問題變?yōu)?231231231231230,1,2,3min6352316251066jjSxxxxxxxxxxxxxxxx y1y2y3y3OROR課件課件LPOROR課件課件LP方法二：按對應(yīng)關(guān)系 直接按上表所列的對應(yīng)關(guān)系來

5、寫y2y1y3例 3.2OROR課件課件LPOROR課件課件LP對稱性：原問題與對偶問題互為對偶；最優(yōu)bYMinS XCMaxZ bYXC 弱對偶性：OROR課件課件LP：弱對偶性的推論； 原（對）無界，則對（原）無可行解，但不存在可逆性（p37）：若 是原、對的可行解，當(dāng)bYXC YX, bYXC 則： 是最優(yōu)解YX, OROR課件課件LP：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且原、對目標(biāo)值相等。1BCYB v書中證明時的表達式：01ABCCB 推導(dǎo)：OROR課件課件LP01ABCCB XABCCbBCXBCCXNBCCXBBCCbBCXBCCXNBCCbBCXCXCXBCNXBCbB

6、CXCXCXCXXXCCCCXZXBNXBbBXbXXXINBAXBBSBSNBNBBBBSBSNBNBSSNNSBNBBSSNNBBSNBSNBSNBSNB)()()()()()(111111111111111 OROR課件課件LP舉例說明：若 分別是原問題和對偶問題的可行解，那么 當(dāng)且僅當(dāng) 為最優(yōu)解 此性質(zhì)描述了原（對）的最優(yōu)解與對（原）的虛變量之間的內(nèi)在聯(lián)系。XB XN XS 0 Ys1 CN-CBB-1N -Ys2 -CBB-1 -Y 原（對）的檢驗數(shù)與對（原）的基本可行解的對應(yīng)關(guān)系：YX, YX, OROR課件課件LPbi 1200 800 1600 1200 0 0 bB YB C

7、 y1 y2 y3 y4 y5 y6 1600 800 y3 y2 1/8 3/2 1/4 0 1 -1/2 -1/4 1/8 1 1 0 2 0 -1/2 Si bi-Si 1200 800 1600 800 -400 -200 0 0 0 400 400 200 cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 2 0 3 x3 x1 x6 x2 0 400 400 200 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0 Zj Cj-Zj 2 3 0 3/2 1/8 0 0 0

8、0 -3/2 -1/8 0 Y=(0, 3/2, 1/8, 0, 0, 0) S=1400X=(400, 200, 0, 0, 0, 400) Z=1400OROR課件課件LP OROR課件課件LP有最優(yōu)解有最優(yōu)解無界解無界解無可行解無可行解有最優(yōu)解有最優(yōu)解一定一定不可能不可能不可能不可能無界解無界解不可能不可能不可能不可能可能可能無可行解無可行解不可能不可能可能可能可能可能OROR課件課件LPOROR課件課件LPOROR課件課件LP資源（資源（bi ）的）的單位改變量單位改變量引起目標(biāo)函數(shù)值（引起目標(biāo)函數(shù)值（Z ）的改變量，通常稱為影子價格（的改變量，通常稱為影子價格（shadow pric

9、e）或邊）或邊際價格（際價格（marginal price）。）。OROR課件課件LPOROR課件課件LP因為影子價格能指出各種資源在實現(xiàn)企業(yè)最優(yōu)目標(biāo)時的影響作用，影子價格越高的資源，表明它對目目標(biāo)增益標(biāo)增益的影響愈大，同時也表明這種資源對該企業(yè)來說愈稀缺和愈貴重，企業(yè)的管理者就應(yīng)該更加重視對這種資源的管理，通過挖潛革新、降低消耗或及時補充該種資源，以保證給企業(yè)帶來較大的收益。企業(yè)的決策者可以把本企業(yè)資源的影子價格與當(dāng)時的市場價相比較，當(dāng)某種資源的影子價格高于市場價格時，則企業(yè)可以買進該種資源；而當(dāng)某種資源的影子價格低于市場價格時（特別是當(dāng)影子價格為零時），則企業(yè)可以賣出賣出該種資源，以獲得較

10、大的利潤。OROR課件課件LP最優(yōu)原問題（MaxZ)：保持原問題可行（bi0)當(dāng)所有的檢驗數(shù)滿足最優(yōu)性檢驗 （cj-zj0）即：保持原問題可行，將對偶問題由不可行轉(zhuǎn)化為可行對偶問題（MinS）：保持對偶問題可行 （ cj-zj0）當(dāng)所有的bi0，則即：保持對偶問題可行，將原問題由不可行化為可行OROR課件課件LP計算步驟：找出基本解，滿足cj-zj0bi0?Y最優(yōu)解Ni=LaLj0?0LjaY無解N找出基本解，滿足cj-zj0?OROR課件課件LP解：化標(biāo)準(zhǔn)型OROR課件課件LP列入單純形表：換出變量：Minbi|bi0bLMin-1200/-2;-800/-2;-1200/-4=300-4O

11、ROR課件課件LP-1-2OROR課件課件LPp有非基變量的檢驗數(shù)為0，多重解最優(yōu)解為：X（0,3/2,1/8,0,0,0） S=1400OROR課件課件LP OROR課件課件LP新增約束條件AYN?OROR課件課件LP：用一般單純形法求出的最優(yōu)單純形表如下表OROR課件課件LPjcicBXb1x2x3x4x5x2x1xjZjjcZ jc 40 45 24 0 0 ic BX b 1x 2x 3x 4x 5x 45 2x 20 0 1 -1/3 1 -2/3 40 1x 20 1 0 1 -1 1 jZ 40 45 25 5 10 jjcZ 0 0 -1 -5 -10 16615,0 xxx1

12、15x jc 40 45 24 0 0 0 ic BX b 1x 2x 3x 4x 5x 6x 45 2x 20 0 1 -1/3 1 -2/3 0 40 1x 20 1 0 1 -1 1 0 0 6x 15 1 0 0 0 0 1 jZ 40 45 25 5 10 0 jjcZ 0 0 -1 -5 -10 0 OROR課件課件LPjcicBXb1x2x3x4x5x2x1xjZjjcZ jc 40 45 24 0 0 0 ic BX b 1x 2x 3x 4x 5x 6x 45 2x 20 0 1 -1/3 1 -2/3 0 40 1x 20 1 0 1 -1 1 0 0 6x -5 0 0 -1 1 -1 1 jZ 40 45 25 5 10 0 jjcZ 0 0 -1 -5 -10 0 OROR課件課件LPjcicBXb1x2x3x4x5x2x1xjZjjcZ-1 jc 40 45