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