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

1、n狹義的管文科學(xué)：數(shù)理方法制定管理決策狹義的管文科學(xué)：數(shù)理方法制定管理決策 n Management Science = Operations research n (MS=OR) n 決策制定主體、環(huán)境、過(guò)程決策制定主體、環(huán)境、過(guò)程n 定量分析數(shù)學(xué)、概率、統(tǒng)計(jì)定量分析數(shù)學(xué)、概率、統(tǒng)計(jì)n 運(yùn)籌方法問(wèn)題、建模、處理運(yùn)籌方法問(wèn)題、建模、處理 n 定性分析的方法定性分析的方法n 德?tīng)柗品椒ǖ聽(tīng)柗品椒╪ 小組討論小組討論n n 定量模型的運(yùn)用定量模型的運(yùn)用n 運(yùn)籌模型運(yùn)籌模型n 管文科學(xué)的方法論管文科學(xué)的方法論運(yùn)籌方法處理典型管理問(wèn)題運(yùn)籌方法處理典型管理問(wèn)題解決方法解決方法典型的辦法典型的辦法 財(cái)務(wù)模

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

3、布數(shù)學(xué)期望與概率分布分析等待的隊(duì)列分析等待的隊(duì)列, ,模擬合理作業(yè)時(shí)間和資源利用模擬合理作業(yè)時(shí)間和資源利用第三章第三章 線性規(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決策變量的非負(fù)性決策變量的非負(fù)性第三章第三章 線性規(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對(duì)偶問(wèn)題與影子價(jià)錢對(duì)偶問(wèn)題與影子價(jià)錢n 定義：定義： 設(shè)以下線性規(guī)劃問(wèn)題設(shè)以下線性規(guī)劃問(wèn)題n MAX Z = CTXn s.t. AXb X0n 為原始問(wèn)題，那么稱以下問(wèn)題為原始問(wèn)題，那么稱以下問(wèn)題n MIN W = bTYn s.t. ATYC Y0n 為原始問(wèn)題的對(duì)

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

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

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

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

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

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

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

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

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

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

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

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

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

18、1+X1-Y2+X2-Y3+X2 = 2000練習(xí)題練習(xí)題1：建立線性規(guī)劃模型：建立線性規(guī)劃模型n每月進(jìn)貨的資金應(yīng)小于擁有的資金和賣出商品每月進(jìn)貨的資金應(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非負(fù)整數(shù)非負(fù)整數(shù)n 練習(xí)題練習(xí)題2：建立線性規(guī)劃模型：建立線性規(guī)

19、劃模型練習(xí)題練習(xí)題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萬(wàn)萬(wàn)n 300X11+280X12+260X21+240X31 550第一種產(chǎn)品第一種產(chǎn)品方案方案1 方案方案2X11 X12第二種產(chǎn)品第

20、二種產(chǎn)品X21第三種產(chǎn)品第三種產(chǎn)品X31練習(xí)題練習(xí)題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練習(xí)題練習(xí)

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

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

24、個(gè)到達(dá)地1，2，n。第i個(gè)出發(fā)地的供應(yīng)量Supply為sisi0， 第j個(gè)到達(dá)地的需求量Demand為 djdj0。 每單位貨物從產(chǎn)地 i 運(yùn)到銷地 j 的運(yùn)價(jià)為Cij。求一個(gè)使總運(yùn)費(fèi)最小的運(yùn)輸方案。 1 2 3 n 供應(yīng) 1 c11 c1n s1 2 c21 本錢 c2n s2 cij m cm1 cmn sm 需求 d1 dn 出發(fā)地到達(dá)地第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展ninjCijXij11njiSXij1mijdXij1n產(chǎn)銷平衡的運(yùn)輸問(wèn)題模型產(chǎn)銷平衡的運(yùn)輸問(wèn)題模型n 令令Xij為為 從從i地運(yùn)到地運(yùn)到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) 矩陣稱為運(yùn)輸矩陣矩陣稱為運(yùn)輸矩陣第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展n目的約束：把約束右端項(xiàng)看成是要追目的約束：把約束右端項(xiàng)看成是要追求的目的值，求的目的值，在到達(dá)此目的時(shí)允許在到達(dá)此目的時(shí)允許有正負(fù)偏向，線性規(guī)劃問(wèn)題的目的函有正負(fù)偏向，線性規(guī)劃問(wèn)題的目的函數(shù)，在給定目的值和參與正、負(fù)偏向數(shù)，在給定目的值和參與正、負(fù)偏向后可變換為目的約束，也可將絕對(duì)約后可變換為目的約束，也可將絕對(duì)約束變換為目的約束。束變換為目的約束。第四章第四章 線性規(guī)劃的擴(kuò)展

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

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

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

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

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

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

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