對偶理論和靈敏度分析

第二章對偶理論和靈敏度分析一、單純形法的矩陣描述CjC1C2……………Cj………….CnCBXBbx1x2…xj…

xnxB1xB2…xBnb1b2...bna11a12…a1j

…

a1na21a22…a2j

…

a2n…an1an2…anj

…

ann檢驗數j1對偶理論和靈敏度分析共128頁，您現在瀏覽的是第1頁!設線性規(guī)劃問題:

目標函數maxz=CX;約束條件AX≤b;非負條件X≥02對偶理論和靈敏度分析共128頁，您現在瀏覽的是第2頁!給這線性規(guī)劃問題的約約束條件加入松弛變量以后，得到標準型：

maxz=CX+0Xs;

AX+IXs=b;X，X

s≥0這里I是m×m單位矩陣。

3對偶理論和靈敏度分析共128頁，您現在瀏覽的是第3頁!令非基變量=0；由上式得到：

4對偶理論和靈敏度分析共128頁，您現在瀏覽的是第4頁!可以先從第1列開始以為主元素,進行變換5對偶理論和靈敏度分析共128頁，您現在瀏覽的是第5頁!然后構造含有（1）列，而其他列都是單位列的矩陣

6對偶理論和靈敏度分析共128頁，您現在瀏覽的是第6頁!而后以第2列的為主元素，進行變換7對偶理論和靈敏度分析共128頁，您現在瀏覽的是第7頁!可得到

8對偶理論和靈敏度分析共128頁，您現在瀏覽的是第8頁!求單純形表的基矩陣的逆矩陣也可以用這方法例：用改進單純形法求解線性規(guī)劃問題：9對偶理論和靈敏度分析共128頁，您現在瀏覽的是第9頁!（2）計算非基變量的檢驗數，確定換入變量。

10對偶理論和靈敏度分析共128頁，您現在瀏覽的是第10頁!（4）基變換計算將新的基單位矩陣。計算：11對偶理論和靈敏度分析共128頁，您現在瀏覽的是第11頁!（6）計算RHS

12對偶理論和靈敏度分析共128頁，您現在瀏覽的是第12頁!第2步重復第1步的計算步驟從新的基，基變量開始。13對偶理論和靈敏度分析共128頁，您現在瀏覽的是第13頁!(3)確定換出變量計算：表示選擇>0的元素14對偶理論和靈敏度分析共128頁，您現在瀏覽的是第14頁!計算RHS

15對偶理論和靈敏度分析共128頁，您現在瀏覽的是第15頁!

第3步從新的基，基變量開始,

重復第1步的計算步驟.

16對偶理論和靈敏度分析共128頁，您現在瀏覽的是第16頁!(3)確定換出變量計算：表示選擇>0的進行計算17對偶理論和靈敏度分析共128頁，您現在瀏覽的是第17頁!計算B逆矩陣18對偶理論和靈敏度分析共128頁，您現在瀏覽的是第18頁!計算非基變量的檢驗數19對偶理論和靈敏度分析共128頁，您現在瀏覽的是第19頁!目標函數的值

20對偶理論和靈敏度分析共128頁，您現在瀏覽的是第20頁!第二章對偶理論和靈敏度分析第二個問題：出讓定價假設出租單位設備臺時的租金和出讓單位原材料A、B所得利潤分別為y1、y2、y3原本用于生產I產品的設備臺時，如若出讓，不應低于自行生產帶來的利潤，否則寧愿自己生產。于是有

y1+4y2≥2同理，對Ⅱ產品而言，則有

2y1+4y3≥3設備臺時出讓的收益（希望出讓的收益最少值）min=8y1+16y2+12y3顯然還有y1，y2，y3≥021對偶理論和靈敏度分析共128頁，您現在瀏覽的是第21頁!第二章對偶理論和靈敏度分析原問題與對偶問題的表達形式22對偶理論和靈敏度分析共128頁，您現在瀏覽的是第22頁!原問題與對偶問題的關系

這兩個式子之間的變換關系稱為“對稱形式的對偶關系”。

23對偶理論和靈敏度分析共128頁，您現在瀏覽的是第23頁!第二章對偶理論和靈敏度分析2、非標準型的對偶變換含等式約束時，將等式約束分解為兩個不等式約束條件。

24對偶理論和靈敏度分析共128頁，您現在瀏覽的是第24頁!原問題與對偶問題的關系，歸納如下：（原始－對偶表）原問題（或對偶問題）對偶問題（或原問題）目標函數maxz變量n個≥0≤0

無約束目標函數minw約束條件n個≥≤＝約束條件m個≤≥＝約束條件右端項目標函數變量的系數變量m個≥0≤0無約束目標函數變量的系數約束條件右端項25對偶理論和靈敏度分析共128頁，您現在瀏覽的是第25頁!第二章對偶理論和靈敏度分析例：試述下列線性規(guī)劃問題分對偶問題minz=2x1+3x2-5x3

+x4

x1+x2-3x3

+x4

≥5

2x1+2x3-x4

≤4

x2+x3

+x4=6x1≤0;x2,x3≥0;x4無約束Maxz’＝5y1＋4y2＋6y3

y1＋2y2≥2

y1＋y3≤3－3y1＋2y2＋y3≤－5y1－y2＋y3＝1

y1≥

0，y2

≤0，y3無約束

26對偶理論和靈敏度分析共128頁，您現在瀏覽的是第26頁!哪一個正確？前一個。原問題是極小化問題，因此應從原始對偶表的右邊往左邊查！27對偶理論和靈敏度分析共128頁，您現在瀏覽的是第27頁!證明思路：弱對偶性推論：極大化問題的任意一個可行解所對應的目標函數值是其對偶問題最優(yōu)目標函數值的一個下界。極小化問題的任意一個可行解所對應的目標函數值是其對偶問題最優(yōu)目標函數值的一個上界。由（L）

左乘，得由（D）

右乘，得28對偶理論和靈敏度分析共128頁，您現在瀏覽的是第28頁!第二章對偶理論和靈敏度分析證明思路：由弱對偶性和已知條件易證。4、主對偶定理如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標函數值相等。證明要點：部分——證明兩者均有最優(yōu)解。由于原始問題和對偶問題均可行，根據弱對偶定理知兩者均有界，于是均有最優(yōu)解。第二部分——證明在達到最優(yōu)時，兩個問題的目標函數值相等。29對偶理論和靈敏度分析共128頁，您現在瀏覽的是第29頁!第二章對偶理論和靈敏度分析該定理的證明告訴我們一個非常重要的概念：對偶變量的最優(yōu)解等于原問題松弛變量的機會成本即對偶變量的最優(yōu)解是原問題資源的影子價格5、互補松弛定理若X0,Y0分別是原問題和對偶問題的可行解。那么Y0Xs＝0和X0Ys＝0，當且僅當X0,Y0為最優(yōu)解。證明：1）Y0Xs＝0和X0Ys＝0時，X0,Y0為最優(yōu)解2）當X0,Y0為最優(yōu)解時，Y0Xs＝0，X0Ys＝030對偶理論和靈敏度分析共128頁，您現在瀏覽的是第30頁!第二章對偶理論和靈敏度分析例5：已知線性規(guī)劃問題已知其對偶問題的最優(yōu)解為y1*=4/5,y2*=3/5,z=5。試用對偶理論找出問題的最優(yōu)解。解：31對偶理論和靈敏度分析共128頁，您現在瀏覽的是第31頁!第二章對偶理論和靈敏度分析影子價格不是資源的實際價格，而是資源配置結構的反映，是在其它數據相對穩(wěn)定的條件下某種資源增加一個單位導致的目標函數值的增量變化。對資源i總存量的評估：購進or出讓對資源i當前分配量的評估：增加or減少①它表明了當前的資源配置狀況，告訴經營者應當優(yōu)先增加何種資源，才能獲利更多。②告訴經營者以怎樣的代價去取得緊缺資源。③提示設備出租或原材料轉讓的基價。④告訴經營者補給緊缺資源的數量，不要盲目大量補給。⑤借助影子價格進行內部核算。特別注意32對偶理論和靈敏度分析共128頁，您現在瀏覽的是第32頁!第二章對偶理論和靈敏度分析對偶單純形的計算步驟如下：1確定出變量找非可行解中最小者，即min{bi|bi<0}，設第i*行的最負，則i*行稱為主行，該行對應的基變量為換出變量xi*2確定換入變量檢查xl所在行的各系數alj（j＝1,2…n)，若所有alj

≥0，則無可行解，停止計算。若存在alj≤0，

33對偶理論和靈敏度分析共128頁，您現在瀏覽的是第33頁!解：化原問題為適合對偶解法的標準建立初始單純形表：34對偶理論和靈敏度分析共128頁，您現在瀏覽的是第34頁!七、靈敏度分析1、靈敏度分析的含義和內容

什麼是靈敏度分析？研究線性規(guī)劃模型某些參數或限制量的變化對最優(yōu)解的影響及其程度的分析過程稱為靈敏度分析或（優(yōu)化后分析）。第二章對偶理論和靈敏度分析

35對偶理論和靈敏度分析共128頁，您現在瀏覽的是第35頁!①這些系數在什麼范圍內發(fā)生變化時，最優(yōu)基不變（即最優(yōu)解或最優(yōu)解結構不變）？②系數變化超出上述范圍時，如何用最簡便的方法求出新的最優(yōu)解？2、

手工進行靈敏度分析的基本原則

1)在最優(yōu)表格的基礎上進行；2)盡量減少附加計算工作量；36對偶理論和靈敏度分析共128頁，您現在瀏覽的是第36頁!

用表格單純形法求解如下：37對偶理論和靈敏度分析共128頁，您現在瀏覽的是第37頁!價值系數Cj變化影響檢驗數目標函數中價值系數Cj的變化分析

第二章對偶理論和靈敏度分析38對偶理論和靈敏度分析共128頁，您現在瀏覽的是第38頁!

例：c3發(fā)生變化時，=c3-z3=c3-[2×（-1）+3×2]=c3-4≤0，得c3≤4。即當c3≤4時，最優(yōu)解不變；否則>0,可使用原始單純形法繼續(xù)迭代求出新的最優(yōu)解。第二章對偶理論和靈敏度分析

如從最優(yōu)表中，C3是非基變量x3的系數，當C3變化時，只會影響到3。39對偶理論和靈敏度分析共128頁，您現在瀏覽的是第39頁!例：當c1發(fā)生變化時，仍用c1代表x1的價值系數（看成待定參數），原最優(yōu)表格即為：012-1/31/3

cjxj

CB

XB

b

c1

3300

X1X2X3X4X5

c1

3

X1X2

1210-14/3-1/3

-Z

-c1-600c1-31-4/3c11/3c1-1

第二章對偶理論和靈敏度分析40對偶理論和靈敏度分析共128頁，您現在瀏覽的是第40頁!第二章對偶理論和靈敏度分析資源數量bi變換的分析當bi發(fā)生變化時，將影響所有基變量的取值。為什麼？因為：因為：41對偶理論和靈敏度分析共128頁，您現在瀏覽的是第41頁!10-14/3-1/3012-1/31/312X1X22300-1-5/3-1/3-8-Z233000-Z3/19/1111101470139X4

X500

j23300

x1x2x3x4x5

Cj

b

xj

XBCB仍然來看上例的最優(yōu)表格：

42對偶理論和靈敏度分析共128頁，您現在瀏覽的是第42頁!7.3技術系數αij的變化

分兩種情況來討論技術系數αij的變化，下面以具體例子來說明。

例9分析在原計劃中是否應該安排一種新產品。以第1章例1為例。設該廠除了生產產品Ⅰ，Ⅱ外，現有一種新產品III。已知生產產品III，每件需消耗原材料A，B各為6kg，3kg，使用設備2臺時；每件可獲利5元。問該廠是否應生產該產品和生產多少?43對偶理論和靈敏度分析共128頁，您現在瀏覽的是第43頁!

分析該問題的步驟(2)是：

44對偶理論和靈敏度分析共128頁，您現在瀏覽的是第44頁!分析該問題的步驟(3)是：(3)將x3′作為換入變量，x5作為換出變量，進行迭代，求出最優(yōu)解。計算結果見表2-13(b)，這時得最優(yōu)解：x1=1,x2=1.5，x3′=2?？偟睦麧櫈?6.5元。比原計劃增加了2.5元。45對偶理論和靈敏度分析共128頁，您現在瀏覽的是第45頁!例10分析原計劃生產產品的工藝結構發(fā)生變化。仍以第1章例1為例，若原計劃生產產品Ⅰ的工藝結構有了改進，這時有關它的技術系數向量變?yōu)镻1′=(2,5,2)T，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響?46對偶理論和靈敏度分析共128頁，您現在瀏覽的是第46頁!表2-14可見x1′為換入變量，x1為換出變量，經過迭代。得到表2-15

47對偶理論和靈敏度分析共128頁，您現在瀏覽的是第47頁!表2-15表明原問題和對偶問題的解都是可行解。所以表中的結果已是最優(yōu)解。即應當生產產品Ⅰ′，3.2單位；生產產品Ⅱ，0.8單位?？色@利15.2元。注意：若碰到原問題和對偶問題均為非可行解時，就需要引進人工變量后重新求解。48對偶理論和靈敏度分析共128頁，您現在瀏覽的是第48頁!表2-16將表2-16的x1′變換為基變量，替換x1，得表2-17。

49對偶理論和靈敏度分析共128頁，您現在瀏覽的是第49頁!引入人工變量x6后，便為-x2-0.5x3+0.4x4+x6=2.4將x6作為基變量代替x2，填入表2-17，得到表2-18。50對偶理論和靈敏度分析共128頁，您現在瀏覽的是第50頁!這時可按單純形法求解。X4為換入變量，x6為換出變量。經基變換運算后，得到表2-19的上表。在表2-19的上表中，確定x2為換入變量，x5為換出變量。經基變換運算后，得到表2-19的下表。此表的所有檢驗數都為非正，已得最優(yōu)解。最優(yōu)生產方案為生產產品Ⅰ′，0.667單位；產品Ⅱ，2.667單位，可得最大利潤10.67元。

51對偶理論和靈敏度分析共128頁，您現在瀏覽的是第51頁!系數陣A的元素發(fā)生變化：（1）增加1個新變量：相當于系數陣A增加1列

如開發(fā)出一種新產品，已知其有關工藝參數（或消耗的資源量）和單位產品利潤，設該種產品的產量為xk，則ck和Pk已知，需要進行“是否投產”的決策。如例中欲增加產品D，單件利潤為c6=5千元，工時消耗與材料消耗為52對偶理論和靈敏度分析共128頁，您現在瀏覽的是第52頁!

23

CB

XB

cj

xjb

θj

X1X2X3X4X5X6

X1

X2

1

21/(5/3)2/(1/3)

-Z

-800-1-5/3-1/32/3

53

X6X23/59/53/50-3/54/5-1/51-1/5111/5-3/52/50

-Z--42/5-2/50-3/5-11/5-1/50

23300510-14/3-1/35/3012-1/31/31/3

-Z

-800-1-5/3-1/32/3-Z--42/52/50-3/5-11/5-1/50

23

CB

XB

cj

xjb

θj

X1X2X3X4X5X6

X1

X2

1

21/(5/3)2/(1/3)

-Z

-800-1-5/3-1/32/3

53

X6X23/59/53/50-3/54/5-1/51-1/5111/5-3/52/50

-Z--42/5-2/50-3/5-11/5-1/50

23300510-14/3-1/35/3012-1/31/31/3

-Z53對偶理論和靈敏度分析共128頁，您現在瀏覽的是第53頁!(2)增加1個約束條件：

相當于系數陣A增加1行

首先將原最優(yōu)解代入新增約束檢查是否滿足？是，則說明新增約束不影響最優(yōu)解。否則再作下面的討論：將新增約束標準化，添加到原最優(yōu)表格中（相當于約束矩陣新增1行）；進行規(guī)格化處理——用矩陣的行變換將當前基變成單位陣；54對偶理論和靈敏度分析共128頁，您現在瀏覽的是第54頁!-Z

CB

XB

cj

xjb

233005

X1X2X3X4X5X6

230

X1X2

X6

12510-14/3-1/30012-1/31/30221001

230

X1X2

X6

12-110-14/3-1/30012-1/31/3000-1-201

00-1-5/3-1/30

比

值

------15/6------

230

X1X2

X4

1/313/61/210-5/30-1/32/30113/601/3-1/6001/210-1/2-Z

-43/6-43/600-1/60-1/3-5/6-Z-800-1-5/3-1/3055對偶理論和靈敏度分析共128頁，您現在瀏覽的是第55頁!(1)對含有某參變量t的參數線性規(guī)劃問題。先令t=0，用單純形法求出最優(yōu)解；(2)用靈敏度分析法，將參變量t直接反映到最終表中；(3)當參變量t連續(xù)變大或變小時，觀察b列和檢驗數行各數字的變化。若在b列首先出現某負值時，則以它對應的變量為換出變量；于是用對偶單純形法迭代一步。若在檢驗數行首先出現某正值時，則將它對應的變量為換入變量；用單純形法迭代一步；56對偶理論和靈敏度分析共128頁，您現在瀏覽的是第56頁!8.1參數c的變化

例12試分析以下參數線性規(guī)劃問題。當參數t≥0時的最優(yōu)解變化。57對偶理論和靈敏度分析共128頁，您現在瀏覽的是第57頁!令t=0，用單純形法求解的結果，

見表2-20。

58對偶理論和靈敏度分析共128頁，您現在瀏覽的是第58頁!當t值變化，在σ4≤0，即0≤t≤9/7時，為最優(yōu)解(2,6,2,0,0)T；

當t值增大，t≥(3/2)/(7/6)=9/7時，在檢驗數行首先出現σ4≥0；表示還可以繼續(xù)改進。t=9/7為臨界點。當t＞9/7時，σ4＞0，這時x4作為換入變量。用單純形法迭代一步，得表2-22。

59對偶理論和靈敏度分析共128頁，您現在瀏覽的是第59頁!8.2參數b的變化分析例13分析以下線性規(guī)劃問題，當t≥0時，其最優(yōu)解的變化范圍。

60對偶理論和靈敏度分析共128頁，您現在瀏覽的是第60頁!令t=0，用單純形法迭代兩次，求解的結果，見

表2-24。

61對偶理論和靈敏度分析共128頁，您現在瀏覽的是第61頁!在表2-25中進行分析，當t增大至t≥2時，

則b≤0；即0≤t≤2時，最優(yōu)解為(2-t.4,0,0)T。

當t＞2時，則b1＜0；故將x1作為換出變量，用對偶單純形法迭代一步，得表2-26

62對偶理論和靈敏度分析共128頁，您現在瀏覽的是第62頁!第二章對偶理論和靈敏度分析.已知線性規(guī)劃問題

s.t.

用單純形方法求解得最終單純形如下表

63對偶理論和靈敏度分析共128頁，您現在瀏覽的是第63頁!試確定:(1)當目標函數變?yōu)闀r,最優(yōu)解會出現什么變化?(2)當目標函數變?yōu)闀r,在什么范圍內變化,最優(yōu)解不變?(3)若第2個約束條件的右端項增大到32時,分析最優(yōu)解的變化;(4)若第2個約束條件變?yōu)?分析在什么范圍內變化,表中基為最優(yōu)基?64對偶理論和靈敏度分析共128頁，您現在瀏覽的是第64頁!分析下列參數規(guī)劃問題中當θ變化時最優(yōu)解的變化情況.1、65對偶理論和靈敏度分析共128頁，您現在瀏覽的是第65頁!第二章對偶理論和靈敏度分析初始單純形表和最終單純形矩陣表示如下:CjCNCB00XSbXNXBXSXS

b

NBI檢驗數jCjCNCB0CBXBbXNXBXSXBB-1bB-1NBB-1B-1

檢驗數jCN-CBB-1N-CBB-166對偶理論和靈敏度分析共128頁，您現在瀏覽的是第66頁!二、改進單純形法求解線性規(guī)劃問題的關鍵是計算以下介紹一種比較簡便的計算方法設m?m系數矩陣A，求其逆矩陣。67對偶理論和靈敏度分析共128頁，您現在瀏覽的是第67頁!68對偶理論和靈敏度分析共128頁，您現在瀏覽的是第68頁!可得到：

69對偶理論和靈敏度分析共128頁，您現在瀏覽的是第69頁!然后構造含有（2）列，而其他列都是單位列的矩陣

70對偶理論和靈敏度分析共128頁，您現在瀏覽的是第70頁!重復以上的步驟，直到獲得

71對偶理論和靈敏度分析共128頁，您現在瀏覽的是第71頁!

第1步：確定初始基，初始基變量;確定換入，換出變量。

（1）確定初始基和初始基變量：

72對偶理論和靈敏度分析共128頁，您現在瀏覽的是第72頁!(3)確定換出變量計算：表示選擇>0的元素73對偶理論和靈敏度分析共128頁，您現在瀏覽的是第73頁!（5）計算非基變量的系數矩陣

74對偶理論和靈敏度分析共128頁，您現在瀏覽的是第74頁!第1步計算結束后的結果

75對偶理論和靈敏度分析共128頁，您現在瀏覽的是第75頁!計算非基變量的檢驗數，確定換入變量。76對偶理論和靈敏度分析共128頁，您現在瀏覽的是第76頁!

77對偶理論和靈敏度分析共128頁，您現在瀏覽的是第77頁!第2步計算結束后的結果78對偶理論和靈敏度分析共128頁，您現在瀏覽的是第78頁!計算非基變量檢驗數，檢查檢驗數，確定換入變量79對偶理論和靈敏度分析共128頁，您現在瀏覽的是第79頁!新的基

80對偶理論和靈敏度分析共128頁，您現在瀏覽的是第80頁!81對偶理論和靈敏度分析共128頁，您現在瀏覽的是第81頁!最優(yōu)解

82對偶理論和靈敏度分析共128頁，您現在瀏覽的是第82頁!第二章對偶理論和靈敏度分析若章中例一關于某廠的生產計劃問題，現有另一企業(yè)想租賃其設備。廠方為了在談判時心中有數，需掌握設備臺時費用的最低價碼，以便衡量對方出價，對出租與否做出抉擇。在這個問題上廠長面臨著兩種選擇：自行生產或出租設備。首先要弄清兩個問題：①合理安排生產能取得多大利潤?②為保持利潤水平不降低，資源轉讓的最低價格是多少？問題①的最優(yōu)解：x1=4，x2=2，Z*=14。三、對偶問題的提出83對偶理論和靈敏度分析共128頁，您現在瀏覽的是第83頁!第二章對偶理論和靈敏度分析對偶問題的最優(yōu)解：y1=3/2，y2=1/8，y3=0，W*=14兩個問題的目標函數值相等，這不是偶然的，上述兩個問題實際上是一個問題的兩個方面，如果把前者稱為線性規(guī)劃原問題，則后者便是它的對偶問題，反之亦然。對偶問題的最優(yōu)解對應于原問題最優(yōu)單純型法表中，初始基變量的檢驗數的負值。例1的對偶問題的數學模型min=8y1+16y2+12y3

y1+4y2≥2

2y1+4y3≥5y1，y2，y3≥0S.t.MaxZ=

2x1+3x2x1+2x2≤84x1≤16

4x2≤12x1,x2≥0S.t.84對偶理論和靈敏度分析共128頁，您現在瀏覽的是第84頁!第二章對偶理論和靈敏度分析四線性規(guī)劃的對偶理論（一）原問題與對偶問題的關系1、標準(max,)型的對偶變換目標函數由max型變?yōu)閙in型對應原問題每個約束行有一個對偶變量yi，i=1,2,…,m對偶問題約束為型，有n行原問題的價值系數C變換為對偶問題的右端項原問題的右端項

b

變換為對偶問題的價值系數原問題的技術系數矩陣A

轉置后成為對偶問題的技術系數矩陣85對偶理論和靈敏度分析共128頁，您現在瀏覽的是第85頁!例：寫出下面線性規(guī)劃的對偶問題：86對偶理論和靈敏度分析共128頁，您現在瀏覽的是第86頁!第二章對偶理論和靈敏度分析按對稱形式變換關系可寫出它的對偶問題，如上所示。87對偶理論和靈敏度分析共128頁，您現在瀏覽的是第87頁!第二章對偶理論和靈敏度分析

怎樣寫出非對稱形式的對偶問題？把一個等式約束寫成兩個不等式約束，再根據對稱形式的對偶關系定義寫出；按照原始-對偶表直接寫出。88對偶理論和靈敏度分析共128頁，您現在瀏覽的是第88頁!第二章對偶理論和靈敏度分析練習：寫出下面線性規(guī)劃的對偶規(guī)劃89對偶理論和靈敏度分析共128頁，您現在瀏覽的是第89頁!（二）對偶問題的基本性質1、對稱性：對偶問題的對偶是原問題。2、弱對偶性若一對對稱形式的對偶線性規(guī)劃（L）

和（D）

均有可行解，分別為和，則C≤b。90對偶理論和靈敏度分析共128頁，您現在瀏覽的是第90頁!第二章對偶理論和靈敏度分析如果原max(min)問題為無界解，則其對偶min(max)問題無可行解如果原max(min)問題有可行解，其對偶min(max)問題無可行解，則原問題為無界解注：有可能存在原問題和對偶問題同時無可行解的情況。3、最優(yōu)性準則定理

若、分別為對稱形式對偶線性規(guī)劃的可行解，且兩者目標函數的相應值相等，即C＝b，則，分別為原始問題和對偶問題的最優(yōu)解。91對偶理論和靈敏度分析共128頁，您現在瀏覽的是第91頁!第二章對偶理論和靈敏度分析設X0為原問題的最優(yōu)解，它所對應的基矩陣是B，X0=B1

b，則其檢驗數滿足CCBB1A0。令Y0=

CBB1，則有Y0

AC；而對原問題松弛變量的檢驗數有0

CBB1I0，即Y0

0。

顯然Y0為對偶問題的可行解。因此有對偶問題目標函數值，g(Y0)=Y0b=CBB1

b而原問題最優(yōu)解的目標函數值為

f(X0)=CX0=CBB1

b故由最優(yōu)解判別定理可知Y0

為對偶問題的最優(yōu)解。證畢。92對偶理論和靈敏度分析共128頁，您現在瀏覽的是第92頁!第二章對偶理論和靈敏度分析例4：已知線性規(guī)劃問題試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。證明：上述問題的對偶問題是：由約束條件可知對偶問題無可行解，而原問題有可行解。故無最優(yōu)解。

93對偶理論和靈敏度分析共128頁，您現在瀏覽的是第93頁!第二章對偶理論和靈敏度分析這說明yi是右端項bi每增加一個單位對目標函數Z的貢獻。對偶變量yi在經濟上表示原問題第i種資源的邊際價值。對偶變量的值yi*所表示的第i種資源的邊際價值，稱為影子價值。若原問題的價值系數Cj表示單位產值，則yi稱為影子價格。若原問題的價值系數Cj表示單位利潤，則yi稱為影子利潤。五、對偶問題的經濟解釋94對偶理論和靈敏度分析共128頁，您現在瀏覽的是第94頁!第二章對偶理論和靈敏度分析六、對偶單純形法基本思路原單純型迭代要求每步都是基礎可行解達到最優(yōu)解時，檢驗數cj–zj

0(max)或cj–zj

0(min)但對于(min,)型所加的剩余變量無法構成初始基礎可行解，因此通過加人工變量來解決大M法和二階段法較繁能否從剩余變量構成的初始基礎非可行解出發(fā)迭代，但保證檢驗數滿足最優(yōu)條件，cj–zj

0(max)或cj–zj

0(min)，保持對偶問題是基可行解，原問題在非可行解的基礎上，通過逐步迭代達到基可行解。95對偶理論和靈敏度分析共128頁，您現在瀏覽的是第95頁!Xk為換入變量。3、以主元alk

為中心迭代檢查當前基礎解是否為可行解若是，則當前解即為最優(yōu)解否則，返回步驟1。例:用對偶單純形求解96對偶理論和靈敏度分析共128頁，您現在瀏覽的是第96頁!

97對偶理論和靈敏度分析共128頁，您現在瀏覽的是第97頁!靈敏度分析的內容：目標函數的系數變化對最優(yōu)解的影響；約束方程右端系數變化對最優(yōu)解的影響；約束方程組系數陣變化對最優(yōu)解的影響；

回答兩個問題：

第二章對偶理論和靈敏度分析98對偶理論和靈敏度分析共128頁，您現在瀏覽的是第98頁!研究例1-6

引入非負的松弛變量x4,x5,將該LP化為

標準型：第二章對偶理論和靈敏度分析

99對偶理論和靈敏度分析共128頁，您現在瀏覽的是第99頁!10-14/3-1/3012-1/31/3

12

X1X2

233/16/311110036-11

36

X1

X5

20011-20

檢驗數j

00-1-5/3-1/3

檢驗數j

23300

檢驗數j3/19/11111014701

39X4

X500j

23300

x1x2x3x4x5

Cj

b

xj

XBCB100對偶理論和靈敏度分析共128頁，您現在瀏覽的是第100頁!若Cj是非基變量xj的系數當cj是非基變量的價值系數——它的變化只影響j一個檢驗數。第二章對偶理論和靈敏度分析101對偶理論和靈敏度分析共128頁，您現在瀏覽的是第101頁!當cr是基變量xr的價值系數——它的變化將影響所有非基變量的檢驗數，為什麼？

當cr變化時，如能保持，則當前解仍為最優(yōu)解，否則可用單純形法繼續(xù)迭代求出新的最優(yōu)解。將cr看作待定參數，令

解這n-m個不等式，可算出保持最優(yōu)解不變時cr的變化范圍！第二章對偶理論和靈敏度分析102對偶理論和靈敏度分析共128頁，您現在瀏覽的是第102頁!令所有檢驗數小于0，得不等式組：解該不等式組得：

說明當時，最優(yōu)解不變。當c1<3/4時,有應選x4進基,x1出基;

當c1>3時,有,可選x3或x5進基,x2出基.103對偶理論和靈敏度分析共128頁，您現在瀏覽的是第103頁!①保持B-1b≥0,當前的基仍為最優(yōu)基，最優(yōu)解的結構不變（取值改變）；②（B-1b）i<0,當前基為非可行基,但是仍保持為對偶可行基,(為什麼?),可用對偶單純形法求出新的最優(yōu)解；③如何求出保持最優(yōu)基不變的bi的范圍?把bi看作待定參數,令B-1b≥0,求解該不等式組即可；

104對偶理論和靈敏度分析共128頁，您現在瀏覽的是第104頁!原b1=3，現用待定參數b1代替3，則最優(yōu)表中的解答列應為：若b1的變化超出這個范圍，則解答列中至少有一個元素小于0，可用對偶單純形法迭代求出新的最優(yōu)解。105對偶理論和靈敏度分析共128頁，您現在瀏覽的是第105頁!

解分析該問題的步驟是：

(1)設生產產品II為x3′臺，其技術系數向量P3′=(2,6,3)T，然后計算最終表中對應x3′的檢驗數σ3′=c3′-CBＢ-1Ｐ3′=5-(1.5,0.125,0)(2,6,3)T=1.25＞0說明安排生產產品III是有利的。106對偶理論和靈敏度分析共128頁，您現在瀏覽的是第106頁!表2-13(a)由于b列的數字沒有變化，原問題的解是可行解。但檢驗數行中還有正檢驗數，說明目標函數值還可以改善。107對偶理論和靈敏度分析共128頁，您現在瀏覽的是第107頁!表2-13(b)

108對偶理論和靈敏度分析共128頁，您現在瀏覽的是第108頁!

解把改進工藝結構的產品Ⅰ看作產品Ⅰ′，設x1′為其產量。于是在原計算的最終表中以x1′代替x1，計算對應x1′的列向量。

。同時計算出x1′的檢驗數為c1′-CBB-1P1′=4-(1.5,0.125,0)(2,5,2)T=0.375將以上計算結果填入最終表x1‘的列向量位置.得表2-14。109對偶理論和靈敏度分析共128頁，您現在瀏覽的是第109頁!表2-15110對偶理論和靈敏度分析共128頁，您現在瀏覽的是第110頁!

例11假