衛(wèi)生管理運(yùn)籌學(xué)課件

*第一節(jié)

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

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

線性規(guī)劃

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

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

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

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

注意：?jiǎn)渭冃畏ㄖ?/p>

1.每一步運(yùn)算只能用矩陣初等行變換；

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

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

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

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

1．最終產(chǎn)生最優(yōu)值的單純形表中，某一非基本變量的檢驗(yàn)數(shù)＝0，意味著作任何增大，目標(biāo)函數(shù)的最優(yōu)值不變．此時(shí)線性規(guī)劃問(wèn)題的最優(yōu)解并不唯一，有多重最優(yōu)解．（見(jiàn)下面例題）例用單純形法求解下列規(guī)劃問(wèn)題解:令于是原線性規(guī)劃問(wèn)題變?yōu)闃?biāo)準(zhǔn)形式：?jiǎn)渭冃伪淼?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．當(dāng)樞列（進(jìn)基變量所在列）中的每一項(xiàng)系數(shù)不是0就是負(fù)值時(shí)，說(shuō)明所有約束條件對(duì)進(jìn)基變量的增加都無(wú)約束作用，因此目標(biāo)函數(shù)可以無(wú)限地增加．這種情況我們稱為無(wú)有限最優(yōu)解（或稱有無(wú)界解或無(wú)最優(yōu)解）．但在現(xiàn)實(shí)中，不可能有此情況，往往是模型建立錯(cuò)誤，遺漏了一些約束條件所致．

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

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

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

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

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

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

①在選擇進(jìn)基變量時(shí)，在所有

j>0的非基變量中選取下標(biāo)最小的進(jìn)基；

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

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

P533(4)規(guī)范化規(guī)范化標(biāo)準(zhǔn)化考慮一般問(wèn)題：

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．兩階段法：兩階段法是把一般問(wèn)題的求解過(guò)程分為兩步：第一步：求解原問(wèn)題的一個(gè)基本解：建立一個(gè)輔助問(wèn)題。對(duì)于前面的約束方程組，構(gòu)造一個(gè)標(biāo)函數(shù)為：Minz＝

xn+1＋

xn+2＋

…＋

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

X*

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

x*n+1

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

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

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

是基本解,它對(duì)應(yīng)的基是單位矩陣。

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

i

=1,…,m

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

，xn＋2

，…，xn+m

列；（2）把第一行的目標(biāo)函數(shù)系數(shù)行換為原問(wèn)題目標(biāo)函數(shù)的系數(shù)；（3）檢驗(yàn)數(shù)行直接用前文介紹的方法在表格上計(jì)算得到，即用xj的價(jià)值系數(shù)cj減去cB列的各元素與xj列各對(duì)應(yīng)元素的乘積，把計(jì)算結(jié)果填入xj列的最后一行，得到檢驗(yàn)數(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第一步

求解原問(wèn)題的一個(gè)基本解：

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

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

把基本可行解填入表中

得到原問(wèn)題的最優(yōu)解:(25/3，10/3，0，11)T最優(yōu)目標(biāo)值：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é)存貯問(wèn)題及其基本概念

一、存貯問(wèn)題

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

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

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

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

1．需求

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

2．補(bǔ)充

(a)

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

2．補(bǔ)充

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

3．費(fèi)用在存貯論研究中，常以費(fèi)用標(biāo)準(zhǔn)來(lái)評(píng)價(jià)和優(yōu)選存貯策略。為了正確地評(píng)價(jià)和優(yōu)選存貯策略，不同存貯策略的費(fèi)用計(jì)算必須符合可比性要求。最重要的可比性要求是時(shí)間可比和計(jì)算口徑可比。

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

計(jì)算口徑可比是指存貯策略的費(fèi)用統(tǒng)計(jì)項(xiàng)目必須一致。經(jīng)?？紤]的費(fèi)用項(xiàng)目有存貯費(fèi)、訂貨費(fèi)、生產(chǎn)費(fèi)、缺貨費(fèi)等。在實(shí)際計(jì)算存貯策略的費(fèi)用時(shí)，對(duì)于不同存貯策略都是相同的費(fèi)用可以省略。二、存貯模型中的基本概念

3．費(fèi)用

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

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

3．費(fèi)用

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

(4)缺貨費(fèi)：存貯不能滿足需求而造成的損失。如失去銷售機(jī)會(huì)的損失，停工待料的損失，延期交貨的額外支出，對(duì)需方的損失賠償?shù)取．?dāng)不允許缺貨時(shí)，可將缺貨費(fèi)作無(wú)窮大處理。二、存貯模型中的基本概念

4.存貯策略

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

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

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

4.存貯策略

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

5.存貯模型

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

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

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

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

例2

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

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

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

模型二：允許缺貨，補(bǔ)充時(shí)間較長(zhǎng)從[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]時(shí)間內(nèi)，存貯費(fèi)為：缺貨費(fèi)為：模型二：允許缺貨，補(bǔ)充時(shí)間較長(zhǎng)故[0，t]時(shí)間內(nèi)平均總費(fèi)用為：將(6-6)和(6-7)代入，整理后得：模型二：允許缺貨，補(bǔ)充時(shí)間較長(zhǎng)解方程組容易證明，此時(shí)的費(fèi)用C(t*，t2*)是費(fèi)用函數(shù)C(t，t2)的最小值。模型二：允許缺貨，補(bǔ)充時(shí)間較長(zhǎng)因此，模型二的最優(yōu)存貯策略各參數(shù)值為：最優(yōu)存貯周期

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

(6-10)

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

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

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

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

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

模型三：不允許缺貨，補(bǔ)充時(shí)間較長(zhǎng)

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

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

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

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

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

模型四：允許缺貨，補(bǔ)充時(shí)間極短

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

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

模型四：允許缺貨，補(bǔ)充時(shí)間極短

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

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

(1)計(jì)算。若，則平均總費(fèi)用：(2)計(jì)算(3)若，則C*對(duì)應(yīng)的批量為最小費(fèi)用訂購(gòu)批量Q*。相應(yīng)地，和最小費(fèi)用C*對(duì)應(yīng)的訂購(gòu)周期t*=Q*/R。模型五：價(jià)格與訂貨批量有關(guān)的存貯模型

例6醫(yī)院每周需打印紙45箱，存貯費(fèi)每箱每周5元，每次訂購(gòu)費(fèi)50元，不允許缺貨。打印紙進(jìn)貨時(shí)若(1)訂貨量1箱～9箱時(shí)，每箱120元；(2)訂貨量10箱～49箱時(shí)，每箱100元；(3)訂貨量50箱～99箱時(shí)，每箱95元；(4)訂貨量99箱以上時(shí)，每箱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模型五：價(jià)格與訂貨批量有關(guān)的存貯模型

標(biāo)準(zhǔ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．兩階段法：第一步：求解原問(wèn)題的一個(gè)基本解建立一個(gè)輔助問(wèn)題。構(gòu)造一個(gè)目標(biāo)函數(shù)為：MinZ＝

xn+1＋

xn+2＋

…＋

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

M

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

Mxn+1-…-

Mxn+m

一、對(duì)偶問(wèn)題的提出

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

1.對(duì)稱形式的對(duì)偶問(wèn)題

2.非對(duì)稱形式的對(duì)偶問(wèn)題

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

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

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

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

例1

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

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

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

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

例2

假設(shè)營(yíng)養(yǎng)科不安排生產(chǎn)食品A、B、C、D，而出售單一營(yíng)養(yǎng)成分的糖、蛋白質(zhì)和脂肪。仍用例1中的數(shù)據(jù)，問(wèn)該營(yíng)養(yǎng)科如何確定糖、蛋白質(zhì)和脂肪的單價(jià)，才能在市場(chǎng)竟?fàn)幹辛⒂诓粩≈?，并可獲得利潤(rùn)最多？現(xiàn)在從另一個(gè)角度來(lái)討論該問(wèn)題。

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

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

元。欲使該廠獲利最多，應(yīng)該讓

W=60y1+40y2+35y3達(dá)到最大值。

如要該營(yíng)養(yǎng)科在市場(chǎng)竟?fàn)幹蟹€(wěn)操勝券，以單一營(yíng)養(yǎng)成分食品合成食品A單價(jià)不得超過(guò)1.5元/公斤，即

5y1+3y2+3y3≤1.5例1是例2的對(duì)偶問(wèn)題

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

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

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

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

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

一對(duì)對(duì)稱形式的對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系：Max，≤，變量皆非負(fù)

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

原變量xj對(duì)偶變量y?

產(chǎn)品類別

資源類別

≤b1

≤b2

≤bm

資源價(jià)格

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

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

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

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

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

（2）若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制；

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

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

a11

x1

+…+a1n

xn

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

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

于是y1

沒(méi)有非負(fù)限制，即

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

看作是a11

x1

+…+a1n

xn

=b1

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

非對(duì)稱形式含有等式約束和變量無(wú)符號(hào)限制變量無(wú)符號(hào)限制等式約束2.非對(duì)稱形式的對(duì)偶問(wèn)題

例4

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

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

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

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

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

對(duì)稱形式的對(duì)偶問(wèn)題Max，≤，變量皆非負(fù)

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

對(duì)稱形式的對(duì)偶問(wèn)題Max，≤，變量皆非負(fù)

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

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

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

非對(duì)稱形式含有等式約束和變量無(wú)符號(hào)限制變量無(wú)符號(hào)限制等式約束見(jiàn)下表所示

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

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

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

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

性質(zhì)1

線性規(guī)劃對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。

性質(zhì)2

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

性質(zhì)3

若分別為互為對(duì)偶線性規(guī)劃問(wèn)題的可行解，則當(dāng)時(shí)，是最優(yōu)解。

性質(zhì)4

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

性質(zhì)5

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

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

對(duì)偶單純形法的基本思想

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

利用對(duì)偶單純形法求解解：

將原問(wèn)題化成再化成標(biāo)準(zhǔn)形列表用對(duì)偶單純形法求解：

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對(duì)偶單純形法的步驟可以歸納如下：(1)

將原問(wèn)題化成標(biāo)準(zhǔn)形式：

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

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

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

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

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

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

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

①

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

②

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

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

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

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

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

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

=B-1Pb

=B-1b

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

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

m

考慮檢驗(yàn)數(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對(duì)于極大化問(wèn)題，只要

k’≤0,即

ck≤-

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

k

用

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

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

時(shí)，原最優(yōu)解不變。當(dāng)3+Δc3

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

2．若cs

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

設(shè)cs

變化為cs+

cs，那么

j’=cj-∑cri

arij-(

cs+

cs)asj=

j-

csas，

i≠s

觀察所有非基變量：對(duì)于極小化問(wèn)題，只要對(duì)所有非基變量

j’≥0，即

j’≥

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

j

用

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

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時(shí)，原最優(yōu)解不變。最優(yōu)值將會(huì)出現(xiàn)相應(yīng)的變化。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時(shí)，原最優(yōu)解不變。

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

只要計(jì)算非基變量的檢驗(yàn)數(shù)即可。

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

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

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

Max

Z=cT

x

Ax≤b

x≥0（二）右端項(xiàng)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ù)迭代即可。見(jiàn)下表比如第三個(gè)式子中，由4+Δb3≥0，解得Δb3≥-4

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