高等運籌第五講劉巍大連海事大學(xué)

1、高等運籌學(xué)高等運籌學(xué)大連海事大學(xué)大連海事大學(xué)劉巍劉巍第二篇 運籌學(xué)中的數(shù)學(xué)規(guī)劃 第四章第四章 線性規(guī)劃線性規(guī)劃 第五章第五章 非線性規(guī)劃非線性規(guī)劃 第六章第六章 錐規(guī)劃、矩陣規(guī)劃及變分不等式錐規(guī)劃、矩陣規(guī)劃及變分不等式 第七章第七章 整數(shù)規(guī)劃整數(shù)規(guī)劃 第八章第八章 動態(tài)規(guī)劃動態(tài)規(guī)劃 第九章第九章 向量優(yōu)化（多目標(biāo)優(yōu)化）向量優(yōu)化（多目標(biāo)優(yōu)化）第七章 整數(shù)規(guī)劃 整數(shù)規(guī)劃是帶整數(shù)變量的最優(yōu)化問題，即整數(shù)規(guī)劃是帶整數(shù)變量的最優(yōu)化問題，即求解一個全部或部分變量為整數(shù)的多元函求解一個全部或部分變量為整數(shù)的多元函數(shù)受約束于一組等式和不等式條件的最優(yōu)數(shù)受約束于一組等式和不等式條件的最優(yōu)化間題?；g題。 整數(shù)規(guī)

2、劃的歷史可以追溯到整數(shù)規(guī)劃的歷史可以追溯到20世紀(jì)世紀(jì)50年代，丹年代，丹齊格首先發(fā)現(xiàn)可以用齊格首先發(fā)現(xiàn)可以用0-1變量來刻畫最優(yōu)化模變量來刻畫最優(yōu)化模型中的固定費用、變量上界、非凸分片線性函型中的固定費用、變量上界、非凸分片線性函數(shù)等。他和富爾克森、約翰遜對旅行商間題的數(shù)等。他和富爾克森、約翰遜對旅行商間題的研究成為后來分支定界法和現(xiàn)代混合整數(shù)規(guī)劃研究成為后來分支定界法和現(xiàn)代混合整數(shù)規(guī)劃算法的開端。算法的開端。1958年戈莫里發(fā)現(xiàn)了第一個一般年戈莫里發(fā)現(xiàn)了第一個一般線性整數(shù)規(guī)劃的收斂算法線性整數(shù)規(guī)劃的收斂算法割平面方法。隨著割平面方法。隨著整數(shù)規(guī)劃理論和算法的發(fā)展，整數(shù)規(guī)劃已成為整數(shù)規(guī)劃理論

3、和算法的發(fā)展，整數(shù)規(guī)劃已成為應(yīng)用最廣泛的最優(yōu)化方法之一，特別是近年來應(yīng)用最廣泛的最優(yōu)化方法之一，特別是近年來整數(shù)規(guī)劃算法技術(shù)和軟件系統(tǒng)的發(fā)展和推廣，整數(shù)規(guī)劃算法技術(shù)和軟件系統(tǒng)的發(fā)展和推廣，整數(shù)規(guī)劃得到了廣泛的應(yīng)用和發(fā)展。整數(shù)規(guī)劃得到了廣泛的應(yīng)用和發(fā)展。 整數(shù)規(guī)劃整數(shù)規(guī)劃什么是整數(shù)規(guī)劃？什么是整數(shù)規(guī)劃？ 整數(shù)規(guī)劃與線性規(guī)劃有什么關(guān)系？整數(shù)規(guī)劃與線性規(guī)劃有什么關(guān)系？ 從集裝箱托運談起從集裝箱托運談起集裝箱托運問題集裝箱托運問題例例1. 某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。量、可

4、獲利潤以及托運所受限制如表所示。甲種貨物至多托運甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大件，問兩種貨物各托運多少件，可使獲得利潤最大?貨物每件體積（立方英尺）每件重量（百千克）每件利潤（百元）甲乙19527344023托運限制1365140 解：設(shè)解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運的件數(shù)分別為甲、乙兩種貨物托運的件數(shù)，建立模型，建立模型 目標(biāo)函數(shù)：目標(biāo)函數(shù)： max z = 2x1 +3 x2 約束條件：約束條件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 為整數(shù)。為整數(shù)。如果去掉最后一個約束

5、，就是一個線性規(guī)劃問題如果去掉最后一個約束，就是一個線性規(guī)劃問題 求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃的非整數(shù)解加以處理都能或去尾法對線性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。解決的，而要用整數(shù)規(guī)劃的方法加以解決。 在整數(shù)規(guī)劃中，如果所有的變量都為非負(fù)整數(shù)在整數(shù)規(guī)劃中，如果所有的變量都為非負(fù)整數(shù)，則稱為，則稱為純整數(shù)規(guī)劃問題純整數(shù)規(guī)劃問題；如果有一部分變量；如果有一部分變量為負(fù)整數(shù)，則稱之為為負(fù)整數(shù)，則稱之為混合整數(shù)規(guī)劃問題混合整數(shù)規(guī)劃問題。在整。在整數(shù)規(guī)劃中，如果變量的取值只限于數(shù)規(guī)劃中，如果變量的取值只

6、限于0和和1，這樣，這樣的變量我們稱之為的變量我們稱之為0-1變量變量。在純整數(shù)規(guī)劃和。在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題中，如果所有的變量都為混合整數(shù)規(guī)劃問題中，如果所有的變量都為0-1變量，則稱之為變量，則稱之為0-1規(guī)劃規(guī)劃。得到線性規(guī)劃的最優(yōu)解為得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為14。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =61 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法1 1

7、整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法性質(zhì)性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。例例2 2： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 為整數(shù)例3： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x3 1

8、x1,x2,x3 0 x1，x3 為整數(shù), x3 為0-1變量用管理運籌學(xué)軟件求解得： x1 = 5 x2 = 2 x3 = 2 用管理運籌學(xué)軟件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.252 2整數(shù)規(guī)劃的計算機求解整數(shù)規(guī)劃的計算機求解3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用 一、投資場所的選擇一、投資場所的選擇 例例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有市部，擬議中有10個位置個位置 aj (j1，2，3，10)可供選擇，考慮到各地可供選擇，考慮到各地區(qū)居民的消費水平及居民居住

9、密集度，規(guī)定：區(qū)居民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由在東區(qū)由a1 ， a2 ，a3 三個點至多選擇兩個；三個點至多選擇兩個； 在西區(qū)由在西區(qū)由a4 ， a5 兩個點中至少選一個；兩個點中至少選一個； 在南區(qū)由在南區(qū)由a6 ， a7 兩個點中至少選一個；兩個點中至少選一個； 在北區(qū)由在北區(qū)由a8 ， a9 ， a10 三個點中至少選兩個。三個點中至少選兩個。 aj 各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況見表所示情況見表所示 (單位：萬元單位：萬元)。但投資總額不能超過。但投資總額不能超過720萬元，問應(yīng)

10、選擇哪萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大幾個銷售點，可使年利潤為最大?3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用解：解：設(shè)：設(shè)：0-1變量變量 xi = 1 (ai 點被選用）或點被選用）或 0 (ai 點沒被選用）點沒被選用）。 這樣我們可建立如下的數(shù)學(xué)模型：這樣我們可建立如下的數(shù)學(xué)模型：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. 100100

11、 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 x1010 720 720 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,

12、= 1,2,3,10,10二、固定成本問題 例例5高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為 150 萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。 資源小號容器中號容器大號容器金屬板（噸）248勞動力（人月）234機器設(shè)備（臺月）123解：這是一個整數(shù)規(guī)劃的問題。解：這

13、是一個整數(shù)規(guī)劃的問題。 設(shè)設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè)種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第當(dāng)生產(chǎn)第 i種容器種容器, 即即 xi 0 時時) 或或0（當(dāng)不生產(chǎn)第（當(dāng)不生產(chǎn)第 i種容種容器即器即 xi = 0 時）。時）。引入約束引入約束 xi m yi ，i =1，2，3，m充分大，以保證當(dāng)充分大，以保證當(dāng) yi = 0 時，時，xi = 0 。 這樣我們可建立如下的數(shù)學(xué)

14、模型：max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi m yi ，i =1，2，3，m充分大 xj 0 yj 為0-1變量，i = 1,2,3三、指派問題三、指派問題 有有 n n 項不同的任務(wù)，恰好項不同的任務(wù)，恰好 n n 個人可分別承擔(dān)這些任務(wù)，個人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項任務(wù)的效率等情況也不同。但由于每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個人去完成一項任務(wù)，怎樣

15、把現(xiàn)假設(shè)必須指派每個人去完成一項任務(wù)，怎樣把 n n 項任務(wù)項任務(wù)指派給指派給 n n 個人，使得完成個人，使得完成 n n 項任務(wù)的總的效率最高，這就項任務(wù)的總的效率最高，這就是指派問題。是指派問題。例例6 6有四個工人，要分別指派他們完成四項不同的工作，每人做各有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應(yīng)如何指派工作，才能使總項工作所消耗的時間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少。的消耗時間為最少。 工作工人abcd甲15182124乙19232218丙26171619丁19212317解：解：引入引入0 01 1變量變量 x

16、xijij，并令并令 x xij ij = 1(= 1(當(dāng)指派第當(dāng)指派第 i i人去完成第人去完成第j j項工作時項工作時) )或或0 0（當(dāng)不指派第（當(dāng)不指派第 i i人去完成第人去完成第j j項工作時項工作時) )這可以表示為一個這可以表示為一個0-1整數(shù)規(guī)劃問題：整數(shù)規(guī)劃問題：min min z=15z=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+1+16 6x x3333+19+

17、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 x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一項工作乙只能干一項工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一項工作丙只能干一項工作) ) x x4141+ + x x424

18、2+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一項工作丁只能干一項工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( a= 1 ( a工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + 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+

19、+ x x4444= 1 ( d= 1 ( d工作只能一人干工作只能一人干) ) x xijij 為為0-10-1變量變量，i,j i,j = 1,2,3,4= 1,2,3,4四、分布系統(tǒng)設(shè)計四、分布系統(tǒng)設(shè)計例例7某企業(yè)在某企業(yè)在 a1 地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為 30 千箱，千箱，為了擴大生產(chǎn)，打算在為了擴大生產(chǎn)，打算在 a2，a3，a4，a5地中再選擇幾個地方建地中再選擇幾個地方建廠。已知在廠。已知在 a2 ， a3，a4，a5地建廠的固定成本分別為地建廠的固定成本分別為175千元、千元、300千元、千元、375千元、千元、500千元，另外，千元，

20、另外， a1產(chǎn)量及產(chǎn)量及a2，a3，a4，a5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價(每千每千箱運費箱運費)如下表所示。如下表所示。 a) 問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最小定成本和總的運輸費用之和最小? b) 如果由于政策要求必須在如果由于政策要求必須在a2，a3地建一個廠，應(yīng)在哪幾個地方建地建一個廠，應(yīng)在哪幾個地方建廠廠? 銷 地產(chǎn) 地b1b2b3產(chǎn) 量 (千 噸 )a184330a252310a343420a49753

21、0a5104240銷 量 (千 噸 )302020解：解： a) 設(shè) xij為從ai 運往bj 的運輸量(單位千箱)， yk = 1(當(dāng)ak 被選中時)或0（當(dāng)ak 沒被選中時),k =2,3,4,5這可以表示為一個整數(shù)規(guī)劃問題：min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53其中前4項為固定投資額，后面的項為運輸費用。s.t. x11+ x12+ x13 30 ( a1 廠的產(chǎn)量限制) x21+ x22+ x23 10y2

22、 ( a2 廠的產(chǎn)量限制) x31+ x32+ x33 20y3 ( a3 廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( a4 廠的產(chǎn)量限制) x51+ x52+ x53 40y5 ( a5 廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x51 = 30 ( b1 銷地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( b2 銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( b3 銷地的限制) xij 0，i = 1,2,3,4,5； j = 1,2,3， yk 為0-1變量，k =2,3,4,5五、投資問題五、投資問題

23、 例例8 8某公司在今后五年內(nèi)考慮給以下的項目投資。已知：某公司在今后五年內(nèi)考慮給以下的項目投資。已知：項目項目a a：從第一年到第四年每年年初需要投資，并于次年末回收本利從第一年到第四年每年年初需要投資，并于次年末回收本利115%， 但要求第一年投資最低金額為但要求第一年投資最低金額為4萬元，第二、三、四年不限萬元，第二、三、四年不限；項目項目b b：第三年初需要投資，到第五年末能回收本利第三年初需要投資，到第五年末能回收本利128，但規(guī)定最低投資，但規(guī)定最低投資金額為金額為3萬元，最高金額為萬元，最高金額為5萬元萬元； 項目項目 c：第二年初需要投資，到第五年末能回收本利：第二年初需要投資

24、，到第五年末能回收本利140%，但規(guī)定其投資，但規(guī)定其投資額或為額或為2萬元或為萬元或為4萬元或為萬元或為6萬元或為萬元或為8萬元。萬元。 項目項目 d：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項投，此項投資金額不限。資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項目的每年投資額，萬元，問它應(yīng)如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大使到第五年末擁有的資金本利總額為最大?解：解：1) 設(shè)設(shè)x xiaia、x xibib、x xicic、x xid id ( i 1，2，3，4，5)

25、分別表示第分別表示第 i 年年初給項目年年初給項目a，b，c，d的投資額；的投資額； 設(shè)設(shè)yia， yib，是，是01變量，并規(guī)定取變量，并規(guī)定取 1 時分別表示第時分別表示第 i 年給年給a、b投資，投資，否則取否則取 0（ i = 1, 2, 3, 4, 5）。）。 設(shè)設(shè)yic 是非負(fù)整數(shù)變量，并規(guī)定：第是非負(fù)整數(shù)變量，并規(guī)定：第2年投資年投資c項目項目8萬元時，取值為萬元時，取值為4；第第 2年投資年投資c項目項目6萬元時，取值萬元時，取值3；第；第2年投資年投資c項目項目4萬元時，取值萬元時，取值2；第第2年投資年投資c項目項目2萬元時，取值萬元時，取值1；第；第2年不投資年不投資c項

26、目時，取值項目時，取值0； 這樣我們建立如下的決策變量：這樣我們建立如下的決策變量： 第1年 第2年 第3年 第4年 第5年 a x1a x2a x3a x4a b x3b c x2c=20000y2c d x1d x2d x3d x4d x5d 2 2）約束條件：）約束條件：第一年：年初有100000元，d項目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x1a+ x1d = 100000；第二年：a的投資第二年末才可收回，故第二年年初的資金為1.06x1d，于是x2a+x2c+x2d = 1.06x1d；第三年：年初的資金為 1.15x1a+1.06x2d，于是 x3a+x3b+

27、x3d = 1.15x1a+ 1.06x2d；第四年：年初的資金為 1.15x2a+1.06x3d，于是 x4a + x4d = 1.15x2a+ 1.06x3d；第五年：年初的資金為 1.15x3a+1.06x4d，于是 x5d = 1.15x3a+ 1.06x4d。 關(guān)于項目a的投資額規(guī)定: x1a 40000y1a ，x1a 200000y1a ，200000是足夠大的數(shù)；保證當(dāng) y1a = 0時， x1a = 0 ；當(dāng)y1a = 1時，x1a 40000 。 關(guān)于項目b的投資額規(guī)定: x3b 30000y3b ，x3b 50000y3b ； 保證當(dāng) y3b = 0時， x3b = 0

28、；當(dāng)y3b = 1時，50000 x3b 30000 。 關(guān)于項目c的投資額規(guī)定: x2c = 20000y2c ，y2c = 0，1，2，3，4。3 3）目標(biāo)函數(shù)及模型：）目標(biāo)函數(shù)及模型： max z = 1.15x4a+ 1.40 x2c+ 1.28x3b + 1.06x5d s.t. x1a+ x1d = 100000； x2a+x2c+x2d = 1.06x1d； x3a+x3b+x3d = 1.15x1a+ 1.06x2d； x4a+x4d = 1.15x2a+ 1.06x3d； x5d = 1.15x3a+ 1.06x4d； x1a 40000y1a ， x1a 200000y1a

29、 ， x3b 30000y3b ， x3b 50000y3b ； x2c = 20000y2c ， yia， yib = 0 或 1，i = 1,2,3,4,5 y2c = 0，1，2，3，4 xia ，xib ，xic ，xid 0 ( i = 1、2、3、4、5） 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法 分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決混合整數(shù)規(guī)劃的問題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法而編制成的。 分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把

30、相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。 下面以例9予以說明。例9 用分枝定界法求解整數(shù)規(guī)劃max 2x1+3x2s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1,x2 0且x1,x2為整數(shù)解: (一)先求出以下線性規(guī)劃的解： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1,x2 0 得z1=14.66,x1=2.44,x2=3.26 (二)確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z*初始上界 和下界z。 分析后，

31、知道 =14.66，由觀察法得下界z=13（當(dāng)x1=2,x2=3時）。zz(三)將一個線性規(guī)劃問題分為兩枝，并求解。 可由x12或x13中取值。將線性規(guī)劃1分解為兩支，如下： 線性規(guī)劃2： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 線性規(guī)劃3： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86(四)修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。

32、 經(jīng)分析，將上界 =14.66修改為 =14.58，z=13。(五)在線性規(guī)劃2和線性規(guī)劃3中選擇一個上界最大的線性規(guī)劃，即線性規(guī)劃3，進行分枝。 線性規(guī)劃3分解為線性規(guī)劃4和線性規(guī)劃5，如下： 線性規(guī)劃4： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 線性規(guī)劃5： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 3 x2 3 x1,x2 0 無可行解zz(六)進一步修改整數(shù)規(guī)劃最優(yōu)目標(biāo)函數(shù)值z*的上下界。 從線

33、性規(guī)劃2，4，5中修改上下界。分析后，可得 =14， z=14。都取線性規(guī)劃2，4，5中的整數(shù)可行解的目標(biāo)函數(shù)值的最大值。性質(zhì)2： 當(dāng)整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z*的上界 等于其下界z時，該整數(shù)規(guī)劃的最優(yōu)解已經(jīng)被求出。這個整數(shù)的最優(yōu)解即為其目標(biāo)函數(shù)值取此下界的對應(yīng)線性規(guī)劃的整數(shù)可行解。zz用圖8-2表示例9的求解過程與求解結(jié)果z線性規(guī)劃線性規(guī)劃1z1=14.66x1=2.44x2=3.26z z=13, =13, =14.66 線性規(guī)劃線性規(guī)劃2z2=13.90x1=2x2=3.30線性規(guī)劃線性規(guī)劃3z3=14.58x1=3x2=2.86線性規(guī)劃線性規(guī)劃4z4=14.00x1=4x2=2線性規(guī)劃

34、線性規(guī)劃5無可行解無可行解x12x13x22x23z z=13, =13, =14.58 z z=14, =14, =14圖圖8-28-2zz z 從以上解題過程可得用分枝定界法求解目標(biāo)函數(shù)值最大的整數(shù)規(guī)劃的步驟，我們將求解的整數(shù)規(guī)劃問題稱為a，將與其相對應(yīng)的線性規(guī)劃問題稱為b： 第一步：求解問題b，可得以下情況之一： 1.b沒有可行解，則a也沒有可行解，求解過程停止。 2.b有最優(yōu)解，且符合問題a的整數(shù)條件，則b的最優(yōu)解即為a的最優(yōu)解，求解過程停止。 3.b有最優(yōu)解，但不符合a的整數(shù)條件，記其目標(biāo)函數(shù)值為z1。 第二步：確定a的最優(yōu)目標(biāo)函數(shù)值z*的上下界，其上界即為z1, =z1,再用觀察法

35、找到a的一個整數(shù)可行解，求其目標(biāo)函數(shù)值作為z*的下界，記為z 。 第三步：判斷 是否等于z 。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標(biāo)函數(shù)值等于z的a的那個整數(shù)可行解；否則進行第四步。zz 第四步：在b的最優(yōu)解中選一個最遠離整數(shù)要求的變量，不妨設(shè)此變量為xj，以bj表示小于bj的最大整數(shù)，構(gòu)造以下兩個約束條件，并加入問題b，得到b的兩個分枝b1和b2。xj bj和xj bj+1 第五步：求解b1和b2 。修改a問題的最優(yōu)目標(biāo)函數(shù)值z*的上下界， 和z 。 第六步：比較和剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中若有小于z者，則剪掉這枝（用打表示），即以后不再考慮了。若大于 ，則不符合整數(shù)條件，則重復(fù)第三步至第六

36、步，直至 =z，求出最優(yōu)解為止。 對于求目標(biāo)函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。zz整數(shù)規(guī)劃問題的困難和挑戰(zhàn)來源于三個方面整數(shù)規(guī)劃問題的困難和挑戰(zhàn)來源于三個方面: 一是大部分整數(shù)規(guī)劃問題都是一是大部分整數(shù)規(guī)劃問題都是np一難的，故本質(zhì)一難的，故本質(zhì)上不太可能存在和線性規(guī)劃和凸規(guī)劃一樣有效的算上不太可能存在和線性規(guī)劃和凸規(guī)劃一樣有效的算法法; 二是對整數(shù)點集合二是對整數(shù)點集合(如多面體格點理論和全單模理如多面體格點理論和全單模理論論)和整數(shù)變量的函數(shù)在數(shù)學(xué)上缺乏有力的理論和和整數(shù)變量的函數(shù)在數(shù)學(xué)上缺乏有力的理論和工具工具; 三是實際間題的規(guī)模往往超過現(xiàn)有算法的求解能力三是實際間題的

37、規(guī)模往往超過現(xiàn)有算法的求解能力，盡管現(xiàn)有的一些整數(shù)規(guī)劃軟件可以求解任意線性，盡管現(xiàn)有的一些整數(shù)規(guī)劃軟件可以求解任意線性、二次和非線性整數(shù)規(guī)劃問題，但往往不能處理來、二次和非線性整數(shù)規(guī)劃問題，但往往不能處理來源于實際間題的整數(shù)規(guī)劃模型，例如運輸和交通中源于實際間題的整數(shù)規(guī)劃模型，例如運輸和交通中的大規(guī)模的大規(guī)模0-1混合線性整數(shù)規(guī)劃間題，金融優(yōu)化中混合線性整數(shù)規(guī)劃間題，金融優(yōu)化中的離散約束問題等。的離散約束問題等。 整數(shù)規(guī)劃未來發(fā)展方向和關(guān)鍵問題包括整數(shù)規(guī)劃未來發(fā)展方向和關(guān)鍵問題包括: (1)整數(shù)多面體凸包的刻畫整數(shù)多面體凸包的刻畫; (2)隨機整數(shù)規(guī)劃隨機整數(shù)規(guī)劃; (3)多層整數(shù)規(guī)劃多層整數(shù)

38、規(guī)劃; (4)混合混合0-1二次整數(shù)規(guī)劃二次整數(shù)規(guī)劃; (5)協(xié)正規(guī)劃協(xié)正規(guī)劃; (6)半定整數(shù)規(guī)劃。半定整數(shù)規(guī)劃。第八章 動態(tài)規(guī)劃 當(dāng)系統(tǒng)模型具備馬爾科夫性，同時目標(biāo)函數(shù)當(dāng)系統(tǒng)模型具備馬爾科夫性，同時目標(biāo)函數(shù)可分且嵌套單調(diào)時，基于貝爾曼提出的最優(yōu)可分且嵌套單調(diào)時，基于貝爾曼提出的最優(yōu)性原理，運用動態(tài)規(guī)劃可將求解多階段全局性原理，運用動態(tài)規(guī)劃可將求解多階段全局最優(yōu)決策問題分解為一系列在各個時間段上最優(yōu)決策問題分解為一系列在各個時間段上的局部優(yōu)化問題。相比其它解法，特別是在的局部優(yōu)化問題。相比其它解法，特別是在有擾動或在隨機情況下，動態(tài)規(guī)劃總是能有有擾動或在隨機情況下，動態(tài)規(guī)劃總是能有效地提供一

39、個在當(dāng)前信息集下的最優(yōu)反饋控效地提供一個在當(dāng)前信息集下的最優(yōu)反饋控制策略。制策略。馬爾科夫性 在某些隨機系統(tǒng)中，有一類具有“無后效性性質(zhì)”，即當(dāng)隨機過程在某一時刻to所處的狀態(tài)已知的條件下，過程在時刻tto時所處的狀態(tài)只和to時刻有關(guān)，而與to以前的狀態(tài)無關(guān)。這種在已知“現(xiàn)在”的條件下，“未來”與“過去”彼此獨立的特性就被稱為馬爾科夫性，具有這種性質(zhì)的隨機過程就叫做馬爾科夫過程，其最原始的模型就是馬爾科夫鏈。貝爾曼“最優(yōu)性原理” 這個原理歸結(jié)為用一組基本的遞推關(guān)系式使過程連續(xù)的最優(yōu)轉(zhuǎn)移，它可以求這樣的最優(yōu)解，這些最優(yōu)解是以計算每個決策的后果并對今后的決策制定最優(yōu)決策為基礎(chǔ)的，但在求最優(yōu)解時要按

40、倒過來的順序進行，即從最終狀態(tài)開始到初始狀態(tài)為止。39動態(tài)規(guī)劃動態(tài)規(guī)劃1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)401 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例例例1 最短路徑問題最短路徑問題 下圖表示從起點a到終點e之間各點的距離。求a到e的最短路徑。bacbdbcdec41231231232216472483867561106437 51411 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例用窮舉法的計算量用窮舉

41、法的計算量: 如果從a到e的站點有k個，除a、e之外每站有3個位置則總共有3k-12條路徑； 計算各路徑長度總共要進行 (k+1) 3k-12次加法以及3k-12-1次比較。隨著 k 的值增加時，需要進行的加法和比較的次數(shù)將迅速增加； 例如當(dāng) k=20時，加法次數(shù)為 4.25508339662271015 次，比較 1.37260754729771014 次。若用1億次/秒的計算機計算需要約508天。42bacbdbcdec41231231232216472483867561106437 51431 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例討論： 1、以上求從a到e的最短路徑

42、問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從di 、ci、bi、a到e的最短路徑問題。 第四階段：兩個始點d1和d2，終點只有一個； 表10-1分析得知：從d1和d2到e的最短路徑唯一。 階段4本階段始點（狀態(tài)）本階段各終點（決策）到e的最短距離本階段最優(yōu)終點（最優(yōu)決策) e d1 d2 10* 6 10 6 e e44bacbdbcdec41231231232216472483867561106437 5145 第三階段：有三個始點c1，c2，c3，終點有d1，d2，對始點和終點進行分析和討論分別求c1，c2，c3到d1，d2 的最短路徑問題： 表10-2分析得知：如果經(jīng)過

43、c1，則最短路為c1-d2-e； 如果經(jīng)過c2，則最短路為c2-d2-e； 如果經(jīng)過c3，則最短路為c3-d1-e。 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段3本階段始點（狀態(tài)）本階段各終點（決策）到e的最短距離本階段最優(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 d146bacbdbcdec41231231232216472483867561106437 5147第二階段：有4個始點b1,b2,b3,b4，終點有c1,c2,c3。對始點和終點

44、進行分析和討論分別求b1,b2,b3,b4到c1,c2,c3 的最短路徑問題： 表10-3 分析得知：如果經(jīng)過b1，則走b1-c2-d2-e； 如果經(jīng)過b2，則走b2-c3-d1-e； 如果經(jīng)過b3，則走b3-c3-d1-e； 如果經(jīng)過b4，則走b4-c3-d1-e。 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段2本階段始點（狀態(tài)） 本階段各終點（決策）到e的最短距離本階段最優(yōu)終點（最優(yōu)決策) c1 c2 c3 b1 b2 b3 b4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11

45、=17 2+11=13 3+11=14 1+11=12 12 13 14 12 c2 c3 c3 c348bacbdbcdec41231231232216472483867561106437 5149 第一階段：只有1個始點a，終點有b1,b2,b3,b4 。對始點終點進行分析和討論分別求a到b1,b2,b3,b4的最短路徑問題： 表10-4 最后，可以得到：從a到e的最短路徑為a b4 c3 d1 e1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段1本階段始點(狀態(tài)) 本階段各終點（決策）到e的最短距離本階段最優(yōu)終點(最優(yōu)決策) b1 b2 b3 b4 a 4+12=16

46、 3+13=163+14=172+12=14 12 c250 以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從a到d的最短路徑，同時，也得到了從圖中任一點到e的最短路徑。 以上過程，僅用了22次加法，計算效率遠高于窮舉法。bacbdbcdec412312312332164724 838675161060106121111121314144b127 5121 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例51一、基本概念： 1、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。 2、狀態(tài)sk：能確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量

47、狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。 決策允許集合dk(sk)：在狀態(tài)sk下，允許采取決策的全體。 4、策略pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。p1,n(s1)即為全過程策略。 5、狀態(tài)轉(zhuǎn)移方程 sk+1=tk(sk, xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理52 6、階段指標(biāo)函數(shù)vk(sk, xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)。 過程指標(biāo)函數(shù)vk,n(sk,

48、xk, xk+1, xn)：從狀態(tài)sk出發(fā)，選擇決策xk, xk+1, , xn所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即 vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可加性，或 vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可乘性。二、基本方程： 最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略pk,n，過程指標(biāo)vk,n的最優(yōu)值，即 ),()(,)(nkknksdxkkpsvsfoptkkk2 2基本概念、基

49、本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理53 對于可加性指標(biāo)函數(shù)，上式可以寫為 上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。 終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1) = 0。nksfxsvsfkkkkksdxkkoptkkk, 2 , 1)(),()(11)(nksfxsvsfkkkkksdxkkoptkkk, 2 , 1)(),()(11)(2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化

50、原理54 三、最優(yōu)化原理三、最優(yōu)化原理 作為整個過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個狀態(tài)以前的狀 態(tài)和決策如何，對該狀態(tài)來說，以后的所有決 策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的 任意子策略都是最優(yōu)的。2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理55一、資源分配問題一、資源分配問題 例2. 某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表10-5所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？ 表10-5 盈利 工廠設(shè)備臺數(shù) 甲 廠 乙 廠 丙 廠 0 0 0 0 1 3 5 4 2

51、7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)56 解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè) sk= 分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。 xk=分配給第k個設(shè)備臺數(shù)。 已知s1=5, 并有 從與的定義，可知 以下我們從第三階段開始計算。222223),(xsxstskskx33xs 3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)111112),(xsxsts57 第三階段: 顯然將臺設(shè)備都分配給第3工廠時， 也就是時，第3階段的指標(biāo)值（即第3廠的盈利） 為最大，即

52、 由于第3階段是最后的階段，故有 其中可取值為0,1,2,3,4,5。其數(shù)值計算見表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ssrxsrsfx3x),(),(max3333333ssrxsrx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)33xs 58 表表10106 6 012345000014 4126623111134121243x3s),(333xsr)(33sf3*x3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)59 其中表示取3子過程上最優(yōu)指標(biāo)值時的 決策，例如在表10-6中可知當(dāng)=4時，有有 此時，即當(dāng)時，此時

53、取 （把4臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值 （盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。 第二階段： 當(dāng)把臺設(shè)備分配給第2工廠和第3工 廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利 即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為 3*x)(33sf3x3s;12)4 , 4(3r,12)4(3f43*x43s43x)5 , 4 , 3 , 2 , 1 , 0(22ss2s)(),(max)(33222222sfxsrsfx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)60 因為上式也可寫成 其數(shù)值計算如表107所示。 表107 , 223xss0123450 00104 51206 5

54、4 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)61 其中在的這一行里，當(dāng)時， 這里從表105中可知，把1臺設(shè)備交給乙廠所得盈 利數(shù)即可，知，這里從表106查 即可知=11。同樣可知當(dāng)時，可知 ; 當(dāng)時，；當(dāng)時， ；當(dāng)時， ；由于，不可能分2廠5 臺設(shè)備，故時，欄空著不填。從 這些數(shù)值中取得最大即得，即有=16。在此行中 我

55、們在取最大值的 上面加一橫以示 區(qū)別，也可知這時的最優(yōu)決策為1或2。42s12x16115) 3() 1 , 4() 14() 1 , 4()(),(3232223222frfrxsfxsr) 1 , 4(2r5) 1 , 4(2r)3()14(33ff)3(3f) 3(3f22x16610)2()2 , 4()24()2 , 4()(),(3232223222frfrxsfxsr02x12120)04()0 , 4(32 fr32x411)34()3 , 4(32 fr42x11011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(2f)(),(2

56、23222xsfxsr2x3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)62 第一階段： 把臺設(shè)備分配給第1，第2，第3廠時，最大 盈利為其中可取值0,1,2,3,4,5. 數(shù)值計算見表108 表10-8 然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個： 1.由于，根據(jù)，查表107可 知，再由 ，求得。即分配 給甲廠0臺，乙廠2臺，丙廠3臺。 2.由于，根據(jù) ，查表107可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)(1xf1*x01*x50

57、51*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)63 知，再由 ,求得， 即分配給甲廠2臺，乙廠2臺，丙廠1臺。 這兩種分配方案都能得到最高的總盈利21萬元。 22*x1232*23xss133* sx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)64 二、背包問題二、背包問題 設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件 重量為wi公斤，每件價值ci元?，F(xiàn)有一只可裝載重量為w 公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背 包中物品的價值最高。 這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種 物品

58、裝入背包的件數(shù)（i =1, 2, , n），背包中物品的總 價值為z，則 max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnw x1, x2, , xn0 且為整數(shù)。3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)65 下面用動態(tài)規(guī)劃逆序解法求解它。設(shè) 階段變量k：第k次裝載第k種物品（k=1, 2, , n） 狀態(tài)變量sk：第k次裝載時背包還可以裝載的重量； 決策變量uk = xk：第k次裝載第k種物品的件數(shù)； 決策允許集合：dk(sk) = xk | 0 xksk/wk，xk為整數(shù)； 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk wkxk； 階段指標(biāo)： vk =

59、 ckxk； 最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使 用價值； 遞推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xdk(sk) 終端條件： fn+1(sn+1) = 0。3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)66 例3.某咨詢公司有10個工作日可以去處理四種類型的咨 詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個 客戶所需工作日數(shù)以及所獲得的利潤如表109所示。顯然該公 司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客 戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這1

60、0 個工作日中獲利最大？ 表109 咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤1234432213472811203 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)67 解：用動態(tài)規(guī)劃來求解此題。 我們把此問題分成四個階段，第一階段我們決策將 處理多少個第一種咨詢項目類型中的客戶，第二階段決 策將處理多少個第二種咨詢項目類型中的客戶，第三階 段、第四階段我們也將作出類似的決策。我們設(shè) 分配給第k種咨詢項目到第四種咨詢項目的所 有客戶的總工作日（第k階段的狀態(tài)變量）。 =在第k種咨詢項目中處理客戶的數(shù)量（第k階段 的決策變量）。 已知10 并有 kx1s,),(11111