第2章對偶理論和靈敏度分析第1節單純形法的矩陣描述

第2節改進單純形法第3節對偶問題的提出第4節線性規劃的對偶理論第5節對偶問題的經濟解釋——影子價格第6節對偶單純形法第7節靈敏度分析第8節*參數線性規劃第1節單純形法的矩陣描述用矩陣描述單純形法的計算過程,有助于對單純形法的理解,以及學習對偶理論和靈敏度分析設線性規劃問題:

目標函數maxz=CX

約束條件AX≤b

非負條件X≥0給這線性規劃問題的約約束條件加入松弛變量以后，得到標準型：

maxz=CX+0Xs

AX+IXs=b(2-1)X，X

s≥0這里I

是m×m單位矩陣。

單純形法計算時,總是取I為初始基,對應的基變量為Xs。設迭代若干步后，基變量為XB，它在初始單純形表中的系數矩陣為B。將B在初始單純形表中單獨列出，而A中去掉B的若干列后剩下的列組成矩陣N，這樣式(2-1)的初始單純形表可列成如表2-1的形式表2-1

0CBCN

Cj-Zj

I

BN0XsbXsXBXN基變量非基變量項目當迭代若干步后，基變量為XB，這時單純形表中由XB的系數組成的矩陣為I。又因單純形法的迭代是對約束增廣矩陣進行的行初等變換，對應的Xs的系數矩陣在新表中應為B-1。故當基變量為XB時，新的單純形表如表2-2的形式表2-2CN-CBB-1N-CBB-1

0

Cj-ZjB-1NB-1ICBXBB-1bXNXsXB非基變量基變量項目從表2-1和表2－2我們可以看出，當迭代后基變量為XB時，其在初始單純形表中的系數矩陣為B，則有：(1)對應初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；(2)初始單純形表中基變量Xs=b,迭代后的表中

XB=B-1b(3)初始單純形表中約束系數矩陣[A,I]=[B,N,I],迭代后的表中約束系數矩陣為

[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1](4)當初始單純形表中變量Xj的系數向量為Pj，迭代后為P’j，則有

P’j=B-1Pj(5)當B為最優基時，在表2-2中應有

CN-CBB-1N≤0-CBB-1≤0

因XB的檢驗數可寫為

CB-CBI=0

又可改寫為

C-CBB-1A≤0-CBB-1≤0

第2節改進單純形法求解線性規劃問題的關鍵是計算B-1，以下介紹一種比較簡便的計算B-1方法。求其逆矩陣時，可以先從第1列開始

以為主元素,進行變換然后構造含有該列，而其他列都是單位列的矩陣然后以第2列的為主元素，進行變換重復以上的步驟，直到獲得求單純形表基矩陣B的逆矩陣B-1也可以用這方法，下面以例1為例說明具體的計算過程

第1步：確定初始基、初始基變量;

確定換入、換出變量。

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

（2）計算非基變量的檢驗數，確定換入變量。

(3)確定換出變量計算：表示選擇>0的元素（4）基變換計算將新的基單位矩陣。計算：（5）計算非基變量的系數矩陣（6）計算等式右邊第1步計算結束后的結果第2步從新的基，基變量開始，重復第1步的計算步驟。計算非基變量的檢驗數，確定換入變量。確定換出變量計算：表示選擇>0的元素計算等式右邊第2步計算結束后的結果第3步從新的基，基變量開始，重復第1步的計算步驟。計算非基變量檢驗數，檢查檢驗數，確定換出變量。確定換出變量計算：表示選擇>0的進行計算新的基計算B逆矩陣計算非基變量的檢驗數最優解目標函數的值第3節對偶問題的提出對偶是什么：對同一事物（或問題），從不同的角度（或立場）提出對立的兩種不同的表述。例如:在平面內，矩形的面積與其周長之間的關系，有兩種不同的表述方法。（1）周長一定，面積最大的矩形是正方形。（2）面積一定，周長最短的矩形是正方形。這是互為對偶關系的表述，這種表述有利于加深對事物的認識和理解。線性規劃問題也有對偶關系。第1章例1的不同表述假設該工廠的決策者決定不生產產品Ⅰ、Ⅱ，而將其所有資源出租或外售。這時工廠的決策者就要考慮給每種資源如何定價的問題。設用y1，y2，y3分別表示出租單位設備臺時的租金和出讓單位原材料A，B的附加額。若用1個單位設備臺時和4個單位原材料A可以生產一件產品Ⅰ，可獲利2元，那么生產每件產品Ⅰ的設備臺時和原材料出租或出讓的所有收入應不低于生產一件產品Ⅰ的利潤。

y1+4y2≥2同理將生產每件產品Ⅱ的設備臺時和原材料出租或出讓的所有收入應不低于生產一件產品Ⅱ的利潤。

2y1+4y3≥3把工廠所有設備臺時和資源都出租或出讓，其收入為

ω=8y1+16y2+12y3從工廠的決策者來看當然ω愈大愈好；從接受者來看他的支付愈少愈好，所以工廠的決策者只能在滿足大于等于所有產品的利潤條件下，提出一個盡可能低的出租或出讓價格，為此需解如下的線性規劃問題

minω=8y1+16y2+12y3y1+4y2≥22y1+4y3≥3yi≥0，i=1,2,3(2-8)稱這個線性規劃問題為例1線性規劃問題(這里稱原問題)的對偶問題。

下面從另一角度來討論，從第1節得到檢驗數的表達式是

CN-CBB-1N與-CBB-1

當CN-CBB-1N≤0(2-9)

-CBB-1≤0(2-10)表示線性規劃問題已得到最優解。(2-9)式，(2-10)式中乘子CBB-1稱為單純形乘子，用符號Y=CBB-1表示。由(2-10)式，可得到Y≥0(2)對應基變量XB的檢驗數是0，即CB-CBB-1B=0。包括基變量在內的所有檢驗數可用

C-CBB-1A≤0表示，從此可得

C-CBB-1A=C-YA≤0

移項后，得到YA≥C(3)由(1)得到

-Y=-CBB-1(2-11)將(2-11)式兩邊右乘b，得到

-Yb=-CBB-1b(2-12)

Yb=CBB-1b=z因Y的上界為無限大，所以只存在最小值。

(4)minω=YbYA≥CY≥0稱它為原線性規劃問題｛maxz=CX｜AX≤b，X≥0｝的對偶規劃問題。對偶規劃問題第4節線性規劃的對偶理論4.1原問題與對偶問題的關系原問題對偶問題

標準型原問題與對偶問題的關系

例2

根據表2-3寫出原問題與對偶問題的表達式。

表2-332c1240y31604y2821y1bx2

x1xy

標準形式的變換關系為對稱形式

原問題對偶問題

非對稱形式的變換關系原問題的約束條件中含有等式約束條件時，按以下步驟處理。

第一步：先將等式約束條件分解為兩個不等式約束條件

第二步：按對稱形式變換關系可寫出它的對偶問題

設yi′是對應(2-13)式的對偶變量

yi″是對應(2-14)式的對偶變量,這里i=1,2,…,m

將上述規劃問題的各式整理后得到

表2-4線性規劃的原問題與對偶問題的關系

例3試求下述線性規劃原問題的對偶問題

解設對應于約束條件(1)(2)(3)的對偶變量分別是y1,y2,y3

，則由表2-4中原問題和對偶問題的對應關系，可以直接寫出上述問題的對偶問題

4.2對偶問題的基本性質

(1)對稱性

對偶問題的對偶是原問題

;(2)弱對偶性若X是原問題的可行解，Y是對偶問題的可行解。則存在CX≤Yb;(3)無界性

若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解;

(4)可行解是最優解時的性質

;(5)對偶定理若原問題有最優解，那么對偶問題也有最優解；且目標函數值相等;(6)互補松弛性

;(7)原問題檢驗數與對偶問題解的關系.(1)對稱性

對偶問題的對偶是原問題

證設原問題是maxz=CX;AX≤b；X≥0根據對偶問題的對稱變換關系，可以找到它的對偶問題是minω=Yb;YA≥C；Y≥0令ω’=-ω，由minω=-max(-ω)=-maxω’可得到maxω’=-Yb;-YA≤-C；Y≥0根據對稱變換關系，得到上式的對偶問題是minz’=-CX；-AX≥-b;X≥0令z=-z’，則上式可改寫為maxz=CX;AX≤b；X≥0這就是原問題。證畢。(2)弱對偶性

(3)無界性

若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解

證：由性質(2)可知，注意：當原問題(對偶問題)為無可行解，其對偶問題(原問題)或有無界解或無可行解。原問題(對偶問題)對偶問題(原問題)(4)可行解是最優解時的性質

設是原問題的可行解，是對偶問題的可行解，當時，是最優解。

(5)對偶定理若原問題有最優解，那么對偶問題也有最優解；且目標函數值相等。

(6)互補松弛性將原問題目標函數中的系數向量C用C=YA-YS代替后，

z=(YA-YS)X=YAX-YSX(2-15)將對偶問題的目標函數中系數列向量b，用b=AX+XS代替后，得到

ω=Y(AX+XS)=YAX+YXS(2-16)(7)原問題檢驗數與對偶問題解的關系設原問題是maxz=CX;AX+XS=b;X,XS≥0它的對偶問題是minω=Yb;YA-YS=C;Y,YS≥0則原問題單純形表的檢驗數行對應其對偶問題的一個基解，其對應關系見表2-5。表2-5對應關系YS1是對應原問題中基變量XB的剩余變量，YS2是對應原問題中非基變量XN的剩余變量。

證:設B是原問題的一個可行基，于是A=(B,N)；原問題可以改寫為

maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS≥0相應地對偶問題可表示為

minω=YbYB-YS1=CB

(2-17)YN-YS2=CN

(2-18)

Y，YS1,YS2≥0這里YS=(YS1，YS2)。求得原問題的一個解：XB=B-1b，這時相應的檢驗數分別為CN-CBB-1N與-CBB-1現分析這些檢驗數與對偶問題的解之間的關系：令Y=CBB-1，將它代入(2-17)式，(2-18)式得

YS1=0-YS2=CN-CBB-1N

證畢例4已知線性規劃問題maxz=x1+x2-x1+x2+x3≤2-2x1+x2-x3≤1x1,x2,x3≥0試用對偶理論證明上述線性規劃問題無最優解。解上述問題的對偶問題為minω=2y1+y2-y1-2y2≥1y1+y2≥1y1-y2≥0y1，y2≥0由第1約束條件，可知對偶問題無可行解；原問題雖然有可行解，但無最優解。例5已知線性規劃問題minω=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其對偶問題的最優解為y1*=4/5，y2*=3/5；z=5。試用對偶理論找出原問題的最優解。解：先寫出它的對偶問題maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0將y1*=4/5,y2*=3/5的值代入約束條件，得②=1/5<3，③=17/5<5，④=7/5<2

它們為嚴格不等式；由互補松弛性得x2*=x3*=x4*=0。因y1，y2>0，原問題的兩個約束條件應取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問題的最優解為X*=(1，0，0，0，1)T；ω*=5在單純形法的每步迭代中，目標函數取值z=CBB-1b，和檢驗數CN-CBB-1N中都有乘子Y=CBB-1，那么Y的經濟意義是什么?設B是｛maxz=CX｜AX≤b，X≥0｝的最優基，由(2-12)式:-Yb=-CBB-1b

可知

z*=CBB-1b=Y*b

。由此

第5節對偶問題的經濟解釋—影子價格

由上式可知，變量yi*的經濟意義是在其他條件不變的情況下，單位資源變化引起的目標函數最優值的變化。

23000

4

10

0

1/4

0-1400-1.5-1/80203x1x5x2

2

01

1/2-1/8

0

4

00

-21/2

1

X(3)=(4，2，0，4，0)T，z3=14cj-zj可見y1*=1.5，y2*=0.125，y3*=0。這說明是其他條件不變的情況下，若設備增加一臺時，該廠按最優計劃安排生產可多獲利1.5元；原材料A增加1kg，可多獲利0.125元；原材料B增加1kg，對獲利無影響。

圖2-1從圖2-1可看到，設備增加一臺時，代表該約束條件的直線由①移至①′，相應的最優解由(4，2)變為(4，2.5)，目標函數z=2×4+3×2.5=15.5，即比原來的增大1.5。又若原材料A增加1kg時，代表該約束方程的直線由②移至②′，相應的最優解從(4，2)變為(4.25，1.875)，目標函數z=２×4.25+3×1.875=14.125。比原來的增加0.125。原材料B增加1kg時，該約束方程的直線由③移至③′，這時的最優解不變。yi*的值代表對第i種資源的估價-影子價格。

在該廠現有資源和現有生產方案的條件下，設備的每小時租費為1.5元，1kg原材料A的出讓費為除成本外再附加0.125元，1kg原材料B可按原成本出讓，這時該廠的收入與自己組織生產時獲利相等。影子價格隨具體情況而異，在完全市場經濟的條件下，當某種資源的市場價低于影子價格時，企業應買進該資源用于擴大生產；而當某種資源的市場價高于企業影子價格時，則企業的決策者應把已有資源賣掉。可見影子價格對市場有調節作用。

第6節

對偶單純形法

一、對偶單純形法的基本思路求解線性規劃問題的單純形法的思路是：對原問題的一個基可行解，判斷是否所有檢驗數

Cj-Zj≤0(j=1,…,n)。如是，又基變量中無非零人工變量，即找到了問題的最優解；否則，再找到相鄰的目標函數值更大的基可行解，并繼續判別，只要最優解存在，就一直循環進行找到最優解為止。

根據對偶問題的性質，因為Cj-Zj＝

Cj-CBB-1Pj，當Cj-Zj≤0(j=1,…,n)，即Ypj≥Cj或(j=1,…,n)，即對偶問題的解為可行解，從而原問題和對偶問題的解均為可行解。

反之，如果存在一個對偶問題的可行基B，即對

j=1,…,n，有CBB-1Pj≥Cj或Cj-Zj≤0，

只要XB=B-1b≥0，即原問題的解也為可行解，從而兩者均為最優解。否則，保持對偶問題為可行解，找出原問題的相鄰基解，再判別是否有XB≥0，循環進行，一直使原問題也為可行解，從而兩者均為最優解。這就是對偶單純形法的基本思路。二、對偶單純形法的計算步驟

(1)根據線性規劃問題，列出初始單純形表。檢查b列的數字，若都為非負，檢驗數都為非正，則已得到最優解。停止計算。若檢查b列的數字時，至少還有一個負分量，檢驗數保持非正，那么進行以下計算。(2)確定換出變量按min｛(B-1b)i｜(B-1b)i＜0}＝(B-1b)l對應的基變量xl為換出變量

(3)確定換入變量在單純形表中檢查xl所在行的各系數αlj(j=1,2,…，n)。若所有αlj≥0，則無可行解，停止計算。若存在αlj＜0(j=1,2,…，n),計算

按θ規則所對應列的非基變量xk為換入變量，這樣才能保持得到的對偶問題解仍為可行解。(4)以αlk為主元素，按原單純形法在表中進行迭代運算，得到新的計算表。重復步驟(1)～(4)。

例6用對偶單純形法求解

minω=2x1+3x2+4x3x1+2x2+x3≥32x1-x2+3x3≥4x1，x2，x3≥0解

先將此問題化成下列形式，以便得到對偶問題的初始可行基

maxz=-2x1-3x2-4x3-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4xj≥0，j=1,2,…,5建立此問題的初始單純形表，見表2-6。

從表2-6看到，檢驗數行對應的對偶問題的解是可行解。因b列數字為負，故需進行迭代運算。

換出變量的確定：按上述對偶單純形法計算步驟(2)，即按min｛(B-1b)i｜(B-1b)i＜0}＝(B-1b)l對應的基變量xl為換出變量。計算min(-3,-4)=-4故x5為換出變量。

換入變量的確定：按上述對偶單純形法計算步驟(3)，即在單純形表中檢查xl所在行的各系數αlj(j=1,2,…，n)。若所有αlj≥0，則無可行解，停止計算。計算故x1為換入變量。換入、換出變量的所在列、行的交叉處“-2”為主元素。按單純形法計算步驟進行迭代，得表2-7。表2-7由表2-7看出，對偶問題仍是可行解，而b列中仍有負分量。故重復上述迭代步驟，得表2-8。表2-8表2-8中，b列數字全為非負，檢驗數全為非正，故問題的最優解為X*=(11/5，2/5，0，0，0)T若對應兩個約束條件的對偶變量分別為y1和y2，則對偶問題的最優解為Y*=(y1*,y2*)=(8/5,1/5)從以上求解過程可以看到對偶單純形法有以下優點：

(1)初始解可以是非可行解，當檢驗數都為負數時就可以進行基的變換，這時不需要加入人工變量，因此可以簡化計算。(2)當變量多于約束條件，對這樣的線性規劃問題用對偶單純形法計算可以減少計算工作量，因此對變量較少，而約束條件很多的線性規劃問題，可先將它變換成對偶問題，然后用對偶單純形法求解。(3)在靈敏度分析及求解整數規劃的割平面法中，有時需要用對偶單純形法，這樣可使問題的處理簡化。對偶單純形法的局限性主要是，對大多數線性規劃問題，很難找到一個初始可行基，因而這種方法在求解線性規劃問題時很少單獨應用。

第7節

靈敏度分析

以前討論線性規劃問題時，假定αij，bi,cj都是常數。但實際上這些系數往往是估計值和預測值。因此會提出這樣兩個問題：(1)當這些系數有一個或幾個發生變化時，已求得的線性規劃問題的最優解會有什么變化；(2)這些系數在什么范圍內變化時，線性規劃問題的最優解或最優基不變。當線性規劃問題中某一個或幾個系數發生變化后，原來已得結果一般會發生變化。當然可以用單純形法從頭計算，以便得到新的最優解。這樣做很麻煩，而且也沒有必要。因在單純形法迭代時，每次運算都和基變量的系數矩陣B有關，因此可以把發生變化的個別系數，經過一定計算后直接填入最終計算表中，并進行檢查和分析，可按表2-9中的幾種情況進行處理。表2-97.1資源數量變化的分析

資源數量變化是指資源中某系數br發生變化，即br′=br+Δbr。并假設規劃問題的其他系數都不變。最終表中原問題的解相應地變化為XB′=B-1(b+Δb)這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗數不變，故最優基不變，但最優解的值發生了變化，所以XB′為新的最優解。新的最優解的值允許變化范圍用以下方法確定。B-1

是最終計算表中的最優基的逆b列的元素變化例如求第1章例1中第二個約束條件b2的變化范圍。解：可以利用第1章例1的最終計算表中的數據：可計算Δb2：由上式，可得Δb2≥-4/0.25=-16，Δb2≥-4/0.5=-8，b2≤2/0.125=16。所以Δb2的變化范圍是［-8，16］；顯然原b2=16，加它的變化范圍后，b2的變化范圍是［8，32］。例7從表1-5得知第1章例1中，每設備臺時的影子價格為1.5元，若該廠又從其他處抽調4臺時用于生產產品Ⅰ，Ⅱ。求這時該廠生產產品Ⅰ，Ⅱ的最優方案。

解先計算B-1Δb,將結果反映到最終表1-5中，得表2-10。

由于表2-10中b列有負數，故用對偶單純形法求新的最優解。計算結果見表2-11。

表2-11即該廠最優生產方案應改為生產4件產品Ⅰ，生產3件產品Ⅱ，獲利z*=4×2+3×3=17(元)7.2目標函數中價值系數cj的變化分析

若cj是非基變量xj的系數

σj=cj-CBB-1Pj

或當cj變化Δcj

σj’=cj+Δcj-CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必須小于或等于YPj-cj，才可以滿足原最優解條件。cj

cj+

cj不影響解的可行性，影響最優性。(2)若cr是基變量xr的系數，因cr∈CB，當cr變化Δcr

時，引起CB

的變化

當cr變化Δcr

后

1-'

000

11≤--=+-=--rBjBBjjpjB),,c,,(PjBCcPjB)CC(cLLDDs

即

…

(j=1,2,…，n)

例8試以第1章例1的最終表表1-5為例。設基變量x2的系數c2變化Δc2，在原最優解不變條件下，確定Δc2的變化范圍。

解這時表1-5最終計算表便成為表2-12所示。若保持原最優解，從表2-12的檢驗數行可見應有由此可得Δc2≥-3和Δc2≤1。Δc2的變化范圍為-3≤Δc2≤1即x2的價值系數c2可以在［0，4］之間變化，而不影響原最優解。

7.3技術系數αij的變化

分兩種情況來討論技術系數αij的變化(1)aij

為非基變量的系數只影響xj的檢驗數，從而影響最優性。例9分析在原計劃中是否應該安排一種新產品。以第1章例1為例。設該廠除了生產產品Ⅰ，Ⅱ外，現有一種新產品III。已知生產產品III，每件需消耗原材料A，B各為6kg，3kg，使用設備2臺時；每件可獲利5元。問該廠是否應生產該產品和生產多少?解(1)設生產產品III為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是有利的。表2-13(a)由于b列的數字沒有變化，原問題的解是可行解。但檢驗數行中還有正檢驗數，說明目標函數值還可以改善。表2-13(b)

(3)將x3′作為換入變量，x5作為換出變量，進行迭代，求出最優解。計算結果見表2-13(b)，這時得最優解：x1=1,x2=1.5，x3′=2。總的利潤為16.5元。比原計劃增加了2.5元。(2)aij為基變量系數基變化，影響最優性、可行性。例10分析原計劃生產產品的工藝結構發生變化。仍以第1章例1為例，若原計劃生產產品Ⅰ的工藝結構有了改進，這時有關它的技術系數向量變為P1′=(2,5,2)T，每件利潤為4元，試分析對原最優計劃有什么影響?

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

同時計算出x1′的檢驗數為c1′-CBB-1P1′=4-(1.5,0.125,0)(2,5,2)T=0.375將以上計算結果填入最終表x1′的列向量位置.得表2-14。表2-14可見x1′為換入變量，x1為換出變量，經過迭代。得到表2-15表2-15表2-15表明原問題和對偶問題的解都是可行解。所以表中的結果已是最優解。即應當生產產品Ⅰ′，3.2單位；生產產品Ⅱ，0.8單位。可獲利15.2元。

例11假設例10的產品Ⅰ′的技術系數向量變為P1′=(4,5,2)T，而每件獲利仍為4元。試問該廠應如何安排最優生產方案?

解

方法與例10相同，以x1′代替x1，并計算列向量x1′的檢驗數為c1′-CBB-1P1′=4-（1.5,0.125,0)(4,5,2)T=-2.625。將這些數字填入最終表1-15的x1列的位置，得到表2-16。表2-16將表2-16的x1′變換為基變量，替換x1，得表2-17。

表2-17從表2-17可見原問題和對偶問題都是非可行解。于是引入人工變量x6。因在表2-17中x2所在行，用方程表示為0x1′+x2+0.5x3-0.4x4+0x5=-2.4表2-18引入人工變量x6后-x2-0.5x3+0.4x4+x6=2.4將x6作為基變量代替x2，填入表2-17，得到表2-18。這時可按單純形法求解

X4為換入變量，x6為換出變量。經基變換運算后，得到表2-19的上表。在表2-19的上表中，確定x2為換入變量，x5為換出變量。經基變換運算后，得到表2-19的下表。此表的所有檢驗數都為非正，已得最優解。最優生產方案為生產產品Ⅰ′，0.667單位；產品Ⅱ，2.667單位，可得最大利潤10.67元。

表2-19第8節*參數線性規劃

靈敏度分析時，主要討論在最優基不變情況下，確定系數aij，bi，cj的變化范圍。而參數線性規劃是研究這些參數中某一參數連續變化時，使最優解發生變化的各臨界點的值。即把某一參數作為參變量，而目標函數在某區間內是這個參變量的線性函數，含這個參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對偶單純形法分析參數線性規劃問題。其步驟是：(1)對含有某參變量t的參數線性規劃問題。先令t=0，用單純形法求出最優解；(2)用靈敏度分析法，將參變量t直接反映到最終表中；(3)當參變量t連續變大或變小時，觀察b列和檢驗數行各數字的變化。若在b列首先出現某負值時，則以它對應的變量為換出變量；于是