浙江大學(xué)最牛應(yīng)用運(yùn)籌學(xué)課件資料講解

1、浙江大學(xué)最牛應(yīng)用運(yùn)籌學(xué)課件第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 目標(biāo)函數(shù)： 約束條件：nnxcxcxcz 2211max(min)mnmn22m11m2nn22221211nn1212111b).(xaxaxab).(xaxaxab).(xaxaxa. t . sX 0 0 第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 Max z = 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目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線Z = X1+3X2可行域可

2、行域(4/3,14/3)第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n對(duì)偶問(wèn)題與影子價(jià)格對(duì)偶問(wèn)題與影子價(jià)格 定義：定義： 設(shè)以下線性規(guī)劃問(wèn)題設(shè)以下線性規(guī)劃問(wèn)題 MAX Z = CTX s.t. AXb X0 為原始問(wèn)題，則稱以下問(wèn)題為原始問(wèn)題，則稱以下問(wèn)題 MIN W = bTY s.t. ATYC Y0 為原始問(wèn)題的為原始問(wèn)題的對(duì)偶問(wèn)題對(duì)偶問(wèn)題，最優(yōu)值，最優(yōu)值Y為為影子價(jià)格影子價(jià)格 第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n對(duì)偶問(wèn)題與原始問(wèn)題的關(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約約束束n

3、xj無(wú)約束無(wú)約束 aTijyi=cjxj0 aTijyicj約約束束m aijxjbiyi0變變量量m aijxj=biyi無(wú)約束無(wú)約束 aijxjbiyi0 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。若兩個(gè)互為對(duì)偶問(wèn)題之一有最優(yōu)解，則另一個(gè)必有最優(yōu)解，若兩個(gè)互為對(duì)偶問(wèn)題之一有最優(yōu)解，則另一個(gè)必有最優(yōu)解，且目標(biāo)函數(shù)值相等且目標(biāo)函數(shù)值相等(Z*=W*)，最優(yōu)解滿足，最優(yōu)解滿足CX*=Y*b。若若X*,Y*分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則 X*,Y*為最為最優(yōu)解的充分必要條件是優(yōu)解的充分必要條件是Y*XL=0和和YSX*=0。第三章第三章 線性規(guī)劃模型線性

4、規(guī)劃模型原問(wèn)題標(biāo)準(zhǔn)型：原問(wèn)題標(biāo)準(zhǔn)型：Max Z= CXCXAX AX + X XL= b bX X, ,X XL0對(duì)偶問(wèn)題標(biāo)準(zhǔn)型：對(duì)偶問(wèn)題標(biāo)準(zhǔn)型：Min W= YbYbYA YA - Y YS= C CY Y, ,Y YS0第三章第三章 線性規(guī)劃模型線性規(guī)劃模型原問(wèn)題和對(duì)偶問(wèn)題的互補(bǔ)松松弛關(guān)系：原問(wèn)題和對(duì)偶問(wèn)題的互補(bǔ)松松弛關(guān)系：第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 根據(jù)對(duì)偶問(wèn)題的性質(zhì)有：根據(jù)對(duì)偶問(wèn)題的性質(zhì)有： Z* = W* = bi yi* 兩邊對(duì)兩邊對(duì)bi求偏導(dǎo)數(shù)得到：求偏導(dǎo)數(shù)得到： Z* = yi* (i= 1,2, ,m) bi 即即 yi* 表示每增加一個(gè)單位表示每增加一個(gè)單位 b

5、i 后后 Z* 的增量的增量第三章第三章 線性規(guī)劃模型線性規(guī)劃模型第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 對(duì)于每一根7.4米長(zhǎng)的鋼材，可有若干種下料方式把它截取成我們所需要的軸，如可以截取2根2.9米和1根1.5米，合計(jì)用料7.3米，余料為0.1米。可以列出全部的下料方式：B1B2B3B4B5B6B7B8需要量需要量2.9m2.1m1.5m余料余料2010.110301200.31110.90220.20130.80301.10041.4100200100最少線性規(guī)劃模型配套問(wèn)題n思考題：思考題： 某廠生產(chǎn)一種產(chǎn)品，由兩個(gè)某廠生產(chǎn)一種產(chǎn)品，由兩個(gè)B1零件和三個(gè)零件和三個(gè)B2零件零件配套組裝而成

6、。該廠有配套組裝而成。該廠有A1，A2，A3三種機(jī)床可加工上三種機(jī)床可加工上述兩種零件，每種機(jī)床的臺(tái)數(shù)以及每臺(tái)機(jī)床每個(gè)工作日述兩種零件，每種機(jī)床的臺(tái)數(shù)以及每臺(tái)機(jī)床每個(gè)工作日全部用于加工某一種零部件的最大產(chǎn)量（即生產(chǎn)率：件全部用于加工某一種零部件的最大產(chǎn)量（即生產(chǎn)率：件/日）如下表所示。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。日）如下表所示。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。 該題不是單純要求兩種零件產(chǎn)量越大越好，而是要求每個(gè)工作日按2:3的比例生產(chǎn)出來(lái)的B1和B2零件的套數(shù)達(dá)到最大。 決策變量：以Xij表示每臺(tái)Ai(i=1,2,3)機(jī)床每個(gè)工作日加工Bj(j=1,2)零件的時(shí)間。Z為B1,B2零件按2:3比

7、例配套的數(shù)量（套/日）。 約束條件：工時(shí)約束 X11+X12 = 1 (A1一天） X21+X22 = 1 (A2一天） X31+X32 = 1 (A3一天） 配套約束： Z = MIN(320X11+235X21+410X31)/2, (330X12+245X22+418X32)/3)Z = MIN(320X11+235X21+410X31)/2, (330X12+245X22+418X32)/3) 等價(jià)于 Z(320X11+235X21+410X31)/2 Z(330X12+245X22+418X32)/3 非負(fù)約束：Z,Xij0,Z為整數(shù)目標(biāo)函數(shù)： MAX Y = Z求解結(jié)果： Y*=Z

8、*=44,X11=0.13,X12=0.87,X21=1,X22=0 X31=0.25,X32=0.75, A1B1:8,A1B2:78,A2B1:70,A2B2:0,A3B1:10,A3B2:54 B1:88件；B2:132件配料問(wèn)題練習(xí)配料問(wèn)題練習(xí)n某化工廠要用三種原料某化工廠要用三種原料D,P,H混合配置三種不同混合配置三種不同規(guī)格的產(chǎn)品規(guī)格的產(chǎn)品A,B,C。各產(chǎn)品的規(guī)格、單價(jià)如左表。各產(chǎn)品的規(guī)格、單價(jià)如左表所示，各原料的單價(jià)及每天的最大供應(yīng)量如右表所示，各原料的單價(jià)及每天的最大供應(yīng)量如右表所示，該廠應(yīng)如何安排生產(chǎn)才能使利潤(rùn)最大？所示，該廠應(yīng)如何安排生產(chǎn)才能使利潤(rùn)最大？ 配料問(wèn)題練習(xí)答案

9、配料問(wèn)題練習(xí)答案n變量：變量： 產(chǎn)品產(chǎn)品A中中D,P,H含量分別為含量分別為 X11,X12,X13 產(chǎn)品產(chǎn)品B中中D,P,H含量分別為含量分別為 X21,X22,X23 產(chǎn)品產(chǎn)品C中中D,P,H含量分別為含量分別為 X31,X32,X33 令：令：X11+X12+X13=X1 X21+X22+X23=X2 X31+X32+X33=X3 根據(jù)規(guī)格條件有：根據(jù)規(guī)格條件有：X110.5X1; X120.25X1 X210.25X2; X220.5X2 配料問(wèn)題答案配料問(wèn)題答案得到：得到： - X11+ X12+X130 - X11+3X12- X130 -3X21+ X22+X230 - X21+

10、 X22- X230原材料供應(yīng)條件：原材料供應(yīng)條件： X11+X21+X31100 X12+X22+X32100 X13+X23+X3360非負(fù)約束：非負(fù)約束：Xij0, i,j=1,2,3目標(biāo)函數(shù)：目標(biāo)函數(shù)：max z = -15X11+25X12+15X13- 30X21+10X22-40X31-10X33第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展(Integer Linear Programming, ILP) ： 決策變量是整數(shù)的線性規(guī)劃決策變量是整數(shù)的線性規(guī)劃 第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 一些變量的取值被限定為0或1。是整數(shù)

11、規(guī)劃的特例。 0-1規(guī)劃的一般模型： s.t. Xj = 0,1 j=1,2,n （X=0,1 等價(jià)于 X1, X0 且取整數(shù)。） 0-1規(guī)劃問(wèn)題求解：思路與LP、IP問(wèn)題一致。 0-1變量的靈活運(yùn)用（選與不選或只能選幾種等）。 jnjjXCz1maxmibXanjijij,.2 , 1,1例例4-2 廠址選擇問(wèn)題廠址選擇問(wèn)題 在在N個(gè)地點(diǎn)中選個(gè)地點(diǎn)中選r個(gè)（個(gè)（Nr）建廠，在第）建廠，在第i個(gè)地點(diǎn)建個(gè)地點(diǎn)建廠（廠（i=1，2，N）所需投資為）所需投資為 Ii 萬(wàn)元，占地萬(wàn)元，占地Li畝，建成以后的生產(chǎn)能力為畝，建成以后的生產(chǎn)能力為Pi 萬(wàn)噸?，F(xiàn)在有總?cè)f噸。現(xiàn)在有總投資投資I萬(wàn)元，土地萬(wàn)元，土

12、地L畝，應(yīng)如何選擇廠址，使建成畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。后總生產(chǎn)能力最大。第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 設(shè)： 整數(shù)規(guī)劃（整數(shù)規(guī)劃（0-1規(guī)劃）模型為：規(guī)劃）模型為： 地建廠表示在地不建廠表示在i1i0 xi1 ,0 xrxLxLIxI. t .sxPzmaxiN1iiN1iiiN1iiiN1iii投資約束土地約束建廠約束第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 例4.3 考慮固定成本的最小生產(chǎn)費(fèi)用問(wèn)題考慮固定成本的最小生產(chǎn)費(fèi)用問(wèn)題 某工廠有三種設(shè)備均可生產(chǎn)同一產(chǎn)品，某工廠有三種設(shè)備均可生產(chǎn)同一產(chǎn)品，第第j種設(shè)備運(yùn)行的固定成本為種設(shè)備運(yùn)行的固定成本為dj，運(yùn)行的

13、單位，運(yùn)行的單位變動(dòng)成本為變動(dòng)成本為cj，則生產(chǎn)成本與產(chǎn)量，則生產(chǎn)成本與產(chǎn)量xj的關(guān)系的關(guān)系為：為： j=1,2,3 如何使設(shè)備運(yùn)行的總成本最?。咳绾问乖O(shè)備運(yùn)行的總成本最?。?0 xxcd0 x0)x(fjjjjjjj當(dāng)當(dāng)?shù)谒恼碌谒恼?線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展引入引入01變量變量 yj ， 令令 建立以下模型：建立以下模型：這里這里M是一個(gè)很大的正數(shù)。是一個(gè)很大的正數(shù)。當(dāng)當(dāng)yj=0時(shí)，時(shí)，xj=0，即第，即第j種設(shè)備不運(yùn)行，相應(yīng)的運(yùn)行成本種設(shè)備不運(yùn)行，相應(yīng)的運(yùn)行成本 djyj+cjxj=0當(dāng)當(dāng)yj1時(shí)，時(shí)，0 xjM，實(shí)際上對(duì)，實(shí)際上對(duì)xj沒(méi)有限制，運(yùn)行成本為沒(méi)有限制，運(yùn)行成本為 dj+c

14、jxj 這是一個(gè)混合這是一個(gè)混合0-1規(guī)劃問(wèn)題規(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ò)展練習(xí)題：建立線性規(guī)劃模型練習(xí)題：建立線性規(guī)劃模型練習(xí)題練習(xí)題 ：建立線性規(guī)劃模型：建立線性規(guī)劃模型n決策變量確定：（是否投資需要決策）決策變量確定：（是否投資需要決策） X11，X12，X21，X31 均為均為01變量變量n約束條件確定：約束條件確定：n第一種產(chǎn)品的方案一和方案二最多只能選一：第一種產(chǎn)品的方案一和方案二最多只能選一

15、： X11+X12 1n第二種產(chǎn)品、第三種產(chǎn)品可選也可不選：第二種產(chǎn)品、第三種產(chǎn)品可選也可不選： X21 1 ， X31 1n 全部投資額應(yīng)不超過(guò)全部投資額應(yīng)不超過(guò)550萬(wàn)萬(wàn) 300X11+280X12+260X21+240X31 550第一種產(chǎn)品第一種產(chǎn)品方案方案1 方案方案2X11 X12第二種產(chǎn)品第二種產(chǎn)品X21第三種產(chǎn)品第三種產(chǎn)品X31練習(xí)題：建立線性規(guī)劃模型練習(xí)題：建立線性規(guī)劃模型n目標(biāo)函數(shù)確定：每年的收益和最大 每年的總收益包含兩部分：n第一部分：項(xiàng)目投資收益，利用投資回收系數(shù)n第二部分：剩余資金的普通投資收益1)26. 01 ()26. 01 (26. 03124010.28)(

16、10.28)0.28(1X212601)28. 01 ()28. 01 (28. 0122801)3 . 01 ()3 . 01 (3 . 01130055555555XXX1) 1 . 01 () 1 . 01 ( 1 . 0)31240212601228011300(55055XXXX第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 n項(xiàng)任務(wù)（項(xiàng)任務(wù)（B1,B2,Bn)由由n個(gè)人個(gè)人 (A1,A2,An) 去完成，每項(xiàng)任務(wù)交給一人，每人只有一項(xiàng)任務(wù)。去完成，每項(xiàng)任務(wù)交給一人，每人只有一項(xiàng)任務(wù)。第第i個(gè)人個(gè)人Ai去做第去做第j項(xiàng)任務(wù)項(xiàng)任務(wù)Bj的工作效率（如工時(shí)、的工作效率（如工時(shí)、成本或價(jià)值等）為

17、成本或價(jià)值等）為Cij。問(wèn)如何安排人員使總工作。問(wèn)如何安排人員使總工作效率最好？效率最好？ 設(shè)設(shè)Xij表示表示Ai完成完成Bj工作，并令工作，并令 1 當(dāng)指派當(dāng)指派Ai去完成去完成Bj工作工作 Xij = 0 當(dāng)不指派當(dāng)不指派Ai去完成去完成Bj工作工作第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展n指派問(wèn)題數(shù)學(xué)模型的標(biāo)準(zhǔn)型 MIN Z = （Cij0) （i= 1,2,n) (j= 1,2,n) Xij 皆為 0 或 1 由 Cij 組成的方陣 C = ( Cij )nn 稱為效率矩陣 ninjCijXij11njXij11niXij11第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展n指派問(wèn)題標(biāo)準(zhǔn)型

18、的求解匈牙利法指派問(wèn)題標(biāo)準(zhǔn)型的求解匈牙利法n 指派問(wèn)題有以下性質(zhì)：指派問(wèn)題有以下性質(zhì)： 若從效率矩陣若從效率矩陣C C的任何一行（列）各元素中的任何一行（列）各元素中分別減去一個(gè)常數(shù)分別減去一個(gè)常數(shù)K K（K K可正可負(fù)）得到新矩可正可負(fù)）得到新矩陣陣D,D,則以則以D D為效率矩陣的指派問(wèn)題與原問(wèn)題為效率矩陣的指派問(wèn)題與原問(wèn)題有相同的解，但最優(yōu)值比原問(wèn)題最優(yōu)值小有相同的解，但最優(yōu)值比原問(wèn)題最優(yōu)值小K K。 用匈牙利法求解的條件：用匈牙利法求解的條件： MIN、i=j 、Cij0第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展n匈牙利法的主要步驟：匈牙利法的主要步驟： 第一步：變換效率矩陣，使在各行

19、各列都出現(xiàn)零元素。第一步：變換效率矩陣，使在各行各列都出現(xiàn)零元素。 1、從矩陣、從矩陣C的每行元素減去該行的最小元素；的每行元素減去該行的最小元素； 2、再?gòu)乃镁仃嚨拿苛兄袦p去該列最小元素。、再?gòu)乃镁仃嚨拿苛兄袦p去該列最小元素。 第二步：以最少數(shù)目的水平線和垂直線劃去所有的零元第二步：以最少數(shù)目的水平線和垂直線劃去所有的零元素。如果所用的直線等于行或列數(shù)，則結(jié)束指派。否則素。如果所用的直線等于行或列數(shù)，則結(jié)束指派。否則繼續(xù)。繼續(xù)。 第三步：找到?jīng)]有被劃去的最小的元素，所有第三步：找到?jīng)]有被劃去的最小的元素，所有被劃被劃中的元素中的元素這一最小值。而被這一最小值。而被的元素（該元的元素（該元

20、素行列都被劃中）則要素行列都被劃中）則要這一最小值。再返回到第一這一最小值。再返回到第一步。步。 第四步：最后根據(jù)零元素的位置，確定最優(yōu)分配方案。第四步：最后根據(jù)零元素的位置，確定最優(yōu)分配方案。第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 從產(chǎn)地到銷地之間運(yùn)送貨物的最佳路徑。從產(chǎn)地到銷地之間運(yùn)送貨物的最佳路徑。 多個(gè)產(chǎn)地和多個(gè)銷地；多個(gè)產(chǎn)地和多個(gè)銷地； 每個(gè)產(chǎn)地的產(chǎn)量不同，每個(gè)銷地的銷量也不同；每個(gè)產(chǎn)地的產(chǎn)量不同，每個(gè)銷地的銷量也不同； 各產(chǎn)銷兩地之間的運(yùn)價(jià)不同。各產(chǎn)銷兩地之間的運(yùn)價(jià)不同。 如何組織調(diào)運(yùn)，才能既滿足各銷地的要求，如何組織調(diào)運(yùn)，才能既滿足各銷地的要求，又使總的運(yùn)輸費(fèi)用（或里程、時(shí)間

21、等）最小。又使總的運(yùn)輸費(fèi)用（或里程、時(shí)間等）最小。第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 設(shè)有同一種貨物從m個(gè)出發(fā)地1，2，m運(yùn)往n個(gè)到達(dá)地1，2，n。第i個(gè)出發(fā)地的供應(yīng)量（Supply）為si（si0）， 第j個(gè)到達(dá)地的需求量（Demand）為 dj（dj0）。 每單位貨物從產(chǎn)地 i 運(yùn)到銷地 j 的運(yùn)價(jià)為Cij。求一個(gè)使總運(yùn)費(fèi)最小的運(yùn)輸方案。 1 2 3 n 供應(yīng)供應(yīng) 1 c11 c1n s1 2 c21 成本成本 c2n s2 cij m cm1 cmn sm 需求需求 d1 dn 出發(fā)地到達(dá)地第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展ninjCijXij11njiSXij1mijd

22、Xij1n產(chǎn)銷平衡的運(yùn)輸問(wèn)題模型產(chǎn)銷平衡的運(yùn)輸問(wèn)題模型 令令Xij為為 從從i i地運(yùn)到地運(yùn)到j(luò) j地的數(shù)量地的數(shù)量 MIN Z = （Cij0) ) （i= 1,2,m) i= 1,2,m) 供應(yīng)約束供應(yīng)約束 (j= 1,2,n) (j= 1,2,n) 需求約束需求約束 Xij0 由由 Cij、S Si、d dj 組成的組成的 (m+1)m+1)(n+1) (n+1) 矩陣矩陣稱為運(yùn)輸矩陣稱為運(yùn)輸矩陣第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展 實(shí)際決策值與目標(biāo)值之間的差異實(shí)際決策值與目標(biāo)值之間的差異決策值超過(guò)目標(biāo)值的部分決策值超過(guò)目標(biāo)值的部分決策值低于目標(biāo)值的部分決策值低于目標(biāo)值的部分 嚴(yán)格

23、滿足的等式或不等式約束嚴(yán)格滿足的等式或不等式約束把約束右端項(xiàng)看成是要追求的目標(biāo)值，把約束右端項(xiàng)看成是要追求的目標(biāo)值， 在達(dá)到此目標(biāo)時(shí)允許有正負(fù)偏差，線性規(guī)劃問(wèn)題在達(dá)到此目標(biāo)時(shí)允許有正負(fù)偏差，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差后的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差后可變換為目標(biāo)約束，也可將絕對(duì)約束變換為目標(biāo)可變換為目標(biāo)約束，也可將絕對(duì)約束變換為目標(biāo)約束。約束。第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展要達(dá)到的多個(gè)目標(biāo)之間有主次、輕重緩急要達(dá)到的多個(gè)目標(biāo)之間有主次、輕重緩急之分，因此各目標(biāo)之間有優(yōu)先等級(jí)。凡第一位要達(dá)到的目標(biāo)賦予等級(jí)之分，因此各目標(biāo)之間有優(yōu)先等級(jí)。凡第一位要達(dá)

24、到的目標(biāo)賦予等級(jí)系數(shù)系數(shù)P1,次位的賦予等級(jí)系數(shù)次位的賦予等級(jí)系數(shù)P2，以此類推；并規(guī)定，以此類推；并規(guī)定PkPk+1, Pk比比Pk+1更大的優(yōu)先權(quán)。相同等級(jí)的以不同的權(quán)系數(shù)更大的優(yōu)先權(quán)。相同等級(jí)的以不同的權(quán)系數(shù)加以區(qū)別。加以區(qū)別。 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各目標(biāo)約束的目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目標(biāo)值確定正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值，因此目標(biāo)規(guī)劃的目標(biāo)函后，決策者的要求是盡可能縮小偏離目標(biāo)值，因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是數(shù)只能是 MIN Z = f f（d+,d- )

25、 )。 要求恰好達(dá)到目標(biāo)值（正負(fù)偏差都要盡可能地小），這時(shí)要求恰好達(dá)到目標(biāo)值（正負(fù)偏差都要盡可能地小），這時(shí) MIN Z = f f（d+ d- ) ) 要求不超過(guò)目標(biāo)值（允許達(dá)不到，正偏差要盡可能地?。┮蟛怀^(guò)目標(biāo)值（允許達(dá)不到，正偏差要盡可能地?。?MIN Z = f f（d+ ) ) 要求不低于目標(biāo)值：要求不低于目標(biāo)值： MIN Z = f f（d- ) )運(yùn)輸與目標(biāo)規(guī)劃練習(xí)：運(yùn)輸與目標(biāo)規(guī)劃練習(xí)：有三個(gè)產(chǎn)地給四個(gè)銷地供應(yīng)某產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價(jià)（有三個(gè)產(chǎn)地給四個(gè)銷地供應(yīng)某產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價(jià)（C Cij）如下：）如下： 銷地銷地產(chǎn)地產(chǎn)地B1B1B2B2B3B3

26、B4B4產(chǎn)量產(chǎn)量(S(Si) )A1A1A2A2A3A35 53 34 42 25 55 56 64 42 27 76 63 3300300200200400400銷量銷量(D(Dj) )200200100100400400200200900900要求：要求：1 1）建立此運(yùn)輸問(wèn)題的線性規(guī)劃模型）建立此運(yùn)輸問(wèn)題的線性規(guī)劃模型( (用矩陣的形式簡(jiǎn)化表示用矩陣的形式簡(jiǎn)化表示) )； 2 2）由于市場(chǎng)情況的變化，）由于市場(chǎng)情況的變化，B3 B3 和和 B4 B4 的銷量各增加了的銷量各增加了5050單位（可求得此時(shí)最單位（可求得此時(shí)最 小運(yùn)費(fèi)為小運(yùn)費(fèi)為29502950元）。由于生產(chǎn)能力無(wú)法再提升，因

27、此有關(guān)部門在研究調(diào)運(yùn)元）。由于生產(chǎn)能力無(wú)法再提升，因此有關(guān)部門在研究調(diào)運(yùn) 方案時(shí)需依次考慮以下情況（已規(guī)定其優(yōu)先等級(jí)方案時(shí)需依次考慮以下情況（已規(guī)定其優(yōu)先等級(jí) P1P1P3P3）：）： P1: A3P1: A3向向B1B1提供的產(chǎn)量不少于提供的產(chǎn)量不少于100100； P2: P2: 給給B1B1和和B3B3的供應(yīng)需求率要相等；的供應(yīng)需求率要相等； P3: P3: 總運(yùn)費(fèi)增加不超過(guò)最小調(diào)運(yùn)方案費(fèi)用的總運(yùn)費(fèi)增加不超過(guò)最小調(diào)運(yùn)方案費(fèi)用的1010。 試建立求解滿意調(diào)運(yùn)方案的目標(biāo)規(guī)劃模型（不需要化簡(jiǎn)整理）。試建立求解滿意調(diào)運(yùn)方案的目標(biāo)規(guī)劃模型（不需要化簡(jiǎn)整理）。 運(yùn)輸與目標(biāo)規(guī)劃練習(xí)：運(yùn)輸與目標(biāo)規(guī)劃練習(xí)

28、：n產(chǎn)銷平衡，運(yùn)輸問(wèn)題模型 令Xij為 從i地運(yùn)到j(luò)地的數(shù)量 目標(biāo)函數(shù)： MIN Z = （Cij0) 約束條件： （i= 1,2,3) i= 1,2,3) 供應(yīng)約束供應(yīng)約束 (j= 1,2,3,4) (j= 1,2,3,4) 需求約束需求約束 Xij03141ijCijXij41jiSXij31ijDXij運(yùn)輸與目標(biāo)規(guī)劃練習(xí)：運(yùn)輸與目標(biāo)規(guī)劃練習(xí)：n供應(yīng)絕對(duì)約束：供應(yīng)絕對(duì)約束： i=1,2,3i=1,2,3n目標(biāo)約束條件：目標(biāo)約束條件： j=1,2,3,4 j=1,2,3,4 需求目標(biāo)約需求目標(biāo)約束束n目標(biāo)函數(shù)：目標(biāo)函數(shù)：41jiSXij31ijDdjdjXij0%)101 (2950:045

29、0200:100:773141366332313312111255311dXddXCPddXXXXXXPddXPijijij，非負(fù)約束：7366251)(mindPddPdPZ第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展決策決策1決策決策2決策決策3決策決策n1狀態(tài)狀態(tài)123n狀態(tài)狀態(tài)n狀態(tài)狀態(tài)4狀態(tài)狀態(tài)3狀態(tài)狀態(tài)2階段階段1階段階段2階段階段3階段階段n第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展表示決策順序的離散量，階段可按時(shí)間或空間劃分。表示決策順序的離散量，階段可按時(shí)間或空間劃分。能確定地表示決策過(guò)程當(dāng)前特征的量。狀態(tài)可以是數(shù)能確定地表示決策過(guò)程當(dāng)前特征的量。狀態(tài)可以是數(shù)量也可以是字符，數(shù)

30、量狀態(tài)可以是連續(xù)的也可以是離散的。量也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的也可以是離散的。表示每一狀態(tài)可以取不同值的變量。表示每一狀態(tài)可以取不同值的變量。：從某一狀態(tài)向下一狀態(tài)過(guò)渡時(shí)所做的選擇。決策是所：從某一狀態(tài)向下一狀態(tài)過(guò)渡時(shí)所做的選擇。決策是所在狀態(tài)變量的函數(shù)，記為在狀態(tài)變量的函數(shù)，記為d (X )。在狀態(tài)在狀態(tài)X 下，允許采取決策的全體。下，允許采取決策的全體。某一狀態(tài)以及該狀態(tài)下的決策，某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。與下一狀態(tài)之間的函數(shù)關(guān)系。第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展動(dòng)態(tài)規(guī)劃作業(yè)動(dòng)態(tài)規(guī)劃作業(yè)第四章第四章 線性規(guī)劃的擴(kuò)展線性規(guī)劃的擴(kuò)展S1=2S4=0

31、S3=2S3=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時(shí)序順序時(shí)間時(shí)序順序時(shí)間n時(shí)序規(guī)劃時(shí)序規(guī)劃 多項(xiàng)任務(wù)等待同一人或物處理，每項(xiàng)多項(xiàng)任務(wù)等待同一人或物處理，每項(xiàng)任務(wù)的單獨(dú)完成的時(shí)間確定，且沒(méi)有先任務(wù)的單獨(dú)完成的時(shí)間確定，且沒(méi)有先后關(guān)系（緊前、緊后）。怎樣安排各項(xiàng)后關(guān)系（緊前、緊后）。怎樣安排各項(xiàng)任務(wù)的順序，使總效率最高？任務(wù)的順序，使總效率最高？n系統(tǒng)時(shí)間加工時(shí)間排隊(duì)時(shí)間系統(tǒng)時(shí)間加工時(shí)間排隊(duì)時(shí)間

32、n平均排隊(duì)（等待）時(shí)間最短問(wèn)題平均排隊(duì)（等待）時(shí)間最短問(wèn)題 加工時(shí)間最短者優(yōu)先加工時(shí)間最短者優(yōu)先 （相同時(shí)間的可任意安排）（相同時(shí)間的可任意安排）n平均延誤時(shí)間最短問(wèn)題平均延誤時(shí)間最短問(wèn)題 最先到期的工作優(yōu)先最先到期的工作優(yōu)先n時(shí)序規(guī)劃擴(kuò)展（約翰遜原則）：時(shí)序規(guī)劃擴(kuò)展（約翰遜原則）： 兩臺(tái)順序機(jī)器完成一批工作兩臺(tái)順序機(jī)器完成一批工作 每項(xiàng)工作在機(jī)器每項(xiàng)工作在機(jī)器1和機(jī)器和機(jī)器2上的加工時(shí)間不上的加工時(shí)間不一樣，如何使系統(tǒng)效率最高？一樣，如何使系統(tǒng)效率最高？ 3214機(jī)器機(jī)器1機(jī)器機(jī)器2工作工作n約翰遜原則約翰遜原則 找出各臺(tái)機(jī)器上加工時(shí)間最短的一項(xiàng)工作，找出各臺(tái)機(jī)器上加工時(shí)間最短的一項(xiàng)工作，

33、如果在機(jī)器如果在機(jī)器1上，這項(xiàng)工作最先做；上，這項(xiàng)工作最先做； 如果在機(jī)器如果在機(jī)器2上，這項(xiàng)工作最后做；上，這項(xiàng)工作最后做； 不斷重復(fù)，從兩端往內(nèi)排。相同時(shí)間可任選不斷重復(fù)，從兩端往內(nèi)排。相同時(shí)間可任選一一 個(gè)，一般先安排機(jī)器個(gè)，一般先安排機(jī)器1上工作。上工作。n最小樹最小樹 一個(gè)網(wǎng)絡(luò)中有很多樹，其中邊的長(zhǎng)度一個(gè)網(wǎng)絡(luò)中有很多樹，其中邊的長(zhǎng)度（權(quán)數(shù)）之和為最小的樹為最小樹。（權(quán)數(shù)）之和為最小的樹為最小樹。n最小樹的獲取破圈法最小樹的獲取破圈法 從圖中任取一個(gè)圈，去掉該圈的一條最從圖中任取一個(gè)圈，去掉該圈的一條最大邊，將此圈破去，然后重復(fù)破圈，直大邊，將此圈破去，然后重復(fù)破圈，直至無(wú)圈為止至無(wú)圈

34、為止。 n通過(guò)一個(gè)網(wǎng)絡(luò)的最短路徑通過(guò)一個(gè)網(wǎng)絡(luò)的最短路徑n問(wèn)題問(wèn)題 在一個(gè)網(wǎng)絡(luò)中，給定一個(gè)始點(diǎn)在一個(gè)網(wǎng)絡(luò)中，給定一個(gè)始點(diǎn)Vs，和一個(gè)，和一個(gè)終點(diǎn)終點(diǎn)Vt，求，求Vs 到到Vt的一條路，使路長(zhǎng)最短。的一條路，使路長(zhǎng)最短。n求解求解 能劃分階段的，可采用動(dòng)態(tài)規(guī)劃方法。能劃分階段的，可采用動(dòng)態(tài)規(guī)劃方法。 不能分階段的，采用不能分階段的，采用狄克斯屈狄克斯屈方法。方法。n狄克斯屈狄克斯屈方法方法n開始節(jié)點(diǎn)標(biāo)永久標(biāo)記開始節(jié)點(diǎn)標(biāo)永久標(biāo)記0,S,其余臨時(shí)其余臨時(shí)T,-n找出與開始節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)，為每一個(gè)設(shè)標(biāo)記找出與開始節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)，為每一個(gè)設(shè)標(biāo)記L,1，其中，其中L值最小的節(jié)點(diǎn)標(biāo)記右上角標(biāo)上值最小的

35、節(jié)點(diǎn)標(biāo)記右上角標(biāo)上*，使之成，使之成為永久標(biāo)志。為永久標(biāo)志。n從新的永久標(biāo)志開始，找出從此節(jié)點(diǎn)出發(fā)可到達(dá)的所有從新的永久標(biāo)志開始，找出從此節(jié)點(diǎn)出發(fā)可到達(dá)的所有節(jié)點(diǎn)，計(jì)算這些節(jié)點(diǎn)的最短距離（現(xiàn)有距離和經(jīng)新的永節(jié)點(diǎn)，計(jì)算這些節(jié)點(diǎn)的最短距離（現(xiàn)有距離和經(jīng)新的永久標(biāo)志到達(dá)的距離的小的一個(gè)值），保持、新設(shè)或更改久標(biāo)志到達(dá)的距離的小的一個(gè)值），保持、新設(shè)或更改這些節(jié)點(diǎn)的標(biāo)志為這些節(jié)點(diǎn)的標(biāo)志為 最短距離，最短路徑上前一節(jié)點(diǎn)標(biāo)最短距離，最短路徑上前一節(jié)點(diǎn)標(biāo)號(hào)號(hào)，比較圖中所有沒(méi)有，比較圖中所有沒(méi)有*的標(biāo)記（臨時(shí)性標(biāo)記），找出的標(biāo)記（臨時(shí)性標(biāo)記），找出距離最短的一個(gè)節(jié)點(diǎn)，使之成為永久性標(biāo)記。重復(fù)這一距離最短的一個(gè)

36、節(jié)點(diǎn)，使之成為永久性標(biāo)記。重復(fù)這一步，直到所有的節(jié)點(diǎn)都成為永久性標(biāo)志為止。步，直到所有的節(jié)點(diǎn)都成為永久性標(biāo)志為止。kijDi,mLijDj,k從從i-j時(shí)：時(shí)： 如果如果Di+LijDj,則不改變則不改變j的標(biāo)記；的標(biāo)記； 如果如果Di+LijDj，則改為，則改為Di+Lij,i狄克斯屈狄克斯屈方法方法最短路徑問(wèn)題的應(yīng)用n例56：設(shè)備更新問(wèn)題 某廠使用一種設(shè)備，每年年初設(shè)備科需要對(duì)該設(shè)備的更新與否作出決策。若購(gòu)置新設(shè)備，就要支付購(gòu)置費(fèi)；如果繼續(xù)使用則需要支付維修費(fèi)，設(shè)備使用的年數(shù)越長(zhǎng)，每年所需的維修費(fèi)越多?，F(xiàn)若第一年年初購(gòu)置了一臺(tái)新設(shè)備，問(wèn)在5年內(nèi)如何制定設(shè)備更新計(jì)劃，以便使新設(shè)備購(gòu)置費(fèi)和維修

37、費(fèi)的總費(fèi)用最??？已知設(shè)備在5年內(nèi)各年年初的價(jià)格及設(shè)備使用不同年數(shù)的維修費(fèi)如下：最短路徑問(wèn)題的應(yīng)用n例56：設(shè)備更新問(wèn)題 把求總費(fèi)用最小問(wèn)題化為最短路徑問(wèn)題。用點(diǎn) i (i=1,2,3,4,5)表示第 i 年買進(jìn)一臺(tái)新設(shè)備。增設(shè)一點(diǎn) 6 表示第五年末。從i點(diǎn)到i+1, 6 各畫一條弧，?。╥ , j）表示在第 i 年買進(jìn)的設(shè)備一直使用到第 j 年年初（第 j 1年年末）。求1點(diǎn)到6點(diǎn)的最短路徑。路徑的權(quán)數(shù)為購(gòu)買和維修費(fèi)用。 ?。╥ , j）的權(quán)數(shù)為第i年的購(gòu)置費(fèi)ai從第i年使用至第j-1年末的維修費(fèi)之和。 從第i年使用至第j-1年末的維修費(fèi)：b1+bj-i （使用壽命為j-i年） 如：（24）權(quán)

38、數(shù)為：a2+b1+b2=1156=22 具體權(quán)數(shù)計(jì)算結(jié)果如下：通過(guò)一個(gè)網(wǎng)絡(luò)的最短路徑n例例56 設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題 ：使用使用Dijstra算法，上述問(wèn)題最短路為算法，上述問(wèn)題最短路為1-3-6或或1-4-6 即：第即：第1、3年年初購(gòu)買設(shè)備，或第年年初購(gòu)買設(shè)備，或第1、4年年初購(gòu)買設(shè)備年年初購(gòu)買設(shè)備 五年最佳總費(fèi)用為五年最佳總費(fèi)用為53。132546162217182330594117301623413122通過(guò)一個(gè)網(wǎng)絡(luò)的最大流量通過(guò)一個(gè)網(wǎng)絡(luò)的最大流量n最大流量問(wèn)題最大流量問(wèn)題 在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中從開始點(diǎn)在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中從開始點(diǎn)到結(jié)束點(diǎn)之間的某種物資流的流量達(dá)到到結(jié)束

39、點(diǎn)之間的某種物資流的流量達(dá)到最大的問(wèn)題。限制條件是每一條邊的最最大的問(wèn)題。限制條件是每一條邊的最大通過(guò)能力（流量）不等。但有多條路大通過(guò)能力（流量）不等。但有多條路n最大流量求解最大流量求解n線性規(guī)劃方法線性規(guī)劃方法n福特富爾克遜標(biāo)號(hào)法（福特富爾克遜標(biāo)號(hào)法（“分步流動(dòng)分步流動(dòng)”） 最大流量的線性規(guī)劃模型最大流量的線性規(guī)劃模型n例例57：有下列石油運(yùn)輸管道圖。某公司欲采用這個(gè)有下列石油運(yùn)輸管道圖。某公司欲采用這個(gè)網(wǎng)絡(luò)圖從網(wǎng)絡(luò)圖從1地向銷地地向銷地7運(yùn)送原油，弧的容量運(yùn)送原油，弧的容量Cij（萬(wàn)升（萬(wàn)升/時(shí)）時(shí)）已給定（因管道直徑的變化，已給定（因管道直徑的變化，Cij不完全相同）。問(wèn)如何不完全相

40、同）。問(wèn)如何安排輸送，方能使每小時(shí)運(yùn)送的原油最多？安排輸送，方能使每小時(shí)運(yùn)送的原油最多？62321256432最大流量的線性規(guī)劃模型最大流量的線性規(guī)劃模型n設(shè)?。ㄔO(shè)?。╥,j）上的流量為）上的流量為Fij, 總流量為總流量為F.n目標(biāo)函數(shù)：目標(biāo)函數(shù)：MAX F=F12+F14n約束條件：約束條件： 流入流出流入流出; FijCij; Fij0 2點(diǎn)：點(diǎn)：F12=F23+F25; 4點(diǎn)：點(diǎn)：F14=F43+F46+F47 3點(diǎn)：點(diǎn)：F23+F43=F35+F36; 5點(diǎn)點(diǎn) ：F25+F35F57 6點(diǎn)：點(diǎn)：F36+F46F67 ; 7點(diǎn)：點(diǎn)：F47+F57+F67=F12+F14n解：解：F12

41、=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2 F36=2;F57=5;F67=3 最大流量最大流量F1062321256432思考題：最小費(fèi)用最大流思考題：最小費(fèi)用最大流n如果?。ㄈ绻。╥,j）上的單位流量費(fèi)用為）上的單位流量費(fèi)用為Bij (百元百元/萬(wàn)升）。萬(wàn)升）。 圖中每一條弧的權(quán)數(shù)前一位為流量限制圖中每一條弧的權(quán)數(shù)前一位為流量限制Cij，后一位為單位費(fèi)，后一位為單位費(fèi)Bij。n怎樣運(yùn)送才能使運(yùn)送最多的石油并使總的費(fèi)用最?。吭鯓舆\(yùn)送才能使運(yùn)送最多的石油并使總的費(fèi)用最?。縩提示：先求得最大提示：先求得最大F值；再求總流量為值；再求總流量為F時(shí)使總

42、費(fèi)用最小的方案。時(shí)使總費(fèi)用最小的方案。n進(jìn)一步思考：進(jìn)一步思考： 1）求最小費(fèi)用問(wèn)題，如何求每小時(shí)運(yùn)送）求最小費(fèi)用問(wèn)題，如何求每小時(shí)運(yùn)送6萬(wàn)升原油的最萬(wàn)升原油的最 小費(fèi)用？小費(fèi)用？ 2）Cij為兩節(jié)點(diǎn)之間的距離時(shí)，求節(jié)點(diǎn)為兩節(jié)點(diǎn)之間的距離時(shí)，求節(jié)點(diǎn)1到節(jié)點(diǎn)到節(jié)點(diǎn)7的最短距離？的最短距離？ 6,32,53,22,31,32,85,76,64,43,42,4n標(biāo)記：標(biāo)記：流入節(jié)點(diǎn)的流量，該流量的來(lái)源節(jié)點(diǎn)流入節(jié)點(diǎn)的流量，該流量的來(lái)源節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)標(biāo)記第一個(gè)節(jié)點(diǎn)標(biāo)記，S。n選取已有標(biāo)記的一個(gè)節(jié)點(diǎn)，找出從此節(jié)點(diǎn)能直選取已有標(biāo)記的一個(gè)節(jié)點(diǎn)，找出從此節(jié)點(diǎn)能直接到達(dá)的一個(gè)節(jié)點(diǎn)，確定到達(dá)節(jié)點(diǎn)的最大流量，接到達(dá)

43、的一個(gè)節(jié)點(diǎn)，確定到達(dá)節(jié)點(diǎn)的最大流量，相應(yīng)地標(biāo)上標(biāo)記。重復(fù)這一步，盡快到達(dá)終點(diǎn)，相應(yīng)地標(biāo)上標(biāo)記。重復(fù)這一步，盡快到達(dá)終點(diǎn)，得到一條從起點(diǎn)到終點(diǎn)的路徑，此路徑的最大得到一條從起點(diǎn)到終點(diǎn)的路徑，此路徑的最大流量為流入終點(diǎn)的流量。將此路徑上的每一邊流量為流入終點(diǎn)的流量。將此路徑上的每一邊的流動(dòng)能力減去此流量。再?gòu)钠鹗脊?jié)點(diǎn)開始，的流動(dòng)能力減去此流量。再?gòu)钠鹗脊?jié)點(diǎn)開始，按新的流動(dòng)能力，重新進(jìn)行標(biāo)號(hào)，找出新的一按新的流動(dòng)能力，重新進(jìn)行標(biāo)號(hào)，找出新的一條途徑和流量，重復(fù)進(jìn)行下去，直到把所有可條途徑和流量，重復(fù)進(jìn)行下去，直到把所有可能的路徑全部找到為止，全部路徑的流量和即能的路徑全部找到為止，全部路徑的流量和即

44、為通過(guò)該網(wǎng)絡(luò)的最大流量。為通過(guò)該網(wǎng)絡(luò)的最大流量。福特富爾克遜標(biāo)號(hào)法：福特富爾克遜標(biāo)號(hào)法：ijFi,KFj,imijFj=min(Fi,mij)福特富爾克遜標(biāo)號(hào)法：福特富爾克遜標(biāo)號(hào)法：第七章第七章 決策分析決策分析n風(fēng)險(xiǎn)決策風(fēng)險(xiǎn)決策n存在幾種自然狀態(tài)，哪一種狀態(tài)發(fā)生不確定，存在幾種自然狀態(tài)，哪一種狀態(tài)發(fā)生不確定，但每種自然狀態(tài)發(fā)生的可能性可以預(yù)計(jì)（主但每種自然狀態(tài)發(fā)生的可能性可以預(yù)計(jì)（主觀概率值）。觀概率值）。n決策依據(jù)：最大期望收益、最小期望損失標(biāo)決策依據(jù)：最大期望收益、最小期望損失標(biāo)準(zhǔn)準(zhǔn)n期望值：不同自然狀態(tài)下可能得到的值期望值：不同自然狀態(tài)下可能得到的值 期望值期望值（概率（概率結(jié)果值）結(jié)

45、果值）n決策方法：最大期望計(jì)算、條件概率、決策決策方法：最大期望計(jì)算、條件概率、決策樹、效用曲線分析樹、效用曲線分析第七章第七章 決策分析決策分析n最大期望收益值計(jì)算 i為備擇方案，i=1,2,n j為自然狀態(tài)，j=1,2,m 為為第i個(gè)備擇方案的期望收益值 pj為第j個(gè)自然狀態(tài)出現(xiàn)的概率 Oij為第i個(gè)備擇方案在第j個(gè)自然狀態(tài)下的收益 Vi0 為第i個(gè)備擇方案的初始投資值01)(iijmjjiVOpE iE第七章第七章 決策分析決策分析n風(fēng)險(xiǎn)的衡量 當(dāng)備擇方案的期望收益值相等時(shí)，需計(jì)算風(fēng)險(xiǎn)值。風(fēng)險(xiǎn)應(yīng)盡可能地小。 為第i個(gè)備擇方案的風(fēng)險(xiǎn) mjjiijipEO12)( 第七章第七章 決策分析決策

46、分析n決策樹結(jié)構(gòu)決策樹結(jié)構(gòu) 狀態(tài)狀態(tài)節(jié)點(diǎn)節(jié)點(diǎn)狀態(tài)狀態(tài)節(jié)點(diǎn)節(jié)點(diǎn)收益收益收益收益收益收益收益收益概率枝概率枝方案枝方案枝概率值概率值概率值概率值概率值概率值概率值概率值第七章第七章 決策分析決策分析n利用決策樹決策利用決策樹決策 繪出決策樹繪出決策樹 預(yù)計(jì)各狀態(tài)概率預(yù)計(jì)各狀態(tài)概率 從右向左計(jì)算各個(gè)方案的收益期望從右向左計(jì)算各個(gè)方案的收益期望 根據(jù)期望值大小選擇方案根據(jù)期望值大小選擇方案n決策樹求解多階段決策問(wèn)題決策樹求解多階段決策問(wèn)題第七章第七章 決策分析決策分析n貝葉斯決策貝葉斯決策 自然狀態(tài)出現(xiàn)的概率估計(jì)的正確程度直自然狀態(tài)出現(xiàn)的概率估計(jì)的正確程度直接影響到?jīng)Q策中收益期望值。在條件許接影響到?jīng)Q

47、策中收益期望值。在條件許可的情況下，往往需要補(bǔ)充新信息。獲可的情況下，往往需要補(bǔ)充新信息。獲得補(bǔ)充信息需支付一定的費(fèi)用。根據(jù)獲得補(bǔ)充信息需支付一定的費(fèi)用。根據(jù)獲得的新信息修正原先對(duì)自然狀態(tài)出現(xiàn)的得的新信息修正原先對(duì)自然狀態(tài)出現(xiàn)的概率的估計(jì)值，并利用修正的概率重新概率的估計(jì)值，并利用修正的概率重新進(jìn)行決策。修正概率主要利用貝葉斯定進(jìn)行決策。修正概率主要利用貝葉斯定理。理。 第七章第七章 決策分析決策分析n貝葉斯決策過(guò)程貝葉斯決策過(guò)程 先驗(yàn)分析先驗(yàn)分析n根據(jù)資料及經(jīng)驗(yàn)對(duì)各自然狀態(tài)出現(xiàn)的概率作出估根據(jù)資料及經(jīng)驗(yàn)對(duì)各自然狀態(tài)出現(xiàn)的概率作出估 計(jì)，稱為先驗(yàn)概率；計(jì)，稱為先驗(yàn)概率；n根據(jù)先驗(yàn)概率可作出決策

48、，得到最優(yōu)期望值，記根據(jù)先驗(yàn)概率可作出決策，得到最優(yōu)期望值，記為為 EMV*。 預(yù)驗(yàn)分析預(yù)驗(yàn)分析n補(bǔ)充信息的成本收益分析補(bǔ)充信息的成本收益分析 后驗(yàn)分析后驗(yàn)分析n獲取條件概率，運(yùn)用貝葉斯定理對(duì)先驗(yàn)概率進(jìn)行獲取條件概率，運(yùn)用貝葉斯定理對(duì)先驗(yàn)概率進(jìn)行修正，得到后驗(yàn)概率；修正，得到后驗(yàn)概率；n根據(jù)后驗(yàn)概率作出決策，計(jì)算補(bǔ)充信息的價(jià)值。根據(jù)后驗(yàn)概率作出決策，計(jì)算補(bǔ)充信息的價(jià)值。第七章第七章 決策分析決策分析n預(yù)驗(yàn)分析n信息的價(jià)值在于它能提高決策的最大期望值。但獲取信息的費(fèi)用超過(guò)它所能提高的期望收益就不合算了。n所有信息中最好、最理想的信息自然是完全可靠、準(zhǔn)確的信息，這種信息預(yù)報(bào)某自然狀態(tài)出現(xiàn)，則在實(shí)際

49、中必定出現(xiàn)這自然狀態(tài)，這種信息稱為完備信息。n補(bǔ)充信息費(fèi)用應(yīng)遠(yuǎn)小于完備信息的價(jià)值（上限）。n當(dāng)完全信息預(yù)報(bào)出現(xiàn)第K個(gè)自然狀態(tài)出現(xiàn)時(shí)，最優(yōu)方案由 MAXUkjj 確定。n在完備信息下，決策所能獲得的最大期望收益值：n ERPI與EMV*之間的差額就是得到完全信息而使期望值增加的部分，即為完備信息價(jià)值EVPI。max1jijmiiuPERPI 第七章第七章 決策分析決策分析n后驗(yàn)分析n補(bǔ)充新信息，通過(guò)對(duì)X1,X2,XS共S個(gè)狀態(tài)的調(diào)查，獲得實(shí)際出現(xiàn)自然狀態(tài)i而預(yù)報(bào)Xj的概率，即：P(Xj|i)。n在已知先驗(yàn)概率P(j)(j=1,2,m)及條件概率P(Xj|i)(j=1,2,s;i=1,2,m)的基

50、礎(chǔ)上，利用貝葉斯定理計(jì)算修正概率，即后驗(yàn)概率：n根據(jù)后驗(yàn)概率，計(jì)算各方案的期望收益值，并依據(jù)期望收益值，重新作出決策(最大期望收益)。n計(jì)算獲得補(bǔ)充信息后，最大期望收益的實(shí)際增量。 mjjijjijijXPPXPPXP1)|()()|()()|( 第七章第七章 決策分析決策分析n后驗(yàn)分析計(jì)算的表格形式I 先驗(yàn)狀態(tài)概率先驗(yàn)狀態(tài)概率 P(j j)II 條件概率條件概率 P(Xi|P(Xi|j)j)III P(j j) P( (Xi i| |j)j)X1, , Xi i, , XS SX1, , Xi i, , XS S1 : P(1 1) , P(Xi|P(Xi|1),.1),., P(1 1)

51、P(Xi|P(Xi|1), .1), .2 : P(2 2) , P(Xi|P(Xi|2), 2), , P(2 2) P(Xi|P(Xi|2), .2), . m : P(m m) , P(Xi| , P(Xi|m), m), , P(m m) P(Xi|P(Xi|m), .m), . 對(duì)第對(duì)第III部分的每一列求和部分的每一列求和P(X1), , P(Xi) , , P(Xm)后驗(yàn)概率后驗(yàn)概率: 1P(1 1|X1), , P(1 1|Xi), P(j j|Xi)= 2 P(j j) P( (Xi i| |j)/ j)/ P(Xi) mP(2 2|X1), , P(2 2|Xi),P(m

52、m|X1), , P(m m|Xi),風(fēng)險(xiǎn)型決策風(fēng)險(xiǎn)型決策貝葉斯決策作業(yè)：貝葉斯決策作業(yè)： 假定天氣是影響某工程項(xiàng)目能否按期完工的假定天氣是影響某工程項(xiàng)目能否按期完工的決定因素，如果天氣好，工程能按期完工，施決定因素，如果天氣好，工程能按期完工，施工單位能獲利工單位能獲利5萬(wàn)元；如果天氣不好，不能按萬(wàn)元；如果天氣不好，不能按期完工，則要罰款期完工，則要罰款1萬(wàn)元；但如不施工則要損萬(wàn)元；但如不施工則要損失人工費(fèi)失人工費(fèi)0.2萬(wàn)元。根據(jù)過(guò)去的經(jīng)驗(yàn)，在計(jì)劃萬(wàn)元。根據(jù)過(guò)去的經(jīng)驗(yàn)，在計(jì)劃期內(nèi)天氣好的可能性為期內(nèi)天氣好的可能性為30。為更好地掌握天。為更好地掌握天氣情況，可請(qǐng)氣象部門作進(jìn)一步的預(yù)報(bào)，需支氣

53、情況，可請(qǐng)氣象部門作進(jìn)一步的預(yù)報(bào)，需支付信息費(fèi)付信息費(fèi)0.08萬(wàn)元。從所提供的預(yù)報(bào)信息可知，萬(wàn)元。從所提供的預(yù)報(bào)信息可知，氣象部門對(duì)好天氣的預(yù)測(cè)準(zhǔn)確性為氣象部門對(duì)好天氣的預(yù)測(cè)準(zhǔn)確性為80，對(duì)壞，對(duì)壞天氣的預(yù)報(bào)準(zhǔn)確性為天氣的預(yù)報(bào)準(zhǔn)確性為90。問(wèn)該如何進(jìn)行決策？。問(wèn)該如何進(jìn)行決策？貝葉斯決策作業(yè)貝葉斯決策作業(yè)n先驗(yàn)分析：先驗(yàn)分析： 好天氣好天氣1 1（0.3) 0.3) 壞天氣壞天氣2 2（0.7) EMV0.7) EMV 施工施工 5 5 1 0.81 0.8 不施工不施工 0.2 0.2 0.2 0.2 0.20.2 EMV EMV* * = 0.8 = 0.8 施工有利，期望收益施工有利，期

54、望收益0.80.8萬(wàn)元萬(wàn)元n預(yù)驗(yàn)分析：預(yù)驗(yàn)分析： 完備信息最大期望收益完備信息最大期望收益 ERPI=0.3ERPI=0.3* *5 50.70.7* *(-0.2)(-0.2) =1.36 ( =1.36 (萬(wàn)元）萬(wàn)元） 完備信息價(jià)值完備信息價(jià)值 EVPI=1.36 - 0.8 = 0.56 (EVPI=1.36 - 0.8 = 0.56 (萬(wàn)元萬(wàn)元) ) EVPI EVPI遠(yuǎn)大于收集信息成本遠(yuǎn)大于收集信息成本(0.08),(0.08),初步認(rèn)為合算。初步認(rèn)為合算。貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗(yàn)分析：后驗(yàn)分析： 氣象中心提供預(yù)報(bào)兩種天氣狀態(tài)：好氣象中心提供預(yù)報(bào)兩種天氣狀態(tài)：好(X1),壞

55、壞(X2) (補(bǔ)充信息的自然狀態(tài)與原自然狀態(tài)一致補(bǔ)充信息的自然狀態(tài)與原自然狀態(tài)一致)n補(bǔ)充信息概率補(bǔ)充信息概率 好天氣預(yù)報(bào)準(zhǔn)確性為好天氣預(yù)報(bào)準(zhǔn)確性為80，壞天氣預(yù)報(bào)準(zhǔn)確性為，壞天氣預(yù)報(bào)準(zhǔn)確性為90 P(X1| 1)=0.8 實(shí)際是好天氣預(yù)報(bào)也是好天氣實(shí)際是好天氣預(yù)報(bào)也是好天氣 P(X2| 1)=0.2 實(shí)際是好天氣預(yù)報(bào)且是壞天氣實(shí)際是好天氣預(yù)報(bào)且是壞天氣 P(X1| 2)=0.1 實(shí)際是壞天氣預(yù)報(bào)且是好天氣實(shí)際是壞天氣預(yù)報(bào)且是好天氣 P(X2| 2)=0.9 實(shí)際是壞天氣預(yù)報(bào)也是壞天氣實(shí)際是壞天氣預(yù)報(bào)也是壞天氣貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗(yàn)分析概率計(jì)算的表格形式：n后驗(yàn)決策： 預(yù)報(bào)天氣好（

56、X1），每個(gè)方案的最大期望收益EMV 好天氣1|X1（0.77) 壞天氣2|X1（0.23) EMV 施工 5 1 3.62* 不施工 0.2 0.2 0.2I 先驗(yàn)狀態(tài)概率先驗(yàn)狀態(tài)概率 P(j j) II 條件概率條件概率 P(Xi|P(Xi|j)j)III P(j j) P( (Xi i| |j)j)好天氣好天氣 X1, 壞天氣壞天氣 X2 X1, X2好天氣好天氣1 : 0.3 0.8 0.2 0.24 0.06 0.24 0.06壞天氣壞天氣2 : 0.7 0.1 0.9 0.07 0.63 0.07 0.63全概率全概率P(Xi):P(Xi): 對(duì)第對(duì)第III部分每一列求和部分每一列

57、求和 0.31 0.69后驗(yàn)概率后驗(yàn)概率P(j j|Xi) : 1 0.77 0.09 P(j j) P( (Xi i| |j)/ j)/ P(Xi) 2 0.23 0.91貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗(yàn)決策：后驗(yàn)決策： 預(yù)報(bào)天氣壞（預(yù)報(bào)天氣壞（X2），每個(gè)方案的最大期望收益），每個(gè)方案的最大期望收益EMV 好天氣好天氣1|X21|X2（0.09) 0.09) 壞天氣壞天氣2|X22|X2（0.91) EMV0.91) EMV 施工施工 5 1 0.46 不施工不施工 0.2 0.2 0.2* n補(bǔ)充信息價(jià)值：補(bǔ)充信息價(jià)值： 后驗(yàn)決策最大期望收益后驗(yàn)決策最大期望收益EMV*=0.313.6

58、2+0.69(0.2)=0.9842 補(bǔ)充信息價(jià)值：補(bǔ)充信息帶來(lái)期望收益增量補(bǔ)充信息價(jià)值：補(bǔ)充信息帶來(lái)期望收益增量0.9842-0.80=0.1842 補(bǔ)充信息價(jià)值大于預(yù)報(bào)信息成本（補(bǔ)充信息價(jià)值大于預(yù)報(bào)信息成本（0.08)，因此的確是合算的。，因此的確是合算的。 n后驗(yàn)決策結(jié)果：后驗(yàn)決策結(jié)果： 預(yù)報(bào)好天氣時(shí)施工，預(yù)報(bào)壞天氣時(shí)不施工。預(yù)報(bào)好天氣時(shí)施工，預(yù)報(bào)壞天氣時(shí)不施工。貝葉斯決策的決策樹貝葉斯決策的決策樹126781110549不預(yù)報(bào)不預(yù)報(bào)預(yù)報(bào)預(yù)報(bào)預(yù)報(bào)好預(yù)報(bào)好0.31預(yù)報(bào)差預(yù)報(bào)差0.69施工施工施工施工不施工不施工不施工不施工施工施工不施工不施工天氣好天氣好 0.3天氣差天氣差 0.7天氣差天

59、氣差 0.91天氣好天氣好 0.09天氣差天氣差 0.23天氣好天氣好 0.77555-0.2-0.2-0.2-1-1-10.83.62-0.2-0.46-0.2-0.2-0.23.620.900.80.93成本成本0.08n繪制網(wǎng)絡(luò)圖的準(zhǔn)備工作n確定目標(biāo)：以時(shí)間要求還是資源費(fèi)用要求為主n工程分解：列出全部分解后的工序及代號(hào)清單n工序關(guān)系：確定每一道工序的緊前工序是哪些n工序時(shí)間：確定每一道工序的完成所需的時(shí)間n一時(shí)估計(jì)法：僅估計(jì)一個(gè)完成工序的最大時(shí)間Dn三時(shí)估計(jì)法：樂(lè)觀時(shí)間 a、悲觀時(shí)間b、最可能時(shí)間m64bmaD 6ab n網(wǎng)絡(luò)圖繪制規(guī)則網(wǎng)絡(luò)圖繪制規(guī)則n方向、時(shí)序與結(jié)點(diǎn)編號(hào)方向、時(shí)序與結(jié)點(diǎn)

60、編號(hào) 網(wǎng)絡(luò)圖是有向圖，按流程的順序，規(guī)定工序從左向網(wǎng)絡(luò)圖是有向圖，按流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個(gè)結(jié)點(diǎn)都有一個(gè)時(shí)間（某一右排列。網(wǎng)絡(luò)圖中的各個(gè)結(jié)點(diǎn)都有一個(gè)時(shí)間（某一個(gè)或若干個(gè)工序開始或結(jié)束時(shí)間），一般按結(jié)點(diǎn)的個(gè)或若干個(gè)工序開始或結(jié)束時(shí)間），一般按結(jié)點(diǎn)的時(shí)間順序編號(hào)（從左到右，從上到下），箭尾結(jié)點(diǎn)時(shí)間順序編號(hào)（從左到右，從上到下），箭尾結(jié)點(diǎn)編號(hào)應(yīng)小于箭頭結(jié)點(diǎn)編號(hào)。始結(jié)點(diǎn)編號(hào)為編號(hào)應(yīng)小于箭頭結(jié)點(diǎn)編號(hào)。始結(jié)點(diǎn)編號(hào)為1 1。n網(wǎng)絡(luò)圖中不能出現(xiàn)缺口和回路網(wǎng)絡(luò)圖中不能出現(xiàn)缺口和回路n二個(gè)結(jié)點(diǎn)之間只能有一個(gè)直接的工序二個(gè)結(jié)點(diǎn)之間只能有一個(gè)直接的工序 兩條箭線不能有同樣的始末結(jié)點(diǎn)，若二個(gè)事項(xiàng)