[學(xué)習(xí)]對(duì)偶理論及靈敏度分析

1、對(duì)偶理論及靈敏度分析,（一）基本要求1、了解對(duì)偶問(wèn)題的特點(diǎn)，熟悉互為對(duì)偶問(wèn)題之間的關(guān)系2、掌握對(duì)偶理論及其性質(zhì)3、掌握對(duì)偶單純形法4、掌握限制常數(shù)和價(jià)值系數(shù)、約束條件系數(shù)的變化對(duì)原最優(yōu)解的影響5、掌握增加新變量和增加新約束條件對(duì)原最優(yōu)解的影響，并求出相應(yīng)因素靈敏度的范圍6、了解影子價(jià)格的經(jīng)濟(jì)意義（二）重點(diǎn) 1、對(duì)偶單純形法2、靈敏度分析（三）難點(diǎn)靈敏度分析,對(duì)偶理論對(duì)偶單純形方法靈敏度分析,對(duì)偶理論

2、及靈敏度分析,對(duì)偶理論,對(duì)偶問(wèn)題概念：任何一個(gè)線性規(guī)劃問(wèn)題都有一個(gè)伴生的線性規(guī)劃問(wèn)題，稱為其“對(duì)偶”問(wèn)題。對(duì)偶問(wèn)題是對(duì)原問(wèn)題從另一角度進(jìn)行的描述，其最優(yōu)解與原問(wèn)題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問(wèn)題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。,問(wèn)題的導(dǎo)出,,問(wèn)題的導(dǎo)出,,,假設(shè)有客戶提出要求，購(gòu)買工廠所擁有的工時(shí)和材料，為客戶加工

3、別的產(chǎn)品，由客戶支付工時(shí)費(fèi)和材料費(fèi)。那么工廠給工時(shí)和材料制訂的最低價(jià)格應(yīng)是多少，才值得出售工時(shí)和材料 ?,問(wèn)題的導(dǎo)出,,,出賣資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利; 約束價(jià)格應(yīng)該盡量低，這樣，才能有競(jìng)爭(zhēng)力; 目標(biāo)價(jià)格應(yīng)該是非負(fù)的,問(wèn)題的導(dǎo)出,,用y1和y2分別表示工時(shí)和材料的出售價(jià)格,總利潤(rùn)最小 min W=3y1+9y2保證A產(chǎn)品利潤(rùn) y1+y2≥2 保證B產(chǎn)品利潤(rùn)

4、 y1+4y2≥3 保證C產(chǎn)品利潤(rùn) y1+7y2≥3 售價(jià)非負(fù) y1≥0 y2≥0,問(wèn)題的導(dǎo)出,,問(wèn)題的導(dǎo)出,,對(duì)偶問(wèn)題的定義,,對(duì)稱形式的對(duì)偶問(wèn)題,對(duì)偶問(wèn)題的定義,,對(duì)稱形式的對(duì)偶問(wèn)題,或,對(duì)偶問(wèn)題的定義,對(duì)偶問(wèn)題的特點(diǎn)：若原問(wèn)題目標(biāo)是求極大化，則對(duì)偶問(wèn)題的目標(biāo)是極小化，反之亦然原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣極大化問(wèn)題

5、的每個(gè)約束對(duì)應(yīng)于極小化問(wèn)題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束。,對(duì)偶問(wèn)題的定義,非對(duì)稱形式對(duì)偶問(wèn)題的處理等式約束的線性規(guī)劃問(wèn)題如下：（1）先將等式約束條件分解為兩個(gè)不等式約束條件,對(duì)偶問(wèn)題的定義,（2）按對(duì)稱形式變換關(guān)系寫出它的對(duì)偶問(wèn)題,整理得,對(duì)偶問(wèn)題的定義,,由此可見，yi不受正負(fù)限制。將yi代入上述線性規(guī)劃問(wèn)題，得到對(duì)偶問(wèn)題為；,,,,,對(duì)偶問(wèn)題的定義,一般線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題,,,對(duì)偶問(wèn)題的定義,一般

6、線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題可歸納如下對(duì)應(yīng)關(guān)系：,對(duì)偶問(wèn)題的寫出,例1標(biāo)準(zhǔn)型對(duì)偶問(wèn)題,對(duì)偶問(wèn)題的寫出,例2,例 max Ζ=2x1+x2+3x3+x4 s.t. x1+x2+x3+x4≤5 2x1-x2+3x3 =-4 x1 -x3+x4 ≥1 x1

7、≥0,x2,x4無(wú)約束,x3 ≤0,min ω=5y1-4y2+y3 s.t. y1+2y2+y3 ≥2 y1-y2 =1 y1+3y2-y3 ≤3 y1 +y3 =1 y1≥0，y2無(wú)約束， y3 ≤0,其對(duì)偶問(wèn)題為,,對(duì)偶問(wèn)題的寫出,練習(xí)寫出對(duì)

8、偶問(wèn)題,max Ζ=x1-x2+5x3-7x4 s.t. x1+3x2-2x3+x4=25 2x1 +7x3 +2x4 ≥ -60 2x1 +2x2 -4x3 ≤ 30 x4 ≤10

9、 -x4 ≤5 x1, x2 ≥0, x3 ,x4無(wú)約束,練習(xí),max Ζ=x1-x2+5x3-7x4 s.t. x1+3x2-2x3+x4=25 2x1 +7x3+2x4 ≥ -60 2x1 +2x2 -4x

10、3 ≤ 30 x4 ≤10 -x4 ≤5 x1, x2 ≥0, x3 ,x4無(wú)約束,對(duì)偶問(wèn)題的基本性質(zhì),,（1）對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題。,(P),(D),對(duì)偶問(wèn)題的基本性質(zhì),（2）弱對(duì)偶性若互為對(duì)偶

11、的線性規(guī)劃分別有可行解 則其相應(yīng)的目標(biāo)函數(shù)值滿足,,,,,對(duì)偶問(wèn)題的基本性質(zhì),,（3）無(wú)界性若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。,對(duì)偶問(wèn)題的基本性質(zhì),（4） 最優(yōu)性準(zhǔn)則定理若X和Y分別是互為對(duì)偶的線性規(guī)劃的可行解 ，且使CX=Yb，則X和Y分別是相應(yīng)線性規(guī)劃問(wèn)題的最優(yōu)解,,,,,,,對(duì)偶問(wèn)題的基本性質(zhì),（5）對(duì)偶定理若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且此時(shí)目標(biāo)函數(shù)值相等。,證明：設(shè)

12、 是原問(wèn)題的最優(yōu)解，它對(duì)應(yīng)的基矩陣為B，則必定所有檢驗(yàn)數(shù)：,令 ，則,即 是對(duì)偶問(wèn)題的可行解所以對(duì)偶問(wèn)題的目標(biāo)值,而 是原問(wèn)題的最優(yōu)解，其目標(biāo)函數(shù)取值為：,由最優(yōu)性準(zhǔn)則定理知， 是對(duì)偶問(wèn)題的最優(yōu)解。,（6）互補(bǔ)松馳性(松緊定理) ：若 ，?分別是(P),(D)問(wèn)題的可行解，那么 ,?為最優(yōu)解的充要條件是： ?XS=0,YS =0

13、 (即若 Ai ?i=0 Ai =bi 0 ?Pj=Cj 0 ?Pj>Cj => j=0),對(duì)偶問(wèn)題的基本性質(zhì),,,?XS=0,YS =0,原問(wèn)題第i個(gè)約束方程是等式約束,若原問(wèn)題第i個(gè)約束方程是不等式約束,例1.已知下列線性規(guī)劃問(wèn)題 max Ζ=x1+2x2+3x3+4x4

14、 s.t. x1+2x2+2x3+3x4≤20 2x1+x2+3x3+2x4≤20 xj≥0, j=1,2,3,4已知其對(duì)偶問(wèn)題的最優(yōu)解為y1=1.2,y2=0.2運(yùn)用對(duì)偶理論找出原問(wèn)題的最優(yōu)解,[解]其對(duì)偶問(wèn)題為 min ω=20y1+20y2 s.t. y1+2y2≥1 2y1+y2≥2

15、 2y1+3y2≥3 3y1+2y2≥4 y1,y2≥0,,,,,,,,,,,,(1.2,0.2),.,.,y1,互補(bǔ)松馳性(松緊定理),,已知對(duì)偶問(wèn)題的最優(yōu)解 y1=1.2, y2=0.2,因y1>0,y2>0。所以x5=x6=0，即原問(wèn)題為等式約束,互補(bǔ)松馳性(松緊定理),將y1=1.2,y2=0.2代入對(duì)偶問(wèn)題的約束

16、條件，得 y3≠0,y4≠0,所以x1=x2=0,min ω=20y1+20y2 s.t. y1+2y2- y3 =1 2y1+y2- y4=2 2y1+3y2- y5=3 3y1+2y2- y6=4 y1,y2≥0,互補(bǔ)松馳性(松緊定理),x1=x2=0 x1

17、+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20,即 x1=x2=0，x3=4,x4=4 ∴原問(wèn)題的最優(yōu)解為(0,0,4,4)T,max Ζ=x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x4≤20 2x1+x2+3x3+2x4≤20 xj≥0, j=1,2,3,4,互補(bǔ)松馳

18、性(松緊定理),（7）原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解.,對(duì)偶問(wèn)題的基解,YS1為對(duì)應(yīng)原問(wèn)題中基變量XB的剩余變量，YS2是對(duì)應(yīng)原問(wèn)題中非基變量XN的剩余變量。,對(duì)偶問(wèn)題的基解,例.max Ζ=x1+4x2+3x3 s.t. 2x1+2x2+x3≤4 x1+2x2+2x3≤6 xj≥0,對(duì)偶問(wèn)題為 min ω=4y1+6y2

19、 s.t. 2y1+y2≥1 2y1+2y2≥4 y1+2y2≥3 y1,y2≥0,對(duì)偶問(wèn)題的基解,對(duì)偶問(wèn)題的基本解為y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,對(duì)偶問(wèn)題的基解,X4X5,由原問(wèn)題的最終表可知， y1=1,y2=1(最優(yōu)解)， ys1

20、=2，ys2=0，ys3=0,其最終表為,對(duì)偶問(wèn)題的基解,X2X3,在單純形法的每步迭代中，目標(biāo)函數(shù)取值z(mì)=CBB-1b，和檢驗(yàn)數(shù)CN-CBB-1N中都有乘子Y=CBB-1，那么Y的經(jīng)濟(jì)意義是什么?,設(shè)B是｛max z=CX｜AX≤b，X≥0｝的最優(yōu)基，則 z*=CBB-1b=Y*b 。對(duì)z求偏導(dǎo)數(shù)，得,影子價(jià)格,變量yi*的經(jīng)濟(jì)意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。,yi*的值代表

21、對(duì)第i種資源的估價(jià)-影子價(jià)格,這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為“影子價(jià)格”。影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣掉?？梢娪白觾r(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。,影子價(jià)格,,,,,從原始問(wèn)題最優(yōu)表求影子價(jià)格,當(dāng)B是原問(wèn)題的最優(yōu)基時(shí)，Y=CBB-1就是影子價(jià)格向量。,初始表,最優(yōu)表

22、,影子價(jià)格,y1=5/3, y2=1/3 即工時(shí)的影子價(jià)格為5/3，材料的影子價(jià)格為1/3。如果目前市場(chǎng)上材料的價(jià)格低于1/3，則企業(yè)可以購(gòu)進(jìn)材料來(lái)擴(kuò)大生產(chǎn)，反之可以賣掉部分材料。 如果有客戶以高于5/3的價(jià)格購(gòu)買工時(shí)，則可以出售一些工時(shí)。,對(duì)偶單純形法,對(duì)偶單純形法并不是求解對(duì)偶問(wèn)題解的方法，而是利用對(duì)偶理論求解原問(wèn)題的解的方法。,根據(jù)對(duì)偶問(wèn)題的對(duì)稱性，單純形表的迭代過(guò)程也可以反過(guò)來(lái)進(jìn)行，即保持對(duì)偶問(wèn)題的解始終是基本可行解

23、（即C-CBB-1A≤0），而使原問(wèn)題從基本非可行解迭代到基本可行解，從而使原問(wèn)題和對(duì)偶問(wèn)題同時(shí)得到最優(yōu)解。這種單純形表的應(yīng)用方法稱之為對(duì)偶單純形法。,對(duì)偶單純形法的計(jì)算步驟如下：,(1) 根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算。 若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。(2) 確定換出變量按min｛(B-1b)i｜(B-1b)i

24、＜0＝(B-1b)l對(duì)應(yīng)的基變量xl為換出變量。,對(duì)偶單純形法,(3)確定換入變量在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無(wú)可行解，停止 計(jì)算。若存在αlj＜0 (j=1,2,…，n), 計(jì)算,按θ規(guī)則所對(duì)應(yīng)的列的非基變量xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍為可行解。(4) 以αlk為主元素，按原單純形法在表中進(jìn)行迭代運(yùn)算，得到新的計(jì)算表。 重復(fù)步驟(1)～(4)。,

25、對(duì)偶單純形法,對(duì)偶單純形法舉例,例 用對(duì)偶單純形法求解：,,,,,,,對(duì)偶單純形法舉例,,,,,,,對(duì)偶單純形法舉例,,,最優(yōu)解為y1=5/3,y2=1/3, 最優(yōu)值Z=-8,Wmin=8,,對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足: ① 單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）； ② 變量取值可有負(fù)數(shù)（非可行解）。注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單

26、純形表。,對(duì)偶單純形法,例. min Ζ=3x1+4x2+5x3 s.t. x1+2x2+3x3≥5 2x1+2x2+x3≥6 x1,x2,x3≥0,[解] 問(wèn)題化為 max W=-3x1-4x2-5x3 s.t. -x1-2x2-3x3+x4 =-5 -2x1-2x2-x3 +x5=-6

27、 x1,x2,x3,x4,x5≥0,對(duì)偶單純形法練習(xí),所以最優(yōu)解為x1=1,x2=2,x3=0，Ζmin=11,對(duì)偶單純形法練習(xí),,xj,,,,,,,,,對(duì)偶單純形法的適用范圍： 適合于解如下形式的線性規(guī)劃問(wèn)題,在引入剩余變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便。,對(duì)于有些線性規(guī)劃模型，如果在開始求解時(shí)不能很快使所

28、有檢驗(yàn)數(shù)非正，最好還是采用單純形法求解。因?yàn)?，這樣可以免去為使檢驗(yàn)數(shù)全部非正而作的許多工作。從這個(gè)意義上看，可以說(shuō)，對(duì)偶單純形法是單純形法的一個(gè)補(bǔ)充。除此之外，在對(duì)線性規(guī)劃進(jìn)行靈敏度分析中有時(shí)也要用到對(duì)偶單純形方法，可以簡(jiǎn)化計(jì)算。,靈敏度分析,在生產(chǎn)計(jì)劃線性規(guī)劃問(wèn)題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，C代表企業(yè)產(chǎn)品的市場(chǎng)狀況 在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)由線性規(guī)劃的最優(yōu)解和最優(yōu)值決

29、定。,在實(shí)際生產(chǎn)過(guò)程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計(jì)劃還是不是最優(yōu)，如果不是，則最優(yōu)解如何變化，這就是靈敏度分析。 如果不是，應(yīng)該如何修訂原來(lái)的最優(yōu)計(jì)劃。更進(jìn)一步，為了防止在各類狀況發(fā)生時(shí)，來(lái)不及隨時(shí)對(duì)其變化作出反應(yīng)，即所謂“計(jì)劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時(shí)，應(yīng)當(dāng)作出什么樣的反應(yīng)。,

30、靈敏度分析,靈敏度分析,當(dāng)系數(shù)A，b，C發(fā)生改變時(shí)，目前最優(yōu)基是否還最優(yōu)？目前的最優(yōu)解是否還最優(yōu)？ 為保持目前最優(yōu)基或最優(yōu)解還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？假設(shè)每次只有一種系數(shù)變化①目標(biāo)函數(shù)系數(shù)C變化 a、基變量系數(shù)發(fā)生變化； b、非基變量系數(shù)發(fā)生變化；②右端常數(shù)b變化③技術(shù)系數(shù)A發(fā)生變化 a、增加一個(gè)變量 b、增加一個(gè)約束,靈敏度分析,若B是最優(yōu)基，則最優(yōu)表形式如下,,★靈敏

31、度分析總是在最優(yōu)表上進(jìn)行,靈敏度分析,例 線性規(guī)劃,,,,,靈敏度分析,例 線性規(guī)劃,,,,靈敏度分析,例 線性規(guī)劃,3-2*（-1）-3*2=-1,,,,,,,,當(dāng)aij,bi,cj中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化？如何求解新的最優(yōu)解？,價(jià)值系數(shù)C的改變,a、價(jià)值系數(shù)CN （非基變量的價(jià)值系數(shù)）發(fā)生改變,C3,C3-4,如果C3>4,則目前解不再是最優(yōu)解,應(yīng)該用單純形方法繼續(xù)求解,否則解不

32、變。即對(duì)于C3而言,使最優(yōu)解不變的條件是C3≤4。,,價(jià)值系數(shù)C的改變,,價(jià)值系數(shù)CN發(fā)生改變,,,5,價(jià)值系數(shù)C的改變,b、價(jià)值系數(shù)CB （基變量的價(jià)值系數(shù))發(fā)生改變,C1-3,1-4/3C1,1/3C1-1,C1-3 ≤0, 1-4/3C1≤0, 1/3C1-1≤0 ¾ ≤C1≤3若C1<3/4 則x4進(jìn)基，x1出基若3< C1 則x3或x5進(jìn)基，x2出基,,價(jià)值系

33、數(shù)C的改變,價(jià)值系數(shù)CB發(fā)生改變,,,1/2,1/2,,價(jià)值系數(shù)C的改變,價(jià)值系數(shù)CB發(fā)生改變,,,資源數(shù)量b變化的分析,右端常數(shù)b1的改變范圍,b1,4b1/3-3,3-b1/3,9/4≤b1 ≤9,-3-5b1/3,,資源數(shù)量b變化的分析,右端常數(shù)b1發(fā)生改變,,,2,,資源數(shù)量b變化的分析,右端常數(shù)b1發(fā)生改變,,,12,例.線性規(guī)劃問(wèn)題 max Ζ=-x2+3x3-2x5 s.t.

34、 x1+3x2-x3 +2x5 =7 -2x2+4x3+x4 =12 -4x2+3x3 +8x5+x6 =10 xj≥0,資源數(shù)量b變化的分析,,B=[P2,P3,P6],要使最優(yōu)基不變，求b2的變動(dòng)范圍,,要保持最優(yōu)基不變

35、，則 -14/3≤b2≤34,若b2超出此范圍，則b<0 可用對(duì)偶單純形法繼續(xù)求解,例上題中，若令b2增加Δb2=30,則,將上式結(jié)果反映到最終表中，得下表,資源數(shù)量b變化的分析,求右端常數(shù)b2改變范圍,b2,4-b2/3,b2/3-1,3≤b2 ≤12,-b2/3-5,練習(xí),技術(shù)系數(shù)A發(fā)生變化的分析,a、增加一個(gè)變量 若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利

36、潤(rùn)，單件資源消耗量時(shí)，可以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗(yàn)數(shù)行也可以由與其它列相同的方法計(jì)算得到。 若檢驗(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)解。,,,,增加一個(gè)變量,,,例.某工廠計(jì)劃生產(chǎn)A,B,C三種產(chǎn)品，需要甲,乙兩種資源。資源限量、每種產(chǎn)品的單位利潤(rùn)和單位產(chǎn)品的資源消耗量如下表所示，試確定

37、使利潤(rùn)最大的生產(chǎn)計(jì)劃。,練習(xí)：,[解]以x1,x2 ,x3分別表示A,B,C三種產(chǎn)品的產(chǎn)量，則該問(wèn)題的線性規(guī)劃模型如下：,max Ζ=2x1+3x2+x3s.t. 1/3x1+1/3x2+1/3x3≤1 1/3x1+4/3x2+7/3x3≤3 x1,x2,x3≥0,引入松馳變量，可得初始單純形表,最終單純形表為,假設(shè)這個(gè)工廠研制了一種新產(chǎn)品D，單位新產(chǎn)品D所需耗用的甲乙兩種資源分別為1/2和1/2

38、，新產(chǎn)品的利潤(rùn)為4元，問(wèn)應(yīng)怎樣調(diào)整生產(chǎn)計(jì)劃？,max Ζ=2x1+3x2+x3s.t. 1/3x1+1/3x2+1/3x3≤1 1/3x1+4/3x2+7/3x3≤3 x1,x2,x3≥0,P6’=B-1P6=,技術(shù)系數(shù)A發(fā)生變化的分析,b、增加一個(gè)約束為提高產(chǎn)品質(zhì)量，要增加一道加工工序，即會(huì)給原問(wèn)題增加一個(gè)約束條件。若把目前的最優(yōu)解代入新增加的約束，能滿足約束條件，

39、則說(shuō)明該增加的約束對(duì)最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計(jì)劃的實(shí)施。若當(dāng)前最優(yōu)解不滿足新增加的約束，則應(yīng)把新的約束添到原問(wèn)題的最優(yōu)表內(nèi)新的一行中去，用對(duì)偶單純形方法來(lái)進(jìn)行迭代，求出新的最優(yōu)解。,,,技術(shù)系數(shù)A發(fā)生變化的分析,例 增加約束,將新的約束條件引入松馳變量后，寫入最終單純形表，并把XB,XS 的系數(shù)列向量化為單位向量，再求解。,,,技術(shù)系數(shù)A發(fā)生變化的分析,增加約束,,,技術(shù)系數(shù)

40、A發(fā)生變化的分析,c、A中某列向量的變化（1）如果系數(shù)矩陣A中某一列向量Pj發(fā)生了變化，且其對(duì)應(yīng)的變量xj為非基變量，那么Pj的變化只影響最終表中的檢驗(yàn)數(shù)σj。若 Pj變?yōu)镻jˊ，則σj=cj-CBB-1Pjˊ如果σj ≤0，則說(shuō)明Pj變換后并不影響當(dāng)前解；如果σj＞0，則說(shuō)明Pj變換后影響到當(dāng)前解，需要求出最終表中第j列的新數(shù)據(jù)B-1Pjˊ填入最終表第j列，然后以xj為進(jìn)基變量繼續(xù)迭代，直到得到最優(yōu)解。,技

41、術(shù)系數(shù)A發(fā)生變化的分析,（2）如果系數(shù)矩陣A中發(fā)生變化的列向量Pj為基變量對(duì)應(yīng)的向量，則Pj變化后不僅影響變量xj的檢驗(yàn)數(shù)，而且影響到最終表中Pj對(duì)應(yīng)的向量也不再是單位列向量，即B和B-1都要變，這時(shí)要求出最終表中xj列的數(shù)，并通過(guò)迭代使該列恢復(fù)單位列向量，再根據(jù)恢復(fù)后的狀態(tài)予以處理。例 分析原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。以第1章例1為例，若原計(jì)劃生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)系數(shù)向量變?yōu)镻1

42、′=(2,5,2)T，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有什么影響?,技術(shù)系數(shù)A發(fā)生變化的分析,同時(shí)計(jì)算出x1′的檢驗(yàn)數(shù)為 c1′-CBB-1P1′ =4-(1.5,0.125,0)(2,5,2)T=0.375將以上計(jì)算結(jié)果填入最終表x1‘的列向量位置.得下表。,解 把改進(jìn)工藝結(jié)構(gòu)的產(chǎn)品Ⅰ看作產(chǎn)品Ⅰ′，設(shè)x1′為其產(chǎn)量。于是在原計(jì)算的最終表中以x1′代替x1，計(jì)算對(duì)應(yīng)x1′的列向量。,表 2-1