管理運籌學(xué)(ppt)
管 理 運 籌 學(xué)
緒論
線性規(guī)劃（運輸問題）
整數(shù)規(guī)劃
動態(tài)規(guī)劃
存儲論
排隊論
對策論
決策分析
第一章 緒論
運籌學(xué)（Operational Research) 直譯為“運作研究”

運籌學(xué)是應(yīng)用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。

運籌學(xué)有廣泛應(yīng)用
運籌學(xué)的產(chǎn)生和發(fā)展
§1 決策、定量分析與管理運籌學(xué)
決策過程（問題解決的過程）：
1）提出問題：認(rèn)清問題
2）尋求可行方案：建模、求解
3）確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑
4）評估各個方案：解的檢驗、靈敏性分析等
5）選擇最優(yōu)方案：決策
6）方案實施：回到實踐中
7）后評估：考察問題是否得到完滿解決

1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。
§2 運籌學(xué)的分支
線性規(guī)劃

非線性規(guī)劃

整數(shù)規(guī)劃

圖與網(wǎng)絡(luò)模型

存儲模型
排隊論

排序與統(tǒng)籌方法

決策分析

動態(tài)規(guī)劃

預(yù)測

§3運籌學(xué)在工商管理中的應(yīng)用
生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下
料、配料問題、物料管理等
庫存管理：多種物資庫存量的管理，庫存方式、庫存
量等
運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、
運輸工具的調(diào)度以及建廠地址的選擇等
人事管理：對人員的需求和使用的預(yù)測，確定人員編
制、人員合理分配，建立人才評價體系等
市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與
銷售計劃制定等
財務(wù)和會計：預(yù)測、貸款、成本分析、定價、證券管
理、現(xiàn)金管理等
*** 設(shè)備維修、更新，項目選擇、評價，工程優(yōu)化設(shè)計與管理等
運籌學(xué)方法使用情況(美1983)

運籌學(xué)的推廣應(yīng)用前景
據(jù)美勞工局1992年統(tǒng)計預(yù)測: 運籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長百分比預(yù)測為73%,增長速度排到各項職業(yè)的前三位.

結(jié)論:
運籌學(xué)在國內(nèi)或國外的推廣前景是非常廣闊的
工商企業(yè)對運籌學(xué)應(yīng)用和需求是很大的
在工商企業(yè)推廣運籌學(xué)方面有大量的工作要做


第二章 線性規(guī)劃的圖解法
在管理中一些典型的線性規(guī)劃應(yīng)用
合理利用線材問題：如何下料使用材最少
配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤
投資問題：從投資項目中選取方案，使投資回報最大
產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大
勞動力安排：用最少的勞動力來滿足工作的需要
運輸問題：如何制定調(diào)運方案，使總運費最小
線性規(guī)劃的組成：
目標(biāo)函數(shù) Max f 或 Min f
約束條件 s.t. (subject to) 滿足于
決策變量 用符號來表示可控制的因素
§1問題的提出
例1. 某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗以及資源的限制，如下表：



問題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？
線 性 規(guī) 劃 模 型
一般形式
目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + … + cn xn
約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0

標(biāo)準(zhǔn)形式
目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + … + cn xn
約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ，x2 ，… ，xn ≥ 0
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
線性規(guī)劃標(biāo)準(zhǔn)型
§2 線 性 規(guī) 劃 的 圖 解 法
例1.
目標(biāo)函數(shù)：
Max z = 50 x1 + 100 x2
約束條件：
s.t.
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最優(yōu)解：
x1 = 50， x2 = 250
最優(yōu)目標(biāo)值 z = 27500

線性規(guī)劃圖解法的步驟

（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。若各半平面交出來的公共區(qū)域存在，顯然，其中的點滿足所有的約束條件，稱這樣的點為此線性規(guī)劃的可行解，全體可行解的集合稱為可行集或可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問題無可行解。

（3）任意給定目標(biāo)函數(shù)一個確定的值，作出對應(yīng)的目標(biāo)函數(shù)等值線，并確定該族等值線平行移動時目標(biāo)函數(shù)值增加的方向。然后平移目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點又不可能使值再增加的位置(有時交于無窮遠(yuǎn)處，此時稱無有限最優(yōu)解）。此時，目標(biāo)函數(shù)等值線與可行域的交點即此線性規(guī)劃的最優(yōu)解（一個或多個），此目標(biāo)函數(shù)的值即最優(yōu)值。
進 一 步 討 論
線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一： —— 引入松馳變量（含義是資源的剩余量）
例1 中引入 s1， s2， s3 模型化為
目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3
約束條件：s.t. x1 + x2 + s1 = 300
2 x1 + x2 + s2 = 400
x2 + s3 = 250
x1 , x2 , s1 , s2 , s3 ≥ 0
對于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0
說明：生產(chǎn)50單位甲產(chǎn)品和250單位乙產(chǎn)品將消耗完所有可能的設(shè)備臺時數(shù)及原料B，但對原料A則還剩余50千克。

進 一 步 討 論（續(xù)）
解的性質(zhì)：
1） 線性規(guī)劃的最優(yōu)解如果存在，則必定有一個頂點（極點）是最優(yōu)解；
2） 有的線性規(guī)劃問題存在無窮多個最優(yōu)解的情況；
3） 有的線性規(guī)劃問題存在無有限最優(yōu)解的情況，也稱無解；
4） 有的線性規(guī)劃問題存在無可行解的情況。
§3圖解法的靈敏度分析
靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。
3.1 目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析
考慮例1的情況， ci 的變化只影響目標(biāo)函數(shù)等值線的斜率，
目標(biāo)函數(shù) z = 50 x1 + 100 x2
在 z = x2 (x2 = z 斜率為0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率為 -1 )之間時，
原最優(yōu)解 x1 = 50，x2 = 100 仍是最優(yōu)解。
一般情況：
z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2
§3圖解法的靈敏度分析（續(xù)）
目標(biāo)函數(shù)等值線的斜率為 - (c1 / c2 )
當(dāng) -1  - (c1 / c2 )  0 （*） 時，原最優(yōu)解仍是最優(yōu)解
假設(shè)產(chǎn)品乙的利潤100元不變，即 c2 = 100，代到式（*）并整理得
0  c1  100
假設(shè)產(chǎn)品甲的利潤 50 元不變，即 c1 = 50 ，代到式（*）并整理得
50  c2  + 
假若產(chǎn)品甲、乙的利潤均改變，則可直接用式（*）來判斷。
假設(shè)產(chǎn)品甲、乙的利潤分別為60元、55元，則
- 2  - (60 / 55)  - 1
那麼，最優(yōu)解為 z = x1 + x2 和 z = 2 x1 + x2 的交點 x1 = 100，x2 = 200 。


3.2 約束條件中右邊系數(shù) bj 的靈敏度分析(續(xù))
解釋：原最優(yōu)解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。
在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個單位時
1）若約束條件的對偶價格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；
2）若約束條件的對偶價格小于0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；
3）若約束條件的對偶價格等于0，則其最優(yōu)目標(biāo)函數(shù)值不變。

線性規(guī)劃問題的計算機求解(1)
管理運籌學(xué)軟件1.0版使用說明：（演示例1）
一、系統(tǒng)的進入與退出：
1、在WINDOWS環(huán)境下直接運行main.exe文件，或者在DOS下UCDOS中文平臺環(huán)境下運行，也可直接運行各可執(zhí)行程序。
2、退出系統(tǒng)的方法可以在主菜單中選退出項，也可按Ctrl+Break鍵直接退出。
3、在WINDOWS環(huán)境下直接運行軟件，如果出現(xiàn)亂碼，那是因為啟用了全屏幕方式，解決辦法是按ALT+ENTER鍵， 即可轉(zhuǎn)換成非全屏的界面（一般就會消除亂碼，如果還是亂碼，可以點擊菜單的“漢”選項）；若要每次啟動程序都沒有亂碼，則需要修改屏幕設(shè)置的相應(yīng)屬性。具體方法是：在非全屏界面下點擊菜單的“屬性”選項，再選擇“窗口”選項，然后選中其中的“窗口”項，并取消“啟動時恢復(fù)設(shè)置”項，這樣就可保證每次運行軟件時以非全屏方式顯示。

線性規(guī)劃問題的計算機求解(1)續(xù)
二、輸入部分：
1、線性規(guī)劃、整數(shù)規(guī)劃的目標(biāo)函數(shù)和約束的輸入必須按由小到大的序號順序輸入，同時約束變量必須放在運算符的左側(cè)。如（x1+x2-x3=0，不能輸為x2-x3+x1=0；x1-x2+x3=0，不能輸為x1+x3=x2）
2、輸入的約束中不包括“≥”或“≤”，而是用“>”或“<”代替，這不會影響求解。如 對于約束 X1≥2, 則輸入 X1>2, 而不是X1≥2。


線性規(guī)劃問題的計算機求解(2)續(xù)
* 允許增加量 = 上限 - 現(xiàn)在值 c1 的允許增加量為 100 - 50 = 50
b1 的允許增加量為 325 - 300 = 25
* 允許減少量 = 現(xiàn)在值 - 下限 c2 的允許減少量為 100 - 50 = 50
b3 的允許減少量為 250 - 200 = 50
* 允許增加的百分比 = 增加量 / 允許增加量
* 允許減少的百分比 = 減少量 / 允許減少量

考慮前面例題的對偶問題： 若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費。試問：設(shè)備工時和原料A、B 各如何收費才最有競爭力？ 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時、 原料 A、B每單位的收取費用。
線性規(guī)劃對偶問題
Max z = 50x1 + 100x2
s.t. x1 + x2 ≤300
2x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
Min f = 300y1+ 400y2 + 250y3
s.t. y1+2y2 ≥50 （不少于甲產(chǎn)品的利潤）
y1+y2+y3 ≥100 （不少于乙產(chǎn)品的利潤）
y1,y2 ,y3 ≥0

線性規(guī)劃對偶問題
對偶定義
對稱形式： 互為對偶

(LP) Max z = cT x (DP) Min f = bT y
s.t. Ax ≤ b s.t. AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤ ” “Min-- ≥”

線性規(guī)劃對偶問題
一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系。
(1)若一個模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對應(yīng)。
線性規(guī)劃對偶問題
(2)從約束系數(shù)矩陣看：一個模型中為Ａ，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量。
(3)從數(shù)據(jù)b、C 的位置看：在兩個規(guī)劃模型中，b和C 的位置對換。
(4)兩個規(guī)劃模型中的變量皆非負(fù)。
線性規(guī)劃對偶問題
非對稱形式的對偶規(guī)劃
一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。
對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系直接給出其對偶規(guī)劃:
（1）將模型統(tǒng)一為“max，≤”或“min，≥” 的形式，對于其中的等式約束按下面（2）、（3）中的方法處理；
（2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負(fù)限制；
線性規(guī)劃對偶問題
（3）若原規(guī)劃的某個變量的值沒有非負(fù)限 制，則在對偶問題中與此變量對應(yīng)的那個約束為等式。

下面對關(guān)系（2）作一說明。對于關(guān)系（3）
可以給出類似的解釋。
設(shè)原規(guī)劃中第一個約束為等式：
a11x1 + … + a1nxn = b1
那么，這個等式與下面兩個不等式等價
線性規(guī)劃對偶問題
a11x1+…+a1nxn≥b1
a11x1+…+a1nxn≤b1
這樣，原規(guī)劃模型可以寫成
maxZ=c1x1+∧+cnxn
a11x1+∧+a1nxn≤b1
-a11x1-∧-a1nxn≤-b1
M
am1x1+∧+amnxn≤bm
xj≥0,j=1,2, ∧,m

線性規(guī)劃對偶問題
此時已轉(zhuǎn)化為對稱形式，直接寫出對偶規(guī)劃
minf=b1y1’-b1y1’’+b2y2+∧+bmym
a11y1’-a11y1’’∧+am1ym≥c1
a12y1’-a12y1’’∧+am2ym≥c2
M
a1ny1’-a1ny1’’∧+amnym≥cn
y1’,,y1’’,y2,∧,ym≥0,y1
這里，把y1看作是y1=y1’-y1’’,
于是y1沒有非負(fù)限制，關(guān)系（2）的說明完畢。
線性規(guī)劃對偶問題
例3.1寫出下面線性規(guī)劃的對偶規(guī)劃模型：
maxZ=x1-x2+5x3-7x4
x1+3x2-2x3+x4=25
2x1+7x3+2x4≥-60
2x1+2x2-4x3≤30
-5≤x4≤10,x1,x2, ≥0,x3沒有非負(fù)限制
解先將約束條件變形為“≤”形式

線性規(guī)劃對偶問題
x1+3x2-2x3+x4=25
-2x1-7x3-2x4 ≤60
2x1+2x2-4x3 ≤30
x4 ≤10
-x4 ≤5
x1≥0,x2≥0,x3,x4沒有非負(fù)限制
再根據(jù)非對稱形式的對應(yīng)關(guān)系，直
接寫出對偶規(guī)劃
線性規(guī)劃對偶問題
minf =25y1+60y2+30y3+10y4+5y5
y1-2y2+2y3≥1
3y1+2y3 ≥-1
-2y1-7y2-4y3=5
y1-2y2+y4-y5= -7
y1沒有非負(fù)限制，y2,y3,y4,y5≥0

線性規(guī)劃對偶問題
影子價格 —— 是一個向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。
若x*,y* 分別為（LP）和（DP）的最優(yōu)解，
那么， cT x* = bT y* 。
根據(jù) f = bTy*=b1y1*+b2y2*++bmym*
可知 f / bi = yi*
yi* 表示 bi 變化1個單位對目標(biāo) f 產(chǎn)生的影響，稱 yi* 為 bi的影子價格。
線性規(guī)劃對偶問題
影子價格的經(jīng)濟含義
(1)影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價
企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費高于某設(shè)備的影子價格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購買設(shè)備，以擴大生產(chǎn)能力，若市價低于某設(shè)備的影子價格，可考慮買進該設(shè)備，否則不宜買進。
線性規(guī)劃對偶問題
(2)影子價格表明資源增加對總效益產(chǎn)生的影響,根據(jù)理論“設(shè)x0和y0分別為原規(guī)劃（P ）和對偶規(guī)劃（D）的可行解，當(dāng)cx0=bty0時，x0,y0分別是兩個問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關(guān)系：
Z*=f *=b1y1*+b2y2*∧+bmym*根
因此，可以將z*看作是bi,i=1,2,…,m的函數(shù)，對bi求偏導(dǎo)數(shù)可得到：
﹠z*
=yi*i=1,2, ∧,m
﹠bi
這說明，如果右端常數(shù)增加一個單位，則目標(biāo)函數(shù)值的增量將是：
yi*,i=1,2, ∧,m
線性規(guī)劃對偶問題
影子價格反映了不同的局部或個體的增量可以獲得不同的整體經(jīng)濟效益。如果為了擴大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。
線性規(guī)劃對偶問題
需要指出，影子價格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經(jīng)濟含義是指資源在一定范圍內(nèi)增加時的情況，當(dāng)某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數(shù)值線性地增加。


線性規(guī)劃在工商管理中的應(yīng)用(1)續(xù)
解：設(shè) xi 表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的
數(shù)學(xué)模型。
目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6
約束條件：s.t. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0

線性規(guī)劃在工商管理中的應(yīng)用(2)續(xù)
解：設(shè) xi ( i = 1～7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的
數(shù)學(xué)模型。
目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 + x7
約束條件：s.t. x1 + x2 + x3 + x4 + x5 ≥ 28
x2 + x3 + x4 + x5 + x6 ≥ 15
x3 + x4 + x5 + x6 + x7 ≥ 24
x4 + x5 + x6 + x7 + x1 ≥ 25
x5 + x6 + x7 + x1 + x2 ≥ 19
x6 + x7 + x1 + x2 + x3 ≥ 31
x7 + x1 + x2 + x3 + x4 ≥ 28
x1,x2,x3,x4,x5,x6,x7 ≥ 0

線性規(guī)劃在工商管理中的應(yīng)用(3)續(xù)
解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。
求 xi 的利潤：利潤 = 售價 - 各成本之和
可得到 xi （i = 1,2,3,4,5） 的利潤分別為 15、10、7、13、9 元。
這樣我們建立如下的數(shù)學(xué)模型。
目標(biāo)函數(shù)： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
約束條件： s.t. 5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0


線性規(guī)劃在工商管理中的應(yīng)用(4)續(xù)
解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。
利潤 = [（銷售單價 - 原料單價）* 產(chǎn)品件數(shù)]之和 - （每臺時的設(shè)備費用*設(shè)備實際使用的總臺時數(shù)）之和。 這樣我們建立如下的數(shù)學(xué)模型:
Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123
s.t. 5x111 + 10x211 ≤ 6000 （ 設(shè)備 A1 ）
7x112 + 9x212 + 12x312 ≤ 10000 （ 設(shè)備 A2 ）
6x121 + 8x221 ≤ 4000 （ 設(shè)備 B1 ）
4x122 + 11x322 ≤ 7000 （ 設(shè)備 B2 ）
7x123 ≤ 4000 （ 設(shè)備 B3 ）
x111+ x112- x121- x122- x123 = 0 （Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）
x211+ x212- x221 = 0 （Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）
x312 - x322 = 0 （Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）
xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3

線性規(guī)劃在工商管理中的應(yīng)用(5)續(xù)
設(shè) x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。
這樣我們建立如下的數(shù)學(xué)模型。
目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5
約束條件： s.t. x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0

線性規(guī)劃在工商管理中的應(yīng)用(6)續(xù)
解：設(shè) xij 表示第 i 種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣我們建立數(shù)學(xué)模型時，要考慮：
對于甲： x11，x12，x13；
對于乙： x21，x22，x23；
對于丙： x31，x32，x33；
對于原料1： x11，x21，x31；
對于原料2： x12，x22，x32；
對于原料3： x13，x23，x33；
目標(biāo)函數(shù)： 利潤最大，利潤 = 收入 - 原料支出
約束條件： 規(guī)格要求 4 個；
供應(yīng)量限制 3 個。


線性規(guī)劃在工商管理中的應(yīng)用(7)續(xù)
問：
a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？
b）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最??？
解： 1）確定決策變量：連續(xù)投資問題
設(shè) xij ( i = 1～5，j = 1～4)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
線性規(guī)劃在工商管理中的應(yīng)用(7續(xù))
2）約束條件：
第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200；
第二年：B次年末才可收回投資，故第二年年初有資金1.1 x11，于是 x21 + x22+ x24 = 1.1x11；
第三年：年初有資金 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；
第四年：年初有資金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22；
第五年：年初有資金 1.1x41+ 1.25x32，于是 x51 = 1.1x41+ 1.25x32；
B、C、D的投資限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
線性規(guī)劃在工商管理中的應(yīng)用(7續(xù))
3）目標(biāo)函數(shù)及模型：
a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）
b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）



運 輸 問 題（1）
§1 運 輸 模 型
例1、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？

運 輸 問 題（1）續(xù)
解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量
設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：




運 輸 問 題（2）
設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：
m n
Min f =   cij xij
i = 1 j = 1
n
s.t.  xij = si i = 1,2,…,m
j = 1
m
 xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)

運 輸 問 題（2）續(xù)
變化：
1）有時目標(biāo)函數(shù)求最大 如求利潤最大或營業(yè)額最大等；
2）當(dāng)某些運輸線路上的能力有限制時，模型中可直接加入（等式或不等式）約束；
3）產(chǎn)銷不平衡時，可加入虛設(shè)的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。

運 輸 問 題（3）續(xù)
例3、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最?。?




解：增加一個
虛設(shè)的產(chǎn)地
運輸費用為0

運輸問題（4）續(xù)§3 運輸問題的應(yīng)用
解： 根據(jù)題意，作出產(chǎn)銷平衡與運價表：







這里 M 代表一個很大的正數(shù)，其作用是強迫相應(yīng)的 x31、 x33、 x34取值為0。



運輸問題（5）續(xù)§3 運輸問題的應(yīng)用
解： 根據(jù)題意，作出產(chǎn)銷平衡與運價表：








最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 M ，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 0 。對應(yīng) 4”的銷量 50 是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定 D的產(chǎn)量為 50。

運輸問題（6）續(xù)§3 運輸問題的應(yīng)用
解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機數(shù)目，那末應(yīng)滿足：
交貨：x11 = 10 生產(chǎn)：x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生產(chǎn)的柴油機數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機數(shù)目看作第 j 個銷售點的銷量；成本加儲存、維護等費用看作運費。可構(gòu)造下列產(chǎn)銷平衡問題：
目標(biāo)函數(shù)：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44






運輸問題（7）續(xù)§3 運輸問題的應(yīng)用
解： 這個生產(chǎn)存儲問題可化為運輸問題來做。考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地
1）1--6月份合計生產(chǎn)能力（包括上年末儲存量）為743臺，銷量為707臺。設(shè)一假想銷地銷量為36；
2）上年末庫存103臺，只有倉儲費和運輸費，把它列為的0行；
3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應(yīng)為70+80=150臺；
4）1--6表示1--6月份正常生產(chǎn)情況， 1’--6’表示1--6月份加班生產(chǎn)情況。
運輸問題（8）§3 運輸問題的應(yīng)用
產(chǎn)銷平衡與運價表：

運 輸 問 題（9）續(xù)
解：設(shè) xij 為從 i 到 j 的運輸量，可得到有下列特點的線性規(guī)劃模型：

目標(biāo)函數(shù)：Min f = 所有可能的運輸費用（運輸單價與運輸量乘積之和）
約束條件：
對產(chǎn)地（發(fā)點） i ：輸出量 - 輸入量 = 產(chǎn)量
對轉(zhuǎn)運站（中轉(zhuǎn)點）：輸入量 - 輸出量 = 0
對銷地（收點） j ：輸入量 - 輸出量 = 銷量

運 輸 問 題（10）續(xù)
用“管理運籌學(xué)”軟件求得結(jié)果：
x13 = 550 x14 = 0 ；
x23 = 0 x24 = 150 x28 = 300 ；
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ；
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。

運輸問題（11）續(xù)

運輸問題（12）續(xù)
第三章 整數(shù)規(guī)劃

§1 整數(shù)規(guī)劃的圖解法
§2整數(shù)規(guī)劃的計算機求解
§3整數(shù)規(guī)劃的應(yīng)用
§4整數(shù)規(guī)劃的分枝定界法
§1 整數(shù)規(guī)劃的圖解法
例1. 某工廠在計劃期內(nèi)要安排甲、乙兩種儀器設(shè)備的生產(chǎn)，已知生產(chǎn)儀器設(shè)備
需要A、B兩種材
料的消耗以及資
源的限制，如右
表。
問題：工廠應(yīng)分
別生產(chǎn)多少件種儀器設(shè)備才
能使工廠獲利最多？
§2整數(shù)規(guī)劃的計算機求解
例2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 為整數(shù)
例2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 為整數(shù) x1 為0-1變量
§3整數(shù)規(guī)劃的應(yīng)用(1)
一、投資場所的選擇
例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置 Aj (j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定：
在東區(qū)由A1 ， A2 ，A3 三個點至多選擇兩個；
在西區(qū)由A4 ， A5 兩個點中至少選一個；
在南區(qū)由A6 ， A7 兩個點中至少選一個；
在北區(qū)由A8 ， A9 ， A10 三個點中至少選兩個。

Aj 各點的設(shè)備投資及每
年可獲利潤由于地點不同都
是不一樣的，預(yù)測情況見右表所
示 (單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?

§3整數(shù)規(guī)劃的應(yīng)用(1)續(xù)
解：設(shè)：0--1變量 xi = 1 (Ai 點被選用）或 0 (Ai 點沒被選用）。
這樣我們可建立如下的數(shù)學(xué)模型：
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且xj 為0--1變量，i = 1,2,3,……,10

二、固定成本問題
例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如下表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可使用的金
屬板有500噸，勞動力有300人月，機器有100臺月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為 150 萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。


§3整數(shù)規(guī)劃的應(yīng)用(3)續(xù)
解：引入0—1變量 xij，并令
xij = 1(當(dāng)指派第 i人去完成第j項工作時)或0（當(dāng)不指派第 i人去完成第j項工作時)．
這可以表示為一個0--1整數(shù)規(guī)劃問題：
Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44
s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項工作)
x21+ x22+ x23+ x24= 1 (乙只能干一項工作)
x31+ x32+ x33+ x34= 1 (丙只能干一項工作)
x41+ x42+ x43+ x44= 1 (丁只能干一項工作)
x11+ x21+ x31+ x41= 1 ( A工作只能一人干)
x12+ x22+ x32+ x42= 1 ( B工作只能一人干)
x13+ x23+ x33+ x43= 1 ( C工作只能一人干)
x14+ x24+ x34+ x44= 1 ( D工作只能一人干)
xij 為0--1變量，i,j = 1,2,3,4
* * * 求解可用《管理運籌學(xué)》軟件中整數(shù)規(guī)劃方法。

§3整數(shù)規(guī)劃的應(yīng)用(4)續(xù)
解： a) 設(shè) xij為從Ai 運往Bj 的運輸量(單位千箱)， yk = 1(當(dāng)Ak 被選中時)或0（當(dāng)Ak 沒被選中時),k =2,3,4,5．
這可以表示為一個整數(shù)規(guī)劃問題：
Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前4項為固定投資額，后面的項為運輸費用。
s.t. x11+ x12+ x13 ≤ 30 ( A1 廠的產(chǎn)量限制)
x21+ x22+ x23 ≤ 10y2 ( A2 廠的產(chǎn)量限制)
x31+ x32+ x33 ≤ 20y3 ( A3 廠的產(chǎn)量限制)
x41+ x42+ x43 ≤ 30y4 ( A4 廠的產(chǎn)量限制)
x51+ x52+ x53 ≤ 40y5 ( A5 廠的產(chǎn)量限制)
x11+ x21+ x31+ x41 + x51 = 30 ( B1 銷地的限制)
x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制)
x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制)
xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 為0--1變量，k = 2,3,4,5。
* * * 求解可用《管理運籌學(xué)》軟件中整數(shù)規(guī)劃方法。

§3整數(shù)規(guī)劃的應(yīng)用(5)續(xù)
解：1) 設(shè)xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分別表示第 i 年年初給項目A，B，C，D的投資額；
設(shè)yiA， yiB，是0—1變量，并規(guī)定取 1 時分別表示第 i 年給A、B投資，否則取 0（ i = 1, 2, 3, 4, 5）。
設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：2年投資C項目8萬元時，取值為4；
2年投資C項目6萬元時，取值為3；
2年投資C項目4萬元時，取值為2；
2年投資C項目2萬元時，取值為1；
2年不投資C項目時， 取值為0；
這樣我們建立如下的決策變量：
第1年 第2年 第3年 第4年 第5年
A x1A x2A x3A x4A
B x3B
C x2C (=20000y2C)
D x1D x2D x3D x4D x5D

§3整數(shù)規(guī)劃的應(yīng)用(6)續(xù)
3）目標(biāo)函數(shù)及模型：
Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D
s.t. x1A+ x1D = 100000；
x2A+x2C+x2D = 1.06x1D；
x3A+x3B+x3D = 1.15x1A+ 1.06x2D；
x4A+x4D = 1.15x2A+ 1.06x3D；
x5D = 1.15x3A+ 1.06x4D；
x1A ≥ 40000y1A ，
x1A ≤ 200000y1A ，
x3B ≥ 30000y3B ，
x3B ≤ 50000y3B ；
x2C = 20000y2C ，
yiA， yiB = 0 或 1，i = 1,2,3,4,5
y2C = 0，1，2，3，4
xiA ，xiB ，xiC ，xiD ≥ 0 ( i = 1、2、3、4、5）

§4整數(shù)規(guī)劃的分枝定界法(1)
問題（A） Min z = c1 x1 + c2 x2 + … + cn xn 記 問題（B）為去掉整數(shù)約束的問題（A）
s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ，x2 ，… ，xn ≥ 0 為整數(shù)
在分枝定界法過程中求解問題(B)，應(yīng)有以下情況之一：
①(B)無可行解，則(A)亦無可行解，停止對此問題的計算；
②(B)有最優(yōu)解，并滿足整數(shù)約束，即同時為(A)的最優(yōu)解，那么z*同時是當(dāng)前問題(A)最優(yōu)目標(biāo)值的上界和下界。停止對這個問題的計算；
③(B)有最優(yōu)解 x 及最優(yōu)值 z 但不符合整數(shù)條件。這時得到當(dāng)前問題(A)最優(yōu)目標(biāo)值的一個下界 z ＝z ,于是通過以下判斷可對此問題進一步計算。
§4整數(shù)規(guī)劃的分枝定界法(1)續(xù)
分枝定界法的計算過程：
1、對原問題(A)，求解松弛問題(B)。根據(jù)上面分析，若出現(xiàn)情況①，②則停機。若情況③發(fā)生，得到(A)問題最優(yōu)值的一個下界。我們?nèi)握?A)問題的一個可行解，那么對應(yīng)的目標(biāo)函數(shù)值是(A)最優(yōu)值的一個上界 z¯ 。即得到 z ＜ z* ＜z¯。(注：找(A)問題的可行解往往需要較大的計算量，這時可簡單記 z¯＝+，而先不必費很大力量去求較好的上界。從以下分析可以看到，找到一個好的最優(yōu)目標(biāo)值上界，將對算法的快速求得目標(biāo)非常有效。)，轉(zhuǎn)2，進行以下一般步的迭代；


§4整數(shù)規(guī)劃的分枝定界法(2)
2、對當(dāng)前問題進行分枝和定界：
分技：無妨設(shè)當(dāng)前問題為(A)，其松弛問題(B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分量 xr 。構(gòu)造兩個附加約束： xr ≤ [xr] 和 xr ≥ [xr]+1 ，對(A)分別加入這兩個約束，可得到兩個子問題(A1)和(A2)，顯然這兩個子問題的可行解集的并是(A)的可行解集；
定界：根據(jù)前面分析，對每個當(dāng)前問題(A)可以通過求解松弛問題(B)，以及找(A)的可行解得到當(dāng)前問題的上、下界 z¯和 z 。
對一般迭代步，設(shè)根據(jù)分枝定界方法得到了原問題(A)的一個同層子問題(AI )，i＝1，2，...，n 之和的分解。這里的同層子問題是指每個子問題(AI)都是(A)經(jīng)過相同分枝次數(shù)得到的。

§4整數(shù)規(guī)劃的分枝定界法(2)續(xù)
3、比較與剪枝：
對當(dāng)前子問題進行考察，若不需再進行計算，則稱之為剪枝。一般遇到下列情況就需剪枝：
①(B)無可行解；
②(B)的最優(yōu)解符合整數(shù)約束；
③(B)的最優(yōu)值 z ≥ z¯ 。
通過比較，若子問題不剪枝則返回 2 。
分枝定界法當(dāng)所有子問題都剪枝了，即沒有需要處理的子問題時，達(dá)到當(dāng)前上界 z¯ 的可行解即原問題的最優(yōu)解， 算法結(jié)束。
§4整數(shù)規(guī)劃的分枝定界法(3)
分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能解決純整數(shù)規(guī)劃的問題，也能解決混合整數(shù)規(guī)劃的問題。
例：
Min f = -5x1-4x2
s.t. 3x1+4x2 ≤ 24
9x1+5x2 ≤ 45
x1,x2 ≥ 0 整數(shù)


§4整數(shù)規(guī)劃的分枝定界法(4)
隱枚舉法是求解0—1規(guī)劃最常用的方法之一
對于 n 個決策變量的完全 0—1 規(guī)劃，其可行點最多有 2n 個，當(dāng) n 較大時其計算量大得驚人。隱枚舉法的基本思想是根據(jù)0—1規(guī)劃的特點，進行分技逐步求解。
1、用于隱枚舉法的0—1規(guī)劃標(biāo)準(zhǔn)形式：
為了計算的方便，需要把一般的 0—1規(guī)劃問題等價地化成下列標(biāo)準(zhǔn)形式
Min f = c1 x1 + c2 x2 + … + cn xn cj ≥ 0 j = 1,2,…,n
s.t. ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m
x1 ，x2 ，… ，xn = 0 或 1
§4整數(shù)規(guī)劃的分枝定界法(4)續(xù)
下面說明一個完全的0—1規(guī)劃問題可以化為等價的標(biāo)準(zhǔn)形式：
(1)若目標(biāo)函數(shù)求最大：Max z，可令 f = - z，變?yōu)榍笞钚?Min f ；
(2)若目標(biāo)函數(shù)的系數(shù)有負(fù)值時，如 cj ＜0。那么，可以令相應(yīng)的 yj = 1- xj ；
(3)當(dāng)某個約束不等式是“≥”時，只需兩端同乘以 -1，即變?yōu)?ldquo;≤” ；
(4)當(dāng)某個約束是等式約束時，可得到兩個方向相反的不等式。
§4整數(shù)規(guī)劃的分枝定界法(5)
隱枚舉法的基本過程：
1、將0—1規(guī)劃問題化為標(biāo)準(zhǔn)形式，設(shè)其最優(yōu)解為 x*，最優(yōu)目標(biāo)值為 f* 。顯然 x = 0 時，目標(biāo)值 f ＝0 是不考慮線性不等式約束的最小解，于是 f* ≥ 0。若 x = 0 是可行解，那末 f ＝0是該問題的最優(yōu)解，結(jié)束計算。否則，置所有分量為自由變量。轉(zhuǎn)2；
2、任選一自由變量 xk ，令 xk 為固定變量，分別固定為 xk = 0 與 xk ＝1，令所有自由變量取零值，則得到兩個分枝。對每個分枝的試探解進行檢驗（把自由變量逐次定為固定變量的順序可以是任意的，在不進行先驗考察時，常按指標(biāo)變量從小到大的順序進行）。轉(zhuǎn)3；

§4整數(shù)規(guī)劃的分枝定界法(5)續(xù)
3、檢驗當(dāng)前試探解時，遇到下列4種情況就剪枝，即不必再向下分枝，在剪枝的子問題下方標(biāo)記“×”：
情況一：若子問題的試探解可行，即滿足所有線性不等式約束，則此問題的目標(biāo)值是原問題最優(yōu)目標(biāo)值的一個上界記為 f¯ 即 f* ≤ f¯ 。把 f¯ 的值記在子問題框的旁邊，并在下方標(biāo)記上“×”；
§4整數(shù)規(guī)劃的分枝定界法(6)
情況二：若試探解不可行，且存在一個線性不等式約束，將所有固定變量值代入后，所得到的不等式中所有負(fù)系數(shù)之和大于右端項或若無負(fù)系數(shù)時，最小的系數(shù)大于右端項，那么此問題的任何分枝都是不可行的問題。于是在此問題框的下方標(biāo)記“×”；
情況三：若試探解不可行，且它的目標(biāo)值與目標(biāo)函數(shù)中對應(yīng)當(dāng)前自由變量的任一個系數(shù)之和大于所有已得到的上界中最小者時，說明在當(dāng)前問題的基礎(chǔ)上，固定任何自由變量都不可能對目標(biāo)函數(shù)有改善，于是在該問題框的下方標(biāo)記“×”；
情況四：若試探解不可行，但所有變量已被置為固定變量，也應(yīng)剪枝，于是在該問題框的下方標(biāo)記“×”。
把已標(biāo)記“×”的子問題，稱為已探明的枝。轉(zhuǎn)4。

§4整數(shù)規(guī)劃的分枝定界法(6)續(xù)
4、進一步考察。如果所有的枝均為已探明的枝，則停機結(jié)束計算。找出所有子問題框邊標(biāo)記 f¯ 值的問題，比較得到其中最小者，其對應(yīng)的試探解即原問題的最優(yōu)解，相應(yīng)值即原問題的最優(yōu)目標(biāo)值 f*；若沒有標(biāo)記 f¯ 值的框，則說明原問題無最優(yōu)解，實際上原問題無可行解。
如果仍存在尚未探明的分枝，則可任選一個未探明的分枝。轉(zhuǎn)2。


§4整數(shù)規(guī)劃的分枝定界法(7)
0-1規(guī)劃的隱枚舉法

例：
Max z=100x1+30x2+40x3+45x4
s.t. 50x1+30x2+25x3+10x4≤95
7x1+ 2x2+ 3x3+ 4x4≤11
2x1+ x2+ x3+10x4≤12
x4 ≤ x2+ x3
xj= 0 或 1 ，i = 1,2,3,4
標(biāo)準(zhǔn)化：
取f’=-z=-100x1-30x2-40x3 -45x4
令 y1=1-x1, y2=1-x2, y3=1-x3, y4=1-x4
f’=100y1+30y2+40y3 +45y4-215,
記 f = f’ + 215, 得到
Min f=100y1+30y2+40y3 +45y4
s.t.
-50y1-30y2-25y3 -10y4≤-20
- 7y1- 2y2- 2y3 - 4y4≤- 4
- 2y1- y2- y3 -10y4≤- 2
y2+ y3 - y4≤ 1
yj= 0 或 1 ，i = 1,2,3,4
第四章 動態(tài)規(guī)劃
第五章 存貯論(Inventory Theory)
§1 經(jīng)濟訂購批量存貯模型
§2 經(jīng)濟生產(chǎn)批量模型
§3允許缺貨的 經(jīng)濟訂購批量模型
§4允許缺貨的 經(jīng)濟生產(chǎn)批量模型
§5 經(jīng)濟訂購批量折扣模型
§6需求為隨機的單一周期的存貯模型
§7需求為隨機變量的訂貨批量、再訂貨點模型
§8需求為隨機變量的定期檢查存貯量模型
§9物料需求計劃(MRP)與準(zhǔn)時化生產(chǎn)方式(JIT)簡介
第五章 存貯論
存貯是緩解供應(yīng)與需求之間出現(xiàn)的供不應(yīng)求或供過于求等不協(xié)調(diào)情況的必要和有效的方法和措施。
但是，要存貯就需要資金和維護，存貯的費用在企業(yè)經(jīng)營的成本中占據(jù)非常大的部分。
存貯論主要解決存貯策略問題，即如下兩個問題：
1．補充存貯物資時，每次補充數(shù)量(Q)是多少？
2．應(yīng)該間隔多長時間( T )來補充這些存貯物資？
建立不同的存貯模型來解決上面兩個問題，如果模型中的需求率、生產(chǎn)率等一些數(shù)據(jù)皆為確定的數(shù)值時，存貯模型被稱為確定性存貯摸型；如果模型中含有隨機變量則被稱為隨機性存貯模型。
§1 經(jīng)濟訂購批量存貯模型
經(jīng)濟訂購批量存貯模型，又稱不允許缺貨，生產(chǎn)時間很短存貯模型，是一種最基本的確定性存貯模型。在這種模型里，需求率即單位時間從存貯中取走物資的數(shù)量是常量或近似乎常量；當(dāng)存貯降為零時，可以立即得到補充并且所要補充的數(shù)量全部同時到位（包括生產(chǎn)時間很短的情況，我們可以把生產(chǎn)時間近似地看成零）。這種模型不允許缺貨，并要求單位存貯費，每次訂購費，每次訂貨量都是常數(shù)，分別為一些確定的、不變的數(shù)值。
主要參數(shù)：
需求率 ： d
單位貨物單位時間的存貯費： c1
每次訂購費： c3
每次訂貨量： Q
是一些確定的、不變的數(shù)值。

§1 經(jīng)濟訂購批量存貯模型
各參量之間的關(guān)系：
訂貨量 Q 單位存貯費 c1 每次訂購費 c3
越小 存貯費用越小 訂購費用越大
越大 存貯費用越大 訂購費用越小
存貯量Q與時間 t 的關(guān)系
§1 經(jīng)濟訂購批量存貯模型
這種存貯模型的特點：
1. 需求率 （單位時間的需求量）為 d；
2. 無限供貨率（單位時間內(nèi)入庫的貨物數(shù)量） ；
3. 不允許缺貨；
4. 單位貨物單位時間的存貯費 c1 ；
5. 每次的訂貨費 c3 ；
6. 每期初進行補充，即期初存貯量為Q 。
單位時間內(nèi)的總費用=單位時間內(nèi)的存貯費用+單位時間內(nèi)的訂貨費用
單位時間內(nèi)的存貯費用=單位時間內(nèi)購買貨物所占用資金的利息
+貯存?zhèn)}庫的費用+保險費用+損耗費用+管理費用等
設(shè)每次的訂貨量為Q，由于補充的貨物全部同時到位，故0時刻的存貯量為Q。到T時刻存貯量為0，則0到T時間內(nèi)的平均存貯量為Q/2。又設(shè)單位時間內(nèi)的總需求量為D，(單位貨物的進價成本即貨物單價為c)，則
§1 經(jīng)濟訂購批量存貯模型
單位時間內(nèi)的總費用

求極值得使總費用最小的訂購批量為

這是存貯論中著名的經(jīng)濟訂購批量公式，也稱哈里斯-威爾遜公式。
單位時間內(nèi)的存貯費用=

單位時間內(nèi)的訂貨費用=

單位時間內(nèi)的總費用=
§1 經(jīng)濟訂購批量存貯模型

經(jīng)濟生產(chǎn)批量模型也稱不允許缺貨、生產(chǎn)需要一定時間模型，這也是一種確定型的存貯模型。它的存貯狀態(tài)圖為


§2 經(jīng)濟生產(chǎn)批量模型
2. 生產(chǎn)率（單位時間的產(chǎn)量）為 p — 有限供貨率；
3. 不允許缺貨；
4. 單位產(chǎn)品單位時間的存貯費 c1 ；
5. 每次的生產(chǎn)準(zhǔn)備費 c3 ；
6. 每期初進行補充。

設(shè)每次生產(chǎn)量為 Q ，由于生產(chǎn)率是 p，則每次的生產(chǎn)時間 t 為Q/ p ，于是最高庫存量為 (p-d) Q/ p。到T 時刻存貯量為0，則0到T時間內(nèi)的平均存貯量為 (p-d) Q/2p 。故單位時間的存貯費為：


另一方面，設(shè)D為產(chǎn)品的單位時間需求量，則單位時間的生產(chǎn)準(zhǔn)備費為 c3 D /Q ，進而，單位時間的總費用TC為：







§3 允許缺貨的經(jīng)濟訂購批量模型
使TC達(dá)最小值的最佳訂購量


訂購量為Q＊時的最大缺貨量


單位時間的最低總費用


訂購量為Q＊時的最大存貯量為


每個周期T所需時間

顯然， 時，允許缺貨訂購模型趨于經(jīng)濟訂購批量模型。






§4 允許缺貨的經(jīng)濟生產(chǎn)批量模型（1）
此模型與經(jīng)濟生產(chǎn)批量模型相比，放寬了假設(shè)條件：允許缺貨。與允許缺貨的經(jīng)濟訂貨批量模型相比，相差的只是：補充不是靠訂貨，而是靠生產(chǎn)逐步補充，因此，補充數(shù)量不能同時到位。開始生產(chǎn)時，一部分產(chǎn)品滿足需要，剩余產(chǎn)品作為存貯。生產(chǎn)停止時，靠存貯量來滿足需要。
這種模型的存貯狀態(tài)圖為 ：
§4 允許缺貨的經(jīng)濟生產(chǎn)批量模型（2）
存貯量
§4 允許缺貨的經(jīng)濟生產(chǎn)批量模型（3）
這種存貯模型的特點：
1. 需求率 （單位時間的需求量）為 d；
2. 生產(chǎn)率（單位時間的產(chǎn)量）為 p — 有限供貨率；
3. 允許缺貨，且最大缺貨量為S；
4. 單位貨物單位時間的存貯費 c1 ；
5. 每次的訂貨費 c3 ；
6.單位時間缺少一個單位貨物所支付的單位缺貨費c2 ；
7. 當(dāng)缺貨量達(dá)到S時進行補充，且逐步補充到最大存貯量。
§4 允許缺貨的經(jīng)濟生產(chǎn)批量模型（4）
單位時間的總費用
TC =（單位時間的存貯費）+（單位時間的生產(chǎn)準(zhǔn)備費）
+ （單位時間的缺貨費）
=（平均存貯量）×c1 +（單位時間的生產(chǎn)次數(shù)）×c3
+ （平均缺貨量）×c2
§4 允許缺貨的經(jīng)濟生產(chǎn)批量模型（5）
使單位時間總費用TC最小的最優(yōu)生產(chǎn)量



最優(yōu)缺貨量



單位時間最少的總費用



§5 經(jīng)濟訂貨批量折扣模型（1）
§5 經(jīng)濟訂貨批量折扣模型（2）
這種存貯模型的特點：
1. 需求率 （單位時間的需求量）為 d；
2. 無限供貨率（單位時間內(nèi)入庫的貨物數(shù)量） ；
3. 不允許缺貨；
4. 單位貨物單位時間的存貯費為 c1 ；
5. 每次的訂貨費為 c3 ；
6. 單位貨物的進價成本即貨物單價為 c ；
7. 每期初進行補充，即期初存貯量為 Q。
全量折扣模型
設(shè)貨物單價 c 為訂貨量 Q 的分段函數(shù)，即
c(Q) = ki， Q∈[Qi -1 ， Qi ) ，i = 1，2，…，n，
其中 k1 > k2 > … > kn ， Q0< Q1< Q2< … < Qn ， Q0 是最小訂購數(shù)量，通常為0； Qn 為最大批量，通常無限制。
§5 經(jīng)濟訂貨批量折扣模型（3）
下圖是 n = 3時 c(Q) 和 TC 的圖形表示：







當(dāng)訂貨量為Q∈[Qi -1 ， Qi ) 時，由于 c(Q)= ki ，則有



由此可見，總費用 TC 也是 Q 的分段函數(shù)，具體表示如下：

§5 經(jīng)濟訂貨批量折扣模型（4）
TC(Q) = TCi， Q∈[Qi -1 ， Qi ) ， i = 1，2，…，n。
由微積分的有關(guān)知識可知，分段函數(shù)TC(Q)的最小值只可能在函數(shù)導(dǎo)數(shù)不存在的點、區(qū)間的端點和駐點達(dá)到。為此，我們需要先找出這些點。由于 TCi 中的 Dki 是常數(shù)，求導(dǎo)數(shù)為0，所以，類似于模型一，得 TCi 的駐點


由TC 的圖形知，如果 TCi 的駐點 滿足 Qi-1< < Qi ，則計算并比較 TCi( ) ，TCi+1(Qi) ，TCi+2(Qi+1)， … ，TCn(Qn-1)的值，其中最小者所對應(yīng)的 Q 即為最佳訂貨批量Q＊，即Q＊滿足
§5 經(jīng)濟訂貨批量折扣模型（5）
例4. 圖書館設(shè)備公司準(zhǔn)備從生產(chǎn)廠家購進閱覽桌用于銷售，每個閱覽桌的價格為500元，每個閱覽桌存貯一年的費用為閱覽桌價格的20%，每次的訂貨費為200元，該公司預(yù)測這種閱覽桌每年的需求為300個。生產(chǎn)廠商為了促進銷售規(guī)定：如果一次訂購量達(dá)到或超過50個，每個閱覽桌將打九六折，即每個售價為480元；如果一次訂購量達(dá)到或超過100個，每個閱覽桌將打九五折，即每個售價為475元。請決定為使其一年總費用最少的最優(yōu)訂貨批量Q＊，并求出這時一年的總費用為多少？
解：已知 D = 300個/年，c3 = 200/次 。
Q < 50時， k1 = 500元， =500*20% =100（元/個年）
50 ≤ Q < 100時， k2 = 480元， = 480*20% = 96（元/個年）
100 ≤ Q時， k3 = 475元， = 475*20% = 95（元/個年）
§5 經(jīng)濟訂貨批量折扣模型（6）

Q < 50時，


50 ≤ Q < 100時，


100 ≤ Q時，

其中只有 在其范圍內(nèi)。
§5 經(jīng)濟訂貨批量折扣模型（7）
計算得




比較上面的數(shù)值，得一年的總費用最少為147600元，因此，最佳訂貨批量為 Q＊= 50。

§6 需求為隨機的單一周期存貯模型（1）
在前面討論的模型中，我們把需求看成是固定不變的已知常量。但是，在現(xiàn)實世界中，更多的情況卻是需求為一個隨機變量。為此，在本節(jié)中我們將介紹需求是隨機變量，特別是需求服從均勻分布和正態(tài)分布這兩種簡單情況的存貯模型。
所謂單一周期存貯是指在產(chǎn)品訂貨、生產(chǎn)、存貯、銷售這一周期的最后階段或者把產(chǎn)品按正常價格全部銷售完畢，或者把按正常價格未能銷售出去的產(chǎn)品削價銷售出去，甚至扔掉。總之，在這一周期內(nèi)把產(chǎn)品全部處理完畢，而不能把產(chǎn)品放在下一周期里存貯和銷售。季節(jié)性和易腐保鮮產(chǎn)品，例如季節(jié)性的服裝、掛歷、麥當(dāng)勞店里的漢堡包等都是按單一周期的方法處理的。報攤銷售報紙是需要每天訂貨的，但今天的報紙今天必須處理完，與明天的報紙無關(guān)。因此，我們也可以把它看成是一個單一周期的存貯問題，只不過每天都要作出每天的存貯決策。
§6 需求為隨機的單一周期存貯模型（2）
報童問題：報童每天銷售報紙的數(shù)量是一個隨機變量，每日售出 d 份報紙的概率 P(d )（根據(jù)以往的經(jīng)驗）是已知的。報童每售出一份報紙賺 k 元，如果報紙未能售出，每份賠 h 元，問報童每日最好準(zhǔn)備多少報紙？
這就是一個需求量為隨機變量的單一周期的存貯問題。在這個問題中要解決最優(yōu)訂貨量 Q 的問題。如果訂貨量 Q 選得過大，那么報童就會因不能售出報紙造成損失；如果訂貨量 Q 選得過小，那么報童就要因缺貨失去銷售機會而造成機會損失。如何適當(dāng)?shù)剡x擇訂貨量 Q，才能使這兩種損失的期望值之和最小呢？
§6 需求為隨機的單一周期存貯模型（3）
設(shè)售出d 份報紙的概率為P(d )，從概率論可知
已知因報紙未能售出而造成每份損失 h 元，因缺貨而造成機會損失每份k 元，則滿足下面不等式的 Q＊是這兩種損失的期望值之和最小的訂報量


例5. 某報亭出售某種報紙，每售出一百張可獲利15元，如果當(dāng)天不能售出，每一百張賠20元。每日售出該報紙份數(shù)的概率P(d )根據(jù)以往經(jīng)驗如下表所示。試問報亭每日訂購多少張該種報紙能使其賺錢的期望值最大。
§6 需求為隨機的單一周期存貯模型（4）
解：要使其賺錢的期望值最大，也就是使其因售不出報紙的損失和因缺貨失去銷售機會的損失的期望值之和為最小。已知 k = 15，h = 20，則有

另有



故當(dāng)Q = 8時，不等式

成立.因此,最優(yōu)的訂報量為每天800張,此時其賺錢的期望值最大。
§6 需求為隨機的單一周期存貯模型（5）
我們可以把公式（12. 42）改寫成


公式（12. 43）既適用于離散型隨機變量也適用于連續(xù)型隨機變量。如果只考慮連續(xù)型隨機變量，公式（12. 43）又可以改寫為



§6 需求為隨機的單一周期存貯模型（6）
例6. 某書店擬在年前出售一批新年掛歷。每售出一本可盈利20元，如果年前不能售出，必須削價處理。由于削價，一定可以售完，此時每本掛歷要賠16元。根據(jù)以往的經(jīng)驗，市場的需求量近似服從均勻分布，其最低需求為550本，最高需求為1100本，該書店應(yīng)訂購多少新年掛歷，使其損失期望值為最?。?
解：由題意知掛歷的需求量是服從區(qū)間[550，1100]上的均勻分布的隨機變量， k = 20，h = 16，則其需求量小于Q＊的概率為


則由公式（12. 44）得

由此求得 Q＊= 856（本），并從 5/9可知，這時有5/9的概率掛歷有剩余，有1－5/9=4/9的概率掛歷脫銷。
§6 需求為隨機的單一周期存貯模型（7）
例7. 某化工公司與一客戶簽訂了一項供應(yīng)一種獨特的液體化工產(chǎn)品的合同?？蛻裘扛袅鶄€月來購買一次，每次購買的數(shù)量是一個隨機變量，通過對客戶以往需求的統(tǒng)計分析，知道這個隨機變量服從以均值  =1000（公斤），方差  =100 （公斤）的正態(tài)分布?；す旧a(chǎn)一公斤此種產(chǎn)品的成本為15元，根據(jù)合同固定售價為20元。合同要求化工公司必須按時提供客戶的需求。一旦化工公司由于低估了需求產(chǎn)量不能滿足需要，那么化工公司就到別的公司以每公斤19元的價格購買更高質(zhì)量的替代品來滿足客戶的需要。一旦化工公司由于高估了需求，供大于求，由于這種產(chǎn)品在兩個月內(nèi)要老化，不能存貯至六個月后再供應(yīng)給客戶，只能以每公斤5元的價格處理掉?；す緫?yīng)該每次生產(chǎn)多少公斤的產(chǎn)品才使該公司獲利的期望值最大呢？
§6 需求為隨機的單一周期存貯模型（8）
解：根據(jù)題意得 k =5－1= 4，h = 15－5= 10，利用公式（12. 44）得

由于需求服從均值  =1000，方差  =100 的正態(tài)分布，上式即為

通過查閱標(biāo)準(zhǔn)正態(tài)表，得

把  =1000， =100 代入，得
從 可知，當(dāng)產(chǎn)量為945公斤時，有0.29的概率產(chǎn)品有剩余，有1－0.29 = 0.71的概率產(chǎn)品將不滿足需求。
§7需求為隨機變量的訂貨批量、再訂貨點模型（1）
本節(jié)介紹需求為隨機變量的多周期存貯模型。在這種模型里，
由于需求為隨機變量，我們無法求得周期（即兩次訂貨時間間隔）的確切時間，也無法求得再次訂貨點確切來到的時間。
下面我們給出求訂貨量和再訂貨點的最優(yōu)解的近似方法，而精確的數(shù)學(xué)公式太復(fù)雜，這里不作介紹。具體求解步驟如下：
1. 設(shè)全年的需求量近似為D，利用經(jīng)濟訂貨批量存貯模型求出（每次的）最優(yōu)訂貨量Q＊。
2. 根據(jù)具體情況制定出服務(wù)水平，即制定在m天里出現(xiàn)缺貨的概率，也即不出現(xiàn)缺貨的概率為1。利用下式求出 r
P( m 天里需求量 r ) = 1，
其中 r 為再訂貨點，即當(dāng)庫存量下降到r 時訂貨， m 天后貨到。
存貯的 ( r， Q ) 策略 r 為最低存貯量，即訂貨點，對庫存量隨時進行檢查，當(dāng) H >r 時不補充；當(dāng) H ≤ r 時進行補充，每次補充的數(shù)量為Q 。
§7需求為隨機變量的訂貨批量、再訂貨點模型（2）
例8.某裝修材料公司經(jīng)營某品牌的地磚，公司直接從廠家進這種產(chǎn)品。由于公司與廠家距離較遠(yuǎn)，雙方合同規(guī)定，在公司填寫訂貨單后一個星期廠家把地磚運到公司。公司根據(jù)以往的數(shù)據(jù)統(tǒng)計分析知道，在一個星期里此種地磚的需求量服從以均值  =850箱，方差  =120箱的正態(tài)分布，又知道每次訂貨費為250元，每箱地磚的成本為48元，存貯一年的存貯費用為成本的20%，即每箱地磚一年的存貯費用為48×20% = 9.6元。公司規(guī)定的服務(wù)水平為允許由于存貯量不夠造成的缺貨情況為5%。公司應(yīng)如何制定存貯策略，使得一年的訂貨費和存貯費的總和為最少？
解：首先按經(jīng)濟訂貨批量存貯模型求出最優(yōu)訂貨批量Q＊ 。已知每年的平均需求量 D =8 50 ×52 = 44200 箱/年，c1 = 9.6 元/箱年， c3 = 250元，得
§7需求為隨機變量的訂貨批量、再訂貨點模型（3）


于是，每年平均約訂貨 44200/1517≈29次。由服務(wù)水平，得
P (一個星期的需求量 r ) = 1 =1  0.05=0.95
進一步，有

查標(biāo)準(zhǔn)正態(tài)分布表，得

進一步，有 r = 1047，安全存貯量為 r  d m =1047 850 =197箱。
在這樣的存貯策略下，在訂貨期有95%的概率不會出現(xiàn)缺貨，有5%的概率會出現(xiàn)缺貨。
§8 需求為隨機變量的定期檢查存貯量模型(1)
需求為隨機變量的定期檢查存貯量模型是另一種處理多周期的存貯問題的模型。在這個模型里，管理者要訂期例如每隔一周、一個月等檢查產(chǎn)品的庫存量，根據(jù)現(xiàn)有的庫存量來確定訂貨量，在這個模型中管理者所要做的決策是：依照規(guī)定的服務(wù)水平制定出產(chǎn)品的存貯補充水平M。一旦確定了M，也就確定了訂貨量Q 如下所示：
Q = M  H，
式中H 為檢查時的庫存量。
存貯的 (t，r，M ) 策略
每隔 t 時間檢查庫存量 H，當(dāng) H > r 時不補充；當(dāng) H ≤ r 時補充存貯量使之達(dá)到 M，補充量為 M  H。
§8 需求為隨機變量的定期檢查存貯量模型(2)
解：設(shè)商品A的存貯補充水平為 MA從統(tǒng)計知識可知
P (商品A的需求量d  MA ) = 1A =1  0.25=0.975
進一步，有

查標(biāo)準(zhǔn)正態(tài)分布表，得

從而 MA = A +1.96 A ≈717（條）。也就是說，商店在每隔兩周的清貨盤店時，發(fā)現(xiàn)A商品還剩 HA 時，馬上向廠家訂貨A商品為 717  HA 條，使得當(dāng)時A商品的庫存量加上訂貨量正好達(dá)到存貯補充水平 717。
第六章 排隊論 (Queuing Theory)
排隊過程的組成部分
單服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間的排隊模型
多服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間的排隊模型
排隊系統(tǒng)的經(jīng)濟分析
單服務(wù)臺泊松到達(dá)、任意服務(wù)時間的排隊模型
單服務(wù)臺泊松到達(dá)、定長服務(wù)時間的排隊模型
多服務(wù)臺泊松到達(dá)、任意的服務(wù)時間、損失制排隊模型
顧客來源有限制排隊模型
§1 排隊過程的組成部分(1)
一、基本概念

一些排隊系統(tǒng)的例子

排隊系統(tǒng) 顧 客 服務(wù)臺 服 務(wù)

電話系統(tǒng) 電話呼叫 電話總機 接通呼叫或取消呼叫
售票系統(tǒng) 購票旅客 售票窗口 收款、售票
設(shè)備維修 出故障的設(shè)備 修理工 排除設(shè)備故障
防空系統(tǒng) 進入陣地的敵機 高射炮 瞄準(zhǔn)、射擊直至敵機被擊落或 離開

排隊的過程可表示為：





§1 排隊過程的組成部分(2)
考慮要點：

1、服務(wù)臺（或通道）數(shù)目：單服務(wù)臺（單通道）、多服務(wù)臺（多通道）。
2、顧客到達(dá)過程：本教材主要考慮顧客的泊松到達(dá)情況。
滿足以下四個條件的輸入流稱為泊松流（泊松過程）
*平穩(wěn)性：在時間區(qū)間 [t, t+t) 內(nèi)到達(dá)k個顧客的概率與t無關(guān)，只與 t 有關(guān)，記為 pk(t）；
*無后效性：不相交的時間區(qū)間內(nèi)到達(dá)的顧客數(shù)互相獨立；
*普通性：在足夠短的時間內(nèi)到達(dá)多于一個顧客的概率可以忽略；
*有限性：任意有限個區(qū)間內(nèi)到達(dá)有限個顧客的概率等于1。
泊松分布  為單位時間平均到達(dá)的顧客數(shù)
P (x) = x e- / x! (x = 0, 1, 2,……)

§1 排隊過程的組成部分(2)續(xù)
3、服務(wù)時間分布： 服從負(fù)指數(shù)分布  為平均服務(wù)率，即單位時間服務(wù)的顧客數(shù)，
P（服務(wù)時間≤ t ) = 1- e- t 。
4、排隊規(guī)則分類
(1) 等待制： 顧客到達(dá)后，一直等到服務(wù)完畢以后才離去，
先到先服務(wù)，后到先服務(wù)，隨機服務(wù)，有優(yōu)先權(quán)的服務(wù)；
(2) 損失制： 到達(dá)的顧客有一部分未接受服務(wù)就離去。

5、平穩(wěn)狀態(tài)： 業(yè)務(wù)活動與時間無關(guān)

§1 排隊過程的組成部分(3)
§2 單服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間的排隊模型
M / M / 1 / ∞ / ∞
單位時間顧客平均到達(dá)數(shù) ，單位平均服務(wù)顧客數(shù)  (< )
數(shù)量指標(biāo)公式:
1、系統(tǒng)中無顧客的概率 P0 =1  /
2、平均排隊的顧客數(shù) Lq =2/(  )
3、系統(tǒng)中的平均顧客數(shù) Ls = Lq +  /
4、顧客花在排隊上的平均等待時間 Wq = Lq / 
5、顧客在系統(tǒng)中的平均逗留時間 Ws = Wq+ 1/
6、顧客得不到及時服務(wù)必須排隊等待的概率 Pw = /
7、系統(tǒng)中恰好有 n 個顧客的概率 Pn =( /)n P0















第七章 對策論
由“齊王賽馬”引入
1.對策論的基本概念
對策模型的三個基本要素：
1.局中人：參與對抗的各方；
2.策略集：局中人選擇對付其它局中人的行動方案稱為策略；某局中人的所有可能策略全體稱為策略集；
3.一局勢對策的益損值：局中人各自使用一個對策就形成了一個局勢，一個局勢決定了各局中人的對策結(jié)果（量化）稱為該局勢對策的益損值。
“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）

其中：齊王的策略集: S1={ 1, 2, 3, 4, 5, 6 }，
田忌的策略集：S2={ 1, 2, 3, 4, 5, 6 }。
下面矩陣稱齊王的贏得矩陣：
3 1 1 1 -1 1
1 3 1 1 1 -1
A= 1 -1 3 1 1 1
-1 1 1 3 1 1
1 1 1 -1 3 1
1 1 -1 1 1 3
1.對策論的基本概念（續(xù)）
二人有限零和對策（又稱矩陣對策）：
局中人為2；每個局中人的策略集的策略數(shù)目都是有限的；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。
通常將矩陣對策記為: G = {S1, S2, A}
S1：甲的策略集； S2：乙的策略集；
A：甲的贏得矩陣。
“齊王賽馬”是一個矩陣策略。
2.矩陣對策的最優(yōu)純策略
在甲方的贏得矩陣中：
A=[aij]m×n
i 行代表甲方策略 i=1, 2, …, m；j 行代表乙方策略 j=1, 2, …, n；aij 代表甲方取策略 i，乙方取策略 j，這一局勢下甲方的益損值。此時乙方的益損值為 -aij（零和性質(zhì)）。
在考慮各方采用的策略時，必須注意一個前提，就是雙方都是理智的，即雙方都是從各自可能出現(xiàn)的最不利的情形選擇一種最為有利的情況作為決策的依據(jù)。
2.矩陣對策的最優(yōu)純策略(續(xù))
例2 某單位采購員在秋天決定冬季取暖用煤的貯兩問題。已知在正常的冬季氣溫條件下要消耗15噸煤，在較暖和較冷的氣溫條件下要消耗10噸和20噸。假定冬季的煤價隨天氣寒冷程度而有所變化，在較暖、正常、較冷的氣候條件下每噸煤價分別為10元，15元和20元，又設(shè)秋季時煤價為每噸10元。在沒有關(guān)于當(dāng)年冬季準(zhǔn)確的氣象預(yù)報的條件下，秋季貯煤多少噸能使單位的支出最少？

解：
局中人I為采購員；局中人II為大自然，采購員有三個策略，在秋季買10噸、15噸和20噸，分別記為1、2 、3，大自然也有三個策略，分別為較暖、正常和較冷，記為1、2、 3。
以冬季取暖用煤實際費用，作為局中I采購員的贏得，得到贏得矩陣如下：
1（較暖） 2 （正常） 3 （較冷） min
1 -100 -175 -300 -300
2 -150 -150 -250 -250
3 -200 -200 -200 -200
Max -100 -150 -200


得 max min aij=min max aij=a32=-200

3.矩陣對策的混合策略
設(shè)矩陣對策 G = { S1, S2, A }。當(dāng)
max min aij  min max aij
i j j i
時，不存在最優(yōu)純策略。
例：設(shè)一個贏得矩陣如下:
min
5 9 5
A = max 6 策略2
8 6 6 i

max 8 9
min 8 策略1
j

當(dāng)甲取策略2 ，乙取策略1時，甲實際贏得8比預(yù)期的多2，乙當(dāng)然不滿意。考慮到甲可能取策略2這一點，乙采取策略2。若甲也分析到乙可能采取策略2這一點，取策略1，則贏得更多為9 … 。此時，對兩個局中人甲、乙來說，沒有一個雙方均可接受的平衡局勢，其主要原因是甲和乙沒有執(zhí)行上述原則的共同基礎(chǔ)，即 max min aij  min max aij 。
i j j i
一個自然的想法：對甲（乙）給出一個選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）-----即混合策略。

求解混合策略的問題有圖解法、迭代法、線性方程法和線性規(guī)劃法等我們這里只介紹線性規(guī)劃法，其他方法略。
例：設(shè)甲使用策略1的概率為X1′，使用策略2的概率為X2′ ，并設(shè)在最壞的情況下，甲贏得的平均值為V（未知）。
5 9
A= STEP 1
8 6 1) X1′+X2′=1
X1′, X2′0

2)無論乙取何策略，甲的平均贏得應(yīng)不少于V:
對乙取1： 5X1’+ 8X2’ V
對乙取2： 9X1’+ 6X2’ V
注意 V>0,因為A各元素為正。
STEP 2
作變換： X1= X1’/V ; X2= X2’/V
得到上述關(guān)系式變?yōu)椋?
X1+ X2=1/V (V愈大愈好）待定
5X1+ 8X21
9X1+ 6X21
X1, X20

建立線性模型：
min X1+X2
s.t. 5X1+8X21 X1= 1/21
9X1+6X21 X2= 2/21
X1, X20 1/V= X1+X2=1/7
所以，V=7
返回原問題： X1’= X1V= 1/3
X2’= X2V= 2/3
于是甲的最優(yōu)混合策略為：
以1/3的概率選1， 以2/3的概率選2，最優(yōu)值V=7.


3.矩陣對策的混合策略(續(xù))
例：求解“齊王賽馬”問題。

優(yōu)超原則：
假設(shè)矩陣對策 G ={ S1, S2, A }
甲方贏得矩陣 A=[aij]mn
若存在兩行（列），s 行（列）的各元素均優(yōu)于 t 行（列）的元素，即
asjatj j=1,2 … n ( ais  ait i=1,2 … m )
稱甲方策略s優(yōu)超于t ( s優(yōu)超于t)
3.矩陣對策的混合策略(續(xù))
優(yōu)超原則：當(dāng)局中人甲方的策略t被其它策略所優(yōu)超時，可在其贏得矩陣A中劃去第t行（同理，當(dāng)局中人乙方的策略t被其它策略所優(yōu)超時，可在矩陣A中劃去第t列）。
如此得到階數(shù)較小的贏得矩陣A’，其對應(yīng)的矩陣對策
G’= { S1, S2, A’} 與 G = { S1, S2, A }
等價，即解相同。
3.矩陣對策的混合策略(續(xù))
例 5. 設(shè)甲方的益損值，贏得矩陣為
3 2 0 3 0 被第3、4行所優(yōu)超
5 0 2 5 9 被第3行所優(yōu)超
A= 7 3 9 5 9
4 6 8 7 5.5
6 0 8 8 3
得到
7 3 9 5 9 被第1列所優(yōu)超
A1= 4 6 8 7 5.5 被第2列所優(yōu)超
6 0 8 8 3

3.矩陣對策的混合策略(續(xù))
3.矩陣對策的混合策略(續(xù))
對A4計算，用線性規(guī)劃方法得到：
（注意：余下的策略為3，4，1，2）
甲： X* = (0，0，1/15，2/15，0)T V=5
X*’= (0，0，1/3 ，2/3 ，0)T
乙： Y* = (1/10，1/10，0，0，0)T V=5
Y*’= (1/2 ，1/2 ，0，0，0)T 。

注：
利用有超原則化簡贏得矩陣時，有可能將原對策問題的解也劃去一些（多解情況）；
線性規(guī)劃求解時有可能是多解問題。
習(xí)題：P343-1，3，4
第八章 決策分析
“決策” 一詞來源于英語 Decision making，直譯為“做出決定”。所謂決策，就是為了實現(xiàn)預(yù)定的目標(biāo)在若干可供選擇的方案中，選出一個最佳行動方案的過程，它是一門幫助人們科學(xué)地決策的理論。
第十五章 決策分析
決策的分類：
按決策問題的重要性分類
按決策問題出現(xiàn)的重復(fù)程度分類
按決策問題的定量分析和定性分析分類
按決策問題的自然狀態(tài)發(fā)生分類：
第十五章 決策分析
確 定 型 決 策 問 題
在決策環(huán)境完全確定的條件下進行，
不 確 定 型 決 策 問 題
在決策環(huán)境不確定的條件下進行，決策者對各自然狀態(tài)發(fā)生的概率一無所知
風(fēng) 險 型 決 策 問 題
在決策環(huán)境不確定的條件下進行，決策者對各自然狀態(tài)發(fā)生的概率可以預(yù)先估計或計算出來
第十五章 決策分析
構(gòu)成決策問題的四個要素：
決策目標(biāo)、行動方案、自然狀態(tài)、效益值
行動方案集： A = { s1, s2, …, sm }
自然狀態(tài)集： N = { n1, n2, …, nk }
效益(函數(shù))值：v = ( si, nj )
自然狀態(tài)發(fā)生的概率P=P(sj) j =1, 2, …, m
決策模型的基本結(jié)構(gòu)：(A, N, P, V)
基本結(jié)構(gòu)(A, N, P, V)常用決策表、決策樹等表示
§1 不確定情況下的決策
特征：1、自然狀態(tài)已知；2、各方案在不同自然狀態(tài)下的收益值已知；3、自然狀態(tài)發(fā)生不確定。

例：某公司需要對某新產(chǎn)品生產(chǎn)批量作出決策，各種批量在不同的自然狀態(tài)下的收益情況如下表（收益矩陣）：
§1 不確定情況下的決策（續(xù)）
一、最大最小準(zhǔn)則（悲觀準(zhǔn)則）
決策者從最不利的角度去考慮問題：
先選出每個方案在不同自然狀態(tài)下的最小收益值（最保險），然后從這些最小收益值中取最大的，從而確定行動方案。 用(Si, Nj)表示收益值
§1 不確定情況下的決策（續(xù)）
二、最大最大準(zhǔn)則（樂觀準(zhǔn)則）
決策者從最有利的角度去考慮問題：
先選出每個方案在不同自然狀態(tài)下的最大收益值（最樂觀），然后從這些最大收益值中取最大的，從而確定行動方案。 用(Si, Nj)表示收益值
§1 不確定情況下的決策（續(xù)）
三、等可能性準(zhǔn)則 ( Laplace準(zhǔn)則 )
決策者把各自然狀態(tài)發(fā)生的機會看成是等可能的：
設(shè)每個自然狀態(tài)發(fā)生的概率為 1/事件數(shù) ，然后計算各行動方案的收益期望值。
用 E(Si )表示第I方案的收益期望值
§1 不確定情況下的決策（續(xù)）
四、樂觀系數(shù)(折衷)準(zhǔn)則(Hurwicz胡魏茲準(zhǔn)則)
決策者取樂觀準(zhǔn)則和悲觀準(zhǔn)則的折衷：
先確定一個樂觀系數(shù) （01），然后計算：CVi =  max [(Si, Nj)] +（1- ）min [(Si, Nj)]
從這些折衷標(biāo)準(zhǔn)收益值CVi中選取最大的，從而確定行動方案。 取  = 0.7
§1 不確定情況下的決策（續(xù)）
五、后悔值準(zhǔn)則（Savage 沙萬奇準(zhǔn)則）
決策者從后悔的角度去考慮問題：
把在不同自然狀態(tài)下的最大收益值作為理想目標(biāo)把各方案的收益值與這個最大收益值的差稱為未達(dá)到理想目標(biāo)的后悔值，然后從各方案最大后悔值中取最小者，從而確定行動方案。 用aij’表示后悔值，構(gòu)造后悔值矩陣：
§2 風(fēng)險型情況下的決策
特征：1、自然狀態(tài)已知；2、各方案在不同自然狀態(tài)下的收益值已知；3、自然狀態(tài)發(fā)生的概率分布已知。
一、最大可能準(zhǔn)則
在一次或極少數(shù)幾次的決策中，取概率最大的自然狀態(tài)，按照確定型問題進行討論。
§2 風(fēng)險型情況下的決策（續(xù)）
二、期望值準(zhǔn)則
根據(jù)各自然狀態(tài)發(fā)生的概率，求不同方案的期望收益值，取其中最大者為選擇的方案。
E(Si) =  P(Nj) (Si,Nj)
§2 風(fēng)險型情況下的決策（續(xù)）
三、決策樹法
具體步驟：
(1) 從左向右繪制決策樹；
(2) 從右向左計算各方案的期望值，并將結(jié)果標(biāo)在相應(yīng)方案節(jié)點的上方；
(3) 選收益期望值最大(損失期望值最小)的方案為最優(yōu)方案，并在其它方案分支上打∥記號。
主要符號
決策點 方案節(jié)點 結(jié)果節(jié)點
§2 風(fēng)險型情況下的決策（續(xù)）
前例 根據(jù)下圖說明S3是最優(yōu)方案，收益期望值為6.5
§2 風(fēng)險型情況下的決策（續(xù)）
四、靈敏度分析
研究分析決策所用的數(shù)據(jù)在什么范圍內(nèi)變化時,原最優(yōu)決策方案仍然有效.
前例 取 P(N1) = p , P(N2) = 1- p . 那么
E(S1) = p30 + (1-p)(-6) = 36p - 6 p=0.35為轉(zhuǎn)折概率
E(S2) = p20 + (1-p)(-2) = 22p - 2 實際的概率值距轉(zhuǎn)
E(S3) = p10 + (1-p)(+5) = 5p + 5 折概率越遠(yuǎn)越穩(wěn)定
§2 風(fēng)險型情況下的決策（續(xù)）
五、全情報的價值（EVPI）
全情報：關(guān)于自然狀況的確切消息。
在前例，當(dāng)我們不掌握全情報時得到 S3 是最優(yōu)方案，數(shù)學(xué)期望最大值為 0.3*10 + 0.7*5 = 6.5萬 記為 EVW0PI。
若得到全情報：當(dāng)知道自然狀態(tài)為N1時，決策者必采取方案S1，可獲得收益30萬，概率0.3；當(dāng)知道自然狀態(tài)為N2時，決策者必采取方案S3，可獲得收益5萬, 概率0.7。于是，全情報的期望收益為
EVWPI = 0.3*30 + 0.7*5 = 12.5萬
那么， EVPI = EVWPI - EVW0PI = 12.5 - 6.5 = 6萬
即這個全情報價值為6萬。當(dāng)獲得這個全情報需要的成本小于6萬時，決策者應(yīng)該對取得全情報投資，否則不應(yīng)投資。

注：一般“全”情報仍然存在可靠性問題。
§2 風(fēng)險型情況下的決策（續(xù)）
六、具有樣本情報的決策分析（貝葉斯決策）
先驗概率：由過去經(jīng)驗或?qū)＜夜烙嫷膶l(fā)生事件的概率；
后驗概率：利用樣本情報對先驗概率修正后得到的概率；
前例，如果請咨詢公司進行市場調(diào)查，可以根據(jù)樣本情報來修正先驗概率，得到后驗概率。如此用決策樹方法，可得到更高期望值的決策方案。
在自然狀態(tài)為Nj的條件下咨詢結(jié)果為Ik的條件概率，可用全概率公式計算

再用貝葉斯公式計算


條件概率的定義： 乘法公式

§3 效用理論在決策中的應(yīng)用
效用：衡量決策方案的總體指標(biāo)，反映決策者對決策問題各種因素的總體看法
使用效用值進行決策：首先把要考慮的因素折合成效用值，然后用決策準(zhǔn)則下選出效用值最大的方案，作為最優(yōu)方案。
例：求下表顯示問題的最優(yōu)方案（萬元）
§3 效用理論在決策中的應(yīng)用（續(xù)）
用收益期望值法：
E(S1) = 0.360 + 0.540 + 0.2(-100) = 18萬
E(S2) = 0.3100 + 0.5（-40）+ 0.2(-60) = -2萬
E(S3) = 0.30 + 0.50 + 0.20 = 0萬
得到 S1 是最優(yōu)方案，最高期望收益18萬。

一種考慮：
由于財務(wù)情況不佳，公司無法承受S1中虧損100萬的風(fēng)險，也無法承受S2中虧損50萬以上的風(fēng)險，結(jié)果公司選擇S3，即不作任何項目。

§3 效用理論在決策中的應(yīng)用（續(xù)）
用效用函數(shù)解釋：
把上表中的最大收益值100萬元的效用定為10，即U(100) = 10；最小收益值-100萬元的效用定為0，即U(-100) = 0；
對收益60萬元確定其效用值：設(shè)經(jīng)理認(rèn)為使下兩項等價的 p=0.95
(1)得到確定的收益60萬；
(2)以 p 的概率得到100萬，以 1- p 的概率損失100萬。
計算得：U（60）= p*U(100)+(1-p)*U(-100) = 0.95*10+0.05*0=9.5

§3 效用理論在決策中的應(yīng)用（續(xù)）
類似地，設(shè)收益值為40、0、- 40、- 60相應(yīng)等價的概率分別為0.90、0.75、0.55、0.40，可得到各效用值：
U(40) = 9.0； U(0) = 7.5； U(-40) = 5.5； U(-60) = 4.0
我們用效用值計算最大期望，如下表：
§3 效用理論在決策中的應(yīng)用（續(xù)）
一般，若收益期望值能合理地反映決策者的看法和偏好，可以用收益期望值進行決策。否則，需要進行效用分析。
收益期望值決策是效用期望值決策的一種特殊情況。



管理運籌學(xué)(ppt)