運(yùn)籌學(xué)第6講 線性規(guī)劃的對(duì)偶理論和靈敏度分析2

1、運(yùn) 籌 學(xué)（Operations Research）上 海 海 事 大 學(xué) 20131009任課教師：鄧 偉郵 箱：影子價(jià)格影子價(jià)格1.影子價(jià)格的概念 考慮一對(duì)對(duì)稱形式的對(duì)偶規(guī)劃問題設(shè) 為對(duì)偶規(guī)劃(D)的最優(yōu)解，則稱 為規(guī)劃(P)的第i個(gè)約束對(duì)應(yīng)的影子價(jià)格(Shadow Price).注: 是對(duì)第i中資源(設(shè)備臺(tái)時(shí))的一種估價(jià)，這個(gè)價(jià)格不是市場(chǎng)價(jià)格，而是針對(duì)具體企業(yè)在一定時(shí)期內(nèi)存在的一種特殊價(jià)格，它蘊(yùn)含在求最大利潤(rùn)的生產(chǎn)計(jì)劃模型中。max( )0zCXAXbPXmin()0TTTwb YA YCDY*12(,)TmYyyy*iy*iy影子價(jià)格影子價(jià)格下面討論影子價(jià)格的幾種經(jīng)濟(jì)含義，這些經(jīng)濟(jì)含義

2、對(duì)于企業(yè)經(jīng)營(yíng)活動(dòng)分析是具有重要作用的。2.影子價(jià)格的經(jīng)濟(jì)含義(1)影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)。 根據(jù)現(xiàn)有資源的影子價(jià)格，對(duì)資源的使用有兩種考慮： 第一，是否將設(shè)備用于外加工或出租，若租費(fèi)高于某設(shè)備的影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租。 第二，是否將投資用于購買設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價(jià)低于某設(shè)備的影子價(jià)格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn)。影子價(jià)格影子價(jià)格(2)影子價(jià)格表明資源增加對(duì)總效益產(chǎn)生的影響。根據(jù)對(duì)偶定理，在最優(yōu)解的情況下，有關(guān)系式1122mmzfb yb yb y因此可以將 看作是 的函數(shù)，對(duì)z,1, 2,ib im,1,2,ib im求偏導(dǎo)數(shù)得到,1,2,i

3、izy imb這說明，如果右端常數(shù)bi增加一個(gè)單位，則目標(biāo)函數(shù)的增量將是,1,2,iy im根據(jù)這一含義，可以知道那種資源的增加可以給企業(yè)帶來較大的效益。影子價(jià)格影子價(jià)格注: 1.影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益，如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價(jià)格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。2.影子價(jià)格不是固定不變的，當(dāng)約束條件、利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格的經(jīng)濟(jì)含義是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超出了這個(gè)“一定范圍”時(shí)，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增加。影子價(jià)

4、格影子價(jià)格影子價(jià)格的應(yīng)用：例6.1 某外貿(mào)公司準(zhǔn)備購進(jìn)A1，A2。購進(jìn)每件產(chǎn)品A1，需要10元，占用5m3的空間，待每件A1賣出后，可獲純利潤(rùn)3元；購進(jìn)每件產(chǎn)品A2，需要15元，占用3m3的空間，待每件產(chǎn)品A2賣出后，可獲純利潤(rùn)4元。公司現(xiàn)有資金1400元，有430m3的倉庫空間可存放產(chǎn)品。根據(jù)這些條件，可以建立求最大利潤(rùn)的線性規(guī)劃模型：12121212max341015140053430,0zxxxxxxx x影子價(jià)格影子價(jià)格求解后，得到最優(yōu)單純形表：基變量 011/9-2/96010-1/151/35000-11/45-1/9-390最優(yōu)方案是，購進(jìn)兩種產(chǎn)品分別為50和60，公司的最大利潤(rùn)

5、是390元。影子價(jià)格影子價(jià)格現(xiàn)在公司有另外一筆資金585元，準(zhǔn)備用于投資。這筆資金如果用來購買產(chǎn)品A1，A2，當(dāng)然可以使公司獲得更多的利潤(rùn)；如果用來增加倉庫的容量，也可以使公司獲得更多的利潤(rùn)。這是因?yàn)椋a(chǎn)品A1，A2的單位利潤(rùn)不同，占據(jù)的空間也不同，由于倉庫容量增加了，可以使購買產(chǎn)品A1，A2的數(shù)量比例發(fā)生變化，仍有可能使公司的利潤(rùn)增加。下面利用影子價(jià)格來分析，應(yīng)如何進(jìn)行投資，使公司獲得更多的利潤(rùn)。影子價(jià)格影子價(jià)格由最優(yōu)表可看出，倉庫的影子價(jià)格y2=1/9，即增加1m3的倉庫空間，公司可多獲得利潤(rùn)1/9元?，F(xiàn)在已知，增加1m3的倉庫空間需要0.8元，也就是說，如果將投資用于增加倉庫空間，則每投

6、資0.8元，可多獲利潤(rùn)1/9元。即，每1元投資可多獲10/72元，近似為0.14元。再來看用于購買產(chǎn)品的資金的影子價(jià)格y2，由最優(yōu)表可看出，y1=11/45，即每增加1元購買產(chǎn)品，可多獲利潤(rùn)11/45元，近似為0.24元。經(jīng)過比較分析，應(yīng)將投資用于購買產(chǎn)品A1，A2，而不用于增加倉庫容量，這樣可獲得更多的利潤(rùn)。影子價(jià)格影子價(jià)格將585元進(jìn)行此投資之后，最大利潤(rùn)的增量為再這一增量值，可通過改變約束條件的新模型的求解結(jié)果，得到驗(yàn)證。新模型為：最優(yōu)解為x1=11,x2=125,即購買兩種產(chǎn)品分別為11件和125件。585y1=58511/45=143元12121212max3410151985534

7、30,0zxxxxxxx x影子價(jià)格影子價(jià)格將585元進(jìn)行此投資之后，最大利潤(rùn)的增量為再這一增量值，可通過改變約束條件的新模型的求解結(jié)果，得到驗(yàn)證。新模型為：最優(yōu)解為x1=11,x2=125,即購買兩種產(chǎn)品分別為11件和125件?？偫麧?rùn)為533元。利潤(rùn)增加量為533-390=143。兩者結(jié)果相同。585y1=58511/45=143元12121212max341015198553430,0zxxxxxxx x影子價(jià)格影子價(jià)格如果不按此決策進(jìn)行投資，而采用其他方案，其利潤(rùn)增加量只能比143少。例如，考慮在585元資金中，將510元用于購買產(chǎn)品A1，A2，將75元用于增加倉庫空間，75元可增空間為

8、93.75m3，得到的模型為：12121212max341015191053523.75,0zxxxxxxx x影子價(jià)格影子價(jià)格經(jīng)求解可知，此模型的最優(yōu)解為 x1=47.25,x2=95.85最大利潤(rùn)為525.15元，增量為525.15-390=135.15元。顯然小于143元。 對(duì)偶單純形法對(duì)偶單純形法對(duì)偶單純形法是求解原規(guī)劃的一種方法，它采用了單純形法和對(duì)偶的思想。 1.對(duì)偶單純形法的基本思想： 對(duì)偶單純形法從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，對(duì)偶單純形法的基本思想是：從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解(檢驗(yàn)數(shù)非正)，所以也可以說是從一個(gè)對(duì)偶可

9、行解出發(fā)，然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解(檢驗(yàn)數(shù)非正)，如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解。 對(duì)偶單純形法對(duì)偶單純形法注: 對(duì)偶單純形法在迭代過程中始終保持對(duì)偶解的可行性(即檢驗(yàn)數(shù)非正)，使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。 對(duì)偶單純形法對(duì)偶單純形法2.對(duì)偶單純形法的主要步驟 (1) 根據(jù)線性規(guī)劃的典式形式，建立初始對(duì)偶單純形表，此表對(duì)應(yīng)原規(guī)劃的一個(gè)基本解。此表要求：檢驗(yàn)數(shù)行各元素一定非正，原規(guī)劃的基本解可以有小于零的分量

10、。 (2)若基本解的所有分量皆非負(fù)。則得到原規(guī)劃的最優(yōu)解，停止計(jì)算；若基本解中有小于零的分量 ，并且 所在行各系數(shù) ，則原規(guī)劃沒有可行解，停止計(jì)算； 若 ，并且存在 ，則確定 為出基變量，并計(jì)算0lblb0lja0lb0lja lxmin|0jkljljlkaaa確定 為進(jìn)基變量。若有多個(gè) ，則選擇其中最小的進(jìn)行分析計(jì)算。kx0ib 對(duì)偶單純形法對(duì)偶單純形法若有多個(gè) ，則選擇其中最小的進(jìn)行分析計(jì)算。0ib 上面求最小值的式子稱為對(duì)偶 規(guī)則，它保證在經(jīng)過迭代后得到的新表中，檢驗(yàn)數(shù)行各元素非正。 (3)以 alk 為中心元素，按照與單純形法類似的方法，在表中進(jìn)行迭代計(jì)算，返回上一步。對(duì)偶單純形法對(duì)

11、偶單純形法例6.2 用對(duì)偶單純形法求解下面線性規(guī)劃 1212121212min323343632,0fxxxxxxxxx x解 引入松弛變量化為標(biāo)準(zhǔn)形，并在約束等式兩側(cè)同乘-1，得到1212312412512345max323343632,0zxxxxxxxxxxxx x x x x 對(duì)偶單純形法對(duì)偶單純形法松弛變量構(gòu)成基變量，上式即為典式形式，并且檢驗(yàn)數(shù)皆非正，因此可構(gòu)造初始對(duì)偶單純形表。 對(duì)偶單純形法對(duì)偶單純形法繼續(xù)迭代： 對(duì)偶單純形法對(duì)偶單純形法在最后的單純形表中，右側(cè)列各元素皆非負(fù)，所以得到原規(guī)劃的最優(yōu)解為X=(3/5,6/5,0,0,11/5)T。注: 用對(duì)偶單純形法求解此問題，只經(jīng)

12、過兩次迭代便得到了最優(yōu)解。如果仍然采用單純形法求解的話，在化成標(biāo)準(zhǔn)形式后，為得到初始基本可行解，需要加入3個(gè)人工變量，這樣，為了得到問題的最優(yōu)解，至少要迭代3次，讓人工變量出基，顯然，計(jì)算量將大大增加。對(duì)偶單純形法對(duì)偶單純形法例6.3 用對(duì)偶單純形法求解下面線性規(guī)劃12123124max221120,1,2,3,4jzxxxxxxxxxj 解 構(gòu)造對(duì)偶單純形表進(jìn)行迭代，從最后的表中可以看到，右側(cè)列元素有-20，并且-2所在行各元素解非負(fù)，因此，原規(guī)劃沒有可行解。對(duì)偶單純形法對(duì)偶單純形法對(duì)偶單純形法對(duì)偶單純形法3.對(duì)偶單純形法的適用范圍對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問題：11min,1,2,0,1,2,njjjnijjijjfc xa xb imxjn注1: 在引入松弛變量