第二章線性規劃的對偶理論與靈敏度分析§1線性規劃的對偶問題§2對偶規劃的根本性質§3影子價格§4對偶單純形法§5線性規劃的靈敏度分析1

一、對偶問題的提出1、

對偶思想舉例周長一定的矩形中，以正方形面積最大；面積一定的矩形中，以正方形周長最小；§1線性規劃的對偶問題2每一個線性規劃問題，都存在每一個與它密切相關的線性規劃的問題，我們稱其為原問題，另一個為對偶問題。例題1某工廠在方案期內安排Ⅰ、Ⅱ兩種產品，生產單位產品所需設備A、B、C臺時如表所示

該工廠每生產一單位產品可獲利50元，每生產一單位產品Ⅱ可獲利100元，問工廠應分別生產多少產品和Ⅱ產品，才能使工廠獲利最多？解：設為產品的方案產量，為產品Ⅱ的方案產量，那么有目標函數：Maxz=50x1+100x2約束條件：

，3現在我們從另一個角度來考慮這個問題。假設有另外一個工廠要求租用該廠的設備A、B、C，那么該廠的廠長應該如何來確定合理的租金呢？設分別為設備A、B、C的每臺時的租金。為了表達方便，這里把租金定義為扣除本錢后的利潤。作為出租者來說，把生產單位產品所需各設備的臺時各總租金不應低于原利潤50元，即，否那么就不出租還是用于生產產品以獲利50元；同樣把生產一單位產品所需各設備的臺時的總租金也不應當低于原利潤100元，即，否那么這些設備臺時就不出租，還是用于生產產品以獲利100元。但對于租用者來說，他要求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設備臺時的總租金越低越好，即min，這樣我們得到了該問題的數學模型：

目標函數：約束條件：這樣從兩個不同的角度來考慮同一個工廠的最大利潤〔最小租金〕的問題，所建立起來的兩個線性模型就是一對對偶問題，其中一個叫做原問題，而另外一個叫對偶問題。42、

換個角度審視生產方案問題例要求制定一個生產方案方案，在勞動力和原材料可能供給的范圍內，使得產品的總利潤最大。它的對偶問題就是一個價格系統，使在平衡了勞動力和原材料的直接本錢后，所確定的價格系統最具有競爭力：5〔用于生產第i種產品的資源轉讓收益不小于生產該種產品時獲得的利潤〕對偶變量的經濟意義可以解釋為對工時及原材料的單位定價；假設工廠自己不生產產品A、B和C，將現有的工時及原材料轉而接受外來加工時，那么上述的價格系統能保證不虧本又最富有競爭力〔包工及原材料的總價格最低〕當原問題和對偶問題都取得最優解時，這一對線性規劃對應的目標函數值是相等的：6二、原問題和對偶問題的關系1、對稱形式的對偶關系〔1〕定義：假設原問題是7那么定義其對偶問題為這兩個式子之間的變換關系稱為“對稱形式的對偶關系〞。8〔2〕對稱形式的對偶關系的矩陣描述（LP）〔3〕怎樣從原始問題寫出其對偶問題？按照定義；記憶法那么：“上、下〞交換，“左、右〞換位，不等式變號，“極大〞變“極小〞(4)對稱性:對偶問題的對偶是原問題.9例：寫出下面線性規劃的對偶規劃模型：10112、非對稱形式的對偶關系：〔1〕原問題對偶問題〔特點：對偶變量符號不限，系數陣轉置〕(特點：等式約束)12〔2〕怎樣寫出非對稱形式的對偶問題？把一個等式約束寫成兩個不等式約束，再根據對稱形式的對偶關系定義寫出；按照原始-對偶表直接寫出；〔3〕原始-對偶表13

原問題（或對偶問題）

對偶問題（或原問題）

目標函數MaxZ目標函數MinW約束條件數：m個第i個約束條件類型為“≤”第i個約束條件類型為“≥”第i個約束條件類型為“=”

對偶變量數：m個第i個變量≥0第i個變量≤0第i個變量是自由變量

決策變量數：n個第j個變量≥0第j個變量≤0第j個變量是自由變量

約束條件數：n第j個約束條件類型為“≥”第j個約束條件類型為“≤”第j個約束條件類型為“=”

14課堂練習：寫出下面線性規劃的對偶規劃：15下面的答案哪一個是正確的？為什么？〔原問題是極小化問題，因此應從原始對偶表的右邊往左邊查！〕√

×

16原始-對偶表規那么(1)假設原問題是極大化問題，那么對偶問題就是極小化問題；假設原問題是極小化問題，那么對偶問題就是極大化問題.(2)在原問題和對偶問題中，約束右端向量與目標函數中系數向量恰好對換.(3)對于極小化問題的“≥〞型約束(極大化問題的“≤〞型約束)，相應的對偶變量有非負限制；對于極小化問題的“≤〞型約束(極大化問題的“≥〞型約束)，相應的對偶變量有非正限制；對于原問題的“＝〞型約束，相應的對偶變量無正負限制.17(4)對于極小化問題的具有非負限制的變量(極大化問題的具有非正限制的變量)，在其對偶問題中，相應的約束為“≤〞型不等式；對于極小化問題的具有非正限制的變量(極大化問題的具有非負限制的變量)，在其對偶問題中，相應的約束為“≥〞型不等式；對于原問題中無正負限制的變量，在其對偶問題中，相應的約束為等式。18練習：寫出下面線性規劃的對偶規劃模型：19第二節對偶問題的根本性質

1對稱性：對偶問題的對偶是原問題。2弱對偶性：CX≤Yb3無界性假設原問題(對偶問題)為無界解，那么其對偶問題(原問題)無可行解。4可行解是最優解的性質設X、Y分別為LP和DP的可行解，當CX=Yb時，X、Y為最優解。5對偶定理假設原問題有最優解，那么對偶問題也有最優解，且目標函數值相等。6互補松弛性

，201單純形法的矩陣描述令：212線性規劃的對偶定理

弱對偶定理定理對偶問題(min)的任何可行解Y0，其目標函數值總是不小于原問題(max)任何可行解X0的目標函數值為了便于討論，下面不妨總是假設22弱對偶定理推論max問題的任何可行解目標函數值是其對偶min問題目標函數值的下限；min問題的任何可行解目標函數值是其對偶max問題目標函數值的上限如果原max(min)問題為無界解，那么其對偶min(max)問題無可行解如果原max(min)問題有可行解，其對偶min(max)問題無可行解，那么原問題為無界解23最優性〔解〕判別定理定理假設原問題的某個可行解X0的目標函數值與對偶問題某個可行解Y0的目標函數值相等，那么X0,Y0分別是相應問題的最優解。證：設X是LP問題的任一個可行解,那么由弱對偶定理推論1，得CX0=Y0bCX,既X0是LP問題的最優解。同理Y0是DP問題的最優解。證畢。2.3主〔強〕對偶定理定理如果原問題和對偶問題都有可行解，那么它們都有最優解，且它們的最優解的目標函數值相等。證：由弱對偶定理推論1可知，原問題和對偶問題的目標函數有界，故一定存在最優解。又由YAC，Y0及w=Yb=CBB—1b=z知，當原問題為最優解時，其對偶問題的解為可行解，且有w=z，由最優性知，這時兩者的解都為最優解。24一般而言，原問題及其對偶問題的解的情況有以下三種：(1)兩個問題都有有限最優解；(2)兩個問題都無可行解；(3)一個問題有無界解，另一個問題無可行解。252.4.互補松弛定理26minz=6x1+8x2+3x3

s.t.

x1+x2

≥1

x1+2x2+x3≥-1

x1,x2,x3≥0求解以下線性規劃問題LP

：互補松弛定理的應用27maxw=y1-y2

s.t.

y1+y2≤6

y1+2y2≤8

y2≤3

y1,y2≥0寫出對偶問題DP：利用圖解法，可以求得DP的最優解為

(y1，y2)T=(6，0)T28得到對偶問題各松弛變量的值即對偶問題的最優解和最優目標函數值為根據互補松弛定理，以下的互補松弛關系成立由得到由 得到由 得到29因此原始問題的約束條件x1+x2

-x4

=1x1+2x2+x3

-x5=-1成為

x1

=1x1-x5=-1由此得到

x1=1，x5=2即原始問題的最優解為

X=(x1，x2，x3，x4，x5)T=(1，0，0，0，2)T z=630例2：給定線性規劃問題，原問題為其對偶問題為設用圖解法求得對偶問題的最優解為試用互補松弛定理求原問題的最優解。3132第三節影子價格對偶問題解的經濟含義分析：

從單純形法的矩陣描述中，目標函數取值和檢驗數

中都有乘子設B是

的最優基矩陣，由強對偶定理知由此或33下面圖解闡述影子價格的直觀含義：

對偶問題解的經濟含義：由上面分析——對偶問題解中變量yi的經濟含義是在其他條件不變的情況下，單位第i種“資源〞變化所引起的目標函數最優值的變化。所以，yi描述了原始線性規劃問題到達最優時〔各種“資源〞都處于最優的配置時〕，第i種“資源〞的某種“價值〞，故稱其為第i種“資源〞的影子價格。34

x1x2D可行域1350=50x1+30x2〔15，20〕〔P〕maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥02x1+x2=504x1+3x2=120L0：50x1+30x2王老板的家具生產模型的圖解：35影子價格的直觀含義：x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2

D可行域〔P〕maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥02x1+x2=514x1+3x2=1211365=50x1+30x21355=50x1+30x236影子價格的特點：影子價格是對偶解的一個十分形象的名稱，它既說明對偶解是對系統內部資源在當前的最優利用配置下的一種客觀估價，又說明它是一種虛擬的價格〔或價值的影象〕而不是真實的價格.特點1、影子價格是對系統資源的一種內部最優估價，只有當系統到達最優狀態時才可能賦予資源這種價值。特點2、系統資源的一種動態價格體系，影子價格的大小與系統的價值取向有關，并受系統狀態變化的影響。系統環境的任何變化都可能會引起影子價格的變化。37特點3、影子價格的大小客觀地反映資源在系統內的稀缺程度。如果某種資源在系統內供大于求，盡管它有實實在在的市場價格，但它在系統內的影子價格卻為零，而影子價格越高，資源在系統內越稀缺。特點4、影子價格是一種邊際價值，其與經濟學中的邊際本錢的概念相同。因而，在經濟管理中十分重要的應用價值。企業管理者可以根據資源在企業內部的影子價格的大小決定企業的經營策略。

特點5、對偶解準確的經濟意義與線性規劃模型的構造方法有關，模型構造方法的不同有時會導致對偶解的不同經濟解釋。38第四節:對偶單純形法對偶單純形法的根本思想對偶單純形法的根本思想是：從原規劃的一個根本解出發，此根本解不一定可行，但它對應著一個對偶可行解〔檢驗數非正〕，所以也可以說是從一個對偶可行解出發；然后檢驗原規劃的根本解是否可行，即是否有負的分量，如果有小于零的分量，那么進行迭代，求另一個根本解，此根本解對應著另一個對偶可行解〔檢驗數非正〕。如果得到的根本解的分量皆非負那么該根本解為最優解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性〔即檢驗數非正〕，使原規劃的根本解由不可行逐步變為可行，當同時得到對偶規劃與原規劃的可行解時，便得到原規劃的最優解。39對偶單純形法在什么情況下使用:應用前提：有一個解，其對應的基滿足:①單純形表的檢驗數行全部非正〔對偶可行解〕；②變量取值可有負數〔非可行解〕。注：對偶單純形法是通過矩陣行變換運算，使所有相應變量取值均為非負數,即得到最優單純形表。單純形法與對偶單純形法的區別：在單純形法的迭代過程中，始終保持右端列(目標函數值除外)非負，即保持原問題的可行性；而在對偶單純形法中，要保持所有判別數非正(對于極小化問題)，即保持對偶可行性。40三、對偶單純形法的實施1、使用條件：①檢驗數全部≤0；②解答列至少一個元素<0；2、實施對偶單純形法的根本原那么：在保持對偶可行的前提下進行基變換：每一次迭代過程中取出基變量中的一個負分量作為換出變量去替換某個非基變量〔作為換入變量〕，使原始問題的非可行解向可行解靠近。413、計算步驟：①建立初始單純形表，計算檢驗數行。解答列≥0——已得最優解；至少一個元素<0,轉下步;解答列≥0——原始單純形法；至少一個元素<0,另外處理；

檢驗數全部≤0（非基變量檢驗數<0）至少一個檢驗數>042基變換：先確定換出變量：解答列中的負元素〔一般選最小的負元素〕對應的基變量出基；即相應的行為主元行。43然后確定換入變量——原那么是：在保持對偶可行的前提下，減少原始問題的不可行性。如果〔最小比值原那么〕，可行那么選為換入變量，相應的列為主元列，可行主元行和主元列交叉處的元素為主元素。44按主元素進行換基迭代〔旋轉運算、樞運算〕，將主元素變成1，主元列變成單位向量，得到新的單純行表。繼續以上步驟，直至求出最優解。45對偶單純形法的計算步驟：(1)給定一個初始對偶可行的根本可行解，設相應的基為B.(2)若則停止計算，現行對偶可行的基本解就是最優解.否則，令(3)若對所有則停止計算，原問題無可行解。否則，令(4)以為主元進行主元消去，返回步驟(2)。46對偶單純形法的計算方法基解

X1X2X3X4X5X1X4X555-9

11100021100-4-601檢驗數

0-1-200比值

--1/41/3----基解

X1X2X3X4X5X1X4X211/41/29/4

10-1/201/400-211/20

12/30-1/4檢驗數

00-1/20-1/4比值

迭代準典式：maxZ=-1x2-2x3s.t.x1+x2+x3=52x2+x3+x4=5-

4x2-6x3+x5=-9x1

，x2，x3

，x4

，x5

≥047minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0maxW’=–120y1–50y2s.t.4y1+2y2–y3

=503y1+y2–y4

=30y1，y2，y3

，y4

≥0

maxW’=–120y1–50y2s.t.–4y1–2y2+y3

=–50–3y1–y2+y4

=–30y1，y2，y3

，y4

≥0

對偶單純形法的計算方法48maxW’=–120y1–50y2s.t.–4y1–2y2+y3

=–50–3y1–y2+y4

=–30y1，y2，y3

，y4

≥0

基解y1y2y3y4y3-50-4-210y4-30-3-101檢驗數j-120-5000-120/-4-50/-2------對偶單純形法的計算方法49基解y1y2y3y4y3-50-4-210y4-30-3-101檢驗數j-120-5000y22521-1/20y4-5-10-1/21檢驗數j-200-25020---50---基解y1y2y3y4y22521-1/20y4-5-10-1/21檢驗數j-200-250y15101/2-1y21501-3/2-2檢驗數j00-15-20對偶單純形法的計算方法50概念：靈敏度分析是指對系統或事物因周圍條件變化顯示出來的敏感程度的分析.第五節靈敏度分析敏感性分析的重要性在于向決策者提供線性規劃問題的最優解所能適應的環境條件變化的范圍，環境條件變化時可能對經營狀況帶來何種影響，產生影響后的解決途徑。51敏感性分析的類型：1、模型中各個參數在什么范圍變化時，最優基不發生改變。2、模型中參數變化已經超出上述范圍時，如何快速確定新的最優基和最優解——新的最優決策方案。敏感性分析的方法：敏感性分析方法的關鍵是從單純形法對應的I表中參數的變化來分析B表中對應參數的變化情況來答復決策者所關心問題。52靈敏度分析的步驟可歸納如下：1.將參數的改變通過計算反映到最終單純行表上來：2.檢查原問題是否仍為可行解；3.檢查對偶問題是否仍為可行解；4.按下表所列情況得出結論或決定繼續計算步驟。具體計算方法是，按下列公式計算出由參數的變化而引起的最終單純行表上有關數字的變化。53原問題對偶問題結論或繼續計算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優解或最優基不變可以用單純形法繼續迭代求最優解可以用對偶單純形法繼續迭代求最優解引進人工變量，編制新的單純形表重新計算線性規劃原問題單純形法對應的I表中參數的變化將引起B表中對應參數的變化情況表：54線性規劃問題I表與B表的關系給定符合典式的線性規劃問題如下：MaxZ=CX+0XSAX+IXS=bX，XS≥0其中C=〔c1，c2，…，cn〕X=x1x2...xnXS=xS1xS2...xSmA=a11a12…a1na21a22…a2n………………..am1am2…amnb=b1b2...bm55線性規劃問題I表與B表的關系對于前面給定符合典式的線性規劃問題中，初始基矩陣為I，基變量為即松弛變量。其對應的初始單純形表如下：I表（初始表）基解

XBXNXSXSb

BNIj

CB

CN

056對初始單純形表進行迭代之后得到B為最優基矩陣，那么初始典式和初始單純形表可以改寫為如下：MaxZ=CBXB+CNXN+0XSBXB+NXN+IXS=bXB

，XN

，XS≥0基解

XBXNXSXSb

BNIj

CB

CN

057對初始單純形表進行迭代之后得到B為最優基矩陣，那么初始典式可以表示為最終典式如下：MaxZ=CBXB+CNXN+0XSBXB+NXN+IXS=bXB

，XN

，XS≥0MaxZ=CBB-1b+〔CN-CBB-1N〕XN+〔0-CBB-1I〕XSXB+B-1NXN+B-1IXS=B-1bXB，XN，XS≥058最終典式所對應的單純形表：B表〔最終表〕MaxZ=CBB-1b+〔CN-CBB-1N〕XN+〔0-CBB-1I〕XSXB+B-1NXN+B-1IXS=B-1bXB，XN，XS≥0基解

XBXNXSXBB-1b

IB-1NB-1j

0

CN–CBB

-1N-

CBB

-159一、分析C的變化當是基變量的目標系數時，若要保持最優解（或基）不變，則必須滿足：基解

XB

XN

XSXSb

BNIj

CB

CN

0對應I式的單純形表——

I

表基解

XB

XN

XSXBB-1b

IB-1NB-1j

0

CN

–CBB

-1N-

CBB

-1對應B

式的單純形表——B

表60非基變量在目標函數中系數的靈敏度分析在線性規劃問題中，對c2進行靈敏度分析。例maxz=-x1-x2+4x3

s.t.

x1+x2+2x3≤9

x1+x2-x3≤2

-x1+x2+x3≤4

x1,x2,x3≥061得到以上問題的最優單純形表：

62當c2’=c2+時，相應的單純形表為：

63要使原來的解仍保持最優解，就要zj-cj≤0〔j=1,2,3,4,5〕，即由此得到，，即當c235/12時，最優解保持不變

64maxz=-x1-x2+4x3

s.t.

x1+x2+2x3≤9

x1+x2-x3≤2

-x1+x2+x3≤4

x1,x2,x3≥0在線性規劃問題中，對c1進行靈敏度分析。例65得到以上問題的最優單純形表：

66當c1’=c1+時，相應的單純形表為：

67要使原來的基仍保持最優基，就要zj-cj≤0〔j=1,2,3,4,5〕，即由此得到，-33，即當-4c12時，最優基保持不變

68二、分析b的變化當I表中b變化為時，在B表中將只有解列

發生變化，為了保證最優基不變則必須滿足：69maxz=-x1-x2+4x3

s.t.

x1+x2+2x