模型決策法課件

章模型決策法線性規(guī)劃等時(shí)序與路徑規(guī)劃分派問(wèn)題最短路問(wèn)題最大流問(wèn)題章模型決策法線性規(guī)劃等1模型決策法優(yōu)化模型max(min)目標(biāo)函數(shù)s.t.約束條件模型決策法優(yōu)化模型2線性規(guī)劃模型的建立實(shí)例1兩種產(chǎn)品的生產(chǎn)。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，資源限制及市場(chǎng)價(jià)格如下表： Ⅰ Ⅱ 資源限制 設(shè)備 1 1 300臺(tái)時(shí) 原材料A 2 1 400千克 原材料B 0 1 250千克 市場(chǎng)價(jià)格 50 100 問(wèn)題：如何安排生產(chǎn)，才能使工廠獲利最多？線性規(guī)劃模型的建立實(shí)例13規(guī)劃與決策分析：（1）設(shè)x1—生產(chǎn)產(chǎn)品Ⅰ的數(shù)量；

x2—生產(chǎn)產(chǎn)品Ⅱ的數(shù)量。（2）目標(biāo)函數(shù)：MAX50x1+100x2（3）約束條件：subjectto(s.t.):

x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0規(guī)劃與決策分析：4規(guī)劃與決策線性規(guī)劃模型：

max50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0規(guī)劃與決策線性規(guī)劃模型：5規(guī)劃與決策線性規(guī)劃模型的一般形式

maxc1x1+c2x2+…+cnxn

s.t.a11x1+…+a1nxn≤(≥,=)b1a21x1+…+a2nxn≤(≥,=)b2

…am1x1+…+amnxn≤(≥,=)bm

xij≥0i=1,…,n,j=1,…,m規(guī)劃與決策線性規(guī)劃模型的一般形式6規(guī)劃與決策線性規(guī)劃應(yīng)用領(lǐng)域：合理利用板、線材問(wèn)題；配料問(wèn)題；投資問(wèn)題；生產(chǎn)計(jì)劃問(wèn)題、勞動(dòng)力安排問(wèn)題；運(yùn)輸問(wèn)題、電子商務(wù)配送問(wèn)題；企業(yè)決策問(wèn)題；企業(yè)或商業(yè)競(jìng)爭(zhēng)對(duì)策問(wèn)題等。規(guī)劃與決策線性規(guī)劃應(yīng)用領(lǐng)域：7規(guī)劃與決策一般線性規(guī)劃建模過(guò)程Step1.理解及分析實(shí)際問(wèn)題，資源狀況，解決問(wèn)題實(shí)現(xiàn)的目標(biāo)；Step2.確定決策變量（x1,…，xn）—解決問(wèn)題的具體方案（量化方案）；Step3.確定目標(biāo)函數(shù)及約束條件；Step4.應(yīng)用線性規(guī)劃軟件求解；Step5.檢驗(yàn)所求得的解決方案是否可行：如可行，則開(kāi)始具體實(shí)施；否則，轉(zhuǎn)Step1或Step2修改模型。規(guī)劃與決策一般線性規(guī)劃建模過(guò)程8規(guī)劃與決策案例2：（生產(chǎn)計(jì)劃問(wèn)題）某公司面臨一個(gè)外協(xié)加工還是自行生產(chǎn)問(wèn)題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車(chē)間。甲、乙兩種產(chǎn)品的鑄造可以外協(xié)加工，亦可以自行生產(chǎn)。但丙產(chǎn)品的鑄造必須自行生產(chǎn)才能保證質(zhì)量。有關(guān)數(shù)據(jù)見(jiàn)下表：規(guī)劃與決策案例2：（生產(chǎn)計(jì)劃問(wèn)題）某公司面臨一個(gè)外協(xié)加工還是9規(guī)劃與決策工時(shí)與成本 甲 乙 丙 總工時(shí) 每件鑄造工時(shí)（小時(shí)） 5 10 7 8000 每件機(jī)加工工時(shí)（小時(shí)） 6 4 8 12000 每件裝配工時(shí)（小時(shí)） 3 2 2 10000 自產(chǎn)鑄件每件成本（元） 3 5 4 外協(xié)鑄件每件成本（元） 5 6 - 機(jī)加工每件成本（元） 2 1 3 裝配每件成本（元） 3 2 2 每件產(chǎn)品售價(jià)（元） 23 18 16 問(wèn)題：如何安排生產(chǎn)計(jì)劃，使公司獲利最大？規(guī)劃與決策工時(shí)與成本 甲 乙 丙 總工時(shí) 10規(guī)劃與決策分析：設(shè)xi

—公司加工甲、乙、丙三種產(chǎn)品數(shù)量，i=1,2,3。x4、x5—由外協(xié)鑄造后再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品數(shù)量；目標(biāo)函數(shù)：每件產(chǎn)品利潤(rùn)分別是：每件x1產(chǎn)品利潤(rùn):23-（3+2+3）=15元每件x2產(chǎn)品利潤(rùn):18-（5+1+2）=10元每件x3產(chǎn)品利潤(rùn):16-（4+3+2）=7元每件x4產(chǎn)品利潤(rùn):23-（5+2+3）=13元每件x5產(chǎn)品利潤(rùn):18-（6+1+2）=9元目標(biāo)函數(shù)為：max15x1+10x2+7x3+13x4+9x5規(guī)劃與決策分析：設(shè)xi—公司加工甲、乙、丙三種產(chǎn)品數(shù)量11規(guī)劃與決策約束條件：5x1+10x2+7x3

≤80006x1+4x2+8x3+6x4+4x5

≤120003x1+2x2+2x3+3x4+2x5

≤10000xi

≥0i=1,…,5規(guī)劃與決策約束條件：12規(guī)劃與決策圖解法:Step1.確定可行域D={x|x滿足上述約束條件}如下圖2-1：Step2.確定直線50x1+100x2=0如下圖2-2：Step3.向上移動(dòng)直線50x1+100x2=0如圖2-2，z=50x1+100x2的值不斷地增加，達(dá)到B點(diǎn)時(shí)，達(dá)到最大；Step4.最優(yōu)解為B=(50,250),z最大=27500。規(guī)劃與決策圖解法:13規(guī)劃與決策

0100200300300200100D圖2-1規(guī)劃與決策014規(guī)劃與決策

0100200300300200100DB(50,250)Z=50x1+100x2圖2-2規(guī)劃與決策015時(shí)序與路徑規(guī)劃討論各種時(shí)序規(guī)劃問(wèn)題介紹時(shí)序規(guī)劃原則分派問(wèn)題運(yùn)輸問(wèn)題網(wǎng)絡(luò)的最短路徑網(wǎng)絡(luò)的最大流時(shí)序與路徑規(guī)劃討論各種時(shí)序規(guī)劃問(wèn)題16時(shí)序規(guī)劃問(wèn)題

ABEFDC機(jī)器機(jī)器DEFCAB等待處理的一批工作按最優(yōu)次序排隊(duì)一臺(tái)機(jī)器工作的時(shí)序規(guī)劃時(shí)序規(guī)劃問(wèn)題ABEFDC機(jī)器機(jī)器DEFCAB等待處理的17時(shí)序規(guī)劃問(wèn)題原則：(1)最緊迫的優(yōu)先實(shí)例1：6種部件作為一批等待一臺(tái)機(jī)器加工。每一部件的平均周需求量、當(dāng)前的存貨水平以及加工一批所需時(shí)間如下表，你將如何安排各種部件的生產(chǎn)次序？部件ABCDEF平均需求量104263473當(dāng)前存貨量722148922823加工時(shí)間2.01.50.50.51.01.5時(shí)序規(guī)劃問(wèn)題原則：18時(shí)序規(guī)劃問(wèn)題

時(shí)序規(guī)劃問(wèn)題19時(shí)序規(guī)劃問(wèn)題

時(shí)序規(guī)劃問(wèn)題20時(shí)序規(guī)劃問(wèn)題

以“加工時(shí)間最短者優(yōu)先”為原則時(shí)序規(guī)劃問(wèn)題以“加工時(shí)間最短者優(yōu)先”為原則21時(shí)序規(guī)劃問(wèn)題

以“加工時(shí)間最短者優(yōu)先”為原則時(shí)序規(guī)劃問(wèn)題以“加工時(shí)間最短者優(yōu)先”為原則22時(shí)序規(guī)劃問(wèn)題(3)到期日最近者原則時(shí)序規(guī)劃問(wèn)題(3)到期日最近者原則23時(shí)序規(guī)劃問(wèn)題(3)到期日最近者原則時(shí)序規(guī)劃問(wèn)題(3)到期日最近者原則24時(shí)序規(guī)劃問(wèn)題(4)延誤的工作項(xiàng)目最少第1步：運(yùn)用先到期者優(yōu)先的原則排出工作的初始次序。如果已經(jīng)沒(méi)有工作被延誤，這便是最優(yōu)解，否則，則進(jìn)行第2步。第2步：在安排的時(shí)序中找到1項(xiàng)延誤的工作。第3步：找出第2步所找工作之前（包括這一工作本身）加工時(shí)間最長(zhǎng)的工作。第4步：將這一工作從時(shí)序安排中抽出來(lái)，并更新相應(yīng)的時(shí)間。如果仍然有被延誤的工作，再轉(zhuǎn)向第2步，否則轉(zhuǎn)向第5步。第5步：將第4步抽出的工作放到時(shí)序的末尾。實(shí)例3：沿用上述實(shí)例的8項(xiàng)工作，求解工作延誤項(xiàng)數(shù)最少的時(shí)序。為此我們采用上述五個(gè)步驟。工作ABCDEFGH加工時(shí)間25384723到期時(shí)間1378301420236時(shí)序規(guī)劃問(wèn)題(4)延誤的工作項(xiàng)目最少25時(shí)序規(guī)劃問(wèn)題第1步：將工作按到期時(shí)間排序。工作GBCAEFDH到期時(shí)間2781314203036開(kāi)始加工時(shí)間0271012162331加工時(shí)間25324783完成加工時(shí)間27101216233134延誤工作****第2步：在上述時(shí)序中，第1項(xiàng)被延誤的工作是C。第3步：到C之前，包括C在內(nèi)，加工時(shí)間最長(zhǎng)的工作是B，加工時(shí)間為5。時(shí)序規(guī)劃問(wèn)題第1步：將工作按到期時(shí)間排序。26時(shí)序規(guī)劃問(wèn)題第4步：抽出工作B，更新相關(guān)的時(shí)間：工作GCAEFDH到期時(shí)間281314203036開(kāi)始加工時(shí)間0257111826加工時(shí)間2324783完成加工時(shí)間25711182629第5步：現(xiàn)在已經(jīng)沒(méi)有工作被延誤了，所以我們將工作B加到時(shí)序的最后。工作GCAEFDHB到期時(shí)間2813142030367開(kāi)始加工時(shí)間025711182629加工時(shí)間23247835完成加工時(shí)間2571118262934現(xiàn)在只有一項(xiàng)工作被延誤，平均排隊(duì)時(shí)間為98/8=12.25，平均延誤時(shí)間為27/8=3.375天。時(shí)序規(guī)劃問(wèn)題第4步：抽出工作B，更新相關(guān)的時(shí)間：27時(shí)序規(guī)劃問(wèn)題(5)Johnson’srule(約翰遜原則)步驟1：列出各項(xiàng)工作及它們?cè)诿颗_(tái)機(jī)器上的加工時(shí)間。步驟2：找出下一個(gè)在各臺(tái)機(jī)器上加工時(shí)間最短的工作。步驟3：如果這是在機(jī)器1上，盡量將這一工作安排在前面；如果這是在機(jī)器2上，盡量將這一工作安排在后面。在重復(fù)做這些的時(shí)候，總是從時(shí)序的兩端向內(nèi)進(jìn)行，新安排的工作離時(shí)序的中間更近。步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的任務(wù)，這就是最優(yōu)解。

實(shí)例4：有7項(xiàng)工作要順序經(jīng)過(guò)機(jī)器1和機(jī)器2加工。每項(xiàng)工作在每臺(tái)機(jī)器上所需的加工時(shí)間如下，如何安排時(shí)序才能使機(jī)器利用率最高。工作ABCDEFG機(jī)器1251084129機(jī)器2147310566時(shí)序規(guī)劃問(wèn)題(5)Johnson’srule(約翰遜原則28時(shí)序規(guī)劃問(wèn)題

時(shí)序規(guī)劃問(wèn)題29時(shí)序規(guī)劃問(wèn)題

時(shí)序規(guī)劃問(wèn)題30分派問(wèn)題如何以總成本最低為目標(biāo)將操作員分派到各臺(tái)機(jī)器上。原則：每個(gè)操作員只能分派給一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。Cij

第i個(gè)操作員完成第j項(xiàng)任務(wù)的成本Xij

minΣΣCijXijΣXij=1ΣXij=1Xij=0,1i=1,…,n,j=1,…,m=1(分派操作員i完成任務(wù)j)=0(不分派操作員i完成任務(wù)j)ji分派問(wèn)題如何以總成本最低為目標(biāo)將操作員分派到各臺(tái)機(jī)器上。=131最短路問(wèn)題最短路問(wèn)題G(V,E)為連通圖，邊（vi,vj)的權(quán)為lij，求一條道路，使它從vs到vt的總權(quán)最少？方法：1動(dòng)態(tài)規(guī)劃法2Dijkstra算法引例：某一配送中心要給一個(gè)快餐店送快餐原料，應(yīng)按什么路線送貨才能使送貨時(shí)間最短？最短路問(wèn)題最短路問(wèn)題32V216v47v646V11228v7185V36v5（配送中心）（快餐店）V21633最大流問(wèn)題最大流問(wèn)題引例：某石油公司擁有一個(gè)管道網(wǎng)絡(luò)（如圖），使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷(xiāo)售地?；∩系臄?shù)字為該管道的容量，問(wèn)如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從v1向銷(xiāo)地v7運(yùn)送石油，每小時(shí)能運(yùn)送多少石油？最大流問(wèn)題最大流問(wèn)題34v1V2(3,0)v5(6,0)(2,0)(2,0)(5,0)v3V6v7(6,0)(3,0)(1,0)(2,0)v4(2,0)(4,0)v1V2(3,0)35

1、最孤獨(dú)的時(shí)光，會(huì)塑造最堅(jiān)強(qiáng)的自己。

2、把臉一直向著陽(yáng)光，這樣就不會(huì)見(jiàn)到陰影。

3、永遠(yuǎn)不要埋怨你已經(jīng)發(fā)生的事情，要么就改變它，要么就安靜的接受它。

4、不論你在什么時(shí)候開(kāi)始，重要的是開(kāi)始之后就不要停止。

5、通往光明的道路是平坦的，為了成功，為了奮斗的渴望，我們不得不努力。

6、付出了不一定有回報(bào)，但不付出永遠(yuǎn)沒(méi)有回報(bào)。

7、成功就是你被擊落到失望的深淵之后反彈得有多高。

8、為了照亮夜空，星星才站在天空的高處。

9、我們的人生必須勵(lì)志，不勵(lì)志就仿佛沒(méi)有靈魂。

10、拼盡全力，逼自己優(yōu)秀一把，青春已所剩不多。

11、一個(gè)人如果不能從內(nèi)心去原諒別人，那他就永遠(yuǎn)不會(huì)心安理得。

12、每個(gè)人心里都有一段傷痕，時(shí)間才是最好的療劑。

13、如果我不堅(jiān)強(qiáng)，那就等著別人來(lái)嘲笑。

14、早晨給自己一個(gè)微笑，種下一天旳陽(yáng)光。

15、沒(méi)有愛(ài)不會(huì)死，不過(guò)有了愛(ài)會(huì)活過(guò)來(lái)。

16、失敗的定義：什么都要做，什么都在做，卻從未做完過(guò)，也未做好過(guò)。

17、當(dāng)我微笑著說(shuō)我很好的時(shí)候，你應(yīng)該對(duì)我說(shuō)，安好就好。

18、人不僅要做好事，更要以準(zhǔn)確的方式做好事。

19、我們并不需要用太華麗的語(yǔ)言來(lái)包裹自己，因?yàn)槲覀円鲎钫鎸?shí)的自己。

20、一個(gè)人除非自己有信心，否則無(wú)法帶給別人信心。

21、為別人鼓掌的人也是在給自己的生命加油。

22、失去金錢(qián)的人損失甚少，失去健康的人損失極多，失去勇氣的人損失一切。

23、相信就是強(qiáng)大，懷疑只會(huì)抑制能力，而信仰就是力量。

24、那些嘗試去做某事卻失敗的人，比那些什么也不嘗試做卻成功的人不知要好上多少。

25、自己打敗自己是最可悲的失敗，自己戰(zhàn)勝自己是最可貴的勝利。

26、沒(méi)有熱忱，世間便無(wú)進(jìn)步。

27、失敗并不意味你浪費(fèi)了時(shí)間和生命，失敗表明你有理由重新開(kāi)始。

28、青春如此華美，卻在煙火在散場(chǎng)。

29、生命的道路上永遠(yuǎn)沒(méi)有捷徑可言，只有腳踏實(shí)地走下去。

30、只要還有明天，今天就永遠(yuǎn)是起跑線。

31、認(rèn)真可以把事情做對(duì)，而用心卻可以做到完美。

32、如果上帝沒(méi)有幫助你那他一定相信你可以。

33、只要有信心，人永遠(yuǎn)不會(huì)挫敗。

34、珍惜今天的美好就是為了讓明天的回憶更美好。

35、只要你在路上，就不要放棄前進(jìn)的勇氣，走走停停的生活會(huì)一直繼續(xù)。

36、大起大落誰(shuí)都有拍拍灰塵繼續(xù)走。

37、孤獨(dú)并不可怕，每個(gè)人都是孤獨(dú)的，可怕的是害怕孤獨(dú)。

38、寧可失敗在你喜歡的事情上，也不要成功在你所憎惡的事情上。

39、我很平凡，但骨子里的我卻很勇敢。

40、眼中閃爍的淚光，也將化作永不妥協(xié)的堅(jiān)強(qiáng)。

41、我不去想是否能夠成功，既然選了遠(yuǎn)方，便只顧風(fēng)雨兼程。

42、寧可自己去原諒別人，莫等別人來(lái)原諒自己。

43、踩著垃圾到達(dá)的高度和踩著金子到達(dá)的高度是一樣的。

44、每天告訴自己一次：我真的很不錯(cuò)。

45、人生最大的挑戰(zhàn)沒(méi)過(guò)于戰(zhàn)勝自己！

46、愚癡的人，一直想要?jiǎng)e人了解他。有智慧的人，卻努力的了解自己。

47、現(xiàn)實(shí)的壓力壓的我們喘不過(guò)氣也壓的我們走向成功。

48、心若有陽(yáng)光，你便會(huì)看見(jiàn)這個(gè)世界有那么多美好值得期待和向往。

49、相信自己，你能作繭自縛，就能破繭成蝶。

50、不能強(qiáng)迫別人來(lái)愛(ài)自己，只能努力讓自己成為值得愛(ài)的人。

51、不要拿過(guò)去的記憶，來(lái)折磨現(xiàn)在的自己。

52、汗水是成功的潤(rùn)滑劑。

53、人必須有自信，這是成功的秘密。

54、成功的秘密在于始終如一地忠于目標(biāo)。

55、只有一條路不能選擇――那就是放棄。

56、最后的措手不及是因?yàn)楫?dāng)初游刃有余的自己

57、現(xiàn)實(shí)很近又很冷，夢(mèng)想很遠(yuǎn)卻很溫暖。

58、沒(méi)有人能替你承受痛苦，也沒(méi)有人能搶走你的堅(jiān)強(qiáng)。

59、不要拿我跟任何人比，我不是誰(shuí)的影子，更不是誰(shuí)的替代品，我不知道年少輕狂，我只懂得勝者為。

60、如果你看到面前的陰影，別怕，那是因?yàn)槟愕谋澈笥嘘?yáng)光。

61、寧可笑著流淚，絕不哭著后悔。

62、覺(jué)得自己做得到和做不到，只在一念之間。

63、跌倒，撞墻，一敗涂地，都不用害怕，年輕叫你勇敢。

64、做最好的今天，回顧最好的昨天，迎接最美好的明天。

65、每件事情都必須有一個(gè)期限，否則，大多數(shù)人都會(huì)有多少時(shí)間就花掉多少時(shí)間。

66、當(dāng)你被壓力壓得透不過(guò)氣來(lái)的時(shí)候，記住，碳正是因?yàn)閴毫Χ兂砷W耀的鉆石。

67、現(xiàn)實(shí)會(huì)告訴你，不努力就會(huì)被生活給踩死。無(wú)需找什么借口，一無(wú)所有，就是拼的理由。

68