Data, Model and Decisions

1、2 2其它規(guī)劃問題其它規(guī)劃問題規(guī)劃的組成規(guī)劃的組成： 目標函數目標函數 opt（optimize） max z (f) 或或 min z(f) 約束條件約束條件 s.t. (subject to) 滿足于滿足于 決策變量決策變量 用符號來表示可控制的因素用符號來表示可控制的因素2022-3-2322.12.1整數規(guī)劃整數規(guī)劃2.22.2目標規(guī)劃目標規(guī)劃2.32.3動態(tài)規(guī)劃動態(tài)規(guī)劃42.1 2.1 整數規(guī)劃整數規(guī)劃 1 1整數規(guī)劃的圖解法整數規(guī)劃的圖解法 2 2整數規(guī)劃的計算機求解整數規(guī)劃的計算機求解 3 3整數規(guī)劃的整數規(guī)劃的應用應用5求整數解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃

2、求整數解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃的非整數解加以處理都能解決的，而要用整數規(guī)劃的方法加以的非整數解加以處理都能解決的，而要用整數規(guī)劃的方法加以解決。解決。在整數規(guī)劃中在整數規(guī)劃中: : 如果所有的變量都為非負整數，則稱為如果所有的變量都為非負整數，則稱為純整數規(guī)劃問題純整數規(guī)劃問題； 如果只有一部分變量為非負整數，則稱之為如果只有一部分變量為非負整數，則稱之為混合整數規(guī)劃問題混合整數規(guī)劃問題。 如果所有的變量都為如果所有的變量都為0-10-1變量，則稱之為變量，則稱之為0-10-1規(guī)劃規(guī)劃。6 1 1整數規(guī)劃的圖解法整數規(guī)劃的圖解法例例8-1. 某公司擬用集裝箱托運甲、

3、乙兩種貨物，這兩種貨物每某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。件的體積、重量、可獲利潤以及托運所受限制如表所示。甲種貨物至多托運甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利件，問兩種貨物各托運多少件，可使獲得利潤最大潤最大?貨物貨物每件體積每件體積（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制13651407解：設解：設x1 、 x2分別為甲、乙兩種貨物托運的件數，建立模型分別為甲、乙兩種貨物托運的件數，建立模型 目標函數：目標函數

4、： Max z = 2x1 +3 x2 約束條件：約束條件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 為整數。為整數。如果去掉最后一個約束，就是一個線性規(guī)劃問題。如果去掉最后一個約束，就是一個線性規(guī)劃問題。利用圖解法，利用圖解法，8得到線性規(guī)劃的最優(yōu)解為得到線性規(guī)劃的最優(yōu)解為x x1 1=2.44, x=2.44, x2 2=3.26,=3.26,目標函數值為目標函數值為14.6614.66。由圖表可看出，整數規(guī)劃的最優(yōu)解為由圖表可看出，整數規(guī)劃的最優(yōu)解為x x1 1=4, x=4, x2 2=2,=2,目標函數值目標函數

5、值為為1414。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=69性質性質1 1： 任何求任何求最大最大目標函數值的純整數規(guī)劃或混合整數目標函數值的純整數規(guī)劃或混合整數規(guī)劃的最大目標函數值規(guī)劃的最大目標函數值小于或等于小于或等于相應的線性規(guī)相應的線性規(guī)劃的最大目標函數值；劃的最大目標函數值； 任何求任何求最小最小目標函數值的純整數規(guī)劃或混合整數目標函數值的純整數規(guī)劃或混合整數規(guī)劃的最小目標函數值規(guī)劃的最小目標函數值大于或等于大于或等于相應的線性規(guī)相應的線性規(guī)劃的最小目標函數值。劃的最小目標函數值。10例例8-28-2： Max z = 3Max z = 3

6、x x1 1 + + x x2 2 + 3 + 3x x3 3 s.t. s.t. - -x x1 1 + 2 + 2x x2 2 + + x x3 3 4 4 4 4x x2 2 -3 -3x x3 3 2 2 x x1 1 -3-3x x2 2 + 2 + 2x x3 3 3 3 x x1 1, ,x x2 2, ,x x3 3 0 0 為整數為整數例例8-38-3： Max z = 3xMax z = 3x1 1 + x + x2 2 + 3x + 3x3 3 s.t. s.t. -x -x1 1 + 2x + 2x2 2 + x + x3 3 4 4 4x 4x2 2 -3x -3x3

7、 3 2 2 x x1 1 -3x -3x2 2 + 2x + 2x3 3 3 3 x x3 3 1 1 x x1 1,x,x2 2,x,x3 3 0 0 x x1 1，x x3 3 為整數為整數 x x3 3 為為0-10-1變量變量用用管理運籌學管理運籌學軟件求解得：軟件求解得： x x1 1 = 5 = 5 x x2 2 = 2 = 2 x x3 3 = 2 = 2 用用管理運籌學管理運籌學軟件求解得：軟件求解得： x x1 1 = 4 = 4 x x2 2 = 1.25 = 1.25 x x3 3 = 1 = 1 z = 16.25 z = 16.25 2 2整數規(guī)劃的計算機求解整數規(guī)

8、劃的計算機求解11 3 3整數規(guī)劃的應用整數規(guī)劃的應用 一、投資場所的選擇一、投資場所的選擇 例例8-4:京成畜產品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售京成畜產品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有門市部，擬議中有10個位置個位置 Aj (j1，2，3，10)可供選擇，考慮到可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定：各地區(qū)居民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由在東區(qū)由A1 ， A2 ，A3 三個點至多選擇兩個；三個點至多選擇兩個； 在西區(qū)由在西區(qū)由A4 ， A5 兩個點中至少選一個；兩個點中至少選一個； 在南區(qū)由在南區(qū)由A6 ， A7 兩

9、個點中至少選一個；兩個點中至少選一個； 在北區(qū)由在北區(qū)由A8 ， A9 ， A10 三個點中至少選兩個。三個點中至少選兩個。 Aj 各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況見表所示情況見表所示 (單位：萬元單位：萬元)。但投資總額不能超過。但投資總額不能超過720萬元，問應選擇哪萬元，問應選擇哪幾個銷售點，可使年利潤為最大幾個銷售點，可使年利潤為最大?12解：設：解：設：0-1變量變量 xi = 1 (Ai 點被選用）或點被選用）或 0 (Ai 點沒被選用）。點沒被選用）。 這樣我們可建立如下的數學模型：這樣我們可

10、建立如下的數學模型：Max z =36Max z =36x x1 1+40+40 x x2 2+50+50 x x3 3+22+22x x4 4+20+20 x x5 5+30+30 x x6 6+25+25x x7 7+48+48x x8 8+58+58x x9 9+61+61x x1010s.t.s.t. 100 100 x x1 1+120+120 x x2 2+150+150 x x3 3+80+80 x x4 4+70+70 x x5 5+90+90 x x6 6+80+80 x x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x x101072

11、0720 x x1 1 + + x x2 2 + + x x3 3 2 2 x x4 4 + + x x5 5 1 1 x x6 6 + + x x7 7 1 1 x x8 8 + + x x9 9 + + x x1010 2 2 x xj j 0 0 且且x xj j 為為0-10-1變量變量，i i = 1,2,3,= 1,2,3,10,1013二、固定成本問題二、固定成本問題 例例8-5:高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設備，制造一個容器所需的各種資源的數量如為金屬板、勞動力和機器設備，制造

12、一個容器所需的各種資源的數量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為 4萬元、萬元、5萬元、萬元、6萬元，可使用的金屬板有萬元，可使用的金屬板有500噸，勞動力有噸，勞動力有300人人/月，機器有月，機器有100臺臺/月，此外不管每種容器制造的數量是多少，都要支付一筆固定的月，此外不管每種容器制造的數量是多少，都要支付一筆固定的費用：小號是費用：小號是l00萬元，中號為萬元，中號為 150 萬元，大號為萬元，大號為200萬元?，F在要制定萬元?，F在要制定一個生產計劃，使獲得的利潤為最大。一個生產計劃，使獲得的利潤為最大。1

13、4解：這是一個整數規(guī)劃的問題。解：這是一個整數規(guī)劃的問題。 設設x1，x2， x3 分別為小號容器、中號容器和大號容器的生產數量。各種容分別為小號容器、中號容器和大號容器的生產數量。各種容器的固定費用只有在生產該種容器時才投入，為了說明固定費用的這種性質，器的固定費用只有在生產該種容器時才投入，為了說明固定費用的這種性質，設設 yi = 1(當生產第當生產第 i種容器種容器, 即即 xi 0 時時) 或或0（當不生產第當不生產第 i種容器即種容器即 xi = 0 時）。時）。 引入約束引入約束 xi M yi ，i =1，2，3，M充分大，充分大，以保證當以保證當 yi = 0 時，時，xi

14、= 0 。 yi=0 xi=0 這樣我們可建立如下的數學模型：這樣我們可建立如下的數學模型：Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3s.t. 2s.t. 2x x1 1 + 4+ 4x x2 2 + 8+ 8x x3 3 500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 100 xi M yi ，i =1，2，3，

15、M充分大充分大 x xj j 0 0 y yj j 為為0-10-1變量變量，i i = 1,2,3= 1,2,315三、指派問題三、指派問題 有有 n n 項不同的任務，恰好項不同的任務，恰好 n n 個人可分別承擔這些任務，但由于每個人可分別承擔這些任務，但由于每人特長不同，完成各項任務的效率等情況也不同?，F假設必須指派每人特長不同，完成各項任務的效率等情況也不同?，F假設必須指派每個人去完成一項任務，怎樣把個人去完成一項任務，怎樣把 n n 項任務指派給項任務指派給 n n 個人，使得完成個人，使得完成 n n 項任務的總的效率最高，這就是項任務的總的效率最高，這就是指派問題。指派問題。例

16、例8-68-6有四個工人，要分別指派他們完成四項不同的工作，每人做各項有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應如何指派工作，才能使總的消耗工作所消耗的時間如下表所示，問應如何指派工作，才能使總的消耗時間為最少。時間為最少。16解：解：引入引入0 01 1變量變量 x xijij，并令并令 x xij ij = 1(= 1(當指派第當指派第 i i人去完成第人去完成第j j項工作時項工作時) )或或0 0（當不指派第（當不指派第 i i人人去完成第去完成第j j項工作時項工作時) )這可以表示為一個這可以表示為一個0-1整數規(guī)劃問題：整數規(guī)劃問題：

17、Minz=15Minz=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x x2323+18+18x x2424+26+26x x3131+17+17x x3232+16+16x x3333+19+19x x3434+19+19x x41 41 +21+21x x4242+23+23x x4343+17+17x x4444s.t. s.t. x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (= 1 (甲只能干一項工作甲只能干一項工作) ) x

18、x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一項工作乙只能干一項工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一項工作丙只能干一項工作) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一項工作丁只能干一項工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+

19、+ x x3232+ + x x4242= 1 ( B= 1 ( B工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( C= 1 ( C工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( D= 1 ( D工作只能一人干工作只能一人干) ) x xijij 為為0-10-1變量變量，i,j i,j = 1,2,3,4= 1,2,3,417四、分布系統(tǒng)設計四、分布系統(tǒng)設計例例8-7某企業(yè)在某企業(yè)在 A1 地已有一個工廠，其產品的生產能力為地已有一個

20、工廠，其產品的生產能力為 30 千箱，為了擴大千箱，為了擴大生產，打算在生產，打算在 A2，A3，A4，A5地中再選擇幾個地方建廠。已知在地中再選擇幾個地方建廠。已知在 A2 ， A3，A4，A5地建廠的固定成本分別為地建廠的固定成本分別為175千元、千元、300千元、千元、375千元、千元、500千元，千元，另外，另外， A1產量及產量及A2，A3，A4，A5建成廠的產量，那時銷地的銷量以及產地建成廠的產量，那時銷地的銷量以及產地到銷地的單位運價到銷地的單位運價(每千箱運費每千箱運費:千元千元)如下表所示。如下表所示。 a) 問應該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總

21、問應該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最小的運輸費用之和最小? b) 如果由于政策要求必須在如果由于政策要求必須在A2，A3地建一個廠，應在哪幾個地方建廠地建一個廠，應在哪幾個地方建廠? 18解：解： a) 設設 x xijij為從為從Ai 運往運往Bj 的運輸量的運輸量(單位千箱單位千箱)， y yk k = 1(= 1(當當A Ak k 被選中時被選中時) )或或0 0（當（當A Ak k 沒被選中時沒被選中時),),k k =2,3,4,5 =2,3,4,5這可以表示為一個整數規(guī)劃問題：這可以表示為一個整數規(guī)劃問題：Min z = 175Min

22、z = 175y y2 2+300+300y y3 3+375+375y y4 4+500+500y y5 5+8+8x x1111+4+4x x1212+3+3x x1313+5+5x x2121+2+2x x2222+3+3x x2323+4+4x x3131+ +3 3x x3232+4+4x x3333+9+9x x41 41 +7+7x x4242+5+5x x4343+10+10 x x51 51 +4+4x x5252+2+2x x5353其中前其中前4項為固定投資額，后面的項為運輸費用。項為固定投資額，后面的項為運輸費用。s.t. s.t. x x1111+ + x x1212

23、+ + x x1313 30 ( A 30 ( A1 1 廠的產量限制廠的產量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 廠的產量限制廠的產量限制) ) x x3131+ + x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 廠的產量限制廠的產量限制) ) x x4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 廠的產量限制廠的產量限制) ) x x5151+ + x x5252+ + x x53 53 40 40y y5 5 ( A

24、 ( A5 5 廠的產量限制廠的產量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 銷地的限制銷地的限制) ) x x1212+ + x x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B= 20 ( B2 2 銷地的限制銷地的限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 銷地的限制銷地的限制) ) x xijij 0

25、 0，i i = 1,2,3,4,5= 1,2,3,4,5； j j = 1,2,3= 1,2,3， y yk k 為為0-10-1變量，變量，k k =2,3,4,5=2,3,4,5。19五、投資問題五、投資問題( (第第4 4章）章） 例例8-88-8某公司在今后五年內考慮給以下的項目投資。已知：某公司在今后五年內考慮給以下的項目投資。已知：項目項目A A：從第一年到第四年每年年初需要投資，并于次年末回收本利從第一年到第四年每年年初需要投資，并于次年末回收本利115%， 但要求第一年投資最低金額為但要求第一年投資最低金額為4萬元，第二、三、四年不限萬元，第二、三、四年不限；項目項目B B：

26、第三年初需要投資，到第五年末能回收本利第三年初需要投資，到第五年末能回收本利128，但規(guī)定最低，但規(guī)定最低投資金額為投資金額為3萬元，最高金額為萬元，最高金額為5萬元萬元； 項目項目 C：第二年初需要投資，到第五年末能回收本利：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其，但規(guī)定其投資額或為投資額或為2萬元或為萬元或為4萬元或為萬元或為6萬元或為萬元或為8萬元。萬元。 項目項目 D：五年內每年初可購買公債，于當年末歸還，并加利息：五年內每年初可購買公債，于當年末歸還，并加利息6%，此，此項投資金額不限。項投資金額不限。 該部門現有資金該部門現有資金10萬元，問它應如何確定給這些項目

27、的每年投資額，萬元，問它應如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大使到第五年末擁有的資金本利總額為最大?20解：解：1) 設設x xiAiA、x xiBiB、x xiCiC、x xiD iD ( i 1，2，3，4，5)分別表示第分別表示第 i 年年初給項年年初給項目目A，B，C，D的投資額的投資額(元元)； 設設yiA， yiB，是，是01變量，并規(guī)定取變量，并規(guī)定取 1 時分別表示第時分別表示第 i 年給年給A、B投投資，否則取資，否則取 0（ i = 1, 3）。）。 設設yiC 是非負整數變量，并規(guī)定：第是非負整數變量，并規(guī)定：第2年投資年投資C項目項目8萬

28、元時萬元時，取值為取值為4；第第 2年投資年投資C項目項目6萬元時，取值萬元時，取值3；第；第2年投資年投資C項目項目4萬元時，取值萬元時，取值2；第第2年投資年投資C項目項目2萬元時，取值萬元時，取值1；第；第2年不投資年不投資C項目時，取值項目時，取值0； 這樣我們建立如下的決策變量：這樣我們建立如下的決策變量： 第第1 1年年 第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 A A x x1A 1A x x2A 2A x x3A3A x x4A4A B B x x3B3B C C x x2C2C=20000y=20000y2C2C D D x x1D 1D x x2D 2

29、D x x3D3D x x4D4D x x5D5D 212 2）約束條件：）約束條件：第一年：年初有第一年：年初有100000100000元，元，D D項目在年末可收回投資，故第一年年初應把全部資金投出去，項目在年末可收回投資，故第一年年初應把全部資金投出去，于是于是 x x1A1A+ + x x1D 1D = 100000= 100000；第二年：第二年：A A的投資第二年末才可收回，故第二年年初的資金為的投資第二年末才可收回，故第二年年初的資金為1.061.06x x1D1D，于是，于是x x2A2A+ +x x2C2C+ +x x2D2D = = 1.061.06x x1D1D；第三年：

30、年初的資金為第三年：年初的資金為 1.151.15x x1A1A+1.06+1.06x x2D2D，于是，于是 x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D；第四年：年初的資金為第四年：年初的資金為 1.151.15x x2A2A+1.06+1.06x x3D3D，于是，于是 x x4A 4A + + x x4D4D = 1.15 = 1.15x x2A2A+ 1.06+ 1.06x x3D3D；第五年：年初的資金為第五年：年初的資金為 1.151.15x x3A3A+1.06+1.06x x4D4D，于

31、是，于是 x x5D 5D = 1.15= 1.15x x3A3A+ 1.06+ 1.06x x4D4D。 關于項目關于項目A A的投資額規(guī)定的投資額規(guī)定: : x x1A1A 40000 40000y y1A1A ，x x1A1A 200000 200000y y1A1A ，200000200000是足夠大的是足夠大的數；保證當數；保證當 y y1A1A = 0 = 0時，時， x x1A1A = 0 = 0 ；當；當y y1A1A = 1 = 1時，時，x x1A1A 40000 40000 。 關于項目關于項目B B的投資額規(guī)定的投資額規(guī)定: : x x3B3B 30000 30000y

32、 y3B3B ，x x3B3B 50000 50000y y3B3B ； 保證當保證當 y y3B3B = 0 = 0時，時， x x3B3B = 0 = 0 ；當；當y y3B3B = 1 = 1時，時，50000 50000 x x3B3B 30000 30000 。 關于項目關于項目C C的投資額規(guī)定的投資額規(guī)定: : x x2C2C = 20000 = 20000y y2C2C ，y y2C2C = 0 = 0，1 1，2 2，3 3，4 4。223 3）目標函數及模型：）目標函數及模型： Max z = 1.15Max z = 1.15x x4A4A+ 1.40+ 1.40 x x2

33、C2C+ 1.28+ 1.28x x3B 3B + 1.06+ 1.06x x5D 5D s.t. s.t. x x1A1A+ + x x1D 1D =10=10； x x2A2A+ +x x2C2C+ +x x2D2D = 1.06 = 1.06x x1D1D； x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D； x x4A4A+ +x x4D4D = 1.15 = 1.15x x2A2A+ 1.06+ 1.06x x3D3D； x x5D 5D = 1.15= 1.15x x3A3A+ 1.06+ 1.0

34、6x x4D4D； x x1A1A 4 4y y1A1A ， x x1A1A 10 10y y1A1A ， x x3B3B 3 3y y3B3B ， x x3B3B 5 5y y3B3B ； x x2C2C = 2 = 2y y2C2C ， y y2C2C 4 4 x xiAiA ，x xiBiB ，x xiCiC ，x xiDiD 0 ( i = 1 0 ( i = 1、2 2、3 3、4 4、5 5）, ,y y1A1A， y y3B3B 為為0-10-1變量變量, ,y y2C 2C 整數整數 案例分析案例分析 教材教材P199案例分析案例分析9-122022-3-232324練練 習習

35、 教材教材P195習題習題2-1125 2.2 2.2 目標規(guī)劃目標規(guī)劃 1 1 目標規(guī)劃問題舉例目標規(guī)劃問題舉例 2 2 目標規(guī)劃問題求解目標規(guī)劃問題求解 3 3 復雜情況下的目標規(guī)劃復雜情況下的目標規(guī)劃 4 4 加權目標規(guī)劃加權目標規(guī)劃26 1 1目標規(guī)劃問題舉例目標規(guī)劃問題舉例多目標問題多目標問題例例1 1企業(yè)生產企業(yè)生產例例2 2商務活動商務活動例例3 3投資投資例例4 4裁員裁員例例5 5營銷營銷27 2 2目標規(guī)劃問題求解目標規(guī)劃問題求解 例例9-6一位投資商有一筆資金準備購買股票。資金總額為一位投資商有一筆資金準備購買股票。資金總額為90000元，目元，目前可選的股票有前可選的股

36、票有A和和B兩種（可以同時投資于兩種股票）。其價格以兩種（可以同時投資于兩種股票）。其價格以及年收益率和風險系數如表及年收益率和風險系數如表1：股票股票價格（元）價格（元）年收益（元）年收益（元）年年風險系數風險系數A2030.5B5040.2從上表可知，從上表可知，A股票的收益率為（股票的收益率為（320）10015，股票，股票B的收益的收益率為率為4501008，A的收益率比的收益率比B大，但同時大，但同時A的風險也比的風險也比B大。大。這也符合高風險高收益的規(guī)律。這也符合高風險高收益的規(guī)律。 試求一種投資方案，使得一年的總投資風險不高于試求一種投資方案，使得一年的總投資風險不高于700，

37、且投資收益，且投資收益不低于不低于10000元。元。28 顯然，此問題屬于目標規(guī)劃問題。它有顯然，此問題屬于目標規(guī)劃問題。它有兩個目標變量兩個目標變量：一：一是限制風險，一是確保收益。在求解之前，是限制風險，一是確保收益。在求解之前，應首先考慮兩個目應首先考慮兩個目標的優(yōu)先權標的優(yōu)先權。 假設第一個目標（即限制風險）的優(yōu)先權比第二個目標假設第一個目標（即限制風險）的優(yōu)先權比第二個目標（確保收益）大，這意味著求解過程中必須首先滿足第一個目（確保收益）大，這意味著求解過程中必須首先滿足第一個目標，然后在此基礎上再盡量滿足第二個目標。標，然后在此基礎上再盡量滿足第二個目標。 建立模型：建立模型： 設

38、設x x1 1、x x2 2分別表示投資商所購買的分別表示投資商所購買的A A股票和股票和B B股票的數量。股票的數量。 首先考慮資金總額的約束：總投資額不能高于首先考慮資金總額的約束：總投資額不能高于9000090000元。元。即即 20 x20 x1 150 x50 x2 29000090000。29一、約束條件一、約束條件 再來考慮風險約束：總風險不能超過再來考慮風險約束：總風險不能超過700700。投資的總風。投資的總風險為險為0.5x0.5x1 10.2x0.2x2 2。引入兩個變量引入兩個變量d d1 1+ +和和d d1 1- -, ,建立等式如下：建立等式如下： 0.5x0.5

39、x1 1 +0.2x +0.2x2 2=700+d=700+d1 1+ +-d-d1 1- - 其中，其中，d d1 1+ +表示總風險高于表示總風險高于700700的部分，的部分，d d1 1- -表示總風險少表示總風險少于于700700的部分，的部分，d d1 1+ +,d,d1 1- - 00。 目標規(guī)劃中把目標規(guī)劃中把d d1 1+ +、d d1 1- -這樣的變量稱為這樣的變量稱為偏差變量偏差變量。 偏差變量的作用是偏差變量的作用是允許約束條件不被精確滿足允許約束條件不被精確滿足。30 把等式轉換，可得到把等式轉換，可得到 0.5x0.5x1 1 +0.2x +0.2x2 2-d-d

40、1 1+ +d+d1 1- -=700=700 再來考慮年收入再來考慮年收入: : 年收入年收入=3x=3x1 1+4x+4x2 2 引入變量引入變量d d2 2+ +和和d d2 2- -，分別表示年收入超過與低于，分別表示年收入超過與低于1000010000的數量。的數量。 于是，第于是，第2 2個目標可以表示為個目標可以表示為 3x3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=10000=1000031二、有優(yōu)先權的目標函數二、有優(yōu)先權的目標函數 本問題中第一個目標的優(yōu)先權比第二個目標本問題中第一個目標的優(yōu)先權比第二個目標大。即最重要的目標是滿足風險不超過大。即最重

41、要的目標是滿足風險不超過700700。分配給第一個目標較高的優(yōu)先權分配給第一個目標較高的優(yōu)先權P P1 1分配給第二個目標較低的優(yōu)先權分配給第二個目標較低的優(yōu)先權P P2 232針對每一個優(yōu)先權，應當建立一個單一目標的線性規(guī)針對每一個優(yōu)先權，應當建立一個單一目標的線性規(guī)劃模型：劃模型：1.1. 首先建立具有最高優(yōu)先權的目標的線性規(guī)劃模型，首先建立具有最高優(yōu)先權的目標的線性規(guī)劃模型，求解；求解；2.2. 然后再按照優(yōu)先權逐漸降低的順序分別建立單一然后再按照優(yōu)先權逐漸降低的順序分別建立單一目標的線性規(guī)劃模型，方法是在原來模型的基礎目標的線性規(guī)劃模型，方法是在原來模型的基礎上修改目標函數，并把原來模

42、型求解所得的目標上修改目標函數，并把原來模型求解所得的目標最優(yōu)值作為一個新的約束條件加入到當前模型中，最優(yōu)值作為一個新的約束條件加入到當前模型中，并求解。并求解。33三、建模三、建模1 1針對優(yōu)先權最高的目標建立線性規(guī)劃針對優(yōu)先權最高的目標建立線性規(guī)劃建立線性規(guī)劃模型如下：建立線性規(guī)劃模型如下： Min dMin d1 1+ +s.t.s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=

43、10000=10000 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -00342 2針對優(yōu)先權次高的目標建立線性規(guī)劃針對優(yōu)先權次高的目標建立線性規(guī)劃優(yōu)先權次高（優(yōu)先權次高（P P2 2）的目標是總收益超過）的目標是總收益超過1000010000。建立線性規(guī)劃如下：建立線性規(guī)劃如下： Min dMin d2 2- - s.t. s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2

44、2- -=10000=10000 d d1 1+ +0 0 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -0035目標規(guī)劃的這種求解方法可以表述如下：目標規(guī)劃的這種求解方法可以表述如下： 1 1確定解的可行區(qū)域。確定解的可行區(qū)域。 2 2對優(yōu)先權對優(yōu)先權最高最高的目標求解，如果找不到能滿足該目標的目標求解，如果找不到能滿足該目標的解，則尋找最接近該目標的解。的解，則尋找最接近該目標的解。 3 3對優(yōu)先權對優(yōu)先權次之次之的目標進行求解。的目標進行求解。注意：必須保證優(yōu)先注意：必須保證優(yōu)先權高的目標不變。權高的目標不變。 4. 4. 重復

45、第重復第3 3步，直至所有優(yōu)先權的目標求解完。步，直至所有優(yōu)先權的目標求解完。 36四、目標規(guī)劃模型的標準化四、目標規(guī)劃模型的標準化 例例6 6中對兩個不同優(yōu)先權的目標單獨建立線性規(guī)劃進行中對兩個不同優(yōu)先權的目標單獨建立線性規(guī)劃進行求解。為簡便，把它們用一個模型來表達，如下：求解。為簡便，把它們用一個模型來表達，如下： min Pmin P1 1（d d1 1+ +）+P+P2 2（d d2 2- -） s.t.s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=70

46、0 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=10000=10000 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -0037管理運籌學軟件運用注意事項管理運籌學軟件運用注意事項 決策變量個數：不包括偏差變量（決策變量個數：不包括偏差變量（2 2） 優(yōu)先級數：目標優(yōu)先等級（優(yōu)先級數：目標優(yōu)先等級（2 2） 目標約束個數：含偏差變量約束條件個數（目標約束個數：含偏差變量約束條件個數（2 2） 絕對約束個數：不含偏差變量約束條件個數（絕對約束個數：不含偏差變量約束條件個數（1 1）38 3 3復雜情況下的目標

47、規(guī)劃復雜情況下的目標規(guī)劃例例9-79-7一工藝品廠商手工生產某兩種工藝品一工藝品廠商手工生產某兩種工藝品A A、B B，已知生產一，已知生產一件產品件產品A A需要耗費人力需要耗費人力2 2工時，生產一件產品工時，生產一件產品B B需要耗費人力需要耗費人力3 3工時。工時。A A、B B產品的單位利潤分別為產品的單位利潤分別為250250元和元和125125元。為了最大元。為了最大效率地利用人力資源，確定生產的效率地利用人力資源，確定生產的首要任務首要任務是保證人員高負是保證人員高負荷生產，要求每周總耗費人力資源不能低于荷生產，要求每周總耗費人力資源不能低于600600工時，但也不工時，但也不

48、能超過能超過680680工時的極限；工時的極限；次要任務次要任務是要求每周的利潤超過是要求每周的利潤超過7000070000元；在前兩個任務的前提下，為了保證庫存需要，元；在前兩個任務的前提下，為了保證庫存需要，要求要求每周產品每周產品A A和和B B的產量分別不低于的產量分別不低于200200和和120120件，因為件，因為B B產品比產品比A A產品更重要，不妨假設產品更重要，不妨假設B B完成最低產量完成最低產量120120件的重要性是件的重要性是A A完成完成200200件的重要性的件的重要性的2 2倍。倍。 試求如何安排生產？試求如何安排生產？39解：解： 本問題中有本問題中有3個不

49、同優(yōu)先權的目標，不妨用個不同優(yōu)先權的目標，不妨用P1、P2、P3表示從高至低的優(yōu)先權。表示從高至低的優(yōu)先權。 對應對應P1有兩個目標：每周總耗費人力資源不能低于有兩個目標：每周總耗費人力資源不能低于600工時工時,也不能超過也不能超過680工時；工時； 對應對應P2有一個目標：每周的利潤超過有一個目標：每周的利潤超過70000元；元； 對應對應P3有兩個目標：每周產品有兩個目標：每周產品A和和B的產量分別不低的產量分別不低于于200和和120件。件。40采用簡化模式，最終得到目標線性規(guī)劃如下：采用簡化模式，最終得到目標線性規(guī)劃如下： Min PMin P1 1(d(d1 1+ +)+ P)+

50、P1 1(d(d2 2)+P)+P2 2(d(d3 3- -)+ P)+ P3 3(d(d4 4- -)+ P)+ P3 3( (2 2d d5 5- -) ) s.t. s.t. 2x1+3x2-d d1 1+ +d d1 1- -=680 對應第對應第1個目標個目標 2x1+3x2-d d2 2+ +d d2 2- -=600 對應第對應第2個目標個目標 250 x1+125x2-d3 + +d3-70000 對應第對應第3個目標個目標 x1-d d4 4+ +d d4 4- -=200 對應第對應第4個目標個目標 x2-d d5 5+ +d d5 5- -=120 對應第對應第5個目標個

51、目標 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -,d,d3 3+ +,d,d3 3- -,d,d4 4+ +,d,d4 4- -,d,d5 5+ +,d,d5 5- -00罰數權重罰數權重41 使用運籌學軟件求解可得：使用運籌學軟件求解可得：x x1 1=250=250；x x2 2=60=60；d d1 1+ +=0=0；d d1 1- -=0=0；d d2 2+ +=80=80；d d2 2- -=0=0；d d3 3+ +=0=0；d d3 3- -=0=0；d d4 4+ +=50=50；d d4 4- -=0=0；d d

52、5 5+ +=0=0；d d5 5- -=60=60，目標函數目標函數120120。 可見，目標可見，目標1 1、目標、目標2 2、目標、目標3 3和目標和目標4 4達達到了，但目標到了，但目標5 5有一些偏差。有一些偏差。 42 4 4加權目標規(guī)劃加權目標規(guī)劃加權目標規(guī)劃加權目標規(guī)劃是另一種解決多目標決策問題的方法，其是另一種解決多目標決策問題的方法，其基本方法基本方法是是: :1.1.通過量化的方法分配給通過量化的方法分配給每個目標的偏離的嚴重程度一個罰數每個目標的偏離的嚴重程度一個罰數權重權重，2.2.然后建立總的目標函數，該目標函數表示的目標是要使每個然后建立總的目標函數，該目標函數表

53、示的目標是要使每個目標函數與各自目標的目標函數與各自目標的加權偏差之和最小加權偏差之和最小，假設所有單個的目標函數及約束條件都符合線性規(guī)劃的要求，假設所有單個的目標函數及約束條件都符合線性規(guī)劃的要求，那么，那么，整個問題都可以描述為一個線性規(guī)劃的問題。整個問題都可以描述為一個線性規(guī)劃的問題。43在例在例7 7中我們對中我們對 每周總耗費的人力資源超過每周總耗費的人力資源超過680680工時或低于工時或低于600600工時工時的每工時罰數權重定為的每工時罰數權重定為7 7； 每周利潤低于每周利潤低于7000070000元時，每元的罰數權重為元時，每元的罰數權重為5 5； 每周產品每周產品A A產

54、量低于產量低于200200件時每件罰數權重為件時每件罰數權重為2 2， 每周產品每周產品B B產量低于產量低于120120件時每件罰數權重為件時每件罰數權重為4 4。44 則其目標函數化為：則其目標函數化為： min7d1+7d2-+5d3-+2d4-+4d5- 這就變成了一個普通的單一目標的線性規(guī)劃問題這就變成了一個普通的單一目標的線性規(guī)劃問題 min7d1+7d2-+5d3-+2d4-+4d5- s.t. 2x1+3x2-d1+d1-=680 2x1+3x2-d2+d2-=680 250 x1+125x2-d3+d3-=70000 x1-d4+d4-=200 x2-d5+d5-=120 x

55、1,x2,d1+,d1-,d2-,d2+, d3+,d3-,d4+,d4-,d5+,d5-0 。練練 習習 教材教材P212P212習題習題1-101-1045462.3 2.3 動態(tài)規(guī)劃動態(tài)規(guī)劃 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理 3 3動態(tài)規(guī)劃的應用動態(tài)規(guī)劃的應用47 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例例例10-1 最短路徑問題最短路徑問題 下圖表示從起點下圖表示從起點A到終點到終點E之間各點的距離。求之間各點的距離。求A到到E的最短路徑。的最短路徑。BACBDBCD

56、EC412312312322164724838675611064375148用窮舉法的計算量用窮舉法的計算量: : 如果從如果從A A到到E E的站點有的站點有k k個，除個，除A A、E E之外每站有之外每站有3 3個位置則個位置則總共有總共有3 3k-1k-12 2條路徑；條路徑； 計算各路徑長度總共要進行計算各路徑長度總共要進行 (k+1) 3(k+1) 3k-1k-12 2次加法以及次加法以及3 3k-k-1 12-12-1次比較。隨著次比較。隨著 k k 的值增加時，需要進行的加法和比較的的值增加時，需要進行的加法和比較的次數將迅速增加；次數將迅速增加； 例如當例如當 k=20k=2

57、0時，加法次數為時，加法次數為 4.25508339662274.255083396622710101515 次，次，比較比較 1.37260754729771.372607547297710101414 次。若用次。若用1 1億次億次/ /秒的計算機計算秒的計算機計算需要約需要約508508天。天。49討論：討論： 1 1、以上求從、以上求從A A到到E E的最短路徑問題，可以轉化為四個性質完的最短路徑問題，可以轉化為四個性質完全相同，但規(guī)模較小的子問題，即分別從全相同，但規(guī)模較小的子問題，即分別從D Di i 、C Ci i、B Bi i、A A到到E E的最短路徑問題。的最短路徑問題。

58、第四階段：兩個始點第四階段：兩個始點D D1 1和和D D2 2，終點只有一個；，終點只有一個； 表表10-110-1分析得知：從分析得知：從D D1 1和和D D2 2到到E E的最短路徑唯一。的最短路徑唯一。 階段階段4本階段始點本階段始點（狀態(tài)）（狀態(tài)）本階段各終點（決策）本階段各終點（決策）到到E的最短距離的最短距離本階段最優(yōu)終點本階段最優(yōu)終點（最優(yōu)決策（最優(yōu)決策) E D1 D2 10* 6 10 6 E E50 第三階段：有三個始點第三階段：有三個始點C1，C2，C3，終點有，終點有D1，D2，對始點，對始點和終點進行分析和討論分別求和終點進行分析和討論分別求C1，C2，C3到到D

59、1，D2 的最短的最短路徑問題：路徑問題： 表表10-2分析得知：如果經過分析得知：如果經過C1，則最短路為則最短路為C1-D2-E； 如果經過如果經過C2，則最短路為則最短路為C2-D2-E； 如果經過如果經過C3，則最短路為，則最短路為C3-D1-E。 階段階段3本階段始點本階段始點（狀態(tài)）（狀態(tài)）本階段各終點（決策）本階段各終點（決策）到到E的最短距離的最短距離本階段最優(yōu)終點本階段最優(yōu)終點（最優(yōu)決策（最優(yōu)決策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D151第二階段：有第二階段

60、：有4個始點個始點B1,B2,B3,B4，終點有，終點有C1,C2,C3。對始點。對始點和終點進行分析和討論分別求和終點進行分析和討論分別求B1,B2,B3,B4到到C1,C2,C3 的最短的最短路徑問題：路徑問題： 表表10-3 分析得知：如果經過分析得知：如果經過B1，則走，則走B1-C2-D2-E； 如果經過如果經過B2，則走，則走B2-C3-D1-E； 如果經過如果經過B3，則走，則走B3-C3-D1-E； 如果經過如果經過B4，則走，則走B4-C3-D1-E。 階段階段2本階段始點本階段始點（狀態(tài)）（狀態(tài)） 本階段各終點（決策）本階段各終點（決策）到到E的最的最短距離短距離本階段最優(yōu)