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

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

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

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

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

第一節(jié)

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

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

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

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

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

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

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

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

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

三、線性規(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ù)學模型

2x1=162x2=10x1x248103583x1+4x2

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

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

Z=3x1+5x2

代表以

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

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

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

2x1=162x2=103x1+4x2

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

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

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

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

（生產(chǎn)資源、市場需要、技術標準…）第一節(jié)

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

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

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

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

一、線性規(guī)劃的標準型式

1、標準型表達方式(1)代數(shù)式

(2)向量式

(3)矩陣式

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

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

1.代數(shù)解法

2x1+x3

=162x2+x4

=10

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

+5x2+0x3

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

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

（1）求初始基可行解

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

x4

=10-2x2

x5=32-3x1-4x2

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

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

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

。第二節(jié)

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

（2）第一次迭代

確定進基變量

2x1+x3=162x2+x4=10

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

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

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

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

x5=32-3x1-4x2保持原非基變量x1=0，x2變成基變量時應保證

x3,x4,,x5非負，即有（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進基變量所在列為主列，離基變量所在行為主行第二節(jié)

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

基變換進行初等變換，變主元為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，找到另一個基可行解x1=0，x2=5，x3=16，x4=0，x5=12目標函數(shù)Z=25第二節(jié)

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

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

第一次迭代結(jié)果

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25目標函數(shù)-Z+3x1+0x2+0x3–5/2x4+0x5=-25，非基變量x1的系數(shù)σ1=3（檢驗數(shù)）為正數(shù)，確定x1為進基變量。第二節(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變成基變量時應保證

x2,x3,,x5非負，即

第二節(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，又找到一個基可行解

目標函數(shù)

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

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

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

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

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

單純形法的計算步驟

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

確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik′為主元素進行迭代，把xk所對應的列向量變?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檢驗數(shù)σjx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8第二節(jié)

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

162010050101/2012300-21x3x2x5050300-5/208-4Cj比值CBXBb檢驗數(shù)σjx1x2x3x4x535000檢驗數(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.單純形法的矩陣計算

數(shù)學模型

maxZ=CX

AX=b

X≥0A中線形無關的子矩陣B為基矩陣

，即A→(B,N)與基矩陣對應的變量XB，其余變量為非基變量XN變形XB用XN線形表示左乘B-1代入整理令XN=0檢驗數(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)有方案作為初始方案，找到最急需要改進的某個問題和改進方向，一次做好某個主要問題的解決與改進；一次只解決和改進一個問題的難度最??；解決之后，再尋求可以改進的其它地方，再次改進，不斷地追求完美。第二節(jié)

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

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

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

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

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

。人工變量最終必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標函數(shù)中令其系數(shù)為-M。M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標函數(shù)就永遠達不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當然亦無最優(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檢驗數(shù)σjx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00x4x5-M-M24第二節(jié)

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

Cj比值CBXBb檢驗數(shù)σjx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24檢驗數(shù)σj212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1檢驗數(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ì)不變。利用兩階段法求解該問題。第一階段：單獨求解人工變量最小化的目標函數(shù)；第二階段：將第一階段結(jié)果帶入第二階段，求解原目標函數(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é)果帶入原目標函數(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ī)劃的單純形法

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

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

例如S.t.標準化

maxZ=

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

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

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

計件工資maxZ=66x1+89x2+70x3

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0崗位工資

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

原料費=65x1+95x2+65x3，營運費=11000maxZ=108x1+138x2+105x3-11000

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0計時工資：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目標函數(shù)的靈活性MMCCGGWB資源G15C12M20B14B28M7C10C9G4$30ABCDEFG5$35$65$30C6M18W9裝配B6W8裝配G15C15C18M20原料第三節(jié)

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

計劃鏈的層次

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

產(chǎn)值計劃

或

利潤計劃

絕對數(shù)量

或

增長幅度

期限:年度

單位:萬元

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

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

期限:年度

單位:萬臺

具體產(chǎn)品具體

時段出產(chǎn)計劃

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

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

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

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

期限:年度

單位:萬臺獨立需求：需求量

和時間與其它物料

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

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

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

和時間則取決于

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

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

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

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

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

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

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

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

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

(1)決策變量:每個季度,必須確定正常生產(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)目標函數(shù):優(yōu)化目標是追求總成本最小化,因此目標函數(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)非負約束：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ī)劃的應用案例-合理下料

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

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

第四節(jié)

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

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

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

第四節(jié)

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

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

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

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

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

對偶規(guī)劃的數(shù)學模型一、對偶問題的提出產(chǎn)品平銷是否做代工：設備臺時的最低價碼？談判時衡量對方出價面臨著兩種選擇：自行生產(chǎn)或代加工①合理安排生產(chǎn)的利潤?②利潤不降低的資源轉(zhuǎn)讓最低價？資源出讓模型(對偶問題)A,B,C工時出讓利潤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)計劃模型(原問題)

假設甲乙產(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ù)學模型二、對偶規(guī)劃的性質(zhì)1.對稱性定理

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

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

設

，

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

則

，

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

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

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

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

，第二節(jié)

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

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

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

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

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

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

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

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

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

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

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

10材料BD15裝配裝配D

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

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

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

第四節(jié)

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

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

整數(shù)規(guī)劃的數(shù)學模型線性規(guī)劃的決策變量取值可以是任意非負實數(shù)，但許多實際問題中只有當決策變量取值為整數(shù)才有意義例如，產(chǎn)品的件數(shù)、機器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分數(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ù)學模型一、純整數(shù)規(guī)劃產(chǎn)品資源甲乙現(xiàn)有量A219B5735單臺利潤65例：某企業(yè)利用材料和設備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺產(chǎn)品的獲利能力如下表所示：

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

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

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

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

第一節(jié)

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

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

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

i

址建廠，

yi=0，不選擇第

i

址建廠；計劃從

i址至區(qū)域市場

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

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

這樣做除少數(shù)情況外，一般不可行，因為化整后的解有可能超出了可行域，成為非可行解；或者雖是可行解，卻不是最優(yōu)解。

不考慮整數(shù)約束則是一個LP問題,稱為原整數(shù)規(guī)劃的松弛問題對于例1的數(shù)學模型，不考慮整數(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ù)規(guī)劃問題，可行的整數(shù)解數(shù)量很多，用窮舉法求解是不可能的。例如，指派問題

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

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

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

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