【正文】 靜態(tài)分析 比較靜態(tài)分析 動(dòng)態(tài)分析 改變價(jià)值向量 ? 一般改變情況 ?改變非基變量的價(jià)值向量 ?改變基變量的價(jià)值向量 ?算例 一 般 改 變 Bx Nx RH S Z Bx 0 ????NBcNBc1 bBc B1?? I NB 1? bB1? 當(dāng)價(jià)值向量改變時(shí)在單純形表里后影響的只是檢驗(yàn)數(shù) 和目標(biāo)函數(shù)值，其它沒有改變，因而只需計(jì)算新的檢 驗(yàn)數(shù)和目標(biāo)函數(shù)值 和 如果檢驗(yàn)數(shù)非正，則原最優(yōu)解依然是最優(yōu)解；否 則是 基可行解。以此為初始基可行解進(jìn)行迭代就可以求出 新問題的解。 ????????NBNcNBc1? bBcxcB1~ ??????非 基 變 量 改變非基變量 kx 的價(jià)值向量 kc ? kc? ： kBkcNBc ?????? 1? ?kkkkcc ????? ?? 為了使原最優(yōu)解還是最優(yōu)解則要求 0??????kkkkcc?? ， 即kkkcc ???? 基 變 量 改變基變量 kx 的價(jià)值向量 kc ? kc ? ，基變量 kx 對(duì)應(yīng)的約束為第 l 個(gè) ??????????NkkBcNBccNBc11)0,0,0,0( ?? )(1))((lkkTNNBcc????? ? lkkBBBbccbcbcbBc )(1??????????? ????????NBNcNBc1?算 例 問題 的目標(biāo)函數(shù)中變量2x的系數(shù)由 0 變成 1. ????????????????5,4,3,2,1。1226..215m i n5321432131jxxxxxxxxxtsxxzj1x 2x 3x 4x 5x 1/2 1 1/4 9/4 31 /4 1/2 1 1/4 1/4 1 2 1/2 3/2 1/4 1/2 由于 2x 為非基變量，所以系數(shù)的改變只影響 2x 的檢驗(yàn)數(shù)， 新的檢驗(yàn)數(shù)為 2/3102/12222 ??????????? cc??。由于新檢 驗(yàn)數(shù)仍然為負(fù)數(shù)，所以原最優(yōu)解依然是新問題的最優(yōu)解。 為了使原最優(yōu)解依然是新問題的最優(yōu)解， 2x 的系數(shù)最小 可以變?yōu)?/122??? c?。 改變右端向量 基 本 思 想 bBb ??? ? 1 ， bcz B ??? ?0 如果 0??b 則原最優(yōu)解還是最優(yōu)解，否則利用對(duì) 偶單純形算法求解新問題。 Bx Nx RHS Z Bx 0 ??? ? NB cNBc 1 bBcB 1?? I NB 1? bB 1? 當(dāng)只改變一個(gè)分量ssbb ?? 時(shí)： 11111)()(???????????????????sssBbbbbBbBbbbBbBb 其中1?sB 為1?B 的第 s 列。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃問題及其數(shù)學(xué)模型 ?例 1 某工廠要生產(chǎn)兩種新產(chǎn)品： 門 和 窗 。 經(jīng)測(cè)算 ，每生產(chǎn)一扇門需要在車間 1加工 1小時(shí) 、 在車間 3加工 3小時(shí)；每生產(chǎn)一扇窗需要在車間 2和車間 3各加工 2小時(shí) 。 而車間 1每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間為 4小時(shí) 、 車間 2為 12小時(shí) 、 車間 3為 18小時(shí) 。已知每扇門的利潤(rùn)為 300元 ， 每扇窗的利潤(rùn)為 500元 。 而且根據(jù)經(jīng)市場(chǎng)調(diào)查得到的該兩種新產(chǎn)品的市場(chǎng)需求狀況可以確定 ， 按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去 。 ?問該 工廠應(yīng)如何安排這兩種新產(chǎn)品的生產(chǎn)計(jì)劃 ，可使總利潤(rùn)最大 ？ ?在該問題中 ， 目標(biāo)是總利潤(rùn)最大化 ， 所要決策的變量是新產(chǎn)品的每周產(chǎn)量 ， 而新產(chǎn)品的每周產(chǎn)量要受到三個(gè)車間每周可用于生產(chǎn)新產(chǎn)品時(shí)間的限制 。 因此 ， 該問題可以用 目標(biāo) 、 決策變量和約束條件 三個(gè)因素加以描述 。 ?實(shí)際上 ， 所有的線性規(guī)劃問題都包含這三個(gè)因素： （ 1） 決策變量 是問題中有待確定的 未知 因素 。 例如決定企業(yè)經(jīng)營(yíng)目標(biāo)的各產(chǎn)品的產(chǎn)量等 。 （ 2） 目標(biāo)函數(shù) 是指對(duì)問題所追求的目標(biāo)的數(shù)學(xué)描述 。 例如利潤(rùn)最大 、 成本最小 等 。 （ 3） 約束條件 是指實(shí)現(xiàn)問題目標(biāo)的 限制因素 。 如原材料供應(yīng)量 、 生產(chǎn)能力 、 市場(chǎng)需求等 ， 它們限制了目標(biāo)值所能到達(dá)的程度 。 解： 例可用下表 表示 。 車間 單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)） 每周可獲得的生產(chǎn) 時(shí)間（小時(shí)） 門 窗 1 1 0 4 2 0 2 12 3 3 2 18 單位利潤(rùn)（元） 300 500 （ 1） 決策變量 本問題的決策變量是每周門和窗的產(chǎn)量 。 可設(shè)： x1為每周門的產(chǎn)量 （ 扇 ） ； x2為每周窗的產(chǎn)量 （ 扇 ） 。 （ 2） 目標(biāo)函數(shù) 本問題的目標(biāo)是總利潤(rùn)最大 。 由于門和窗的單位利潤(rùn)分別為 300元和 500元 ， 而其每周產(chǎn)量分別為x1和 x2， 所以每周總利潤(rùn) z為： z = 300x1＋ 500x2 （ 元 ） （ 3） 約束條件 本問題的約束條件共有 四 個(gè) 。 ?車間 1每周可用工時(shí)限制： x1 ? 4 ?車間 2每周可用工時(shí)限制： 2x2 ? 12 ?車間 3每周可用工時(shí)限制： 3x1 +2x2 ? 18 ?非負(fù)約束 :x1 ? 0, x2 ? 0 例 線性規(guī)劃模型 : 12121212M ax z 3 0 0 5 0 0 4 2 12s .t . 3 2 1 8, 0xxxxxxxx???????????? ??這是一個(gè)典型的 利潤(rùn)最大化 的生產(chǎn)計(jì)劃問題。其中，“ Max”是英文單詞“ Maximize”的縮寫，含義為“最大化”； “ .”是“ subject to”的縮寫，表示“滿足于 ……”。因此，上述模型的含義是：在給定的條件限制下，求使得目標(biāo)函數(shù) z達(dá)到最大時(shí) x1， x2的取值。 ?在 Excel電子表格中建立線性規(guī)劃模型 ?用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ?在用電子表格建立數(shù)學(xué)模型 （ 這里是一個(gè)線性規(guī)劃模型 ） 的過程中 ， 有三個(gè)問題需要得到回答： （ 1） 要作出的決策是什么 ？ （ 決策變量 ） （ 2） 在作出這些決策時(shí) ， 有哪些約束條件 ？（ 約束條件 ） （ 3） 這些決策的目標(biāo)是什么 ？ （ 目標(biāo)函數(shù) ） ? 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 （如果 “ 工具 ” 菜單中沒有 “ 規(guī)劃求解 ” 選項(xiàng)，請(qǐng)參見 SOLVER文件夾下的 “ Excel規(guī)劃求解工具的安裝說(shuō)明 .doc”） 在用 Excel的 “ 規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ， 為 單元格命名 能使線性規(guī)劃問題的電子表格模型更加容易理解 。 主要表現(xiàn)在兩個(gè)方面： （ 1） 在公式中使用名稱使人們 更容易理解公式的含義 ； （ 2） 在 “ 規(guī)劃求解參數(shù) ” 對(duì)話框中使用名稱使人們 更加容易理解線性規(guī)劃模型的含義 。 所以 ， 一般給跟公式和模型有關(guān)的四類單元格命名 。 例如：在例 表格模型中 ， 單元格命名如下： （ 1） 數(shù)據(jù)單元格 ：?jiǎn)挝焕麧?rùn) （ C4:D4） 、 可用工時(shí) （ G7:G9） ； （ 2） 可變單元格 ：每周產(chǎn)量 （ C12:D12） ； （ 3） 輸出單元格 ：實(shí)際使用 （ E7:E9） ； （ 4） 目標(biāo)單元格 ：總利潤(rùn) （ G12） 。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃結(jié)束！