管理運(yùn)籌學(xué)(講義)A-2

1、第二章對偶理論與靈敏度分析(duality theory and sensitivity analysis)第一節(jié)單純形法的矩陣描述用矩陣描述單純形法求解過程比較簡便，也有助于加深對單純形法 的理解。設(shè)有線性規(guī)劃問題，用矩陣形式表示，max z = cxax <bx >0在約朿條件中加入松弛變量xs =(e+i，£+2，£+j，將其化成標(biāo)準(zhǔn)型：max z = cx + 0 ax+i xs=bx>0,xs >0式中i為m xm的單位陣運(yùn)用單純形法求解，需將標(biāo)準(zhǔn)型中系數(shù)矩陣、變量和目標(biāo)函數(shù)中的 系數(shù)向量改寫成分塊形式：系數(shù)矩陣(兒/)改寫為(b, n)兩

2、塊，b為基矩陣；變量(x、改寫為/ 、xb,xb為對應(yīng)于基矩陣b的基變量;s丿pn丿目標(biāo)函數(shù)中系數(shù)向量(c, 0)改寫為(q, cq，c 為對應(yīng)于基變 量的系數(shù)向量；一(x 目標(biāo)函數(shù)：z 二 cx+0xs =(cb cn) b =cbxb+cnxn(x和丿(x、 約束條件：ax+i xs=(b n) b =bxb+nxn =bxn)所以，改寫后的線性規(guī)劃問題為，maxz = cbxb + cnxn(1)bxb + nxn=b下面按照單純形法求解原理，對改寫后的線性規(guī)劃模型進(jìn)行分析：從(2)式中，可得出用非基變量表示基變量的表達(dá)式：xb=blb-blnxn(3)在(3)式中，令xn=o,可得到一

3、個基解乂 = i。丿再將(3)式代入(1)式，可得出用非基變量表示目標(biāo)函數(shù)的表達(dá)式：z = cb(bb-b-lnxn) + cnxn二cbb5(cn-cb b-' n)x n(4)令xn=o,可得目標(biāo)函數(shù)值，z = cbbb再對(3)和(4)進(jìn)行分析，又可得出：。在(4)式中，非基變量x”系數(shù)cn7 礦即為非基變量的檢驗數(shù)cr；v,基變量xr的檢驗數(shù)為0；這個非基變量檢驗數(shù)=cn-cbb'n與前一章提到的非基變量cfj = cj -zj, j = m+ !,"含義完全相同。在這個檢驗數(shù)b” = cn cbb-'n中，由于c”中對應(yīng)于xs的系數(shù)為0,所以，xs的

4、檢驗數(shù)為-cbb'x o另外，由于基變量的檢驗數(shù)為cb-cbb*",所以，所有變量的檢驗數(shù)都可用c - q礦1a和-cbb表示o從(3)式，確定換出變量的0規(guī)則，用矩陣可表示為,(滬以0=h_ia這里的0規(guī)則與前面介紹的0規(guī)則含義完全相同，在上一章介紹的 。規(guī)則為，0 - min 糾。0在上式中，(bs是向量礦的第i個分量，即亦(b“p)是礦”的第i個分量，即aik。用矩陣描述的單純形表。為用矩陣描述的單純形表，需要將上面(1)和(2)再進(jìn)行改寫，將非基變量乂何再分成兩塊(xm，xs),即bxb+nxni+ixs =b二xb + b-'nxn + bxs = bxb(

5、5)將(4)式移項后，得，-+鳳+%"+()心=0(6)將式代入式,得， z + (cn_cbb 一'n)xn、_cbb'xs =-cb 礦(7)用單純形表表示即為,xbxnrhsxnxsib-'n礦1bf0cncbb-'n-cbb-cbbxb這是迭代后的單純形表，從表中可以看出，各部分?jǐn)?shù)字都與基矩陣b 的逆矩陣3"有關(guān)，而逆矩陣對應(yīng)于松弛變量的位置。將(5)式和(7)式合并，用矩陣表示即為, 廠_ 7、0 i b-'nbx、j 0 cn-cbb'n -cbb-xbxnbxbj-cm 丿第二節(jié)改進(jìn)單純形法從上一章介紹的表格單純

6、形法可以看出，用該法求解線性規(guī)劃問題 時，每迭代一次都要把整個單純形表計算一遍，實際上，從上一張單純 形表變換到下一張時，即迭代一次有許多計算是不必要的，所需重新計 算的數(shù)據(jù)僅僅是檢驗數(shù)、主元列元素、當(dāng)前的基變量及b列數(shù)據(jù)等，一 些與基變換運(yùn)算暫時無關(guān)的列向量沒有必要計算。因此，按此法用計算機(jī)求解線性規(guī)劃問題，特別是大型線性規(guī)劃問 題時，計算效率非常低。為了提高計算效率，人們對表格單純形法進(jìn)行 了改進(jìn)提出了適合于計算機(jī)計算的改進(jìn)單純形法。改進(jìn)單純形法有兩個特點(diǎn)：在迭代過程屮，有許多數(shù)據(jù)計算都依 賴于基矩陣b的逆矩陣所以，在迭代過程中，只要求出基矩陣的b 的逆矩陣滬，檢驗數(shù)cn-cbb-'

7、;n、基可行解屮的基變量b»b、日標(biāo)函 數(shù)值cbblb及0值等數(shù)據(jù)都可以從線性規(guī)劃問題的初始數(shù)據(jù)直接求出。在進(jìn)行了基變換后，如何用最少的計算量來求出新的基矩陣的逆矩陣 就成了該法的關(guān)鍵。如果每次迭代都必須從原始數(shù)據(jù)來計算計 算量是很大的。改進(jìn)單純形法能夠在相鄰的兩次迭代中，用上一次基矩陣的b的逆矩陣3"直接計算出新的基矩陣的目的逆矩陣大大簡化了計算。改進(jìn)單純形法的計算步驟：1根據(jù)給出的線性規(guī)劃問題，在加入松弛變量或人工變量后，得到初 始基變量，求出初始可行基b的逆矩陣和初始基可行解，5坷比丿< 0 >再計算單純形乘子y = cbb 計算非基變量x”的檢驗數(shù)乙，c

8、n=cn-cbb 'n；如果<0, 即每一個非基變量對應(yīng)的檢驗數(shù)都小于零，則表示已得到了最優(yōu)解, 停止計算。如果還存在（jj <0,jen,轉(zhuǎn)入下一步；3 根據(jù)max（bj勺0）=6,對應(yīng)的非基變量血為換人變量，再計算jbpk （礦九為進(jìn)基列向量，以為兀所對應(yīng)的原始系數(shù)列向量）； 如果b-'pg，原問題無界解，停止計算，否則，轉(zhuǎn)入下一步;4 根據(jù)&規(guī)則，求出(bg對應(yīng)的基變量嗎為換出變量，同時，得到一組新的基變量和新的基 矩陣5 計算新的基矩陣的逆矩陣先要構(gòu)造一個初等變換矩陣e,再利用bf1 = eb1計算出卯，再求出bjb、y = cbibj ；6重復(fù)2至

9、5步驟，直至求出最優(yōu)解。在兩次相鄰的迭代中，如何用用上一次基矩陣b的逆矩陣b 直接 計算出新的基矩陣的目的逆矩陣而不用新基的原始數(shù)據(jù)來計算逆矩 陣即0由于在兩次相鄰的迭代中，上一步迭代的基矩陣在基變換后， 即用非基變量忑取代基變量西，得到下一步迭代的新基矩陣目，兩個基 矩陣相比僅差一列的系數(shù)列向量，因此，可以直接根據(jù)上一步的基矩陣b 的逆矩陣b '和換人變量兀的系數(shù)列向量計算出新基矩陣昌“。在相鄰的兩次迭代中，設(shè)上一步迭代的可行基b為，b = (pl,p2,-,pl_l,pl,pl+l,-,pm)經(jīng)過基變換后，得到一新的可行基目為，場=(門，02,，門-1，幾，門+1，門”)則迭代后所

10、得到新的可行基目的為，b-=elkb 其中,1e】k =第/列aik / alka2k /1 / a,lk一 amk 1 a，lk乞稱為初等變換矩陣。證明：因為b'b =（b'p,b'p2，b'pi，b'pi，b'pz，b'pj = i,即<1>0 b 1p2 =p、1，blpm =90©01已知,b pk =（aik，q爲(wèi)，°爲(wèi)），乂因為，礦e=（礦i】,礦0，礦1/一1，肝礦1/+1，滬幾）第/列心a2kaik_qmk根據(jù)矩陣知識，第/列一 ak lalka2k / aik(b鳥尸=elk =1 / a

11、lk amk /a，lkb = elkb具體構(gòu)造初等變換矩陣乞：在確定了換人變量兀和換出變量兀/后， 在與基同階的單位陣中用進(jìn)基列向量3-1幾替換與換出變量所在列相對 應(yīng)的單位列向量，其中進(jìn)基列向量幾中的元素必取倒數(shù)，其余元素用元素如去除，并取相反數(shù)，這樣就得到初等變換矩陣e/例1用改進(jìn)單純形法求解下列線性規(guī)劃問題。max z = 2x+ 3x2兀i + 2x2 < 84x < 16 s.t. <4x2 < 12x2 > 0解：將上述問題化為標(biāo)準(zhǔn)型，即max z = 2兀+ 3x2 + ox3 + 0x4 + ox5兀1 + 2x2 + x3 = 8 4兀+巾=1

12、6s.t. <4x2 + % = 12 x7>0 ) = 1,2,5取初始可彳亍基=（3，4, "5）=八 計算得，b, = i初始基可行解，x肌=血 = （8,16,12）7'單純形乘子,匕=cb°bf =（0,0,0）計算非基變量檢驗數(shù)，%嚴(yán)cn（）-cb（）b：n（嚴(yán)cno-y（n5 2、=(2,3) - (0,0,0) 4 0= (2,3),(0 4丿按照max(b/勺0) = 3,所以，確定勺為換人變量。計算進(jìn)基列向量，b：卩2 = pi = (2,0,4)7確定換出變量，按照&規(guī)則,6 = min(b()' p2)i(3加0對

13、應(yīng)的基變量兀5為換出變量。所以，得到新基為b產(chǎn)(p3，p“2)。_1 0 -1/2'_1 0 -1/2-e=0 1 0，即=e.b-1 =0 1 0_0 01/4 _0 01/4 _第1次迭代：p2 = p2 = (2,0,4)r-1/2t 8求新的基可行解,1 0心1=眄= 0 10 00 161/4 £12= (2,16,3/1單純形乘子,y= “即=(0,0,3) 000 -1/210=(0,03/4)01/4計算非基變量檢驗數(shù)，c7n=cn_cbbjn=cn_yn= (2,0)-(0,0,3/4) 40、0 =(2-3/4),對應(yīng)的非基變量x為換人變量。1丿1 0計算

14、進(jìn)基列向量，p = 0 10 0-1/2t1=(1，4,0)丁,1/40確定換出變量，按照&規(guī)則,> 0> = min=2第2次迭代：對應(yīng)的基變量d為換出變量。所以，得到新基為b2=(pl9p49p2)o 1 0 o' 1 0 o-_1 0 -1/2-e=-4 1 0,b； = e2b =-4 1 00 1 0_ 0 0 1_ 0 0 1_0 01/4 _bp=(l,4,0r1-40-1/221/4求新的基可行解，x b2=b'b =_ 10-1/21-412_ 001/4 j= (2,8,3/81612單純形乘子,y2 = cb2b =(2,0,3)1-4

15、0-1/221/4= (2,0,1/4)計算非基變量檢驗數(shù)，ctn2=cn2-y2n2= (0,0)-(2,0-1/4)<1040、0 =(-2,1/4),對應(yīng)的非基變量兀5為換人變量。1丿計算進(jìn)基列向量，b?卩5 = 10-1/2-o-4120001/4 _1= (l/221/4)r確定換出變量，按照&規(guī)則,0 = min(咕"2 1/4=4對應(yīng)的基變量兀為換出變量。所以，得到新基為b3=(p,p5，p2)。第3次迭代： 巧1必=(-1/2,2,1/4卩_11/40_11/40_ 10-1/2-e3 =01/2001/20-4120-1/81_0-1/81001/4

16、_1-21/21/41/2-1/8求新的基可行解,_ 11/40_8-21/21161/2-1/80_12= (4,4,2/x b廠 b?b =1/401/21 =(3/2,1/&0)-1/8 00單純形乘子，=(2,0,3) -21/2計算非基變量檢驗數(shù)，3=53-em0、= (0,0)-(3/2j/&0) 0 1 =(-3/2,-1/8)，非基變量全為非負(fù),得到最優(yōu)解。第三節(jié)對偶問題的提出在線性規(guī)劃中，任何線性規(guī)劃問題都具有對偶性，即任何一個線性 規(guī)劃問題都存在有與它相對應(yīng)的另外一個線性規(guī)劃問題，如果把前一個 線性規(guī)劃問題稱為原問題，后一個相對應(yīng)的線性規(guī)劃問題就稱為它的對

17、偶問題，互為對偶的原問題和對偶問題是相對的。線性規(guī)劃的對偶理論是專門研究原問題與對偶問題之間的關(guān)系及其 解的性質(zhì)的理論，是線性規(guī)劃理論的重要組成部分。在線性規(guī)劃中，對偶理論有著很重要的應(yīng)用。女口，根據(jù)對偶理論， 提出了另一個求解線性規(guī)劃問題的方法對偶單純形法；應(yīng)用對偶理論可 以對影子價格進(jìn)行分析，在經(jīng)濟(jì)管理中有著重要的意義；在靈敏度分析 以及運(yùn)輸問題的算法屮等都有著應(yīng)用。下曲從一個實際問題引出對偶問題。在第一章例1中，我們討論了 一個工廠制訂生產(chǎn)計劃的線性規(guī)劃問題。現(xiàn)在假設(shè)工廠的決策者決定自 己不再生產(chǎn)產(chǎn)品，而將全部可以利用的資源出租，收取出租費(fèi)，這樣， 工廠的決策者就得考慮如何給這些資源確定

18、一個合理的價格。顯然，決策者在確定收費(fèi)價格時，考慮的原則是，一是出租資源所 收回的費(fèi)用應(yīng)不低于自己生產(chǎn)獲得的利潤，否則，就不出租，自己生產(chǎn); 二是定價又不能太高，耍使對方愿意接受。所以，合理的定價應(yīng)在保證自己的收入不低于自己生產(chǎn)獲得的利潤 的前提下，自己的收入即對方的支出盡可能小，這樣自己不會吃虧，對 方也能接受。否則，雙方就不能成交。假設(shè)y八乃、力分別為三種資源的收費(fèi)單價，已知每生產(chǎn)一件產(chǎn)品l 需要1個設(shè)備臺時和4噸原材料a,為不使工廠收益減少，出租生產(chǎn)一件 產(chǎn)品的資源所獲得的收入應(yīng)不低于生產(chǎn)一件產(chǎn)品的利潤，即有力+4乃同樣地，出租生產(chǎn)產(chǎn)品ii的資源所獲得的收入也應(yīng)不低于自己生產(chǎn) 產(chǎn)品的利潤

19、，2% +4" »3該廠所有資源都出租，所得的總收入（即對方的總支出）為，w = 8尹1 +162 +123所以，該廠出租資源這個問題的數(shù)學(xué)模型，即為min w = 8兒 + 16y2 + 12y3力+4力2力 +42 >3戸、力、乃這一規(guī)劃問題就是原問題的對偶問題。事實上，這兩個問題是有內(nèi) 在聯(lián)系的，它們的最優(yōu)目標(biāo)值是相同的，對決策者這兩個方案都是最優(yōu) 方案。這個對偶問題有它相應(yīng)的意義，但有一些對偶問題很難從直觀上給 予解釋。下面從數(shù)學(xué)理論上提出線性規(guī)劃的對偶問題。已知線性規(guī)劃問題，max z = cxax <bix >0其非基變量的檢驗數(shù)為，cn-cb

20、b'n cbb當(dāng)該線性規(guī)劃問題得到最優(yōu)解時，cn-cbb-'ns(1)q礦乜0令ycgb"1,從(2)式可以得岀，y >0因為所有變量的檢驗數(shù)(包括基變量和非基變量)都可表示為,c-cbb'a<0 n c-ya<0 n ya>c又由 y = cbb" 得,yb = cbbxb = cb xb=z由于y的上界為無窮大，所以，yb最優(yōu)值只存在最小值。歸納起來, 可以得到另一個線性規(guī)劃問題，即原問題的對偶問題。min w = ybya>cr >o第四節(jié)原問題與對偶問題的關(guān)系原問題與對偶問題的關(guān)系分為對稱型對偶關(guān)系和非對稱

21、型對偶關(guān) 系.1 對稱型對偶關(guān)系對稱型對偶關(guān)系具有以下兩點(diǎn)特征：門目標(biāo)函數(shù)求max,約束條件是5;日標(biāo)函數(shù)求min,約束條件是 (2所有變量為非負(fù).對稱型對偶關(guān)系的標(biāo)準(zhǔn)形式如下： 原問題：max z = c“ +。2兀2 cn xn用矩陣表示: max z = cx ax <bix >0anxx+anx2 + + ainxn <b 。21 兀i +。22兀2 + +。2“” “2知內(nèi)+細(xì)2七+ °如兒 §嘰 兀1，兀2，,兀斤no對偶問題:用矩陣表示: min z = ybj)s > c|y >ominw = biyi +b2y2+- + 山1

22、兒+°21)，2 + °加1)5©2 +0222 + + d加丁加< 旬1 +。2小2 +。加幾丁12,，幾這一對對偶問題由于結(jié)構(gòu)的對稱性（約束類型和變量取值），所以，稱 為對稱型對偶關(guān)系.對稱型對偶關(guān)系可歸納如下：1原問題求目標(biāo)函數(shù)最大化；對偶問題求日標(biāo)函數(shù)最小化；（2原問題的約束條件是a對偶問題的約束條件是乙3原問題約束條件的右端項是對偶問題目標(biāo)函數(shù)的系數(shù)；對偶問題 約束條件的右端項是原問題目標(biāo)函數(shù)的系數(shù)；4原問題約束條件的個數(shù)等于對偶變量個數(shù)；對偶問題約束條件的 個數(shù)等于原問題變量個數(shù)；根據(jù)原問題與對偶問題的變換關(guān)系，可以寫岀一個線性規(guī)劃問題的對偶問題

23、。例2原問題:max z = " + 2x2 一 3x3 + 4x4x + 2x2 + 2x3 一 3 < 25< 2x + x2 - 3無3 + 2x4 < 15 xi,x2,x3,x4 > 0min w = 25/ +15% bl +22 >1 其對偶問題為：2?1 + j2 -2v 2i -3y2 > -3-3% +2y2 >42. 非對稱型對偶關(guān)系如果線性規(guī)劃的約束條件即包含有不等式又包含有等式，變量又有 非正或無約束，那么，這一對對偶問題就稱為非對稱型對偶關(guān)系。對于非對稱型線性規(guī)劃問題，可以將它轉(zhuǎn)換為對稱型，然后再按照對稱型的變換規(guī)

24、則，寫出它的對偶問題。 例3寫出下列線性規(guī)劃的對偶問題min z = 7兀+ 4x2 一 3x3 4 兀+ 2兀2 6 兀3 24_ 3 兀_ 6 兀2 一 4 兀3 n 15 5兀2 + 3 兀3 = 30 兀1 <0,%2無約束，兀3 no解：令x = -x19x2 = x2-x2且尤2、兀2并將所有約束寫成'的形式,1hmin z = -7xj + 4x2 一 4x2 一 3x4%| 2兀2 + 2%2 + 6兀3 » 24一 3 兀1 一 6 兀2 + 6 兀2 _ 4 兀3 - 15ih< 5兀2 一 5兀2 +3兀3 - 30ftl+ 5兀2 3七30

25、fhx、兀2、兀2、兀3 » 0再令對偶變量為力、2、丁3、y；，寫出對偶問題,f»flmax w = 一24兒 + 15y2 + 30y3 一 30y3_4力 +3乃 w-7 -2y'l-6y2+5y3 一5y； <4< 2兒 +62 5九 +5y； <-4 6” _ 42 + 3乃-3乃 < -3 力、乃、兒、y；再令力=一丁13 =歹3 一丁3,并將、兩個約束合并成等式約束,得,max w = 24y + 15y2 + 30y3-4力-3y2 w_72ji -6y2+5y3 =4_6兒_4力+3乃-3 ji 0 y2 0旳無約束對于非對

26、稱型對偶問題，關(guān)鍵在于處理等式約束和無約束變量，從 上面例子可以看出，等式約束和無約束變量之間的關(guān)系：原問題的等式約束條件，對應(yīng)于對偶問題的無約束變量；對偶問題的等式約束條件，對應(yīng)于原問題的無約束變量；例4所以，原問題與對偶問題的對偶規(guī)則可以歸納如下，根據(jù)這些規(guī)則 直接寫出一般線性規(guī)劃問題的對偶問題:原問題（對偶問題）對偶問題（原問題）目標(biāo)函數(shù)maxz目標(biāo)函數(shù)minw” n個n個1約變>0>束量<0<條無約束件約” m個m個、束<>0變條><0量件無約束約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項寫岀下列線性規(guī)劃問題的對偶問題

27、min z = 2xj + 3x2 一 5x3 + x4 x + x2 - 3x3 + x4> 52“ + 2兀3 -x4 < 4x2 + x3 + x4 = 6兀<0;x2>x3 >0;x4無約束解：根據(jù)原問題與對偶問題的對偶規(guī)則，對偶問題為,max w = 5尹+ 4y2 + 6y3 力+2乃x +2 +3 § 3 _3戸 + 2y2 + y3 < -5);1 -2 + 丁3 ix > 0,y2 < cl,”無約束 第五節(jié)對偶問題的基本性質(zhì)這些基本性質(zhì)將揭示原問題的解與對偶問題解之間的一些重要性質(zhì)。 以下約定原問題是指max z =

28、 cxax <bx >0其對偶問題為min w = ybya>c|y >o對于其它的互為對偶的線性規(guī)劃問題，也有相應(yīng)的以下這些性質(zhì)。1. 對稱性證：將對偶問題的兩邊同乘(-1),得，一minw = -yb ,-ya< -c , k > 0由于minw =-max(w),有,max(-w) = -yb，-ya< -c ,y >0(1)根據(jù)對偶變換關(guān)系，上式問題的對偶問題為， min(-w) = -cx ,-ax>-b,x >0又由于，min(-w') =-maxw', 所以，max= maxz = cx，ax <b

29、 , x >0 即為原問題。2. 弱對偶性如果x、y分別是原問題和對偶問題的可行解，則必有cx<ybo 證：因為x、y分別是原問題和對偶問題的可行解，所以，有ax <b , x >0; n yax < yb ;和 ya>c , k >0=> yax > cx ;所以，必有，cx<yb3. 最優(yōu)性如果xj廠分別是原問題和對偶問題的可行解，且那 么，x*、廠分別是原問題和對偶問題的最優(yōu)解。證：根據(jù)性質(zhì)2,對于原問題任一個可行解x,有cx < tb ,而cxrb n cx<yb = cx所以，x*是原問題目標(biāo)函數(shù)值最大的可行解，

30、x堤 原問題的最優(yōu)解。同理，根據(jù)性質(zhì)2,對于對偶問題任一個可行解y,有cx/yb,又已知, cx*=y6 n yb = cx<yb，所以，廠是對偶問題目標(biāo)函數(shù)值最小的 可行解，廠是對偶問題的最優(yōu)解。4. 無界性如果原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解。 證：用反證法證明，假設(shè)其對偶問題有可行解丫，則必有"，根據(jù)弱對 偶性，有cx<yb,顯然，這與原問題有無界解矛盾，所以，其對偶問題 無可行解。但要注意，這個性質(zhì)的逆命題不一定成立，即原問題(對偶問題)為無可 行解，其對偶問題(原問題)可能有無界解，也可能有無可行解。min w = 2y + y2_歹1

31、 - 2乃' 1x +丁2<h -2 n o例5已知原問題及其對偶問題:max z = x + 2x2xi + x + xo w 223和_x3 - 1xj>0, j = 1,2,3試用對偶理論證明原問題無界。證：顯然，在原問題中，x = (0,0,0)t是原問題的一個可行解，說明原 問題有可行解；而對偶問題的第一個約束條件- - 2力n 1明顯不能成 立，對偶問題不可行，所以，原問題無界。5. 強(qiáng)對偶性如果原問題有最優(yōu)解，那么，對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值 相等。(或者說，如果原問題和對偶問題都有可行解，則它們都是最優(yōu)解, 且目標(biāo)函數(shù)值相等。)證：設(shè)原問題的最優(yōu)解為r

32、,根據(jù)最優(yōu)性條件，對應(yīng)于基矩陣必然有,c-cbba<0 ,-cbbx < 0y = cbb1 ,則有，c-ya<q , y >0 n ya>c , y >0,可見，y是對偶問題的一個可行解，對應(yīng)的目標(biāo)函數(shù)值w為，w = yb = c8bb已知，"是原問題的最優(yōu)解，目標(biāo)函數(shù)值z為，z = cx =cbbb所以，可得，cx* =yb ,根據(jù)性質(zhì)3, y也是最優(yōu)解，且目標(biāo)值相等。6. 互補(bǔ)松弛性如果x*、廠分別是原問題和對偶問題的可行解，則它們?yōu)樽顑?yōu)解的充分必要條件是齊x* = 0, yxs = 0 o證：必要性，在原問題和對偶問題中分別引入松弛變量x$

33、和乙，則有,ax + x,=b , ya-ys=c若x*、廠為原問題和對偶問題的最優(yōu)解，根據(jù)對偶性質(zhì)，cx = rb, 有，yax + xs） = y*b ,（y*a-k）x*=cx*,整理后，y"xs+ysx" =0 n 必有，ex* =0,廠x, =0充分性，如果匕對=0,廠/=0,則有， (心c)x* =0,廠(4x*-b) = 0 n y*b = yx* =cx*所以，x*、廠為最優(yōu)解。互補(bǔ)松弛性質(zhì)，說明了線性規(guī)劃達(dá)到最優(yōu)時，原問題與對偶問題存 在下列關(guān)系：1如果原問題的某一約束為緊約束（松弛變量為零），該約束對應(yīng) 的對偶變量應(yīng)大于或等于零；（2果如果原問題的某一約

34、束為松約束（松弛變量大于零），該約束 對應(yīng)的對偶變量應(yīng)必為零；3如果原問題的某一變量大于零，該變量對應(yīng)的對偶約束必為緊 約束；（4如果原問題的某一變量等于零，該變量對應(yīng)的對偶約束可能為 緊約朿，也可能為松約朿?；パa(bǔ)松弛性的經(jīng)濟(jì)意義，是如果某資源在系統(tǒng)內(nèi)的影子價格大于零，則 該資源必是緊缺資源，對應(yīng)的約束為緊約束；如果某資源在系統(tǒng)內(nèi)有剩 余，資源約束為松約束，其影子價格等于零；對于影子價格大于零的資源，增加該資源可使目標(biāo)值增大。例6已知線性規(guī)劃問題+ x2 + 2x3 + x4 + 3兀5 > 4min w = 2xl + 3x2 + 5x3 + 2%4 + 3x5v 2xl - x2 +

35、 3x3 + x4+ x5 > 3xj >0,丿=12，5已知其對偶問題的最優(yōu)解為» =獎,z = 5。試用對偶理論找岀原問題的最優(yōu)解。 解：其對偶問題為,maxz = 4丁 +3y2(2)(4)(5)由于大于°根據(jù)互補(bǔ)松弛性，原問題的約束條件應(yīng)取等式；再將x=%，£ =釆代入對偶問題的約束條件中，可以看出，、為松約束（嚴(yán)格不等式），所以，對應(yīng)的原問題丘=珀=%： =0,則有,兀+兀5 = 42x _ 兀5 = 3=>x* = (wa1)t7. 用單純形法求解線性規(guī)劃問題的若干問題門）在單純形法迭代的每一步，在得到原問題的一個基可行解的同時，其檢

36、驗數(shù)的相反數(shù)構(gòu)成對偶問題的一個基解；2在單純形法迭代的每一步，原問題的目標(biāo)函數(shù)值都小于等于其對偶問題的目標(biāo)函數(shù)值；3在單純形法迭代的某一步，若原問題是可行解，其對偶問題也 是可行解，則這兩個可行解分別是兩個問題的最優(yōu)解。證：設(shè)b是原問題的一個可行基,引入松弛變量xs和剩余變量ys后，原問題和對偶問題可改寫如下:min w = ybyb-ys產(chǎn) cb<yn-ys2=cnmax z cgx匕十 cnx“ bxb + nxn+xs =b若求得原問題的一個解為，xb=b»b,其相應(yīng)的檢驗數(shù)為,cn-cbbn和-cb礦1,顯然，其對偶變量對應(yīng)于原問題松弛變量檢驗 數(shù)的相反數(shù)；再將y =

37、q礦i代入對偶約束中,有*1=0，-乙2 = gv - cbbn , 其對應(yīng)關(guān)系如下表：xbxnxs0cn -cbb-n- c bb-'$ys2-y第六節(jié)對偶單純形法前面介紹的單純形法，有時也稱為原始單純形法。它是在保持原問 題為可行解的基礎(chǔ)上，這時其對偶問題為非可行解，通過迭代，使原問 題從一個基可行解迭代到另一個基可行解，并向最優(yōu)解靠近，同時，對 偶問題也由非可行解向可行解靠近（也就是單純形表中檢驗數(shù)逐步變?yōu)?負(fù)數(shù)），當(dāng)對偶問題的解為可行解時，原問題就得到了最優(yōu)解，對偶問題 也得到最優(yōu)解。對偶單純形法它是在迭代過程中保持對偶問題的可行性（即始終保 持所有的檢驗數(shù)為負(fù)數(shù)），同時取消單

38、純形表b列元素非負(fù)限制（也就是 原問題一般為非可行解），通過迭代，使原問題在非可行解的基礎(chǔ)上逐步 向可行解靠近，當(dāng)原問題達(dá)到了可行解，也就得到了最優(yōu)解。實際上，對偶單純形法是根據(jù)對偶對稱性，從另一個角度考慮，它 將原問題的基變量的值作為其對偶問題的某一解的非基變量的檢驗數(shù)， 由于對偶問題是求極小值，所以當(dāng)這個檢驗數(shù)中還有負(fù)數(shù)時，繼續(xù)迭代, 當(dāng)檢驗數(shù)全部為正數(shù)（原問題得到可行解），也就得到了最優(yōu)解。對偶單純形法求解步驟如下：（1）建立初始單純形表，并進(jìn)行最優(yōu)性檢驗。檢查b列的值，如果全都為止數(shù)，檢驗數(shù)也都為負(fù)數(shù)，則已取得最 優(yōu)解，停止計算；如果檢驗數(shù)全部為負(fù)數(shù)，b列屮至少有一個負(fù)分量，則 轉(zhuǎn)入下

39、一步；2）確定換出變量。若不滿足最優(yōu)性條件，找出最小的負(fù)檢驗數(shù)，即基變量中最小 的負(fù)數(shù)，它所對應(yīng)的基變量毎為換出變量。即min（礦則（礦）, v（礦對應(yīng)的基變量匕為換出變量。（3）在單純形表中，檢查兀/所在行的各個系數(shù)呵，j = 1,2,n，如果所有的atj >0,則無可行解，停止計算；如果有atj <qj = 1,2,衛(wèi),將檢驗數(shù)行檢驗數(shù)s與七行的系數(shù)切，計算對應(yīng)的非基變量忑為換入變量。（4以q仏為主元素，按照一般單純形法在表中進(jìn)行迭代運(yùn)算，得到新的單純形表。5重復(fù)(1)(4)步驟，直到求出最優(yōu)解。 在使用0規(guī)則，應(yīng)注意以下兩點(diǎn)：*由于主元素d/k從第l行的切屮產(chǎn)生，而b嚴(yán)丄又必

40、須為正數(shù)，所 %以，0規(guī)則中切必須小于零；*檢驗數(shù)行元素與主元行元素的比值必須取min,這樣才能保持對偶 問題始終有可行解；設(shè)基變量可為換出變量，非基變量以為換入變量，在換基后，檢驗 數(shù)行的各個檢驗數(shù)為，切1 056,丿=12丿aik將第l行除以主元素做，得，,0,0,丄,0,0, /,w+1，,1,如(*)aikaikaikaik因為非基變量耳換基后將變成基變量，其檢驗數(shù)為零，所以，將變化后的丄元行元素乘以加到檢驗數(shù)行，即可得到上式(*) o由于要求，c>'. =c> -ok <0 ，j = l,2，,aik因為鳥 < 0，< 0 ,< 0 , j

41、 = 1,2,當(dāng) a ik » 0 時，自然滿足耍求；當(dāng)恢50時，耍使c>7<0,就必須,5/alk= alj<0alk丿而v 0 ,所以,o i 6-必須人于零, ali alksi>2k. alj alk所以，0 = min<jcj sauatj < 0alk例7用對偶單純形法求解min w = 2xl + 3x2 + 4x3x + 2x2 +x3 > 3v 2x1 -x2 + 3x3 > 4x，兀2，兀3 - 0解:先將其化為標(biāo)準(zhǔn)型，為此引入剩余變量勺、兀5,并將約束等式兩邊乘以小得到初始可行基，即max z = 2兀一 3x2

42、一 4x3_ 兀_ 2%2 _ 兀3 + 兀4 = _3v 2xj + 兀2 3 兀3 + 兀5 = 一4 xj no,) = 12，5建立的初始單純形表如下表:cj-2-3-400cbxbb兀i兀2兀3兀4兀50兀4-3-1-21100兀54(-2)1301cj-zj-2-3-400從上表可以看出，檢驗數(shù)行檢驗數(shù)全部為負(fù)數(shù)，b列數(shù)字為負(fù)，說明對偶問題有可行解，原問題是非可行解，需要迭代計算。確定換出變量，b列有兩個負(fù)數(shù)，一般選取負(fù)數(shù)最小者對應(yīng)的基變量為換出變量，即min-3,-4=-4對應(yīng)的基變量氐為換出變量; 確定換入變量，按照。規(guī)則，即min<jaljcj勺-4即對應(yīng)的非基變量無1

43、為換入變量，主元行為第2行，主元列為第1列, 以2為主元素按照單純形法進(jìn)行迭代計算，得下表：ci-2-3-400cbxbb兀1兀2兀3x4無50x4-10(-5/2)1/21-1/2-2xi21-1/23/20-1/2cj-zi04-10-1從上表看出，檢驗數(shù)行所有檢驗數(shù)仍為負(fù)數(shù)，在b列中仍有負(fù)分量，所 以，還需要進(jìn)行迭代運(yùn)算，重復(fù)上述迭代，得下表：ci-2-3-400cbxbb兀1兀2*3x4-3兀22/501-1/5-2/51/5-2兀111/5107/5-1/5-2/5cj-zj00-9/5-8/5-1/5從上表看出，b列數(shù)字全為正數(shù)，檢驗數(shù)也全為負(fù)數(shù)，原問題得到最優(yōu)解為，x*=（少00

44、0）7。根據(jù)對偶原理，對偶問題的最優(yōu)解為y*=（翼,%）。對偶單純形法并不只是求解對偶問題的單純形法，而是根據(jù)對偶原 理用來求解線性規(guī)劃問題的一種方法。使用對偶單純形法，當(dāng)約束條件 為時，不需要引入人工變量，簡化了計算；但使用對偶單純形法是 有條件的，它要求初始單純形表中其對偶問題應(yīng)有可行解（也就是單純形 表屮檢驗數(shù)必須全為負(fù)數(shù)），單純形表屮b列屮至少有一個負(fù)值，所以， 對偶單純形法一般不單獨(dú)使用，主要是用在靈敏度分析以及整數(shù)規(guī)劃等 內(nèi)容中。第七節(jié)靈敏度分析在前面討論線性規(guī)劃問題時，均假設(shè)數(shù)學(xué)模型中的原始數(shù)據(jù)是不變 的常數(shù)，如約束條件系數(shù)d廠目標(biāo)函數(shù)價值系數(shù)勺和資源限量勺等，并 在此基礎(chǔ)上求最

45、優(yōu)解。但實際上，這些數(shù)據(jù)并非一成不變，因為這些數(shù) 據(jù)往往都是一些估計值或預(yù)測值，不可能很精確。如在生產(chǎn)計劃模型中，當(dāng)市場行情發(fā)生變化后（原材料價格、未來 需求量等發(fā)生變化后）就會引起價值系數(shù)勺變化；隨著生產(chǎn)技術(shù)的提高 約束條件系數(shù)旬也會發(fā)生變化；資源限量勺也會隨著市場供應(yīng)狀況而發(fā) 生變化等。這樣，就提出一個問題，這些數(shù)據(jù)發(fā)生變化后，對已求得的線性規(guī) 劃問題的最優(yōu)解有什么影響；或者說當(dāng)這些數(shù)據(jù)在什么范圍變化時，已 求得的線性規(guī)劃問題的最優(yōu)解或最優(yōu)基保持不變。這就是靈敏度分析所 要討論的問題。對于系數(shù)變化后的線性規(guī)劃問題，可以看成是一個新的線性規(guī)劃問 題，利用單純形法從頭計算求解，但這樣做既費(fèi)事，

46、也沒有必要。在靈 敏度分析中，采取了最簡便的計算方法，即在最優(yōu)表基礎(chǔ)上，計算這些 系數(shù)應(yīng)在什么范圍內(nèi)變化時，原問題的最優(yōu)解保持不變，和計算當(dāng)這些 系數(shù)超出范圍后新的最優(yōu)解。具體計算時，只要將個別變化的系數(shù)，經(jīng)過一定的計算后直接填入 最優(yōu)表中，并進(jìn)行檢查和分析，再按照不同的情況判別最優(yōu)解會不會發(fā) 生變化和計算出新的最優(yōu)解。原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解表中的解仍為最優(yōu)解可行解非可行解用一般單純形法繼續(xù)迭代求解非可行解可行解用對偶單純形法繼續(xù)迭代求解非可行解非可行解引進(jìn)人工變量，編制新單純形表，繼續(xù)求解1.資源數(shù)量變化的分析設(shè)第廠種資源數(shù)量侏變化為brr = br + abr,并假

47、設(shè)其它資源數(shù)量不變,x；=b（b + ab） = b'b + b'ab = b'b + b_10 ahr 0b +air abrbi + % abr其中，礦 =（勺,/?2,，方j(luò) ,為最優(yōu)基逆矩陣礦中第廠列第i個元素。由此可見，某一資源數(shù)量的發(fā)生變化力你，使得x；的可行性有兩種 可能：可行解（x；no）和非可行解。如果力你變化量在一定的范圍變化，使得x； no仍為可行解。由于 /休變化不影響檢驗數(shù)，最優(yōu)表中檢驗數(shù)不變，最優(yōu)基不變，所以，x;仍 為最優(yōu)解（根據(jù)對偶理論），但x：最優(yōu)解的值發(fā)生變化為新的最優(yōu)解。如果z1你變化量超出一定的范圍，使得x： no變?yōu)榭尚薪?。由?/p>

48、在 最優(yōu)表中，原問題的解不可行，對偶問題的解可行，則應(yīng)運(yùn)用對偶單純 形法繼續(xù)迭代求出新的最優(yōu)解，顯然，最優(yōu)基、最優(yōu)解都發(fā)生改變。那么，力休變化范圍應(yīng)為多大，才能使得最優(yōu)基保持不變，x；仍為 最優(yōu)解，但x；的值要發(fā)生變化。要保持最優(yōu)基不變，則必須x；no,即bt + air - abr > 0 , i = 12,，m由此，可以導(dǎo)出,當(dāng)<0時，有迥=-叩仏當(dāng) air > 0 時,有 abr>/ air因此，abr的允許變化范圍為，例8.求第一章例1中第二個約束條件仇的變化范圍/仇btmax< -air > °> < abr < min

49、<jair < 0 >7 d”j1j具體使用上式：先在最優(yōu)表中找出最優(yōu)基b的逆矩陣再各的 第廠列中的正分量放在不等式左邊，負(fù)分量放在不等式右邊，即可求出/br 的變化范圍。解：在最優(yōu)表中，最優(yōu)基b的逆矩陣礦|為，_ 00.250_b' = -20.511/2 -0.125 0_最優(yōu)表中b列元素為，4bb= 42代入上式，得44 . f 21i 0.250.5j - i -0.125j=>max-16,-8 < ab2 < min16所以，加2變化范圍為-8,16,或$變化范圍為8,32。2.目標(biāo)函數(shù)中價值系數(shù)j的變化分析從非基變量檢驗數(shù)式子（或稱最優(yōu)

50、性判別條件），aj=cj-ciib-ipj, 可以看出，目標(biāo)函數(shù)系數(shù)勺的變化會引起檢驗數(shù)勺的變化，即引起原問 題最優(yōu)解或最優(yōu)基的變化。那么，耍保持原規(guī)劃問題最優(yōu)解或最優(yōu)基不 變，價值系數(shù)勺應(yīng)在什么范圍變化；如果價值系數(shù)勺超出了變化范圍， 原問題的最優(yōu)解又如何計算。由于價值系數(shù)勺對應(yīng)非基變量和基變量兩種情況，分別討論：（1）非基變量©的價值系數(shù)勺的變化非基變量的檢驗數(shù)j為，af =cj -cbb'pj如果非基變量©的價值系數(shù)勺改變?yōu)閏；=勺+/勺，則變化后的檢驗數(shù)c'j 應(yīng)為,（t'j = cj + acj cqb ipj要保持原最優(yōu)解不變，則必須，c

51、'j = c j + 4c j _ cb b ' pj 5 0a叭=cj + 笙-cbbpj=j + 4c）< 0即，acj < jcr7 ,其中，勺為最優(yōu)表中非基變量的檢驗數(shù)。如果非基變量價值系數(shù)勺的變化超出了原問題對應(yīng)的非基變量檢驗 數(shù)，這時，原問題的解可行（但不是最優(yōu)解），對偶問題的解不可行，應(yīng) 該應(yīng)用一般單純形法繼續(xù)迭代求出最優(yōu)解。例9.已知線性規(guī)劃問題max z = 一兀 1 + 2x2 + x3s.t. <x+ x2+x3< 62x - x2 < 4 xj >0j = 1,2,3其最優(yōu)表如下表所示,cj-12100cbxbb兀ix

52、2七兀4兀52x26111100兀510301115-12-30-1-20求：非基變量州系數(shù)q的變化范圍;當(dāng)系數(shù)q變?yōu)?時，求新的最優(yōu)解。解：從上表可以知道，3,要保持最優(yōu)解不變，則必須，acl <= 3c； = q + /c 5 1 + 3 = 2即c；值小于2時，最優(yōu)解不變。 當(dāng)q變?yōu)?時，顯然，c；=4已超出2的變化范圍，最優(yōu)解要變, 求最優(yōu)解可在最優(yōu)表基礎(chǔ)上進(jìn)行。首先，求出新的檢驗數(shù)即cr；=c；-cs 礦爪4 (2,0)_1 0_t1 1_2_=2>0最優(yōu)性已不滿足，用新的檢驗數(shù)a； = 2代替5 =-3,其余數(shù)據(jù)不變, 繼續(xù)用一般單純形法迭代。由于罠=2,應(yīng)選擇相應(yīng)的變

53、量坷換入，根據(jù)&規(guī)則可知，應(yīng)選擇基變量兀5換出，如卜表,cj42100ecbxbb兀ix2£兀4兀52x261111060兀510k3i011110/3（jj-1220-1-202x28/3012/32/3-1/34兀10/3101/31/31/3(7 j-56/300-5/3-8/3-2/3最優(yōu)解為 x* =(10/3,8/3,0,0,=56/3（2）基變量的價值系數(shù)s的變化設(shè)某個基變量兀.的價值系數(shù)由c廠變?yōu)閏； =c+ acr 則其中,如=(0,0,，俎,0)c； =5+力5, s =(c,c2,，s ，5)a，j=cj c,bbpj=cj-(cb+acb)bipj=cj-cbbpj-ac8bpj=bj - (0,0,生,=(t j - acr 6z < 0要保持最優(yōu)解不變，則必須滿足，即ej =ctj-acr q <0, j = m +由此，可以導(dǎo)出，當(dāng)夠 <0時,有 acr < aj /arj當(dāng) arj0時，有 acr > oj /arj因此，的允許變化范圍為，m