現(xiàn)代企業(yè)運(yùn)籌學(xué)管理方案(完整版)
【正文】 4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 價(jià)值系數(shù) CN發(fā)生改變 C3 C34 如果 C34,則目前解不再是最優(yōu)解 ,應(yīng)該用單純形方法繼續(xù)求解 ,否則解不變。 ① 現(xiàn)行解最優(yōu)，但不唯一； ② 現(xiàn)行解不可行（指出哪個(gè)變量造成）； ③ 一個(gè)約束條件有矛盾； ④ 現(xiàn)行解是退化的基本可行解； ⑤ 現(xiàn)行解可行，但問題無有限最優(yōu)解； ⑥ 現(xiàn)行解是唯一最優(yōu)解； ⑦ 現(xiàn)行解可行，但將 x1取代 x6后，目標(biāo)函數(shù)能改進(jìn)。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。 ④ 主元變換 對(duì)偶單純形法舉例 例 2－ 6 用對(duì)偶單純形法求解： 21 93min yyW ?????????????????0,037342..21212121yyyyyyyyts2139。 其含議是在目前已給定的情況下，最優(yōu)目標(biāo)值隨資源數(shù)量變化的變化率； 其經(jīng)濟(jì)含義是為約束條件所付出的代價(jià)。 約束 ?價(jià)格應(yīng)該盡量低，這樣，才能有競爭力 。 對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問題的理論 ， 是線性規(guī)劃理論的重要內(nèi)容之一 。 最優(yōu)性準(zhǔn)則定理 定理 2－ 2 最優(yōu)性準(zhǔn)則定理 若 X和 Y分別是互為對(duì)偶的線性規(guī)劃的可行解 ， 且使 CX=Yb， 則 X和 Y分別是相應(yīng)線性規(guī)劃問題的最優(yōu)解 證明：由弱對(duì)偶定理可知 ， 對(duì)任意可行解有 ， CX≤Yb 因此對(duì)于 X和 Y也將分別有 CX≤Yb CX≤Yb 又因?yàn)? CX=Yb 故有 Yb ≤Yb CX≤CX 主對(duì)偶定理 定理 2－ 3 （ 主對(duì)偶定理 ） 若原始問題和對(duì)偶問題兩者均可行 ，則兩者均有最優(yōu)解 ， 且此時(shí)目標(biāo)函數(shù)值相同 。 由檢驗(yàn)數(shù)的計(jì)算方法可知： ? =C ?A 若 A中有單位子矩陣，則在最優(yōu)表中有： ijjc ?? ?? jji c ?? ?? CB XB cj 2 3 3 0 0 ? xj b x1 x2 x3 x4 X5 0 x4 3 1 1 1 1 0 3/1 0 x5 9 1 4 7 0 1 9/1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 對(duì)偶單純形法 對(duì)偶單純形法并不是求解對(duì)偶問題解的方法，而是利用對(duì)偶理論求解原問題的解的方法。即對(duì)于 C3而言 ,使最優(yōu)解不變的條件是 C3≤4。 討論題 ① 現(xiàn)行解最優(yōu)，但不唯一； ② 現(xiàn)行解不可行（指出哪個(gè)變量造成）； ③ 一個(gè)約束條件有矛盾； ④ 現(xiàn)行解是退化的基本可行解； ⑤ 現(xiàn)行解可行，但問題無有限最優(yōu)解； ⑥ 現(xiàn)行解是唯一最優(yōu)解； ⑦ 現(xiàn)行解可行，但將 x1取代 x6后，目標(biāo)函數(shù)能改進(jìn)。 ≤C1≤3 若 C13/4 則 x4進(jìn)基， x1出基 若 3 C1 則 x3或 x5進(jìn)基 ， x2出基 靈敏度分析 例 2－ 7 線性規(guī)劃 CB XB cj 1/2 3 3 0 0 ? xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 1/2 x1 1 1 0 1 4/3 1/3 3/4 3 x2 2 0 1 2 1/3 1/3 ∞ －Ｚ 13/2 0 0 5/2 1/3 5/6 價(jià)值系數(shù) CB發(fā)生改變 0 x4 3/4 3/4 0 3/4 1 1/4 3 x2 9/4 1/4 1 7/4 0 1/4 －Ｚ 27/4 1/4 0 9/4 0 3/4 靈敏度分析 例 2－ 7 線性規(guī)劃 CB XB cj 4 3 3 0 0 ? xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 4 x1 1 1 0 1 4/3 1/3 ∞ 3 x2 2 0 1 2 1/3 1/3 3/2 －Ｚ 10 0 0 1 13/3 1/3 價(jià)值系數(shù) CB發(fā)生改變 4 X1 3 1 1 1 1 0 0 X5 6 0 3 6 1 1 －Ｚ 12 0 1 1 4 0 靈敏度分析 例 2－ 7 線性規(guī)劃 右端常數(shù) b發(fā)生改變 CB XB cj 2 3 3 0 0 ? xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 b1 4b1/33 ?????????????????????????????????????????????3/3334931313134911111bbbbB3b1/3 9/4≤b1 ≤9 35b1/3 靈敏度分析 例 2－ 7 線性規(guī)劃 CB XB cj 2 3 3 0 0 xj b x1 x2 x3 x4 x5 0 x4 2 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1/3 1 0 1 4/3 1/3 3 x2 7/3 0 1 2 1/3 1/3 －Ｚ 19/3 0 0 1 5/3 1/3 右端常數(shù) b發(fā)生改變 0 X5 1 3 0 3 4 1 3 X2 2 1 1 1 1 0 －Ｚ 6 1 0 0 3 0 最小比值 1 1 靈敏度分析 例 2－ 7 線性規(guī)劃 CB XB cj 2 3 3 0 0 xj b x1 x2 x3 x4 x5 0 x4 12 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 13 1 0 1 4/3 1/3 3 x2 1 0 1 2 1/3 1/3 －Ｚ 23 0 0 1 5/3 1/3 右端常數(shù) b發(fā)生改變 2 X1 9 1 4 7 0 1 0 X4 3 0 3 6 1 1 －Ｚ 18 0 5 11 0 2 最小比值 5 靈敏度
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1