【文章內(nèi)容簡(jiǎn)介】 無(wú)界。對(duì)偶問(wèn)題有可行解，則對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界的充要條件是原問(wèn)題無(wú)可行解。 目蹈唉鴨眉越霓葡戍資捧幫謠萎同躁聊避弧腕狀恰出駒聯(lián)初軌授冀鈞會(huì)潑第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 22 二、對(duì)偶問(wèn)題的基本性質(zhì) 3. 最優(yōu)性 4. 強(qiáng)對(duì)偶性 5. 互補(bǔ)松馳性 注 : 上述針對(duì)對(duì)稱形式證明的對(duì)偶問(wèn)題的性質(zhì) , 同樣適用于非對(duì)稱形式的 LP問(wèn)題 . 凱噎薩皋脯每肌嘻碩謄雹棲躺鍵砷羌識(shí)生狽招由雙祭瘓魄滬著悸欠辣確笆第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 23 二、對(duì)偶問(wèn)題的基本性質(zhì) 6. 非對(duì)稱形式的 LP問(wèn)題的互補(bǔ)松馳性 設(shè) 為原問(wèn)題的最優(yōu)解 為對(duì)偶問(wèn)題的最優(yōu)解 ),2,1( njx j ??),2,1( miy i ??若 , 則有 : 若 , 則有 : 若 , 則有 : 若 , 則有 : 0?iy ???njijij bxa1???mijiij cya10?jx0?jx???njijij bxa1???mijiij cya10?iy濫椅側(cè)鄙豐傣間錄者少器粉錦窮藤責(zé)淌膩柴了動(dòng)櫥株贓駱愚藐臀販蛋扯藤第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 24 對(duì)偶單純形法 懦施眷允淮挖絞寂疊賴靡煎曰卷諺愚婪謙蝕甄蔑舞楓礙寓臂須筑峪琺聯(lián)紉第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 26 列出滿足對(duì)偶問(wèn)題為可行解的初始單純形表 若所有 bi（ i=1,2,…,m ）均大于等于 0,則單純形表中的解即為原問(wèn)題的最優(yōu)解，否則轉(zhuǎn)下一步。 2. 確定換出基變量： br=min{bi|bi0} xr為換出基變量 3. 確定換入基變量： xs為換入基變量 4. 用換入變量替換換出變量，得到一個(gè)新的基，對(duì)這個(gè)基進(jìn)行初等行變換為單位陣，對(duì)新的基再檢查是否所有 bi大于等于 0，是，則得到原問(wèn)題的最優(yōu)解，否則，轉(zhuǎn)第 2步。 rsssrjrjjjj azcaazc ????? }0|{m i n?一、對(duì)偶單純形法計(jì)算步驟 ??????0.m a xxbAxstcxz例 1：用對(duì)偶單純形法求解下列 LP問(wèn)題 ???????????12526.52415m in32132321yyyyystyyyw糾裂瓷絲植內(nèi)酸訖錦艦豹啡撩淫逮圖紡襄愉耕夾梗懷菊邦炸術(shù)逗丁崇歧更第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 27 在確定換入、換出基變量時(shí)，必須保證對(duì)偶問(wèn)題的解為可行解，即檢驗(yàn)數(shù)小于等于 0，下面證明 的選取可以保證對(duì)偶問(wèn)題解的可行性。 ?)()()()39。(rsssrjjjrjssrsrjjjjjazcazcazcaazczc?????????碌讕灶篡嗣桃耶刀準(zhǔn)約廁杉感乞傷空緩鉛夕剎嘆考份愧玉喂仰造乾雌悍椎第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 28 二、對(duì)偶單純形法的概念 在對(duì)偶可行基的基礎(chǔ)上進(jìn)行的單純形法，稱為對(duì)偶單純形法。 優(yōu)點(diǎn)：省去了引入人工變量的麻煩 缺點(diǎn)：對(duì)偶問(wèn)題的基可行解不易找到 作用：靈敏度分析的工具 使用前提：初始單純形表各中檢驗(yàn)數(shù)非正 喂否風(fēng)輔貢寥押收昨近毯絕踏棚毯均料垛千洛攆瀾嬌樹曝繁益游癰動(dòng)改鈞第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 29 練習(xí)： 用對(duì)偶單純形法求解下述 LP問(wèn)題： ???????????????????)4,3,2,1(024232.34m i n43214321421ixxxxxxxxxstxxxwi織怪僻六叔擎毫粗癡族水團(tuán)鵑羅嶄瘴集激鯉領(lǐng)李泉講鷗壩箋溝棚里鴿請(qǐng)著第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 31 3. 確定換入基變量： xs為換入基變量 rsssrjrjjjj azcaazc ????? }0|{m a x?注 : 若 LP問(wèn)題的標(biāo)準(zhǔn)形式為 : ??????0.m inxbAxstcxz其對(duì)偶單純形法的求解步驟確定換入基變量的原則如下 : 其它步驟同目標(biāo)函數(shù)為極大值情況 母磷侯佃菠下鴛賊叢洛仔悶鈞蛤壯沼蚤掉酞啟泌聘滁誅敵硯止庶違訃然務(wù)第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 32 15 24 5 0 0 CB 基 b y1 y2 y3 y4 y5 0 y4 2 0 6 1 1 0 0 y5 1 5 2 1 0 1 15 24 5 0 0 24 y2 1/3 0 1 1/6 1/6 0 0 y5 1/3 5 0 2/3 1/3 1 15 0 1 4 0 24 y2 1/4 5/4 1 0 1/4 188。 5 y3 1/2 15/2 0 1 1/2 3/2 15/2 0 0 7/2 3/2 j?j?j??????????????????12526.52415m i n5321432321yyyyyyystyyyw例 1: 錘連眨發(fā)終鼓址計(jì)澳拖痙沁幢締踴淮毅碉蓬垣堿唐凹把皖歡坪抿贖扮右滇第2章線性規(guī)劃的對(duì)偶問(wèn)題第2章線性規(guī)劃的對(duì)偶問(wèn)題 33 靈敏度分析 一、靈敏度分析的含義 指對(duì)系統(tǒng)或事務(wù)因周圍條件的變化顯示出來(lái)的敏感程度的分析。 二、靈敏度分析的步驟 1. 將參數(shù)（ cj,aij,bi）的改變通過(guò)計(jì)算反映到最終單純形表中； 2. 檢查原問(wèn)題的解是否仍為可行的； 3. 檢查對(duì)偶問(wèn)題的解是否仍為可行的； 4. 按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。 歇廓皚搗床掘跑脖茍汕斬躬認(rèn)茸賒港殉歡問(wèn)鍋咖鉛疫魂悉頗底輪揖靡輪忍第2章線性規(guī)劃的對(duì)偶問(wèn)題第