運籌學,線性規(guī)劃

第二章線性規(guī)劃的對偶理論和靈敏度分析常見疑問解答1、已知原線性規(guī)劃問題如何寫出其對偶問題？（1）如果原問題是MAX問題，則其對偶問題是MIN問題。按下表可將其對偶問題寫出。原問題（L）一一對應對偶問題（D）max問題min問題有m個約束條件有m個變量第j個約束條件為W關系第j個變量N0第j個約束條件為N關系第j個變量W0第j個約束條件為等式關系第j個變量無非負約束，是自由變量第i個變量N0第i個約束條件為N關系第i個變量W0第i個約束條件為W關系第i個變量無非負約束，是自由變量第i個約束條件為=關系資源向量價值向量價值向量資源向量（2）如果原問題是MIN問題，則其對偶問題是MAX問題。按下表可將其對偶問題寫出。原問題（L）一一對應對偶問題（D）min問題max問題有m個約束條件有m個變量第j個約束條件為W關系第j個變量W0第j個約束條件為N關系第j個變量N0第j個約束條件為等式關系第j個變量無非負約束，是自由變量第i個變量N0第i個約束條件為W關系第i個變量W0第i個約束條件為N關系第i個變量無非負約束，是自由變量第i個約束條件為=關系資源向量價值向量價值向量資源向量2、 在已求出原問題的最優(yōu)單純形表后，如何求出對偶問題的最優(yōu)解（即影子價格）？在已求出原問題的最優(yōu)單純形表后，可確定出相應的最優(yōu)基B和及其對應的CB，然后通過公式Y*=CbB-1,即可求出對偶問題的最優(yōu)解，或甚至直接從其最終單純形表中就能得到對偶問題的最優(yōu)解。3、 如何通過公式Y*=CbB-i（B是線性規(guī)劃問題的最優(yōu)基）計算以下問題的影子價格及其對偶問題的最優(yōu)解？

答:a.%1+3%2答:a.%1+3%2+8%3+4%4<452342x1+X2+%3+3%4<40X1,x2,x3,x4N0將原問題化為標準形maxz=x1+x2+4x3+3x4X1+3X2+8X3+4X4+X5 =452x+x+x+3x +x=401 2 3 4 6b.x「xb.x「x2,%,x4,%,療0用單純形法求解，得到原問題的最終單純形表為TOC\o"1-5"\h\z□5 0 1 1 0 3/5 1/5「㈤豆可）§ 1 _4 o -315 4/5L10 0 1 3 1 2/5 -1/5c. 在最終單純形表中觀察影子價格□5 0 1 1 0 3/5 1/5「筋歐］孔可）5 1 -1 -4 0 -315 4/5L10 0 1 3 1 W m(-3(54J5)最終單純形表中松弛變量x5,x6對應的檢驗數3/5,1/5,就是影子價格，即丫*=??'“一'?=(3/5,1/5).它也是對偶問題min2'=45min2'=45七+40七^1+2^2^13y1+2y2N1陽+%N片，『°的最優(yōu)解。并且最終單純形表中松弛變量x5,x6對應的子陣5 ，就是原問題最優(yōu)基B的逆矩陣，即最優(yōu)基B-1=1"一'⑶4,通過對一個線性規(guī)劃問題的最優(yōu)單純形表的觀察直接得到其對偶問題的最優(yōu)解（影子價格），這種觀察法適宜于哪種類型的線性規(guī)劃問題？這種觀察法最適宜于如下類型的線性規(guī)劃問題，Mu..吃占相奉JJ.41^+心3* 十%.、虹fWL*r勾?A■￡。此類線性規(guī)劃問題正好在每個約束條件上添加了一個松弛變量后才化為標準形。因而，在其最優(yōu)單純形表上，直接觀察那些松弛變量對應的檢驗數即可得到對偶問題的最優(yōu)解（影子價格九同時，原問題最優(yōu)基B的逆矩陣B-1,也可直接從最優(yōu)單純形表上松弛變量的檢驗數下方的那些列構成的方陣觀察得出。5通過對一個線性規(guī)劃問題的最優(yōu)單純形表的觀察直接得到其對偶問題的最優(yōu)解（影子價格），這種觀察法的理論依據何在？不妨設線性規(guī)劃問題具有如下形式，maxz=CXAXWbXN°.加入松弛變量向量X可化為如下標準形maxz=CXAX+X=bX,XN°.其系數矩陣引，其中E是單位陣。設其最優(yōu)基存在且為B,則在該基下的最優(yōu)單純形表具有如下形式，c^~lA-c展T][B-1&"JX旭=可以看到，最優(yōu)基B下松弛變量Xs對應的檢驗數CbB-1正好是求影子價格和對偶問題最優(yōu)解的公式Y*=CbB-1（B是線性規(guī)劃問題的最優(yōu)基）的右端項，所以，直接觀察最優(yōu)單純形表松弛變量的檢驗數即可得到影子價格和對偶問題的最優(yōu)解。同時，最優(yōu)基B的逆矩陣也可直接在檢驗數正下方的子陣中觀察得到。6、6、影子價格的經濟意義何在?其中，變量x,j=1,其中，變量x,j=1,2,…，n,是每種產品的產量;s=sFl+卒7+%知031+句衛(wèi)矣+￡3“?勺?+&+■電1獎 中性就*&+MMMM MM十5心十*氣十氏十1、5,A和？0May.%如%&5,j=1,2,…，n,是每種產品的單位利潤或i=1,2,…，m,是每種資源的總量，a.,j表示生產第j種產品一個單位所消耗的第i種資源的量，i=1,2,…，m,j=1,2,…，n.a.,j其對偶問題即有如下形式，十+十+MMMMayri?弁方+MMMMA ?_ %\o"CurrentDocument"M MNA ? 普叩M MMA ? 土.-0其中，對偶問題中的變量yk，k=1,2,…，m,反映了單位資源（所可能創(chuàng)造）的價值。我們知道這個線性規(guī)劃問題的對偶問題的最優(yōu)解Y*=CbB-i（B是原問題的最優(yōu)基）被稱為影子價格。因此影子價格自然就反映了資源在最優(yōu)配置模式下，單位資源所創(chuàng)造的（平均）價值。

如果我們從經濟學的邊際概念出發(fā)，那么可以看到影子價格實質上是資源最優(yōu)配置下，關于資源的邊際收益或邊際成本。（B是原問題的最優(yōu)基）。此外，從管理會計的角度看，影子價格在資源出售、出租或購入行為決策中，它也可作為機會成本或機會收益予以考慮。最后，簡單地說，影子價格反映了（稀缺）單位資源在最優(yōu)配置下所創(chuàng)造的價值7、影子價格和市場價格有何區(qū)別？影子價格并不等同于市場價格。一般而言，在研究利用資源實現利潤或收益等最大化的問題中，如果資源的影子價格低于市場價格，則這種資源被組織利用的效率比市場利用效率低，因此可以出售或出租；反之，就應該吸納。因此，市場價格作為了一種資源吸納、利用的基準，它與影子價格一道服務于企業(yè)或政府的資源利用策略中。8、影子價格向量中，某種資源對應的值為0或非0值，反映了關于資源的什么信息？當某種資源對應的值為0時，一般表示該種資源經最優(yōu)配置后，還可能有剩余，因此繼續(xù)吸納這種有閑置性的資源并不會帶來利潤或收益的增加；當某種資源對應的值為非0時，一般表示該種資源經最優(yōu)配置后，無剩余，是一種稀缺資源9如何理解互補松弛定理？互補松弛定理是對偶問題最重要的性質之一。它指出了原線性規(guī)劃問題及其對偶問題最優(yōu)解與約束關系式間的關系。當將原問題和對偶問題基本最優(yōu)解分別帶入各自的線性規(guī)劃模型中時，存在如下關系：原問題（L）對偶問題（D）第j個約束條件為嚴格的不等式對應的第j個變量值=0第j個約束條件為等式對應的第j個變量值N0第i個變量值＞0對應的第j個約束條件為等式對偶問題（D）原問題（L）第j個約束條件取嚴格的不等式對應的第j個變量值=0第j個約束條件取等式對應的第j個變量值N0

第i第i個變量值＞0對應的第j個約束條件為等式10如何利用互補松弛定理求出以下只有一個約束方程的線性規(guī)劃問題的最優(yōu)解?MaxZ=c1x1+c1x2H c/nax+axH axWb11 12 nnX1，X2,…，XnNO,c.,b>0,i=1,2,???,n.答：a.寫出其對偶問題a.寫出其對偶問題Minf=byyN0imax—b.利用原問題與對偶問題間的相互轉換關系，易知其對偶問題的最優(yōu)解y*= 昭」b.c,應用互補松弛定理不妨設y*=不妨設y*=對偶問題3”原問題CL)尸第1個約束第1個變量 J1*=O】第W個約束 角廣次2『第2個變星 或=。> P.?■???第上個約束 明1*第個變量 職*"1 P.?■???斗［第》個約束 咐E槌第H個變量 知*71第1個變量 />0第1個約束口的*十旬超*+..口浜*十…十瓦耳*2，化簡餌，俺泌=b?d,所以，原問題的最優(yōu)解：xk*=硫，沖=0,i=1,2,…，n,i尹k.11*本章關于對偶問題的性質6談到，“原問題某個基下的單純形表中的檢驗數對應于對偶問題的某個基解”，其理論依據何在?答：關于此性質的理論推導可如下進行。不妨設原問題(乙)具有如下模型形式，max蕓=成(￡)密5Z>0且從A中選出了一些列向量構成一個基B.相應于基B，A被分解為A=(BN),其中B是所選的那個基，N是此時非基向量形成的子陣，變量X被分解為X=(XBXn)t.引入松弛變量X；,得到原問題(L)標準形(L)的向量矩陣形式為maxs=cT(r)氏5熠—W=8其對偶問題(D)為minJ=爬YN>c^引入松弛變量丫暗Ys2后，可寫出對偶問題(D)的標準形(D')為，選定關于對偶問題標準形（D，）的基為土,其中E為單位陣，則基后下，基變量的值由此可以看出，基虐下對偶問題的基解（不一定是對偶問題的基本可行解）與原問題基B下的單純形表中的檢驗向量之間存在如下對應關系：原問題變星在基B下的分類F基變非基變星X*松曲變墾X妒原問題基B下黑熙表史的橙批向量。OpCeB^K-ChPCL對偶1司題基另下的基解甲松■弛變星丫戰(zhàn)的值p松曲變量￥以的值F『的值『12假設原問題是如下所示的追求利潤最大的生產計劃問題，它的對偶問題中的變量反映了單位資源可能創(chuàng)造的價值，則對偶問題標準形中松弛變量具有怎樣的經濟含義？原問題的模型形式如下。Ma*s=勺#1+（32^2*%+聞彼十十5+&+<4-電1矣4-aW+△+己Mr<MMMMMMM4-4-7+<-0其中，變量斗，j=1,2,…，n,是每種產品的產量；弓，j=1,2,…，n,是每種產品的單位利潤；b.,i=1,2,…，m,是每種資源的總量，a.j表示生產第j種產品一個單位所消耗的第i種資源的量，i=1,2,…，m,j=1,2,…，n.答:其對偶問題即有如下形式，瑚1+再此+A+電/，+hMMMMM+切凹+A+VmMMMMMiSMl+盆欣-4-A+口花心IB-町MM》勺MM2%其中，對偶問題中的變量yk，k=1,2,…，m,反映了單位資源（所可能創(chuàng)造）的價值。寫出對偶問題的標準形式為，蜘f=勒+糧u站備in++k+知口裁■^M+l=句J.f.句河i+Ugg+~y^±+2=叮MMMM0MMW+""乃+也+%{p3Hp粗+j=如MMMM0M即Fl+叫對3 +蟲+婭Wt一『5=*松弛變量的決策分析十*、…寸鼻7沖4?-人，乙士向做+電J此+A+12昭％B-/阱J=勺不妨僅研究對偶標準形的第j個約束，薩、隅」」注意到松弛變量'帝7可表示為為+J=紙M +直"戒忒由于財此十叼咫科十⑶扁反映了若原問題中第j種產品的生產量Xj減少一個生產單位（決策1：減產決策）時，所節(jié)約的各廣知］

也jM種資源（節(jié)約量為頃晾"）被重新利用時可創(chuàng)造的價值（參見本章FAQ（7）問題），因而可反映減產決策所產生的機會收益（機會利潤）；同時，氣曲+電也反映了若原問題中第j種產品的生產量Xj增加一個生產單位（決策2：增產決策）時，所耗aM費的各種資源（耗費量為頃邱"）必須從其它產品的生產中轉移出來，因而必須為這種轉移所引起的其它產品減產及利潤減少付出代價（參見本章FAQ（9）問題），故，電而十電庭普f拔也可反映增產決策所產生的機會成本。而弓表示生產第j種產品所獲的單位利潤，因而，它可反映“第j種產品的生產量斗減少一個生產單位”這個減產決策所帶來的機會成本，也可反映“第j種產品的生產量弓增加一個生產單位”這個增產決策所帶來的機會收益或機會利潤。d, 松弛變量的經濟含義綜上，外+廣Swi撲Ma十a松做q-町=減產決策的機會利潤一減產決策的機會成本=增產決策的機會成本一增產決策的機會利潤=減產決策的機會利潤一增產決策的機會利潤 （差額利潤）=增產決策的機會成本一減產決策的機會成本 （差額成本）故，松弛變量y，F.具有差額利潤、差額成本的經濟含義。有些教材上也稱之為遞減成本。13單純形表中的檢驗數具有怎樣的經濟含義？不妨以以下問題為例進行解釋。假設原問題是如下所示的追求利潤最大的生產計劃問題，其模型形式如下。s=勺X]+^2^2*%+備獨1句1河+句衛(wèi)矣+￡3“?勺?+&+MMMMM口洋兇十5心十*氣十氏十心嚀』和？0其中，變量%,j=1,2,…，n,是每種產品的產量；Cj,j=1,2,…，n,是每種產品的單位利潤；b.,i=1,2,…，m,是每種資源的總量，a.j表示生產第j種產品一個單位所消耗的第i種資源的量，i=1,2,…，m,j=1,2,…，n.

Msmf=處］* W沖+勺+A+聞勺+聞2/勺+AMMMMMM++A+口嗤叫M?財MMMMMMM戶心1+erw+A+知德花>b.該生產計劃問題的對偶問題即有如下形式，其中，對偶問題中的變量yk，k=1,b.該生產計劃問題的對偶問題即有如下形式，其中，對偶問題中的變量yk，k=1,2,…m,反映了單位資源(所可能創(chuàng)造)的價值。c.寫出對偶問題的標準形式為，++h+口城m-^K+l■5.f."i河i+口以3+h+兩河:w一刑+3MMMM□Mw十+h+聞對黜biMM□MFIkFI+叫對3+占+w就一『程十IS蜘f=81+R/A+*航=句=叮M=叮=+d.松弛變量心可表示為心?=%?哄*+°心Fe. 引用對偶問題的性質6本章對偶問題的性質6談到，“原問題某個基B下的單純形表中的檢驗數對應于對偶問題的某個基解”，且y=(y1y2…ym)=cBbf故，其中f. 故，原問題某個基下的檢驗數即是對偶問題某個基解中某個松弛變量的值。g.引用本章FAQ(38)，關于對偶問題松弛變量的經濟解釋，可以得到關于原問題某個基下檢驗數的經濟解釋。14互補松弛定理有何經濟意義?

不妨以以下問題為例進行解釋。a. 假設原問題是如下所示的追求利潤最大的生產計劃問題，其模型形式如下。s二電氣+A+備氣1句1皿+^12^2+財氣+占+4七也 +生槌*MMMMMajwPL十巧十gy十山十

心恐，AaK~°其中，變量斗，j=1,2,…，n,是每種產品的產量；"=1,2,…，n,是每種產品的單位利潤；b,,i=1,2,…，m,是每種資源的總量，a.j表示生產第j種產品一個單位所消耗的第i種資源的量，i=1,2,…，m,j=1,2,…，n.其標準形具有如下形式，Maxs=勺電+^2*%+靠氣可劇和*境41%!枷 +xs+2MM可劇和*境41%!枷 +xs+2MM|=S=&Mf+沖=膈宅］和 + + +'MMM0M戶虹叮十&1想十 +M宴kX"浦」L，沖出？CI其中，是松弛變量，它們分別反映了第一到m種資源被使用后的剩余部分。該生產計劃問題的對偶問題即有如下形式，其中，對偶問題中的變量y其中，對偶問題中的變量yk，k=1,2,?,m,反映了單位資源（所可能創(chuàng)造）的價值。d.寫出對偶問題的標準形式為，d.寫出對偶問題的標準形式為，蜘f=8l*如叮*A+B用上1『1十+A+如口禎>C1叫河1十+A>MMMMMMM+口碩+A+如樸1叮MMMMMM思"14-電砂+A+口花時秋>"室hj/用>0蜘f=81+R/A+WiwTOC\o"1-5"\h\z+ + -^k+1 =門薄“i河i+電+也+心昭知-^+2 =嚀M M M M□ M M十口"巧十也+如服改 —/粉J =叮M M M M□ M M『"1+叫對3+%*W宙JR -^M+M=*e. 設原問題和對偶問題的最優(yōu)解分別是x*,y*.互補松弛定理可表述為互補松弛定理的經濟含義可解釋如下。在利潤最大化的生產計劃中，4+*>。，表明第i種資源在最優(yōu)配置下有剩余，因此第i種資源的增加只會帶來更多的資源冗余，故第i種資源的邊際利潤y*=0，即xn+i*>0,則y*=0.此數學表達式的經濟含義可簡述為：有剩余的資源其邊際利潤為0.y*>0,表明第i種資源必然是一種稀缺資源，在最優(yōu)配置下沒有剩余，第i種資源邊際利潤大于0(因為如果第i種資源在最優(yōu)配置下有剩余，則第i種資源的增加只會帶來更多的資源冗余，那么必然發(fā)生第i種資源的邊際利潤y*=0)，故xn+i*=0，即y*>0,則xn+i*=0.此數學表達式的經濟含義可簡述為：邊際利潤大于0的資源沒有剩余；ym+j*>0,表明資源最優(yōu)配置下，增產j產品一個單位的機會成本超過了增產j產品一個單位所帶來的利潤增加；同時，減產j產品一個單位的機會利潤