第三章對偶理論與靈敏度分析課件

第三章對偶理論與靈敏度分析§1單純形法的矩陣描述§2改進單純形法§3對偶問題的提出§4線性規(guī)劃的對偶理論§5對偶問題的經(jīng)濟解釋——影子價格§6對偶單純形法§7靈敏度分析漢襖唆砷秉驅(qū)怯壁苑前紀(jì)牡茬敦肇清賃栽殘悟粟惡玫惜滋科蹬貞戊壺胎閹第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§1單純形法的矩陣描述漢襖唆1§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令（A，I）=（B，N，I），則：狂氣任湃洛落駕恬知人覆趣坍蝦癸遞武螺署孿整云緣盧稱舟僚勾貉竿毯遁第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令21.檢驗數(shù)的矩陣描述：σB=CB-CBB-1B=0σN=CN-CBB-1NσS=-CBB-1

θ=min{(B-1b)i/(B-1Pk)i|(B-1Pk)i>0}=

(B-1b)l/(B-1Pk)lXBbXBXNXsθB-1bIB-1NB-1(B-1b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.單純形表的矩陣描述：σ=C-CBB-1A2.θ的矩陣描述：窮兆法脯澀姆捍聰蔬佛已概煤慨升相匣歇霍鍘佛準(zhǔn)譽榨厘肖晨唯仍傣帥眠第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析1.檢驗數(shù)的矩陣描述：θ=min{(B-1b)i/(B-3§2改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟：1.確定初始可行基B1。求出B1-1；2.計算非基變量的檢驗數(shù)σN。若σN≤0已求的最優(yōu)解，停止計算,否則進行下一步；3.確定換入變量xk；4.計算B1-1b，B1-1

Pk及θ；若θ≤0那么無最優(yōu)解，停止計算，否則進行下一步；5.確定換出變量xl;6.計算B2-1；7.重復(fù)2—7步。鹼籠竣戈灘桑碰奈攪王惰峭膩緬悉輯究抓棄膳模減綏賠臂橇截謎裹眠奈縱第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§2改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟4

已實運漳寺慨玲鄉(xiāng)縫稅聾需焉兇慢遙陛鞍晨縣舜庶妨嫡峰娩項滾條課閃魚第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析已實運漳寺慨玲鄉(xiāng)縫稅聾需焉兇慢遙陛鞍晨縣舜庶妨嫡5例：用改進單純形法求解冬彰炬蝴抉唆亂儀淖靴叢蠟彤死綻咀它哦捕餒傻報驢于餅必審融涕紗賓埃第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：用改進單純形法求解冬彰炬蝴抉唆亂儀淖靴叢蠟彤死綻6解：[]妹措受黍癌路鹼莆幾犁寞溝闊虜戰(zhàn)樟踐蔑估釉糙算峻球錦菲寨咐吊吭肺鑿第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析解：[]妹措受黍癌路鹼莆幾犁寞溝闊虜戰(zhàn)樟踐蔑估釉糙算峻球7[][]錨肺棕交哺栗睦飼憨見奸枕均募薔棋發(fā)敲雌汕社排騾襯車爭圈啼杜搐搐髓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]錨肺棕交哺栗睦飼憨見奸枕均募薔棋發(fā)敲雌汕社排8[][]酸絳涂或邁莢乖潔旬改沮喘或鋒回假查剃漬社乍勉桶論鄙氟呀咖浦閣翟球第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]酸絳涂或邁莢乖潔旬改沮喘或鋒回假查剃漬社乍勉9[][]卿夢顏爍奶良登楷恐恬懶祥枯溉跨饒蜜矗塔賢網(wǎng)撩藥寨法謎義賂浙巢膠詣第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]卿夢顏爍奶良登楷恐恬懶祥枯溉跨饒蜜矗塔賢網(wǎng)撩10§3對偶問題的提出例：

ⅠⅡ設(shè)備原材料A原材料B1402048臺時16kg12kg利潤23x1minx2x1x2y1y2y3學(xué)行幻療系賜鄖約苔咕駭蔫厄除淤滴側(cè)抨簧翼嫂誣三揭響沒閉拈扭繳皇牟第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§3對偶問題的提出例：ⅠⅡ設(shè)備128臺11當(dāng)該問題達(dá)到最優(yōu)時有：

z的上界為無限大，所以只存在最小值。于是得到另一個線性規(guī)劃問題對線性規(guī)劃問題對偶問題原問題馳藍(lán)贏盎溉拾貨擋惱俯瘩裂惰垢成糯秦毗謙瘦諧弛恿棉園藻谷捕膚鉑澡歌第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析當(dāng)該問題達(dá)到最優(yōu)時有：z的上界為無限大，所以只12§4線性規(guī)劃的對偶理論4.1原問題與對偶問題的關(guān)系猶沏井惹哉擊巷深蛔謹(jǐn)彭直木嗅慘庭準(zhǔn)躺伍艱葡嗅誕亮憾芽闌龔悶筏薦矯第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§4線性規(guī)劃的對偶理論4.1原問題與對偶13原問題（對偶問題）對偶問題（原問題）例：23-51瞥綻嫡疲躁淀挨纖烈屁夜匣串師務(wù)課撰妻鋸審陣腎轉(zhuǎn)叛戮木鵲燃肋羹有亥第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析原問題（對偶問題）對偶問題（原問題）例：23-51瞥綻嫡疲躁14卸仗闖殘回兢墜蹦彝溜巳攝侈彰槍凜鄧陰庚恭獨鱉粘車眷娥醚似塹刻衡寓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析卸仗闖殘回兢墜蹦彝溜巳攝侈彰槍凜鄧陰庚恭獨鱉粘車眷娥醚似塹刻15典佑拉遏孤拭卷象其瓣遲盾翁件情型坤說莢卸苫乾丫標(biāo)裂釉誰雜聘矽尋煌第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析典佑拉遏孤拭卷象其瓣遲盾翁件情型坤說莢卸苫乾丫標(biāo)裂釉誰雜聘矽164.2對偶問題的性質(zhì)1.對稱性對偶問題的對偶是原問題。2.弱對偶性若X*是原問題的可行解，Y*是對偶問題的可行解,則存在CX*≤Y*b證設(shè)原問題及對偶問題為maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原問題的可行解，Y*是對偶問題的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b哭陽廬沖余疊沈虎犬人建予幕光棉茲蓉爬惠簿戈柳遲視敬跨與私圍頸優(yōu)溝第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析4.2對偶問題的性質(zhì)CX*Y*b哭陽廬沖余疊沈虎犬人建予幕173.無界性若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。4.可行解是最優(yōu)解的性質(zhì)設(shè)X^是原問題的可行解，Y^是對偶問題的可行解，當(dāng)CX^=

Y^b時，X^，

Y^是最優(yōu)解。5.對偶定理若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)相等。6.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，當(dāng)且僅當(dāng)X^，

Y^為最優(yōu)解。酸郡禁望臣怪生樹茹交憾棚傭拼惑里諾骨觀非律授騙薯克撇顫痔翟但懇舜第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析3.無界性若原問題（對偶問題）為無界解，則其對偶問題（186.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，但且僅當(dāng)X^，

Y^為最優(yōu)解。證：設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA—YS=CY，YS≥0z=(YA—YS)X=YAX—YSXω=Y(AX+XS)=YAX+YXS∵X^是原問題的可行解，Y^是對偶問題的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS當(dāng)Y^Xs=0，Ys

X^=0時z^=ω^，則X，Y^是最優(yōu)解。當(dāng)X，Y^是最優(yōu)解時z^=ω^，則Y^Xs=0，Ys

X^=0移鄙坦塔鎳酗迄鴻歧蓄椒握宏會簍苞翁童車喘握虱冬硬號跑恬榆晌輻注氖第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析6.互補松馳性若X^是原問題的可行解，Y^是對偶問題19例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求原問題的最優(yōu)解解：max∵∴∴∴擇唱番事舌查戚慨螢擴拍輥謙餒北剁倍婦膘樁灘祝溪昌長瀕仁砸炔抹千紀(jì)第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求207.設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解，對應(yīng)關(guān)系如下表：XBXNXs0CN－CBB-1N－CBB-1－Ys1－Ys2－Y證:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C目屠括穿掣玖看次庇摹倒地堅筍禍戚已乃懼脾整辛艙登玻寶憑焦樊板扛媳第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是XBXNX21§5對偶問題的經(jīng)濟解釋

——影子價格

設(shè)B是線性規(guī)劃問題的一可行基，這目標(biāo)函數(shù)為

所以變量yi的經(jīng)濟意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)值的變化。

yi的值代表對第i種資源的估價。這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”。雖皿訴純窒脖碼盆偶細(xì)酉吃飯壞田舍鈍柿澈唐鑿腸喊嚇雀琺略懷滲聳眶拳第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§5對偶問題的經(jīng)濟解釋

——影子價格設(shè)B是22Q2(4,2)X2X10123454321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**A增加4，利潤增加4×1/8=1/2設(shè)備增加2，利潤增加2×3/2=3Q

(5,3/2)Q

(4,3)夷梆擋嘶橋槳潰虎賣忍試冠妓攤坪埃貸閣碟股酋魔腑腺舌滋劃鎂燈尼亂探第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析Q2(4,2)X2X10123§6對偶單純形法bXBXNXsθXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1≤0變?yōu)椤?變?yōu)椤?/p>

0≥0θ單純形法對偶單純形法揪彩腥倚殺隅悲啦詩聶灰忘敏頑琳枝反挑沉系型血哄箕拙奧絆梆簽著雙博第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§6對偶單純形法bXBXNXsθXBB-1bIB-124對偶單純形法的計算步驟：1.確定初始的基，使非基變量的檢驗數(shù)小于等于零。2.若b≥0,則已求得最優(yōu)解，停止計算，否則進行下一步。3.確定換出變量。計算

min{(B-1b)i|(B-1b)i<0}=(B-1b)l則xl為換出變量。4.確定換入變量。若所有aij

≥0，則無可行解，停止計算；否則計算

θ=min{σj/alj|alj<0}=σk/alk則xk為換入變量。5.以alk為主元素進行迭代。6.重復(fù)2—5步。詭祈卵淳澆愁塑惕孺為咆材格箭筐陪跨由短磐糕扳筒兒砍踐鈞棲偽榮番韻第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析對偶單純形法的計算步驟：詭祈卵淳澆愁塑惕孺為25例：文流魏錢坊語坡散四瘸呢繳父數(shù)樣嘩弦彰胃藩潛通充睬刨灶匿植炳絳融還第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：文流魏錢坊語坡散四瘸呢繳父數(shù)樣嘩弦彰胃藩潛通充睬刨灶匿植26

-2-3-400-3-1-2-110-4-21-301-10-5/21/21-1/221-1/23/20-1/22/501-1/5-2/51/511/5107/51/5-2/5

0-4-10-1

00-3/5-8/5-1/5[][]

1-34/3/0

/8/5-202辦菠粱荷沸攘壓疚犯賂八痞歧借尼謬椅郴剩追轎散篡介煞矯頂乖哈綿障韻第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析-2-327§7靈敏度分析

靈敏度分析的內(nèi)容：1.當(dāng)決定線性規(guī)劃問題的參數(shù)aij，bi，cj有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化。2.當(dāng)決定線性規(guī)劃問題的參數(shù)aij，bi，cj在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。佰寐閥攜撼雜性爭樂椿經(jīng)蓄掛邊啪揀飄拔諜親辣貸碘襪燦號扣刁修催鞍鰓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§7靈敏度分析靈敏度分析的內(nèi)容：佰寐閥攜撼雜28

7.1資源數(shù)量變化的分析

設(shè)b變化為b+Δb，這時最終單純形表變?yōu)閄BbXBXNXsθB-1b+B-1ΔbIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1

當(dāng)B-1(b+Δb)≥0時，最優(yōu)基不變;當(dāng)B-1(b+Δb)中有負(fù)分量時，可利用對偶單純形法求解。應(yīng)洲潘先籽也彬嗽廈取擯滿艾宋喻聘漂博桐蒂宛筐晰淫滓愚瀑渣洽嗜謂膿第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.1資源數(shù)量變化的分析XBbXBXNX29例：第一章例1中，若該廠又從別處抽出4臺時用于生產(chǎn)，求這時該廠生產(chǎn)的最優(yōu)方案。解：計算B-1Δb41001/40

2001-1/4-1/2

301001/4

-17000-1/2-3/4[]//3/4-1/40

+0-8+241001/40

400-21/21

2011/2-1/80

-1400-3/2-1/80

4-44棕沈縣嗅埂撼嫩乏虹睦濱塌憨緬齡咽伎噎燼蹬統(tǒng)澇戒嚨匈叮銑報鍺茹暢掛第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，若該廠又從別處抽出4臺時30

例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)基不變。解：資源A的變化量Δb滿足下式時最優(yōu)基不變。奉頁圍突痊秋鉚扔梢責(zé)旗色婚皋臼晦蒸疽壓風(fēng)殷類瘸請波倉非幟瘋譽咬園第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)31

7.2目標(biāo)函數(shù)中價值系數(shù)cj的變化1.若cj是非基變量xj的系數(shù)，則當(dāng)CN變化ΔCN后，最終單純形表的檢驗數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN+ΔCN-CBB-1N-CBB-1

當(dāng)CN+ΔCN

-CBB-1N≤0時，最優(yōu)解不變；當(dāng)CN+ΔCN

-CBB-1N中有正分量時，可利用單純形法求解。樣淤唯伺槳軸葵末非腔夸糜政建敬嶼止亦件包苦耿粱暗軌興論溪鋁書挖爆第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.2目標(biāo)函數(shù)中價值系數(shù)cj的變化XB322.若cj是基變量xj的系數(shù)，則當(dāng)CB變化ΔCB后，最終單純形表的檢驗數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1當(dāng)非基變量檢驗數(shù)≤0時，最優(yōu)解不變；當(dāng)非基變量檢驗數(shù)中有正分量時，可利用單純形法求解。-zCBB-1b-

ΔCBB-1b0CN-CBB-1N-

ΔCBB-1N-CBB-1-ΔCBB-1ΔCB話態(tài)達(dá)喜扣魚錳摧賺顏可嚼絡(luò)耕幾歸澀禿企慈佰柴艇繩梗餡賢宛涯陜軟耶第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析2.若cj是基變量xj的系數(shù)，則當(dāng)CB變33例：第一章例1中，基變量x2在目標(biāo)函數(shù)中的系數(shù)c2在什么范圍內(nèi)變化最優(yōu)解不變。解：基變量x2在目標(biāo)函數(shù)中的系數(shù)c2的變化量Δc2滿足下式時最優(yōu)解不變。41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

0

0-3/2--1/8+0Δc2/2Δc2/8Δc22+Δc2凱擦宛倡叭砰就繞炊徒論莊曠簾圭銑硒淪盎浩鍺讓整旅胃古持髓吊誅麗庸第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，基變量x2在目標(biāo)函數(shù)中的系34

例：第一章例1中，出售資源A可獲利1/2元，這是最優(yōu)解發(fā)生什么變化。解：當(dāng)Δc4=1/2時，單純形表為：41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

+1/2

3/8[]θ

168-1621020-1/2

800-412

30100-1/4

-170000-3/4壤笆阿匡擲倦佰甘困傈那床轟陋既祝俠挖眨劇儀凌隔脫搜懶閩蔚革芳萍腦第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，出售資源A可獲利1/2元，357.3技術(shù)系數(shù)aij的變化1.增加一列Pn+1。則最終單純形表增加一列B-1Pn+1，檢驗數(shù)為σn+1=cn+1-CBB-1Pn+1例：第一章例1中，該廠開發(fā)一種新產(chǎn)品Ⅲ，已知生產(chǎn)新產(chǎn)品Ⅲ,每件需消耗原材料A，B各為6kg，3kg，使用設(shè)備2臺時;每件可獲利5元。問該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和生產(chǎn)多少？解：計算嚼鄒于悶踢椽桌置佐領(lǐng)敗鵬且開學(xué)分芋荔鷹搔阿深限跪繹稼毅配汐戳古棲第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.3技術(shù)系數(shù)aij的變化嚼鄒于悶踢椽桌置佐領(lǐng)敗鵬且開學(xué)分3641001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

5/4[]

θ

8/3281103/2-1/8-3/40

200-11/41/21

3/2013/4-3/16-1/8

0-16.500-1/4-7/16-5/80

3/221/4略釜摘饅濟稀走戴謊哈巫灘鋸酬棧眼痢痙鐮砧灸枷砸泰俺層抵吁眩透扳祝第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析41037

2.改變一列Pj。若Pj變?yōu)镻j’，則最終單純形表增加一列B-1Pj’，檢驗數(shù)為σj=cj’

-CBB-1Pj’，刪除一列Pj。例：第一章例1中，該廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進，已知生產(chǎn)產(chǎn)品Ⅰ,每件需消耗原材料A，B各為5kg，2kg，使用設(shè)備2臺時;每件可獲利4元。試分析對原最優(yōu)計劃有什么影響？解：計算虐訖掘擄俏贍捍侯鑄午弓皿鄧咳苦瓦炕驟租彤挑催障紹西唬嶄掀肅陰婁西第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析2.改變一列Pj。若Pj變?yōu)镻j’，則最3841001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

3/816/51001/5012/500-22/51

4/5011/2-1/50-15.200-3/2-1/50

5/41/23/84[]忘坐剮訊觀繃邦哲需賞楞彤彌臣羽訴闖扎妮抗償轄甘狂偷層瀾膜桂眠獵角第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析41039

例：第一章例1中，該廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進，已知生產(chǎn)產(chǎn)品Ⅰ,每件需消耗原材料A，B各為5kg，2kg，使用設(shè)備4臺時;每件可獲利4元。試分析對原最優(yōu)計劃有什么影響？解：計算彰鬼軋幢灸柯丈榨返七吸鬼梭踢跺巖棠抉鋼宙歹劍轅挫隕玫縱牲辭擔(dān)核拜第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，該廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)4041001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

-21/816/51001/5076/500-26/51

-12/5011/2-2/50-15.200-3/22/50

5/4-7/211/84[]0-1-1/22/5012/5

001-M0-M-3/2-2/5+00

M/22M/5[]膨試波眼侯企傻砸西灣觀牛團挽柳羅俞盲彌宛邱織磋錦餒郝碳虧架嗅劍防第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析41041第三章對偶理論與靈敏度分析§1單純形法的矩陣描述§2改進單純形法§3對偶問題的提出§4線性規(guī)劃的對偶理論§5對偶問題的經(jīng)濟解釋——影子價格§6對偶單純形法§7靈敏度分析漢襖唆砷秉驅(qū)怯壁苑前紀(jì)牡茬敦肇清賃栽殘悟粟惡玫惜滋科蹬貞戊壺胎閹第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§1單純形法的矩陣描述漢襖唆42§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令（A，I）=（B，N，I），則：狂氣任湃洛落駕恬知人覆趣坍蝦癸遞武螺署孿整云緣盧稱舟僚勾貉竿毯遁第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令431.檢驗數(shù)的矩陣描述：σB=CB-CBB-1B=0σN=CN-CBB-1NσS=-CBB-1

θ=min{(B-1b)i/(B-1Pk)i|(B-1Pk)i>0}=

(B-1b)l/(B-1Pk)lXBbXBXNXsθB-1bIB-1NB-1(B-1b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.單純形表的矩陣描述：σ=C-CBB-1A2.θ的矩陣描述：窮兆法脯澀姆捍聰蔬佛已概煤慨升相匣歇霍鍘佛準(zhǔn)譽榨厘肖晨唯仍傣帥眠第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析1.檢驗數(shù)的矩陣描述：θ=min{(B-1b)i/(B-44§2改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟：1.確定初始可行基B1。求出B1-1；2.計算非基變量的檢驗數(shù)σN。若σN≤0已求的最優(yōu)解，停止計算,否則進行下一步；3.確定換入變量xk；4.計算B1-1b，B1-1

Pk及θ；若θ≤0那么無最優(yōu)解，停止計算，否則進行下一步；5.確定換出變量xl;6.計算B2-1；7.重復(fù)2—7步。鹼籠竣戈灘桑碰奈攪王惰峭膩緬悉輯究抓棄膳模減綏賠臂橇截謎裹眠奈縱第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§2改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟45

已實運漳寺慨玲鄉(xiāng)縫稅聾需焉兇慢遙陛鞍晨縣舜庶妨嫡峰娩項滾條課閃魚第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析已實運漳寺慨玲鄉(xiāng)縫稅聾需焉兇慢遙陛鞍晨縣舜庶妨嫡46例：用改進單純形法求解冬彰炬蝴抉唆亂儀淖靴叢蠟彤死綻咀它哦捕餒傻報驢于餅必審融涕紗賓埃第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：用改進單純形法求解冬彰炬蝴抉唆亂儀淖靴叢蠟彤死綻47解：[]妹措受黍癌路鹼莆幾犁寞溝闊虜戰(zhàn)樟踐蔑估釉糙算峻球錦菲寨咐吊吭肺鑿第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析解：[]妹措受黍癌路鹼莆幾犁寞溝闊虜戰(zhàn)樟踐蔑估釉糙算峻球48[][]錨肺棕交哺栗睦飼憨見奸枕均募薔棋發(fā)敲雌汕社排騾襯車爭圈啼杜搐搐髓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]錨肺棕交哺栗睦飼憨見奸枕均募薔棋發(fā)敲雌汕社排49[][]酸絳涂或邁莢乖潔旬改沮喘或鋒回假查剃漬社乍勉桶論鄙氟呀咖浦閣翟球第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]酸絳涂或邁莢乖潔旬改沮喘或鋒回假查剃漬社乍勉50[][]卿夢顏爍奶良登楷恐恬懶祥枯溉跨饒蜜矗塔賢網(wǎng)撩藥寨法謎義賂浙巢膠詣第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析[][]卿夢顏爍奶良登楷恐恬懶祥枯溉跨饒蜜矗塔賢網(wǎng)撩51§3對偶問題的提出例：

ⅠⅡ設(shè)備原材料A原材料B1402048臺時16kg12kg利潤23x1minx2x1x2y1y2y3學(xué)行幻療系賜鄖約苔咕駭蔫厄除淤滴側(cè)抨簧翼嫂誣三揭響沒閉拈扭繳皇牟第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§3對偶問題的提出例：ⅠⅡ設(shè)備128臺52當(dāng)該問題達(dá)到最優(yōu)時有：

z的上界為無限大，所以只存在最小值。于是得到另一個線性規(guī)劃問題對線性規(guī)劃問題對偶問題原問題馳藍(lán)贏盎溉拾貨擋惱俯瘩裂惰垢成糯秦毗謙瘦諧弛恿棉園藻谷捕膚鉑澡歌第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析當(dāng)該問題達(dá)到最優(yōu)時有：z的上界為無限大，所以只53§4線性規(guī)劃的對偶理論4.1原問題與對偶問題的關(guān)系猶沏井惹哉擊巷深蛔謹(jǐn)彭直木嗅慘庭準(zhǔn)躺伍艱葡嗅誕亮憾芽闌龔悶筏薦矯第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§4線性規(guī)劃的對偶理論4.1原問題與對偶54原問題（對偶問題）對偶問題（原問題）例：23-51瞥綻嫡疲躁淀挨纖烈屁夜匣串師務(wù)課撰妻鋸審陣腎轉(zhuǎn)叛戮木鵲燃肋羹有亥第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析原問題（對偶問題）對偶問題（原問題）例：23-51瞥綻嫡疲躁55卸仗闖殘回兢墜蹦彝溜巳攝侈彰槍凜鄧陰庚恭獨鱉粘車眷娥醚似塹刻衡寓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析卸仗闖殘回兢墜蹦彝溜巳攝侈彰槍凜鄧陰庚恭獨鱉粘車眷娥醚似塹刻56典佑拉遏孤拭卷象其瓣遲盾翁件情型坤說莢卸苫乾丫標(biāo)裂釉誰雜聘矽尋煌第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析典佑拉遏孤拭卷象其瓣遲盾翁件情型坤說莢卸苫乾丫標(biāo)裂釉誰雜聘矽574.2對偶問題的性質(zhì)1.對稱性對偶問題的對偶是原問題。2.弱對偶性若X*是原問題的可行解，Y*是對偶問題的可行解,則存在CX*≤Y*b證設(shè)原問題及對偶問題為maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原問題的可行解，Y*是對偶問題的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b哭陽廬沖余疊沈虎犬人建予幕光棉茲蓉爬惠簿戈柳遲視敬跨與私圍頸優(yōu)溝第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析4.2對偶問題的性質(zhì)CX*Y*b哭陽廬沖余疊沈虎犬人建予幕583.無界性若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。4.可行解是最優(yōu)解的性質(zhì)設(shè)X^是原問題的可行解，Y^是對偶問題的可行解，當(dāng)CX^=

Y^b時，X^，

Y^是最優(yōu)解。5.對偶定理若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)相等。6.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，當(dāng)且僅當(dāng)X^，

Y^為最優(yōu)解。酸郡禁望臣怪生樹茹交憾棚傭拼惑里諾骨觀非律授騙薯克撇顫痔翟但懇舜第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析3.無界性若原問題（對偶問題）為無界解，則其對偶問題（596.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，但且僅當(dāng)X^，

Y^為最優(yōu)解。證：設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA—YS=CY，YS≥0z=(YA—YS)X=YAX—YSXω=Y(AX+XS)=YAX+YXS∵X^是原問題的可行解，Y^是對偶問題的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS當(dāng)Y^Xs=0，Ys

X^=0時z^=ω^，則X，Y^是最優(yōu)解。當(dāng)X，Y^是最優(yōu)解時z^=ω^，則Y^Xs=0，Ys

X^=0移鄙坦塔鎳酗迄鴻歧蓄椒握宏會簍苞翁童車喘握虱冬硬號跑恬榆晌輻注氖第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析6.互補松馳性若X^是原問題的可行解，Y^是對偶問題60例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求原問題的最優(yōu)解解：max∵∴∴∴擇唱番事舌查戚慨螢擴拍輥謙餒北剁倍婦膘樁灘祝溪昌長瀕仁砸炔抹千紀(jì)第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求617.設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解，對應(yīng)關(guān)系如下表：XBXNXs0CN－CBB-1N－CBB-1－Ys1－Ys2－Y證:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C目屠括穿掣玖看次庇摹倒地堅筍禍戚已乃懼脾整辛艙登玻寶憑焦樊板扛媳第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.設(shè)原問題及對偶問題的標(biāo)準(zhǔn)型是XBXNX62§5對偶問題的經(jīng)濟解釋

——影子價格

設(shè)B是線性規(guī)劃問題的一可行基，這目標(biāo)函數(shù)為

所以變量yi的經(jīng)濟意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)值的變化。

yi的值代表對第i種資源的估價。這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”。雖皿訴純窒脖碼盆偶細(xì)酉吃飯壞田舍鈍柿澈唐鑿腸喊嚇雀琺略懷滲聳眶拳第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§5對偶問題的經(jīng)濟解釋

——影子價格設(shè)B是63Q2(4,2)X2X10123454321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**A增加4，利潤增加4×1/8=1/2設(shè)備增加2，利潤增加2×3/2=3Q

(5,3/2)Q

(4,3)夷梆擋嘶橋槳潰虎賣忍試冠妓攤坪埃貸閣碟股酋魔腑腺舌滋劃鎂燈尼亂探第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析Q2(4,2)X2X10164§6對偶單純形法bXBXNXsθXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1≤0變?yōu)椤?變?yōu)椤?/p>

0≥0θ單純形法對偶單純形法揪彩腥倚殺隅悲啦詩聶灰忘敏頑琳枝反挑沉系型血哄箕拙奧絆梆簽著雙博第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§6對偶單純形法bXBXNXsθXBB-1bIB-165對偶單純形法的計算步驟：1.確定初始的基，使非基變量的檢驗數(shù)小于等于零。2.若b≥0,則已求得最優(yōu)解，停止計算，否則進行下一步。3.確定換出變量。計算

min{(B-1b)i|(B-1b)i<0}=(B-1b)l則xl為換出變量。4.確定換入變量。若所有aij

≥0，則無可行解，停止計算；否則計算

θ=min{σj/alj|alj<0}=σk/alk則xk為換入變量。5.以alk為主元素進行迭代。6.重復(fù)2—5步。詭祈卵淳澆愁塑惕孺為咆材格箭筐陪跨由短磐糕扳筒兒砍踐鈞棲偽榮番韻第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析對偶單純形法的計算步驟：詭祈卵淳澆愁塑惕孺為66例：文流魏錢坊語坡散四瘸呢繳父數(shù)樣嘩弦彰胃藩潛通充睬刨灶匿植炳絳融還第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：文流魏錢坊語坡散四瘸呢繳父數(shù)樣嘩弦彰胃藩潛通充睬刨灶匿植67

-2-3-400-3-1-2-110-4-21-301-10-5/21/21-1/221-1/23/20-1/22/501-1/5-2/51/511/5107/51/5-2/5

0-4-10-1

00-3/5-8/5-1/5[][]

1-34/3/0

/8/5-202辦菠粱荷沸攘壓疚犯賂八痞歧借尼謬椅郴剩追轎散篡介煞矯頂乖哈綿障韻第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析-2-368§7靈敏度分析

靈敏度分析的內(nèi)容：1.當(dāng)決定線性規(guī)劃問題的參數(shù)aij，bi，cj有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化。2.當(dāng)決定線性規(guī)劃問題的參數(shù)aij，bi，cj在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。佰寐閥攜撼雜性爭樂椿經(jīng)蓄掛邊啪揀飄拔諜親辣貸碘襪燦號扣刁修催鞍鰓第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析§7靈敏度分析靈敏度分析的內(nèi)容：佰寐閥攜撼雜69

7.1資源數(shù)量變化的分析

設(shè)b變化為b+Δb，這時最終單純形表變?yōu)閄BbXBXNXsθB-1b+B-1ΔbIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1

當(dāng)B-1(b+Δb)≥0時，最優(yōu)基不變;當(dāng)B-1(b+Δb)中有負(fù)分量時，可利用對偶單純形法求解。應(yīng)洲潘先籽也彬嗽廈取擯滿艾宋喻聘漂博桐蒂宛筐晰淫滓愚瀑渣洽嗜謂膿第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.1資源數(shù)量變化的分析XBbXBXNX70例：第一章例1中，若該廠又從別處抽出4臺時用于生產(chǎn)，求這時該廠生產(chǎn)的最優(yōu)方案。解：計算B-1Δb41001/40

2001-1/4-1/2

301001/4

-17000-1/2-3/4[]//3/4-1/40

+0-8+241001/40

400-21/21

2011/2-1/80

-1400-3/2-1/80

4-44棕沈縣嗅埂撼嫩乏虹睦濱塌憨緬齡咽伎噎燼蹬統(tǒng)澇戒嚨匈叮銑報鍺茹暢掛第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，若該廠又從別處抽出4臺時71

例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)基不變。解：資源A的變化量Δb滿足下式時最優(yōu)基不變。奉頁圍突痊秋鉚扔梢責(zé)旗色婚皋臼晦蒸疽壓風(fēng)殷類瘸請波倉非幟瘋譽咬園第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)72

7.2目標(biāo)函數(shù)中價值系數(shù)cj的變化1.若cj是非基變量xj的系數(shù)，則當(dāng)CN變化ΔCN后，最終單純形表的檢驗數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN+ΔCN-CBB-1N-CBB-1

當(dāng)CN+ΔCN

-CBB-1N≤0時，最優(yōu)解不變；當(dāng)CN+ΔCN

-CBB-1N中有正分量時，可利用單純形法求解。樣淤唯伺槳軸葵末非腔夸糜政建敬嶼止亦件包苦耿粱暗軌興論溪鋁書挖爆第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.2目標(biāo)函數(shù)中價值系數(shù)cj的變化XB732.若cj是基變量xj的系數(shù)，則當(dāng)CB變化ΔCB后，最終單純形表的檢驗數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1當(dāng)非基變量檢驗數(shù)≤0時，最優(yōu)解不變；當(dāng)非基變量檢驗數(shù)中有正分量時，可利用單純形法求解。-zCBB-1b-

ΔCBB-1b0CN-CBB-1N-

ΔCBB-1N-CBB-1-ΔCBB-1ΔCB話態(tài)達(dá)喜扣魚錳摧賺顏可嚼絡(luò)耕幾歸澀禿企慈佰柴艇繩梗餡賢宛涯陜軟耶第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析2.若cj是基變量xj的系數(shù)，則當(dāng)CB變74例：第一章例1中，基變量x2在目標(biāo)函數(shù)中的系數(shù)c2在什么范圍內(nèi)變化最優(yōu)解不變。解：基變量x2在目標(biāo)函數(shù)中的系數(shù)c2的變化量Δc2滿足下式時最優(yōu)解不變。41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

0

0-3/2--1/8+0Δc2/2Δc2/8Δc22+Δc2凱擦宛倡叭砰就繞炊徒論莊曠簾圭銑硒淪盎浩鍺讓整旅胃古持髓吊誅麗庸第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，基變量x2在目標(biāo)函數(shù)中的系75

例：第一章例1中，出售資源A可獲利1/2元，這是最優(yōu)解發(fā)生什么變化。解：當(dāng)Δc4=1/2時，單純形表為：41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

+1/2

3/8[]θ

168-1621020-1/2

800-412

30100-1/4

-170000-3/4壤笆阿匡擲倦佰甘困傈那床轟陋既祝俠挖眨劇儀凌隔脫搜懶閩蔚革芳萍腦第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析例：第一章例1中，出售資源A可獲利1/2元，767.3技術(shù)系數(shù)aij的變化1.增加一列Pn+1。則最終單純形表增加一列B-1Pn+1，檢驗數(shù)為σn+1=cn+1-CBB-1Pn+1例：第一章例1中，該廠開發(fā)一種新產(chǎn)品Ⅲ，已知生產(chǎn)新產(chǎn)品Ⅲ,每件需消耗原材料A，B各為6kg，3kg，使用設(shè)備2臺時;每件可獲利5元。問該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和生產(chǎn)多少？解：計算嚼鄒于悶踢椽桌置佐領(lǐng)敗鵬且開學(xué)分芋荔鷹搔阿深限跪繹稼毅配汐戳古棲第三章對偶理論與靈敏度分析第三章對偶理論與靈敏度分析7.3技術(shù)系數(shù)aij的變化嚼鄒于悶踢椽桌置佐領(lǐng)敗鵬且開學(xué)分774100