物流運(yùn)籌學(xué) 課件 第3章 對(duì)偶理論x

第3章線性規(guī)劃對(duì)偶理論及其應(yīng)用例1

穗羊公司的例子3.1線性規(guī)劃的對(duì)偶問題生產(chǎn)計(jì)劃問題（LP1）III每周可使用量A（千克）125B（噸）214C（百工時(shí)）439單位產(chǎn)品利潤(rùn)（萬元）32III每周可使用量A（千克）125B（噸）214C（百工時(shí)）439單位產(chǎn)品利潤(rùn)（萬元）32穗羊公司如果要出讓其擁有的資源:單價(jià)y1,y2,y3y1y2y3生產(chǎn)每件產(chǎn)品的資源出讓后獲得的收益應(yīng)該不低于該件產(chǎn)品的收益.產(chǎn)品I:產(chǎn)品II:接手其所有資源的廠家期望出價(jià)越低越好:資源定價(jià)問題（LP2）比較原問題（生產(chǎn)計(jì)劃）對(duì)偶問題（資源定價(jià)）3.1.2規(guī)范形式的線性規(guī)劃問題原問題（LP）對(duì)偶問題（DLP）

規(guī)范形式最大化問題:約束條件全為型決策變量全部非負(fù)最小化問題:約束條件全為型決策變量全部非負(fù)規(guī)范形式的對(duì)偶關(guān)系原問題對(duì)偶問題目標(biāo)函數(shù):maxCX目標(biāo)函數(shù):minb′Ym個(gè)約束條件:AXbm個(gè)決策變量:Y0n個(gè)決策變量:X0n個(gè)約束條件:A′YC′原問題對(duì)偶問題非規(guī)范形式的對(duì)偶關(guān)系對(duì)非規(guī)范形式的對(duì)偶關(guān)系，只需對(duì)上述表進(jìn)行相應(yīng)修改即可：例如對(duì)于一個(gè)最小化問題，若某個(gè)決策變量yi

0,則其對(duì)偶的約束條件為型的;若其某個(gè)約束條件是型,則其對(duì)應(yīng)的對(duì)偶變量是非正的.3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問題1變量取值范圍不符合非負(fù)要求的情況3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問題2約束方程不是“≤”的情況

3.1.4總結(jié)約束條件對(duì)變量，變量對(duì)約束條件；正常對(duì)正常，不正常對(duì)不正常；變量正常是非負(fù)，約束條件正?？茨繕?biāo)(max≤，min≥)。

例2.5求解下面線性規(guī)劃的對(duì)偶規(guī)劃LPDLP3.2對(duì)偶規(guī)劃的基本性質(zhì)3.2.1對(duì)稱性定理：線性規(guī)劃的對(duì)偶問題的對(duì)偶問題是原問題。證明：

對(duì)偶定義令w’=-w；約束方程左右同乘“-1”對(duì)偶定義令z=-z’；約束方程左右同乘“-1”3.2對(duì)偶規(guī)劃的基本性質(zhì)3.2.2弱對(duì)偶性定理：如果X、Y分別是原問題和對(duì)偶問題的一個(gè)可行解，則其對(duì)應(yīng)的原問題的目標(biāo)函數(shù)值不大于對(duì)偶問題的目標(biāo)函數(shù)值，也即證明：因?yàn)閄、Y分別是原問題（3.1）與對(duì)偶問題（3.2）的可行解，故：

所以推論一：原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。推論二：如果原問題存在無界解，則對(duì)偶問題一定無可行解；反之，如果對(duì)偶問題存在無界解，原問題也一定不存在可行解。3.2.3最優(yōu)性定理也就是說若原問題與對(duì)偶問題各存在一個(gè)可行解,且它們對(duì)應(yīng)的目標(biāo)函數(shù)值相等,則它們分別是原問題與對(duì)偶問題最優(yōu)解.如果原問題存在最優(yōu)解X*，則其對(duì)偶問題一定具有最優(yōu)解Y*，且初始單純形表的矩陣表示CBCN0CSxBxNxS0BNISbCBCN00最優(yōu)單純形表的矩陣表示CBCN0CBxBxNxSCBIB－1NB-1B-1b0CN-CBB－1N-CBB－1CBB－1b令則Y*>=0,且故Y*即為對(duì)偶問題的最優(yōu)解。又因?yàn)?.2.4強(qiáng)對(duì)偶性定理（對(duì)偶定理）B-1B-1B-1B-1在初始單純形表中單位矩陣經(jīng)過迭代后變?yōu)榛仃嘊的逆在初始單純形表給出的解中基變量Xs=b,而在迭代后的表給出的解中基變量

XB=B-1b系數(shù)矩陣的變化:[A,I]B-1[A,I]在初始單純形表中變量xj的系數(shù)為Pj經(jīng)過迭代后變?yōu)镻j′,并且Pj′=B-1Pj若迭代后的單純形表為最終表則該表也同時(shí)給出對(duì)偶問題的最優(yōu)解

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

32000

CBXBx1x2x3x4x5b0x3

1210050x4

2101040x5430019

320000例3.1的初始表與最終表B?B-1例3.1的原問題與對(duì)偶問題最終單純形表的比較

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

54900

y1y2y3y4y5

4y2-5/210-3/221/29y33/2011/2-11/2

3/2003/2113/2

原問題對(duì)偶問題對(duì)于最大化問題,其最終表的檢驗(yàn)數(shù)的相反數(shù)是對(duì)偶問題最優(yōu)解對(duì)于最小化問題,其最終表的檢驗(yàn)數(shù)是對(duì)偶問題最優(yōu)解原問題LP（生產(chǎn)計(jì)劃）對(duì)偶問題DLP（資源定價(jià)）3.2.5互補(bǔ)松弛定理原問題對(duì)偶問題變量xi或yi

0分為兩種情況yi>0，變量比較松；yi=0，變量比較緊；約束條件

分為兩種情況

，約束條件比較松；

，約束條件比較緊；變量同其對(duì)偶問題的約束方程之間，至多只能夠有一個(gè)取松弛的情況；當(dāng)其中一個(gè)取松弛的情況時(shí)，另外一個(gè)比較緊，即取嚴(yán)格等號(hào)?；パa(bǔ)松弛定理例3.6已知下面的LP1和LP2為一組對(duì)偶規(guī)劃，且已知LP1的最優(yōu)解為X=（1.5，1）’。試運(yùn)用互補(bǔ)松弛定理求出對(duì)偶問題的最優(yōu)解Y。原問題（LP1）對(duì)偶問題（LP2）解：由X=（1.5，1）’得聯(lián)立求解得：

說明資源增加1個(gè)單位，企業(yè)總利潤(rùn)可以增加單位。所以如果資源的市場(chǎng)價(jià)格低于，就要買進(jìn)。3.3影子價(jià)格和靈敏度分析3.3.1影子價(jià)格 對(duì)偶變量的經(jīng)濟(jì)含義就是資源的定價(jià)，然而這種價(jià)格同市場(chǎng)價(jià)格不同，我們稱之為影子價(jià)格。它反映了資源對(duì)于企業(yè)的緊缺程度、利潤(rùn)貢獻(xiàn)程度等，并不能反映資源的生產(chǎn)成本，以及在外部市場(chǎng)的緊缺程度。1、影子價(jià)格是邊際利潤(rùn)根據(jù)互補(bǔ)松弛定理：如果某種資源有剩余，則增加資源不會(huì)增加利潤(rùn)，影子價(jià)格為0；如果某種資源影子價(jià)格大于0，則一定沒有剩余。如果新產(chǎn)品對(duì)m種資源的單位消耗量分別為則其機(jī)會(huì)成本為如果其利潤(rùn)大于機(jī)會(huì)成本就生產(chǎn)，否則不生產(chǎn)。2、影子價(jià)格是機(jī)會(huì)成本第i種資源減少1個(gè)單位，企業(yè)的利潤(rùn)減少yi。如果其他企業(yè)要購(gòu)買該種資源，給出的而價(jià)格高于yi

，就要考慮賣出。如果該產(chǎn)品機(jī)會(huì)成本大于利潤(rùn)，則該產(chǎn)品不生產(chǎn)。對(duì)于原有產(chǎn)品，如果生產(chǎn)的，則其機(jī)會(huì)成本等于利潤(rùn)。

對(duì)偶單純形法按對(duì)偶問題與原問題之間的關(guān)系，對(duì)最大化問題，在用單純形法求解原問題時(shí)，最終表不但給出了原問題的最優(yōu)解，而且其檢驗(yàn)數(shù)的相反數(shù)就是對(duì)偶問題的最優(yōu)解。單純形法求解的基本思路基可行解檢驗(yàn)數(shù)非正保持解的可行性對(duì)偶單純形法的基本思路對(duì)偶問題基可行解（檢驗(yàn)數(shù)非正）原問題基可行解保持對(duì)偶問題解的可行性（檢驗(yàn)數(shù)非正（對(duì)偶問題可行解）對(duì)偶單純形法計(jì)算步驟適用于求解這樣的LP問題：標(biāo)準(zhǔn)化后不含初始基變量，但將某些約束條件兩端乘以“-1”后，即可找出初始基變量。要求：初始單純形表中的檢驗(yàn)數(shù)滿足最優(yōu)性條件對(duì)滿足上述條件的LP問題，對(duì)偶單純形法的步驟是：旋轉(zhuǎn)運(yùn)算。然后回到第2步。作出初始單純形表（注意要求）檢查b列的數(shù)據(jù)是否非負(fù)，若是，表中已經(jīng)給出最優(yōu)解；否則轉(zhuǎn)下一步確定換出變量：取b列最小的數(shù)對(duì)應(yīng)的變量為換出變量確定換入變量：用檢驗(yàn)數(shù)去除以換出變量行的那些對(duì)應(yīng)的負(fù)系數(shù)，在除得的商中選取其中最小者對(duì)應(yīng)的變量為換入變量例用對(duì)偶單純形法求解如下的LP問題化成標(biāo)準(zhǔn)形式將各約束條件兩端同乘“-1”得用對(duì)偶單純形法求解得最優(yōu)解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最優(yōu)目標(biāo)函數(shù)值：w*=-8.5（z*=8.5）注：通常很少直接使用對(duì)偶單純形法求解線性規(guī)劃問題。選擇b列的最小(負(fù))元素對(duì)應(yīng)基變量為換出變量用檢驗(yàn)數(shù)除以換出變量行的負(fù)的元素,取所得的最小商對(duì)應(yīng)的變量為換入變量最優(yōu)解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最優(yōu)目標(biāo)函數(shù)值：w*=-8.5（z*=8.5）注：通常很少直接使用對(duì)偶單純形法求解線性規(guī)劃問題。選擇b列的最小(負(fù))元素對(duì)應(yīng)基變量為換出變量用檢驗(yàn)數(shù)除以換出變量行的負(fù)的元素,取所得的最小商對(duì)應(yīng)的變量為換入變量

甲公司的生產(chǎn)情況3.5靈敏度分析1、目標(biāo)函數(shù)系數(shù)cj變化例3.7C由(3.2)變?yōu)?3,1)，請(qǐng)問最優(yōu)生產(chǎn)計(jì)劃如何變化？解：由原最優(yōu)單純形表得：基變量31000bCBxBx1x2x3x4x50x30015/2-3/23/23x11003/2-1/23/21x2010-2[1]1000-5/21/211/2

單純形迭代得：基變量31000bCBxBx1x2x3x4x50x303/21-1/2033x111/201/2020x5010-2110-1/20-3/2-3/26

所以得到新的最優(yōu)生產(chǎn)計(jì)劃為產(chǎn)品I生產(chǎn)2件，產(chǎn)品II不生產(chǎn)，此時(shí)總利潤(rùn)為6萬元。例3.8假設(shè)產(chǎn)品II的價(jià)格不變，請(qǐng)問產(chǎn)品I的價(jià)格在什么范圍內(nèi)波動(dòng)時(shí)，最優(yōu)生產(chǎn)計(jì)劃不變？欲使最優(yōu)生產(chǎn)計(jì)劃不變，須

2000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/2x1

1003/2-1/23/22x2010-211

000也即時(shí)，最優(yōu)生產(chǎn)計(jì)劃不變。解：假設(shè)c1由3變?yōu)椋瑒t2、約束條件右端向量b的變化例3.9穗羊公司倉(cāng)庫(kù)盤點(diǎn)時(shí)發(fā)現(xiàn)，資源B的每周可使用量可以增加到5噸，請(qǐng)制定新的最優(yōu)生產(chǎn)計(jì)劃。解：因?yàn)?，所以需要進(jìn)行對(duì)偶單純形迭代。由原最優(yōu)單純形表得：基變量32000bCBxBx1x2x3x4x50x30015/2-3/24（1）3x11003/2-1/23（2）2x2010[-2]1-1（3）000-1/2-1/27

（4）因?yàn)閤2=-1<0，所以令其岀基。拿檢驗(yàn)數(shù)所在行除以出基變量所在行的負(fù)數(shù)，商最小的列對(duì)應(yīng)的元素作為主元素。這里正數(shù)和零不能作為主元素。本題中第三行只有a34=-2<0，所以選擇a34作為主元素，進(jìn)行對(duì)偶迭代。迭代的目標(biāo)：右端向量劃為非負(fù)把基變量所在列劃成單位矩陣基變量檢驗(yàn)數(shù)化為零?；兞?2000bCBxBx1x2x3x4x50x305/410-1/411/4（1）+5*（3）/43x113/4001/49/4（2）+3*（3）/40x40-1/201-1/21/2（3）*（-1/2）0-1/400-1/427/4

（4）-（3）/4迭代后得：3、增加一種新產(chǎn)品例3.10穗羊公司研發(fā)部門開發(fā)了一種新產(chǎn)品III，單位產(chǎn)品對(duì)A、B、C三種資源的消耗系數(shù)為（3,0,2）/，該產(chǎn)品單位利潤(rùn)為2萬元。問產(chǎn)品III是否應(yīng)該生產(chǎn)？如果生產(chǎn)，各產(chǎn)品生產(chǎn)量是多少？解：產(chǎn)品III機(jī)會(huì)成本

該產(chǎn)品的檢驗(yàn)數(shù)，所以應(yīng)該生產(chǎn)。將上述數(shù)據(jù)代入原最優(yōu)單純形表得下表：基變量320002bCBxBx1x2x3x4x5x60x30015/2-3/203/23x11003/2-1/2-13/22x2010-21[2]1000-1/2-1/2113/2

0x30015/2-3/203/23x11001/20022x601/20-11/211/20-1/20-11/4-107所以，新的最優(yōu)生產(chǎn)計(jì)劃是產(chǎn)品I和產(chǎn)品III分別生產(chǎn)2件和1/2件，產(chǎn)品II不生產(chǎn)，總利潤(rùn)為7萬元。4、增加一個(gè)新的約束條件例3.11：穗羊公司生產(chǎn)部門發(fā)現(xiàn)生產(chǎn)除了受到A、B、C三種資源的約束外，還要受到資源D的約束。資源D周可用量為6，生產(chǎn)單位產(chǎn)品I、II對(duì)資源D的消耗分別為7/2和2。請(qǐng)制定新的最優(yōu)生產(chǎn)計(jì)劃。解：根據(jù)題意，需要在原問題后面增加新約束將原最優(yōu)生產(chǎn)計(jì)劃X=（3/2，1）’代入該約束方程得：不滿足新約束條件。將約束方程添加松弛條件得：將此約束方程代入原最優(yōu)單純形表得下表：基變量310000bCBxBx1x2x3x5x5x60x30015/2-3/203/2（1）3x11003/2-1/203/2（2）1x2010-2101（3）0x67/2200016（4）000-1/2-1/2011/2

將a41、a42化為0得下表：基變量310000bCBxBx1x2x3x5x5x60x30015/2-3/203/2（1）3x11003/2-1/203/2（2）1x2010-2101（3）0x6000[-5/4]-1/41-5/4（4）000-1/2-1/2011/2對(duì)偶單純形迭代得下表：基變量310000bCBxBx1x2x3x5x5x60x30010[-2]2-13x11000-4/56/501x201007/5-8/530x400011/5-4/510000-2/5-2/550x500-1/201-11/23x110-2/5002/52/51x2017/1000-1/523/100x4001/1010-3/59/1000-1/500-4/524/5所以新的最優(yōu)生產(chǎn)計(jì)劃是產(chǎn)品I和產(chǎn)品II分別生產(chǎn)2/5件和23/10件，總利潤(rùn)為24/5萬元。

5、約束條件系數(shù)aij的變化例3.12：穗羊公司經(jīng)過技術(shù)革新，將生產(chǎn)產(chǎn)品I對(duì)資源C的單位消耗量從4變?yōu)?，即P1=（1,2,4）’變?yōu)镻1=（1,2,2）’。請(qǐng)求出新的最優(yōu)生產(chǎn)計(jì)劃。解：令將插入原最優(yōu)單純形表格得：基變量-99731000bCBxBx1x1’x2x3x4x50x30[3]015/2-3/23/2-997x112003/2-1/23/22x20-210-21102001002999/2-1001/22987/23