運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(第五版)-(第二章)(編輯修改稿)
2024-09-12 00:10 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 互補(bǔ)基解，原問(wèn)題的松弛變量與對(duì)偶問(wèn)題 的變量對(duì)應(yīng)；原問(wèn)題的變量與對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)?；パa(bǔ)的基解 對(duì)應(yīng)的目標(biāo)函數(shù)值相等。 2022/8/28 22 例 書 P59 例 3 ???????????????0, . . . ,15x 5 16x 41222515241321xxxxxxx21 32m a x xxZ ??321yyy2 3 0 0 0 2 3 1 0 1/2 0 1/5 0 4 0 0 2 1 4/5 3 5 0 1 0 0 1/5 0 0 1 0 1/5 1y 2y 3y5y4y1x 2x 3x 4x 5xBCbBX1x4x2x?j?2022/8/28 23 基 1 1 2 0 1/2 0 1/5 0 4/5 1 1/5 1/5 0 4 0 3 3 321 151612m i n yyyW ???242. 421 ??? yyyts0,...,35251531????yyyyy1x2x1y 2y 3y 4y 5y1y3yb1x 2x3x 4x 5x?j?2022/8/28 24 對(duì)偶變量 可理解為對(duì)一個(gè)單位第 種資源的估價(jià)，稱為 影子價(jià) 格 ，但并非市場(chǎng)價(jià)格。 對(duì)偶變量 的值（即影子價(jià)格）表示第 種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。因?yàn)? 167。 4 影子價(jià)格 0m a x???XbAXCXZ0m in???YCYAYbWTTT假設(shè)有 原問(wèn)題 和 對(duì)偶問(wèn)題 如下： iyiii bzy???iiy2022/8/28 25 21 32m a x xxz ??資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化 1,1322 21 ???? zxx0,174 1 ??? ,165 2 ??? zx2x1xO1Q2Q3Q4Q3421 32 xxZ ??目標(biāo)函數(shù)等值線 2022/8/28 26 影子價(jià)格可用于指導(dǎo)資源的購(gòu)入與賣出。 當(dāng) 影子價(jià)格 市場(chǎng)價(jià)格時(shí) ， 買入 ； 影子價(jià)格 市場(chǎng)價(jià)格 時(shí)， 賣出 . 由互補(bǔ)松弛性可知， 即影子價(jià)格為 零，經(jīng)濟(jì)解釋：資源未用完，再增加對(duì)目標(biāo)函數(shù)也無(wú)貢獻(xiàn)。反之， 表明該種資源用盡，再購(gòu)進(jìn)用于擴(kuò)大生 產(chǎn)可增加總利潤(rùn)。 .0?,1????iinjjij ybxa 則。,0?1injjiji bxay ?? ??則2022/8/28 27 167。 5 對(duì)偶單純形法 在單純形表中， 列對(duì)應(yīng)原問(wèn)題的基可行解， 行 對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè) 基解 （不一定可行），當(dāng) 時(shí)， 在檢驗(yàn)數(shù)行就得到對(duì)偶問(wèn)題的 基可行解 ，此時(shí)兩個(gè)問(wèn)題的目 標(biāo)函數(shù)值相等 ，由 最優(yōu)性條件 知，兩個(gè) 問(wèn)題都達(dá)到了最優(yōu)解。 j?0?b0?j?YbbBCCX B ?? ? 1單純形法： 找一個(gè)初始基可行解，保持 b列為正，通過(guò)迭代 找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng) 檢驗(yàn)數(shù)行 全部小于等于零 時(shí)，達(dá)到最優(yōu)解。 2022/8/28 28 對(duì)偶單純形法： 找一個(gè)對(duì)偶問(wèn)題的基可行解（保持 行非 正），原問(wèn)題的解為基解（ b列可以為負(fù)），通過(guò)迭代，當(dāng) b列全部為正（原問(wèn)題也達(dá)到了基可行解） ，即找到最優(yōu)解。 j?檢查是否達(dá)最優(yōu) ： b列 非負(fù) 時(shí)達(dá)最優(yōu)，否則繼續(xù) 2。 對(duì)偶單純形法計(jì)算步驟： 確定出基變量 ： 選擇 b列中負(fù)值最小者對(duì)應(yīng)變量出、 基，即 對(duì)應(yīng)的 為出基變量。 確定進(jìn)基變量 ： 最小比值規(guī)則，即以 對(duì)應(yīng)的 為進(jìn)基變量， 為主元素進(jìn)行迭代。 ? ?0m i n ?? iir bbbrxsjsrjrjjaaa??? ????????????? 0m i nsx rsa2022/8/28 29 為何只考慮 行中 的元素對(duì)應(yīng)的變量進(jìn)基？ 為使迭代后的基變量取正值。 rx0?rja為何采用最小比值規(guī)則選擇進(jìn)基變量？ 為了使得迭代后的多偶問(wèn)題解仍為可行解（檢驗(yàn)數(shù)行仍為非正） 原問(wèn)題無(wú)可行解的判別準(zhǔn)則： 當(dāng)對(duì)偶問(wèn)題存在可行解時(shí)， 若有某個(gè) ，而所有 ，則原問(wèn)題無(wú)可行解，對(duì)偶 問(wèn)題目標(biāo)值無(wú)界。 因?yàn)榈?r行的約束方程即為： 其中 ， ，因此不可能存在 使上式成 立。也即原問(wèn)題無(wú)可行解。 0?rb 0?rjarnnrmmrr bxaxax ???? ?? ,11, . .. ..0?rja 0?rb 0?X2022/8/28 30 例 、用對(duì)偶單純形法求解下述問(wèn)題 321 151612m i n yyyW ???242. 21 ?? yyts0,35232131???yyyyy解 將問(wèn)題改寫為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型 321 151612)m a x ( yyyW ?????242. 421 ????? yyyts0,...,35251531??????yyyyy2022/8/28 31 列單純形表 12 16 15 0 0 0 2 2 4 0 1 0 0 3 2 0 [5] 0 1 12 16 15 0 0 1y 2y 3y 4y 5yBCbBX4y5y0 2 [2] 4 0 1 0 15 3/5 2/5 0 [1] 0 1/5 6 16 0 0 3 4y3y12 1 [1] 2 0 1/2 0 15 1/5 0 4/5 1 1/5 1/5 0 4 0 3 3 1y3y達(dá)到最優(yōu) 2022/8/28 32 注意： 使用對(duì)偶單純形法時(shí)， 當(dāng)約束條件是 時(shí)，可以不必 添加人工變量。 使用對(duì)偶單純形法時(shí)， 初始單純形表中要保證對(duì)偶解為 可行解常難以做到， 所以一般不單獨(dú)使用，常與靈敏 度分析結(jié)合使用。 ?2022/8/28 33 167。 6 靈敏度分析 靈敏度分析： 線性規(guī)劃問(wèn)題中的某些參數(shù)發(fā)生變化，對(duì)解的影響。（ C， A， b） 靈敏度分析的一般步驟： 將參數(shù)的改變經(jīng)計(jì)算后反映到最終單純形表中； 檢查原問(wèn)題和對(duì)偶問(wèn)題是否仍為可行解； 按照下表對(duì)應(yīng)情況，決定下一步驟。 原問(wèn)題 對(duì)偶問(wèn)題 結(jié)論或計(jì)算步驟 可行解 可行解 仍是最優(yōu)解 可行解 非可行解 用單純形法繼續(xù)迭代得到新的最優(yōu)解 非可行解 可行解 用對(duì)偶單純形法繼續(xù)迭代得到新的最優(yōu)解 非可行解 非可行解 引入人工變量，重新編單純形表，重新計(jì)算 2022/8/28 34 一、 C 的變化分析 C的變化只影響檢驗(yàn)數(shù)。 例、 設(shè)有如下的線性規(guī)劃模型 試分析 分別在什么范圍變化時(shí)，最優(yōu)解不變？ ????????????0,15 5 16
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1