1、5 對偶問題的經(jīng)濟(jì)解釋 影子價(jià)格,(P)的最終單純形表中松弛變量的檢驗(yàn)數(shù)對應(yīng)(D)的最優(yōu)解。,當(dāng)某約束條件的右端常數(shù)增加一個(gè)單位時(shí)（假設(shè)原問題的最優(yōu)基不變），原問題的目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。,+yi*(bi+1),=Y*b+yi* =Z*+yi*,第I種資源的影子價(jià)格是第i個(gè)約束條件的右端常數(shù)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)增加的數(shù)量,X(3)=(4，2，0，0, 4)T， z3 =14,經(jīng)濟(jì)意義：在其它條件不變的情況下， 單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。,影子價(jià)格,X*=(30,35,0,50,0)T, Z*=135,y1*=3/4 y2*=0, y3*=1/4,經(jīng)濟(jì)意義：在其它條件不

2、變的情況下， 單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。,影子價(jià)格的意義,(1)影子價(jià)格客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。 如果某一資源在系統(tǒng)內(nèi)供大于求（即有剩余），其影子價(jià)格就為零。如果某一資源是稀缺的（即相應(yīng)約束條件的剩余變量為零）,則其影子價(jià)格必然大零。影子價(jià)格越高，資源在系統(tǒng)中越稀缺。 (2)影子價(jià)格是對系統(tǒng)資源的一種優(yōu)化估價(jià)，只有當(dāng)系統(tǒng)達(dá)到最優(yōu)時(shí)才能賦予該資源這種價(jià)值，因此也稱最優(yōu)價(jià)格。 (3)影子價(jià)格的取值與系統(tǒng)狀態(tài)有關(guān)。系統(tǒng)內(nèi)部資源數(shù)量、技術(shù)系數(shù)和價(jià)格的任何變化，都會(huì)引起影子價(jià)格的變化，它是一種動(dòng)態(tài)價(jià)格。 (4)如果考慮擴(kuò)大生產(chǎn)能力，應(yīng)該從影子價(jià)格高的設(shè)備入手。,6 對偶單純形

3、法,保持對偶可行性，逐步改進(jìn)主可行性，求解主問題。,當(dāng)b有負(fù)分量，A中有一明顯初始對偶可行基(檢驗(yàn)數(shù)均非正)，因而易得一初始解時(shí)，可用對偶單純形法求解。,設(shè)B為一個(gè)基,基本解,X（0）為基本可行解的條件？,B-1b0,X（0）為最優(yōu)解的條件？,原,原始可行性條件,原始最優(yōu)性條件,令Y=CBB-1，代入原始最優(yōu)性條件，YAC,對偶可行性條件,例 用對偶單純形法求解,單純形法,大M 法,剩余變量、人工變量,用（-1）乘不等式兩邊，再引入松弛變量。,先選出基變量 后選進(jìn)基變量,原問題，符合原始最優(yōu)性條件，但不可行,最優(yōu)解 X*=（7，0，4，0）T Z*=-7,例6 用對偶單純形法求解,（P）,1

4、- 4/3 - -,-1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1,- 8/5 - - 2,2/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5, , ,對偶單純形法的一個(gè)應(yīng)用： 增加一個(gè)約束條件的分析 。,檢查原最優(yōu)解是否滿足新的約束條件 滿足，則原最優(yōu)解仍為最優(yōu)解，否則，2。 2 將約束方程帶到最優(yōu)單純形表中。,7 靈敏度分析,系數(shù)bi、cj 、aij 變化，最優(yōu)解的最優(yōu)性、可行性是否變化？,系數(shù)在什么范圍內(nèi)變化，最優(yōu)解或最優(yōu)性不變？,如何求新的最優(yōu)解？,7

5、.1 靈敏度分析的原理,是最優(yōu)解，則,可行性條件,基變量cB,增加新變量,系數(shù)aij的變化，要視aij對應(yīng)的變量是基變量或非基變量而定。,XB=B-1(b+b)，其中b=(0, br ,0,0)T 只要XB0，最終表中檢驗(yàn)數(shù)不變（b變化，不影響檢驗(yàn)數(shù)），則最優(yōu)性不變，但最優(yōu)解的值發(fā)生變化, XB成為新的最優(yōu)解.,B-1(b+b)= B-1b+ B-1b0,新的最優(yōu)解允許范圍是:,當(dāng)某一個(gè)資源系數(shù)br 發(fā)生變化，亦即br= br +br ，其他系數(shù)不變，這樣最終的單純形表中原問題的解相應(yīng)地變化為,1、資源系數(shù)br的靈敏度變化分析,B-1的第r列,x1, x5, x2是基變量，從而可得基B,例：求

6、第一章例題中當(dāng)?shù)诙€(gè)約束條件b2變化范圍b2。,可得 b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16 由公式知b2變化范圍-8,16, 顯然b2變化范圍8,32,例題: 將上面例題進(jìn)行實(shí)際應(yīng)用。每臺(tái)設(shè)備臺(tái)時(shí)的影子價(jià)格為1.5元。若該廠又從別處抽出4臺(tái)時(shí)用于生產(chǎn)兩種產(chǎn)品，求這時(shí)該廠生產(chǎn)兩種產(chǎn)品的最優(yōu)方案。,B=（x1 x5 x2),將這個(gè)結(jié)果放到最終表中得,解：先計(jì)算B-1b,表中b列中有負(fù)數(shù)，即解答列有負(fù)數(shù)，故可用對偶單純形法求最優(yōu)解。 最優(yōu)解見下表,最優(yōu)生產(chǎn)方案應(yīng)改為第一種產(chǎn)品4件，第二種產(chǎn)品3件，獲利z=17元。,（1）當(dāng)cj是非基底變量xj的系數(shù)，檢驗(yàn)數(shù)

7、為,或,當(dāng)cj變化cj后，檢驗(yàn)數(shù)應(yīng)要小于或等于零，即,2、目標(biāo)函數(shù)中價(jià)值系數(shù)C的變化,（2）當(dāng)cr是基底變量xr的系數(shù)，即crCB，cr變化cr后，有,最優(yōu)解不變,cr的變化范圍,例8： 仍以第一章例1的最終表為例。設(shè)基變量x2的系數(shù)c2變化c2，在原最優(yōu)解不變的條件下，確定c2的變化范圍。,解：這時(shí)最終計(jì)算表為,可見 c2-1.5/0.5; c2-0.125/(-0.125) 故c2的變化范圍: -3c21 即x2的價(jià)值系數(shù)c2可在0,4之間變化，不影響原最優(yōu)解。,已知線性規(guī)劃問題,最優(yōu)單純形表,練習(xí)1,3 aij的變化分析,(1). aij 為非基變量的系數(shù),只影響xj的檢驗(yàn)數(shù)，從而影響最

8、優(yōu)性。,例: 第一章例1，增加一種新產(chǎn)品，它的技術(shù)系數(shù)是(2，6，3)T，利潤系數(shù)是5。問該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？,解：設(shè)新產(chǎn)品的產(chǎn)量為x3 (對于原最優(yōu)解來說是非基變量)。因,故應(yīng)生產(chǎn)產(chǎn)品。,x3進(jìn)基,在最終表中的系數(shù)是：,原最終表成為：,用單純形法求解得：,(2). aij為基變量系數(shù),基變化，影響最優(yōu)性、可行性。,例: 第一章例1，若生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)有改進(jìn)，其技術(shù)系數(shù)變?yōu)椋?， 5 ，2)T，利潤系數(shù)為4，試分析對生產(chǎn)計(jì)劃有什么影響？,解： 設(shè)產(chǎn)品產(chǎn)量為x1(產(chǎn)品產(chǎn)量在原最優(yōu)解中是基變量)。計(jì)算,將和所求系數(shù)填入原最終表的x1列位置，得,將x1的系數(shù)列向量變換為單位向量,上表中

9、假如對偶可行，主不可行，則用對偶單純形法求新解；假如主對偶均不可行，要加入人工變量，用單純形法繼續(xù)解。,注意：,例11 假設(shè)例10的產(chǎn)品的技術(shù)系數(shù)向量為 p1=（4，5，2），而每件獲利仍為4元。試該廠應(yīng)如何安排最優(yōu)生產(chǎn)方案？,練習(xí)2 在練習(xí)1中，如果新增加產(chǎn)品，其目標(biāo)系數(shù)為100，消耗系數(shù)為（9，3.5） 是否應(yīng)該生產(chǎn)該產(chǎn)品,例2-14 已知線性規(guī)劃問題,其最優(yōu)單純形表為,現(xiàn)增加新約束 求新問題的最優(yōu)解,解：增加約束后的新問題為,原問題的最優(yōu)解為,帶入新增加的約束,故X*不滿足新增加的約束條件，因此引入松弛變量x7后，新增加的約束條件變?yōu)?將第1行的3倍，第3行的（-6）倍分別加到第4行上，

10、使基變量x1、 x5、 x3 、x7的系數(shù)列向量構(gòu)成單位矩陣，即,得到下表,在表中 故當(dāng)前解不是可行解，用對偶單純形法求解，x7是換出變量，A4為主行又,p6是主列， 是主元素,新問題的最優(yōu)解,要注意的是追加約束條件后，新問題的目標(biāo)函數(shù)值總不會(huì)比原問題的目標(biāo)函數(shù)值好（為什么）,線性規(guī)劃綜合例題,某工廠使用5種生產(chǎn)方式，生產(chǎn)A、B、C三種產(chǎn)品，有關(guān)每種方法的批產(chǎn)量數(shù)據(jù)如表1、資源消耗如表2。有一合同要求至少生產(chǎn)A110單位。,表1 每種方法的批產(chǎn)量,表2 資源消耗,列出利潤最大化的線性規(guī)劃模型,(1)求線性規(guī)劃問題的最優(yōu)解； (2)求對偶問題的最優(yōu)解； (3)當(dāng)b3= -150時(shí)最優(yōu)基是否發(fā)生變

11、化？為什么？ (4)求C2的靈敏度范圍; (5)如果x3的系數(shù)由1，3，5變?yōu)?，3，2最優(yōu)基是否改變？若改變求新的最優(yōu)解 ; (6)假定新增決策變量x8，且p8=(2，5，3)，C8=4，原最優(yōu)解是否改變？為什么？,線性規(guī)劃綜合例題,某工廠使用5種生產(chǎn)方式，生產(chǎn)A、B、C三種產(chǎn)品，有關(guān)每種方法的批產(chǎn)量數(shù)據(jù)如表1、資源消耗如表2。有一合同要求至少生產(chǎn)A110單位。,表1 每種方法的批產(chǎn)量,表2 資源消耗,1.若第2種生產(chǎn)方法的成本提高到21元，問是否改變最有解？,2.現(xiàn)每工時(shí)的工資為3元，若加班，另附加費(fèi)用1.5元/h，加班是否使利潤增加？,3.若只要另付加班費(fèi)0.3元/h，加班是否有利？如果有利，可加班多少小時(shí)？,4.若購置1臺(tái)新機(jī)器，購價(jià)為30萬元，每天可以增加8h，機(jī)器可以用5年，每年250工作日，問是否有利？,5.問增加3臺(tái)新機(jī)器是否有利？,6.公司按合同每天至少供應(yīng)110單位A，若變更合同減少供應(yīng)量，是否有利？,7.第4種生產(chǎn)方法的成本要降低到什么程度才能增加利潤？,8.若第2 種方法的批量不能超過20次，最優(yōu)解有無變化？若不能超過15次呢？,求：（1）線性規(guī)劃問題的最優(yōu)解； （2）求對偶