線性規(guī)劃對(duì)偶問(wèn)題ppt課件-在線瀏覽
2025-06-20 01:34本頁(yè)面
【正文】 ③無(wú)界性：若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。從而得到如下線性規(guī)劃模型： Min W=1600y1+2500y2+400y3 2y1+?3 . 2y1+5y2+y3 ?4 y y y3 ?0 線性規(guī)劃原問(wèn)題和對(duì)偶問(wèn)題 原問(wèn)題： Max Z=c1x1+…+c nxn a11x1+…+a 1nxn?b1 a21x1+…+a 2nxn?b2 . … … am1x1+…+a mnxn ?bm X1,…,x n?0 對(duì)偶問(wèn)題： Min W=b1y1+…+b mym a11y1+…+a m1ym ? c1 a12y1+…+a m2ym ?c2 . … … a1ny1+…+a mnym ? y1,…,y m ? 0 矩陣表述 原問(wèn)題： ? Max Z=CTX . AX?b X ?0 對(duì)偶問(wèn)題： ? Min W=bTY . ATY ? C Y ? 0 ? 兩個(gè)模型之間的關(guān)系： –原問(wèn)題是求最大值，而對(duì)偶問(wèn)題是求最小值； –原問(wèn)題的約束條件是“ ?”，而對(duì)偶問(wèn)題的約束條件是“ ?”； –原問(wèn)題的目標(biāo)函數(shù)系數(shù)是對(duì)偶問(wèn)題的約束條件右端的常數(shù)項(xiàng)；原問(wèn)題的約束條件右端的常數(shù)項(xiàng)是對(duì)偶問(wèn)題目標(biāo)函數(shù)的系數(shù)； –原問(wèn)題約束條件中 xi的系數(shù)是對(duì)偶問(wèn)題第 i個(gè)約束條件的系數(shù)，原問(wèn)題第 i個(gè)約束條件的系數(shù)是對(duì)偶問(wèn)題的約束條件中 yi的系數(shù)。第 2章 對(duì)偶理論 線性規(guī)劃續(xù) 知識(shí)點(diǎn) ? 了解對(duì)偶問(wèn)題的特點(diǎn)，熟悉互為對(duì)偶的問(wèn)題之間的關(guān)系； ? 掌握對(duì)偶規(guī)劃的理論和性質(zhì)，如可逆性、弱對(duì)偶性、對(duì)偶定理、互補(bǔ)松馳定理等； ? 掌握對(duì)偶單純形法； 主要內(nèi)容 ? 一、對(duì)偶問(wèn)題的基本概念 ? 二、對(duì)稱的對(duì)偶線性規(guī)劃 ? 三、對(duì)偶的基本性質(zhì) ? 四、對(duì)偶單純形法 一、對(duì)偶問(wèn)題的基本概念 載重汽車 大轎車 資源限制 鋼材 勞動(dòng)力 座椅 2 0 2 5 1 1600 2500 400 利潤(rùn)（千元 /輛） 3 4 ? 傳統(tǒng)的線性規(guī)劃問(wèn)題： –在有限的資源下如何安排生產(chǎn)以獲得最大利潤(rùn) ? 該問(wèn)題的線性規(guī)劃模型為： 目標(biāo)函數(shù)： max Z=4x1+3x2 約束條件： 2x1 ＋ 2x2 ?1600 5x1+ ? 2500 x1 ? 400 x1 ? 0,x2 ?0 ? 現(xiàn)在的問(wèn)題：如果工廠目前不再打算生產(chǎn)汽車，而是將鋼材和座椅以比買價(jià)更高的價(jià)格賣出去（加價(jià)），把生產(chǎn)能力以更高的工時(shí)費(fèi)接受外協(xié)加工，那么材料和工時(shí)的定價(jià)應(yīng)該是多少才是合算的？ ? 假設(shè) y1表示出售單位鋼材的利潤(rùn)， y2表示外協(xié)加工的工時(shí)利潤(rùn)， y3表示出售每套大轎車座椅的利潤(rùn) ? 那么生產(chǎn)一輛載重汽車的材料銷售利潤(rùn)和工時(shí)利潤(rùn)之和不應(yīng)低于出售一輛載重汽車所得的利潤(rùn)，即： 2y1+?3 ? 同樣有， 2y1+5y2+y3 ?4 ? 為了不虧本，各種材料的利潤(rùn)（加價(jià)）不能為負(fù)值，即： y y y3 ?0 ? 工廠的總利潤(rùn)是出售材料的利潤(rùn)、工時(shí)利潤(rùn)和座椅利潤(rùn)之和，即： W=1600y1+2500y2+400y3 ? 從工廠決策者的角度看 W越大越好。但為了在市場(chǎng)實(shí)現(xiàn)交易，在滿足上述條件的基礎(chǔ)上， W應(yīng)盡可能小。 對(duì)稱的對(duì)偶線性規(guī)劃 ? 定義：如果一個(gè)線性規(guī)劃具備下面兩個(gè)條件，則稱它具有對(duì)稱形式： –所有的變量都是非負(fù)的； –所有的約束條件都是不等式，且在目標(biāo)函數(shù)是求極大值的情況下，為“ ?”型，求極小值時(shí)，為“ ?”型。 –例： –說(shuō)明：無(wú)界性質(zhì)并不存在逆（例見(jiàn)： P57） ??????????????0,0442..4m a x21212121xxxxxxtsxxZ? ④可行解是最優(yōu)解的條件： –設(shè) X*是原問(wèn)題的可行解， Y*是對(duì)偶問(wèn)題的可行解，當(dāng) CTX*=bTY*時(shí)， X*， Y*是最優(yōu)解。因而是最優(yōu)解。 ? ⑤對(duì)偶定理：若原問(wèn)題有最優(yōu)解，則對(duì)偶問(wèn)題也有最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值相等。 ? 原規(guī)劃的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶規(guī)劃的一個(gè)解；對(duì)偶規(guī)劃的檢驗(yàn)數(shù)對(duì)應(yīng)于原規(guī)劃的一個(gè)解。 m a x . . ,0TssZ
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1