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

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

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

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

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

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

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

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