【正文】 2 x 3 x 4 x 5 b x 1 1 0 4/ 5 3/ 5 1/ 5 2 x 2 0 1 2/ 5 1/ 5 2/ 5 3 C 0 0 9/ 5 3/ 5 4/ 5 13 影子價(jià)格（ 4） 例 9 某廠在下一個(gè)計(jì)劃期內(nèi)要安排生產(chǎn) I ， I I 兩種產(chǎn)品，現(xiàn)有生產(chǎn)每種產(chǎn)品一件要消耗的鋼材，煤和機(jī)械加工時(shí)間數(shù)；資源數(shù)及每件產(chǎn)品可獲得的利潤(rùn)如表所示（見(jiàn)表 1. 55 ） 試制訂一個(gè)最優(yōu)生產(chǎn)計(jì)劃。當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)當(dāng)買進(jìn)該種資源用于擴(kuò)大生產(chǎn)；當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，企業(yè)的決策者應(yīng)當(dāng)把已有的該種資源賣掉。由于企業(yè)生產(chǎn)任務(wù)，產(chǎn)品的結(jié)構(gòu)及其知識(shí)的含量等情況的變化，資源的影子價(jià)格也隨之改變。 （二）第 i 種資源的影子價(jià)格又代表對(duì)一個(gè)單位第 i 種資源的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)。 影子價(jià)格的經(jīng)濟(jì)意義： （一）第 i 種資源的影子價(jià)格 y i * 是一個(gè)邊際函數(shù)。 對(duì)偶單純形法（ 2） ?????????????????????????????5102263433252142132121, .. . ,i,xxxxxxxxxx.xxffm a xi39。已知甲，乙，丙，丁四種復(fù)合肥每公斤的價(jià)格及含氮，磷，鉀的數(shù)量，如表 1 . 5 。三個(gè)紡織廠所需數(shù)量和兩個(gè)倉(cāng)庫(kù)現(xiàn)有庫(kù)存量，以及每噸原棉從各個(gè)倉(cāng)庫(kù)運(yùn)送到各個(gè)紡織廠所需的運(yùn)費(fèi)見(jiàn)表 1 . 3 表 1 . 3 運(yùn)輸費(fèi) 工廠 1* 工廠 2* 工廠 3* 庫(kù)存量 （噸） 倉(cāng)庫(kù) 1 2 1 3 50 倉(cāng)庫(kù) 2 2 2 4 30 需求量（噸） 40 15 25 如何 調(diào)運(yùn) ， 才能 使 總 成本 最省 ？ 第一章 線性規(guī)劃 圖解法 單純型法 兩階段法 對(duì)偶規(guī)劃 對(duì)偶單純型法 靈敏度分析 目標(biāo)規(guī)劃 圖解法（ 1） ——唯一最優(yōu)解 ???????????????)(08234..52m a x212121jxxxxxtsxxsj圖解法（ 2） ——基本概念 可行解 —— 不可行解 可行解集 （ 可行區(qū)域 ） 最優(yōu)解 最優(yōu)目標(biāo)函數(shù)值 基本可行解 基本最優(yōu)解 圖解法（ 3） ——無(wú)窮多最優(yōu)解 ???????????????)(08234..2m a x212121jxxxxxtsxxsj圖解法（ 4） ——解無(wú)界 ?????????????0021..22m a x2,1212121xxxxxtsxxs圖解法（ 5） ——無(wú)可行解 ??????????????021..22m i n2,1212121xxxxxtsxxs圖解法（ 6） —— 結(jié)論 線性規(guī)劃問(wèn)題的解有四種情況 1．有唯一最優(yōu)解 2．有無(wú)窮多最優(yōu)解 3．有可行解，但無(wú)最優(yōu)解（解無(wú)界） 4．無(wú)可行解 單純型法 標(biāo)準(zhǔn)化 單純型法 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 (一 ) 1．目標(biāo)函數(shù)求最大 2．約束條件取等號(hào) 3．變量為非負(fù) 11( 1 )m a x( 1 , 2 , ..., ).0 ( 1 , 2 , ..., )njjjnij j ijjf c xa x b i mstx j n????????? ?????標(biāo) 準(zhǔn) 形 的 代 數(shù) 表 示 ? ?? ?? ?121212, , ..., , ..., , ...,Tij m nTnTnTnmax f = c xA x = b .x0Aac c c cb b b bx x x x?????????（ 2 ） 標(biāo) 準(zhǔn) 形 的 矩 陣 表 示其 中 （ ）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（二） 12121212m i n 23 2 674..20 1 2j1. 5 f x xxxxxstxxxj?????????????? ???例 將 下 列 線 性 規(guī) 劃 問(wèn) 題 化 為 標(biāo) 準(zhǔn) 形， ，單純型法（一） 某工廠計(jì)劃在一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品分別需要經(jīng)過(guò) A、 B兩道工序加工。又知每一調(diào)度人員在任 1 時(shí)段開(kāi)始上班后，要連續(xù)工作 8 小時(shí)（包括輪流吃飯時(shí)間）才能滿足調(diào)度值班工作需要。 表 2 4 1 手機(jī) 車間 甲 乙 丙 丁 車間最大生產(chǎn)能力 A 1 . 5 3 1 3 1200 小時(shí) B 8 20 3 12 3000 小時(shí) C 3 8 3 5 2400 小時(shí) 單位利潤(rùn) 200 元 1200 元 100 元 400 元 — 如果你是主管，應(yīng)該投產(chǎn)那幾種手機(jī)，各生產(chǎn)多少，才能獲得盡可能多的利潤(rùn)？ 運(yùn)籌學(xué)模型（ 2） 【七橋問(wèn)題】 在哥雷斯堡（ Konigsbe rg ）有一條名叫普雷爾（ P r e g e l ）的河流從城市中間流過(guò)，普雷爾河的中央有一大一小兩座島嶼，河岸和兩座島由七座橋相互連接，如圖 3 53 所示 : 圖 3 53 于是在居民們每天散步的時(shí)候就產(chǎn)生了一項(xiàng)有趣的消遣活動(dòng)：從 A 岸、 B 島、 C島、 D 岸這四個(gè)地方任選一處出發(fā)，走過(guò)所有七座橋，最后回到出發(fā)的地方，而且要求每座橋只能經(jīng)過(guò)一次，不得重復(fù)。運(yùn)籌學(xué)模型（ 1） [ 生產(chǎn)計(jì)劃模型 ] 國(guó)內(nèi)某手機(jī)產(chǎn)商考慮生產(chǎn)甲、乙、丙、丁型號(hào)的四款手機(jī)，每款手機(jī)都需要依次經(jīng)過(guò) A 、 B 、 C 三個(gè)車間加工完成。假設(shè)每款手機(jī)需要各車間加工的工時(shí)（單位：小時(shí)）、每個(gè)車間的最大生產(chǎn)能力以及每款手機(jī)預(yù)期的利潤(rùn)都已知，具體數(shù)據(jù)參見(jiàn)表 2 4 1 。 B C A D 運(yùn)籌學(xué)模型（ 3） 【合理下料問(wèn)題】 某工地要求做 100 套鋼筋，每套為 3 根，它們的長(zhǎng)度分別 為 米， 米和 米；原材料長(zhǎng)為 米，為應(yīng)當(dāng)怎樣截割鋼筋，才能使所需的原材料根數(shù)為最少？ 提示 1：如果只需要截 100根，如何下料？ 提示 2：如果需要截 100根，又如何下料？ 有八種方法截取 ? 1 2 3 4 5 6 7 8 2 1 1 1 0 0 0 0 0 2 1 0 3 2 1 0 0 0 1 3 0 1 3 4 x1 x2 x3 x4 x5 x6 x7 x8 ? Mf=x1+x2+x3+x4+x5+x6+x7+x8 ? 2x1+x2+x3+x4=100 ? 2x2+3x3 +3x5+2x6+x7=100 ? x3+3x4 +x6+3x7+x8=100 ? Xj=0且為整數(shù) j=1,2,3,……8 運(yùn)籌學(xué)模型（ 4） 【排班問(wèn)題】 某工廠的中心調(diào)度室，每晝夜 24 小時(shí)都要有人員值班，已知每個(gè)時(shí)間段（每 4 小時(shí)為一個(gè)時(shí)間段）所需要的值班人員如表 1 . 6 。為使參加值班的總?cè)藬?shù)最少，試列出數(shù)學(xué)模型 J段 時(shí)間段 需人數(shù) 1 26 2 2 610 5 3 1014 10 4 1418 12 5 1822 6 6 222 7 ? Xjj時(shí)段初形成得人數(shù) j=1,2,3,4,5,6 ? Minf=x1+x2+x3+x4+x5+x6 ? X1+x6=2 ? X1+x2=5 ? X2+x3=10 ? X3+x4=12 ? X4+x5=6 ? X5+x6=7 運(yùn)籌學(xué)模型（ 5） 【運(yùn)輸問(wèn)題】 現(xiàn)有兩個(gè)倉(cāng)庫(kù)（發(fā)點(diǎn)）運(yùn)送庫(kù)存原棉來(lái)滿足三個(gè)紡織廠（收點(diǎn)）的需要。已知每件產(chǎn)品在每道工序上加工所需的機(jī)時(shí)及生產(chǎn)每件產(chǎn)品可以獲得的利潤(rùn)如下表，如何安排生產(chǎn)，才能使總利潤(rùn)最大？ 甲 乙 可用機(jī)時(shí) 工序 A 2 4 80 工序 B 3 2 60 單位利潤(rùn) 60 50 單純型法（二） 80. . 6 0012121212ma x f = 6 0 x +5 0 x2 x +4 xs t 3 x +2 xx 0 , x?????? ???（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x1x單純型法（三） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x單純型法（四） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，???????????????????432102031324032382021120042143242,j,xxxxxxx.xxfma xj????????????????????43210302123402425151 5 0 042143141,j,xxxxxxx.xxfm a xj??????????????????432104021260234321432,j,xxxxxxx.fma xj??????????????????4,3,2,1,020212204121..225351000m a x43132131jxxxxxxxtsxxfj???????????????????4,3,2,1,0154183102141..2354151350m a x43243143jxxxxxxxtsxxfj單純型