第4章線性規(guī)劃靈敏度分析問題提出前面假定cj，aij，bi是常數(shù)，實(shí)際上，cj（市場(chǎng)價(jià)格決定），aij（工藝條件決定），bi（根據(jù)經(jīng)濟(jì)效果決定，市場(chǎng)與影子價(jià)格），這些變量都會(huì)隨著市場(chǎng)、工藝等條件的改變而改變。1、當(dāng)這些參數(shù)一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題的最優(yōu)解或最優(yōu)基如何變化；

2、參數(shù)在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)解或最優(yōu)基不變。

針對(duì)以上現(xiàn)象討論兩個(gè)問題:

重新求解？CBCN0b表頭CBXBXNXSBNIb初始表…………CBIB-1NB-1B-1b最優(yōu)表CB-CBICN-CBB-1N0-CBB-1CBB-1b檢驗(yàn)數(shù)求解思路問題提出（2/2）2、b變化影響1、C（CBCN）變化影響3、A（BN）變化影響最優(yōu)解和目標(biāo)函數(shù)值檢驗(yàn)數(shù)行N

變化：主要影響非基變量檢驗(yàn)數(shù)和系數(shù)列向量B變化：系數(shù)矩陣、檢驗(yàn)數(shù)和目標(biāo)函數(shù)、最優(yōu)解主要內(nèi)容§4-2資源數(shù)量變化的分析（右端常數(shù)項(xiàng)bi的變化）§4-3技術(shù)系數(shù)aij的變化§4-1目標(biāo)函數(shù)系數(shù)的變化（

cj

的變化）§4-1目標(biāo)函數(shù)系數(shù)的變化cj的變化對(duì)檢驗(yàn)數(shù)有影響，進(jìn)而影響解的最優(yōu)性。cj對(duì)應(yīng)的變量又分為基變量、非基變量，兩者變化會(huì)對(duì)σj產(chǎn)生不同的影響。一、ck為非基變量xk的價(jià)值系數(shù)

二、cr為基變量xr的價(jià)值系數(shù)

2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-10問題：x3的價(jià)值系數(shù)c3在什么范圍變化，使得最優(yōu)解不變？分析：x3非基變量c3減少：

3減少，負(fù)c3增加：

3增加，負(fù)、0、正Δc32即：c3

1+2一、ck為非基變量xk的價(jià)值系數(shù)（1/2）例4－1當(dāng)非基變量xk對(duì)應(yīng)的ck變?yōu)?/p>

時(shí)，

（不同于xk的另外任一變量xj對(duì)應(yīng)的檢驗(yàn)數(shù)

不會(huì)發(fā)生變化。）

當(dāng)時(shí)，最優(yōu)解不變，即:當(dāng)ck為非基變量xk的價(jià)值系數(shù)時(shí)，最優(yōu)解不變的Δck的變化范圍為此時(shí)最優(yōu)解、最優(yōu)值不變。

一、ck為非基變量xk的價(jià)值系數(shù)（2/2）c2的變化范圍為：

－2－0.5×Δc2

≤0－0.25+0.125×Δc2≤0得：得：Δc2的變化范圍

34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125020000－0.5×Δc2+0.125×Δc2例4－2生產(chǎn)計(jì)劃問題：產(chǎn)品乙收益的變化范圍

甲乙資源約束原材料128設(shè)備A4016設(shè)備B0412獲利34二、cr為基變量xr的價(jià)值系數(shù)（1/2）-2-0.25當(dāng)基變量xr對(duì)應(yīng)的cr變?yōu)?/p>

任意非基變量xj有

若最優(yōu)解不變，則所有

二、cr為基變量xr的價(jià)值系數(shù)（2/2）任意變量xj的檢驗(yàn)數(shù):

（j=1，2，…，n）

負(fù)數(shù)正數(shù)

（3）Δcr的變化范圍由檢驗(yàn)數(shù)行與xr所在行的系數(shù)來(lái)確定

（1）小結(jié)34000x1x2x3x4x5341000.2500400-20.5142010.5-0.12502000-2-0.250

Δck（對(duì)應(yīng)非基變量）的變化范圍：Δcr（對(duì)應(yīng)基變量）的變化范圍：§4-2約束右端常數(shù)項(xiàng)的變化一、br發(fā)生變化，最優(yōu)解改變最優(yōu)基不變（影子價(jià)格不變）最優(yōu)基改變（影子價(jià)格改變）二、最優(yōu)基不變（影子價(jià)格不變），Δbr允許變化的范圍一、br發(fā)生變化，最優(yōu)解改變?cè)O(shè)第r種資源br發(fā)生變化△

br，則

設(shè)備A增加2，即

所以，最優(yōu)基不變，最優(yōu)解為

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250影子價(jià)格不變cj34000CBXBbx1x2x3x4x53x14.51000.2500x5500-20.514x21.75010.5-0.125000-2-0.250一、br發(fā)生變化——最優(yōu)基不變例4-3生產(chǎn)計(jì)劃問題，用到原材料、設(shè)備A、設(shè)備B三項(xiàng)資源例4－4生產(chǎn)計(jì)劃問題增加4單位原材料，即

因?yàn)?/p>

，最優(yōu)解變?yōu)榉强尚薪?，所以用?duì)偶單純形法迭代，

過程如下

cj34000CBXBbx1x2x3x4x53x14

1000.2500x5400-20.514x22

010.5-0.125000-2-0.250x1x3x2＋0－8＋2[-2]1002-0.25-0.503400140.250010300.25000-0.75-124最優(yōu)基：最優(yōu)解：最優(yōu)值：影子價(jià)格改變！??！原材料設(shè)備A設(shè)備B一、br發(fā)生變化——最優(yōu)基改變∴

的變化范圍為：

b2的變化范圍為：即：

二、最優(yōu)基不變，Δbr允許變化的范圍（1/4）cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250例4－5求生產(chǎn)計(jì)劃問題

的變化范圍

,所以

時(shí)，

時(shí)，

則Δbr的變化范圍為：

負(fù)中取大≤≤正中取小

負(fù)數(shù)正數(shù)最終表中松弛變量對(duì)應(yīng)的系數(shù)矩陣最終表中的b列最終表中第r個(gè)松弛變量對(duì)應(yīng)的系數(shù)列向量，即

，仍設(shè)第r種資源發(fā)生Δbr的變化，則

二、最優(yōu)基不變，Δbr允許變化的范圍（2/4）由以上分析可知，最優(yōu)基不變則必有

二、最優(yōu)基不變，Δbr允許變化的范圍（3/4）34000341000.2500400-20.5142010.5-0.125000-2-0.250△br的變化范圍：負(fù)中取大≤≤正中取小

（3）△br的范圍是由b列與第r個(gè)松弛變量對(duì)應(yīng)的系數(shù)列向量來(lái)確定的。

（1）（2）說明：1、上述公式只能判斷一個(gè)br發(fā)生變化的情況，當(dāng)多個(gè)br同時(shí)發(fā)生變化時(shí)，不適用。2、注意區(qū)分br的變化范圍與Δbr的變化范圍。3、b的變化肯定會(huì)引起最優(yōu)解的變化，但最優(yōu)基（影子價(jià)格）是否改變要應(yīng)用上述公式判斷。4、Δbr的變化范圍也確定第r種原材料買入或賣出的范圍（以例4-4為例說明），一旦超出該范圍影子價(jià)格就會(huì)發(fā)生變化。二、最優(yōu)基不變，Δbr允許變化的范圍（4/4）§4-3技術(shù)系數(shù)A

的變化二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）三、增加新產(chǎn)品四、增加約束條件

五、改變約束條件

一、A中某個(gè)元素的變化列的變化行的變化例4－6cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-10一、A中某個(gè)元素的變化（1/2）求解x3的技術(shù)系數(shù)a13不影響最優(yōu)解的變化范圍。非基變量 此處討論的是：非基變量xj的系數(shù)列向量pj的某個(gè)分量aij發(fā)生變化?！腔兞康南禂?shù)aij的變化僅影響該非基變量的檢驗(yàn)數(shù)。

假設(shè)非基變量的系數(shù)

aij

’＝aij＋Δ

aij∴Δaij向小的方向變化有一個(gè)下限，向大的方向變化不會(huì)影響當(dāng)前最優(yōu)解。∵σj＜0非基變量一、A中某個(gè)元素的變化（2/2）二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（1/11）—非基變量例4－7

cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-101、非基變量的系數(shù)列向量Pk

計(jì)算檢驗(yàn)數(shù)

則最優(yōu)解不變；

（1）若，（2）若，則將和代入單純形表，用單純形法繼續(xù)迭代。

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（2/11）—非基變量

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（3/11）—非基變量

2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-101221-1x21701012-11x37/200101/21/22x135/210013/2-1/2000-1-3/2-1/2利用單純形法繼續(xù)迭代求優(yōu)2-11000CBXBbx1x2x3x4x5x6例4－8

生產(chǎn)計(jì)劃問題

分析以上兩種情況對(duì)原最優(yōu)解會(huì)有什么影響？

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（4/11）—基變量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.2502、基變量的系數(shù)列向量

Pk①迭代后直接得到最優(yōu)解；

②迭代后原問題和對(duì)偶問題均為非可行解；

③迭代后原問題為非可行解（對(duì)偶單純形法）；對(duì)偶問題為非可行解（單純形法）。

（2）迭代，使xk的系數(shù)列向量迭代恢復(fù)為單位列向量，再根據(jù)恢復(fù)后的狀態(tài)處理

（1）將和代入最終表，最終表中xk的系數(shù)列向量不再是單位列向量；

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（5/11）—基變量

例4－8生產(chǎn)計(jì)劃問題

產(chǎn)品甲的工藝改為

解：分析對(duì)原最優(yōu)解會(huì)有什么影響？

①迭代后直接得到最優(yōu)解

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（6/11）—基變量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.25030434000341000.2500400-20.5142010.5-0.125000-2-0.2500.5-10.250.581000.501200-2110010.5-0.25000-2-0.5024迭代，使x1的系數(shù)列向量迭代恢復(fù)為單位列向量，再根據(jù)恢復(fù)后的狀態(tài)處理單純形表迭代后直接得到最優(yōu)解二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（7/11）—基變量

34000②迭代后原問題和對(duì)偶問題均為非可行解

例4－8生產(chǎn)計(jì)劃問題：產(chǎn)品甲的工藝改為

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（8/11）—基變量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.2501-41.5-6cj34000CBXBbx1x2x3x4x53x141000.2500x52000-21.514x2-4010.5-0.5000-21.250引入人工變量（i）x2所在行同乘-1（ii）引入人工變量x6用單純形法繼續(xù)迭代求解迭代，原問題和對(duì)偶問題均為非可行解。cj34000CBXBbx1x2x3x4x53x141000.2500x52000-21.514x2-4010.5-0.5000-21.25000104-M-0.5M-0.75+0.5M0040-1-0.50.50-M-M二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（9/11）—基變量

最優(yōu)解：二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（10/11）—基變量

cj34000-MCBXBbx1x2x3x4x5x63x141000.25000x52000-21.510-Mx640-1-0.50.50104-M-0.5M-0.75+0.5M003x1210.50.2500-0.50x5803-0.501-30x480-2-110202.5-200-M+1.53x12/3101/30-1/604x28/301-1/601/3-10x416/300-4/312/3000-1/30-5/6-M+4③迭代后原問題為非可行解：用對(duì)偶單純形法迭代

迭代后對(duì)偶問題為非可行解：用單純形法迭代

二、結(jié)構(gòu)改進(jìn)（列向量發(fā)生變化）（11/11）—基變量

新產(chǎn)品的相關(guān)數(shù)據(jù)是P新、c新和σ新判斷是否生產(chǎn)該產(chǎn)品：

例4－9生產(chǎn)計(jì)劃問題計(jì)劃生產(chǎn)新產(chǎn)品丙

若σ新≥0，則生產(chǎn)該產(chǎn)品，問：①是否應(yīng)該生產(chǎn)該產(chǎn)品；②生產(chǎn)多少？

代入最終表，用單純形法迭代，求得生產(chǎn)量。

和同時(shí)將

若σ新<

0，則不生產(chǎn)該產(chǎn)品。三、增加新產(chǎn)品（增加一列）（1/2）cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250例4－9生產(chǎn)計(jì)劃問題：計(jì)劃生產(chǎn)新產(chǎn)品丙解：①用

表示產(chǎn)量

，說明生產(chǎn)該新產(chǎn)品利潤(rùn)增加。

問：①是否應(yīng)該生產(chǎn)該產(chǎn)品；②生產(chǎn)多少？

代入最終表，用單純形法迭代，得

將

和②

所以應(yīng)該生產(chǎn)III三、增加新產(chǎn)品（增加一列）（2/2）其最終表見右表，增加一個(gè)約束條件

，問如何變化？

cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/2經(jīng)過以下兩步判斷

（1）將原問題最優(yōu)解代入該約束條件，滿足，最優(yōu)解不變。否則，進(jìn)入（2）

（2）將新增約束條件加入一個(gè)松弛變量代入單純形表，迭代求解。將最終表中的解代入該約束為

不滿足該約束，所以最優(yōu)解變化

四、增加約束條件（增加一行）（1/2）例4－10已知

cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/200x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200x6000-1/4-1/200x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200x6000-1/4-1/2001232000100003/220-3/43/210-3/200-1/4-3/210然后用對(duì)偶單純形法繼續(xù)迭代求解。求解過程，略基變量變換為單位向量四、增加約束條件（增加一行）（2/2）

cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110112000-2-1-10按列分析：