管理運(yùn)籌學(xué)：管理科學(xué)方法(第4版)全書電子教案整套教學(xué)課件

線性規(guī)劃的數(shù)學(xué)模型

2.物資運(yùn)輸問題3個(gè)供貨源A1,A2,A34個(gè)需求市場B1,B2,B3,B4產(chǎn)量、銷量、單位運(yùn)費(fèi)如表統(tǒng)一籌劃運(yùn)銷的最小運(yùn)費(fèi)方案

銷地貨源地R1R2R3產(chǎn)量A134515A22235銷量5105（1）決策變量：設(shè)從Wi到Rj的運(yùn)輸量為xij，（2）最小運(yùn)費(fèi)：minZ=3x11+4x12+5x13+2x21+2x22+3x23（3）產(chǎn)銷平衡：供應(yīng)平衡x11+x12+x13=15x21+x22+x23=5銷售平衡x11+x21=5x12+x22=10x13+x23=5非負(fù)性約束

xij≥0(i=1,2；j=1,2,3)

第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

模型隱含假定（1）線性化假定

函數(shù)關(guān)系式f(x)=c1x1+c2x2+…+cnxn，稱線性函數(shù)。

建模技巧：將非線性的函數(shù)進(jìn)行分段線性化。（2）同比例假定決策變量變化引起目標(biāo)函數(shù)和約束方程的改變量比例。（3）可加性假定

決策變量對目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的。目標(biāo)函數(shù)值是決策變量對目標(biāo)函數(shù)貢獻(xiàn)的總和。

（4）連續(xù)性假定

決策變量取值連續(xù)。（5）確定性假定

所有參數(shù)都是確定的，不包含隨機(jī)因素。第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

三、線性規(guī)劃的圖解方法

1.線性規(guī)劃的可行域可行域：滿足所有約束條件的解的集合，即所有約束條件共同圍城的區(qū)域。maxZ=3x1+5x2

2x1≤162x2≤10

3x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

2x1=162x2=10x1x248103583x1+4x2

=320ABCD三、線性規(guī)劃的圖解方法

2.線性規(guī)劃的最優(yōu)解目標(biāo)函數(shù)

Z=3x1+5x2

代表以

Z為參數(shù)的一族平行線。Z=30Z=37Z=15第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

四、線性規(guī)劃解的可能性1.唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)2.多重最優(yōu)解：無窮多個(gè)最優(yōu)解當(dāng)市場價(jià)格下降到74元，其數(shù)學(xué)模型變?yōu)?/p>

2x1=162x2=103x1+4x2

=32x1x248102580ABCDZ=24Z=32Z=12第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

四、線性規(guī)劃解的可能性3.無界解：可行域無界，目標(biāo)值無限增大

(缺乏必要約束)原因在于：建模時(shí)遺漏了主要條件

（生產(chǎn)資源、市場需要、技術(shù)標(biāo)準(zhǔn)…）第一節(jié)

線性規(guī)劃的數(shù)學(xué)模型

四、線性規(guī)劃解的可能性4.沒有可行解：線性規(guī)劃問題的可行域是空集

(約束條件相互矛盾)技術(shù)沖突利害沖突強(qiáng)沖突弱沖突原因：舍去其一，保留另一個(gè)：限制其一，另一個(gè)最優(yōu)：經(jīng)濟(jì)補(bǔ)償?shù)诙?jié)

線性規(guī)劃的單純形法

一、線性規(guī)劃的標(biāo)準(zhǔn)型式

1、標(biāo)準(zhǔn)型表達(dá)方式(1)代數(shù)式

(2)向量式

(3)矩陣式

A：技術(shù)系數(shù)矩陣，簡稱系數(shù)矩陣；B：可用的資源量，稱資源向量；C：決策變量對目標(biāo)的貢獻(xiàn)，稱價(jià)值向量；X：決策向量。第二節(jié)

線性規(guī)劃的單純形法

1.代數(shù)解法

2x1+x3

=162x2+x4

=10

3x1+4x2+x5=32-Z+3x1

+5x2+0x3

+0x4+0x5=0x1x2x3x4x5x3x4x5非奇異子陣作為一個(gè)基基變量x3,x4,x5非基變量x1,x2第二節(jié)

線性規(guī)劃的單純形法

（1）求初始基可行解

將基變量用非基變量線性表示，即x3=16-2x1

x4

=10-2x2

x5=32-3x1-4x2

令非基變量x1=0，x2=0，找到一個(gè)初始基可行解：x1=0，x2

=0，x3=16，x4=10，x5

=32一個(gè)可行解就是一個(gè)生產(chǎn)方案，在上述方案中兩種產(chǎn)品都不生產(chǎn)，利潤Z=0

。第二節(jié)

線性規(guī)劃的單純形法

（2）第一次迭代

確定進(jìn)基變量

2x1+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0

從目標(biāo)函數(shù)-Z+3x1+5x2+0x3+0x4+0x5=0可知：非基變量x1，x2的系數(shù)為正數(shù)，生產(chǎn)哪種產(chǎn)品都會(huì)增加利潤。因?yàn)閤2的系數(shù)大于x1的系數(shù)，即生產(chǎn)單位乙產(chǎn)品比甲產(chǎn)品利潤更高一些，故應(yīng)優(yōu)先多生產(chǎn)乙產(chǎn)品。第二節(jié)

線性規(guī)劃的單純形法

確定離基變量基變量用非基變量線性表示x3=16–2x1x4=10－2x2

x5=32-3x1-4x2保持原非基變量x1=0，x2變成基變量時(shí)應(yīng)保證

x3,x4,,x5非負(fù)，即有（2）第一次迭代（續(xù)）

x3=16≥0x4=10-2x2≥0x5=32-4x2≥0x2≤10/2x2≤32/4第二節(jié)

線性規(guī)劃的單純形法

（2）第一次迭代（續(xù)）主行主列主元

2x1+0x2+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0進(jìn)基變量所在列為主列，離基變量所在行為主行第二節(jié)

線性規(guī)劃的單純形法

基變換進(jìn)行初等變換，變主元為1，主列為單位列向量。（2）第一次迭代（續(xù)）

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+5x2+0x3+0x4+0x5=0

2x1+0x2+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0

2x1+x3=16

x2+1/2x4=5

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0第二節(jié)

線性規(guī)劃的單純形法

（2）第一次迭代（續(xù)）將基變量用非基變量線性表示，即x3=16–2x1x2=5-1/2x4

x5=12-3x1+4x4令非基變量x1=0，x4=0，找到另一個(gè)基可行解x1=0，x2=5，x3=16，x4=0，x5=12目標(biāo)函數(shù)Z=25第二節(jié)

線性規(guī)劃的單純形法

確定進(jìn)基變量（3）第二次迭代

第一次迭代結(jié)果

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25目標(biāo)函數(shù)-Z+3x1+0x2+0x3–5/2x4+0x5=-25，非基變量x1的系數(shù)σ1=3（檢驗(yàn)數(shù)）為正數(shù)，確定x1為進(jìn)基變量。第二節(jié)

線性規(guī)劃的單純形法

確定離基變量（3）第二次迭代

（續(xù)）x3=16-2x1≥0x2=5≥0

x5=12-3x1≥0x1≤16/2x1≤12/3基變量用非基變量線性表示

x3=16–2x1x2=5-1/2x4

x5=12-3x1+4x4保持原非基變量x4=0，x1變成基變量時(shí)應(yīng)保證

x2,x3,,x5非負(fù)，即

第二節(jié)

線性規(guī)劃的單純形法

基變換變主元為1，主列為單位列向量。（3）第二次迭代（續(xù)）

x3+4/3x4-2/3x5=8

x2+1/2x4=5x1-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

x3+4/3x4-2/3x5=8

x2+1/2x4=6x1+-2/3x4+1/3x5=4

-Z+0x1+0x2+0x3-1/2x4-x5=-37

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

2x1+x3=16

x2+1/2x4=5

x1+-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-25第二節(jié)

線性規(guī)劃的單純形法

（3）第二次迭代（續(xù)）將基變量用非基變量線性表示，即x3=8–4/3x4+2/3x5x2=5-1/4x4

x1=4+2/3x4-1/3x5

令非基變量x4=0，x5=0，又找到一個(gè)基可行解

目標(biāo)函數(shù)

-Z+0x1+0x2+0x3-1/2x4-x5=-37

x1=4，x2=5，x3=8，x4=0，x5=0Z=37檢驗(yàn)數(shù)σj非正，得最優(yōu)解X*=(4,5,8,0,0)T，Z*=37第二節(jié)

線性規(guī)劃的單純形法

對代數(shù)法步驟進(jìn)行具體化、表格化2.單純形法表CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1nθ1CB2xB2b2a21a22…a2j…a2nθ2………………………CBnxBnbmam1am2…amj…amnθm檢驗(yàn)數(shù)σj-Zσ1σ2…σj…σn第二節(jié)

線性規(guī)劃的單純形法

單純形法的計(jì)算步驟

①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)σj=Cj-CBPj′，若所有σj≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)σk所對應(yīng)的系數(shù)列向量Pk′≤0，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步。⑤根據(jù)max{σj｜σj＞0}=σk原則，確定xk為換入變量(進(jìn)基變量)，再按θ規(guī)則計(jì)算：θ=min{bi′/aik′|aik′＞0}=bl′/aik′

確定xBl為換出變量。建立新的單純形表，此時(shí)基變量中xk取代了xBl的位置。⑥以aik′為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik′變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。

第二節(jié)

線性規(guī)劃的單純形法

舉例-Z+3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32

Cj比值CBXBb檢驗(yàn)數(shù)σjx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8第二節(jié)

線性規(guī)劃的單純形法

162010050101/2012300-21x3x2x5050300-5/208-4Cj比值CBXBb檢驗(yàn)數(shù)σjx1x2x3x4x535000檢驗(yàn)數(shù)σj80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最優(yōu)解:X*=(4,5,8,0,0)T，Z*=37第二節(jié)

線性規(guī)劃的單純形法

3.單純形法的矩陣計(jì)算

數(shù)學(xué)模型

maxZ=CX

AX=b

X≥0A中線形無關(guān)的子矩陣B為基矩陣

，即A→(B,N)與基矩陣對應(yīng)的變量XB，其余變量為非基變量XN變形XB用XN線形表示左乘B-1代入整理令XN=0檢驗(yàn)數(shù)第二節(jié)

線性規(guī)劃的單純形法

4、單純形法的管理啟示

2x1=162x2=103x1+4x2

=32x1x24812590ABC(4,5)DX0=(0,0,16,10,32)TX1=(0,5,16,0,12)TX2=(4,5,8,0,0)T企業(yè)管理過程也是如此：

把現(xiàn)有方案作為初始方案，找到最急需要改進(jìn)的某個(gè)問題和改進(jìn)方向，一次做好某個(gè)主要問題的解決與改進(jìn)；一次只解決和改進(jìn)一個(gè)問題的難度最??；解決之后，再尋求可以改進(jìn)的其它地方，再次改進(jìn)，不斷地追求完美。第二節(jié)

線性規(guī)劃的單純形法

用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝”型的約束，沒有現(xiàn)成的單位矩陣。人工變量的構(gòu)造

采用人造基的辦法：人工構(gòu)造單位矩陣在沒有單位列向量的等式約束中加入人工變量，構(gòu)成原線性規(guī)劃問題的伴隨問題，從而得到一個(gè)初始基。人工變量是在等式中人為加進(jìn)的，只有它等于0時(shí)，約束條件才是它本來的意義。處理方法有兩種：大M法兩階段法第二節(jié)

線性規(guī)劃的單純形法

沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量

。人工變量最終必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為-M。M為無限大的正數(shù)，這是一個(gè)懲罰項(xiàng)，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒有置換出去，那么這個(gè)問題就沒有可行解，當(dāng)然亦無最優(yōu)解。

大M法例如

S.t.3x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0maxZ=

3x1-x2-2x3第二節(jié)

線性規(guī)劃的單純形法

按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問題如下：

maxZ=3x1-x2-2x3-Mx4-Mx5

3x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值CBXBb檢驗(yàn)數(shù)σjx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00x4x5-M-M24第二節(jié)

線性規(guī)劃的單純形法

Cj比值CBXBb檢驗(yàn)數(shù)σjx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24檢驗(yàn)數(shù)σj212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1檢驗(yàn)數(shù)σj31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2第二節(jié)

線性規(guī)劃的單純形法

沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量

。人工變量最終必須等于0才能保持原問題性質(zhì)不變。利用兩階段法求解該問題。第一階段：單獨(dú)求解人工變量最小化的目標(biāo)函數(shù)；第二階段：將第一階段結(jié)果帶入第二階段，求解原目標(biāo)函數(shù)。兩階段法例如

S.t.x1-x2+6x3-x4=2x1+x2+2x3–x5=1xi≥0,i=1,2,3,4,5minZ=

5x1+21x2第二節(jié)

線性規(guī)劃的單純形法

首先，引入人工變量x6,x7構(gòu)建模型：

minZ’=

x6+x7x1-x2+6x3-x4+x6=2x1+x2+2x3–x5+x7=1xi≥0,i=1,2,3,4,5,6,7Cj比值CBXBbσjx6x7-1-11/31/2

s.t.x1x2x3x4x5x6x700000-1-1211-1[6]-10101120-101208-1-100第二節(jié)

線性規(guī)劃的單純形法

Cj比值CBXBbσjx3x200x1x2x3x4x5x6x700000-1-13/81/41/401-1/8-1/81/81/81/2101/4-3/4-1/43/400000-1-1Cj比值CBXBbσjx3x2-2103/21/2x1x2x3x4x5-50-21003/81/41/401-1/8-1/8[1/2]101/4-3/41/400-21/8-21/8第二階段，刪除人工變量x6,x7，將結(jié)果帶入原目標(biāo)函數(shù)第二節(jié)

線性規(guī)劃的單純形法

Cj比值CBXBbσjx3x2-2103/21/2x1x2x3x4x5-50-21003/81/41/401-1/8-1/8[1/2]101/4-3/41/400-21/8-21/8Cj比值CBXBbσjx3x1-210x1x2x3x4x5-50-21001/41/20-1/210-1/41201/2-3/20-1/20-11/4-9/4得到最優(yōu)解:(1/2,0,1/4,0,0)T第二節(jié)

線性規(guī)劃的單純形法

單純形法補(bǔ)遺進(jìn)基變量相持：單純形法運(yùn)算過程中，同時(shí)出現(xiàn)多個(gè)相同的σj最大。在符合要求的σj(目標(biāo)為max：σj＞0，min：σj＜0)中，選取下標(biāo)最小的非基變量為換入變量；離基變量相持：單純形法運(yùn)算過程中，同時(shí)出現(xiàn)多個(gè)相同的最小θ值。繼續(xù)迭代，便有基變量為0，稱這種情況為退化解。選取其中下標(biāo)最大的基變量做為換出變量。多重最優(yōu)解：最優(yōu)單純形表中，存在非基變量的檢驗(yàn)數(shù)σj=0。讓這個(gè)非基變量進(jìn)基，繼續(xù)迭代，得另一個(gè)最優(yōu)解。無界解：大于0的檢驗(yàn)數(shù)中，若某個(gè)σk所對應(yīng)的系數(shù)列向量Pk′≤0，則解無界。無可行解：最終表中存在人工變量是基變量。第二節(jié)

線性規(guī)劃的單純形法

例如S.t.標(biāo)準(zhǔn)化

maxZ=

3x1+2x2-2x1+x2+x3=2x1-3x2+x4=3x1,x2,x3,x4≥0Cj比值CBXBb檢驗(yàn)數(shù)σjx1x2x3x432002-211031-301x3x40003200-3檢驗(yàn)數(shù)σj80-512x3x103--31-301-90110-3此時(shí)，檢驗(yàn)數(shù)σ2=11＞0，還沒有得到最優(yōu)解。確定x2進(jìn)基，但x2所在列的系數(shù)向量元素非正，無界θ值不存在，有進(jìn)基變量但無離基變量。maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1,x2≥0第三節(jié)

線性規(guī)劃的建模技巧

計(jì)件工資maxZ=66x1+89x2+70x3

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0崗位工資

總收入=173x1+233x2+170x3

原料費(fèi)=65x1+95x2+65x3，營運(yùn)費(fèi)=11000maxZ=108x1+138x2+105x3-11000

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0計(jì)時(shí)工資：maxZ=108x1+138x2+105x3-11000

0x1+30x2+15x3≤2400

10x1+20x2+0x3≤240031x1+21x2+21x3≤4800

31x1+13x2+24x3≤4800

x1

≤40x2

≤80x3≤40x1,x2,x3≥0目標(biāo)函數(shù)的靈活性MMCCGGWB資源G15C12M20B14B28M7C10C9G4$30ABCDEFG5$35$65$30C6M18W9裝配B6W8裝配G15C15C18M20原料第三節(jié)

線性規(guī)劃的建模技巧

計(jì)劃鏈的層次

粗能力計(jì)劃定單可行不可行CRP主生產(chǎn)計(jì)劃MPS物料需求計(jì)劃MRP能力需求計(jì)劃車間作業(yè)計(jì)劃產(chǎn)品分銷計(jì)劃可行否作業(yè)統(tǒng)計(jì)與控制物料清單庫存管理采購計(jì)劃供應(yīng)商生產(chǎn)計(jì)劃大綱預(yù)測當(dāng)前條件企業(yè)經(jīng)營計(jì)劃

產(chǎn)值計(jì)劃

或

利潤計(jì)劃

絕對數(shù)量

或

增長幅度

期限:年度

單位:萬元

產(chǎn)品銷售收入或臺(tái)套

確定產(chǎn)品品種和數(shù)量

期限:年度

單位:萬臺(tái)

具體產(chǎn)品具體

時(shí)段出產(chǎn)計(jì)劃

合同單,預(yù)測轉(zhuǎn)換為生產(chǎn)任務(wù)

將產(chǎn)品出產(chǎn)計(jì)劃轉(zhuǎn)換成物料需求表

大類產(chǎn)品年度生產(chǎn)計(jì)劃

品種和數(shù)量的最優(yōu)組合

期限:年度

單位:萬臺(tái)獨(dú)立需求：需求量

和時(shí)間與其它物料

沒直接關(guān)系來自企業(yè)外部市場,

數(shù)量和時(shí)間取決于

企業(yè)外部需求訂單和預(yù)測確定相關(guān)需求：需求量

和時(shí)間則取決于

另一物料制造過程的材料、

毛坯、零件需求BOM,產(chǎn)量和交期

計(jì)算—MRP線性規(guī)劃的適用層次第四節(jié)

線性規(guī)劃的應(yīng)用案例-配送中心選擇

供貨源S1(產(chǎn)地)的供貨能力5萬臺(tái)/月新增供貨源S2可以滿足市場需求且兩個(gè)貨源的價(jià)格相同目標(biāo)市場(銷地)的需求量5,10,5萬臺(tái)/月分銷渠道中擬定在2個(gè)地點(diǎn)中選址設(shè)立分銷中心轉(zhuǎn)運(yùn)產(chǎn)品決策變量：設(shè)從供貨源到分銷中心的運(yùn)輸量yij從分銷中心到需求市場的運(yùn)輸量xjk選址規(guī)劃在于二者的實(shí)際取值：若y11+y21=0,則不設(shè)分銷中心W1；反之設(shè)置W1規(guī)模y11+y21若y12+y21=0,則不設(shè)分銷中心W2；反之設(shè)置W2規(guī)模y12+y21目標(biāo)函數(shù)：各路段上的實(shí)際運(yùn)量×單位物流運(yùn)費(fèi)之和最小，即第四節(jié)

線性規(guī)劃的應(yīng)用案例-配送中心選擇

供應(yīng)能力平衡約束市場需求平衡約束配送中心不存留產(chǎn)品所有變量大于等于零第四節(jié)

線性規(guī)劃的應(yīng)用案例-庫存控制

某帆船公司需確定年內(nèi)四個(gè)季度的生產(chǎn)計(jì)劃安排，根據(jù)歷史數(shù)據(jù)做出市場預(yù)測：一季度市場需求為30艘,二季度60艘,三季度75艘,四季度25艘。需求必須被滿足季度期初生產(chǎn)：每季度最大產(chǎn)能是40艘,所需成本為400元/艘。若加班生產(chǎn),則加班生產(chǎn)的數(shù)量不能超過20艘,加班生產(chǎn)的單位成本是450元/艘。如果沒有銷售出去,每艘帆船每季度的庫存持有成本是20元。年度生產(chǎn)計(jì)劃該如何安排才能實(shí)現(xiàn)生產(chǎn)成本和庫存成本的最小化？

(1)決策變量:每個(gè)季度,必須確定正常生產(chǎn)和加班生產(chǎn)的帆船數(shù)量,因此定義如下決策變量：xi=第i季度正常生產(chǎn)帆船的數(shù)量(i=1,2,3,4)yi=第i季度加班生產(chǎn)帆船的數(shù)量(i=1,2,3,4)si=第i季度末的帆船庫存量(i=1,2,3,4）(2)目標(biāo)函數(shù):優(yōu)化目標(biāo)是追求總成本最小化,因此目標(biāo)函數(shù)是：

(3)約束條件:庫存守恒：第(i-1)季度末的庫存量+第i季度的生產(chǎn)量=第i季度的需求量+第i季度末的庫存量庫存平衡約束：si-1+(xi+yi)=di+si(i=1,2,3,4)生產(chǎn)能力約束：xi<=40,yi<=20(i=1,2,3,4)非負(fù)約束：xi≥0,yi≥0,si≥0(i=1,2,3,4)

最優(yōu)解：Z=78850,x1=x2=x3=40,x4=25,y1=5,y2=y3=20,y4=0

s1=s2=15,s3=s4=0第四節(jié)

線性規(guī)劃的應(yīng)用案例-合理下料

某建筑公司要用鋁型材作為構(gòu)架，制作100個(gè)鋁合金窗子，每個(gè)窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根，原材料每根6米。怎樣下料才能使余料最少?

(1)決策變量:無法直接定義，應(yīng)列選可行方案。如方案1為：2.8米1根，1.8米1根，1.17米1根，0.6米0根，合計(jì)5.77米，余料0.23(2)目標(biāo)函數(shù)和約束條件:

第四節(jié)

線性規(guī)劃的應(yīng)用案例-營養(yǎng)配餐

假定一個(gè)成年人每天需要從食物中攝取3000千卡的熱量、55克的蛋白質(zhì)和800毫克的鈣。如果市場上只有4種食品可供選擇(當(dāng)然可以擴(kuò)充到n種食品),它們每千克所含的熱量、營養(yǎng)成分和市場價(jià)格見表1-13。如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小?

(1)決策變量:設(shè)變量為每種食品每天的購入量。(2)目標(biāo)函數(shù)和約束條件:

第四節(jié)

線性規(guī)劃的應(yīng)用案例-產(chǎn)品混合

新時(shí)代制藥公司利用4種化學(xué)原料A，B，C，D來生產(chǎn)一種新藥，新藥的產(chǎn)量必須達(dá)到每天1000公斤以上。新藥中含有3種有效成分甲、乙、丙，它們的含量分別不低于8%，4%，2%。每公斤原料的價(jià)格和所含有效成分的比例如表1-14所示。如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小?

(1)決策變量:設(shè)變量為每種化學(xué)原料的投入量。(2)目標(biāo)函數(shù)和約束條件:

構(gòu)建線性規(guī)劃問題的對偶規(guī)劃模型理解對偶規(guī)劃模型的解和基本性質(zhì)掌握影子價(jià)格的含義及其實(shí)際應(yīng)用了解參數(shù)變動(dòng)分析原理和經(jīng)濟(jì)意義能分析價(jià)值系數(shù)和資源數(shù)量的變動(dòng)掌握資源總存量和分配量增減決策第2章對偶規(guī)劃引入案例

根據(jù)第一章中的引入案例，該汽車制造廠的主營業(yè)務(wù)為機(jī)動(dòng)汽車的生產(chǎn)加工制造，并且為了擴(kuò)大市場占有率而實(shí)行資產(chǎn)經(jīng)營。隨著該廠業(yè)務(wù)量的提升，為了滿足更高的需求，該制造廠希望能擴(kuò)展業(yè)務(wù)范圍、增加業(yè)務(wù)種類，不僅局限于生產(chǎn)制造環(huán)節(jié)，而是通過產(chǎn)業(yè)升級獲得更多的利潤。因此,汽車制造環(huán)節(jié)的設(shè)備產(chǎn)生冗余，為了避免設(shè)備閑置帶來的損失，該廠計(jì)劃將制造設(shè)備和技術(shù)人員等資源出租，從而獲取一定的利潤。如果你是該部門主管，會(huì)怎樣制定出租計(jì)劃、選擇出租單位?生產(chǎn)不同型號汽車的設(shè)備中哪些屬于緊缺設(shè)備,哪些存在冗余呢?而當(dāng)進(jìn)口生產(chǎn)成本、工人費(fèi)用等條件發(fā)生變化時(shí),應(yīng)該如何調(diào)整生產(chǎn)計(jì)劃來應(yīng)對復(fù)雜的變化?（從企業(yè)管理或者運(yùn)籌學(xué)角度想一想）第一節(jié)

對偶規(guī)劃的數(shù)學(xué)模型一、對偶問題的提出產(chǎn)品平銷是否做代工：設(shè)備臺(tái)時(shí)的最低價(jià)碼？談判時(shí)衡量對方出價(jià)面臨著兩種選擇：自行生產(chǎn)或代加工①合理安排生產(chǎn)的利潤?②利潤不降低的資源轉(zhuǎn)讓最低價(jià)？資源出讓模型(對偶問題)A,B,C工時(shí)出讓利潤y1,y2,y3minw=16y1+10y2+32y3

2y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1,y2,y3≥0

最優(yōu)解

y1=0,y2=1/2,y3=1,w*=37生產(chǎn)計(jì)劃模型(原問題)

假設(shè)甲乙產(chǎn)量x1,x2

maxZ=

3x1+5x2

2x1≤162x2≤103x1+4x2≤32x1

,x2

≥0最優(yōu)解

x1=4,x2=5,Z*=37第一節(jié)

對偶規(guī)劃的數(shù)學(xué)模型二、對偶規(guī)劃的性質(zhì)1.對稱性定理

對偶問題的對偶問題是原問題。

根據(jù)對偶規(guī)劃，很容易寫出對偶問題的對偶問題模型。2.最優(yōu)性定理

設(shè)

，

分別為原問題和對偶問題的可行解，且

則

，

分別為各自的最優(yōu)解。3.對偶性定理

若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且

兩者的目標(biāo)函數(shù)值相等。4.互補(bǔ)松弛性

最優(yōu)解的充分必要條件

，第二節(jié)

對偶規(guī)劃的經(jīng)濟(jì)解釋

影子價(jià)值的內(nèi)涵左邊是資源bi每增加一個(gè)單位對目標(biāo)函數(shù)Z的貢獻(xiàn)；yi在經(jīng)濟(jì)上表示原問題第i種資源的邊際價(jià)值。第二節(jié)

對偶規(guī)劃的經(jīng)濟(jì)解釋影子價(jià)格不是資源的實(shí)際價(jià)格，反映資源配置結(jié)構(gòu)其它數(shù)據(jù)固定，某資源增加一單位導(dǎo)致目標(biāo)函數(shù)的增量若原問題價(jià)值系數(shù)Cj表示單位產(chǎn)值，則yi稱影子價(jià)格若原問題價(jià)值系數(shù)Cj表示單位利潤，則yi稱影子利潤影子價(jià)格=資源成本+影子利潤對資源i總存量的評估：購進(jìn)

or出讓對資源i分配量的評估：增加

or減少影子利潤說明增加哪種資源對經(jīng)濟(jì)效益最有利影子價(jià)格告知以怎樣的代價(jià)去取得緊缺資源影子價(jià)格是機(jī)會(huì)成本，提示資源出租/轉(zhuǎn)讓的基價(jià)利用影子價(jià)格分析新品的資源效果：定價(jià)決策利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)的資源緊性可以幫助分析工藝改變后對資源節(jié)約的收益可以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺第三節(jié)

資源的參數(shù)變動(dòng)分析參數(shù)變動(dòng)分析的必要性環(huán)境和條件處在不斷的變化中模型參數(shù)的值是通過估計(jì)或預(yù)測得到的,帶有一定的不確定性價(jià)值系數(shù)的變動(dòng)分析非基變量xj的價(jià)值系數(shù)cj變動(dòng)

只要σj'=cj+Δcj-CBB-1Pj≤0，最優(yōu)基不變基變量xBi的價(jià)值系數(shù)cBi的改變

基變量的檢驗(yàn)數(shù)σB=CB+ΔCB-(CB+ΔCB)B-1B=0,不受變動(dòng)影響;非基變量的檢驗(yàn)數(shù)變?yōu)?σj’=cj-(CB+ΔCB)B-1Pj=cj-CBB-1Pj-ΔCBB-1Pj=σj-ΔCBB-1Pj資源限量的變動(dòng)分析考察b的變化分析

不影響檢驗(yàn)數(shù),只影響XB=B-1b考察b的變化范圍

br的增量為Δbr,其他數(shù)據(jù)不變。新的基解為:XB’=B-1(b+Δb)只要XB'≥0,則可保持最優(yōu)基不變。第四節(jié)

對偶規(guī)劃的應(yīng)用案例案例：甲乙生產(chǎn)工藝如圖，試確定獲利最大的生產(chǎn)計(jì)劃?材料A材料AD

10材料BD15裝配裝配D

20C8甲D15D25C12C28乙產(chǎn)品資源資源消耗資源成本擁有量甲乙元/單位材料A(Kg)40202002500材料B(Kg)30401003000設(shè)備C(h)4020102000設(shè)備D(h)6050204500預(yù)測售價(jià)(元)1460011600設(shè)甲的計(jì)劃產(chǎn)量x1，乙的計(jì)劃產(chǎn)量x2，試建立線性規(guī)劃模型用LINDO軟件求最優(yōu)組合方案，識別緊缺資源和非緊缺資源寫出對偶問題模型及其最優(yōu)解，并進(jìn)行經(jīng)濟(jì)解釋若材料B的現(xiàn)有市場價(jià)格為150元/Kg裝配設(shè)備C可外協(xié)加工，外協(xié)加工價(jià)20元/時(shí)請問是否購進(jìn)或外協(xié)加工，企業(yè)如何決策？

利用LINDO軟件進(jìn)行參數(shù)變動(dòng)性分析計(jì)劃執(zhí)行過程中，若甲的售價(jià)上升到16600元；或乙售價(jià)下降300元，所制定的生產(chǎn)計(jì)劃是否需要進(jìn)行調(diào)整？非緊缺資源最多可減少多少，而緊缺資源最多可增加多少?第四節(jié)

對偶規(guī)劃的應(yīng)用案例資源定價(jià)的決策案例二應(yīng)如何安排甲、乙量產(chǎn)品的產(chǎn)量，使利潤最大？若出讓資源，應(yīng)如何定價(jià)？哪種為緊缺資源，哪種非緊缺？目標(biāo)函數(shù)和約束條件：產(chǎn)品資源資源消耗資源成本擁有量甲乙元/單位原材料(Kg)9420360設(shè)備(hour)4550200電力(Kwh)3101300銷售價(jià)格(Yuan)390352

第四節(jié)

對偶規(guī)劃的應(yīng)用案例資源獲利決策若不生產(chǎn)甲、乙兩種產(chǎn)品，而是出租出售或代工，應(yīng)如何確定三種資源的價(jià)格？決策變量為原材料的單位出讓利潤。構(gòu)建對偶模型。解線性規(guī)劃問題，根據(jù)影子利潤判斷瓶頸資源。

了解整數(shù)規(guī)劃的含義及類型掌握分支定界的原理和步驟能夠正確引入0-1變量建模熟悉整數(shù)規(guī)劃問題應(yīng)用實(shí)例第3章整數(shù)規(guī)劃第一節(jié)

整數(shù)規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問題中只有當(dāng)決策變量取值為整數(shù)才有意義例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱為整數(shù)規(guī)劃(IntegerProgramming)。全部決策變量的取值都為整數(shù)，稱為全整數(shù)規(guī)劃(AllIP)僅要求部分決策變量的取值為整數(shù)，稱混合整數(shù)規(guī)劃(MixedIP)要求決策變量只取0或1值，則稱0-1規(guī)劃(0-1Programming)第一節(jié)

整數(shù)規(guī)劃的數(shù)學(xué)模型一、純整數(shù)規(guī)劃產(chǎn)品資源甲乙現(xiàn)有量A219B5735單臺(tái)利潤65例：某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺(tái)產(chǎn)品的獲利能力如下表所示：

問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。解：設(shè)x1為甲產(chǎn)品的臺(tái)數(shù)，x2為乙產(chǎn)品的臺(tái)數(shù)。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2

≥0x1,x2取整數(shù)第一節(jié)

整數(shù)規(guī)劃的數(shù)學(xué)模型二、0-1規(guī)劃某企業(yè)計(jì)劃在華東、華南、華北、華中、東北、西北、西南七個(gè)區(qū)域新建工廠。假設(shè)每個(gè)區(qū)域最多只能建設(shè)一個(gè)工廠,且該工廠只能覆蓋本區(qū)域的銷售。各區(qū)域的工廠建設(shè)成本見和銷售份額見下表。一期建設(shè)最多可投入的建設(shè)資金為2500萬。問該企業(yè)應(yīng)優(yōu)先建設(shè)哪些地區(qū)的工廠,使得覆蓋的銷售份額最大？序號1234567區(qū)域華東華南華北華中西南西北東北成本（百萬）55261224銷售份額（%）311518148410解：每個(gè)區(qū)域的工廠無非有兩種狀態(tài):建或者不建，不妨設(shè)=1或0，表示建廠或不建。其中，所以,此0—1規(guī)劃的模型為:

第一節(jié)

整數(shù)規(guī)劃的數(shù)學(xué)模型三、混合整數(shù)規(guī)劃例：某產(chǎn)品有n個(gè)區(qū)域市場，各區(qū)域市場的需求量為

bj噸/月；現(xiàn)擬在m個(gè)地點(diǎn)中選址建生產(chǎn)廠，一個(gè)地方最多只能建一家工廠；若選

i地建廠，生產(chǎn)能力為ai噸/月，其運(yùn)營固定費(fèi)用為F元/月；已知址i至j區(qū)域市場的運(yùn)價(jià)為cij元/噸。如何選址和安排調(diào)運(yùn)，可使總費(fèi)用最小？解：選址建廠與否是個(gè)0-1型決策變量，假設(shè)yi=1，選擇第

i

址建廠，

yi=0，不選擇第

i

址建廠；計(jì)劃從

i址至區(qū)域市場

j的運(yùn)輸運(yùn)量xij為實(shí)數(shù)型決策變量。第二節(jié)

整數(shù)規(guī)劃的典型解法一、舍入化整法為了滿足整數(shù)解的要求，自然想到“舍入”或“截尾”處理，以得到與最優(yōu)解相近的整數(shù)解。

這樣做除少數(shù)情況外，一般不可行，因?yàn)榛蟮慕庥锌赡艹隽丝尚杏颍蔀榉强尚薪?；或者雖是可行解，卻不是最優(yōu)解。

不考慮整數(shù)約束則是一個(gè)LP問題,稱為原整數(shù)規(guī)劃的松弛問題對于例1的數(shù)學(xué)模型，不考慮整數(shù)約束的最優(yōu)解：x1

*=28/9，

x2

*=25/9，Z

*=293/9

舍入化整x1=3，

x2=3，Z=33，不滿足約束條件5x1+7x2≤35，非可行解；x1=3，

x2=2，Z=28，滿足約束條件，是可行解，但不是最優(yōu)解；x1=4，

x2=1，Z=29，滿足約束條件，才是最優(yōu)解。第二節(jié)

整數(shù)規(guī)劃的典型解法二、窮舉整數(shù)法對于決策變量少，可行的整數(shù)解又較少時(shí)，這種窮舉法有時(shí)是可行的，并且也是有效的。但對于大型的整數(shù)規(guī)劃問題，可行的整數(shù)解數(shù)量很多，用窮舉法求解是不可能的。例如，指派問題

。5x1+7x2=352x1+x2=9?

(3,3)??????????x1x2123125344第二節(jié)

整數(shù)規(guī)劃的典型解法三、分支定界法不考慮整數(shù)限制，先求出相應(yīng)線性規(guī)劃

的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則是原IP的最優(yōu)解；若不滿足整數(shù)條件，則任選一個(gè)不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。依次在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，直到獲得原整數(shù)規(guī)劃的最優(yōu)解。定界的含義：IP是在相應(yīng)的LP基礎(chǔ)上增加整數(shù)約束IP的最優(yōu)解不會(huì)優(yōu)于相應(yīng)L