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

運(yùn)籌學(xué)對(duì)偶問(wèn)題演示文稿目前一頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)運(yùn)籌學(xué)對(duì)偶問(wèn)題目前二頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)一、對(duì)偶問(wèn)題的一般形式若設(shè)一線性規(guī)劃問(wèn)題如下：（A）目前三頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)則以下線性規(guī)劃問(wèn)題：（B）

稱為原問(wèn)題（A）的對(duì)偶線性規(guī)劃問(wèn)題，或稱A、B互為對(duì)偶問(wèn)題。目前四頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)如果采用向量、矩陣來(lái)表示（A）（B）其中：目前五頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)可以將以上關(guān)系列成以下對(duì)偶表：maxminx1x2…xnby1a11a12…a1n≤b1y2a21a22…≤b2…………………ymam1am2…amn≤bm≥≥…≥cc1c2…cn目前六頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題目前七頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)解：可以將原問(wèn)題的有關(guān)參數(shù)列成下表maxminx1x2x3by1142≤48y2124≤60≥≥≥c61413目前八頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)∴對(duì)偶規(guī)劃問(wèn)題為目前九頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)比較以上我們介紹的對(duì)偶問(wèn)題是嚴(yán)格定義的對(duì)偶問(wèn)題，也成為對(duì)稱對(duì)偶問(wèn)題。它滿足兩個(gè)條件：目前十頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)兩個(gè)條件：1、所有變量非負(fù)：即X>0，Y>02、約束條件均為同向不等式。若原問(wèn)題約束條件均為“≤”，則它的對(duì)偶問(wèn)題的約束條件都是“≥”。當(dāng)原問(wèn)題的約束條件的符號(hào)不完全相同時(shí)，也存在對(duì)偶問(wèn)題，這種對(duì)偶問(wèn)題稱為非對(duì)稱對(duì)偶問(wèn)題。目前十一頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例分析：為求對(duì)偶問(wèn)題，可先做過(guò)渡，將問(wèn)題對(duì)稱化：目前十二頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)對(duì)稱化目前十三頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)

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

則得到以下對(duì)偶問(wèn)題（B‘）（B）目前十八頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)合并（B）目前十九頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)比較對(duì)于任何一個(gè)線性規(guī)劃問(wèn)題，我們都可以求出它的對(duì)偶問(wèn)題。（A）（B）目前二十頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)原問(wèn)題與對(duì)偶問(wèn)題的相應(yīng)關(guān)系原問(wèn)題A（對(duì)偶問(wèn)題B）對(duì)偶問(wèn)題B（原問(wèn)題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è)約束條件為不等式“≤”目前二十一頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例：寫出下列問(wèn)題的對(duì)偶形式：目前二十二頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)解：目前二十三頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例：寫出下列問(wèn)題的對(duì)偶問(wèn)題目前二十四頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)解：目前二十五頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)二、對(duì)偶問(wèn)題的經(jīng)濟(jì)意義：若原規(guī)劃問(wèn)題是“在一定條件下，使工作或成果（產(chǎn)品產(chǎn)量、利潤(rùn)等）盡可能的大”，那么它的對(duì)偶問(wèn)題就是“在另外一些條件下，使工作的消耗（浪費(fèi)、成本等）盡可能的小”。實(shí)際上是一個(gè)問(wèn)題的兩個(gè)方面。目前二十六頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例：某產(chǎn)品計(jì)劃問(wèn)題的

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

目前三十五頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)定理3（最優(yōu)性定理）設(shè)和分別是問(wèn)題A和B的可行解，若相應(yīng)于和，A和B的目標(biāo)函數(shù)值相等，即，則和分別是A和B的最優(yōu)解。

目前三十六頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)定理4（無(wú)界性定理）如果原問(wèn)題A的目標(biāo)函數(shù)值無(wú)界，則對(duì)偶問(wèn)題B無(wú)可行解；如果對(duì)偶問(wèn)題B的目標(biāo)函數(shù)值無(wú)界，則原問(wèn)題A無(wú)可行解。目前三十七頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)以上三個(gè)定理可以這樣記憶原問(wèn)題A和對(duì)偶問(wèn)題B如果有可行解，則它們的可行解區(qū)域只可能相接，不可能相交。兩個(gè)區(qū)域的交界線即是它們的最優(yōu)解，如果原問(wèn)題A的目標(biāo)函數(shù)無(wú)界，意味著可行解區(qū)域無(wú)界，向外擴(kuò)張，擠占了對(duì)偶問(wèn)題B的可行解區(qū)域，則對(duì)偶問(wèn)題無(wú)可行解，反之同理可說(shuō)明。對(duì)偶問(wèn)題(B)minW原問(wèn)題(A)maxZy0bcx0目前三十八頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)定理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)值相等。目前三十九頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)定理6（存在性定理）若線性規(guī)劃A和B都存在可行解，則A和B都存在最優(yōu)解。目前四十頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)第三節(jié)對(duì)偶單純形法條件：①b列中至少有一個(gè)bi<0；②原問(wèn)題A的檢驗(yàn)數(shù)滿足符號(hào)條件。目前四十一頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)例目前四十二頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)解：minmax解：引入松弛變量，化為標(biāo)準(zhǔn)形式：目前四十三頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)觀察A矩陣目前四十四頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)解以上標(biāo)準(zhǔn)形式中沒(méi)有完全單位向量組，我們將約束條件進(jìn)行變換，兩邊同乘（-1）。A矩陣中存在完全單位向量組，但bi<0，考慮求解。用單純形法求解。目前四十五頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)步驟1判斷對(duì)偶單純形法的條件是否滿足。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→目前四十六頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)步驟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→目前四十七頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)步驟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→目前四十八頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)（2）計(jì)算θj：找出主元行Pj*中所有負(fù)分量，計(jì)算注：若主元行中沒(méi)有負(fù)分量，則問(wèn)題無(wú)解。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--目前四十九頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)（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--目前五十頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)（4）找主元素主元行與主元列相交處的元素即主元素，記為Pi*j*。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--目前五十一頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)（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→目前五十二頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)計(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→目前五十三頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)找主元行、確定調(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→目前五十四頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)計(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--目前五十五頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)繼續(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

→目前五十六頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)繼續(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

→目前五十七頁(yè)\總數(shù)六十一頁(yè)\編于五點(diǎn)繼續(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)