1、n狹義的管文科學：數理方法制定管理決策狹義的管文科學：數理方法制定管理決策 n Management Science = Operations research n (MS=OR) n 決策制定主體、環境、過程決策制定主體、環境、過程n 定量分析數學、概率、統計定量分析數學、概率、統計n 運籌方法問題、建模、處理運籌方法問題、建模、處理 n 定性分析的方法定性分析的方法n 德爾菲方法德爾菲方法n 小組討論小組討論n n 定量模型的運用定量模型的運用n 運籌模型運籌模型n 管文科學的方法論管文科學的方法論運籌方法處理典型管理問題運籌方法處理典型管理問題解決方法解決方法典型的辦法典型的辦法 財務模

2、型財務模型 線性規劃線性規劃 目標規劃目標規劃 預預 測測 網絡分析網絡分析 決策分析決策分析 庫存模型庫存模型 概率統計概率統計 排隊模擬排隊模擬盈虧平衡與經營安全分析盈虧平衡與經營安全分析在線性目標和約束條件下取得最優結果在線性目標和約束條件下取得最優結果在多個相對立的目標下尋得合理結果在多個相對立的目標下尋得合理結果設計時間序列，或找到因果關系設計時間序列，或找到因果關系用各種活動和事件的網絡排列來說明項目計劃用各種活動和事件的網絡排列來說明項目計劃風險決策與不確定決策的基本方法風險決策與不確定決策的基本方法尋求使庫存成本降至最低的存儲策略尋求使庫存成本降至最低的存儲策略數學期望與概率分

3、布數學期望與概率分布分析等待的隊列分析等待的隊列, ,模擬合理作業時間和資源利用模擬合理作業時間和資源利用第三章第三章 線性規劃模型線性規劃模型n決策變量本身能否有限制條決策變量本身能否有限制條件？件？第三章第三章 線性規劃模型線性規劃模型nnxcxcxcz 2211max(min)mnmn22m11m2nn22221211nn1212111b).(xaxaxab).(xaxaxab).(xaxaxa. t . s第三章第三章 線性規劃模型線性規劃模型nn一切參數一切參數a、b、c都應是確定值都應是確定值n決策變量的非負性決策變量的非負性第三章第三章 線性規劃模型線性規劃模型 Max z =

4、X1+3X2 s.t. X1+ X26 -X1+2X28 X1 , X20z=0z=3z=6z=9z=12z=15.30 1 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2 -1654321x1x2目的函數等值線目的函數等值線Z = X1+3X2可行域可行域(4/3,14/3)第三章第三章 線性規劃模型線性規劃模型n對偶問題與影子價錢對偶問題與影子價錢n 定義：定義： 設以下線性規劃問題設以下線性規劃問題n MAX Z = CTXn s.t. AXb X0n 為原始問題，那么稱以下問題為原始問題，那么稱以下問題n MIN W = bTYn s.t. ATYC Y0n 為原始問題的對

5、偶問題，最優為原始問題的對偶問題，最優值值Y為影子價錢為影子價錢 第三章第三章 線性規劃模型線性規劃模型n對偶問題與原始問題的關系目標極大化問題極大化問題 Cj（max Z）極小化問題極小化問題bi（min W）目標變變量量nxj0 aTijyicj約約束束nxj無約束無約束 aTijyi=cjxj0 aTijyicj約約束束m aijxjbiyi0變變量量m aijxj=biyi無約束無約束 aijxjbiyi0么么 X*,Y*為最優解的充分必要條件是為最優解的充分必要條件是Y*XL=0和和YSX*=0。第三章第三章 線性規劃模型線性規劃模型原問題規范型：原問題規范型：Max Z= CXAX

6、 + XL= bX,XL0對偶問題規范型：對偶問題規范型：Min W= YbYA - YS= CY,YS0第三章第三章 線性規劃模型線性規劃模型原問題和對偶問題的互補松松弛關系：原問題和對偶問題的互補松松弛關系：第三章第三章 線性規劃模型線性規劃模型對偶問題求解舉例：對偶問題求解舉例：對以下線性規劃問題：對以下線性規劃問題： MIN Z2X1X22X3 s.t. X1X2X34 X1X2KX36 X10，X2 0，X3 無約無約束束知其最優解為知其最優解為 X1* =5 , X2* = 0 , X3* =1。寫出其對偶問題并求其最優解和寫出其對偶問題并求其最優解和 K 的值。的值。寫出對偶問題

7、：寫出對偶問題： MAX W = 4Y1+6Y2 s.t. -Y1-Y2 2 Y1+Y2-1 Y1-KY2=2 Y20根據對偶性質：根據對偶性質： 4Y1+6Y2 = -12 -Y1-Y2 =2 Y1-KY2=2Y1*=0,Y2*=-2,K=1 第三章第三章 線性規劃模型線性規劃模型第三章第三章 線性規劃模型線性規劃模型n展展n義務指派問題線性規劃問題擴義務指派問題線性規劃問題擴展展第四章第四章 線性規劃的擴展線性規劃的擴展n第四章第四章 線性規劃的擴展線性規劃的擴展第四章第四章 線性規劃的擴展線性規劃的擴展nX=0,1 等價于X1, X0 且取整數。nn 0-1規劃問題求解：思緒與LP、IP

8、問題一致。n教材P8183 實例4.7、實例4.8 jnjjXCz1maxmibXanjijij,.2 , 1,1 思索固定本錢的最小消費費用問題 某工廠有三種設備均可消費同一產品，第j種設備運轉的固定本錢為dj，運轉的單位變動本錢為cj，那么消費本錢與產量xj的關系為： j=1,2,3 如何使設備運轉的總本錢最小？ 0 xxcd0 x0)x(fjjjjjjj當當第四章第四章 線性規劃的擴展線性規劃的擴展引入01變量 yj ， 令 建立以下模型：這里M是一個很大的正數。當yj=0時，xj=0，即第j種設備不運轉，相應的運轉本錢 djyj+cjxj=0當yj1時，0 xjM，實踐上對xj沒有限制

9、，運轉本錢為 dj+cjxj 這是一個混合0-1規劃問題 1 , 0, 03 , 2 , 1. .)(min31jjjjjjjjjyxjMyxtsxcydz0 x種設備時，即j當采用第10 x種設備時，即j當不采用第 0jjjy第四章第四章 線性規劃的擴展線性規劃的擴展互斥約束的處置：如：互斥約束的處置：如：f(x) a (a0) 當問題需求同時思索一對分段約束時，如何將其當問題需求同時思索一對分段約束時，如何將其同時出如今模型中非線性變成線性：同時出如今模型中非線性變成線性： 如：如： f(x)-30 (1) ; f(x)0 (2) 經過引入一個經過引入一個01整數變量整數變量 y 和一個充

10、分大的正和一個充分大的正實數實數M, 可化為：可化為： f(x)+3My (3) f(x) M(1-y) (4) 當當y=0時，時，(3)=(1), (4)自然成立，不起作用自然成立，不起作用 當當y=1時，時，(4)=(2),(3)為：為：3M+f(x),當當M很很大時也自然成立，因此也不起作用。大時也自然成立，因此也不起作用。 3和和4可同時進入模型約束。可同時進入模型約束。第四章第四章 線性規劃的擴展線性規劃的擴展多中選一的處置： 模型希望在以下n個約束中，只能有一個約束有效： fi (x) 0 (i=1,2,n) 1 引入n個01整數變量yi ,(i=1,2,n),可將上式改寫為： f

11、i (x) M(1- yi) (i=1,2,n), (2) (3) M為恣意大的正數。 (2) : 當yi1 時 ，(2)=(1) ; yi 0 時，自然滿足 (3) : 保證了yi 有且只需一個取值為1，其他為0。 11niiy第四章第四章 線性規劃的擴展線性規劃的擴展多中選一的處置： 模型希望在以下n個約束中，只能有一個約束有效： fi (x) 0 (i=1,2,n) 1 引入n個01整數變量yi ,(i=1,2,n),可將上式改寫為： fi (x) M(1- yi) (i=1,2,n), (2) (3) M為恣意大的正數。 (2) : 當yi1 時 ，(2)=(1) ; yi 0 時，自

12、然滿足 (3) : 保證了yi 有且只需一個取值為1，其他為0。 11niiy第四章第四章 線性規劃的擴展線性規劃的擴展多中選一的處置： 模型希望在以下2個約束中，只能有一個約束有效： 3X1+4X2 5，4X3-2X2 3 引入2個01整數變量yi ,(i=1,2),可將上式改寫為： Y=1時不采用，Y0時采用 3X1+4X2 5 + MY1 4X3-2X2 3 +MY2 Y1+Y2=1 M為恣意大的正數。第四章第四章 線性規劃的擴展線性規劃的擴展第四章第四章 線性規劃的擴展線性規劃的擴展n Xij = n 0 當不指派當不指派Ai去去完成完成Bj任務任務第四章第四章 線性規劃的擴展線性規劃

13、的擴展n指派問題數學模型的規范型n n MIN Z = Cij0)n i= 1,2,n)n n (j= 1,2,n)n Xij 皆為 0 或 1n 由 Cij 組成的方陣 C = ( Cij )nn 稱為效率矩陣 ninjCijXij11njXij11niXij11第四章第四章 線性規劃的擴展線性規劃的擴展n指派問題規范型的求解匈牙利法指派問題規范型的求解匈牙利法n 指派問題有以下性質：指派問題有以下性質：n 假設從效率矩陣假設從效率矩陣C的任何一行列各的任何一行列各元素中分別減去一個常數元素中分別減去一個常數KK可正可負得可正可負得到新矩陣到新矩陣D,那么以那么以D為效率矩陣的指派問題為效率

14、矩陣的指派問題與原問題有一樣的解，但最優值比原問題最與原問題有一樣的解，但最優值比原問題最優值小優值小K。n n 用匈牙利法求解的條件：用匈牙利法求解的條件：n MIN、i=j 、Cij0第四章第四章 線性規劃的擴展線性規劃的擴展n匈牙利法的主要步驟：匈牙利法的主要步驟：n 第一步：變換效率矩陣，使在各行各列都出第一步：變換效率矩陣，使在各行各列都出現零元素。現零元素。n 1、從矩陣、從矩陣C的每行元素減去該行的最小元的每行元素減去該行的最小元素；素；n 2、再從所得矩陣的每列中減去該列最小元、再從所得矩陣的每列中減去該列最小元素。素。n 第二步：以最少數目的程度線和垂直線劃去第二步：以最少數

15、目的程度線和垂直線劃去一切的零元素。假設所用的直線等于行或列數，一切的零元素。假設所用的直線等于行或列數，那么終了指派。否那么繼續。那么終了指派。否那么繼續。n 第三步：找到沒有被劃去的最小的元素，一第三步：找到沒有被劃去的最小的元素，一切沒有被劃中的元素減去這一最小值。而被劃切沒有被劃中的元素減去這一最小值。而被劃中兩次的元素該元素行列都被劃中那么要中兩次的元素該元素行列都被劃中那么要加上這一最小值。再前往到第一步。加上這一最小值。再前往到第一步。n 第四步：最后根據零元素的位置，確定最優第四步：最后根據零元素的位置，確定最優分配方案。分配方案。練習題：建立線性規劃模型練習題：建立線性規劃模

16、型練習題練習題1：建立線性規劃模型：建立線性規劃模型n確定決策變量：確定決策變量：n X1，X2，X3為每月買進的商品量為每月買進的商品量n Y1，Y2，Y3為每月賣出的商品量為每月賣出的商品量n確定目的函數：確定目的函數：n MAX Z=3.31Y1+3.25Y2+2.95Y3n -2.85X1-3.05X2-2.90X3n確定約束條件：確定約束條件：n買進的商品當月到貨下月賣出，每月賣出的量應買進的商品當月到貨下月賣出，每月賣出的量應小于月初時的庫存量小于月初時的庫存量n在買賣時間沒有嚴厲要求的情況下，先賣再買總在買賣時間沒有嚴厲要求的情況下，先賣再買總是有利的，因此每月最大庫存量為月初庫

17、存減去是有利的，因此每月最大庫存量為月初庫存減去賣出再加上買進的量賣出再加上買進的量練習題練習題1：建立線性規劃模型：建立線性規劃模型 月初庫存量月初庫存量 買進買進 賣賣出出 一月一月 1000 X1 Y1 二月二月 1000Y1+X1 X2 Y2 三月三月 1000Y1+X1-Y2+X2 X3 Y3 因此：因此： Y1 1000 Y2 1000Y1+X1 Y3 1000Y1+X1-Y2+X2每月庫存容量最多為每月庫存容量最多為5000，三月末為，三月末為2000 ： 一月：一月： 1000Y1+X1 5000 二月：二月： 1000Y1+X1-Y2+X2 5000 三月：三月： 1000Y

18、1+X1-Y2+X2-Y3+X2 = 2000練習題練習題1：建立線性規劃模型：建立線性規劃模型n每月進貨的資金應小于擁有的資金和賣出商品每月進貨的資金應小于擁有的資金和賣出商品的收入之和：先賣再買的收入之和：先賣再買n 一月：一月：2.85 X1 20000 + 3.10 Y1n 二月：二月：3.05 X2 20000 + 3.10 Y1n -2.85X1+3.25Y2n 三月：三月：2.90 X3 20000 + 3.10 Y1n -2.85X1+3.25Y2n -3.05X2+2.95Y3nX1,X2,X3,Y1,Y2,Y3非負整數非負整數n 練習題練習題2：建立線性規劃模型：建立線性規

19、劃模型練習題練習題2：建立線性規劃模型：建立線性規劃模型n決策變量確定：能否投資需求決策決策變量確定：能否投資需求決策n n X11，X12，X21，X31 均為均為01變量變量n約束條件確定：約束條件確定：n第一種產品的方案一和方案二最多只能選一：第一種產品的方案一和方案二最多只能選一：n X11+X12 1n第二種產品、第三種產品可選也可不選：第二種產品、第三種產品可選也可不選：n X21 1 ， X31 1n 全部投資額應不超越全部投資額應不超越550萬萬n 300X11+280X12+260X21+240X31 550第一種產品第一種產品方案方案1 方案方案2X11 X12第二種產品第

20、二種產品X21第三種產品第三種產品X31練習題練習題2：建立線性規劃模型：建立線性規劃模型n目的函數確定：每年的收益和最大n 每年的總收益包含兩部分：n第一部分：工程投資收益，利用投資回收系數n第二部分：剩余資金的普通投資收益1)26. 01 ()26. 01 (26. 03124010.28)(10.28)0.28(1X212601)28. 01 ()28. 01 (28. 0122801)3 . 01 ()3 . 01 (3 . 01130055555555XXX1) 1 . 01 () 1 . 01 ( 1 . 0)31240212601228011300(55055XXXXn練習題練習

21、題3：n n 有張、王、李、趙有張、王、李、趙4位教師被分配教語文、位教師被分配教語文、數學、物理、化學數學、物理、化學4門課程，每位教師教一門門課程，每位教師教一門課程，每門課程由一位教師教。根據這四位課程，每門課程由一位教師教。根據這四位教師以往教課的情況，他們分別教這四門課教師以往教課的情況，他們分別教這四門課程的平均成果如下表：程的平均成果如下表：n 四位教師每人只能教一門課，每一門課四位教師每人只能教一門課，每一門課只能由一個教師來教。要確定哪一位教師上只能由一個教師來教。要確定哪一位教師上哪一門課，使四門課的平均成果之和為最高。哪一門課，使四門課的平均成果之和為最高。n 結果：張化

22、學結果：張化學76 王物理王物理77 n 李數學李數學90 趙語文趙語文93 指派問題線性規劃模型舉例指派問題線性規劃模型舉例n設設xiji=1, 2, 3, 4；j=1, 2, 3, 4為第為第i個教師能否教第個教師能否教第j門課，門課，xij只能取值只能取值0或或1，這個指派問題的線性規劃模型，這個指派問題的線性規劃模型為：為：nmax z= 92x11+68x12+85x13+76x14+82x21 +91x22+77x23+63x24+83x31+90 x32+74x33n +65x34+93x41+61x42+83x43+75x44ns.t.x11+x12+x13+x14=1 1n

23、x21+x22+x23+x24=1 2n x31+x32+x33+x34=1 3n x41+x42+x43+x44=1 4n x11+x21+x31+x41=1 5n x12+x22+x32+x42=1 6n x13+x23+x33+x43=1 7n x14+x24+x34+x44=1 8n xij=0, 1 x14=1，x23=1，x32=1，x41=1，max z=336 第四章第四章 線性規劃的擴展線性規劃的擴展地的要求，又使總的運輸費用或地的要求，又使總的運輸費用或里程、時間等最小。里程、時間等最小。第四章第四章 線性規劃的擴展線性規劃的擴展 設有同一種貨物從m個出發地1，2，m運往n

24、個到達地1，2，n。第i個出發地的供應量Supply為sisi0， 第j個到達地的需求量Demand為 djdj0。 每單位貨物從產地 i 運到銷地 j 的運價為Cij。求一個使總運費最小的運輸方案。 1 2 3 n 供應 1 c11 c1n s1 2 c21 本錢 c2n s2 cij m cm1 cmn sm 需求 d1 dn 出發地到達地第四章第四章 線性規劃的擴展線性規劃的擴展ninjCijXij11njiSXij1mijdXij1n產銷平衡的運輸問題模型產銷平衡的運輸問題模型n 令令Xij為為 從從i地運到地運到j地的數量地的數量n MIN Z = Cij0)n i= 1,2,m)

25、供應約供應約束束n n (j= 1,2,n) 需求約束需求約束n n Xij0n 由由 Cij、Si、dj 組成的組成的 (m+1)(n+1) 矩陣稱為運輸矩陣矩陣稱為運輸矩陣第四章第四章 線性規劃的擴展線性規劃的擴展n目的約束：把約束右端項看成是要追目的約束：把約束右端項看成是要追求的目的值，求的目的值，在到達此目的時允許在到達此目的時允許有正負偏向，線性規劃問題的目的函有正負偏向，線性規劃問題的目的函數，在給定目的值和參與正、負偏向數，在給定目的值和參與正、負偏向后可變換為目的約束，也可將絕對約后可變換為目的約束，也可將絕對約束變換為目的約束。束變換為目的約束。第四章第四章 線性規劃的擴展

26、線性規劃的擴展要求恰好到達目的值正負偏向都要盡能夠地要求恰好到達目的值正負偏向都要盡能夠地小，這時小，這時 MIN Z = fd+ d- )要求不超越目的值允許達不到，正偏向要盡能要求不超越目的值允許達不到，正偏向要盡能夠地小夠地小 MIN Z = fd+ )要求不低于目的值：要求不低于目的值： MIN Z = fd- )練習：建立目的規劃模型某單位指點在思索本單位職工的晉級調資方案時，依次遵守以下某單位指點在思索本單位職工的晉級調資方案時，依次遵守以下規定：規定：不超越年工資總額不超越年工資總額60000元；元；每級的人數不超越定編規定的人數；每級的人數不超越定編規定的人數；II，III級的

27、晉級面盡能夠到達現有人數的級的晉級面盡能夠到達現有人數的20；III級缺乏編制的人數可錄用新職工，又級缺乏編制的人數可錄用新職工，又I級的職工中有級的職工中有10 要退要退休。休。有關資料匯總于下表中，問該指點應如何擬定一個稱心的方案。有關資料匯總于下表中，問該指點應如何擬定一個稱心的方案。等級工資額（元/年）現有人數編制人數IIIIII200015001000101215121515合計3742目的規劃求解：目的規劃求解：n設設X1,X2,X3分別表示提升到分別表示提升到I,II級和錄用級和錄用到到III級的人數。級的人數。n優先因子優先因子P1:不超年工資總額不超年工資總額60000元元n

28、 優先因子優先因子P2:每級人數不超越定編人數每級人數不超越定編人數 n 優先因子優先因子P3:II,III級晉級面盡能夠到級晉級面盡能夠到達達n建立目的約束：建立目的約束：n 2000(10100.1X1)+1500(12-X1+X2)+1000(15-X2+X3)+d1d1+=60000目的規劃求解：目的規劃求解：每級人數不超越定編人數：每級人數不超越定編人數： I級有：級有：10(1-0.1)+X1+d2-d2+=12II級有：級有：12-X1+X2+d3- -d3+=15III級有：級有：15-X2+X3+d4- -d4+=15II,III級晉級面不大于現有人數的級晉級面不大于現有人數

29、的20，但，但盡能夠多提；盡能夠多提；對對II級有：級有：X1+d5- -d5+=120.2對對III級有：級有：X2+d6- -d6+=150.2目的函數：目的函數： MIN Z=P1 d1+P2(d2+ d3+ + d4+ )+P3(d5- +d6- )第四章第四章 線性規劃的擴展線性規劃的擴展nn動態規劃沒有規范模型，沒有獨一動態規劃沒有規范模型，沒有獨一確定的解法確定的解法決策決策1決策決策2決策決策3決策決策n1形狀形狀123n形狀形狀n形狀形狀4形狀形狀3形狀形狀2階段階段1階段階段2階段階段3階段階段n第四章第四章 線性規劃的擴展線性規劃的擴展n允許采取決策的全體。允許采取決策的

30、全體。n形狀轉移方程形狀轉移方程Xk+1=T(Xk,dk)：某一：某一形狀以及該形狀下的決策，與下一形狀形狀以及該形狀下的決策，與下一形狀之間的函數關系。之間的函數關系。第四章第四章 線性規劃的擴展線性規劃的擴展n最優化原理最優化原理n 最正確途徑中任一形狀中間點到最最正確途徑中任一形狀中間點到最終形狀最終點的途徑也是該形狀到最終形狀最終點的途徑也是該形狀到最終形狀一切能夠中的最短途徑。終形狀一切能夠中的最短途徑。CjABiCjDtE階段1階段2階段3階段4Dt第四章第四章 線性規劃的擴展線性規劃的擴展動態規劃練習動態規劃練習第四章第四章 線性規劃的擴展線性規劃的擴展S1=2S4=0S3=2S

31、3=1S3=0S2=2S2=1S2=00.060.480.300.160.300.500.800.300.500.800.200.400.600.600.400.600.150.200.40第一組第一組第三組第三組第二組第二組剩余人數剩余人數效率最高？效率最高？n系統時間加工時間排隊系統時間加工時間排隊時間時間n延誤的任務項數最少延誤的任務項數最少n 先按先到期者優先的原那么排初先按先到期者優先的原那么排初次次序次次序 n 假設沒有延誤的任務，那么是最假設沒有延誤的任務，那么是最優解。優解。n 假設有延誤的任務，那么找出其假設有延誤的任務，那么找出其中的一項，找出到此項任務之前包中的一項，找出

32、到此項任務之前包括該項加工時間最長的一項，并將括該項加工時間最長的一項，并將之抽去，重新安排時間，假設已沒有之抽去，重新安排時間，假設已沒有延誤的任務，那么將被抽取的這一項延誤的任務，那么將被抽取的這一項放置最后；如仍有被延誤的任務，那放置最后；如仍有被延誤的任務，那么再反復這一步。么再反復這一步。n時序規劃擴展約翰遜原那么：時序規劃擴展約翰遜原那么：n 兩臺順序機器完成一批任務兩臺順序機器完成一批任務n n 每項任務在機器每項任務在機器1和機器和機器2上的上的加工時間不一樣，如何使系統效率加工時間不一樣，如何使系統效率最高？最高？ 3214機器機器1機器機器2任務任務n約翰遜原那么約翰遜原那

33、么n 找出各臺機器上加工時間最短的一項找出各臺機器上加工時間最短的一項任務，任務， n 假設在機器假設在機器1上，這項任務最先上，這項任務最先做；做；n 假設在機器假設在機器2上，這項任務最后上，這項任務最后做；做；n 不斷反復，從兩端往內排。一樣時間不斷反復，從兩端往內排。一樣時間可任選一可任選一 個，普通先安排機器個，普通先安排機器1上任務。上任務。n例例53：教材：教材P110 實例實例5.6n最小樹最小樹n 一個網絡中有很多樹，其中邊的長一個網絡中有很多樹，其中邊的長度權數之和為最小的樹為最小樹。度權數之和為最小的樹為最小樹。n最小樹的獲取破圈法最小樹的獲取破圈法n 從圖中任取一個圈，去掉該圈的一從圖中任取一個圈，去掉該圈的一條最大邊，將此圈破去