運籌學對偶問題

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

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

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

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

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

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

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

計算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→當前54頁，總共61頁。計算θ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--當前55頁，總共61頁。繼續(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

→當前56頁，總共61頁。繼續(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

→當前57頁，總共61頁。繼續(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