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