管理運(yùn)籌學(xué)期末復(fù)習(xí)

01緒論

?運(yùn)籌學(xué)：為決策機(jī)構(gòu)在對其控制下業(yè)務(wù)活動進(jìn)行決策時，提供以數(shù)量化為基

礎(chǔ)的科學(xué)方法。

運(yùn)籌學(xué)是應(yīng)用分析、試驗、量化的方法，對管理系統(tǒng)中人力、物力、財力等

資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。

?運(yùn)籌學(xué)的工作步驟：

提出和形成問題；目標(biāo)、約束、可控變量，有關(guān)資料；建立模型；形象模型；

模擬模型；符號與數(shù)學(xué)模型；求解；解的檢驗；解的控制與調(diào)整；解的實施

?運(yùn)籌學(xué)研究的主要特點：科學(xué)性、實踐性、系統(tǒng)性、綜合性

?運(yùn)籌學(xué)一般結(jié)構(gòu)：優(yōu)化模型或者說，最優(yōu)化模型

02線性規(guī)劃

§1線性規(guī)劃模型的建立

一、線性規(guī)劃的概念

線性規(guī)劃模型就是目標(biāo)函數(shù)為線性函數(shù)，約束條件也是線性函數(shù)的最優(yōu)化模型。

二、線性規(guī)劃模型的建立

線性規(guī)劃模型包括三個部分：決策變量、目標(biāo)函數(shù)、約束條件

線性規(guī)劃的性質(zhì)：

①線性規(guī)劃模型是目標(biāo)函數(shù)為線性函數(shù)，約束條件也是線性函數(shù)的最優(yōu)化模型。

②沒有約束條件的目標(biāo)函數(shù)值是不存在的，趨向于無窮大或無窮小，所以現(xiàn)實

的模型必須包括對自變量取值的限制。

可行解：滿足所有約束條件的解

可行域：線性規(guī)劃問題可行解的集合

最優(yōu)解：使得目標(biāo)函數(shù)值最大（或最?。┑目尚薪?/p>

最優(yōu)值：此目標(biāo)函數(shù)稱為最優(yōu)目標(biāo)函數(shù)值

＞最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。

＞如果線性規(guī)劃問題有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解;

（一定可以在其頂點達(dá)到，但不一定只在其頂點達(dá)到，有時在兩頂點的連線

上得到，包括頂點）

唯一最優(yōu)解：只在其一個頂點達(dá)到

無窮多個最優(yōu)解：在其兩個頂點及其連線上達(dá)到

無界解：可行域無界。缺少必要的約束

無可行解（無解）：可行域為空集。約束條件自相矛盾導(dǎo)致的建模錯誤

＞線性規(guī)劃問題的可行域非空時,其可行域是凸集。

＞若在兩個頂點同時得到最優(yōu)解,則它們連線上的任意一點都是最優(yōu)解，線性

規(guī)劃問題存在無窮多解。

＞線性規(guī)劃可行域若非空、有界,則它一定有最優(yōu)解。

LP的可行域LP的解與最優(yōu)解

空集無可行解

有唯一最優(yōu)解

有最優(yōu)解一

祚空」無窮多個最優(yōu)解

無界解

可行域：空集m段（有界、無界）

最優(yōu)解：無解唯一最優(yōu)解無窮多最優(yōu)解無界解

三、線性規(guī)劃模型的一般形式

max(min)cxxx+c2x2+…+cnxn

司］±+…+環(huán)〃3<仁,=)4

%的+…+效〃4<(2-)4

s.t.

當(dāng)內(nèi)+…+%/〃<(之二)〃

Xij>0(7=1,???,/7,j=1,???,Ill)

§2線性規(guī)劃的求解

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

圖解法只適合于二維線性規(guī)劃問題

標(biāo)準(zhǔn)型：對“W”約束條件加非負(fù)松弛變量si,S2,S3

>當(dāng)約束方程左邊為“2”不等式時，則可在左邊減去一個非負(fù)剩余變量，變

成等式約束條件。

>當(dāng)右邊的常量Bj4時，兩邊都要乘以-1

>當(dāng)變量XK<0時，可令X.-XK',X/>0

>當(dāng)變量XK為無約束時,可令XK=XK：XK〃,其中，X/,X//>0

>令z』-z,把求minz問題改求為maxz,,即可得到該問題的標(biāo)準(zhǔn)型。

【例】MinZ=-Xi+2X2-3X3

ST

Xi+X2+X3<=7

Xi-X2+X3>=2

-3Xi+X2+2X3=5

X1,X2>=0,X3無約束

標(biāo)準(zhǔn)型：Maxz'=Xi-2X2+3(X4-X5)+0X6+0X7

st

Xi+X2+(X4-X5)+x6=7

Xi-X2+(X4-X5)-x7=2

-3Xi+X2+2(X4-X5)=5

Xi,X2,X4,X5zX6zX7>=0

二、線性規(guī)劃圖解法的敏感性分析

?“百分百定理”：對于所有變化的目標(biāo)函數(shù)決策變量系數(shù)，當(dāng)其所允許增加

百分比和允許減少百分比之和不超過100%時，最優(yōu)解不變。

?松弛量：對一個約束條件中，沒有使用完的資源或能力的大小稱為松

弛量

?對偶價格：在約束條件右邊常量增加一個單位而使最優(yōu)目標(biāo)函數(shù)得到改進(jìn)的

數(shù)量稱之為這個約束條件的對偶價格。

對偶價格只適用于約束條件的右端值變化較小的情況。若資源越來越多，右

端項的值也越來越大，其他的約束條件就有可能成為新的束縛條件，限制目

標(biāo)函數(shù)值的變大。

＞當(dāng)某約束條件中的松弛變量不為零時，約束條件的對偶價格為零。

＞某一約束條件的對偶價格只在某一范圍內(nèi)有效，當(dāng)這種約束條件的資源不斷

的獲得，使得其bi值不斷增大，由于其他約束條件的限制，使得這種資源用

不完，即其松弛變量不為零，導(dǎo)致其對偶價格為零。

＞對偶價格可以理解為對目標(biāo)函數(shù)的貢獻(xiàn)。如果對偶價格大于零，則其最優(yōu)目

標(biāo)函數(shù)值得到改進(jìn)。即求最大值時，變得更大；求最小值時，變得更小。

如果對偶價格小于零,則其最優(yōu)目標(biāo)函數(shù)值變壞。即求最大值時，變得小了；

求最小值時，變得大了。

如果對偶價格等于冬,則其最優(yōu)目標(biāo)函數(shù)值不變。

三、線性規(guī)劃的計算機(jī)解法【看書】

§3線性規(guī)劃建模案例

一、線性規(guī)劃應(yīng)用領(lǐng)域

二、一般線性規(guī)劃建模過程

三、建立線性規(guī)劃模型案例

L人力資源分配問題

4.投資問題

5.混合問題

靈敏度分析

03單純形法

基本可行解：可行域的頂點

初始基本可行解：第一個找到的可行域的頂點。

基本可行解：滿足非負(fù)條件的一個基本解。這樣的基叫可行基。

最優(yōu)性檢驗的工具：檢驗數(shù)（對于求最大目標(biāo)函數(shù)的問題中，檢驗數(shù)需要＜=0）

所有基變量的檢驗數(shù)=0

1.基本迭代

2.大M法

3.無窮多最優(yōu)解：對于某個最優(yōu)的基本可行解，如果存在某個非基變量的檢驗

數(shù)為零，則此線性規(guī)劃問題有無窮多最優(yōu)解。

4.無界解：

在某次迭代的單純形表中，如果存在一個大于零的檢驗數(shù)，并且該列的系數(shù)向量

的每個元素都小于或等于零，則此線性規(guī)劃問題為無界解

5.無解：

求線性規(guī)劃的最優(yōu)解里有人工變量大于0,則此線性規(guī)劃無可行解。

04對偶規(guī)劃

線性規(guī)劃的對偶理論：

>從另一個角度來思考同一個問題，將一個生產(chǎn)計劃問題轉(zhuǎn)化為資源定價問題:

沒有機(jī)會損失時的最低資源出售收入

影子價格/對偶價格：資源增加對總效益的影響：

是在系統(tǒng)具有一定數(shù)量資源的前提下，在系統(tǒng)達(dá)到最優(yōu)狀態(tài)時，對資源價格的一

種估計。

>對于有剩余的資源，影子價格等于零。

>對于已經(jīng)用盡的資源，影子價格一般大于零；在臨界的情況，資源沒有剩余，

影子價格也可能等于零。

>當(dāng)某種資源的市場價格低于影子價格時，企業(yè)應(yīng)該買進(jìn)該資源用于擴(kuò)大生產(chǎn);

而當(dāng)某種資源的市場價格高于影子價格時，企業(yè)應(yīng)該賣出資源獲得利潤。

對偶規(guī)劃的性質(zhì)

1、對稱性：對偶規(guī)劃的對偶為原規(guī)劃。

2、弱對偶定理：原規(guī)劃任意可行解的目標(biāo)函數(shù)值小于等于對偶規(guī)劃可行解的目

標(biāo)函數(shù)值。

3、對偶定理：若x*和y*分別是原規(guī)劃和對偶規(guī)劃的可行解，則x*和y*是最優(yōu)

解的充要條件是它們對應(yīng)的目標(biāo)函數(shù)值相等。

4、互補(bǔ)松弛定理：若x*和y*分別是原規(guī)劃和對偶規(guī)劃的最優(yōu)解，則原問題松弛

變量取值和相應(yīng)的對偶規(guī)劃變量取值乘積為0,對偶問題松弛變量取值和相應(yīng)的

原規(guī)劃變量取值乘積為o（注：其逆也成立）。

原問題（或?qū)ε紗栴}）對偶問題（或原1礴）

目標(biāo)函數(shù)max1目例數(shù)minv

'n個〃個,

>

亦號>0約束條件

又里

<0<

〔無約束

?個m個

<N°

約束條件,>變量

><0

無約束

?

會延以印比較LP與DLP結(jié)果

LP結(jié)果DLP結(jié)果

OBJECTIVEFlNCTIO、VALLEOBJECTIVEHNCTIONVALIE

1)27500.001)27500.00

VARIABLEVALUERFDrCEDCOST

VARIABLEVALIEREDICEDCOST

XI50.000000D.000000

Yl50.0000000.(KHW)00

X2250.000000D.000000

Y20.00000050.000000

ROWS?LACKORSURPLUSDl'AI.PRICE￥350.000(X)0O.(KMNMX)

2)OJHHHHM)

ROWSLACKORSIRPLV!

3)50.0000000.000000iDLALPRICES

2)0.000000-50.000000

4)0.00000()50.000000

3)O.(NMMMM)

原規(guī)劃與對偶規(guī)劃的結(jié)果有如此密切的關(guān)系！

因為它們的模理之間有密切關(guān)系。

2019/1/1021

例：LP例：DLP

maxz=2x14-4x2-3x3Min10yl-5y2+8y3

s.t.s.t.

xl-x2+x3<10yl-y2+3y3*>2

-xl+4x2-3x3=7

3x1充彳35可三-3

xlN匚—

x2g仁二Z一

餐由變量

x3是自由變量

y3<0

■對偶問題約束條件的系數(shù)矩陣是原問題約束條件的系數(shù)矩陣A的轉(zhuǎn)置AT

如,/孝對偶規(guī)劃的互補(bǔ)松弛定理示例

OBJECTIVEFUNCTIONVALUEOBJECTIVERJhCTIONVALUE

)27500.00I)27500.00

Q.OMOOI

aORSURPLUSDUALPRICES

50.00削

2019/1/10

對偶規(guī)劃的變換書寫題目再練習(xí)一下~

05運(yùn)輸問題

一、運(yùn)輸問題

1、產(chǎn)銷平衡問題

產(chǎn)銷平衡的運(yùn)輸問題可以用等式約束，也可以對供給用。，對需求用＞=O

2、產(chǎn)銷不平衡問題

（1）產(chǎn)大于銷問題（供過于求）

?建立假想銷地，假想銷地運(yùn)費(fèi)為0

?也可以不假設(shè)有倉庫，對供給用。，對需求用＞=

（2）銷大丁產(chǎn)問題（供不應(yīng)求）

?建立假想的產(chǎn)地

?也可以不設(shè)有假想產(chǎn)地，對供給用=,對需求用＜=

二、運(yùn)輸問題應(yīng)用

1、產(chǎn)銷不平衡的運(yùn)輸問題（盡量滿足需求）

銷地供應(yīng)

一區(qū)二區(qū)三區(qū)

運(yùn)費(fèi)單價狀

產(chǎn)地

A1.631.691.744000

B1.581.611.731500

3000/22000/

需求量1000

5001200

MIN1.63X11+1.69X12+1.74X13+1.58X21+1.61X22+1.73X23

ST

Xll+X12+X13=4000

X21+X22+X23=1500

Xll+X21<=3000

Xll+X21>=2500

X12+X22=1000

X13+X23<=2000

X13+X23>=1200

end

2、配置問題

（1）機(jī)器配置

（2）任務(wù)配置（要求完成時間最短）一一指派問題（0-1規(guī)劃）

（3）銷售人員與銷售區(qū)域配置

3、生產(chǎn)與存儲問題

4、轉(zhuǎn)運(yùn)問題（網(wǎng)絡(luò)流程問題）

運(yùn)輸網(wǎng)絡(luò)圖

（1）供銷平衡：對供給用<=,中轉(zhuǎn)點左右相等，需求用二

（2）供銷不平衡：

①供應(yīng)〉需求：發(fā)點的約束寫成“<="，不能寫“=”；收點寫成“二”或">=

但不能同時寫成

②供應(yīng)〈需求：發(fā)點的約束寫成“=”，收點寫成

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

一、整數(shù)規(guī)劃的性質(zhì)：

①整數(shù)規(guī)劃（IP）的可行解也是原線性規(guī)劃（LP）的可行解。

②若原線性規(guī)劃（LP）有最優(yōu)解，且解是整數(shù)，則它也是整數(shù)規(guī)劃（IP）的最

優(yōu)解。

③任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于

或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；

④任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于

或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。

二、整數(shù)規(guī)劃的計算機(jī)求解

LINDO中，在END之后說明

?0-1變量INT

對偶成本、遞減價格無意義

若所有10個變量都是0—1變量，可以用INT10

?一般整數(shù)GIN

若所有13個變量都是整數(shù)變量，可以用GIN13

注意：整數(shù)規(guī)劃求解后不作靈敏度分析

三、整數(shù)規(guī)劃應(yīng)用

1、選址問題

2、固定成本問題

＞固定費(fèi)用y為。-1變量：Xi＜=Myj（當(dāng)月＞0時，w必須為1,而不可能為

0）

3、批量定價問題（折扣問題不考）

4、指派問題

（1）每人只能從事一頃工作，每項工作只能一人從事，如何分配效率最高？

（2）每人只能從事一項工作，每項工作只能一人從事，如何分配，才能使最慢

完成工作的時間最短？

（3）每人只能從事一項工作，每項工作只能一人從事，如何分配，才能使最快

和最慢完成工作的時間之差最?。?/p>

注意：解整數(shù)規(guī)劃，可能得不到最優(yōu)解。

（4）每個人最多干兩項工作，每項工作最多兩人干，如何？

5、分布系統(tǒng)設(shè)計（生產(chǎn)布局問題）

例4【難點】

6、相互排斥的約束問題

例5【難點】

如：小班上課不超過50人；大班上課不超過100人。

若X為選課人數(shù)，設(shè)Y為0-1變量，Y=0小班上課，Y=1大班上課；如何表示?

X<=50或X<=100相互排斥，用以下約束表示：

X<=50+10000Y

X<=100+10000（l-Y）

46、折扣問題（見一補(bǔ)充例題）

■喝設(shè)一個公司為鼓勵批量購買,提出多購買可以獲得折扣，

原本定價為10元，件如果買1000以上則超過部分九折。如何

描述？

-假設(shè)購買量為限X,可以將購買量X分為兩個部分XI,X2,XI

為買夠1000的部分，X2為超過1000的部分。顯然當(dāng)XI<=1000

時，X2只能為0。為了表現(xiàn)這種關(guān)系，引入0—1變量Y,當(dāng)XI

<二1000時，即Y=0,（1）起作用，使X2=0,

■購買貨款：10X1+9X2,約束條件為：

-Xl<=1000....（1）

-Xl>=1000Y….（2）

■X2CMY

伊戈國有銀行例7.3.1

07圖與網(wǎng)絡(luò)

一、圖論簡介

1、無向圖的概念

無向圖：由點和邊構(gòu)成

度：與該點相鄰的邊數(shù)稱為“度”

奇點：度為奇數(shù)的點

偶點：度為偶數(shù)的點

定理：一個圖中奇點的個數(shù)一定為偶數(shù)。

圖中各點度的總和等于邊數(shù)的2倍。

鏈一一無向圖中的點和邊交錯相連的序列

圈一一起點與終點相同的鏈

連通圖一一對于圖中任意兩點，都有連接它們的鏈。

賦權(quán)圖一一邊（無向圖）或?。ㄓ邢驁D）有相應(yīng)的指標(biāo)（權(quán)重），例如距離、費(fèi)

用等，這樣的圖稱為賦權(quán)圖。無向圖邊上的指標(biāo)稱為權(quán)。

歐拉回路：

連通圖G中若存在一條道路（回路），過每邊一次且僅一次，當(dāng)且僅當(dāng)該圖無奇

點或只有兩個奇點。

2、有向圖的概念

有向圖：由點和弧構(gòu)成（“弧”：帶箭頭的連線）

路一一方向圖中的點和弧交錯相連的序列

回路一一起點與終點相同的路

無向圖是特殊的有向圖（每條邊轉(zhuǎn)化成兩條反向?。?/p>

網(wǎng)絡(luò)：有發(fā)點、收點、中間點的賦權(quán)有向圖，稱為網(wǎng)絡(luò)。

弧上的賦權(quán)數(shù)，為弧的容量

二、最小生成樹問題

樹：無圈，連通圖（邊數(shù)=點數(shù)-1）

1、避圈法

2、破圈法

三、最短路問題

1、“雙標(biāo)弓法”

2、線性規(guī)劃模型

①有向圖用0-1規(guī)劃求解

②無向圖用0-1規(guī)劃求解

minXd"

/ff

XxiJ=1，對于起點,

J

s￡.?￡xjj=i，對于終點，

Zx.-2y7=0,對于其他點憶

%為0T變量

四、最大流問題

1、最小截截量法

使起點和終點在截開的兩面

定理：最大流的流量等于最小截的截量。

2、線性規(guī)劃法

?守恒條件：

網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的總流出量等于收點的總流入量;

?流量可行條件：

①中間點的總流入量等于總流出量；

②每一條弧的流量應(yīng)小于等于弧的容量；

③每一條弧的流量應(yīng)大于等于零。

五、最小費(fèi)用最大流問題

1、先求出最大流，再求最小費(fèi)用。

目標(biāo)函數(shù)：Min總費(fèi)用

約束條件：發(fā)點總流出量;收點總流入量二求得的最大流

中間點總流入量;總流出量

0〈二每一條弧的流量。容量

2、線性規(guī)劃法

MAX100F-C

ST

F二發(fā)點總流出量=收點總流入量

C=總費(fèi)用

08統(tǒng)籌方法

一、車間作業(yè)計劃模型（排序問題）

1、一臺機(jī)器，N個零件

按照加工時間從少到多排出加工零件的順序，就能使各個零件的平均停留時訶為

最少。

2、兩臺機(jī)器，N個零件

從未安排的零件中，選取量短的加工時間的零件。若該時間是在車床上（第一臺

機(jī)器上），該零件排在最前面，若是在磨床上（第二臺機(jī)器上），該零件排在最

后面C

3、M臺機(jī)器，N個零件

類似于整數(shù)規(guī)劃

產(chǎn)品機(jī)器1（車床）機(jī)器2（磨床）

1XII15X2112

2X1220X2216

3X139X236

4X145X248

5X1511X2513

設(shè)xij表示機(jī)器i開始對零件j進(jìn)行加工的時間。

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

同一產(chǎn)品在不同機(jī)器上加工順序：

X21>=X11+15

X22>=X12+20

X23>=X13+9

X24>=X14+5

X25>=X15+11

不是加工產(chǎn)品1,就是加工產(chǎn)品2：

X11+15<=X12+MylorX12+20<=Xll+M(l-yl)

X11+15<=X13+My2orX13+9<=Xll+M(l-y2)

Z>=X11+15

Z>=X21+12

Z>=X25+13

二、統(tǒng)籌方法

1、計劃網(wǎng)絡(luò)圖

?路線：從起點到終點之間相連接的節(jié)點和弧組成的序列.

?畫網(wǎng)絡(luò)圖：

AOA(Activity-on-arc)：用弧表示活動

AON(Activity-on-node)：用點表示活動

注意：

①兩點之間只有一條弧;

②不能有缺口：除發(fā)點和收點外，其他各個點的前后都應(yīng)有弧連接。即從發(fā)點

經(jīng)過任何路線都可以到達(dá)收點，必要時可以添加虛工序。

③不能產(chǎn)生回路,否則將使組成的工序永遠(yuǎn)不能結(jié)束。

【練習(xí)】

2、關(guān)鍵路線法

關(guān)鍵路線法

?關(guān)鍵路線一定存在C

?關(guān)鍵路線可能一條，也可能多條。

?關(guān)鍵路線上的工序：最早開工時間=最晚開工時間，或者最早完工時間=最

晚完工時間。關(guān)鍵路線工序時差等于0。

?工序時差=最晚開始時間一最早開始時間=最晚完工時間一最早完工時間。

線性規(guī)劃方法：

(1)用弧求關(guān)鍵路線：

設(shè)fij為網(wǎng)絡(luò)中的工序，fij=o,l(0為非關(guān)鍵工序，1為關(guān)鍵工序)，最長路模型。

Max6fl2+7fl3+10f24+9f25+8f35+4f46+7f56+0f32

St

fl2+fl3=l

fl2+f32-f24-f25=0

fl3-f35-f32=0

f24-f46=0

f25+f35-f56=0

f46+f56=l

End

Int8

（2）用點求關(guān)鍵路線：（結(jié)果中凡是dualprice不等于零的是關(guān)鍵路線）

設(shè)Tj為第j點之前工序完成的最早時刻，T1=O,T6為工序完成所需的時間

MinT6

St

T2-Tl>=6

ROWSLACKORSURPLUSDUALPRICES

T3-Tl>=72)1.0000000.000000

3)0.000000-1.000000

T2-T3>=0

4)0.000000-1.000000

T4-T2>=105)0.0000000.000000

0.000000-1.000000

T5-T2>=96)

7)1.0000000.000000

T5-T3>=88)2.0000000.000000

T6-T4>=49)0.000000-1.000000

10)0.0000000.000000

T6-T5>=7

T1=O

End

對于AON網(wǎng)絡(luò)圖（參見上面AON圖）

MINT

ST

A2-A1>=6、-----

B2-B1>=7各項工作的時間約束

C2-Cl>=10______________________

D2-D1>=9>----一

E2-E1>=8

F2-F1>=4

G2-G1>=7)

Cl-A2>=0

Cl-B2>=0

Dl-A2>=0各項工作的緊前工序

Dl-B2>=0

El-B2>=0

Fl-C2>=0

Gl-D2>=0

Gl-E2>=0

T-F2>=0

T-G2>=0

END

3、工序時間不確定的關(guān)鍵路線

a;樂觀時間；b=悲觀時間；m;最可能時間

均值=（a+4m+b）/6（平均時間或期望時間）

方差:

b.=.(-b-—-a、

I6J

期望總工期=關(guān)鍵路線工序期望之和

平均所需完成時間的方差/=關(guān)鍵路線工序方差之和

【例】如果計算出期望總工期為15,<T2=1.O5,要求：計算培訓(xùn)組織工作16周

內(nèi)完成的概率。

T-E(T)I八一

LI=---------=----=0.976

。1.025

查正態(tài)分布表，可知概率①(4)=0.8355

4、網(wǎng)絡(luò)優(yōu)化

【難點】例a(word)

目標(biāo):趕工期增加的直接費(fèi)用最少

變量:設(shè)Tl,T2,T3,...,T8,表示該點前面工序

全部完成的最早時間，也是后續(xù)工序可以開始的時間.

I：序(i,j)提前完I：的時間為Yij

MTN120Y27+300Y23+400Y24+500Y25+230Y37+350Y46+400Y57+290Y67

ST

Tl=0

T2-Tl>=60-Y12正常時間-提前時間

T3-T2>=10-Y23

T4-T2>=20-Y24

T5-T2>=40-Y25

T5-T4>=0

T6-T4>=30-Y46

T7-T6>=25-Y67

T7-T2>=45-Y27

T7-T3>=18-Y37

T7-T5>=15-Y57

T8-T7>=35-Y78

T8<=150

Y12<=0

Y27<=15

Y23<=5

Y24<=10

Y25<=5

Y37<=8

Y46<=10

Y57<=5

Y67<=10

Y78<=0

END

09存儲論

一、經(jīng)濟(jì)叵批量存儲模型（不允許缺貨模型）

一年的總費(fèi)用二一年存儲費(fèi)+一年訂貨費(fèi)

_1八,D

最優(yōu)訂貨量：

D-總需求量；C3-每次訂貨費(fèi)；c】-每單位存儲費(fèi)。

?最優(yōu)訂購量（最大庫存量）與需求呈平方根關(guān)系。

?在經(jīng)濟(jì)訂貨批量的模型中，能使一年存儲費(fèi)與訂貨費(fèi)相等的訂貨量Q就是最

優(yōu)訂貨量Q*

一年存儲費(fèi)=二腎一年最優(yōu)總訂貨次數(shù)=1

每次最優(yōu)訂貨間隔時間=及

一年訂貨費(fèi)=俳。3=J與氣

%。

■最高存儲最=(p-J)r=(p-^)^-=(l-

最優(yōu)經(jīng)濟(jì)批量生產(chǎn)公式：—T~

■平均存儲最=3(1-十)。

4P忖芹

■一年存儲費(fèi)=--)01

2P每年的存儲費(fèi)與每年的生產(chǎn)準(zhǔn)備費(fèi)相等，為:

-?年的生產(chǎn)準(zhǔn)備費(fèi)=每年生產(chǎn)次數(shù)*缽次準(zhǔn)備費(fèi)=*

*w

IDc3(l--)<?!

■總費(fèi)用TC=L(l_4)0j+2c3

2PQ

二、經(jīng)濟(jì)較批量模型

C1-單位存儲費(fèi)(單位維持費(fèi))

C3每次生產(chǎn)準(zhǔn)備費(fèi)(配置費(fèi))

在時間t內(nèi)產(chǎn)量為Q,Q=pto

P?生產(chǎn)率，d?需求率

最高存儲量=(p-d)t

三、允進(jìn)缺貨的經(jīng)濟(jì)叵批量模型

一年的總費(fèi)用二一年存儲費(fèi)+一年訂貨費(fèi)+一年缺貨費(fèi)

cl為存儲快,

總費(fèi)川最小時(最優(yōu))訂貨量::c3為訂貨

費(fèi),c2為缺貨

?二2Z）q（G+G）

V平2

總觀川及小時或大缺貨出

四、經(jīng)濟(jì)訂購批量而模型

一年的總費(fèi)用二一年存儲費(fèi)+一年訂貨費(fèi)+一年才購的商品的貨款

TC=-Qc{+—Ct+De

213

10排隊論

一、單服務(wù)臺、泊松到達(dá)、負(fù)指數(shù)服務(wù)時間

設(shè)入為單位時間的平均到達(dá)率，U為單位時間的平均服務(wù)率

■A七、一位顧客在系統(tǒng)里一的平均逗留時間：

1、系統(tǒng)中沒有顧客的概率：-一

￡

2、平均排隊的顧客數(shù)：4'一/二、6、顧客到達(dá)系統(tǒng)必須排隊的概率。，務(wù)強(qiáng)度，或忙率）：

-㈤

2

3、在系統(tǒng)眼的平均顧客數(shù)：A

7rPw二一

Li一

7、系統(tǒng)班正好有n個顧客的概率：

4、一位顧客花在排隊上的平均時間：

Pn=（-YPo

注：公式3、4、5對任何一個排隊模型都成立

②兩個M\M\1:

把顧客分流，每個系統(tǒng)的服務(wù)率U不變，平均到達(dá)率人=單服務(wù)臺的到達(dá)率/2

二、多服務(wù)臺、泊松到達(dá)、負(fù)指數(shù)服務(wù)時間

M\M\C：

［一堆公式］

結(jié)論:排隊系統(tǒng)中使用M\M\2模型與使用兩個M\M\1模型，盡管服務(wù)臺數(shù)都是

2,服務(wù)率和顧客到達(dá)率一樣（對整個系統(tǒng)而言），結(jié)果卻不一樣。

M\M\2系統(tǒng)服務(wù)水平優(yōu)于M\M\1系統(tǒng)。

三、單服務(wù)臺、泊松到達(dá)、任意服務(wù)時間分布

M\G\1：

■44、一位顧客花在排隊上的平均時間:

1、系統(tǒng)中沒有顧客的概率：P°=l-一沙二土

qA

5、?位顧客在系統(tǒng)咽的平均逗用時間：

2、平均揖隊的順客數(shù)［二

%二心+L

Q2(1-A/A)

6、顧客到達(dá)系統(tǒng)必須排隊的概率：

3、在系統(tǒng)里的平均顧客數(shù)：2

L=L+-2

四、單服務(wù)臺、泊松到達(dá)、定長服務(wù)時間

M\D\1：

是M\G\1的一種特殊情況，M\G\1中各數(shù)量指標(biāo)的公式適用。

因服務(wù)時間是常數(shù)，均方差為。=0

平均排隊的顧客數(shù)：公式中。=0

222

R2CT+(2///)(4/〃)2

q-2(1-2/〃)-2(1-2///)

五、多服務(wù)臺、泊松到達(dá)、任意服務(wù)時間、損失制

M\G\c\c；如民航的訂票系統(tǒng)。

系統(tǒng)中有n個顧客的概率Pn

Pnc八---，

i-0

系統(tǒng)中的平均顧客數(shù)k

4=-0-^)

六、顧客來源有限制

M\M\l\8\m：顧客到達(dá)服從泊松分布，服務(wù)時間服從負(fù)指數(shù)分布，有一個服務(wù)

臺，隊長無限制，顧客總數(shù)為有限制的m個。

1、系統(tǒng)中沒有顧客的概率:3、在系統(tǒng)里的平均顧客數(shù):

?加J)”Ls=Lq+Q—P。)

2、平均排隊的顧客數(shù)：4、一位顧客花在排隊上的平均時間：

丁義+4八\W__________

Lq=〃i--^-Q一〃0)q2(/w-ZJ

5、一位顧客在系統(tǒng)里的平均逗留時間：

憶二印+J-

A

6、系統(tǒng)中有n個顧客的概率：

7W!/4、力cc<-

p=-------(-)紇，〃=0,12???，"7

n(??7-77)!/U

一些概念：

泊松分布:顧客到達(dá)獨立；顧客到達(dá)的時間隨機(jī)；適合于描述單位時間(或空司)

內(nèi)隨機(jī)事件發(fā)生的次數(shù)。

服務(wù)時間服仄”負(fù)指數(shù)概率分優(yōu)

服務(wù)時間。時間長度t的概率：夕(服務(wù)時間“1)=1-丁"

?U為單位時間里被服務(wù)完的平均顧客數(shù)

11決策分析

一、決策方法

1、定性決策

專家會議法；頭腦風(fēng)暴法；；Delphi法(匿名性、問卷設(shè)計、專家選擇、反饋性、

收斂性)；波士頓矩陣

2、定量決策

確定型決策分析；不確定型決策分析；風(fēng)險型決策分析

二、不確定決策：

1、悲觀準(zhǔn)則(最小最大準(zhǔn)則)：分析各最壞的結(jié)果，從中找出最好的結(jié)果。

——從最小中取最大

2、樂觀準(zhǔn)則(最大最大準(zhǔn)則)：爭取好中更好。

3、等可能性準(zhǔn)則：各種概率=1/事件數(shù)(1/N),計算各方案的期望收益，選擇期

望收益值最大的。

需求大寓求小期里他

大批求S130-612

中批最S220-29

小批最S31057.5

七(S1)=30x0.5+(-6)x0.5=12

E(S2)=20x0.5+(-2)x0.5=9

E(S3)=10x0.5+5x0.5=7.5

4、折中準(zhǔn)則：中和悲觀準(zhǔn)則和樂觀準(zhǔn)則，根據(jù)樂觀系數(shù)計算各方案的期望收益.

折中準(zhǔn)則:樂觀準(zhǔn)則和悲觀準(zhǔn)則之間進(jìn)行折衷,

取一個樂觀系數(shù)。例如I：取樂觀系數(shù)a=O.6。

標(biāo)準(zhǔn)收益值=amax(si)+(l-a)min(si)

需求大需求小折衷標(biāo)準(zhǔn)收益

大批量S130-615.6

中批量S220-211.2

小批中S31058

5、后悔值準(zhǔn)則(最小機(jī)會損失準(zhǔn)則)

’與每種自然狀態(tài)卜最佳收益之間的差稱為后悔值，使最大后

悔值最小。

需求大需求小后悔值準(zhǔn)則

大批量30-6同時用悲觀

中批量

20-2L準(zhǔn)則,

小批量105__匕//

后悔值需求大需求小

11)min]

大批量011

中批量107FToT

小批量20020

三、風(fēng)險型決策

(一)最大可能收益決策準(zhǔn)則

選擇一個發(fā)生概率最大的自然狀況進(jìn)行決策，而對于其它狀況不再考慮。

自N1(需求大)N2(需求小)

max

P(Nl)=0.25P(N2)=0.7^

大批量生產(chǎn)(S1)30-6-6

中批量生產(chǎn)(S2)20-2-2

小批量生產(chǎn)(S3)105■

(二)期望值決策準(zhǔn)則

1、方案選擇

自N1(需求大)N2(需求小)

效益值、我率--

E(Si)

P(Nl)=0.4P(N2)=0.6

大批量生產(chǎn)＜si)30-6Q-max

中批量生產(chǎn)(S2)20-26.8

小批量生產(chǎn)(S3)1057.0

石⑹=30x0.4+(-6)x0.6=8.4

￡(S)=20X0.4+(-2)X06=6.8

2所以,選擇S1

￡(53)=10x0.4+5xC.6=7.0

2、敏感性分析：

在期望值分析中，得出的最佳方案往往是在一定的風(fēng)險承擔(dān)的前提下的。

設(shè)：N1發(fā)生的概率為p,則N2發(fā)生的概率為1-p

爾SJ=30xp+(-6)x(1-p)=36p-6

E(S)=20xp+(-2)x(1-p)=22p-2

夕(S3)=10xp+(5)x(1-p)=5p+5

當(dāng)比線E(S3)=5p+5

與白線E(Sl)=36p-6

相等時，可求出

P=Q.3548,——E(S)

P=O.3548為轉(zhuǎn)折

概率實際中可以根

據(jù)估計概率的值,決

定最優(yōu)方案.

E(S3)=5p+5

3、全情報價值(EVPI)分析

EVPI(全情報價值)=全情報價值期望收益一沒有全情報的期望收益

-如：上例中根據(jù)期望值準(zhǔn)則，按照各種自然狀態(tài)

卜各方案的收益但，選擇S1作為最優(yōu)方案，此時

期望侑稱為沒有全情報的期望收益。

EVW0PI：

E(S；)=30X0.4+(-6)X0.6=8.4

■全情報價值期望收益：

EVWPI=30*0.4+5*0.6=15

EVPI(全情報價值)=15-8.4=6.6(萬元)

(三)期望效用決策準(zhǔn)則

(四)貝葉斯決策準(zhǔn)則

(五)風(fēng)險決策方法：決策樹法

決策樹

4.80N1,需求量大，9(Nl)=0.3

N2,需求量小，P(N2)=0.7

△-6

4.6N1,需求量大，P(Nl)=0.3

△20

決策

N2,■量小，P(N2)=0.7

△-2

6.5N1,都量A：,P(Nl)=0.3

△10

N2,幟量小，P(N2)=0.7

△5

決策：選擇方案3,小批量生產(chǎn)

概率修正:

-例：某鉆井大隊在某地區(qū)進(jìn)行石油勘探，主觀估計地區(qū)有油的械試驗好的概率P(F)：(等于各種自然狀態(tài)的概率

概率P(0)R.5,無油的概率P(D)R.5.根據(jù)經(jīng)驗，凡是行油地

乘以各種情況下試驗好的概率之和一全概公式)

區(qū)做試驗結(jié)果好的概率為以E◎型，做試驗結(jié)果不好的概率

為P(U/0)=0.1?凡是無油地M做試驗結(jié)果好的概率為P(F)=P(0)*P(F/0)+P(D)*P(F/D)=0.5X0.940.5X0.2=0.55

P(F/D)=0.2,做試驗結(jié)果不好的概率為P(U/D)=0.8°同在該即：有油的收率乘以有油的情況下試顫的據(jù)率，加上無油的根率乘以無

地區(qū)做試驗后，有油和無油的概率各為多少？油的情況下遮好的螯率。

解：分析：本題“有油”用“0”我小，“無油”用"D”衣小；-同理，做試驗不好的概率：

“試驗好”用“曠表示「試驗不好”用“IT表示.因此，P(U)=P(0)*P(U/0)+P(D)*P(U/D)=0.5X0.1+0.5X0.8=0.45

本題是求：P(0/F)、P(D/F);P(0/U)、P(D/U)：而

即：有油的K率乘以有油的情況下述坯比捌K率，加上無油的嵌率乘以

無油的情況下靖丕好的戳率.

尸(。)?尸(尸/。)

P(O/F)=

P(F)

必索先求：ftiit

I利用貝葉斯公式計算各第件的后驗概率：

.1)做試收好的條件日j油的概率：

.P(O/F)=P(O)P(F/O)/P(F)=0.45/0.55=9/11

-2)做試驗好的條件卜無油的概率：

?P(D/F)=P(D)P(F/D)/P(F)=0.1/0.55=2/11

?3)做試監(jiān)不好的條件下有油的概率：

.P(O/U)=P(O)P(U/O)/P(U)=0.05/0.45=1/9

-4)做試已不好的條件下無油的概率：

?P(D/U)=P(D)P(U/D)/P(U)=0.45/0.45=8/9

12層次分析

一、層次分析法的概念

依據(jù)序標(biāo)度，將系統(tǒng)因素按支配關(guān)系分組以形成有序的遞階層次結(jié)構(gòu)，通過

兩兩比較判斷的方式確定每一層次中因素的相對重要性，然后在遞階層次結(jié)構(gòu)內(nèi)

進(jìn)行合成以得到?jīng)Q策因素相對于目標(biāo)重要性的總順序，從而為決策提供確定性的

判據(jù)。

1、層次結(jié)構(gòu)：

(1)目標(biāo)層(A)；

(2)準(zhǔn)則層(C)；

(3)方案層(P).

2、本質(zhì)上是一種決策思維方法，整個過程體現(xiàn)了人的決策思維的基本特征一一

即分解、判斷與綜合，便于決策者之間彼此溝通，是一種十分有效的系統(tǒng)分析方

法。

3、即采用具有適應(yīng)環(huán)境變化的靈活性的“相對標(biāo)度”，同時又充分利用了專家的

經(jīng)驗和判斷，并能對其誤差作出估計，能比較好地解決管理決策系統(tǒng)中的問題。

4、缺點就是對于目標(biāo)準(zhǔn)則有時難以保證互斥性和完備性。

二、層次分析步驟

三、案例分析

13預(yù)測

一、定性方法

Delphi法；專家判斷法；遠(yuǎn)景方案論述法；直觀法

二、定量方法

(一)時間序列方法

1、確定型方法

(1)平滑法

WeekGasSales移動平均預(yù)測值預(yù)測誤差覆測誤差的平方

117

WeekGasSales221

117319

22117+21+19”42319416

19

3351821-39

2361620-416

18

K+X+X=21+19+23=2]7201911

16

8181800

2033

1892218416

2210202000

1020FJo+%+&_20+15+22-19111520-525

1512221939

1133

12