對(duì)偶及對(duì)偶單純形法

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

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

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

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

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

6、=第13頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)31分，星期三對(duì)偶問(wèn)題的形成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原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)； 原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。原始問(wèn)

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

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

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

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

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

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

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

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

15、 是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解. 略去松弛變量得原LP問(wèn)題的最優(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頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)31分，星期三例6. 用對(duì)偶單純形法求解：引入松弛變量得到標(biāo)準(zhǔn)型線性規(guī)劃解：第32頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)31分，星期三構(gòu)造對(duì)偶單純形表選取離基變量選取進(jìn)基變量-2 -1 -4 0 1 0 -2-2 -2 0 -4 0 1 -312 8 16 12 0 0 0滿(mǎn)足 , 但不滿(mǎn)足第33頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)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滿(mǎn)足 , 但不滿(mǎn)足第34頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)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滿(mǎn)足 , 但不滿(mǎn)足第35頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)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滿(mǎn)足 第36頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)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滿(mǎn)足 是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解. 略去松弛變量得原LP問(wèn)題的最優(yōu)解為最優(yōu)值為第37頁(yè)，共40頁(yè)，2022年，5月20日，22點(diǎn)31分，星期三 對(duì)偶單純形法應(yīng)注意的問(wèn)題： 對(duì)偶單純形法是直接求解原線性規(guī)劃是一種方法，而不是去求對(duì)偶問(wèn)題的最優(yōu)解. 初始表中一定要滿(mǎn)足對(duì)偶問(wèn)題的基本解可行，即底行中對(duì)應(yīng)于單位子塊的元素為零，其余元素非負(fù). 對(duì)偶單純形法與普通單純形法的換基順序不一樣，普