第十五章 線性規(guī)劃的靈敏度分析

1、第十五章 線性規(guī)劃的靈敏度分析15.1 邊際值(影子價(jià)格) 以(max,£)為例，邊際值(影子價(jià)格其實(shí)指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)趇個(gè)約束行的右端項(xiàng) bi 減少一個(gè)單位時(shí)，目標(biāo)函數(shù)的變化量 偏導(dǎo)數(shù)，機(jī)會(huì)成本 因此松弛變量，人工變量剩余變量機(jī)會(huì)成本的另外表達(dá)形式例15.1.1 其最優(yōu)單純表形式如下：表15.1.1關(guān)于影子價(jià)的一些說明影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格，資源的影子價(jià)與資源的緊缺度有關(guān)松弛變量增加一個(gè)單位等于資源減少一個(gè)單位剩余變量增加一個(gè)單位等于資源增加一個(gè)單位資源有剩余，在最優(yōu)解中就有對(duì)應(yīng)松弛變量存在，且其影子價(jià)為 0影子價(jià)為 0，資源并不一定有剩余15.2 價(jià)值系數(shù) C

2、j 的靈敏度分析 cj 變動(dòng)可能由于市場(chǎng)價(jià)格的波動(dòng)，或生產(chǎn)成本的變動(dòng) cj 的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj 允許的變動(dòng)范圍Dcj cj 的變化會(huì)引起檢驗(yàn)數(shù)的變化，有兩種情況:非基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù)基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)15.2.1非基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析要保持 故有例15.2.1表15.2.1表15.2.2為非基變量，所以要保持 故有15.2.2 基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析由于基變量對(duì)應(yīng)的價(jià)值系數(shù) cj 在CB中出現(xiàn)，因此它會(huì)影響所有非基變量的檢驗(yàn)數(shù)。只有一個(gè)基變量的發(fā)生變化，變化量為即在CB中的k分量，

3、研究非基變量xj 機(jī)會(huì)成本的變化：要滿足 則有 當(dāng)有 當(dāng)有為保證所有非基變量檢驗(yàn)數(shù)仍滿足最優(yōu)條件，有表15.2.3由 設(shè) x4 的價(jià)值系數(shù)增加Dc4，對(duì)應(yīng)k=2， 有一邊為空集如何處理（右：+，或左：- ） 為什么akj=0不出現(xiàn)在任何一邊的集合中 與對(duì)偶單純型法找入基變量的公式類似。15.3 右端項(xiàng) bi 的靈敏度分析 設(shè)XB=B-1b是最優(yōu)解，則有XB=B-1b³0 b的變化不會(huì)影響檢驗(yàn)數(shù)； b的變化量Db可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪狻ＴO(shè)第s個(gè)分量發(fā)生變化。為保證最優(yōu)解的基變量不發(fā)生變化，必須滿足 即當(dāng)時(shí)，B仍是新問題的最優(yōu)基矩陣。當(dāng)，則有 當(dāng)，則有 要求對(duì)所有k都成立，從而有

4、此時(shí)，基變量的解值和目標(biāo)函數(shù)會(huì)發(fā)生變化： 即 表15.3.1還是對(duì)前面的例分析，以b2為例, x6是對(duì)應(yīng)的初始基變量，有變化，s=1，即取基矩陣中第二列計(jì)算令，則有15.4 技術(shù)系數(shù) aij 的靈敏度分析技術(shù)系數(shù)aij變化的影響比較復(fù)雜對(duì)應(yīng)基變量的 aij ，且資源bi已全部用完對(duì)應(yīng)基變量的 aij ，但資源bi未用完 對(duì)應(yīng)非基變量的 aij ，且資源bi全用完或未用完1）對(duì)應(yīng)基變量的 aij ，且資源bi已全部用完 D aij=02）對(duì)應(yīng)基變量的 aij ，但資源bi未用完 上述兩個(gè)公式不充分，為什么？引起B(yǎng)1發(fā)生變化，從而引起非基變量的檢驗(yàn)數(shù) zj cj 的變化3）對(duì)應(yīng)非基變量的 aij

5、只影響對(duì)應(yīng)非基變量xj的檢驗(yàn)數(shù) zj cj 若D aij > 0，不會(huì)破壞最優(yōu)解 若D aij < 0，必須保證 0£ zj cj設(shè)為非基變量，則有 設(shè)變動(dòng)，則有 即對(duì)于第i行約束型， 所以 表15.4.1x1, x3為非基變量， q1= 0, q2= 0.25, q3= 1, 故有x2, x4為基變量，x5=100, b1有剩余， 故有 15.5 新增決策變量的分析例15.1.1中，若新增產(chǎn)品 x8，單位產(chǎn)品的資源消耗量分別是：5，4，3，單位產(chǎn)品的利潤是：9，問是否生產(chǎn)？ 已知 c8=9, a18=5, a28=4, a38=3 計(jì)算 x8 的檢驗(yàn)數(shù)可知生產(chǎn)是否有利結(jié)

6、論：生產(chǎn)x8有利。將B1P8加入最優(yōu)單純型表中，以x8為入基變量進(jìn)行迭代。（過程學(xué)生完成）15.6 新增約束條件的分析1）將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2）若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型3、利用對(duì)偶單純型法繼續(xù)迭代為什么可以利用對(duì)偶單純型法例15.6.1 續(xù)前例15.1.1，如果生產(chǎn)中為提高產(chǎn)品性能，增加一種原料，已知各產(chǎn)品單件生產(chǎn)的該原料消耗量為：1，2，3，3，該原料總量為：650。應(yīng)該如何調(diào)整生產(chǎn)計(jì)劃？解：先把新增加的條件添加到表格中，再典范化：表15.6.1（以上為典范化的過程。下面先計(jì)算判別數(shù)，可以發(fā)現(xiàn)是對(duì)偶可行的，因

7、此利用對(duì)偶單純形方法求解。）表15.6.2注意：最優(yōu)解的目標(biāo)函數(shù)減少了25個(gè)單位。15.7 靈敏度分析舉例例15.7.1 某工廠生產(chǎn)三種產(chǎn)品A, B, C，有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng)A產(chǎn)品至少110 個(gè)，求收益最大的生產(chǎn)方案。表15.7.1解：設(shè)xj為已選定各種組合方案的組數(shù)(j=1,2,5)， x6為A產(chǎn)品的剩余變量， x7，x8分別為工人工時(shí)和機(jī)器工時(shí)的松弛變量。表15.7.2 例15.7.2 最優(yōu)解的B1是什么 產(chǎn)品A的影子價(jià)為多少 第II組方案的生產(chǎn)費(fèi)用提高2元，是否要調(diào)整生產(chǎn)組別 若工人加班費(fèi)為1元/小時(shí)，是否要采取加班措施 若通過租借機(jī)器增加工時(shí)，租費(fèi)的上

8、限應(yīng)為多少 A產(chǎn)品的訂購合同是否有利，A產(chǎn)品的變動(dòng)范圍多大 若要選用第IV組方案，該組的生產(chǎn)費(fèi)用應(yīng)降低多少 若工人加班費(fèi)為0.3元/小時(shí)，最多允許加班時(shí)間多少 若機(jī)器租費(fèi)低于44元/小時(shí)，問租幾部機(jī)器才合適(每天8小時(shí)計(jì)) 若第III組方案使機(jī)器工時(shí)減少0.5小時(shí)，能否被選入15.8 參數(shù)線性規(guī)劃 前面只考慮aij, bi, cj 一個(gè)發(fā)生變化，如果多個(gè)同時(shí)發(fā)生變化則很難解析。但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進(jìn)行多個(gè)系數(shù)的靈敏度分析。15.8.1 參數(shù)cj的變化分析 第i種資源的單位費(fèi)用變化量，不限 變化對(duì) cj 的影響率例15.8.1 資源b1變化量q1，aj=a1j表15.

9、8.1例15.8.2資源b1變化量q1 與Dc515.8.2 參數(shù) bi 的變化分析例15.8.1中，將b1,b2,b3理解為三個(gè)車間的周工時(shí)資源。假設(shè)從第1向2車間調(diào)動(dòng)工人q 個(gè)，每個(gè)工人的周工時(shí)為 40小時(shí)，問調(diào)動(dòng)多少工人不會(huì)破壞最優(yōu)產(chǎn)品組合。習(xí) 題151.已知線性規(guī)劃問題和它的最優(yōu)單純形表15.9.1. 表15.9.1右邊1250204831102-2-20-116（1） 求原問題和對(duì)偶問題的最優(yōu)解。（2） 確定最優(yōu)基不改變的前提下變量和的目標(biāo)函數(shù)系數(shù)的變化范圍（3） 確定最優(yōu)基不改變的前提下兩個(gè)右邊項(xiàng)系數(shù)的變化范圍。 2.已知線性規(guī)劃問題 當(dāng)時(shí)求解得最終單純形表如表15.9.2.（1）

10、 確定和的值；（2） 當(dāng)時(shí)，值在什么范圍內(nèi)變化，上述最優(yōu)值不變；（3） 當(dāng)時(shí)，值在什么范圍內(nèi)變化，上述最優(yōu)值不變；表15.9.2右邊0404201/211/205/21-1/20-1/61/35/23.某廠生產(chǎn)I,II,III三種產(chǎn)品，其所需勞動(dòng)力、材料等數(shù)據(jù)見表15.9.3.要求：（1）確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃； （2）產(chǎn)品I的利潤在什么范圍內(nèi)變動(dòng)時(shí)，上述最優(yōu)計(jì)劃不變； （3）若設(shè)計(jì)一種新產(chǎn)品IV，單件勞動(dòng)力消耗為8單位，材料消耗為2單位，每件獲利3元，問該產(chǎn)品是否值得生產(chǎn)？ （4）若勞動(dòng)力數(shù)量不增，材料不足時(shí)從市場(chǎng)購買，問該廠是否購進(jìn)原材料擴(kuò)大生產(chǎn)，如果可以購買，則最多應(yīng)購入多少？表15.9.3IIIIII可用量（單位）勞動(dòng)力63545材料34530產(chǎn)品利潤（元/件）3144.已知線性規(guī)劃問題： 已知用單純形法求得最優(yōu)解的單純形表如表15.9.4所示試分析在下列各種條件單獨(dú)變化的情況下，最優(yōu)解將如何變化。表15.9.4迭代BV.Eq.右邊最優(yōu)（1）1001/34/300（2）0012/