運(yùn)籌學(xué)基礎(chǔ)對(duì)偶線性規(guī)劃(2)(已修改)
2025-05-12 12:05 本頁(yè)面
【正文】 任一 線性規(guī)劃 問(wèn)題都存在另一與之伴隨的線性規(guī)劃問(wèn)題 ，他們從不同角度對(duì)一個(gè)實(shí)際問(wèn)題提出并描述 ， 組成一對(duì)互為對(duì)偶的線性規(guī)劃問(wèn)題 。 第二章 線性規(guī)劃的對(duì)偶理論 167。 對(duì)偶線性規(guī)劃問(wèn)題的提出 一、對(duì)偶線性規(guī)劃問(wèn)題 某工廠計(jì)劃安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品 ， 已知每種單位產(chǎn)品的利潤(rùn) 、 生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、 B兩種原材料的消耗 、現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如下表所示： 【 例 1】 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤(rùn)（萬(wàn)元） 2 3 ?原問(wèn)題的策略 : ?問(wèn)應(yīng)如何安排生產(chǎn)才能使工廠獲利最大？ ?現(xiàn)在的策略 : ?假設(shè)不生產(chǎn) Ⅰ 、 Ⅱ 產(chǎn)品 ,而是計(jì)劃將現(xiàn)有資源出租或出售 ,從而獲得利潤(rùn) ,這時(shí)需要考慮如何定價(jià)才合理 ? 21 32 xxf ??m a x????????????0x,x12x4 16 x48x2x.212121 設(shè) x x2分別表示計(jì)劃生產(chǎn) 產(chǎn)品 Ⅰ 、 Ⅱ 的單位數(shù)量，由題意 原問(wèn)題的模型 為： 工廠獲得最大利潤(rùn) 符合資源限制 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤(rùn)（萬(wàn)元） 2 3 原問(wèn)題的模型 ? 改變策略后，需要考慮如何給資源定價(jià)的問(wèn)題！ 設(shè) y y2 、 y3分別表示出租單位設(shè)備 臺(tái)時(shí)的租金和出售單位原材料 A、 B的利潤(rùn) . y1+4y2≥2 ， 2y1+4y3≥3 則： ? 工廠出租設(shè)備 、 原材料的租金要大于生產(chǎn)的利潤(rùn)才合算 。 321 y12y16y8gm in ???工廠把所有設(shè)備臺(tái)時(shí)和資源都出租和出讓 ， 其收入為： ? 要尋找使租用者支付的租金最少的策略 。 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤(rùn)（萬(wàn)元） 2 3 新問(wèn)題的模型 工廠 改變策略以后 的數(shù)學(xué)模型為： 321 y12y16y8g m i n ??????????????3,2,1,034y2y24yy.. 3121iytsi工廠獲得相應(yīng) 利潤(rùn) 用戶所付租金最少 321 12168m i n yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x????????????0,12416482..212121xxxxxxts 聯(lián)系在于，它們都是關(guān)于工廠生產(chǎn)經(jīng)營(yíng)的模型 ,并且使用相同的數(shù)據(jù)； 原模型和對(duì)偶模型既有聯(lián)系又有區(qū)別 區(qū)別在于 ,它們所反映的實(shí)質(zhì)內(nèi)容是完全不同的：前者是站在工廠 經(jīng)營(yíng)者 的立場(chǎng)上追求工廠的 銷(xiāo)售收入最大 ，而后者則是站在談判對(duì)手 的立場(chǎng)上尋求應(yīng)付工廠 租金最少 的策略。 所謂 對(duì)偶規(guī)劃 ，就是與線性規(guī)劃原問(wèn)題相對(duì)應(yīng)并使用同一組數(shù)據(jù)按照特定方法形成的另一種反映不同性質(zhì)問(wèn)題的線性規(guī)劃模型。 原模型與對(duì)偶模型有很多的內(nèi)在聯(lián)系和相似之處。如原問(wèn)題如求目標(biāo)函數(shù)最大化，對(duì)偶問(wèn)題即求目標(biāo)函數(shù)最小化；原問(wèn)題目標(biāo)函數(shù)的系數(shù)變成為對(duì)偶問(wèn)題的右邊項(xiàng)，而原問(wèn)題的約束的右邊項(xiàng)則變成為對(duì)偶問(wèn)題目標(biāo)函數(shù)的系數(shù)；對(duì)偶問(wèn)題的系數(shù)矩陣是原問(wèn)題系數(shù)矩陣的轉(zhuǎn)置。就象一個(gè)人對(duì)著鏡子會(huì)左右顛倒一樣，原問(wèn)題與對(duì)偶問(wèn)題之間存在著嚴(yán)格的對(duì)應(yīng)關(guān)系。 原問(wèn)題的一般模型可定義為： 二、對(duì)偶規(guī)劃的一般數(shù)學(xué)模型 n n x c x c x c Z ? ? ? ? ... max 2 2 1 1 . 1 1 2 12 1 11 ... b x a x a x a n n ? ? ? ? 2 2 2 22 1 21 ... b x a x a x a n n ? ? ? ? … … …. m n mn m m b x a x a x a ? ? ? ? ... 2 2 1 1 0 ,..., , 2 1 ? n x x x 相應(yīng)的對(duì)偶問(wèn)題的一般模型可定義為： m m y b y b y b S ? ? ? ? ... min 2 2 1 1 . 1 1 2 21 1 11 ... c y a y a y a m m ? ? ? ? 2 2 2 22 1 12 ... c y a y a y a m m ? ? ? ? … … … n m mn n n c y a y a y a ? ? ? ? ... 2 2 1 1 0 ,..., , 2 1 ? m y y y 上述的原問(wèn)題 P和對(duì)偶問(wèn)題 D還可以用矩陣形式寫(xiě)為： (P) max Z= cx . Ax ≤b x ≥0 其中 ) ,.., , ( 2 1 m y y y y ? 上述的對(duì)偶模型都稱(chēng)作為 對(duì)稱(chēng)型對(duì)偶模型 。 而在當(dāng)原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型以后所建立的對(duì)偶模型則是 非對(duì)稱(chēng)型的 ，如： (P) maxZ= cx . Ax =b x≥ 0 . yA y ≥ c ≥ 0 (D) min S= yb . yA≥c y為自由變量 (D) minS= yb 原問(wèn)題與對(duì)偶問(wèn)題的矩陣形式 問(wèn)題：如何由原模型寫(xiě)出對(duì)偶模型？其規(guī)律是什么 ? 三、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系 當(dāng)我們討論對(duì)偶問(wèn)題時(shí)必定是指一對(duì)問(wèn)題，因?yàn)闆](méi)有原問(wèn)題也就不可能有對(duì)偶問(wèn)題。原問(wèn)題和對(duì)偶問(wèn)題總是相依存在的。同時(shí)，原問(wèn)題和對(duì)偶問(wèn)題之間也并沒(méi)有嚴(yán)格的界線，它們互為對(duì)偶，誰(shuí)都可以是原問(wèn)題，誰(shuí)也都可以是對(duì)偶問(wèn)題。 321 12168m i n yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x??????????0,12416482..212121xxxxxxts 下列的表給出了原問(wèn)題模型和模型的對(duì)應(yīng)關(guān)系，這些也可以看作是一個(gè)線性規(guī)劃原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的一般規(guī)律。 原問(wèn)題線性規(guī)劃模型 對(duì)偶線性規(guī)劃模型 原問(wèn)題為 maxZ的線性規(guī)劃問(wèn)題對(duì)偶關(guān)
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1