運(yùn)籌學(xué)對(duì)偶問題

運(yùn)籌學(xué)對(duì)偶問題演示文稿當(dāng)前1頁(yè)，總共61頁(yè)。運(yùn)籌學(xué)對(duì)偶問題當(dāng)前2頁(yè)，總共61頁(yè)。一、對(duì)偶問題的一般形式若設(shè)一線性規(guī)劃問題如下：（A）當(dāng)前3頁(yè)，總共61頁(yè)。則以下線性規(guī)劃問題：（B）

稱為原問題（A）的對(duì)偶線性規(guī)劃問題，或稱A、B互為對(duì)偶問題。當(dāng)前4頁(yè)，總共61頁(yè)。如果采用向量、矩陣來表示（A）（B）其中：當(dāng)前5頁(yè)，總共61頁(yè)?？梢詫⒁陨详P(guān)系列成以下對(duì)偶表：maxminx1x2…xnby1a11a12…a1n≤b1y2a21a22…≤b2…………………ymam1am2…amn≤bm≥≥…≥cc1c2…cn當(dāng)前6頁(yè)，總共61頁(yè)。例寫出下列線性規(guī)劃問題的對(duì)偶問題當(dāng)前7頁(yè)，總共61頁(yè)。解：可以將原問題的有關(guān)參數(shù)列成下表maxminx1x2x3by1142≤48y2124≤60≥≥≥c61413當(dāng)前8頁(yè)，總共61頁(yè)?！鄬?duì)偶規(guī)劃問題為當(dāng)前9頁(yè)，總共61頁(yè)。比較以上我們介紹的對(duì)偶問題是嚴(yán)格定義的對(duì)偶問題，也成為對(duì)稱對(duì)偶問題。它滿足兩個(gè)條件：當(dāng)前10頁(yè)，總共61頁(yè)。兩個(gè)條件：1、所有變量非負(fù)：即X>0，Y>02、約束條件均為同向不等式。若原問題約束條件均為“≤”，則它的對(duì)偶問題的約束條件都是“≥”。當(dāng)原問題的約束條件的符號(hào)不完全相同時(shí)，也存在對(duì)偶問題，這種對(duì)偶問題稱為非對(duì)稱對(duì)偶問題。當(dāng)前11頁(yè)，總共61頁(yè)。例分析：為求對(duì)偶問題，可先做過渡，將問題對(duì)稱化：當(dāng)前12頁(yè)，總共61頁(yè)。對(duì)稱化當(dāng)前13頁(yè)，總共61頁(yè)。

則，原問題變?yōu)椋ˋ）（A‘）當(dāng)前14頁(yè)，總共61頁(yè)。則（A’）的對(duì)偶問題如下：（B‘）（A‘）當(dāng)前15頁(yè)，總共61頁(yè)。對(duì)比結(jié)果以上對(duì)偶問題（B‘）并非原問題（A）的對(duì)偶問題，它是線性規(guī)劃問題（A’）的對(duì)偶問題。（A）（B‘）當(dāng)前16頁(yè)，總共61頁(yè)。調(diào)整對(duì)照問題B‘目標(biāo)函數(shù)系數(shù)的符號(hào)與原問題A中約束條件右端常數(shù)項(xiàng)的符號(hào)，可做以下調(diào)整：令y1=y1’，y2=-y2’，y3=y4’-y3’當(dāng)前17頁(yè)，總共61頁(yè)。令y1=y1’，y2=-y2’，y3=y4’-y3’

則得到以下對(duì)偶問題（B‘）（B）當(dāng)前18頁(yè)，總共61頁(yè)。合并（B）當(dāng)前19頁(yè)，總共61頁(yè)。比較對(duì)于任何一個(gè)線性規(guī)劃問題，我們都可以求出它的對(duì)偶問題。（A）（B）當(dāng)前20頁(yè)，總共61頁(yè)。原問題與對(duì)偶問題的相應(yīng)關(guān)系原問題A（對(duì)偶問題B）對(duì)偶問題B（原問題A）最大化max最小化minA系數(shù)矩陣ATB右端常數(shù)（列向量）目標(biāo)函數(shù)系數(shù)(行向量)C目標(biāo)函數(shù)系數(shù)右端常數(shù)（列向量）第i個(gè)約束條件為等式“=”yi為自由變量第i個(gè)約束條件為不等式“≤”yi≥0第i個(gè)約束條件為不等式“≥”yi≤0xj為自由變量第j個(gè)約束條件為等式“=”xj≥0第j個(gè)約束條件為不等式“≥”xj≤0第j個(gè)約束條件為不等式“≤”當(dāng)前21頁(yè)，總共61頁(yè)。例：寫出下列問題的對(duì)偶形式：當(dāng)前22頁(yè)，總共61頁(yè)。解：當(dāng)前23頁(yè)，總共61頁(yè)。例：寫出下列問題的對(duì)偶問題當(dāng)前24頁(yè)，總共61頁(yè)。解：當(dāng)前25頁(yè)，總共61頁(yè)。二、對(duì)偶問題的經(jīng)濟(jì)意義：若原規(guī)劃問題是“在一定條件下，使工作或成果（產(chǎn)品產(chǎn)量、利潤(rùn)等）盡可能的大”，那么它的對(duì)偶問題就是“在另外一些條件下，使工作的消耗（浪費(fèi)、成本等）盡可能的小”。實(shí)際上是一個(gè)問題的兩個(gè)方面。當(dāng)前26頁(yè)，總共61頁(yè)。例：某產(chǎn)品計(jì)劃問題的

線性規(guī)劃數(shù)學(xué)模型為假設(shè)生產(chǎn)部門根據(jù)市場(chǎng)變化，決定停止生產(chǎn)甲、乙產(chǎn)品，而將原有的原料、設(shè)備專用于接受外來訂貨以生產(chǎn)市場(chǎng)急需的緊俏商品，則需要考慮決策的問題就是“在什么樣的價(jià)格條件下，才能接受外來訂貨？”。問題的實(shí)質(zhì)就是如何確定原料、設(shè)備的收費(fèi)標(biāo)準(zhǔn)？當(dāng)前27頁(yè)，總共61頁(yè)。分析若設(shè)y1為單位原材料的價(jià)格，y2為設(shè)備單位臺(tái)時(shí)價(jià)格，由于用了3個(gè)單位原料和5個(gè)單位設(shè)備臺(tái)時(shí)就可以生產(chǎn)一個(gè)單位甲產(chǎn)品而獲利2個(gè)單位，現(xiàn)在不生產(chǎn)甲產(chǎn)品，轉(zhuǎn)而接受外來訂貨加工，則收取的費(fèi)用不能低于2個(gè)單位，否則自己生產(chǎn)甲產(chǎn)品更有利。因此，可以得到下面的條件：當(dāng)前28頁(yè)，總共61頁(yè)。分析同理，將生產(chǎn)乙產(chǎn)品的原料和設(shè)備工時(shí)用于接受外來加工訂貨，收取的費(fèi)用不能低于乙產(chǎn)品的單位利潤(rùn)1個(gè)單位：當(dāng)前29頁(yè)，總共61頁(yè)。分析另外，為了爭(zhēng)取外來加工訂貨，在滿足上述要求的基礎(chǔ)上，收費(fèi)標(biāo)準(zhǔn)應(yīng)盡可能低從而具有競(jìng)爭(zhēng)力，因此總的收費(fèi)w=15y1+10y2應(yīng)極小化。這樣，就得到一個(gè)目標(biāo)函數(shù)：當(dāng)前30頁(yè)，總共61頁(yè)。這樣，就得到另一個(gè)線性規(guī)劃模型：當(dāng)前31頁(yè)，總共61頁(yè)。比較生產(chǎn)問題（要利用資源）資源利用問題（會(huì)影響生產(chǎn)）當(dāng)前32頁(yè)，總共61頁(yè)。第二節(jié)對(duì)偶理論當(dāng)前33頁(yè)，總共61頁(yè)。定理1（對(duì)稱性定理）對(duì)偶問題（B）的對(duì)偶規(guī)劃為線性規(guī)劃（A）對(duì)稱性定理是很重要的。它表明原規(guī)劃問題（A）和對(duì)偶規(guī)劃問題（B）是互為對(duì)偶的。也就是說，如果（B）是（A）的對(duì)偶，那么（A）也是（B）的對(duì)偶。這就為以后的討論帶來方便。不難理解，如果當(dāng)A具有某種性質(zhì)時(shí)可以推出B的某些性質(zhì)，于是可以無需另加證明地得到：當(dāng)B具有某種性質(zhì)時(shí)，問題A也具有那些性質(zhì)。當(dāng)前34頁(yè)，總共61頁(yè)。定理2（弱對(duì)偶定理）當(dāng)原問題A是求最大值max，而對(duì)偶問題是求最小值時(shí)，如果X0是原問題的任意可行解，Y0是對(duì)偶問題的任意可行解，則有以下關(guān)系式成立：

當(dāng)前35頁(yè)，總共61頁(yè)。定理3（最優(yōu)性定理）設(shè)和分別是問題A和B的可行解，若相應(yīng)于和，A和B的目標(biāo)函數(shù)值相等，即，則和分別是A和B的最優(yōu)解。

當(dāng)前36頁(yè)，總共61頁(yè)。定理4（無界性定理）如果原問題A的目標(biāo)函數(shù)值無界，則對(duì)偶問題B無可行解；如果對(duì)偶問題B的目標(biāo)函數(shù)值無界，則原問題A無可行解。當(dāng)前37頁(yè)，總共61頁(yè)。以上三個(gè)定理可以這樣記憶原問題A和對(duì)偶問題B如果有可行解，則它們的可行解區(qū)域只可能相接，不可能相交。兩個(gè)區(qū)域的交界線即是它們的最優(yōu)解，如果原問題A的目標(biāo)函數(shù)無界，意味著可行解區(qū)域無界，向外擴(kuò)張，擠占了對(duì)偶問題B的可行解區(qū)域，則對(duì)偶問題無可行解，反之同理可說明。對(duì)偶問題(B)minW原問題(A)maxZy0bcx0當(dāng)前38頁(yè)，總共61頁(yè)。定理5（強(qiáng)對(duì)偶定理）若線性規(guī)劃A存在最優(yōu)解，則對(duì)偶規(guī)劃B也存在最優(yōu)解，并且它們的最優(yōu)值相等；相反地，若規(guī)劃B存在最優(yōu)解，則規(guī)劃A也存在最優(yōu)解，并且它們的最優(yōu)值相等。當(dāng)前39頁(yè)，總共61頁(yè)。定理6（存在性定理）若線性規(guī)劃A和B都存在可行解，則A和B都存在最優(yōu)解。當(dāng)前40頁(yè)，總共61頁(yè)。第三節(jié)對(duì)偶單純形法條件：①b列中至少有一個(gè)bi<0；②原問題A的檢驗(yàn)數(shù)滿足符號(hào)條件。當(dāng)前41頁(yè)，總共61頁(yè)。例當(dāng)前42頁(yè)，總共61頁(yè)。解：minmax解：引入松弛變量，化為標(biāo)準(zhǔn)形式：當(dāng)前43頁(yè)，總共61頁(yè)。觀察A矩陣當(dāng)前44頁(yè)，總共61頁(yè)。解以上標(biāo)準(zhǔn)形式中沒有完全單位向量組，我們將約束條件進(jìn)行變換，兩邊同乘（-1）。A矩陣中存在完全單位向量組，但bi<0，考慮求解。用單純形法求解。當(dāng)前45頁(yè)，總共61頁(yè)。步驟1判斷對(duì)偶單純形法的條件是否滿足。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→當(dāng)前46頁(yè)，總共61頁(yè)。步驟2在對(duì)偶單純形表中，檢驗(yàn)數(shù)是b列。當(dāng)b>0時(shí)，得到最優(yōu)解。否則，進(jìn)行換基迭代段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→當(dāng)前47頁(yè)，總共61頁(yè)。步驟3：換基迭代（1）找主元行：找到b列中絕對(duì)值最大者所在行為主元行，記為Pi*，主元行對(duì)應(yīng)的變量Xi*為調(diào)出變量。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→當(dāng)前48頁(yè)，總共61頁(yè)。（2）計(jì)算θj：找出主元行Pj*中所有負(fù)分量，計(jì)算注：若主元行中沒有負(fù)分量，則問題無解。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--當(dāng)前49頁(yè)，總共61頁(yè)。（3）找主元列θj中絕對(duì)值最小者所在的列為主元列，記為Pj*，主元列所對(duì)應(yīng)的變量xj*為調(diào)入變量。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--當(dāng)前50頁(yè)，總共61頁(yè)。（4）找主元素主元行與主元列相交處的元素即主元素，記為Pi*j*。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--當(dāng)前51頁(yè)，總共61頁(yè)。（5）迭代用高斯消去法，使原主元列中除了原主元素為1外，其余元素均為0。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x110x60Cj-Zj→θj→當(dāng)前52頁(yè)，總共61頁(yè)。計(jì)算結(jié)果段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→θj→當(dāng)前53頁(yè)，總共61頁(yè)。找主元行、確定調(diào)出變量、

計(jì)算zj-cj段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→-140300θj→--1-2--3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→---2-1-2--θj→當(dāng)前54頁(yè)，總共61頁(yè)。計(jì)算θj、確定調(diào)入變量段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→-0-2-1-210θj→-2/31/22/3--當(dāng)前55頁(yè)，總共61頁(yè)。繼續(xù)換基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3(-2)-321→Cj-Zj→-0-2-1-2-10θj

→--2/31/22/3--3-1x100x31Cj-Zj→θj

→當(dāng)前56頁(yè)，總共61頁(yè)。繼續(xù)換基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj

→-12-3--2-1x1312-11-100x6-80-3(-2)-321→Cj-Zj→-0-2-1-2-10θj

→--2/31/22/3--3-1x1717/205/2-2-1/20x3403/213/2-1-1/2Cj-Zj→θj

→當(dāng)前57頁(yè)，總共61頁(yè)。繼續(xù)換基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj

→-12-3--2-1x1312-11-100x6-80-3(-2)-321→Cj