NEW線性規(guī)劃對(duì)偶理論

1、返回繼續(xù)單純形法的進(jìn)一步討論-單純形法的矩陣描述 及對(duì)偶理論為什麼要研究單純形法的矩陣描述？ 進(jìn)一步討論修正單純形法 便于理論推導(dǎo)（如對(duì)偶定理的證明）1、準(zhǔn)備工作：（1）標(biāo)準(zhǔn)型的矩陣形式 （2）將式中矩陣寫成分塊矩陣形式 2、將分塊形式代入矩陣形式標(biāo)準(zhǔn)型，得出兩個(gè)基本表達(dá)式：（1）由約束條件 可得 用非基變量表示基變量的表達(dá)式：（2-1） （2）將式（2-1）代入目標(biāo)函數(shù)的表達(dá)式， 可得：用非基變量表示目標(biāo)函數(shù)的表達(dá)式：5（3）借助一個(gè)恒等式推出用非基變量表示 目標(biāo)函數(shù)的另一個(gè)等價(jià)表達(dá)式：代入式（2-2），并令 （2-4） 單純形乘子 6返回繼續(xù)線性規(guī)劃的對(duì)偶問題一、對(duì)偶問題的提出二、原問題與

2、對(duì)偶問題的數(shù)學(xué)模型三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種 產(chǎn)品， 有關(guān)數(shù)據(jù)如下表： 設(shè)備A 設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí) 5時(shí)產(chǎn)品產(chǎn)品D一、對(duì)偶問題的提出 （從生產(chǎn)計(jì)劃問題到對(duì)資源的定價(jià)）如何安排生產(chǎn)，使獲利最多？廠家設(shè) 產(chǎn)量 產(chǎn)量 設(shè)：設(shè)備A 元時(shí) 設(shè)備B 元時(shí) 調(diào)試工序 元時(shí)收購(gòu) 付出的代價(jià)最小， 且對(duì)方能接受。出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤(rùn)。 設(shè)備A 設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí) 5時(shí)D廠家能接受的條件：收購(gòu)方的意愿：?jiǎn)挝划a(chǎn)品(消耗資源)出租收入不低于2元單位產(chǎn)品 (消耗資源)出租收入不低于1元出

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

4、偶問題:令 ，得對(duì)偶問題為：證畢。三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系 原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）例:對(duì)偶問題為返回結(jié)束線性規(guī)劃的對(duì)偶問題返回繼續(xù)第二節(jié) 對(duì)偶問題的基本性質(zhì)引例對(duì)稱性弱對(duì)偶性最優(yōu)性對(duì)偶性（強(qiáng)對(duì)偶性）互補(bǔ)松弛性對(duì)偶問題的基本性質(zhì)一、對(duì)稱定理： 定理： 對(duì)偶問題的對(duì)偶是原問題。設(shè)原問題（1） 對(duì)偶問題（2）二、弱對(duì)偶性定理： 若 和 分別是原問題（1）及對(duì)偶問題（2）的可行解，則有 證明：對(duì)偶問題的基本性質(zhì)從弱對(duì)偶性可得到以下重要結(jié)論：（1）極大化問題（原問題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的下界。（2）極小化問題（對(duì)偶問題）的任一可行解所對(duì)應(yīng)的目標(biāo)

5、函數(shù)值是原問題最優(yōu)目標(biāo)函數(shù)值的上界。（3）若原問題可行，但其目標(biāo)函數(shù)值無(wú)界，則對(duì)偶問題無(wú)可行解。（4）若對(duì)偶問題可行，但其目標(biāo)函數(shù)值無(wú)界，則原問題無(wú)可行解。（5）若原問題有可行解而其對(duì)偶問題無(wú)可行解，則原問題目標(biāo)函數(shù)值無(wú)界。（6）對(duì)偶問題有可行解而其原問題無(wú)可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無(wú)界。原問題對(duì)偶問題對(duì)偶問題的基本性質(zhì)定理三 最優(yōu)性準(zhǔn)則定理 若 、 分別為對(duì)稱形式對(duì)偶線性規(guī)劃的可行解，且兩者目標(biāo)函數(shù)的相應(yīng)值相等，C =b ，則 ， 分別為原始問題和對(duì)偶問題的最優(yōu)解。 C = bCXYb弱對(duì)偶定 理已 知結(jié)論最優(yōu)解定義X=CX bY=特別取 bYbCXCC Yb證明思路 證明：原問題與對(duì)偶

6、問題的解一般有三種情況：一個(gè)有有限最優(yōu)解 另一個(gè)有有限最優(yōu)解。一個(gè)有無(wú)界解 另一個(gè)無(wú)可行解。兩個(gè)均無(wú)可行解。四、對(duì)偶定理（強(qiáng)對(duì)偶性）： 若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。對(duì)偶問題的基本性質(zhì)五、互補(bǔ)松弛性： 若 分別是原問題（1）與對(duì)偶問題（2）的可行解， 分別為（1）、（2）的松弛變量，則： 即：為最優(yōu)解原問題第i條約束 A的第i行 說(shuō)明：在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件去嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。另一方面：對(duì)偶問題的第j條約束五、互補(bǔ)松弛性： 若 分別是原

7、問題（1）與對(duì)偶問題（2）的可行解， 分別為（1）、（2）的松弛變量，則：為最優(yōu)解原理：在一對(duì)互為對(duì)偶的線型的規(guī)劃問題中，原問題的變量和對(duì)偶問題的約束是一一對(duì)應(yīng)的，原問題的約束和對(duì)偶問題的變量也是一一對(duì)應(yīng)的。解釋：互補(bǔ)松弛性描述了線型規(guī)劃問題達(dá)到最優(yōu)時(shí)，原問題（或?qū)ε紗栴}）的變量取值和對(duì)偶問題（或原問題）約束的松緊性之間的對(duì)應(yīng)關(guān)系。當(dāng)線型規(guī)劃達(dá)到最優(yōu)時(shí)，有下列關(guān)系：1、如果原問題的某一約束為緊約束（松弛變量為零），該約束對(duì)應(yīng)的對(duì)偶變量應(yīng)大于或等于零。2、如果原問題的某一約束為松約束（松弛變量大于零），該約束對(duì)應(yīng)的對(duì)偶變量必為零。3、如果原問題的某一變量大于零，該變量對(duì)應(yīng)的對(duì)偶約束為緊約束。4、如果原問題的某一變量等于零，該變量對(duì)應(yīng)的對(duì)偶約束可能是緊約束，也可能是松約束。互補(bǔ)松弛定理應(yīng)用：（1）從已知的最優(yōu)對(duì)偶解，求原問題最優(yōu)解，反之亦然。（2）證實(shí)原問題可行解是否為最優(yōu)解。（3）從不同假設(shè)來(lái)進(jìn)行試算，從而研究原始、對(duì)偶問題最優(yōu)解的一般性質(zhì)。（4）非線性的方面的應(yīng)用。以上性質(zhì)同樣適用于非對(duì)稱形式。書P52，例2已知：X=(x1，x2)T =(7/6，4/3