運(yùn)籌學(xué)第6講：對(duì)偶問(wèn)題的基本概念

1、第6講：對(duì)偶問(wèn)題的基本概念1一、對(duì)偶問(wèn)題的提出例1：習(xí)題3-1運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗和各種資源的限制量，如下表所示。該工廠每生產(chǎn)一件甲產(chǎn)品可獲利2元，每生產(chǎn)一件乙產(chǎn)品可獲利3元，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？ 2例2：習(xí)題3-2 對(duì)于例1，假設(shè)該工廠的決策者決定不生產(chǎn)甲、乙兩種產(chǎn)品，而是將所有資源外售。你作為一個(gè)收購(gòu)者，該如何決策來(lái)購(gòu)買這些資源？ 運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念3設(shè)有LP問(wèn)題(P)的數(shù)學(xué)模型為：（P）： max Z = CX s.t. AX b X 0則稱(D)

2、是(P)的對(duì)偶問(wèn)題，(P)是原問(wèn)題式中:設(shè)另一個(gè)LP問(wèn)題(D)的數(shù)學(xué)模型為： s.t. YAC Y 0（D）： min = Yb式中:運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念4（P）： max Z = CX s.t. AX b X 0 (P)和(D)具有對(duì)稱性，即互為對(duì)偶 上述兩種形式稱為L(zhǎng)P問(wèn)題的對(duì)稱形式，請(qǐng)不要混淆對(duì)稱形式和標(biāo)準(zhǔn)形式 s.t. YAC Y 0（D）： min = Yb運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念5例3：寫出下述LP問(wèn)題的對(duì)偶問(wèn)題max Z = 2x1 3x2 + 4x3 s.t. 2x1 + 3x2 5x3 2 3x1 + x2 + 7x3 3 -x1 + 4x2 + 6x

3、3 5 x1, x2, x3 0運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念6二、非對(duì)稱形式的原-對(duì)偶問(wèn)題關(guān)系例4(P33)：求下述LP問(wèn)題的對(duì)偶問(wèn)題max Z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 b1 a21x1 + a22x2 + a23x3 b2 a31x1 + a32x2 + a33x3 b3 x10, x20, x3 無(wú)約束運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念7可根據(jù)以下規(guī)則求LP問(wèn)題的對(duì)偶問(wèn)題，分3步驟(P34表3-3) 若(P)為max型,則(D)為min型，反之亦然；同時(shí)，(P):bT = (D):C； (P):AT = (D):

4、A； (P):CT = (D):b(D)中約束條件取向規(guī)則：(P)的第j個(gè)變量xj對(duì)應(yīng)于(D)的第j個(gè)約束式 若(P)為max型，且xj0，則(D)的第j個(gè)約束式取向?yàn)椤啊?若(P)為min型，且xj0，則(D)的第j個(gè)約束式取向?yàn)椤啊?若(P)中的xj無(wú)約束，則(D)中的第j個(gè)約束式取向?yàn)椤啊?其余情況與對(duì)稱形式相同(D)中變量取值規(guī)則：(P)的第i個(gè)約束式對(duì)應(yīng)于(D)的第i個(gè)變量yi 若(P)為max型，且第i個(gè)約束式取向?yàn)椤啊?，則yi 0 若(P)為min型，且第i個(gè)約束式取向?yàn)椤啊?，則yi 0 若(P)中的第i個(gè)約束式為等式，則yi無(wú)約束 其余情況與對(duì)稱形式相同8 (P)中約束式為對(duì)稱

5、形式，則(D)中相應(yīng)變量為對(duì)稱形式； (P)中約束式為非對(duì)稱形式，則(D)中相應(yīng)變量為非對(duì)稱形式； (P)中變量為對(duì)稱形式，則(D)中相應(yīng)約束式為對(duì)稱形式； (P)中變量為非對(duì)稱形式，則(D)中相應(yīng)約束式為非對(duì)稱形式； 對(duì)稱的變量與對(duì)稱的約束式相對(duì)應(yīng)！不對(duì)稱的變量與不對(duì)稱的約束式相對(duì)應(yīng)！運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念 對(duì)稱對(duì)應(yīng)對(duì)稱，不對(duì)稱對(duì)應(yīng)不對(duì)稱！9例5：求下述LP問(wèn)題的對(duì)偶問(wèn)題max Z = -7x1 + 14x2 + 3x3 s.t. x1 + 6x2 + 28x3 5 2x1 3x2 + 17x3 6 x1 + x2 4x3 7 x10, x20, x3 無(wú)約束運(yùn)籌學(xué) 第6講：對(duì)偶

6、問(wèn)題的基本概念10例6：求下述LP問(wèn)題的對(duì)偶問(wèn)題max Z = 2x1 3x2 + 4x3 s.t. 2x1 + 3x2 5x3 2 3x1 + x2 + 7x3 3 x1 + 4x2 + 6x3 5 x1 , x2 0, x3 0運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念11習(xí)題3-3（1,3）max Z = 2x1 + 3x2 5x3 + x4 s.t. 運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念12（P）： max Z = CX s.t. AX b X 0 s.t. YAC Y 0（D）： min = Yb給定一對(duì)對(duì)稱型對(duì)偶問(wèn)題：有如下5個(gè)定理：定理1 (對(duì)稱性定理): 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題運(yùn)籌學(xué) 第

7、6講：對(duì)偶問(wèn)題的基本概念三、對(duì)偶問(wèn)題的基本性質(zhì)(1)13定理2 (弱對(duì)偶定理): 設(shè) 和 分別是(P)和(D)的可行解，則必有推論1：若 和 分別是(P)和(D)的可行解，則 是(D)的min的下界， 是(P)的max Z的上界推論2：在一對(duì)(P)和(D)中，若其中一個(gè)問(wèn)題可行，但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題無(wú)可行解推論3：在一對(duì)(P)和(D)中，若一個(gè)問(wèn)題有可行解，而另一個(gè)問(wèn)題無(wú)可行解，則有可行解的問(wèn)題無(wú)界運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念14例1：試證如下LP問(wèn)題無(wú)界max Z = x1+ 2x2 s.t. x1 + x2 + x3 2 2x1 + x2 x3 1 x1, x2, x3 0運(yùn)

8、籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念15定理3 (最優(yōu)性判別定理): 若X*和Y*分別是(P)和(D)的可行解，且CX* = Y*b，則X*和Y*分別是(P)和(D)的最優(yōu)解定理4 (強(qiáng)對(duì)偶定理): 若 (P)和(D)都有可行解，則它們都有最優(yōu)解，且Z* =*推論4：若(P)和(D)中的任意一個(gè)有最優(yōu)解，則另一個(gè)也必有最優(yōu)解，且Z* =*運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念16綜上所述，(P)和(D)的解的關(guān)系存在下列三種情況： 都有最優(yōu)解，且CX* = Y*b 一個(gè)問(wèn)題有無(wú)界解，另一個(gè)問(wèn)題無(wú)可行解 兩個(gè)都無(wú)可行解（例：習(xí)題3-4）max Z = x1+ x2 s.t. x1 x2 1 x1 + x2 1 x1, x2 0說(shuō)明如下LP問(wèn)題及其對(duì)偶問(wèn)題的解的情況運(yùn)籌學(xué) 第6講：對(duì)偶問(wèn)題的基本概念17判斷： 如果線性規(guī)劃的原問(wèn)題存在可行解，則對(duì)偶問(wèn)題也一定存在可行解 如果線性規(guī)劃的對(duì)