浙江大學(xué)管理學(xué)院ppt課件

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

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

3、布數(shù)學(xué)期望與概率分布分析等待的隊列分析等待的隊列, ,模擬合理作業(yè)時間和資源利用模擬合理作業(yè)時間和資源利用第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n決策變量本身能否有限制條決策變量本身能否有限制條件？件？第三章第三章 線性規(guī)劃模型線性規(guī)劃模型nnxcxcxcz 2211max(min)mnmn22m11m2nn22221211nn1212111b).(xaxaxab).(xaxaxab).(xaxaxa. t . s第三章第三章 線性規(guī)劃模型線性規(guī)劃模型nn一切參數(shù)一切參數(shù)a、b、c都應(yīng)是確定值都應(yīng)是確定值n決策變量的非負性決策變量的非負性第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 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目的函數(shù)等值線目的函數(shù)等值線Z = X1+3X2可行域可行域(4/3,14/3)第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n對偶問題與影子價錢對偶問題與影子價錢n 定義：定義： 設(shè)以下線性規(guī)劃問題設(shè)以下線性規(guī)劃問題n MAX Z = CTXn s.t. AXb X0n 為原始問題，那么稱以下問題為原始問題，那么稱以下問題n MIN W = bTYn s.t. ATYC Y0n 為原始問題的對

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

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

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

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

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

10、分大的正和一個充分大的正實數(shù)實數(shù)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可同時進入模型約束?？赏瑫r進入模型約束。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展多中選一的處置： 模型希望在以下n個約束中，只能有一個約束有效： fi (x) 0 (i=1,2,n) 1 引入n個01整數(shù)變量yi ,(i=1,2,n),可將上式改寫為： f

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

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

13、的擴展n指派問題數(shù)學(xué)模型的規(guī)范型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第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展n指派問題規(guī)范型的求解匈牙利法指派問題規(guī)范型的求解匈牙利法n 指派問題有以下性質(zhì)：指派問題有以下性質(zhì)：n 假設(shè)從效率矩陣假設(shè)從效率矩陣C的任何一行列各的任何一行列各元素中分別減去一個常數(shù)元素中分別減去一個常數(shù)KK可正可負得可正可負得到新矩陣到新矩陣D,那么以那么以D為效率矩陣的指派問題為效率

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

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

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

17、存減去是有利的，因此每月最大庫存量為月初庫存減去賣出再加上買進的量賣出再加上買進的量練習題練習題1：建立線性規(guī)劃模型：建立線性規(guī)劃模型 月初庫存量月初庫存量 買進買進 賣賣出出 一月一月 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：建立線性規(guī)劃模型：建立線性規(guī)劃模型n每月進貨的資金應(yīng)小于擁有的資金和賣出商品每月進貨的資金應(yīng)小于擁有的資金和賣出商品的收入之和：先賣再買的收入之和：先賣再買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非負整數(shù)非負整數(shù)n 練習題練習題2：建立線性規(guī)劃模型：建立線性規(guī)

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

20、二種產(chǎn)品X21第三種產(chǎn)品第三種產(chǎn)品X31練習題練習題2：建立線性規(guī)劃模型：建立線性規(guī)劃模型n目的函數(shù)確定：每年的收益和最大n 每年的總收益包含兩部分：n第一部分：工程投資收益，利用投資回收系數(shù)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位教師被分配教語文、位教師被分配教語文、數(shù)學(xué)、物理、化學(xué)數(shù)學(xué)、物理、化學(xué)4門課程，每位教師教一門門課程，每位教師教一門課程，每門課程由一位教師教。根據(jù)這四位課程，每門課程由一位教師教。根據(jù)這四位教師以往教課的情況，他們分別教這四門課教師以往教課的情況，他們分別教這四門課程的平均成果如下表：程的平均成果如下表：n 四位教師每人只能教一門課，每一門課四位教師每人只能教一門課，每一門課只能由一個教師來教。要確定哪一位教師上只能由一個教師來教。要確定哪一位教師上哪一門課，使四門課的平均成果之和為最高。哪一門課，使四門課的平均成果之和為最高。n 結(jié)果：張化

22、學(xué)結(jié)果：張化學(xué)76 王物理王物理77 n 李數(shù)學(xué)李數(shù)學(xué)90 趙語文趙語文93 指派問題線性規(guī)劃模型舉例指派問題線性規(guī)劃模型舉例n設(shè)設(shè)xiji=1, 2, 3, 4；j=1, 2, 3, 4為第為第i個教師能否教第個教師能否教第j門課，門課，xij只能取值只能取值0或或1，這個指派問題的線性規(guī)劃模型，這個指派問題的線性規(guī)劃模型為：為：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 第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展地的要求，又使總的運輸費用或地的要求，又使總的運輸費用或里程、時間等最小。里程、時間等最小。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 設(shè)有同一種貨物從m個出發(fā)地1，2，m運往n

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

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

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

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

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

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

30、全體。n形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程Xk+1=T(Xk,dk)：某一：某一形狀以及該形狀下的決策，與下一形狀形狀以及該形狀下的決策，與下一形狀之間的函數(shù)關(guān)系。之間的函數(shù)關(guān)系。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展n最優(yōu)化原理最優(yōu)化原理n 最正確途徑中任一形狀中間點到最最正確途徑中任一形狀中間點到最終形狀最終點的途徑也是該形狀到最終形狀最終點的途徑也是該形狀到最終形狀一切能夠中的最短途徑。終形狀一切能夠中的最短途徑。CjABiCjDtE階段1階段2階段3階段4Dt第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展動態(tài)規(guī)劃練習動態(tài)規(guī)劃練習第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展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第一組第一組第三組第三組第二組第二組剩余人數(shù)剩余人數(shù)效率最高？效率最高？n系統(tǒng)時間加工時間排隊系統(tǒng)時間加工時間排隊時間時間n延誤的任務(wù)項數(shù)最少延誤的任務(wù)項數(shù)最少n 先按先到期者優(yōu)先的原那么排初先按先到期者優(yōu)先的原那么排初次次序次次序 n 假設(shè)沒有延誤的任務(wù)，那么是最假設(shè)沒有延誤的任務(wù)，那么是最優(yōu)解。優(yōu)解。n 假設(shè)有延誤的任務(wù)，那么找出其假設(shè)有延誤的任務(wù)，那么找出其中的一項，找出到此項任務(wù)之前包中的一項，找出

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

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