對偶及對偶單純形法

1、關(guān)于對偶及對偶單純形法第1頁，共40頁，2022年，5月20日，22點31分，星期三本節(jié)主要內(nèi)容線性規(guī)劃的對偶模型對偶性質(zhì)對偶單純形法 學(xué)習(xí)要點： 1. 掌握線性規(guī)劃的對偶形式 2. 掌握對偶單純形法的解題思路及求解步驟第2頁，共40頁，2022年，5月20日，22點31分，星期三對偶現(xiàn)象普遍存在 “對偶”，在不同的領(lǐng)域有著不同的詮釋。在詞語中，它是一種修辭方式，指兩個字?jǐn)?shù)相等、結(jié)構(gòu)相似的語句，旨表達(dá)出相關(guān)或相反的意思。如：“下筆千言，離題萬里”周長一定，面積最大的矩形是正方形；面積一定，周長最小的矩形是正方形。 數(shù)學(xué)上也有如下對偶例子：“橫眉冷對千夫指，俯首甘為孺子?！?“天高任鳥飛，海闊憑

2、魚躍” 第3頁，共40頁，2022年，5月20日，22點31分，星期三一、線性規(guī)劃的對偶模型設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，生產(chǎn)每件產(chǎn)品所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時數(shù)列于下表 ：表1. 產(chǎn)品數(shù)據(jù)表 設(shè)備產(chǎn)品ABCD產(chǎn)品利潤（千元件） 甲 21402乙 22043設(shè)備可利用機時數(shù)（時） 1281612問：充分利用設(shè)備機時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？1. 對偶問題的現(xiàn)實來源第4頁，共40頁，2022年，5月20日，22點31分，星期三解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，最優(yōu)解為最優(yōu)值為如何安排生產(chǎn)，使獲利最多？則

3、數(shù)學(xué)模型為： 第5頁，共40頁，2022年，5月20日，22點31分，星期三反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么種機器的機時如何定價才是最佳決策？出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。 付出的代價最小， 且對方能接受。第6頁，共40頁，2022年，5月20日，22點31分，星期三在市場競爭的時代，廠長的最佳決策應(yīng)符合兩條：（1）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。 （2）競爭性原則。即在上述不吃虧原則下，機時總收費盡可能低一些，以便爭取更多用戶，最終將設(shè)備出租出去。第7頁，共40頁，2022年，5月20日，2

4、2點31分，星期三解：設(shè)A、B、C、D設(shè)備的機時價分別為y1、y2、y3、y4元，用單純形法求得最優(yōu)解為最優(yōu)值為則新的線性規(guī)劃數(shù)學(xué)模型為：第8頁，共40頁，2022年，5月20日，22點31分，星期三2. 原問題與對偶問題的對應(yīng)關(guān)系原問題（對偶問題）對偶問題（原問題）原始規(guī)劃與對偶規(guī)劃是同一組數(shù)據(jù)參數(shù),只是位置有所不同,所描述的問題實際上是同一個問題從另一種角度去描述.第9頁，共40頁，2022年，5月20日，22點31分，星期三線性規(guī)劃的對偶模型特點：目標(biāo)函數(shù)求極大值時，所有約束條件為號，變量非負(fù); 目標(biāo)函數(shù)求極小值時，所有約束條件為號，變量非負(fù).原始線性規(guī)劃問題對偶線性規(guī)劃問題對稱形式的線

5、性規(guī)劃第10頁，共40頁，2022年，5月20日，22點31分，星期三線性規(guī)劃的對偶模型例2 寫出線性規(guī)劃問題的對偶問題解：由于若給出的線性規(guī)劃不是對稱形式，所以先將它化成對稱形式，然后再寫出相應(yīng)的對偶問題。第11頁，共40頁，2022年，5月20日，22點31分，星期三解：首先將原問題變形為則對偶模型為：第12頁，共40頁，2022年，5月20日，22點31分，星期三線性規(guī)劃的對偶變換規(guī)則(單向)原問題（或?qū)ε紗栴}）對偶問題（或原問題）約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項目標(biāo)函數(shù) max目標(biāo)函數(shù) min約束條件m個m個變量00=無約束變量n個n個約束條件00無約束

6、=第13頁，共40頁，2022年，5月20日，22點31分，星期三對偶問題的形成min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unr原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)； 原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問

7、題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)，用 表示 原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)，用 表示第14頁，共40頁，2022年，5月20日，22點31分，星期三例4:寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為第15頁，共40頁，2022年，5月20日，22點31分，星期三定理6.1 (對合性) 對偶線性規(guī)劃的對偶問題是原始線性規(guī)劃問題。對偶定義對偶定義二、對偶性質(zhì)（選讀）第16頁，共40頁，2022年，5月20日，22點31分，星期三定理6.2 弱對偶原理(弱對偶性)：設(shè) 和 分別是問題(LP)和(DP)的可行解，則必有推論1: 原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)

8、函數(shù)值的上界；反之，對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的下界。第17頁，共40頁，2022年，5月20日，22點31分，星期三推論2: 在一對對偶問題（LP）和（DP）中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解；這也是對偶問題的無界性。推論3：在一對對偶問題（LP）和（DP）中，若一個有可行解，而另一個無可行解，則該可行的問題目標(biāo)函數(shù)值無界。第18頁，共40頁，2022年，5月20日，22點31分，星期三定理6.3 最優(yōu)性判定定理：如果 是原問題的可行解，則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。是其對偶問題的可行解，并且:定理6.4. 在一對對偶問題（LP

9、）和（DP）中，若任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且對應(yīng)的最優(yōu)值相等。第19頁，共40頁，2022年，5月20日，22點31分，星期三定理6.6 強對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。推論4：（LP）與（DP）要么兩者都有最優(yōu)解，要么都無最優(yōu)解。定理6.7 互補松弛性：設(shè)X0和Y0分別是(LP) 問題和 (DP) 問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs為松弛變量、Ys為剩余變量.互補松弛條件第20頁，共40頁，2022年，5月20日，22點31分，星期三對偶性質(zhì)的應(yīng)用 借助以上性質(zhì)可以證明，在用單純形法求解原問題的

10、迭代過程中，單純形表右列中的元素對應(yīng)于原問題的基本可行解，底行中松弛變量對應(yīng)的元素恰好構(gòu)成對偶問題的基本解。逐次迭代下去，當(dāng)?shù)仔袑?yīng)于對偶問題的解也變成基本可行解（底行元素全非負(fù)）時，原問題和對偶問題同時達(dá)到最優(yōu)解. 即此時對偶問題的這個基本可行解就是它的最優(yōu)解。 用單純形方法求解原線性規(guī)劃的過程中，每次迭代都保證得到原問題的一個基本可行解，底行某些元素對應(yīng)于對偶問題的基本解. 單純形法的迭代的過程既可以看作使原問題的基本可行解逐步變?yōu)樽顑?yōu)解（此時底行元素非負(fù))的過程，也可看作使對偶問題的基本解逐步變成基本可行解的過程。 第21頁，共40頁，2022年，5月20日，22點31分，星期三根據(jù)性質(zhì)

11、1（對偶問題的對偶是它本身），在用單純形法求解LP時也可這樣考慮：從對偶問題的某個基本可行解開始，每次迭代總保證得到對偶問題的一個基本可行解（底行元素均非負(fù)），通過逐步迭代，當(dāng)對偶問題達(dá)到最優(yōu)解時，根據(jù)對偶理論，對偶問題的對偶即原問題也達(dá)到最優(yōu)解。對偶單純形法 適用情況：當(dāng)原問題沒有初始的基本可行解，但是對偶問題有初始的基本可行解（初始表格容易滿足 ）時，用此方法。 優(yōu)點：當(dāng)原問題沒有初始的基本可行解，不需要借助大M法或二階段法構(gòu)造新的模型.對偶單純形法的基本思想第22頁，共40頁，2022年，5月20日，22點31分，星期三三、對偶單純形法注意：它并不是求解對偶問題的單純形法，而是一 個直接

12、求解原LP問題的新算法。 對偶單純形法是求解LP問題的另一個基本方法。它是根據(jù)對偶理論和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。第23頁，共40頁，2022年，5月20日，22點31分，星期三對偶單純形法找出一個DP的基本可行解LP是否可行保持DP為基本可行解情況下轉(zhuǎn)移到LP的另一個基本解最優(yōu)解是否循環(huán)結(jié)束第24頁，共40頁，2022年，5月20日，22點31分，星期三1.對偶單純形法的迭代步驟1）將原問題化為標(biāo)準(zhǔn)形,寫出相應(yīng)的表格;2）利用容許的運算建立滿足 三個特點的單純形表;3）檢查右列元素，若全非負(fù)，即表格滿足 四個特點，結(jié)束運算；否則，進(jìn)去第4）步；4）確定離基變量. 取右列

13、中最小的負(fù)元素所在的行設(shè)是第行.第25頁，共40頁，2022年，5月20日，22點31分，星期三5) 確定進(jìn)基變量所在列對應(yīng)的變量取為進(jìn)基變量;觀察該行豎線左邊的元素若所有則無可行解，結(jié)束運算;否則，按如下規(guī)則從負(fù)系數(shù)中選擇一個記為第26頁，共40頁，2022年，5月20日，22點31分，星期三6) 進(jìn)行旋轉(zhuǎn)運算利用容許的運算將變?yōu)?,該列其它元素變?yōu)?,從而實現(xiàn)將變?yōu)榛兞康哪康?7）觀察得到的新表(滿足 ). 若右列元素均非負(fù), 則已得最優(yōu)解, 結(jié)束運算;否則, 返回第4)步.第27頁，共40頁，2022年，5月20日，22點31分，星期三例 5.（教材P79 例5.4）用對偶單純形法求解

14、：引入松弛變量得到標(biāo)準(zhǔn)型線性規(guī)劃解：第28頁，共40頁，2022年，5月20日，22點31分，星期三構(gòu)造對偶單純形表選取離基變量選取進(jìn)基變量 -1 -2 -3 1 0 -5 -2 -2 -1 0 1 -6 3 4 5 0 0 0滿足 , 但不滿足第29頁，共40頁，2022年，5月20日，22點31分，星期三 0 -1 -5/2 1 -1/2 -2 1 1 1/2 0 -1/2 3 0 1 7/2 0 3/2 -9 0 1 5/2 -1 1/2 2 1 0 -2 1 -1 1 0 0 1 1 1 -11滿足 , 但不滿足滿足 第30頁，共40頁，2022年，5月20日，22點31分，星期三滿足

15、 是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解. 略去松弛變量得原LP問題的最優(yōu)解為最優(yōu)值為 0 1 5/2 -1 1/2 2 1 0 -2 1 -1 1 0 0 1 1 1 -11第31頁，共40頁，2022年，5月20日，22點31分，星期三例6. 用對偶單純形法求解：引入松弛變量得到標(biāo)準(zhǔn)型線性規(guī)劃解：第32頁，共40頁，2022年，5月20日，22點31分，星期三構(gòu)造對偶單純形表選取離基變量選取進(jìn)基變量-2 -1 -4 0 1 0 -2-2 -2 0 -4 0 1 -312 8 16 12 0 0 0滿足 , 但不滿足第33頁，共40頁，2022年，5月20日，22點31分，星期三-2 -1 -4 0

16、1 0 -2-2 -2 0 -4 0 1 -312 8 16 12 0 0 0-2 -1 -4 0 1 0 -21/2 1/2 0 1 0 -1/4 3/4 6 2 16 0 0 3 -9滿足 , 但不滿足第34頁，共40頁，2022年，5月20日，22點31分，星期三 -2 -1 -4 0 1 0 -21/2 1/2 0 1 0 -1/4 3/4 6 2 16 0 0 3 -9 2 1 4 0 -1 0 2-1/2 0 -2 1 1/2 -1/4 -1/4 2 0 8 0 2 3 -13滿足 , 但不滿足第35頁，共40頁，2022年，5月20日，22點31分，星期三 1 1 0 2 0 -

17、1/2 3/21/4 0 1 -1/2 -1/4 1/8 1/8 0 0 0 4 4 2 -14 2 1 4 0 -1 0 2-1/2 0 -2 1 1/2 -1/4 -1/4 2 0 8 0 2 3 -13滿足 第36頁，共40頁，2022年，5月20日，22點31分，星期三 1 1 0 2 0 -1/2 3/21/4 0 1 -1/2 -1/4 1/8 1/8 0 0 0 4 4 2 -14滿足 是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解. 略去松弛變量得原LP問題的最優(yōu)解為最優(yōu)值為第37頁，共40頁，2022年，5月20日，22點31分，星期三 對偶單純形法應(yīng)注意的問題： 對偶單純形法是直接求解原線性規(guī)劃是一種方法，而不是去求對偶問題的最優(yōu)解. 初始表中一定要滿足對偶問題的基本解可行，即底行中對應(yīng)于單位子塊的元素為零，其余元素非負(fù). 對偶單純形法與普通單純形法的換基順序不一樣，普