運(yùn)籌學(xué)課件2012

1、適用專業(yè)：信息管理 授課教師：張鳳玲,運(yùn) 籌 學(xué),課程回顧,線性規(guī)劃問題靈敏度分析,1）C CN 影響對(duì)應(yīng)的某個(gè)非基變量檢驗(yàn)數(shù) CB 影響所有非基變量檢驗(yàn)數(shù) 2）b 影響基變量取值 最優(yōu)基 最優(yōu)解,本次授課內(nèi)容,增加一個(gè)變量 增加一個(gè)約束 技術(shù)系數(shù)A發(fā)生變化,課程回顧,1、單純形法小結(jié) 2、線性規(guī)劃應(yīng)用,本次授課內(nèi)容,線性規(guī)劃問題靈敏度分析 價(jià)值系數(shù) 資源常數(shù),課程回顧,一、什么樣的問題可以建立線性規(guī)劃模型？,一般講，一個(gè)經(jīng)濟(jì)、管理問題凡滿足以下條件時(shí)，才能建立線性規(guī)劃模型 （1）要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)； （2）存在著多種方案； （3）要求達(dá)到的目標(biāo)是在一定的約束

2、條件下實(shí)現(xiàn)的，這些約束條件可用線性等式或不等式來描述。,二、建立模型的步驟,（1）設(shè)變量 （2）定目標(biāo) （3）列約束,課程回顧,添加松弛變量，構(gòu)造單位矩陣 添加人工變量 1）大M法人工變量不能夠影響目標(biāo)函數(shù)，必須取0 用M放大人工變量的影響 2）兩階段法 對(duì)人工變量構(gòu)造新的目標(biāo)函數(shù)，使人工變量的系數(shù)為-1,迭 代 運(yùn) 算 1、用非基變量替換基變量 2、對(duì)主元素行（第l行） 令bi/ aikbl;alj/alk ajl 3、對(duì)主元素列（第k列） 令1 alk;0 其它元素 4、表中其它行列元素 令aij-ali/alkaik aij bi-bl/alkaik bi,添加松弛變量、人工變量 列出初

3、始單純形表,計(jì)算非基變量 各列的檢驗(yàn)數(shù)J,所有J0,基變量中有非 零的人工變量,某非基變量 檢驗(yàn)數(shù)為零,唯一 最優(yōu)解,對(duì)任一J 0 有aik0,令KmaxJ ,對(duì)所有aik 0計(jì)算 ibi/ aik 令lmini xl為換出變量 aik為主元素,無界解,無可行解,無窮多最優(yōu)解,是,否,否,是,否,是,是,否,第三章靈敏度分析,3.1靈敏度分析的含義 1、意義 A代表企業(yè)的技術(shù)狀況 B代表企業(yè)的資源狀況 C代表企業(yè)產(chǎn)品市場(chǎng)狀況 決策者 預(yù)先了解各因素變化時(shí)的反應(yīng),在實(shí)際生產(chǎn)過程中，不斷變化,2、靈敏度分析的類型,目標(biāo)函數(shù)中價(jià)值系數(shù)C的變化（基變量價(jià)值系數(shù)變化；非基變量價(jià)值系數(shù)變化） 右端資源常數(shù)

4、b變化 增加一個(gè)變量 增加一個(gè)約束 技術(shù)系數(shù)A發(fā)生變化,第三章 靈敏度分析,3.2 價(jià)值系數(shù)C發(fā)生改變,1）當(dāng)CN中某個(gè)Cj發(fā)生變化時(shí)，只影響xj的檢驗(yàn)數(shù)，若cj的變化滿足j(cj-zj)0，則目前解還是最優(yōu)；否則就不是最優(yōu)，繼續(xù)單純形迭代就可以求得新的最優(yōu)解。 若不影響原最優(yōu)解，分析Cj變化范圍,例：對(duì)于下例問題，討論c3范圍,1、價(jià)值系數(shù)C發(fā)生改變,2）當(dāng)CB中某個(gè)Ci發(fā)生變化時(shí)，則會(huì)影響所有非基變量的檢驗(yàn)數(shù)，若ci的變化滿足N0，則目前解還是最優(yōu)；否則就不是最優(yōu)，繼續(xù)單純形迭代就可以求得新的最優(yōu)解。 最優(yōu)解不變的情況下，CB的變化范圍,例：對(duì)于下題中，討論C1在什么范圍內(nèi)變化，問題的最優(yōu)

5、解不變,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,c1-3,CB,XB,b,j(cj-zj),c1,c1,-1,-5/3,-1/3,3c1-3,4,5,0,0,0,c13,C13/4,c13,當(dāng)3/4c13時(shí)，最優(yōu)解不變。,習(xí)題,已知右側(cè)的線性規(guī)劃問題用單純形法求解得最終單純形表如下表所示：,試分析： (1)目標(biāo)函數(shù)中變量x3的系數(shù)變?yōu)?，最優(yōu)解是什么？ (2)目標(biāo)函數(shù)中變量x1和x2的系數(shù)在什么范圍內(nèi)變動(dòng)時(shí)最優(yōu)解不變？,3.3 右端資源常數(shù)b發(fā)生改變,當(dāng)b中某個(gè)分量bi發(fā)生改變時(shí)，將影響

6、所在基變量的取值XB=B-1b。若bi的變化仍滿足B-1b0，則目前基還是最優(yōu)基。最優(yōu)解為X=(B-1b,0)；否則，若bi的變化使B-1b中某些分量小于0，則目前基成了不可行基?？梢杂脤?duì)偶單純形法迭代求得新的最優(yōu)解。,例：在例1中，討論b1改變的情況（b1在什么范圍內(nèi)變化時(shí)，當(dāng)前最優(yōu)基不變）,解：設(shè)b變?yōu)?b1,9)T,若B1b0則,解得9/4b19,習(xí)題,已知右側(cè)的線性規(guī)劃問題用單純形法求解得最終單純形表如下表所示：,0,-2,-1,-3,0,0 1,x5,1 1,x4,1 1,x3,1 3,x2,1 0,6 10,x1 x5,x1,cj-zj,試說明分別發(fā)生下列變化時(shí)，最優(yōu)解改變么？ (

7、a)目標(biāo)函數(shù)變?yōu)閙axZ=2x1+3x2+x3 (b)約束條件右端項(xiàng)由(6,4)T變?yōu)?3,4)T,課程小結(jié),線性規(guī)劃問題合理配料問題 靈敏度分析 1）C CN 影響對(duì)應(yīng)的某個(gè)非基變量檢驗(yàn)數(shù) CB 影響所有非基變量檢驗(yàn)數(shù) 2）b 影響基變量取值 最優(yōu)基 最優(yōu)解,3.3 增加一個(gè)變量,若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)， 是否會(huì)影響原定生產(chǎn)計(jì)劃？,若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn) 則在知道新產(chǎn)品的單位利潤C(jī)n+1， 消耗量Pn+1=(a1n+1,a2n+1,amn+1)T時(shí)， 可以在最優(yōu)表中補(bǔ)充一列，可以由B-1Pn+1得到，而檢驗(yàn)數(shù)行可以由n+1=Cn+1-CBB-1Pn+1計(jì)算得到。

8、若n+10，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則當(dāng)n+10時(shí)，則應(yīng)以xn+1進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。,例：在例1中，討論增加產(chǎn)品D時(shí)的情況，假設(shè)產(chǎn)品D的單位利潤為5（千元），工時(shí)消耗和材料消耗為（2,3）T,解：,6=c6-CBB-1P6=5-(2,3) =2/30,5,x6,5/3,1/3,2/3,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/3,CB,XB,b,j(cj-zj),0,x5,5/3,1/3,2/3,3/5,0,-3/

9、5,4/5,-1/5,-1/5,1,11/5,-3/5,2/5,3/5,9/5,x6,x2,5,3,1,0,-2/5,0,-3/5,-11/5,-1/5,0, ,習(xí)題,7、已知右側(cè)的線性規(guī)劃問題用單純形法求解得最終單純形表如下表所示：,試說明分別發(fā)生下列變化時(shí)，新的最優(yōu)解是什么？ (3)約束條件右端項(xiàng)由(1,3)T變?yōu)?2,3)T (4)增加一個(gè)新的變量x6，P6= (1,1)T，C6=7,3.4 增加約束條件,外部環(huán)境變化 生產(chǎn)原材料變化 條件變化 出現(xiàn)新的約束條件,增加一個(gè)約束,把目前的最優(yōu)解代入新增加的約束， 能滿足約束條件，則說明該增加的約束條件對(duì)最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計(jì)劃

10、的實(shí)施。 若當(dāng)前最優(yōu)解不滿足新增加的約束，則應(yīng)把新的約束添加到原問題的最優(yōu)表內(nèi)新的一行中去，用對(duì)偶單純形方法來進(jìn)行迭代，求出新的最優(yōu)解。,例：在例1的問題中增加約束2x1+2x2+x35，討論最優(yōu)解的情況,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/3,CB,XB,b,j(cj-zj),解：將當(dāng)前最優(yōu)解X=(1,2,0)T代入約束條件中，得 21+22+065,在新增加的約束條件中引入松弛變量得2x1+2x2+x3+x6=5 加入最優(yōu)表得,2,2,1,0,0,1,0,x

11、6,0,0,5,x6,0,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,CB,XB,b,j(cj-zj),0,x6,0,0,2,2,1,0,0,1,5,x6,0,0,2,3,-8/3,2/3,1,3,0,0,-1,-2,0,1,-1,0,0,-1,-5/3,-1/3,0,2,3,0,x1,x2,x4,1/3,13/6,1/2,1,0,-5/3,0,-1/3,0,1,13/6,0,1/3,2/3,-1/6,0,0,1,0,1/2,-1/2,0,0,-1/6,0,-1/3,-5/6,1,5/6, ,企業(yè)某

12、種工藝改進(jìn)，原材料消耗發(fā)生變化 生產(chǎn)計(jì)劃如何調(diào)整,3.5 A中的元素發(fā)生變化,N中Pj改變的情形：與增加一個(gè)變量時(shí)完全相同，只需要認(rèn)為新增加一個(gè)產(chǎn)品，其利潤與xj的利潤相同為cj，而其消耗系數(shù)Pn+1等于變化后的Pj，則可以直接用處理增加一個(gè)變量的方法進(jìn)行處理。,例：對(duì)例1中的線性規(guī)劃，若a23由7改變?yōu)?，試討論其最優(yōu)解的情況。,-1,2,4/3,-1/3,1,0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,Cj-zj,XB,CB,b,x4,x5,0,0,3,0,2,3,0,3,9/4,Cj-zj,初始單純形表,最終單純形表,解：虛擬一種產(chǎn)品D，其

13、單位利潤為c6=3，資源消耗為P6(1，5)T，則,6C6-CBB-1P6-1/30,由此可知，最優(yōu)解不變。,試討論a23在什么范圍變化時(shí)最優(yōu)解不變？,CB,XB,b,初始單純形表,最終單純形表,問題一：若原計(jì)劃生產(chǎn)產(chǎn)品I的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)系數(shù)向量變?yōu)镻1(2,5,2)T，每件利潤為4元。試分析對(duì)原計(jì)劃有什么影響？,問題二：若原計(jì)劃生產(chǎn)產(chǎn)品I的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)系數(shù)向量變?yōu)镻1(4,5,2)T，每件利潤為4元。試問該廠應(yīng)如何安排最優(yōu)生產(chǎn)方案？,解：把改進(jìn)工藝的產(chǎn)品I看作產(chǎn)品I，設(shè)x1為其產(chǎn)量，計(jì)算在最終表中x1對(duì)應(yīng)的列向量B-1P1和檢驗(yàn)數(shù)1。,1 0 0,5

14、/4 1/2 3/8,0,x1,x1,3/8,5/4 -7/2 11/8,-21/8,2、已知線性規(guī)劃問題用單純形法計(jì)算時(shí)得到的初始單純形表及最終單純形表如下所示，請(qǐng)將表中空白處數(shù)字填上。,習(xí)題,CB,XB,b,cj-zj,cj-zj,習(xí)題,6、已知右側(cè)的線性規(guī)劃問題用單純形法求解得最終單純形表如下表所示：,0,-2,-1,-3,0,0 1,x5,1 1,x4,1 1,x3,1 3,x2,1 0,6 10,x1 x5,x1,cj-zj,試說明分別發(fā)生下列變化時(shí)，新的最優(yōu)解是什么？ (a)目標(biāo)函數(shù)變?yōu)閙axZ=2x1+3x2+x3 (b)約束條件右端項(xiàng)由(6,4)T變?yōu)?3,4)T (c)增添一

15、個(gè)新的約束x1+2x32,習(xí)題,7、已知右側(cè)的線性規(guī)劃問題用單純形法求解得最終單純形表如下表所示：,試說明分別發(fā)生下列變化時(shí)，新的最優(yōu)解是什么？ (1)目標(biāo)函數(shù)中變量x3的系數(shù)變?yōu)?； (2)目標(biāo)函數(shù)中變量x1和x2的系數(shù)在什么范圍內(nèi)變動(dòng)時(shí)最優(yōu)解不變？ (3)約束條件右端項(xiàng)由(1,3)T變?yōu)?2,3)T (4)增加一個(gè)新的變量x6，P6= (1,1)T，C6=7 (5)增添一個(gè)新的約束x1+2x2 +x34,例1.某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、三種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的A、B兩種原材料的消耗，如表1-1所示。,該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品、可獲利3元，問應(yīng)如何安排計(jì)劃使該工廠獲利最多？,表1-1,XB,CB,b,x4,x5,0,0,3,0,2,3,0,-3/4,7/4,1,0,3/4,1/4,0,1,-1/4,1/4,-9/4,0,5/4,0,-3/4,3/4,9/4,x4,x2,0,3,-1,2,4/3,-1/3,1,0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,3,9/4, ,1,9, ,Cj-zj,Cj-zj,Cj-zj,用單純形法求解下列問題,