衛(wèi)生管理運籌學課件

*第一節(jié)

基本概念*第二節(jié)線性規(guī)劃問題的圖解法*第三節(jié)線性規(guī)劃模型的解及性質(zhì)*第四節(jié)單純形法

第五節(jié)對偶規(guī)劃第六節(jié)運輸問題及表上作業(yè)法

線性規(guī)劃

一、單純形法的解題過程二、線性規(guī)劃模型的變換三、單純形法的計算方法四、一般情況的處理--人工變量法

（2）檢驗、確定進基變量如果任何一個非基變量的值增加都不能使目標函數(shù)值增加，即所有檢驗數(shù)非正，則當前的基本可行解就是最優(yōu)解，計算結(jié)束。若存在檢驗數(shù)大于0，那么絕對值最大者對應的非基變量xj稱為“進基變量”，轉(zhuǎn)（3）。單純形法的基本步驟:

這個基變量xr稱為出基變量。轉(zhuǎn)（4）。如果進基變量的值增加時，所有基變量的值都不減少，即所有aij非正，則表示可行域是不封閉的，且目標函數(shù)值隨進基變量的增加可以無限增加，此時，不存在有限最優(yōu)解，計算結(jié)束。(3)確定出基變量滿足單純形法的基本步驟:

（4）迭代運算將進基變量作為新的基變量，出基變量作為新的非基變量，確定新的基、新的基本可行解和新的目標函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上重復（1）。單純形法的基本步驟:

注意：單純形法中

1.每一步運算只能用矩陣初等行變換；

2.表中第3列(b列)的數(shù)總應保持非負（≥0）

3.當所有檢驗數(shù)均非正（≤0）時，得到最優(yōu)單純形表。

4.可能出現(xiàn)的特殊情況

單純形法求解中的特殊情況

1．最終產(chǎn)生最優(yōu)值的單純形表中，某一非基本變量的檢驗數(shù)＝0，意味著作任何增大，目標函數(shù)的最優(yōu)值不變．此時線性規(guī)劃問題的最優(yōu)解并不唯一，有多重最優(yōu)解．（見下面例題）例用單純形法求解下列規(guī)劃問題解:令于是原線性規(guī)劃問題變?yōu)闃藴市问剑簡渭冃伪淼?0-1/81/41-3x1

00-10Cj-Zj013/81/43-1x200-10Cj-Zj1[4]0-1/214-1x4-11?02-1x2

-2

2

00Cj-Zj631016-1x42-2[2]104-1x3x1x2x3x4-3-1

-1-1b最優(yōu)解為：最優(yōu)值為：2．當樞列（進基變量所在列）中的每一項系數(shù)不是0就是負值時，說明所有約束條件對進基變量的增加都無約束作用，因此目標函數(shù)可以無限地增加．這種情況我們稱為無有限最優(yōu)解（或稱有無界解或無最優(yōu)解）．但在現(xiàn)實中，不可能有此情況，往往是模型建立錯誤，遺漏了一些約束條件所致．

單純形法求解中的特殊情況

單純形法求解中的特殊情況

3．在選取進基變量時，有2個及2個以上變量的檢驗數(shù)具有相同的最大正值（極小化問題為相同的最小負值），這時可任選其中一個變量進基．選擇進基變量的不同，可能在達到最優(yōu)解前迭代的次數(shù)也不同，但事先無法預測．

4．出現(xiàn)相同的最小比值，此時可從具有相同最小比值所對應的基本變量中，選擇下標最大的那個基本變量為出基變量．這時有可能出現(xiàn)退化的基本可行解，即至少有一個基本變量為零（見規(guī)劃教材例2-8中的表2-6和表2-7）．出現(xiàn)退化的基本可行解對運算帶來麻煩，理論上可能出現(xiàn)單純形法陷入循環(huán)或閉環(huán)，在每次迭代中值保持不變，不能使解趨向最優(yōu)解．但幸運的是，在實際應用中從未遇到或發(fā)生過這種情況．盡管如此，人們還是對如何防止出現(xiàn)循環(huán)作了大量研究。提出了各種避免循環(huán)的方法。

單純形法求解中的特殊情況

在選擇進基變量和出基變量時作以下規(guī)定：

①在選擇進基變量時，在所有

j>0的非基變量中選取下標最小的進基；

②當有多個變量同時可作為出基變量時，選擇下標最小的那個變量出基。這樣就可以避免出現(xiàn)循環(huán),當然，這樣可能使收斂速度降低。#避免循環(huán)的方法：五、一般情況的處理--人工變量法

一般情況的處理：主要是討論初始基本可行解不明顯時，常用的方法。例如

P533(4)規(guī)范化規(guī)范化標準化考慮一般問題：

bi>0

，i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0引入人工變量

xn+i

≥0，i=1

,…,m；

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

...am1x1+am2x2+…+amnxn+xn+m

=bm

x1,x2...

xn,xn+1,…,xn+m

≥01．兩階段法：兩階段法是把一般問題的求解過程分為兩步：第一步：求解原問題的一個基本解：建立一個輔助問題。對于前面的約束方程組，構(gòu)造一個標函數(shù)為：Minz＝

xn+1＋

xn+2＋

…＋

xn+m這樣，從目標最優(yōu)角度迫使人工變量取零值，以達到原問題一個基本可行解的目的。這個階段的輔助問題有下列明顯的事實：設(shè)

X*

=(x*1,x*2,…,x*n,x*n＋1,…,x*n＋m）為這個問題的最優(yōu)解，那么，若

x*n+1

＝x*n＋2＝…＝x*n＋m＝0，則(x*1,x*2,…,x*n

）為原問題的一個基本可行解，這時目標函數(shù)值為零；否則，即x*n＋1,…,x*n＋m不全為零時，說明原問題無可行解。即引入人工變量

xn+i

≥0，i=1,…,m；

構(gòu)造:Min

Ｚ＝xn+1

＋xn+2

＋…

＋xn+m

MaxＺ

=-xn+1

-xn+2

-…-xn+m

a11x1+a12x2+…+a1nxn+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2

=b2

.

.

.am1x1+am2x2+…+amnxn+xn+m

=bmx1，

x2，...

，xn，

xn+1，…，xn+m

≥0

顯然，xj=0，j=1,…,n;

xn+i=bi，

i=1,…,m

是基本解,它對應的基是單位矩陣。

結(jié)論：若得到的最優(yōu)解滿足xn+i=0

i

=1,…,m

，則是原問題的基本可行解;否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。第二步：求解原問題：以第一步得到的基本可行解為初始基本可行解，用單純形法求解原問題。在表格計算過程中，這一步的初始單純形表可這樣產(chǎn)生（1）由第一步的最優(yōu)單純形表刪去xn＋1

，xn＋2

，…，xn+m

列；（2）把第一行的目標函數(shù)系數(shù)行換為原問題目標函數(shù)的系數(shù)；（3）檢驗數(shù)行直接用前文介紹的方法在表格上計算得到，即用xj的價值系數(shù)cj減去cB列的各元素與xj列各對應元素的乘積，把計算結(jié)果填入xj列的最后一行，得到檢驗數(shù)σj

。例1：Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0第一步

求解原問題的一個基本解：

Max

Z=-x5-x6

x1+2x2+3x3+x5=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6≥0

第一階段得到原問題的基本可行解:(0，15/7，25/7，52/7)T第二步，求解原問題：

把基本可行解填入表中

得到原問題的最優(yōu)解:(25/3，10/3，0，11)T最優(yōu)目標值：112/3

引入人工變量xn+i

≥0（i=1,…,m）及充分大正數(shù)M

。得到：

MaxZ=c1x1+c2x2+cnxn+M

xn+1

+Mxn+m

a11

x1+a12

x2+…+a1n

xn+xn+1

=b1

a21

x1+a22

x2+…+a2n

xn+xn+2

=b2...

am1

x1+am2

x2+…+amn

xn+xn+m

=bm

x1,x2，…

，xn

，xn+1，…

，xn+m

≥02．大M法Max

Z=5x1+2x2+3x3-x4-M

x5-M

x6

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6

≥0例1：Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0第一節(jié)存貯問題及其基本概念

一、存貯問題

問題1醫(yī)院血庫的存血問題一方面，為搶救病人，血庫必須儲備一定數(shù)量的血液，血庫存量越多，不僅搶救病人方便，應急能力越強，而且輸血越多，血庫經(jīng)濟效益也越好；另—方面，血庫存血要用恒溫箱等醫(yī)療設(shè)備，血存的越多，設(shè)備數(shù)量及為此支付的費用就越多，如果存放時間太長，血液還可能變質(zhì)，造成更大損失?？梢?，血存得多，整體效益未必好。一、存貯問題

問題2中成藥的存放問題藥庫存放中成藥的品種數(shù)量越多，醫(yī)生看病開藥方選擇藥物的余地就越大，病人取藥也越方便。但是存貯量大，所占空間也就大，支付的各種費用也多，特別是中成藥受溫度，濕度及蟲害影響極易變質(zhì)，可能造成更大經(jīng)濟損失。顯然，存貯量大，綜合效益也未必好。一、存貯問題

一方面說明了存貯問題的重要性和普遍性，另方面又說明了存貯問題的復雜性和多樣性。近年來，隨計算機的普及與推廣，存貯論的應用也越來越廣泛，已滲透到社會生活的各個領(lǐng)域。在衛(wèi)生系統(tǒng)，諸如血庫管理、藥品存貯等都有所應用。

二、存貯模型中的基本概念

1．需求

根據(jù)需求的時間特征．可將需求分為連續(xù)性需求和間斷性需求。在連續(xù)性需求中，隨著時間的變化，需求連續(xù)地發(fā)生，因而存貯也連續(xù)地減少，在間斷性需求中，需求發(fā)生的時間極短，可以看作瞬時發(fā)生，因而存貯的變化是跳躍式地減少。根據(jù)需求的數(shù)量特征，可將需求分為確定性需求和隨機性需求。在確定性需求中，需求發(fā)生的時間和數(shù)量是確定的。在隨機性需求中，需求發(fā)生的時間或數(shù)量是不確定的。對于隨機性需求，要了解需求發(fā)生時間和數(shù)量的統(tǒng)計規(guī)律性。二、存貯模型中的基本概念

2．補充

(a)

開始訂貨到開始補充(開始生產(chǎn)或貨物到達)為止的時間。這部分時間如從訂貨后何時開始補充的角度看，稱為拖后時間，如從為了按時補充需要何時訂貨的角度看，稱為提前時間。在同一存貯問題中，拖后時間和提前時間是一致的，只是觀察的角度不同而已。在實際存貯問題中，拖后時間可能很短，以致可以忽略．此時可以認為補充能立即開始，拖后時間為零。如拖后時間較長，則它可能是確定性的，也可能是隨機性的。二、存貯模型中的基本概念

2．補充

(b)開始補充到補充完畢為止的時間(即入庫或生產(chǎn)時間)。這部分時間和拖后時間一樣，可能很短(因此可以忽略)，也可能很長，可能是確定的，也可能是隨機的。對存貯問題進行研究的目的是給出一個存貯策略，用以回答在什么情況下需要對存貯進行補充。什么時間補充，補充多少。一個存貯策略必須滿足可行性要求，即它所給出的補充方案是可以實行的，并且能滿足需求的必要條件。二、存貯模型中的基本概念

3．費用在存貯論研究中，常以費用標準來評價和優(yōu)選存貯策略。為了正確地評價和優(yōu)選存貯策略，不同存貯策略的費用計算必須符合可比性要求。最重要的可比性要求是時間可比和計算口徑可比。

時間可比是指各存貯策略的費用發(fā)生時間范圍必須一致。實際計算時，常用—個存貯周期內(nèi)的總費用或單位時間平均總費用來衡量；

計算口徑可比是指存貯策略的費用統(tǒng)計項目必須一致。經(jīng)常考慮的費用項目有存貯費、訂貨費、生產(chǎn)費、缺貨費等。在實際計算存貯策略的費用時，對于不同存貯策略都是相同的費用可以省略。二、存貯模型中的基本概念

3．費用

(1)存貯費：存貯物資資金利息、保險以及使用倉庫、保管物資、物資損壞變質(zhì)等支出的費用，一般和物資存貯數(shù)量及時間成比例。

(2)訂貨費：向外采購物資的費用。其構(gòu)成有兩類：一類是訂購費用，如手續(xù)費、差旅費等，它與訂貨次數(shù)有關(guān)，而和訂貨數(shù)量無關(guān)；另—類是物資進貨成本，如貸款、運費等，它與訂貨數(shù)量有關(guān)。二、存貯模型中的基本概念

3．費用

(3)生產(chǎn)費：自行生產(chǎn)需存貯物資的費用。其構(gòu)成有兩類：一類是裝配費用(準備結(jié)束費用)，如組織或調(diào)整生產(chǎn)線的有關(guān)費用，它同組織生產(chǎn)的次數(shù)有關(guān)，而和每次生產(chǎn)的數(shù)量無關(guān)；另一類是與生產(chǎn)的數(shù)量有關(guān)的費用，如原材料和零配件成本、直接加工費等。

(4)缺貨費：存貯不能滿足需求而造成的損失。如失去銷售機會的損失，停工待料的損失，延期交貨的額外支出，對需方的損失賠償?shù)?。當不允許缺貨時，可將缺貨費作無窮大處理。二、存貯模型中的基本概念

4.存貯策略

所謂一個存貯策略，是指決定什么情況下對存貯進行補充，以及補充數(shù)量的多少。下面是一些比較常見的存貯策略。

(1)t-循環(huán)策略：不論實際的存貯狀態(tài)如何，總是每隔一個固定的時間t，補充一個固定的存貯量Q。

(2)(t，S)策略：每隔一個固定的時間t補充一次，補充數(shù)量以補足一個固定的最大存貯量S為準。因此，每次補充的數(shù)量是不固定的，要視實際存貯量而定。當存貯(余額)為I時，補充數(shù)量為Q=S-I。二、存貯模型中的基本概念

4.存貯策略

(3)(s，S)策略：當存貯(余額)為I，若I>s，則不對存貯進行補充；若I≤s，則對存貯進行補充，補充數(shù)量Q=S-I。補充后存貯量達到最大存貯量S。s稱為訂貨點(或保險存貯量、安全存貯量、警戒點等)。在很多情況下，實際存貯量需要通過盤點才能得知。若每隔一個固定的時間t盤點一次，得知當時存貯I，然后根據(jù)I是否超過訂貨點s，決定是否訂貨、訂貨多少，這樣的策略稱為(t，s，S)策略。二、存貯模型中的基本概念

5.存貯模型

所謂存貯模型，指為控制物資的合理存貯數(shù)量和選擇最佳訂貨時間或訂貨點而建立的數(shù)學模型。按變量的類型不同，存貯模型可分為兩類：一類為確定型存貯模型，適用于需求方式為確定性的存貯問題；另一類為隨機性存貯模型，適用于需求方式為隨機性的存貯問題。第二節(jié)確定型存貯模型

一、模型一：不允許缺貨，補充時間極短為了便于描述和分析，對模型作如下假設(shè)：(1)需求是連續(xù)均勻的，即需求速度(單位時間的需求量)R是常數(shù)；(2)補充可以瞬時實現(xiàn)，即補充時間(拖后時間和生產(chǎn)時間)近似為零；(3)單位存貯費(單位時間內(nèi)單位存貯物的存貯費用)為C1。由于不允許缺貨，故單位缺貨費(單位時間內(nèi)每缺少一單位存貯物的損失)C2為無窮大。訂貨費(每訂購一次的固定費用)為C3。貨物(存貯物)單價為K．采用t-循環(huán)策略。設(shè)補充間隔時間為t，補充時存貯已用盡，每次補充量(訂貨量)為Q，則存貯狀態(tài)圖見圖6-1。模型一：不允許缺貨，補充時間極短一次補充量Q必須滿足t時間內(nèi)的需求，故Q=Rt。因此，訂貨費為C3+KRt，而t時間內(nèi)的平均訂貨費為C3/t+KR。由于需求是連續(xù)均圖6-1勻的，故t時間內(nèi)的平均存貯量為模型一：不允許缺貨，補充時間極短t時間內(nèi)的平均存貯費為1/2C1Rt。由于不允許缺貨，故不需考慮缺貨費用。所以t時間內(nèi)的平均總費用C(t)隨t的變化而變化，其圖像見圖6-2。當t=t*時，C(t*)＝C*是C(t)的最小值。為了求得t*，可解模型一：不允許缺貨，補充時間極短由于存貯物單價K和補充量Q無關(guān)，它是一常數(shù)，因此，存貯物總價KQ和存貯策略的選擇無關(guān)。所以，為了分析和計算的方便，在求費用函數(shù)C(t)時，常將這一項費用略去。略去這一項費用后，模型一：不允許缺貨，補充時間極短

例1某醫(yī)院每月需要某重要藥品400件，每件定價2000元，不可缺貨。設(shè)每件每月保管費為0.1%，每次定購費為100元，假設(shè)該藥品的進貨可以隨時實現(xiàn)。問應怎樣組織進貨，才能最經(jīng)濟。

解：K=2000元/件，R=400件/月，Cl=2000·0.1％=2元/件·月，C3=100元/次。模型一：不允許缺貨，補充時間極短所以，應該每隔15天進貨一次，每次進貨該藥品200件，能使總費用(存貯費和訂購費之和)為最少400元/月，平均每天約26.67元。若按年計劃，則每年大約進貨12/0.5=24(次)，每次進貨200件。模型一：不允許缺貨，補充時間極短

例2

某大醫(yī)院每月消耗青霉素針劑160000盒，每盒每月保管費0.2元，不允許缺貨，試比較每次訂貨費為1000元或100元兩種情況下的經(jīng)濟訂貨批量。

解：Cl=0.2元/盒·月，R=160000盒/月。（1）（（（模型一：不允許缺貨，補充時間極短（2）模型一：不允許缺貨，補充時間極短本例由于訂貨費不同，我們采用不同策略，當訂貨費低時，我們采用多次小批量，可使費用達最優(yōu)；當訂貨費高時，我們采用少次大批量，可使費用達最優(yōu)。模型二：允許缺貨，補充時間較長

模型假設(shè)條件：(1)需求是連續(xù)均勻的，即需求速度R為常數(shù)；(2)補充需要一定時間。不考慮拖后時間，只考慮生產(chǎn)時間。即一旦需要，生產(chǎn)可立刻開始，但生產(chǎn)需一定周期。設(shè)生產(chǎn)是連續(xù)均勻的，即生產(chǎn)速度P為常數(shù)。同時，設(shè)P>R；(3)單位存貯費為C1，單位缺貨費為C2，訂購費為C3。不考慮貨物價值。模型二：允許缺貨，補充時間較長存貯狀態(tài)圖見圖6-3。[0，t]為一個存貯周期，t1時刻開始生產(chǎn)，t3時刻結(jié)束生產(chǎn)；[0，t2]時間內(nèi)存貯為零，t1時達到最大缺貨量B；[t1，t2]時間內(nèi)產(chǎn)量一方面以速度R滿足需求，另方面以速度(P-R)彌補[0，t1]時間內(nèi)的缺貨。至t2時刻缺貨補足；模型二：允許缺貨，補充時間較長[t2，t3]時間內(nèi)產(chǎn)量一方面以速度R滿足需求，另方面以速度(P-R)增加存貯。至t3時刻達到最大存貯量A，并停止生產(chǎn)；[t3，t]時間內(nèi)以存貯滿足需求，存貯以速度R減少。至t時刻存貯降為零，進入下一個存貯周期。下面，根據(jù)模型假設(shè)條件和存貯狀態(tài)圖，首先導出[0，t]時間內(nèi)的平均總費用(即費用函數(shù))，然后確定最優(yōu)存貯策略。

模型二：允許缺貨，補充時間較長從[0，t1]看，最大缺貨量B=Rt1；從[t1，t2]看，最大缺貨量B＝(P-R)(t2-t1)。故有Rt1=(P-R)(t2-t1)，從中解得：

（6-6）從[t2,t3]看，最大存貯量A＝(P-R)(t3-t2)：從[t3，t]看，最大存貯量A＝R(t-t3)。故有(P-R)(t3-t2)＝R(t-t3)，從中解得：（6-7）在[0，t]時間內(nèi)，存貯費為：缺貨費為：模型二：允許缺貨，補充時間較長故[0，t]時間內(nèi)平均總費用為：將(6-6)和(6-7)代入，整理后得：模型二：允許缺貨，補充時間較長解方程組容易證明，此時的費用C(t*，t2*)是費用函數(shù)C(t，t2)的最小值。模型二：允許缺貨，補充時間較長因此，模型二的最優(yōu)存貯策略各參數(shù)值為：最優(yōu)存貯周期

(6-9)經(jīng)濟生產(chǎn)批量

(6-10)

缺貨補足時間(6-11)模型二：允許缺貨，補充時間較長開始生產(chǎn)時間(6-12)結(jié)束生產(chǎn)時間(6-13)最大存貯量(6-14)最大缺貨量(6-15)平均總費用(6-16)模型二：允許缺貨，補充時間較長例3某藥廠生產(chǎn)某種藥品，正常生產(chǎn)條件下每天可生產(chǎn)100件。根據(jù)供貨合同，需每天80件供貨。存貯費每件每天2元，缺貨費每件每天5元，每次生產(chǎn)準備費用(裝配費)為800元，求最優(yōu)存貯策略。解依題意，符合模型二的條件且P=100件/d，R=80件/d，Cl=2元/d·件，C2=5元/d·件，C3=800元/次。模型二：允許缺貨，補充時間較長利用公式(6-9)～(6-16)，可得最優(yōu)存貯周期

經(jīng)濟生產(chǎn)批量缺貨補足時間模型二：允許缺貨，補充時間較長開始生產(chǎn)時間結(jié)束生產(chǎn)時間最大存貯量最大缺貨量平均總費用模型二：允許缺貨，補充時間較長可以把模型一看作模型二的特殊情況。在模型二中，取消允許缺貨和補充需要一定時間的條件，即C2→，P→，則模型二就是模型一。事實上，如將C2→和P→代入模型二的最優(yōu)存貯策略各參數(shù)公式，就可得到模型一的最優(yōu)存貯策略。只是必須注意，按照模型一的假設(shè)條件，應有：t1*＝t2*=t3*=0A*＝Q*B*=0模型三：不允許缺貨，補充時間較長

在模型二的假設(shè)條件中，取消允許缺貨條件(即設(shè)C2→，t2=0)，就成為模型三。因此，模型三的存貯狀態(tài)圖和最優(yōu)存貯策略可以從模型二直接導出。模型三的存貯狀態(tài)圖見圖6-4。最優(yōu)存貯周期經(jīng)濟生產(chǎn)批量結(jié)束生產(chǎn)時間最大存貯量平均總費用模型三：不允許缺貨，補充時間較長

例4某醫(yī)院2001年每月需用某種針劑10000支，每月購進25000支(在邊補充邊消耗期間，訂購后需6天才開始到貨)，單位存貯費為0.05元/支·月，單位訂購費1000元，試求最優(yōu)存貯策略。解：本例特點是補充除需要入庫時間，還需考慮拖后時間。因此，訂購時間應在存貯降為零之前的第6天。除此之外，本例和模型三的假設(shè)條件完全一致。本例的存貯狀態(tài)圖見圖6-5。模型三：不允許缺貨，補充時間較長

從圖6-5可見，拖后時間為[0，t0]，存貯量L應恰好滿足這段時間的需求，故L=Rt0由題意知P=25000支/月R=10000支/月Cl=0.05元/支·月C3=1000元/次t0=6天，L=100006/30=2000支。代入式(6-17)~(6-21)可算得：最優(yōu)存貯周期模型三：不允許缺貨，補充時間較長

模型三：不允許缺貨，補充時間較長

經(jīng)濟生產(chǎn)批量結(jié)束生產(chǎn)時間最大存貯量平均總費用模型四：允許缺貨，補充時間極短

在模型二的假設(shè)條件中，取消補充需要一定時間的條件(即設(shè)P→)，就成為模型四。因此，和模型三一樣，模型四的存貯狀態(tài)圖和最優(yōu)存貯策略也可以從模型二中直接導出。模型四的存貯狀態(tài)圖見圖6-6。最優(yōu)存貯策略各參數(shù)：最優(yōu)存貯周期

經(jīng)濟生產(chǎn)批量生產(chǎn)時間最大存貯量最大缺貨量平均總費用模型四：允許缺貨，補充時間極短

例5假設(shè)某醫(yī)院每年均勻地耗用A種衛(wèi)生材料24000單位(允許缺貨，瞬時補充)。已知每單位A材料每月存貯費0.1元，每采購一次該材料需采購費350元，單位缺貨費為0.2元/單位·月，試求最優(yōu)存貯策略。解：由題意知：R=24000/12=2000單位Cl=0.1元/單位·月C2=0.2元/單位·月C3=350元/次,可算得：最優(yōu)存貯周期

經(jīng)濟生產(chǎn)批量

模型四：允許缺貨，補充時間極短

生產(chǎn)時間最大存貯量最大缺貨量平均總費用模型四：允許缺貨，補充時間極短

對于確定型存貯問題，上述四個模型是最基本的模型。其中，模型一、三，四又可看作模型二的特殊情況。在每個模型的最優(yōu)存貯策略的各個參數(shù)中，最優(yōu)存貯周期t*是最基本的參數(shù)，其它各個參數(shù)和它的關(guān)系在各個模型中都是相同的。根據(jù)模型假設(shè)條件的不同，各個模型的最優(yōu)存貯周期t*之間也有明顯的規(guī)律性。因子對應了是否允許缺貨的假設(shè)條件，因子對應了補充是否需要時間的假設(shè)條件。

模型四：允許缺貨，補充時間極短

一個存貯問題是否允許缺貨或補充是否需要時間，完全取決于對實際問題的處理角度，不存在絕對意義上的不允許缺貨或絕對意義上的補充不需要時間。如果缺貨引起的后果或損失十分嚴重，則從管理的角度應當提出不允許缺貨的建模要求；否則，可視為允許缺貨的情況。至于缺貨損失的估計，應當力求全面和精確。如果補充需要的時間相對于存貯周期是微不足道的，則可考慮補充不需要時間的假設(shè)條件；否則，需要考慮補充時間。在考慮補充時間時，必須分清拖后時間和生產(chǎn)時間，兩者在概念上是不同的。為了鼓勵大批量訂貨，供方常對需方實行價格優(yōu)惠。訂貨批量越大，貨物價格就越便宜。模型五除含有這樣的價格刺激機制外，其它假設(shè)條件和模型一相同。一般地，設(shè)訂貨批量為Q，對應的貨物單價為K(Q)。當Qi-1≤Q<Qi，時，K(Q)＝Ki(i=1，2,…，n)。其中，Qi為價格折扣的某個分界點，且0≤Q0<Ql<Q2<…<Qn，K1>K2>…>Kn。由式(6-1)，在一個存貯周期內(nèi)模型五的平均總費用(費用函數(shù))為：其中，Q=Rt。當Qi-1≤Q=Rt<Qi時，K(Q)=Kii=1,2,…,nC(t)為關(guān)于t的分段函數(shù)。為了了解它的性質(zhì)，以n＝3為例，畫出其圖象，見圖6-7。模型五：價格與訂貨批量有關(guān)的存貯模型

模型五：價格與訂貨批量有關(guān)的存貯模型

(1)計算。若，則平均總費用：(2)計算(3)若，則C*對應的批量為最小費用訂購批量Q*。相應地，和最小費用C*對應的訂購周期t*=Q*/R。模型五：價格與訂貨批量有關(guān)的存貯模型

例6醫(yī)院每周需打印紙45箱，存貯費每箱每周5元，每次訂購費50元，不允許缺貨。打印紙進貨時若(1)訂貨量1箱～9箱時，每箱120元；(2)訂貨量10箱～49箱時，每箱100元；(3)訂貨量50箱～99箱時，每箱95元；(4)訂貨量99箱以上時，每箱90元。求最優(yōu)存貯策略。解R=45箱/周，C1=5元/周，C3=50元/次Q0=0，Ql=1，Q2=10，Q3=50，Q4=100K1=120，K2=100，K3=95，K4=90模型五：價格與訂貨批量有關(guān)的存貯模型

標準的線性規(guī)劃模型不含有明顯的單位基

——人工變量法引入人工變量xn+i

≥0，i=1

,…,m；x1,x2...

xn,xn+1,…,xn+m

≥

0a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

am1x1+am2x2+…+amnxn+xn+m

=bm

......

1．兩階段法：第一步：求解原問題的一個基本解建立一個輔助問題。構(gòu)造一個目標函數(shù)為：MinZ＝

xn+1＋

xn+2＋

…＋

xn+m第二步：求解原問題：以第一步得到的基本可行解為初始基本可行解，用單純形法求解原問題。2．大M法：引入充分大正數(shù)

M

，改造目標函數(shù)MaxZ=c1x1+c2x2+cnxn-

Mxn+1-…-

Mxn+m

一、對偶問題的提出

二、對偶規(guī)劃的形式

1.對稱形式的對偶問題

2.非對稱形式的對偶問題

3.一般形式對偶問題三、對偶規(guī)劃的基本性質(zhì)四、對偶單純形法五、靈敏度分析小結(jié)一、對偶問題的提出

線性規(guī)劃是研究資源最優(yōu)利用的理論，所謂最優(yōu)利用包括兩方面的含意，即者包含相同的1.在一定的資源條件下完成最多的任務(wù)；2.完成給定的任務(wù)，使用的資源最小。因此，線性規(guī)劃就有一個有趣的特征：

任何一個求極大值的規(guī)劃問題，必存在一個與其匹配的求極小值的規(guī)劃問題

它們的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個特征稱為對偶性。如果稱前一個問題為原問題，則后一個問題便叫做原問題的對偶問題；反之，若稱后一個問題為原問題，則前一個問題便是對偶問題，即對偶問題是相對而言的。

例1

某醫(yī)院營養(yǎng)科用糖、蛋白質(zhì)和脂肪生產(chǎn)四種食品A、B、C、D,一個人每月各種營養(yǎng)成分的最低需求量、不同食品的營養(yǎng)成分含量及其單價如表1-8所示。問某人每月怎樣購買這些食品，才能既滿足營養(yǎng)要求，又可以花錢最少？

表1-8食品營養(yǎng)成分含量及單價ABCD最低需求量（單位）

含量（單位/公斤）糖蛋白質(zhì)脂肪533221412245604035單價（元/公斤）1.50.70.91.2解：設(shè)某人每月購買食品A、B、C、D各為x1、

x2、x3、x4公斤，共花費Z元，于是它的數(shù)學模型為：

例2

假設(shè)營養(yǎng)科不安排生產(chǎn)食品A、B、C、D，而出售單一營養(yǎng)成分的糖、蛋白質(zhì)和脂肪。仍用例1中的數(shù)據(jù)，問該營養(yǎng)科如何確定糖、蛋白質(zhì)和脂肪的單價，才能在市場竟爭中立于不敗之地，并可獲得利潤最多？現(xiàn)在從另一個角度來討論該問題。

同理，由單一營養(yǎng)成分食品合成的食品B、C和D的單價分別不得超過0.7、0.9和1.2元/公斤，故有：

2y1+2y2+y3≤0.74y1+y2+2y3≤0.92y1+4y2+5y3≤1.2解：設(shè)糖、蛋白質(zhì)和脂肪的單價分別為y1元/單位、y2元/單位和y3元/單位，某人每月購買單一營養(yǎng)成分食品共花費W

元。欲使該廠獲利最多，應該讓

W=60y1+40y2+35y3達到最大值。

如要該營養(yǎng)科在市場竟爭中穩(wěn)操勝券，以單一營養(yǎng)成分食品合成食品A單價不得超過1.5元/公斤，即

5y1+3y2+3y3≤1.5例1是例2的對偶問題

這里，y1，y2和y3稱為單一營養(yǎng)成分食品的影子價格，影子價格并不是單一營養(yǎng)成分食品的實際成本或價格，而是從生產(chǎn)活動的反面來分析問題，即從出售合成食品的收益來估計所利用的單一營養(yǎng)成分食品的價值。例1與例2互為對偶線性規(guī)劃

我們應用單純形法求解例1和例2，將會發(fā)現(xiàn)原規(guī)劃的最后單純形表不僅給出了原規(guī)劃的最優(yōu)解，而且它的對應的檢驗行Cj-Zj也給出了對應的對偶規(guī)劃的最優(yōu)解（符號相反）。

所以兩個規(guī)劃問題，互相對偶時，只要解一個就夠了。對偶規(guī)劃的解，就是原規(guī)劃中的影子價格，也就是資源的擁有者寧愿停止生產(chǎn)活動而將資源轉(zhuǎn)讓出去的最低價格。返回二、對偶規(guī)劃的形式

以上從一個食品生產(chǎn)問題引出了對資源的估價問題，得到了對偶規(guī)劃。實際上，對于一般的線性規(guī)劃模型可以直接給出其對偶規(guī)劃模型，并不需要像上面那樣經(jīng)過一番討論。為此，我們需要分析原規(guī)劃與對偶規(guī)劃之間的關(guān)系。對偶規(guī)劃的形式分為對稱形式和非對稱形式。返回1.對稱形式的對偶問題稱具有下面形式的一對規(guī)劃是對稱形式的對偶規(guī)劃：它的對偶規(guī)劃y1,y2,…,ym稱為對偶變量

例1和例2中的一對規(guī)劃就是對稱形式的系數(shù)矩陣互為轉(zhuǎn)置

一對對稱形式的對偶問題的對應關(guān)系：Max，≤，變量皆非負

Min，≥，變量皆非負變量約束條件價值系數(shù)右端常數(shù)系數(shù)矩陣為AA轉(zhuǎn)置矩陣AT（1）若一個模型目標函數(shù)是求“極大”，約束條件為“小于等于”的不等式，則對偶模型的目標函數(shù)是求“極小”，約束是“大于等于”的不等式；即“Max，≤”?“Min，≥”（2）若一個模型有n個變量，m個約束條件,則對偶模型有n個約束條件；m個變量；（3）一個模型目標函數(shù)中價值系數(shù)等于對偶模型中相應約束條件的右端常數(shù)；一個模型約束條件中的右端常數(shù)等于對偶模型目標函數(shù)中相應的價值系數(shù)；（4）若一個模型約束條件中的系數(shù)矩陣為A，則對偶模型約束條件中的系數(shù)矩陣為A轉(zhuǎn)置矩陣AT；（5）兩個規(guī)劃模型中的變量皆非負。一對對稱形式的對偶規(guī)劃之間具有下面的對應關(guān)系：

原變量xj對偶變量y?

產(chǎn)品類別

資源類別

≤b1

≤b2

≤bm

資源價格

產(chǎn)品價值\∨\∨\∨

МinWМa(chǎn)xZ表1-10線性規(guī)劃原問題與對偶問題間變換關(guān)系例3

求下列線性規(guī)劃的對偶規(guī)劃（書中例15）對偶變量y1y2y3y1y2y3解：這兩個模型都是對稱形式的規(guī)劃模型，它們的對偶規(guī)劃分別為：對偶變量x1x2x3x1x2返回2.非對稱形式的對偶問題

對于非對稱形式的規(guī)劃，可以按照下面的對應關(guān)系直接給出其對偶規(guī)劃。

（1）將模型統(tǒng)一為“max，≤”或“min，≥”的形式，對于其中的等式約束按下面（2）、（3）中的方法處理；

（2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制；

一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。含有等式約束和變量無符號限制

（3）若原規(guī)劃某個變量的值沒有非負限制，則在對偶問題中與此變量對應的那個約束為等式。例如：設(shè)原規(guī)劃中第一個約束為等式

a11

x1

+…+a1n

xn

=b1那么，這個等式與下面兩個不等式等價統(tǒng)一成≤

這樣，原規(guī)劃模型可以寫成對偶變量

于是y1

沒有非負限制，即

此時已轉(zhuǎn)化為對稱形式，直接寫出對偶規(guī)劃這里，把y1

看作是a11

x1

+…+a1n

xn

=b1

非對稱形式的對偶規(guī)劃的對應關(guān)系

非對稱形式含有等式約束和變量無符號限制變量無符號限制等式約束2.非對稱形式的對偶問題

例4

寫出下面線性規(guī)劃的對偶規(guī)劃模型解先將約束條件變形為“≤”形式對偶變量y1y2y3y4y5

再根據(jù)非對稱形式的對應關(guān)系，直接寫出對偶規(guī)劃對偶變量x1x2x3x4例5

設(shè)有線性規(guī)劃問題（書中例16）試寫出它的對偶問題。解：對偶規(guī)劃為：對偶變量y1y2例6

設(shè)有線性規(guī)劃問題（書中例17）試寫出它的對偶問題。解：所求的對偶問題是：對偶變量y1y2返回3.一般形式的對偶關(guān)系見下表所示

對于一般形式的對偶問題,也可以不考慮對稱形式的轉(zhuǎn)化,而直接遵循如下對偶關(guān)系進行轉(zhuǎn)化。返回小結(jié)

對稱形式的對偶問題Max，≤，變量皆非負

Min，≥，變量皆非負變量約束條件價值系數(shù)右端常數(shù)系數(shù)矩陣為AA轉(zhuǎn)置矩陣AT二、對偶規(guī)劃的形式

對稱形式的對偶問題Max，≤，變量皆非負

Min，≥，變量皆非負變量約束條件價值系數(shù)右端常數(shù)系數(shù)矩陣為AA轉(zhuǎn)置矩陣AT

一般形式的對偶關(guān)系

非對稱形式的對偶規(guī)劃的對應關(guān)系

非對稱形式含有等式約束和變量無符號限制變量無符號限制等式約束見下表所示

二、對偶規(guī)劃的形式返回

設(shè)有原線性規(guī)劃問題，它的矩陣表示如下：三、對偶規(guī)劃的基本性質(zhì)式中其對偶規(guī)劃的矩陣表示是這里，A，B，C

與上面的原規(guī)劃相同。

下面我們用矩陣表示法說明對偶問題的基本性質(zhì)：三、對偶規(guī)劃的基本性質(zhì)三、對偶規(guī)劃的基本性質(zhì)

性質(zhì)1

線性規(guī)劃對偶問題的對偶是原問題。

性質(zhì)2

若分別為互為對偶線性規(guī)劃問題的可行解，則有

性質(zhì)3

若分別為互為對偶線性規(guī)劃問題的可行解，則當時，是最優(yōu)解。

性質(zhì)4

若互為對偶的兩個線性規(guī)劃問題中，有一個有最優(yōu)解，那么另一個也一定有最優(yōu)解，且最優(yōu)的目標函數(shù)值相等。

性質(zhì)5

原問題的判別數(shù)對應著對偶問題的一個解。有了性質(zhì)5，在求解線性規(guī)劃問題時，原規(guī)劃問題單純形表中的判別數(shù)，就是對偶問題的一個解，但符號相反。返回四、對偶單純形法

我們前面介紹的一般單純形法，是從“可行”(右端項非負）開始，逐步地迭代運算，直到得出最優(yōu)解。而應用對偶規(guī)劃的性質(zhì)，可以找到一種求解線性規(guī)劃的新方法——對偶單純形法。對偶單純形法則是從“不可行”(右端項含負）開始，在保持最優(yōu)性之下逐步迭代，直到不可行變?yōu)榭尚?，即得到可行最?yōu)解為止。當對偶問題的約束條件的數(shù)目較原問題為少時，應用對偶單純形法求解較為方便。單純形法思路（保持可行性）對偶單純形法思路（保持最優(yōu)性）可行(右端項非負）非最優(yōu)（檢驗數(shù)非負）可行最優(yōu)解可行非最優(yōu)（檢驗數(shù)非負）不可行(右端項含負）最優(yōu)（檢驗數(shù)非正）可行最優(yōu)解不可行最優(yōu)（檢驗數(shù)非正）

對偶單純形法的基本思想

對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數(shù)非正）。如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。例7

利用對偶單純形法求解解：

將原問題化成再化成標準形列表用對偶單純形法求解：

0

S50S6[-1]-21-11021-4-101-3←2

Zj

Cj-Zj000000-1-40-3000

-1x10S612-11-100-3[-2]-3213

-8←

Zj

Cj-Zj-1-21-1100-2-1-2-10-3

-1x10x317/205/2-2-1/203/213/2-1-1/274

Zj

Cj-Zj-1-7/20-5/221/20-1/20-1/2-2-1/2-7

Cj

－1－40－300

x1x2

x3

x4

s5s6

b

1

23

2/31/22/3對偶單純形法的步驟可以歸納如下：(1)

將原問題化成標準形式：

建立初始對偶單純形表,若b列全為非負，判別數(shù)行Cj-Zj≤0,則已得最優(yōu)解，計算停止；若b列中至少有一個負分量，且判別數(shù)Cj-Zj≤0，則進行下一步；(2)

以對應的基變量作為換出變量;（3）檢查所在行的系數(shù)若所有的則無可行解，計算停止。若存在則計算確定為換入變量；（4）以為主元素，進行迭代運算，得新表。重復步驟（1）—（4）對偶單純形法的步驟可以歸納如下：1．確定換出變量：選擇最負的基本變量為換出變量。

2．確定換入變量：用換出變量那一行具有負值的系數(shù)分別去除同列的檢驗數(shù)，取最小商數(shù)所對應的變量為換入變量；如果換出變量那一行無負值的系數(shù)，則原問題無可行解。

3．初等行運算，使樞元位置變?yōu)?,其他樞列位置變?yōu)?。

4．最優(yōu)解檢查。如果所得的基本解都是非負的，則此解即為最優(yōu)解。如果基本解中還有負的數(shù)值，則重復第一步繼續(xù)迭代，直到所有基本變量為非負的數(shù)值為止。對偶單純形法迭代的要點1．初始解可以是非可行解，當檢驗數(shù)都是小于等于零時，就可以進行基變換，這樣就避免了增加人工變量，使運算簡化。

2．對變量較少，而約束條件很多的線性規(guī)化問題，可先將其變?yōu)閷ε紗栴}，再用對偶單純形法求解，簡化計算。

3．用于靈敏度分析。對偶單純形法的優(yōu)點及用途

①

單純形表檢驗數(shù)行全部非正（對偶可行）

②

變量取值可有負數(shù)（非可行解）

對偶單純形法在什么情況下使用：注：通過矩陣行變換運算，使所有相應變量取值均為非負數(shù)即得到最優(yōu)單純形表。應用前提：有一個基，其對應的基滿足:

適合于解如下形式的線性規(guī)劃問題對偶單純形法的適用范圍

在引入松弛變量化為標準型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進行求解，非常方便。對于有些線性規(guī)劃模型，如果在開始求解時不能很快使所有檢驗數(shù)非正，最好還是采用單純形法求解。因為，這樣可以免去為使檢驗數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除此之外，在對線性規(guī)劃進行靈敏度分析中有時也要用到對偶單純形方法，可以簡化計算。#返回它主要考慮兩種情況：一是這些系數(shù)在什么范圍內(nèi)變化時，已得到的最優(yōu)解保持不變，或者最優(yōu)解的基本變量保持不變（但數(shù)值有所改變）；二是如果某些系數(shù)的變化引起最優(yōu)解的變化，如何用最簡便的方法求出新的最優(yōu)解。五、靈敏度分析系數(shù)變化的靈敏度分析

基矩陣B——原始系數(shù)矩陣中對應于基本變量的列所組成的矩陣。

基矩陣的逆陣B-1——在任一單純形表中相應于初始基本變量的那些列給出了相應于該表格的基矩陣的逆陣B-1。在單純形表每次迭代后,每個變量的系數(shù)列向量是B的逆陣B-1乘以該變量的原始列向量而得到的，右端常數(shù)的列向量是B的逆陣B-1乘以右端常數(shù)的原始列向量而得到的。P

=B-1Pb

=B-1b

檢驗數(shù)是Cj-Zj=Cj-CBB-1P

（一）價值系數(shù)c發(fā)生變化：

m

考慮檢驗數(shù)

j=cj-∑cri

arij（

j=1,2,…,n）

i=1

1.若ck是非基變量的系數(shù)：

設(shè)ck變化為

ck+

ck

k’=ck+

ck-∑cri

arik=

k+

ck對于極大化問題，只要

k’≤0,即

ck≤-

k，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

k

用

k’取代，繼續(xù)單純形法的表格計算。

MinY’=-2x1-3x2-x3+0x4+0x5

1/3x1+1/3x2+1/3x3+x4=1

1/3

x1+4/3x2+7/3x3+x5=3

x1,x2,x3,x4,x5≥0例8

MaxY=2x1+3x2+x3

1/3x1+1/3x2+1/3x3≤

1

1/3

x1+4/3x2+7/3x3≤3

x1,x2,x3≥0

最優(yōu)單純形表從表中看到σ3=c3+Δc3-(c1×a13+c2×a23)

可得到Δc3

≥

－3

時，原最優(yōu)解不變。當3+Δc3

≥0最優(yōu)解不變

2．若cs

是基變量的系數(shù)：

設(shè)cs

變化為cs+

cs，那么

j’=cj-∑cri

arij-(

cs+

cs)asj=

j-

csas，

i≠s

觀察所有非基變量：對于極小化問題，只要對所有非基變量

j’≥0，即

j’≥

csasj，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

j

用

j’取代，繼續(xù)單純形法的表格計算。

Max{

j/asj

asj>0}≤

cs≤Min{

j/asj

asj<0}下表為最優(yōu)單純形表（考慮基變量系數(shù)c1發(fā)生變化）3+Δc1

≥05-4Δc1≥01+Δc1≥0最優(yōu)解不變可得到-1≤ΔC2≤5/4時，原最優(yōu)解不變。最優(yōu)值將會出現(xiàn)相應的變化。MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5

≥

0例9下表為最優(yōu)單純形表（考慮基變量系數(shù)c2發(fā)生變化）從表中看到σj=cj-(c1×a1j+c5×

a5j+(c2+Δc2)×a2j)

j=3,4可得到-3≤Δc2≤1時，原最優(yōu)解不變。

3.若基變量的系數(shù)和非基變量的系數(shù)都變化：

只要計算非基變量的檢驗數(shù)即可。

設(shè)分量br變化為br+

br，根據(jù)前面的討論，最優(yōu)解的基變量xB=B-1b，那么只要保持B-1(b+

b)≥0，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。對于問題

Max

Z=cT

x

Ax≤b

x≥0（二）右端項b

發(fā)生變化最優(yōu)單純形表中含有B-1=(aij

）i=1,…,m;j=n+1,…,n+m

那么，新的xi=(B-1b)I+

brairi=1,…,m

由此可得，最優(yōu)基不變的條件是Max{-bi

/air

air>0

}≤

br≤Min{-bi

/air

air<0}

例9的最優(yōu)單純形表如下例9MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3

=84x1+

x4

=164x2+x5=

12

x1,x2,x3,x4,x5

≥

0若Δb3=-8，則4+（-8）=-4<0，改變了最優(yōu)性，只要再繼續(xù)迭代即可。見下表比如第三個式子中，由4+Δb3≥0，解得Δb3≥-4

時最優(yōu)性不變。#小結(jié)1.對偶單純形法迭代的要點2.對偶單純形法的優(yōu)點及用途3.對偶單純形法的適用范圍五、靈敏度分析（一）價值系數(shù)c