【文章內(nèi)容簡介】 B b X1 X2 X3 X4 X5 X6 X4 X1 X2 1 4 3 0 1 0 0 0 1 3 1 1 1 0 0 1 1 0 1 0 1 Z’ 18 0 0 6 0 3 2 則最終單純形表為： …… 得到最優(yōu)解為： 18)034(**???ZX第六節(jié) 線性規(guī)劃問題的靈敏度分析 一、靈敏度分析的基本概念和基本原理 靈敏度分析是指系數(shù)及常數(shù)項的變化對最優(yōu)解的影響，有時也討論新產(chǎn)品是否投產(chǎn)等生產(chǎn)計劃問題。 以標準線性規(guī)劃問題為例： ??????0XbAXCXM ax Z?????????????0,)(1111NBNBNBNBXXbBNXBXXNBCCbBCM a x ZB ，其典式為：選定一個基則Ｂ為最優(yōu)基的條件是： ?????????正則性條件可行性條件 0 011NBCCbBXBNB 當某系數(shù)（常數(shù)）發(fā)生變化，若能繼續(xù)滿足可行性條件和正則性條件，則最優(yōu)基不變；如果不滿足某一個條件，可選擇單純形法或對偶單純形法繼續(xù)迭代。 二、資源數(shù)量 b變化的靈敏度分析 資源數(shù)量變化不影響正則性條件，只影響可行性條件，因此若能繼續(xù)保持 01 ?? ? bBX B則，最優(yōu)基不發(fā)生變化，但決策變量的取值一般會改變。 設原資源數(shù)量為： )( 1 ?? mr bbbb ??現(xiàn)第 r種資源發(fā)生變化，變化后資源的數(shù)量為： )( 1 ??????? mrr bbbbbbb ??資源變化后的可行性條件將變化為： ??????????????????????????00)(1111??rbBbBbbBbB迭代尋找最優(yōu)方案。，基不變，否則應重新若 01 ?? bB另外，資源數(shù)量在什么范圍內(nèi)變化，而最優(yōu)基不變呢？ ????????????????mmmrmmrmraaaaaaaaaB???????1222111111若???????????????????????????????????????????????????????rmrrrrrmrbabababbbbBbBbB????21211110000 22111 ???????????????????????rmrmrrrrbabbabbabbB?即，若）；；的情況（應分析 000 ???irairirirririririrabbabaabba??????????，當任意，當，當000? ? ? ?00 m i nm a x ?? ?????irir airirairiabbab于是得到： 例 7 分析下列線性規(guī)劃問題 (p31) ??????????????0,124164823221212121xxxxxxxxM ax Z模型為：則最終單純形表為： 2 3 0 0 0 XB b X1 X2 X3 X4 X5 X1 X5 X2 4 4 2 1 0 0 0 0 1 0 2 1/2 1/4 1/2 1/8 0 1 0 Z 14 0 0 3/2 1/8 0 ① 最優(yōu)基的逆矩陣是什么？ ②討論第二種資源的變化范圍 ????????????????? ??8/12m i n2/14,4/14m a x2b③ 第一種資源有４個單位的增量，最優(yōu)解如何變化？ ????????????????????????????????????????????? ??? ???4442/1204244001111bBbBbB 三、目標函數(shù)系數(shù) C變化的靈敏度分析 目標函數(shù)系數(shù)的變化不影響可行性條件，只影響正則性條件（檢驗數(shù)），正則性條件（檢驗數(shù)）可以表示為： ? ? ? ?nmmBnmmBNNPPPBCcccNBCC?? 211211 ???????????jBjj PBCC 1????對于任一檢驗數(shù)： 非基變量和基變量目標函數(shù)系數(shù)的變化對檢驗數(shù)的影響是不同的。 可以看出：從檢驗數(shù) jBjj PBCC 1????是非基變量系數(shù)若 jCjjj CCC ???jjjBjjjBjjCPBCCCPBCC????????????? 11 這里得到了兩個方面的 結論：一是非基變量系數(shù)發(fā)生變化后，檢驗數(shù)的變化情況，因此可判斷是否對最優(yōu)解產(chǎn)生影響；二是可確定最優(yōu)解不變時，非基變量系數(shù)變化范圍，即 jjC ???? ，則影響所有檢驗數(shù)?；兞肯禂?shù)的變化影響 BCBrBrBr CCC ???個變量的檢驗數(shù)為：則變化后第 j? ?? ?? ?rjBrjjBrjjBrjBjjBmBrBrBjjBjjaCPCPBCPBCCPBCCCCCPBCC???????????????????????? 00 00 11111??????為保持原最優(yōu)解，則： 0????? rjBrjj aC??? ? ? ?00 m i nm a x ?? ???rjrj arjjBrarjjaCa ??于是得到：2 3 0 0 0 XB b X1 X2 X3 X4 X5 X1 X5 X2 4 4 2 1 0 0 0 0 1 0 2 1/2 1/4 1/2 1/8 0 1 0 Z 14 0 0 3/2 1/8 0 仍以上例： 2141811111???????ccc最優(yōu)解不變的范圍：，最優(yōu)解是否變化呢？發(fā)生變化， 四、約束條件變化的靈敏度分析 就是判斷最優(yōu)解能否滿足新的約束條件。 滿足：仍為最優(yōu)解（可能可行域減?。? 不滿足：增加該約束條件，用對偶單純形法迭代。 原某個約束條件的資源是否有剩余？ 有剩余，說明原某個約束條件為非嚴格等式 無剩余，嚴格等式 結合改變后的約束條件和原最優(yōu)解進行分析。 例 8 約束條件變化的靈敏度分析 5 5 13 0 0 XB b X1 X2 X3 X4 X5 X4 X5 20 90 1 12 1 4 3 10 1 0 0 1 Z 0 5 5 13 0 0 X2 X5 20 10 1 16 1 0 3 2 1 4 0 1 Z 100 0 0 2 5 0 ① 無窮多最優(yōu)解 ②第一個方程為嚴格等式（資源用盡），第二個方程資源有剩余 ③ 第二個約束條件變化后，變成了嚴格等式，最優(yōu)解不變（！？）。 ④增加一個約束條件后，若不滿足，則應增加約束方程繼續(xù)迭代（可將原最優(yōu)表寫成模型，再增加方程）。 XB b X1 X2 X3 X4 X5 X6 X2 X5 X6 20 10 50 1 16 2 1 0 3 3 2 5 1 4 0 0 1 0 0 0 1 Z 100 0 0 2 5 0 0 X2 X5 X6 20 10 10 1 16 5 1 0 0 3 2 4 1 4 3 0 1 0 0 0 1 Z 100 0 0 2 5 0 0 五、增加新決策變量的靈敏度分析 增加新變量指單純形表增加一列。 在單純形表迭代中，可以認為該決策變量原先沒有被換入基（不管按最大法則是否該入基）。 不影響可行性條件，只影響正則性條件（該新決策變量的檢驗數(shù)） tBtttPBCcx1 ????，則：設增加可入基，原基不是最優(yōu)基，不能入基，原基仍為最優(yōu)基，若ttttxx00 ????入基后，應注意其技術系數(shù)向量的變化！ 六、技術系數(shù) A變化的靈敏度分析 總體原則就是將 技術系數(shù)變化的 某決策變量作為新變量進行處理。例如（注意兩個表所表示的模型等價）： XB b X1 X2 X3 X4 X5 X1’ X1 X5 X2 4 4 2 1 0 0 0 0 1 0 2 1/2 1/4 1/2 1/8 0 1 0 5/4 1/2 3/8 Z 0 0 3/2 1/8 0 3/8 XB b X1 X2 X3 X4 X5 X1’ X3 X4 X5 8 16 12 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 5 2 Z 2 3 0 0 0 4 第三章 運輸問題 運輸問題是一類特殊的線性規(guī)劃問題，特殊就在于：特殊的結構、特殊的求解方法。 第一節(jié) 運輸問題的數(shù)學模型及特征 一、問題的提出 設某種物資共有 m個產(chǎn)地， n個銷地，供應與需求的數(shù)量及運價如下表所示，問如何制定調運方案，使總運費最低（噸公里、時間）？ 產(chǎn)地 \銷地 B1 B2 … Bn 產(chǎn)量 A1 A2 … Am a1 a2 … am 銷量 b1 b2 … bn 產(chǎn)地 \銷地 B1 B2 … Bn A1 A2