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

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

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

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

非線性規(guī)劃

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

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

存儲(chǔ)模型
排隊(duì)論

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

決策分析

動(dòng)態(tài)規(guī)劃

預(yù)測(cè)

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

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

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


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



問(wèn)題：工廠應(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）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。若各半平面交出來(lái)的公共區(qū)域存在，顯然，其中的點(diǎn)滿足所有的約束條件，稱(chēng)這樣的點(diǎn)為此線性規(guī)劃的可行解，全體可行解的集合稱(chēng)為可行集或可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問(wèn)題無(wú)可行解。

（3）任意給定目標(biāo)函數(shù)一個(gè)確定的值，作出對(duì)應(yīng)的目標(biāo)函數(shù)等值線，并確定該族等值線平行移動(dòng)時(shí)目標(biāo)函數(shù)值增加的方向。然后平移目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置(有時(shí)交于無(wú)窮遠(yuǎn)處，此時(shí)稱(chēng)無(wú)有限最優(yōu)解）。此時(shí)，目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即此線性規(guī)劃的最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。
進(jìn) 一 步 討 論
線性規(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
對(duì)于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0
說(shuō)明：生產(chǎn)50單位甲產(chǎn)品和250單位乙產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。

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


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

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

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


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

考慮前面例題的對(duì)偶問(wèn)題： 若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費(fèi)。試問(wèn)：設(shè)備工時(shí)和原料A、B 各如何收費(fèi)才最有競(jìng)爭(zhēng)力？ 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時(shí)、 原料 A、B每單位的收取費(fèi)用。
線性規(guī)劃對(duì)偶問(wèn)題
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)品的利潤(rùn)）
y1+y2+y3 ≥100 （不少于乙產(chǎn)品的利潤(rùn)）
y1,y2 ,y3 ≥0

線性規(guī)劃對(duì)偶問(wèn)題
對(duì)偶定義
對(duì)稱(chēng)形式： 互為對(duì)偶

(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ī)劃對(duì)偶問(wèn)題
一對(duì)對(duì)稱(chēng)形式的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系。
(1)若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對(duì)偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對(duì)應(yīng)。
線性規(guī)劃對(duì)偶問(wèn)題
(2)從約束系數(shù)矩陣看：一個(gè)模型中為Ａ，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量。
(3)從數(shù)據(jù)b、C 的位置看：在兩個(gè)規(guī)劃模型中，b和C 的位置對(duì)換。
(4)兩個(gè)規(guī)劃模型中的變量皆非負(fù)。
線性規(guī)劃對(duì)偶問(wèn)題
非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃
一般稱(chēng)不具有對(duì)稱(chēng)形式的一對(duì)線性規(guī)劃為非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃。
對(duì)于非對(duì)稱(chēng)形式的規(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ù)限制；
線性規(guī)劃對(duì)偶問(wèn)題
（3）若原規(guī)劃的某個(gè)變量的值沒(méi)有非負(fù)限 制，則在對(duì)偶問(wèn)題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。

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

線性規(guī)劃對(duì)偶問(wèn)題
此時(shí)已轉(zhuǎn)化為對(duì)稱(chēng)形式，直接寫(xiě)出對(duì)偶規(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沒(méi)有非負(fù)限制，關(guān)系（2）的說(shuō)明完畢。
線性規(guī)劃對(duì)偶問(wèn)題
例3.1寫(xiě)出下面線性規(guī)劃的對(duì)偶規(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沒(méi)有非負(fù)限制
解先將約束條件變形為“≤”形式

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

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


線性規(guī)劃在工商管理中的應(yīng)用(1)續(xù)
解：設(shè) xi 表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(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)表示星期一至日開(kāi)始休息的人數(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é)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。
求 xi 的利潤(rùn)：利潤(rùn) = 售價(jià) - 各成本之和
可得到 xi （i = 1,2,3,4,5） 的利潤(rùn)分別為 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ù)量。
利潤(rùn) = [（銷(xiāo)售單價(jià) - 原料單價(jià)）* 產(chǎn)品件數(shù)]之和 - （每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(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é)模型時(shí)，要考慮：
對(duì)于甲： x11，x12，x13；
對(duì)于乙： x21，x22，x23；
對(duì)于丙： x31，x32，x33；
對(duì)于原料1： x11，x21，x31；
對(duì)于原料2： x12，x22，x32；
對(duì)于原料3： x13，x23，x33；
目標(biāo)函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 - 原料支出
約束條件： 規(guī)格要求 4 個(gè)；
供應(yīng)量限制 3 個(gè)。


線性規(guī)劃在工商管理中的應(yīng)用(7)續(xù)
問(wèn)：
a）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？
b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最小？
解： 1）確定決策變量：連續(xù)投資問(wèn)題
設(shè) xij ( i = 1～5，j = 1～4)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量：
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）



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

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




運(yùn) 輸 問(wèn) 題（2）
設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型：
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)

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

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




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

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







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



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








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

運(yùn)輸問(wèn)題（6）續(xù)§3 運(yùn)輸問(wèn)題的應(yīng)用
解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(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)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷(xiāo)平衡問(wè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






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

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

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

運(yùn) 輸 問(wèn) 題（10）續(xù)
用“管理運(yùn)籌學(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 。

運(yùn)輸問(wèn)題（11）續(xù)

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

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

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

§3整數(shù)規(guī)劃的應(yīng)用(1)續(xù)
解：設(shè)：0--1變量 xi = 1 (Ai 點(diǎn)被選用）或 0 (Ai 點(diǎn)沒(méi)被選用）。
這樣我們可建立如下的數(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

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


§3整數(shù)規(guī)劃的應(yīng)用(3)續(xù)
解：引入0—1變量 xij，并令
xij = 1(當(dāng)指派第 i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第 i人去完成第j項(xiàng)工作時(shí))．
這可以表示為一個(gè)0--1整數(shù)規(guī)劃問(wèn)題：
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 (甲只能干一項(xiàng)工作)
x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作)
x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作)
x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作)
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
* * * 求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

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

§3整數(shù)規(guī)劃的應(yīng)用(5)續(xù)
解：1) 設(shè)xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分別表示第 i 年年初給項(xiàng)目A，B，C，D的投資額；
設(shè)yiA， yiB，是0—1變量，并規(guī)定取 1 時(shí)分別表示第 i 年給A、B投資，否則取 0（ i = 1, 2, 3, 4, 5）。
設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：2年投資C項(xiàng)目8萬(wàn)元時(shí)，取值為4；
2年投資C項(xiàng)目6萬(wàn)元時(shí)，取值為3；
2年投資C項(xiàng)目4萬(wàn)元時(shí)，取值為2；
2年投資C項(xiàng)目2萬(wàn)元時(shí)，取值為1；
2年不投資C項(xiàng)目時(shí)， 取值為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)
問(wèn)題（A） Min z = c1 x1 + c2 x2 + … + cn xn 記 問(wèn)題（B）為去掉整數(shù)約束的問(wèn)題（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ù)
在分枝定界法過(guò)程中求解問(wèn)題(B)，應(yīng)有以下情況之一：
①(B)無(wú)可行解，則(A)亦無(wú)可行解，停止對(duì)此問(wèn)題的計(jì)算；
②(B)有最優(yōu)解，并滿足整數(shù)約束，即同時(shí)為(A)的最優(yōu)解，那么z*同時(shí)是當(dāng)前問(wèn)題(A)最優(yōu)目標(biāo)值的上界和下界。停止對(duì)這個(gè)問(wèn)題的計(jì)算；
③(B)有最優(yōu)解 x 及最優(yōu)值 z 但不符合整數(shù)條件。這時(shí)得到當(dāng)前問(wèn)題(A)最優(yōu)目標(biāo)值的一個(gè)下界 z ＝z ,于是通過(guò)以下判斷可對(duì)此問(wèn)題進(jìn)一步計(jì)算。
§4整數(shù)規(guī)劃的分枝定界法(1)續(xù)
分枝定界法的計(jì)算過(guò)程：
1、對(duì)原問(wèn)題(A)，求解松弛問(wèn)題(B)。根據(jù)上面分析，若出現(xiàn)情況①，②則停機(jī)。若情況③發(fā)生，得到(A)問(wèn)題最優(yōu)值的一個(gè)下界。我們?nèi)握?A)問(wèn)題的一個(gè)可行解，那么對(duì)應(yīng)的目標(biāo)函數(shù)值是(A)最優(yōu)值的一個(gè)上界 z¯ 。即得到 z ＜ z* ＜z¯。(注：找(A)問(wèn)題的可行解往往需要較大的計(jì)算量，這時(shí)可簡(jiǎn)單記 z¯＝+，而先不必費(fèi)很大力量去求較好的上界。從以下分析可以看到，找到一個(gè)好的最優(yōu)目標(biāo)值上界，將對(duì)算法的快速求得目標(biāo)非常有效。)，轉(zhuǎn)2，進(jìn)行以下一般步的迭代；


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

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


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

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

§4整數(shù)規(guī)劃的分枝定界法(6)續(xù)
4、進(jìn)一步考察。如果所有的枝均為已探明的枝，則停機(jī)結(jié)束計(jì)算。找出所有子問(wèn)題框邊標(biāo)記 f¯ 值的問(wèn)題，比較得到其中最小者，其對(duì)應(yīng)的試探解即原問(wèn)題的最優(yōu)解，相應(yīng)值即原問(wèn)題的最優(yōu)目標(biāo)值 f*；若沒(méi)有標(biāo)記 f¯ 值的框，則說(shuō)明原問(wèn)題無(wú)最優(yōu)解，實(shí)際上原問(wèn)題無(wú)可行解。
如果仍存在尚未探明的分枝，則可任選一個(gè)未探明的分枝。轉(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
第四章 動(dòng)態(tài)規(guī)劃
第五章 存貯論(Inventory Theory)
§1 經(jīng)濟(jì)訂購(gòu)批量存貯模型
§2 經(jīng)濟(jì)生產(chǎn)批量模型
§3允許缺貨的 經(jīng)濟(jì)訂購(gòu)批量模型
§4允許缺貨的 經(jīng)濟(jì)生產(chǎn)批量模型
§5 經(jīng)濟(jì)訂購(gòu)批量折扣模型
§6需求為隨機(jī)的單一周期的存貯模型
§7需求為隨機(jī)變量的訂貨批量、再訂貨點(diǎn)模型
§8需求為隨機(jī)變量的定期檢查存貯量模型
§9物料需求計(jì)劃(MRP)與準(zhǔn)時(shí)化生產(chǎn)方式(JIT)簡(jiǎn)介
第五章 存貯論
存貯是緩解供應(yīng)與需求之間出現(xiàn)的供不應(yīng)求或供過(guò)于求等不協(xié)調(diào)情況的必要和有效的方法和措施。
但是，要存貯就需要資金和維護(hù)，存貯的費(fèi)用在企業(yè)經(jīng)營(yíng)的成本中占據(jù)非常大的部分。
存貯論主要解決存貯策略問(wèn)題，即如下兩個(gè)問(wèn)題：
1．補(bǔ)充存貯物資時(shí)，每次補(bǔ)充數(shù)量(Q)是多少？
2．應(yīng)該間隔多長(zhǎng)時(shí)間( T )來(lái)補(bǔ)充這些存貯物資？
建立不同的存貯模型來(lái)解決上面兩個(gè)問(wèn)題，如果模型中的需求率、生產(chǎn)率等一些數(shù)據(jù)皆為確定的數(shù)值時(shí)，存貯模型被稱(chēng)為確定性存貯摸型；如果模型中含有隨機(jī)變量則被稱(chēng)為隨機(jī)性存貯模型。
§1 經(jīng)濟(jì)訂購(gòu)批量存貯模型
經(jīng)濟(jì)訂購(gòu)批量存貯模型，又稱(chēng)不允許缺貨，生產(chǎn)時(shí)間很短存貯模型，是一種最基本的確定性存貯模型。在這種模型里，需求率即單位時(shí)間從存貯中取走物資的數(shù)量是常量或近似乎常量；當(dāng)存貯降為零時(shí)，可以立即得到補(bǔ)充并且所要補(bǔ)充的數(shù)量全部同時(shí)到位（包括生產(chǎn)時(shí)間很短的情況，我們可以把生產(chǎn)時(shí)間近似地看成零）。這種模型不允許缺貨，并要求單位存貯費(fèi)，每次訂購(gòu)費(fèi)，每次訂貨量都是常數(shù)，分別為一些確定的、不變的數(shù)值。
主要參數(shù)：
需求率 ： d
單位貨物單位時(shí)間的存貯費(fèi)： c1
每次訂購(gòu)費(fèi)： c3
每次訂貨量： Q
是一些確定的、不變的數(shù)值。

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

求極值得使總費(fèi)用最小的訂購(gòu)批量為

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

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

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

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


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

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


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







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


訂購(gòu)量為Q＊時(shí)的最大缺貨量


單位時(shí)間的最低總費(fèi)用


訂購(gòu)量為Q＊時(shí)的最大存貯量為


每個(gè)周期T所需時(shí)間

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






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



最優(yōu)缺貨量



單位時(shí)間最少的總費(fèi)用



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







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



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

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


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

Q < 50時(shí)，


50 ≤ Q < 100時(shí)，


100 ≤ Q時(shí)，

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




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

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


例5. 某報(bào)亭出售某種報(bào)紙，每售出一百?gòu)埧色@利15元，如果當(dāng)天不能售出，每一百?gòu)堎r20元。每日售出該報(bào)紙份數(shù)的概率P(d )根據(jù)以往經(jīng)驗(yàn)如下表所示。試問(wèn)報(bào)亭每日訂購(gòu)多少?gòu)堅(jiān)摲N報(bào)紙能使其賺錢(qián)的期望值最大。
§6 需求為隨機(jī)的單一周期存貯模型（4）
解：要使其賺錢(qián)的期望值最大，也就是使其因售不出報(bào)紙的損失和因缺貨失去銷(xiāo)售機(jī)會(huì)的損失的期望值之和為最小。已知 k = 15，h = 20，則有

另有



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

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


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



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


則由公式（12. 44）得

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

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

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

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


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

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

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

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

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

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

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

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

排隊(duì)的過(guò)程可表示為：





§1 排隊(duì)過(guò)程的組成部分(2)
考慮要點(diǎn)：

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

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

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

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















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

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

解：
局中人I為采購(gòu)員；局中人II為大自然，采購(gòu)員有三個(gè)策略，在秋季買(mǎi)10噸、15噸和20噸，分別記為1、2 、3，大自然也有三個(gè)策略，分別為較暖、正常和較冷，記為1、2、 3。
以冬季取暖用煤實(shí)際費(fèi)用，作為局中I采購(gòu)員的贏得，得到贏得矩陣如下：
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.矩陣對(duì)策的混合策略
設(shè)矩陣對(duì)策 G = { S1, S2, A }。當(dāng)
max min aij  min max aij
i j j i
時(shí)，不存在最優(yōu)純策略。
例：設(shè)一個(gè)贏得矩陣如下:
min
5 9 5
A = max 6 策略2
8 6 6 i

max 8 9
min 8 策略1
j

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

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

2)無(wú)論乙取何策略，甲的平均贏得應(yīng)不少于V:
對(duì)乙取1： 5X1’+ 8X2’ V
對(duì)乙取2： 9X1’+ 6X2’ V
注意 V>0,因?yàn)锳各元素為正。
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
返回原問(wèn)題： X1’= X1V= 1/3
X2’= X2V= 2/3
于是甲的最優(yōu)混合策略為：
以1/3的概率選1， 以2/3的概率選2，最優(yōu)值V=7.


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

優(yōu)超原則：
假設(shè)矩陣對(duì)策 G ={ S1, S2, A }
甲方贏得矩陣 A=[aij]mn
若存在兩行（列），s 行（列）的各元素均優(yōu)于 t 行（列）的元素，即
asjatj j=1,2 … n ( ais  ait i=1,2 … m )
稱(chēng)甲方策略s優(yōu)超于t ( s優(yōu)超于t)
3.矩陣對(duì)策的混合策略(續(xù))
優(yōu)超原則：當(dāng)局中人甲方的策略t被其它策略所優(yōu)超時(shí)，可在其贏得矩陣A中劃去第t行（同理，當(dāng)局中人乙方的策略t被其它策略所優(yōu)超時(shí)，可在矩陣A中劃去第t列）。
如此得到階數(shù)較小的贏得矩陣A’，其對(duì)應(yīng)的矩陣對(duì)策
G’= { S1, S2, A’} 與 G = { S1, S2, A }
等價(jià)，即解相同。
3.矩陣對(duì)策的混合策略(續(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.矩陣對(duì)策的混合策略(續(xù))
3.矩陣對(duì)策的混合策略(續(xù))
對(duì)A4計(jì)算，用線性規(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 。

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

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

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

再用貝葉斯公式計(jì)算


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

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

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

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

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



管理運(yùn)籌學(xué)(ppt)