數(shù)據(jù)模型——線性規(guī)劃-閱讀頁
2024-08-20 16:51本頁面
【正文】 1 1 1 0 5 2 1 3 1 0 2 1 1 4 1 1 迭 代 2 由于013 ???，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于 0的元素，所以取3x為入基變量。 注： 1 . 該算法在實(shí)際應(yīng)用中非常有效，被廣泛采用， 但在理論上不是多項(xiàng)式時(shí)間算法。 對(duì) 偶 理 論 ? 對(duì)偶規(guī)劃 ? 對(duì)偶理論 ? 對(duì)偶單純形算法 規(guī) 范 形 式 的 對(duì) 偶 規(guī) 劃 規(guī)范形式的線性規(guī)劃 ??????0..m i nxbAxtsxc ???????0,..m i nyxbIyAxtsxc 其對(duì)偶規(guī)劃為 ? )0,(),(..m a x??? cIAtsb?? ??????0..m a x???cAtsb 一般形式的對(duì)偶規(guī)劃 對(duì)于一般形式的線性規(guī)劃 通過把其轉(zhuǎn)化為標(biāo)準(zhǔn)形式同樣可以得到其對(duì)偶規(guī)劃為 ： ???????????????????????qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn, . . . ,2,1。0, . . . ,1。..m i n221122112211無限制????????????????mpiqjcAnqjcAtsbijjjj,...,1。,...,1。1226..215m i n5321432131jxxxxxxxxxtsxxj 其對(duì)偶規(guī)劃為 ?????????????????????00212605..2m a x2121212121??????????ts ???????????????????00212605..2m a x2121212121??????????ts ?????????????3,2,1。 定理 線性規(guī)劃的對(duì)偶規(guī)劃的對(duì)偶規(guī)劃是原始規(guī)劃。 定理 給定一個(gè)原規(guī)劃 和對(duì)偶規(guī)劃，則下面三種情況必有其一： 1. 都有最優(yōu)解 2. 都無可行解 3. 一個(gè)有可行解另一個(gè)無界 定理 若x和 ?分別是原規(guī)劃和對(duì)偶規(guī)劃的可行解，則 x和 ? 分別是原規(guī)劃和對(duì)偶規(guī)劃的最優(yōu)解的充要條件是， mibxa iii ,...,2,1。0)( ??? ?計(jì)算典式檢驗(yàn)數(shù) 否 算 法 過 程 初始正則解 檢查可行 是則停止 得最優(yōu)解 選出基變量 檢查 是否無可 行解 是則停止 否 無最優(yōu)解 選入基變量 靈 敏 度 分 析 ? 概況 ? 改變價(jià)值向量 ? 改變右端向量 概 況 ? 信息的不確定性 信息的變化： 價(jià)值向量 —市場(chǎng)變化 右端向量 —資源變化 系數(shù)矩陣 —技術(shù)進(jìn)步 認(rèn)知的誤差 ? 分析方法 靜態(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)解；否 則是 基可行解。 ????????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。由于新檢 驗(yàn)數(shù)仍然為負(fù)數(shù)，所以原最優(yōu)解依然是新問題的最優(yōu)解。 改變右端向量 基 本 思 想 bBb ??? ? 1 ， bcz B ??? ?0 如果 0??b 則原最優(yōu)解還是最優(yōu)解，否則利用對(duì) 偶單純形算法求解新問題。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃問題及其數(shù)學(xué)模型 ?例 1 某工廠要生產(chǎn)兩種新產(chǎn)品： 門 和 窗 。 而車間 1每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間為 4小時(shí) 、 車間 2為 12小時(shí) 、 車間 3為 18小時(shí) 。 而且根據(jù)經(jīng)市場(chǎng)調(diào)查得到的該兩種新產(chǎn)品的市場(chǎng)需求狀況可以確定 ， 按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去 。 因此 ， 該問題可以用 目標(biāo) 、 決策變量和約束條件 三個(gè)因素加以描述 。 例如決定企業(yè)經(jīng)營目標(biāo)的各產(chǎn)品的產(chǎn)量等 。 例如利潤最大 、 成本最小 等 。 如原材料供應(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 單位利潤（元） 300 500 （ 1） 決策變量 本問題的決策變量是每周門和窗的產(chǎn)量 。 （ 2） 目標(biāo)函數(shù) 本問題的目標(biāo)是總利潤最大 。 ?車間 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è)典型的 利潤最大化 的生產(chǎn)計(jì)劃問題。因此，上述模型的含義是：在給定的條件限制下，求使得目標(biāo)函數(shù) z達(dá)到最大時(shí) x1， x2的取值。 主要表現(xiàn)在兩個(gè)方面： （ 1） 在公式中使用名稱使人們 更容易理解公式的含義 ； （ 2） 在 “ 規(guī)劃求解參數(shù) ” 對(duì)話框中使用名稱使人們 更加容易理解線性規(guī)劃模型的含義 。 例如：在例 表格模型中 ， 單元格命名如下： （ 1） 數(shù)據(jù)單元格 ：?jiǎn)挝焕麧?（ C4:D4） 、 可用工時(shí) （ G7:G9） ； （ 2） 可變單元格 ：每周產(chǎn)量 （ C12:D12） ； （ 3） 輸出單元格 ：實(shí)際使用 （ E7:E9） ； （ 4） 目標(biāo)單元格 ：總利潤 （ G12
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1