第8章離散模型

1、第八章第八章 離散模型離散模型8.1 層次分析模型層次分析模型8.2 循環(huán)比賽的名次循環(huán)比賽的名次y離散模型離散模型 離散模型：差分方程（第離散模型：差分方程（第7 7章）、章）、整數(shù)規(guī)劃（第整數(shù)規(guī)劃（第4 4章）、圖論、對策章）、圖論、對策論、網絡流、論、網絡流、 分析社會經濟系統(tǒng)的有力工具分析社會經濟系統(tǒng)的有力工具 只用到代數(shù)、集合及圖論（少許）只用到代數(shù)、集合及圖論（少許）的知識的知識8.1 層次分析模型層次分析模型背背景景 日常工作、生活中的決策問題日常工作、生活中的決策問題 涉及經濟、社會等方面的因素涉及經濟、社會等方面的因素 作比較判斷時人的主觀選擇起相當作比較判斷時人的主觀選擇起

2、相當大的作用，各因素的重要性難以量化大的作用，各因素的重要性難以量化 Saaty于于1970年代提出層次分析法年代提出層次分析法 AHP (Analytic Hierarchy Process) AHP一種一種定性與定量相結合的、定性與定量相結合的、系統(tǒng)化、層次化系統(tǒng)化、層次化的分析方法的分析方法目標層目標層O(選擇旅游地選擇旅游地)P2黃山黃山P1桂林桂林P3北戴河北戴河準則層準則層方案層方案層C3居住居住C1景色景色C2費用費用C4飲食飲食C5旅途旅途一一. . 層次分析法的基本步驟層次分析法的基本步驟例例. . 選擇旅游地選擇旅游地如何在如何在3 3個目的地中按照景色、個目的地中按照景色

3、、費用、居住條件等因素選擇費用、居住條件等因素選擇. .“選擇旅游地選擇旅游地”思維過程的歸思維過程的歸納納 將決策問題分為將決策問題分為3個層次：目標層個層次：目標層O，準則層，準則層C，方案層方案層P；每層有若干元素，；每層有若干元素， 各層元素間的關系各層元素間的關系用相連的直線表示。用相連的直線表示。 通過相互比較確定各準則對目標的權重，及各方通過相互比較確定各準則對目標的權重，及各方案對每一準則的權重。案對每一準則的權重。 將上述兩組權重進行綜合，確定各方案對目標的將上述兩組權重進行綜合，確定各方案對目標的權重。權重。層次分析法將定性分析與定量分析結合起來層次分析法將定性分析與定量分

4、析結合起來完成以上步驟，給出決策問題的定量結果。完成以上步驟，給出決策問題的定量結果。1135/13/11125/13/13/12/117/14/1557123342/11AijjiijnnijaaaaA1, 0,)(層次分析法的基本步驟層次分析法的基本步驟一一.計算成對比計算成對比較陣和權向量較陣和權向量 元素之間兩兩對比，對比采用相對尺度元素之間兩兩對比，對比采用相對尺度 設要比較各準則設要比較各準則C1,C2, , Cn對目標對目標O的重要性的重要性ijjiaCC:A成對比較陣成對比較陣A是正互反陣是正互反陣要由要由A確定確定C1, , Cn對對O的權向量的權向量選選擇擇旅旅游游地地nn

5、nnnnwwwwwwwwwwwwwwwwwwA21222121211171242/11A成對比較的不一致情況成對比較的不一致情況):(2/ 12112CCa ):(43113CCa ):(83223CCa 一致比較一致比較不一致不一致允許不一致，但要確定不一致的允許范圍允許不一致，但要確定不一致的允許范圍考察完全一致的情況考察完全一致的情況nwwwW,) 1(21jiijwwa/令權向量),(21TnwwwwwAwnnnnnnwwwwwwwwwwwwwwwwwwA212221212111成對比較完全一致的情況成對比較完全一致的情況nkjiaaaikjkij, 2 , 1,滿足滿足的正互反陣的正

6、互反陣A稱稱一致陣一致陣，如，如 A的秩為的秩為1，A的唯一非零特征根為的唯一非零特征根為n A的任一列向量是對應于的任一列向量是對應于n 的特征向量的特征向量 A的歸一化特征向量可作為權向量的歸一化特征向量可作為權向量對于不一致對于不一致( (但在允許范圍內但在允許范圍內) )的成對的成對比較陣比較陣A，建議用對應于最大特征根，建議用對應于最大特征根 的特征向量作為權向量的特征向量作為權向量w ，即，即一致陣一致陣性質性質2 4 6 8比較尺度比較尺度aij Saaty等人提出等人提出19尺度尺度aij 取值取值1,2, , 9及其互反數(shù)及其互反數(shù)1,1/2, , 1/9尺度尺度 1 3 5

7、 7 9 ija相同相同 稍強稍強 強強 明顯強明顯強 絕對強絕對強的重要性jiCC :jiCC :aij = 1,1/2, ,1/9的重要性與上面相反的重要性與上面相反 心理學家認為成對比較的因素不宜超過心理學家認為成對比較的因素不宜超過9個個 用用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等等27種比較尺度對若干實例構造成對比較陣，種比較尺度對若干實例構造成對比較陣，算出權向量，與實際對比發(fā)現(xiàn)，算出權向量，與實際對比發(fā)現(xiàn)， 19尺度較優(yōu)。尺度較優(yōu)。 便于定性到定量的轉化：便于定性到定量的轉化：二二.一致性檢驗一致性檢驗對對A確定不一

8、致的允許范圍確定不一致的允許范圍已知：已知：n 階一致陣的唯一非零特征根為階一致陣的唯一非零特征根為n可證：可證：n 階正互反陣最大特征根階正互反陣最大特征根 n, 且且 =n時為一致陣時為一致陣1nnCI定義一致性指標定義一致性指標:CI 越大，不一致越嚴重越大，不一致越嚴重RI0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51 n1 234567891110為衡量為衡量CI 的大小，引入的大小，引入隨機一致性指標隨機一致性指標 RI隨機模隨機模擬得到擬得到aij , 形成形成A，計算，計算CI 即得即得RI。定義一致性比率定義一致性比率 CR

9、= CI/RI 當當CR0.1時，通過一致性檢驗時，通過一致性檢驗Saaty的結果如下的結果如下“選擇旅游地選擇旅游地”中中準則層對目標的權準則層對目標的權向量及一致性檢驗向量及一致性檢驗1135/13/11125/13/13/12/117/14/1557123342/11A準則層對目標的準則層對目標的成對比較陣成對比較陣最大特征根最大特征根 =5.073權向量權向量( (特征向量特征向量) )w =(0.263,0.475,0.055,0.090,0.110)T018.0155073.5CI一致性指標一致性指標隨機一致性指標隨機一致性指標 RI=1.12 (查表查表)一致性比率一致性比率CR

10、=0.018/1.12=0.0163)個頂點的雙向連通競賽圖，存在個頂點的雙向連通競賽圖，存在正整數(shù)正整數(shù)r，使鄰接矩陣，使鄰接矩陣A 滿足滿足Ar 0，A稱稱素陣素陣seAkkklim 素陣素陣A的最大特征根為正單的最大特征根為正單根根 ，對應正特征向量，對應正特征向量s，且，且eAAsskkk ) 1()(0001100011000110A排名為排名為1，2，4，3sskk)(,)(歸一化后Ts)230. 0 ,167. 0 ,280. 0 ,323. 0(, 4 . 1用用s排名排名1234(4)1, 2, 3, 4?00010010010011000000101011100011101

11、0ATTTTssss)16,25,21,32,28,38(,)9 ,12,7 ,16,10,15()3 , 4, 3 , 9 , 5 , 8(,)1 , 2, 2, 3 , 3 , 4()4()3()2()1(1234566支球隊比賽結果支球隊比賽結果Ts)104. 0 ,150. 0 ,113. 0 ,231. 0 ,164. 0 ,238. 0(,232. 2排名次序為排名次序為1，3， 2，5，4，6第九章第九章 概率模型概率模型9.1 傳送系統(tǒng)的效率傳送系統(tǒng)的效率9.2 報童的訣竅報童的訣竅9.3 隨機存貯策略隨機存貯策略確定性因素和隨機性因素確定性因素和隨機性因素隨機因素可以忽略隨機

12、因素可以忽略隨機因素影響可以簡單隨機因素影響可以簡單地以平均值的作用出現(xiàn)地以平均值的作用出現(xiàn)隨機因素影響必須考慮隨機因素影響必須考慮概率模型概率模型統(tǒng)計回歸模型統(tǒng)計回歸模型馬氏鏈模型馬氏鏈模型隨機模型隨機模型確定性模型確定性模型隨機性模型隨機性模型傳送帶傳送帶掛鉤掛鉤產品產品工作臺工作臺工人將生產出的產品掛在經過他上方的空鉤上運走，若工工人將生產出的產品掛在經過他上方的空鉤上運走，若工作臺數(shù)固定，掛鉤數(shù)量越多，傳送帶運走的產品越多。作臺數(shù)固定，掛鉤數(shù)量越多，傳送帶運走的產品越多。背背景景在生產進入穩(wěn)態(tài)后，給出衡量傳送帶效在生產進入穩(wěn)態(tài)后，給出衡量傳送帶效率的指標，研究提高率的指標，研究提高傳送

13、帶效率傳送帶效率的途徑的途徑9.1 傳送系統(tǒng)的效率傳送系統(tǒng)的效率問題分析問題分析 進入穩(wěn)態(tài)后為保證生產系統(tǒng)的周期性運轉，應進入穩(wěn)態(tài)后為保證生產系統(tǒng)的周期性運轉，應假定工人們的假定工人們的生產周期相同生產周期相同，即生產一件產品的，即生產一件產品的時間相同。假設每人作完一件產品后，要么恰有時間相同。假設每人作完一件產品后，要么恰有空鉤經過他的工作臺，使他可將產品掛上運走，空鉤經過他的工作臺，使他可將產品掛上運走，要么沒有空鉤經過，迫使他放下這件產品并立即要么沒有空鉤經過，迫使他放下這件產品并立即投入下件產品的生產。投入下件產品的生產。 可以用一個周期內傳送帶運走的產品數(shù)占產品可以用一個周期內傳送

14、帶運走的產品數(shù)占產品總數(shù)的總數(shù)的比例比例，作為衡量傳送帶效率的數(shù)量指標。，作為衡量傳送帶效率的數(shù)量指標。 工人們生產周期雖然相同，但穩(wěn)態(tài)下每人生產工人們生產周期雖然相同，但穩(wěn)態(tài)下每人生產完一件產品的時刻不會一致，可以認為是隨機的，完一件產品的時刻不會一致，可以認為是隨機的，并且在一個周期內并且在一個周期內任一時刻的可能性相同任一時刻的可能性相同。模型假設模型假設1）n個工作臺個工作臺均勻排列，均勻排列，n個工人生產相互獨立，個工人生產相互獨立，生產周期是常數(shù)；生產周期是常數(shù)；2）生產進入穩(wěn)態(tài)，每人生產完一件產品的時刻在）生產進入穩(wěn)態(tài)，每人生產完一件產品的時刻在一個周期內是一個周期內是等可能等可

15、能的；的；3）一周期內）一周期內m個均勻排列的掛鉤個均勻排列的掛鉤通過每一工作臺通過每一工作臺的上方，到達第一個工作臺的掛鉤都是空的；的上方，到達第一個工作臺的掛鉤都是空的；4）每人在生產完一件產品時都）每人在生產完一件產品時都能且只能觸到一只能且只能觸到一只掛鉤掛鉤，若這只掛鉤是空的，則可將產品掛上運走；，若這只掛鉤是空的，則可將產品掛上運走；若該鉤非空，則這件產品被放下，退出運送系統(tǒng)。若該鉤非空，則這件產品被放下，退出運送系統(tǒng)。模型建立模型建立 定義定義傳送帶效率傳送帶效率為一周期內運走的產品數(shù)（記作為一周期內運走的產品數(shù)（記作s,待定）與生產總數(shù)待定）與生產總數(shù) n（已知）之比，記作（已

16、知）之比，記作 D=s /n 若求出一周期內每只掛鉤非空的概率若求出一周期內每只掛鉤非空的概率p，則，則 s=mp為確定為確定s s，從，從工人工人考慮還是從考慮還是從掛鉤掛鉤考慮，哪個方便？考慮，哪個方便？ 設每只掛鉤為空的概率為設每只掛鉤為空的概率為q，則，則 p=1-q如如何何求求概概率率 設每只掛鉤不被一工人觸到的概率為設每只掛鉤不被一工人觸到的概率為r，則，則 q=rn 設每只掛鉤被一工人觸到的概率為設每只掛鉤被一工人觸到的概率為u，則，則 r=1-uu=1/mp=1-(1-1/m)nD=m1-(1-1/m)n/n一周期內有一周期內有m個掛鉤通過每一工作臺的上方個掛鉤通過每一工作臺的

17、上方模型解釋模型解釋若若(一周期運行的一周期運行的)掛鉤數(shù)掛鉤數(shù)m遠大于工作臺數(shù)遠大于工作臺數(shù)n, 則則)2)1(1(12mnnmnnmD 傳送帶效率傳送帶效率(一周期內運走一周期內運走產品數(shù)與生產總數(shù)之比）產品數(shù)與生產總數(shù)之比）)11(1nmnmD定義定義E=1-D (一周期內未運走產品數(shù)與生產總數(shù)之比）一周期內未運走產品數(shù)與生產總數(shù)之比）提高效率提高效率的途徑：的途徑： 增加增加m 習題習題1當當n遠大于遠大于1時時, E n/2m E與與n成正比，與成正比，與m成反比成反比若若n=10, m=40, D 87.5% (89.4%)mn2119.2 報童的訣竅報童的訣竅問問題題報童售報：報

18、童售報： a (零售價零售價) b(購進價購進價) c(退回價退回價)售出一份賺售出一份賺 a-b；退回一份賠；退回一份賠 b-c 每天購進多少份可使收入最大？每天購進多少份可使收入最大？分分析析購進太多購進太多賣不完退回賣不完退回賠錢賠錢購進太少購進太少不夠銷售不夠銷售賺錢少賺錢少應根據(jù)需求確定購進量應根據(jù)需求確定購進量每天需求量是隨機的每天需求量是隨機的優(yōu)化問題的目標函數(shù)應是長期的日平均收入優(yōu)化問題的目標函數(shù)應是長期的日平均收入每天收入是隨機的每天收入是隨機的存在一個合存在一個合適的購進量適的購進量等于每天收入的期望等于每天收入的期望建建模模 設每天購進設每天購進 n 份，份，日平均收入為

19、日平均收入為 G(n)調查需求量的隨機規(guī)律調查需求量的隨機規(guī)律每天每天需求量為需求量為 r 的概率的概率 f(r), r=0,1,2準準備備)()(rncbrnrbarnr賠退回賺售出nbannr)( 賺售出nrnrrnfbarfrncbrbanG01)()()()()()(求求 n 使使 G(n) 最大最大 已知售出一份賺已知售出一份賺 a-b；退回一份賠；退回一份賠 b-cnndrrnpbadrrprncbrbanG0)()()()()()(dndG求解求解將將r視為連續(xù)變量視為連續(xù)變量概率密度）()()(rprf0dndGcbbadrrpdrrpnn)()(0nndrrpbadrrpcb

20、0)()()()(ndrrpbannpba)()()()(ndrrpcbnnpba0)()()()(cbbadrrpdrrpnn)()(0結果解釋結果解釋nnPdrrpPdrrp201)(,)(nP1P2cbbaPP21取取n使使 a-b 售出一份賺的錢售出一份賺的錢 b-c 退回一份賠的錢退回一份賠的錢ncbnba)(,)(0rp9.3 隨機存貯策略隨機存貯策略問問題題以周為時間單位；一周的商品銷售量為隨機；以周為時間單位；一周的商品銷售量為隨機；周末根據(jù)庫存決定是否訂貨，供下周銷售。周末根據(jù)庫存決定是否訂貨，供下周銷售。（s, S) 存貯策略存貯策略制訂下界制訂下界s, 上界上界S，當周末

21、庫存小于，當周末庫存小于s 時訂貨，時訂貨，使下周初的庫存達到使下周初的庫存達到S; 否則，不訂貨。否則，不訂貨?？紤]訂貨費、存貯費、缺貨費、購進費，制訂考慮訂貨費、存貯費、缺貨費、購進費，制訂（s, S) 存貯策略存貯策略, ,使使( (平均意義下平均意義下) )總費用最小總費用最小模型假設模型假設 每次訂貨費每次訂貨費c0, 每件商品購進價每件商品購進價c1,每件商品每件商品一周貯存費一周貯存費c2,每件商品缺貨損失費每件商品缺貨損失費c3 ,c3 相當相當于售出價，所以于售出價，所以c1c3 每周銷售量每周銷售量 r 隨機、連續(xù)，概率密度隨機、連續(xù)，概率密度 p(r) 周末庫存量周末庫存

22、量x, 訂貨量訂貨量 u, 周初庫存量周初庫存量 x+u 一周的銷售是集中在周初進行的，即每周一周的銷售是集中在周初進行的，即每周貯存量按貯存量按 x+u-r 計計 ，一周內不隨時間而改變。，一周內不隨時間而改變。（可考慮修改此假設）（可考慮修改此假設）建模與求解建模與求解（s, S) 存貯策略存貯策略0usx確定確定(s, S), 使目標函數(shù)使目標函數(shù)每周總費用的期望值最每周總費用的期望值最小，即長期經營中每周總費用的平均值小，即長期經營中每周總費用的平均值Suxusx , 0s 訂貨點，訂貨點， S 訂貨值訂貨值0)(0),()(10uxLuuxLuccuJxxdrrpxrcdrrprxcxL032)()()()()(平均平均費用費用 訂貨費訂貨費c0,