對(duì)偶和對(duì)偶單純形法應(yīng)用

1、關(guān)于對(duì)偶與對(duì)偶單純形法的應(yīng)用第一張，PPT共五十六頁，創(chuàng)作于2022年6月一、對(duì)偶問題的提出每一個(gè)線性規(guī)劃問題，都存在每一個(gè)與它密切相關(guān)的線性規(guī)劃的問題，我們稱其為原問題，另一個(gè)為對(duì)偶問題。原問題：某工廠在計(jì)劃期內(nèi)安排、兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示，該工廠每生產(chǎn)一單位產(chǎn)品 可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，問工廠應(yīng)分別生產(chǎn)多少 產(chǎn)品和產(chǎn)品，才能使工廠獲利最多？第二張，PPT共五十六頁，創(chuàng)作于2022年6月解：設(shè)x1為產(chǎn)品I的計(jì)劃產(chǎn)量，x2產(chǎn)品的計(jì)劃產(chǎn)量，則有Max z=50 x1 +100 x2x1 +x2 3002x1+x2 400 x2 250 x1，x

2、20第三張，PPT共五十六頁，創(chuàng)作于2022年6月假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么該廠的廠長應(yīng)該如何來確定合理的租金呢？對(duì)原廠：租金收入自己組織生產(chǎn)的收入對(duì)租借廠：總租金最低變量改變產(chǎn)品設(shè)備設(shè)備不再是約束條件，必須從產(chǎn)品入手設(shè)y1，y2，y3是A、B、C每小時(shí)的出租價(jià)格對(duì)于產(chǎn)品I：每件I自行生產(chǎn)的收入是50元，租金收入是y1+2y2元。對(duì)于產(chǎn)品來說，自行生產(chǎn)收入100元，租金收入是y1+y2+y3元第四張，PPT共五十六頁，創(chuàng)作于2022年6月Minw=300y1+400y2+250y3（設(shè)備租用總收入） S.T y1+2y2 50 y1 + y2+y3 100其中y1，y

3、2，y3均0比較一下與原線性規(guī)劃問題的不同？1、目標(biāo)函數(shù) 2、變量 3、約束條件第五張，PPT共五十六頁，創(chuàng)作于2022年6月這樣從兩個(gè)不同的角度來考慮同一個(gè)工廠的最大利潤（最小租金）的問題，所建立起來的兩個(gè)線性模型就是一對(duì)對(duì)偶問題，其中一個(gè)叫做原問題，而另外一個(gè)叫對(duì)偶問題。矩陣形式比較：解1：MaxZ=CX AX b X 0 解2：minW=b Y A Y C Y 0第六張，PPT共五十六頁，創(chuàng)作于2022年6月二、原問題和對(duì)偶問題的轉(zhuǎn)化1、目標(biāo)函數(shù)MAXMin2、約束條件變量約束條件n個(gè)變量n個(gè)約束條件0 變量 0約束條件 0 變量 0約束條件=0變量無約束要點(diǎn)：max為反向關(guān)系（約束條件

4、變量）第七張，PPT共五十六頁，創(chuàng)作于2022年6月3、變量約束條件變量m個(gè)約束條件m個(gè)變量0約束條件 0變量 0 約束條件 0變量無約束約束條件=0 4、目標(biāo)函數(shù)中變量的系數(shù)C為對(duì)偶問題中約束條件的右端常數(shù)項(xiàng)b，個(gè)數(shù)對(duì)等變動(dòng)。第八張，PPT共五十六頁，創(chuàng)作于2022年6月記憶要點(diǎn)：1、把握“三要素”，目標(biāo)函數(shù)、約束條件變量、C-b的轉(zhuǎn)化。2、把握重點(diǎn)變量與約束條件的關(guān)系。（1）約束條件=0的情況，變量無約束。（2）在約束條件0時(shí)候，看原問題目標(biāo)函數(shù)。1）max：約束條件變量，反向；變量約束條件，正向。（反正）2）min：約束條件變量，正向；變量約束條件，反向。（正反）第九張，PPT共五十六頁

5、，創(chuàng)作于2022年6月記憶寶典：1、MaxMin2、C b3、無約束等于0，個(gè)數(shù)m變n。4、max就反正，min就正反。（約束條件變量）第十張，PPT共五十六頁，創(chuàng)作于2022年6月示例：轉(zhuǎn)化為對(duì)偶問題第十一張，PPT共五十六頁，創(chuàng)作于2022年6月第一種做法：按照定義來第十二張，PPT共五十六頁，創(chuàng)作于2022年6月其中 第三個(gè)條件用兩個(gè)式子替代。第十三張，PPT共五十六頁，創(chuàng)作于2022年6月第十四張，PPT共五十六頁，創(chuàng)作于2022年6月第十五張，PPT共五十六頁，創(chuàng)作于2022年6月第十六張，PPT共五十六頁，創(chuàng)作于2022年6月用所學(xué)原則寫一次？第十七張，PPT共五十六頁，創(chuàng)作于20

6、22年6月示例2：寫出下列問題的對(duì)偶問題：minz=7x1+4x2-3x3S.T-4x1+2x2-6x3 24-3x1-6x2-4x3 15 5x2+3x3=30其中，x1 0，x2無約束，x3 0第十八張，PPT共五十六頁，創(chuàng)作于2022年6月Maxz=24y1+15y2+30y3S.T-4y1-3y2 72y1-6y2+5y3 =4-6y1-4y2+3y3 -3y1 0，y2 0，y3取值無約束第十九張，PPT共五十六頁，創(chuàng)作于2022年6月三、對(duì)偶問題的性質(zhì)（一）對(duì)稱性。對(duì)偶問題的對(duì)偶問題是原問題。（類似于“負(fù)負(fù)得正”）Minw=300y1+400y2+250y3S.T y1+2y2 5

7、0 y1 + y2+y3 100其中y1，y2，y3均0其對(duì)偶問題是？第二十張，PPT共五十六頁，創(chuàng)作于2022年6月Max z=50 x1 +100 x2x1 +x2 3002x1+x2 400 x2 250 x1，x20第二十一張，PPT共五十六頁，創(chuàng)作于2022年6月（二）若原問題為（弱對(duì)偶性定理）maxZ=CXAX bX 0其對(duì)偶問題為Minw=YbYA CY 0 若X為原問題任一可行解，Y為對(duì)偶問題任一可行解，則必有CX Yb第二十二張，PPT共五十六頁，創(chuàng)作于2022年6月弱對(duì)偶性定理的意義：原問題任一個(gè)可行解是對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的一個(gè)下界。反過來說：對(duì)偶問題的任一個(gè)可行解是原

8、問題目標(biāo)函數(shù)值的一個(gè)上界。理解：（1）很多個(gè)界。（2）看目標(biāo)函數(shù)的類型判斷。第二十三張，PPT共五十六頁，創(chuàng)作于2022年6月（三）若原問題為（無界性定理）maxZ=CXAX bX 0其對(duì)偶問題為Minw=YbYA CY 0 若原問題有可行解，則目標(biāo)函數(shù)為無界解的充要條件是對(duì)偶問題無可行解。第二十四張，PPT共五十六頁，創(chuàng)作于2022年6月（四）若X和Y分別為原問題和對(duì)偶問題的可行解，當(dāng)CX=Yb（目標(biāo)函數(shù)值相同）時(shí)，則X和Y分別為原問題和對(duì)偶問題的最優(yōu)解。（最優(yōu)性定理）一般情況下是：CXYb，當(dāng)取=時(shí)，Yb最小，CX最大。第二十五張，PPT共五十六頁，創(chuàng)作于2022年6月（五）若原問題和對(duì)偶

9、問題具有可行解，若原問題或?qū)ε紗栴}之一有最優(yōu)解，則另一個(gè)對(duì)偶問題也必有最優(yōu)解，且最優(yōu)值相同。（主對(duì)偶性定理）證明含義：若原問題有一個(gè)對(duì)應(yīng)于基B的最優(yōu)解，則CBB-1為對(duì)偶問題的最優(yōu)解。第二十六張，PPT共五十六頁，創(chuàng)作于2022年6月（六）若X，Y為原問題和對(duì)偶問題的的可行解，則X，Y為最優(yōu)解的充要條件是V*X=0，Y*U=0，其中V是對(duì)偶問題的剩余變量，U是原問題的松弛變量。（互補(bǔ)松弛性定理）第二十七張，PPT共五十六頁，創(chuàng)作于2022年6月（七）原問題在單純性法迭代過程中的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問題的一個(gè)基本解。（對(duì)應(yīng)性定理）原問題 XB XN XS 對(duì)應(yīng)基B檢驗(yàn)數(shù) 0 CN-CBB-1BN C

10、BB-1對(duì)偶問題的變量 -YS1 -YS2 -Y第二十八張，PPT共五十六頁，創(chuàng)作于2022年6月原問題：maxZ =12x1+8x2+5x33x1 +2x2+x3 20 x1 +x2 +x3 1112x1+4x2+x3 5x1，x2，x30標(biāo)準(zhǔn)化：maxZ =12x1+8x2+5x33x1 +2x2+x3 +x4 =20 x1 +x2 +x3 +x5 =1112x1+4x2+x3 +x6 =5x1，x2，x3，x4，x5 ，x6 0第二十九張，PPT共五十六頁，創(chuàng)作于2022年6月Minw=20y1+11y2+5y33y1+y2+12y3 122y1+4y2+y3 8y1+y2+y3 5y1

11、，y2，y30Maxf=-20y1-11y2-5y33y1+y2+12y3 y4 =122y1+4y2+y3 -y5 =8y1+y2+y3 -y6 =5y1，y2，y3，y4，y5，y60第三十張，PPT共五十六頁，創(chuàng)作于2022年6月原問題的松弛變量（XS）=對(duì)偶問題的變量原問題的變量=對(duì)偶問題的剩余變量（YS）第三十一張，PPT共五十六頁，創(chuàng)作于2022年6月X（1）=（0,0,0,20,11,48）Y（1）=（0,0,0，-12，-8，-5）X（2）=（4,0,0,8,7,0）Y（2）=（0,0,1，0，-4，-4）X（3）=（4/3,8,0,0,5/3,0）Y（3）=（4,0,0，0，

12、0，-1）X（4）=（2,5,4,0,0,0）Y（4）=（12/5,12/5,1/5，0，0，0）第三十二張，PPT共五十六頁，創(chuàng)作于2022年6月對(duì)偶問題性質(zhì)的啟示原問題 對(duì)偶問題有最優(yōu)解 有最優(yōu)解無可行解 無可行解有可行解無上界 無有限最優(yōu)解無有限最優(yōu)解 有可行解但無下界第三十三張，PPT共五十六頁，創(chuàng)作于2022年6月四、對(duì)偶問題經(jīng)濟(jì)學(xué)含義影子價(jià)格因?yàn)閆*=Y*=Yb所以：Z/ b=Yb資源的量Z目標(biāo)函數(shù)經(jīng)濟(jì)學(xué)含義：資源每變動(dòng)一個(gè)單位，目標(biāo)函數(shù)（利潤、總產(chǎn)值等）變動(dòng)的大小。資源對(duì)生產(chǎn)做出的貢獻(xiàn)。（影子價(jià)格）是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益的一個(gè)評(píng)價(jià)，叫機(jī)會(huì)成本。第三十四張，PPT共五十六頁，創(chuàng)作

13、于2022年6月五、對(duì)偶單純形法思路：?jiǎn)渭冃苑ǖ慕忸}思路：從可行域的一個(gè)頂點(diǎn)（基本可行解）通過迭代（初等行變換）換到另一個(gè)頂點(diǎn)（基本可行解），保持頂點(diǎn)的最優(yōu)性不變（每一個(gè)頂點(diǎn)所取得的目標(biāo)函數(shù)值處于增加（max）或者減少（min）的情況，直到取得最優(yōu)解（目標(biāo)函數(shù)值不可能繼續(xù)增大（減少）=所有變量的檢驗(yàn)數(shù)全部0。第三十五張，PPT共五十六頁，創(chuàng)作于2022年6月按照對(duì)偶問題的性質(zhì)7來說，當(dāng)原問題獲得一個(gè)基本可行解（頂點(diǎn)）時(shí)，對(duì)偶問題獲得一個(gè)基本解。當(dāng)對(duì)偶問題獲得基本解，同時(shí)也為可行解時(shí)，原問題的檢驗(yàn)數(shù)全部0，即原問題獲得最優(yōu)解。第三十六張，PPT共五十六頁，創(chuàng)作于2022年6月作業(yè)題中原問題 與對(duì)

14、偶問題解之間的關(guān)系。x1 x2 x3 x4 x5 x6 y1 y2 y3 y4 y5 y60 0 0 20 11 48 0 0 0 0 0 04 0 0 8 7 0 0 -4 -4 0 0 14/3 8 0 0 5/3 0 0 0 -1 4 0 02 5 4 0 0 0 0 0 0 12/5 12/5 1/5從頂點(diǎn)1迭代到頂點(diǎn)4，對(duì)偶問題一直是基本解，當(dāng)為基本可行解的時(shí)候，原問題和對(duì)偶問題共同取得最優(yōu)解。第三十七張，PPT共五十六頁，創(chuàng)作于2022年6月對(duì)偶單純性法的思想：根據(jù)原問題對(duì)偶問題的特性（主對(duì)偶定理、最優(yōu)性定理、對(duì)應(yīng)性定理），用單純性法求解線性規(guī)劃問題（單純性法的一種）。解題思路：每

15、次迭代中，保持對(duì)偶問題的解是可行解，不管原問題的基本解是否為基本可行解，當(dāng)原問題取得基本可行解時(shí)，則這個(gè)解是原問題的最優(yōu)解。第三十八張，PPT共五十六頁，創(chuàng)作于2022年6月二、例題例:用對(duì)偶單純性法求解線性規(guī)劃問題。Minw=12y1+16y2+15y32y1+4y2 22y1 +5y33y1，y2，y30在不用對(duì)偶單純性法之前，用什么方法，請(qǐng)寫出初始單純性表？第三十九張，PPT共五十六頁，創(chuàng)作于2022年6月用“大M”法，或者二階段法。（必須用“人工變量法”）MaxZ=-12y1-16y2-15y3+0y4+0y5-My6-My72y1+4y2 -y4 +y5 =22y1 +5y3 -y6

16、 +y7 =3y1，y2，y3，y4，y5，y6，y70第四十張，PPT共五十六頁，創(chuàng)作于2022年6月用對(duì)偶單純性解題：第一步：化成“標(biāo)準(zhǔn)型”Maxz=-12y1-16y2-15y3+0y4+0y5-2y1-4y2 +y4 = -2-2y1 -5y3 +y5 = -3y1,y2,y3,y4,y50bi0添加的人工變量不一樣。第四十一張，PPT共五十六頁，創(chuàng)作于2022年6月初始對(duì)偶單純性表ci -12 -16 -15 0 0CB B b y1 y2 y3 y4 y50 y4 -2 -2 -4 0 1 0 0 y5 -3 -2 0 -5 0 1 -12 -16 -15 0 0確定出基變量：bk

17、=minbi, bi0=min-2，-3=-3;確定進(jìn)基變量：=min/akj,akj0=-15/-5從而確定主元素akr，以此為中心做初等行變換。第四十二張，PPT共五十六頁，創(chuàng)作于2022年6月對(duì)偶單純性表2ci -12 -16 -15 0 0CB B b y1 y2 y3 y4 y50 y4 -2 -2 -4 0 1 0 -15 y3 3/5 2/5 0 1 0 -1/5 -6 -16 0 0 -3確定出基變量：bk=minbi , bi0=min-15=-15;確定進(jìn)基變量：=min/akj,akj0，此時(shí)，原問題取得基本可行解，即目標(biāo)函數(shù)值達(dá)到最優(yōu)。第四十四張，PPT共五十六頁，創(chuàng)作

18、于2022年6月對(duì)偶單純性法和一般單純性法的區(qū)別：相同點(diǎn)：解題步驟一樣建立初始單純性表判斷是否最優(yōu)選定進(jìn)出基變量初等行變換（迭代）單純性表最優(yōu)。不同點(diǎn)：思路不同，步驟不同。一般單純性法：原問題保持基本可行解不變，直到對(duì)偶問題由基本解取得基本可行解。第四十五張，PPT共五十六頁，創(chuàng)作于2022年6月對(duì)偶單純性法的要點(diǎn)1、單純性法的一種（利用原問題對(duì)偶問題的性質(zhì)求解），并不是求解原問題的對(duì)偶問題的單純性法。（針對(duì)的還是原問題）2、適用的范圍（適用條件很苛刻）：（1）原問題約束條件有0；（2）目標(biāo)函數(shù)價(jià)值系數(shù)max函數(shù)，且Ci0（原問題的對(duì)偶問題是基本可行解）。不必引入人工變量，簡(jiǎn)化計(jì)算。第四十六張

19、，PPT共五十六頁，創(chuàng)作于2022年6月對(duì)偶單純性法：保持對(duì)偶問題為基本可行解，直到原問題由基本解變成基本可行解。解題思路正好相反。2、具體解題步驟（1）判斷最優(yōu)性的標(biāo)準(zhǔn)一般單純性法：當(dāng)前表中所有變量的檢驗(yàn)數(shù)（主要指非基變量）0。相當(dāng)于對(duì)偶問題取得基本可行解。對(duì)偶單純性法：當(dāng)前表中所有bi0。相當(dāng)于原問題取得基本可行解。第四十七張，PPT共五十六頁，創(chuàng)作于2022年6月（2）確定主元素（進(jìn)出基變量）1）次序不一樣。一般單純性法：先確定進(jìn)基變量再確定出基變量。（先進(jìn)后出先縱向后橫向）對(duì)偶單純性法：先確定出基變量再確定進(jìn)基變量。（先出后進(jìn)先橫向后縱向）2）確定進(jìn)基變量一般單純性法： max(j0)=k，確定xk為進(jìn)基變量。（首先進(jìn)行橫向?qū)Ρ龋?duì)偶單純性法： min/akj,akj0= ，確定ajk為出基變量。（第二步進(jìn)行縱向?qū)Ρ龋?duì)偶單純性法： min bj0）；4、進(jìn)出基最小化原則；第五十張，PPT共五十六頁，創(chuàng)作于2022年6月練習(xí)：P 125頁minf=x1+2x2+3x2x1-x2+x34x1+x2+2x38 x2-x32X1，x2，