物流運(yùn)籌學(xué)(第10節(jié)-對偶單純形法).ppt

對偶單純形法,對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。 不是求解對偶問題的單純形法，而是在原始問題的單純形表中進(jìn)行對偶處理。,對偶單純形法原理,證明過程省略,對偶單純形法,找出一個DP的可行基,LP是否可行 （XB 0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個基本解,最優(yōu)解,是,否,循 環(huán),結(jié)束,不是求解對偶問題的單純形法，而是在原始問題的單純形表中進(jìn)行對偶處理。,即檢驗(yàn)數(shù)0,是否b0,用對偶單純形表求解條件： （1）找到檢驗(yàn)數(shù)0的對偶單純形表為初始單純形表。 （2）存在bj0,對偶單純形法,例2.9 用對偶單純形法求解：,解:（1）轉(zhuǎn)化為標(biāo)準(zhǔn)式。 （2）滿足對偶單純形法求解的基本條件,即檢驗(yàn)數(shù)0,存在至少一個Bj0,Ci 0,對偶單純形法,1. 確定出基變量：找出最小的檢驗(yàn)數(shù)，設(shè)為bl，它對應(yīng)的原問題的基變量即為換出變量。,2. 確定入基變量，,檢驗(yàn)數(shù)行,對偶單純形法,對偶單純形法,原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其對偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），W*= 72,對偶單純形法,找出一個DP的可行基,LP是否可行 （XB 0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個基本解,最優(yōu)解,是,否,循 環(huán),結(jié)束,不是求解對偶問題的單純形法，而是在原始問題的單純形表中進(jìn)行對偶處理。,即檢驗(yàn)數(shù)0,是否b0,用對偶單純形表求解條件： （1）找到檢驗(yàn)數(shù)0的對偶單純形表為初始單純形表。 （2）存在bj0,1. 確定出基變量：找出最小的檢驗(yàn)數(shù)，設(shè)為bl，它對應(yīng)的原問題的基變量即為換出變量。,2. 確定入基變量，,3. 基變換,作業(yè),2.11,線性規(guī)劃的對偶問題與靈敏度分析,線性規(guī)劃的對偶問題 對偶問題的基本性質(zhì) 影子價格 對偶單純形法 靈敏度分析 參數(shù)線性規(guī)劃,靈敏度分析,在生產(chǎn)計劃問題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計劃和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。 在實(shí)際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計劃，而在計劃實(shí)施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來的最優(yōu)計劃。更進(jìn)一步，為了防止在各類狀況發(fā)生時，來不及隨時對其變化作出反應(yīng)，即所謂“計劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時，應(yīng)當(dāng)作出什么樣的反應(yīng)。,靈敏度分析的步驟,靈敏度分析的步驟可歸納如下： 1.將參數(shù)的改變通過計算反映到最終單純形表上來。 2.檢查原問題是否仍為可行解。 3.檢查對偶問題是否仍為可行解。 4.按下表所列情況得出結(jié)論或決定繼續(xù)計算的步驟。,靈敏度分析,若B是最優(yōu)基，則最優(yōu)表形式如下,靈敏度分析總是在最優(yōu)表上進(jìn)行,靈敏度分析,當(dāng)系數(shù)A，b，C發(fā)生改變時，目前最優(yōu)基是否還最優(yōu)？ 為保持目前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？ 假設(shè)每次只有一種系數(shù)變化 目標(biāo)系數(shù)C變化 基變量系數(shù)發(fā)生變化； 非基變量系數(shù)發(fā)生變化； 右端常數(shù)b變化 增加一個變量 增加一個約束 技術(shù)系數(shù)A發(fā)生變化,靈敏度分析舉例,分析cj的變化 例2-7 在第一章例1的美佳公司例子中：（1）若家電的利潤降至1.5元/件，而家電的利潤增至2元/件時，美佳公司最優(yōu)生產(chǎn)計劃有何變化?,即美佳公司隨家電，的利潤變化應(yīng)調(diào)整為生產(chǎn)2件，生產(chǎn)3件。,（2）若家電的利潤不變，則家電的利潤在什么范圍內(nèi)變化時，該公司的最優(yōu)生產(chǎn)計劃將不發(fā)生變化？ 設(shè)家電的利潤為（1+）元，如下,為保證最優(yōu)解， -1/4+1/40， -1/2-3/2 0 解得-1/3 1 即家電的利潤c2的變化范圍應(yīng)滿足2/3 c2 2,靈敏度分析舉例,分析bi的變化 例2-8 在美佳公司的例子中：（1）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32h，分析公司最優(yōu)計劃的變化；,靈敏度分析舉例,靈敏度分析舉例,例2-8 （2）設(shè)設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變。 設(shè)調(diào)試工序每天可用能力為（5+）h，因有,最終單純形表中b列數(shù)字為,因b0時最優(yōu)基不變，故-11。 調(diào)試工序的能力應(yīng)在4h6h之間。,增加一個變量xj的分析 若企業(yè)在計劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤，單件資源消耗量時，可以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗(yàn)數(shù)行也可以由與其它列相同的方法計算得到。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。,例2-9 設(shè)美佳公司又計劃推出新型號的家電，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時間分別為3h、4h、2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對該公司的最優(yōu)生產(chǎn)計劃有何影響。 設(shè)生產(chǎn)x6件家電，有c6=3，P6=（3，4，2）T,靈敏度分析舉例,增加一個變量xj的分析,靈敏度分析舉例,最優(yōu)生產(chǎn)計劃應(yīng)為每天生產(chǎn)7/2件家電，51/4件家電。,靈敏度分析舉例,分析參數(shù)aij的變化,例2-10 在美佳公司的例子中，若家電每件需設(shè)備A,B和調(diào)試工時變?yōu)?h、4h、1h，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計劃。 設(shè)生產(chǎn)工時變化后的新家電的生產(chǎn)量為x2，其中：,靈敏度分析舉例,原問題和對偶問題均為非可行解,上表中第二階段第一行的約束為： x3+4x4-24x5=-9 -x3-4x4+24x5+x6=9 替換后重新得表：,靈敏度分析舉例,最優(yōu)生產(chǎn)計劃為每天生產(chǎn)11/4臺家電，15/8臺家電,靈敏度分析舉例,增加一個約束條件 在企業(yè)的生產(chǎn)過程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺的某種資源變成為緊缺資源，對生產(chǎn)計劃造成影響。 若把目前的最優(yōu)解代入新增加的約束，能滿足約束條件，則說明該增加的約束對最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計劃的實(shí)施。 若當(dāng)前最優(yōu)解不滿足新增加的約束，則應(yīng)把新的約束添到原問題的最優(yōu)表內(nèi)新的一行中去，用對偶單純形方法來進(jìn)行迭代，求出新的最優(yōu)解。,增加一個約束條件,靈敏度分析舉例,例2-11 設(shè)家電，經(jīng)調(diào)試后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。家電每件需環(huán)境試驗(yàn)3h，家電每件需2h，又環(huán)境試驗(yàn)工序每天生產(chǎn)能力為12h。試分析增加該