第八章整數(shù)規(guī)劃

1、12 線性規(guī)劃的決策變量取值可以是任意非負實數(shù)，但許多實際線性規(guī)劃的決策變量取值可以是任意非負實數(shù)，但許多實際問題中，只有當決策變量的取值為整數(shù)時才有意義。問題中，只有當決策變量的取值為整數(shù)時才有意義。 例如，產(chǎn)品的件數(shù)、機器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，例如，產(chǎn)品的件數(shù)、機器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分數(shù)或小數(shù)解顯然是不合理的。分數(shù)或小數(shù)解顯然是不合理的。 要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱為整數(shù)線性規(guī)劃，簡稱整數(shù)規(guī)劃為整數(shù)線性規(guī)劃，簡稱整數(shù)規(guī)劃( (Integer Programming) )。 全部

2、決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃(All IP)； 僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(Mixed IP)； 要求決策變量只能取要求決策變量只能取0或或1值，則稱為值，則稱為0- -1規(guī)劃規(guī)劃(0- -1 rogramming)。 3為了滿足整數(shù)要求，似乎可以把線性規(guī)劃的小數(shù)最優(yōu)解進行為了滿足整數(shù)要求，似乎可以把線性規(guī)劃的小數(shù)最優(yōu)解進行“”以得到與最優(yōu)解相近的整數(shù)解。以得到與最優(yōu)解相近的整數(shù)解?！吧崛牖崛牖币话闶遣豢尚械模阂话闶遣豢尚械模?化整后的解有可能成為化整后的解

3、有可能成為； 雖是可行解，卻雖是可行解，卻。例如例如一、問題的提出一、問題的提出 產(chǎn)品產(chǎn)品資源資源甲甲乙乙現(xiàn)有量現(xiàn)有量A219B5735單臺利潤單臺利潤63 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。 4 解：解：設(shè)設(shè)x1為甲產(chǎn)品的臺數(shù)，為甲產(chǎn)品的臺數(shù)，x2為乙產(chǎn)品的臺數(shù)。為乙產(chǎn)品的臺數(shù)。maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2取整數(shù)取整數(shù) 不考慮整數(shù)約束則是一個不考慮整數(shù)約束則是一個LP問題問題,稱為原整數(shù)規(guī)劃的松弛問題。稱為原整數(shù)規(guī)劃的松弛問題。 不考慮整數(shù)約束的最優(yōu)解：不考

4、慮整數(shù)約束的最優(yōu)解：x1 *=28/9=3.111， x2 * =25/9=2.778，Z * =293/9=32.556 舍入化整舍入化整 x1 =3， x2 =3，Z =33，不滿足約束條件，不滿足約束條件5x1 +7 x2 35，非可行解；，非可行解； x1 =3， x2 =2，Z =28，滿足約束條件，是可行解，但不是最優(yōu)解；，滿足約束條件，是可行解，但不是最優(yōu)解； x1 =4， x2 =1，Z =29，滿足約束條件，才是最優(yōu)解。，滿足約束條件，才是最優(yōu)解。55x1 +7 x2 =352x1 + x2 =9x1x2123125344)972,913(6 步驟：步驟： 在線性規(guī)劃的可行域

5、內(nèi)列出所有決策變量可能取的整數(shù)值，在線性規(guī)劃的可行域內(nèi)列出所有決策變量可能取的整數(shù)值， 求出這些變量所有可行的整數(shù)解，求出這些變量所有可行的整數(shù)解， 比較它們相應(yīng)的目標函數(shù)值，最優(yōu)的目標函數(shù)值所對應(yīng)的比較它們相應(yīng)的目標函數(shù)值，最優(yōu)的目標函數(shù)值所對應(yīng)的解就是整數(shù)規(guī)劃的最優(yōu)解。解就是整數(shù)規(guī)劃的最優(yōu)解。 實用性：實用性： 只有兩個決策變量，只有兩個決策變量， 可行的整數(shù)解較少?？尚械恼麛?shù)解較少。 二、二、 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法 7例1. 某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。每件的體

6、積、重量、可獲利潤以及托運所受限制如表所示。貨物每件體積（立方英尺）每件重量（百千克）每件利潤（百元）甲乙19527344023托運限制1365140 甲種貨物至多托運甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大。件，問兩種貨物各托運多少件，可使獲得利潤最大。解：設(shè)設(shè)x1 、 x2分別為分別為甲、乙兩種貨物托運的件數(shù)，建立模型甲、乙兩種貨物托運的件數(shù)，建立模型 目標函數(shù)：目標函數(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ù)。如果去掉最

7、后一個約束，就是一個線性規(guī)劃問題。利用圖解法，如果去掉最后一個約束，就是一個線性規(guī)劃問題。利用圖解法，8得到線性規(guī)劃的最優(yōu)解為得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標函數(shù)值為目標函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標函數(shù)值為目標函數(shù)值為14。性質(zhì)1：任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值的純整數(shù)規(guī)劃或混合

8、整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標函數(shù)值。應(yīng)的線性規(guī)劃的最小目標函數(shù)值。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =69例2： Max z = 3Max z = 3x 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,

9、 ,x x2 2, ,x x3 3 0 0 為整數(shù)為整數(shù)例例3 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 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 為整數(shù)為整數(shù) x x3 3 為為0-10-1變量變量用管理運籌學軟件求解得： x1 = 5 x2 = 2 x3 = 2 用

10、管理運籌學軟件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.2510 例例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有擬議中有10個位置個位置 Aj (j1，2，3，10)可供選擇，考慮到各地區(qū)居可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定：民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由在東區(qū)由A1 ， A2 ，A3 三個點至多選擇兩個；三個點至多選擇兩個； 在西區(qū)由在西區(qū)由A4 ， A5 兩個點中至少選一個；兩個點中至少選一個； 在南區(qū)由在南區(qū)由A6 ， A7 兩個

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

12、我們可建立如下的數(shù)學模型：這樣我們可建立如下的數(shù)學模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 為為0-1變量變量，i = 1,2,3,1012Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+5

13、8x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 為為0-1變量變量，i = 1,2,3,10最優(yōu)解：最優(yōu)解： x1=1, x2=1, x3=0, x4=0, x5=1, x6=1, x7=0, x8=0, x9=1, x10=1 最大利潤最大利潤 245 萬元。萬元。即在即在 A1, A2, A5, A6, A9, A10 等等6個地點建立銷售門市部。個地點

14、建立銷售門市部。實際投資額為實際投資額為 100+120+70+90+160+180=72013例例5 5高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為不考慮固定費用，每種容器售出一只所得的利潤分別為 4 4萬元、萬元、5 5萬元、萬元、6 6萬元，可使用的金屬板有萬元，可使用的金屬板有500500噸，勞動力有噸，勞動力有300300人月，機器有人

15、月，機器有100100臺月，臺月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是是l00l00萬元，中號為萬元，中號為 150150萬元，大號為萬元，大號為200200萬元。萬元?，F(xiàn)在要制定一個生產(chǎn)計現(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。劃，使獲得的利潤為最大。二、固定成本問題二、固定成本問題14解：解：這是一個整數(shù)規(guī)劃的問題。這是一個整數(shù)規(guī)劃的問題。 設(shè)設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。 各種容器的固定費用只有在生產(chǎn)該種容器時才

16、投入，為了說明固定費各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，用的這種性質(zhì)，設(shè)設(shè) yi = 1(當生產(chǎn)第當生產(chǎn)第 i種容器種容器, 即即 xi 0 時時) 或或0（當不生產(chǎn)（當不生產(chǎn)第第 i種容器即種容器即 xi = 0 時）時） 引入約束引入約束 xi M yi ，i =1，2，3，M充分大，以保證當充分大，以保證當 yi = 0 時，時，xi = 0 。 這樣我們可建立如下的數(shù)學模型：這樣我們可建立如下的數(shù)學模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500

17、 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 xjN yj 為為0-1變量變量，i = 1,2,315例例6 6有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最所消耗的時間如表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少。少。三、指派問題三、指派問題: 有有 n n 項不同的任務(wù)，恰好項不同的任務(wù)，恰好 n n 個人可分別承擔這些任務(wù)個人可分別承擔這些任務(wù)，但由于

18、每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須，但由于每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個人去完成一項任務(wù)，怎樣把指派每個人去完成一項任務(wù)，怎樣把 n n 項任務(wù)指派給項任務(wù)指派給 n n 個人，使得完成個人，使得完成 n n 項任務(wù)的總的效率最高，這就是項任務(wù)的總的效率最高，這就是指派問題指派問題。16解：引入：引入01變量變量 xij，并令并令 xij = 1(當指派第當指派第 i人去完成第人去完成第j項工作時項工作時)或或0（當（當不指派第不指派第 i人去完成第人去完成第j項工作時項工作時)這可以表示為一個這可以表示為一個0-1整數(shù)規(guī)劃問題：整數(shù)規(guī)劃

19、問題：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( A工

20、作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij N 為為0-1變量變量，i,j = 1,2,3,4 * * * 求解可用求解可用管理運籌學管理運籌學軟件中整數(shù)規(guī)劃方法軟件中整數(shù)規(guī)劃方法。 17 對于有對于有m m 個人，個人，n 項任務(wù)的一般指派問題，設(shè)：項任務(wù)的一般指派問題，設(shè)：1,0ijijxij當?shù)?人去完成 項工作時；，當?shù)?人不去完成 項工作時.并設(shè)：

21、并設(shè)：cij 為第為第 i 人去完成第人去完成第 n項任務(wù)的成本（如時間、費用等）項任務(wù)的成本（如時間、費用等）則一般指派問題的模型可以寫為：則一般指派問題的模型可以寫為：11minmnijijijzcx約束條件：約束條件：111,1,2,1,1,2,nijjmijiximxjnxij為為0-1變量，對所有的變量，對所有的 i和和 j.18 因為因為m不一定等于不一定等于n，當，當mn，即人數(shù)多于任務(wù)數(shù)時，就，即人數(shù)多于任務(wù)數(shù)時，就有人沒有任務(wù)，所以前面?zhèn)€約束條件都是有人沒有任務(wù)，所以前面?zhèn)€約束條件都是“小于等于小于等于1”1”，這，這是說每個人至多承擔一項任務(wù)，而后面是說每個人至多承擔一項任

22、務(wù)，而后面n個約束條件說明每項個約束條件說明每項工作正好有一人承擔，所以都是工作正好有一人承擔，所以都是“等于等于1”.1”.當當nm時，需要設(shè)時，需要設(shè)假想的假想的n-m個人便獲得可行解個人便獲得可行解. .19還有一種指派問題叫做多重指派問題，它于一般的指派問題還有一種指派問題叫做多重指派問題，它于一般的指派問題的區(qū)別在于：一般的指派問題中每個人至多承擔一項任務(wù)，的區(qū)別在于：一般的指派問題中每個人至多承擔一項任務(wù)，而多重指派問題中一個人可以根據(jù)自己能力的大小承擔一項而多重指派問題中一個人可以根據(jù)自己能力的大小承擔一項、兩項或更多項的任務(wù)、兩項或更多項的任務(wù). .這時約束條件中的前個條件不是

23、這時約束條件中的前個條件不是11,1,2,nijjxim而是改為而是改為1,1,2,nijijxa im其中其中ai是第是第i個人至多承擔的任務(wù)的數(shù)，對于不同的個人至多承擔的任務(wù)的數(shù)，對于不同的i ， ai可以可以是不一樣的是不一樣的. .20四、分布系統(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千元、

24、千元、300千元、千元、375千元、千元、500千元，另外，千元，另外， A1產(chǎn)量及產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時銷建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價地的銷量以及產(chǎn)地到銷地的單位運價(每千箱運費每千箱運費)如下表所示。如下表所示。 （1） 問應(yīng)問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最小輸費用之和最小? （2） 如果由于政策要求必須在如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在地建一個廠，應(yīng)在哪幾個地方建廠哪幾個地方建廠? 21解： a) 設(shè)設(shè) xij

25、為從為從Ai 運往運往Bj 的運輸量的運輸量(單位千箱單位千箱)， yi = 1(當當Ai 被選中時被選中時)或或0（當（當Ai 沒被選中時沒被選中時) 這可以表示為一個整數(shù)規(guī)劃問題：這可以表示為一個整數(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)量限制廠的產(chǎn)量

26、限制) x21+ x22+ x23 10y2 ( A2 廠的產(chǎn)量限制廠的產(chǎn)量限制) x31+ x32+ x33 20y3 ( A3 廠的產(chǎn)量限制廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( A4 廠的產(chǎn)量限制廠的產(chǎn)量限制) x51+ x52+ x53 40y5 ( A5 廠的產(chǎn)量限制廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 銷地的限制銷地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制銷地的限制) xij

27、 0 xjN ，yi為為0-1變量變量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用求解可用管理運籌學管理運籌學軟件中整數(shù)規(guī)劃方法。軟件中整數(shù)規(guī)劃方法。 22b) 如果由于政策要求必須在如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠地建一個廠，應(yīng)在哪幾個地方建廠? 解： 設(shè)設(shè) xij為從為從Ai 運往運往Bj 的運輸量的運輸量(單位千箱單位千箱)， yi = 1(當當Ai 被選中時被選中時)或或0（當（當Ai 沒被選中時沒被選中時) 這可以表示為一個整數(shù)規(guī)劃問題：這可以表示為一個整數(shù)規(guī)劃問題：Min z = 175y2+300y3+375y4+500y5

28、+ 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)量限制廠的產(chǎn)量限制) x21+ x22+ x23 10y2 ( A2 廠的產(chǎn)量限制廠的產(chǎn)量限制) x31+ x32+ x33 20y3 ( A3 廠的產(chǎn)量限制廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( A4 廠的產(chǎn)量限制廠的產(chǎn)量限制) x51+ x52+ x53 40y5 (

29、 A5 廠的產(chǎn)量限制廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 銷地的限制銷地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制銷地的限制) y2+y3=1 (必須在必須在A2，A3地建一個廠地建一個廠) xij 0 yi為為0-1變量變量，i = 1,2,3,4,5；j = 1,2,323五、投資問題五、投資問題例例8某公司在今后五年內(nèi)考慮給以下的項目投資。已知：某公司在今后五年內(nèi)考慮給以下的項目投資。已知： 項目項目

30、A：從第一年到第四年每年年初需要投資，并于次年末回收本利從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為，但要求第一年投資最低金額為4萬元，第二、三、四年不限；萬元，第二、三、四年不限； 項目項目B：第三年初需要投資，到第五年未能回收本利第三年初需要投資，到第五年未能回收本利128，但規(guī)定最低，但規(guī)定最低投資金額為投資金額為3萬元，最高金額為萬元，最高金額為5萬元；萬元； 項目項目 C：第二年初需要投資，到第五年未能回收本利第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投，但規(guī)定其投資額或為資額或為2萬元或為萬元或為4萬元或為萬元或為6萬元或為

31、萬元或為8萬元。萬元。 項目項目 D：五年內(nèi)每年初可購買公債，于當年末歸還，并加利息五年內(nèi)每年初可購買公債，于當年末歸還，并加利息6%，此項，此項投資金額不限。投資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項目的每年投資額，萬元，問它應(yīng)如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大使到第五年末擁有的資金本利總額為最大? 24解：解：1) 設(shè)設(shè)xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分別表示第分別表示第 i 年年初給項目年年初給項目A，B，C，D的投資額；的投資額； 設(shè)設(shè)y1A， y3B，是，是01變量，并規(guī)定變量，并規(guī)定:

32、設(shè)設(shè)y2C 是非負整數(shù)變量，并規(guī)定：是非負整數(shù)變量，并規(guī)定：第第2年投資年投資C項目項目8萬元時，取值為萬元時，取值為4；第第2年投資年投資C項目項目6萬元時，取值為萬元時，取值為3；第第2年投資年投資C項目項目4萬元時，取值為萬元時，取值為2；第第2年投資年投資C項目項目2萬元時，取值為萬元時，取值為1；第第2年不投資年不投資C項目時，項目時， 取值為取值為0； 11,0,Ay當?shù)?年給A項目投資時， 當?shù)?年不給A項目投資時.31,0,By當?shù)?年給B項目投資時， 當?shù)?年不給B項目投資時.25這樣我們建立如下的決策變量：這樣我們建立如下的決策變量： 第第1年年 第第2年年 第第3年年 第

33、第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D 262）約束條件：）約束條件：第一年：年初有第一年：年初有100000元，元，D項目在年末可收回投資，故第一年項目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是年初應(yīng)把全部資金投出去，于是 x1A+ x1D = 100000；第二年：第二年：A次年末才可收回投資次年末才可收回投資,故第二年年初的資金為故第二年年初的資金為1.06x1D，于是于是x2A+x2C+x2D = 1.06x1D；第三年：年初的資金為第三年：年初的資金為 1.15x

34、1A+1.06x2D，于是，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D；第四年：年初的資金為第四年：年初的資金為 1.15x2A+1.06x3D，于是，于是 x4A + x4D = 1.15x2A+ 1.06x3D；第五年：年初的資金為第五年：年初的資金為 1.15x3A+1.06x4D，于是，于是 x5D = 1.15x3A+ 1.06x4D；27關(guān)于項目關(guān)于項目A的投資額規(guī)定的投資額規(guī)定: x1A 40000y1A ，x1A 200000y1A ，200000是足夠大的數(shù)；是足夠大的數(shù)； 保證當保證當 y1A = 0時，時， x1A = 0 ；當；當y1A = 1時

35、，時，x1A 40000 。 關(guān)于項目關(guān)于項目B的投資額規(guī)定的投資額規(guī)定: x3B 30000y3B ，x3B 50000y3B ； 保證當保證當 y3B = 0時，時， x3B = 0 ；當；當y3B = 1時，時，50000 x3B 30000 。 關(guān)于項目關(guān)于項目C的投資額規(guī)定的投資額規(guī)定: x2C = 20000y2C ，y2C = 0，1，2，3，4。283）目標函數(shù)及模型：）目標函數(shù)及模型： Max z = 1.15x4A+ 1.40 x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D； x3A+

36、x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D； x1A 40000y1A ， x1A 200000y1A ， x3B 30000y3B ， x3B 50000y3B ； x2C = 20000y2C ， y1A， y3B = 0 或或 1， y2C = 0，1，2，3，4 xiA ，xiB ，xiC ，xiD 0 ( i = 1、2、3、4、5）29 分枝定界法分枝定界法(Branch and Bound Method) 基本思想：基本思想： 先求出整數(shù)規(guī)劃相應(yīng)的先求出整數(shù)規(guī)劃相應(yīng)的

37、LP(即不考慮整數(shù)限制即不考慮整數(shù)限制)的最優(yōu)解，的最優(yōu)解， 若求得的最優(yōu)解符合整數(shù)要求，則是原若求得的最優(yōu)解符合整數(shù)要求，則是原IP的最優(yōu)解；的最優(yōu)解； 若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。 然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。規(guī)劃的最優(yōu)解。30 定界的含義：定界的含

38、義： 整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應(yīng)線性規(guī)劃的最約束條件，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應(yīng)線性規(guī)劃的最優(yōu)解。優(yōu)解。 對極大化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)最優(yōu)值是原對極大化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；整數(shù)規(guī)劃函數(shù)值的上界； 對極小化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)的最優(yōu)值是對極小化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標函數(shù)值的下界。原整數(shù)規(guī)劃目標函數(shù)值的下界。31例例 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7

39、x2 35 x1, x2 0 x1, x2取整數(shù)取整數(shù) 第一步第一步, ,不考慮變量的整數(shù)約束不考慮變量的整數(shù)約束, ,求相應(yīng)求相應(yīng)LP(LP(問題問題1)1)的最優(yōu)解：的最優(yōu)解： x1=28/9，x2 =25/9，Z1=293/9 第二步第二步, ,定界過程定界過程 這個解不滿足整數(shù)約束，這時目標函值這個解不滿足整數(shù)約束，這時目標函值Z Z1 1是整數(shù)規(guī)劃的目標上界；是整數(shù)規(guī)劃的目標上界； 因為因為x1=x2=0=0是整數(shù)規(guī)劃問題的可行解，所以下界為是整數(shù)規(guī)劃問題的可行解，所以下界為0 0。 第三步第三步, ,分枝過程分枝過程 將不將不滿足整數(shù)約束的變量滿足整數(shù)約束的變量x1進行分枝，進行分

40、枝，x1稱為分枝變量，構(gòu)造兩個新稱為分枝變量，構(gòu)造兩個新的約束條件：的約束條件： x1 28/9=3， x1 28/9 +1=4 32這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個部分，如圖所示。這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個部分，如圖所示。5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=3 x1=4問題問題2：maxZ= 6x1 +5 x2 問題問題3： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 4 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù)

41、x1, x2取整數(shù)取整數(shù)33 求解相應(yīng)的線性規(guī)劃的最優(yōu)解求解相應(yīng)的線性規(guī)劃的最優(yōu)解 問題問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2 =20/7，Z2=226/7 問題問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=4，x2 =1，Z3=29 第四步，定界過程第四步，定界過程 LP3的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是29，大于原有下界大于原有下界0，則新的下界為，則新的下界為29； 現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為226/7。 LP2的解仍不滿足

42、整數(shù)約束的要求，它的目標函數(shù)值的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值226/7大于大于現(xiàn)有下界，則應(yīng)繼續(xù)分枝。現(xiàn)有下界，則應(yīng)繼續(xù)分枝。 第五步，分枝過程第五步，分枝過程 將不將不滿足整數(shù)約束的變量滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件：進行分枝，構(gòu)造兩個新的約束條件： x2 20/7=2， x2 20/7 +1=3 345x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3問題問題4：maxZ= 6x1 +5 x2 問題問題5： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +

43、7 x2 35 x13 x1 3 x22 x2 3 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)x2 =2 x2=335 求解相應(yīng)的線性規(guī)劃的最優(yōu)解求解相應(yīng)的線性規(guī)劃的最優(yōu)解 問題問題4相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解： x1=3，x2 =2，Z4=28 問題問題5相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=14/5，x2 =3，Z5=159/5 第六步，定界過程第六步，定界過程 LP4的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是28，小于原有下界小于原有下界29，則下界仍為，則下

44、界仍為29； 現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為159/5。 LP5的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值159/5大于大于現(xiàn)有下界現(xiàn)有下界2929，則應(yīng)繼續(xù)分枝。，則應(yīng)繼續(xù)分枝。 第七步，分枝過程第七步，分枝過程 將不將不滿足整數(shù)約束的變量滿足整數(shù)約束的變量x1進行分枝，構(gòu)造兩個新的約束條件：進行分枝，構(gòu)造兩個新的約束條件： x1 14/5=2，x1 14/5 +1=3 36問題問題6：maxZ= 6x1 +5 x2 問題問題7： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1

45、+ x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x1 3 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)x2 =2 x2=35x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x1=237 求解相應(yīng)的線性規(guī)劃的最優(yōu)解：求解相應(yīng)的線性規(guī)劃的最優(yōu)解： 問題問題6相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解： x1=2，x2 =25/7，Z6=209/7 問題問題7相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：無最優(yōu)解無最優(yōu)解 第八步，定界過程第八步，定界

46、過程 LP7的無最優(yōu)解，不必再分枝，下界仍為的無最優(yōu)解，不必再分枝，下界仍為29； 現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為209/7。 LP6的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值209/7大于大于現(xiàn)有下界現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。，則應(yīng)繼續(xù)分枝。 第九步，分枝過程第九步，分枝過程 將不將不滿足整數(shù)約束的變量滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件：進行分枝，構(gòu)造兩個新的約束條件： x2 3， x2 4 38問題問題8：maxZ= 6x1 +5 x2 問題問題9： maxZ= 6x1

47、+5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x12 x23 x2 4 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x2=3x1=2x2 =2 x2 =439 求解相應(yīng)的線性規(guī)劃的最優(yōu)解求解相應(yīng)的線性規(guī)劃的最優(yōu)解 問題問題8相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解： x1=2，x2 =3，Z8=27 問題問題9相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最

48、優(yōu)解：x1=7/5，x2 =4，Z9=142/5 第十步，定界過程第十步，定界過程 LP8的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為29； 現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為29。 雖然雖然LP9的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值142/5小于現(xiàn)有下界小于現(xiàn)有下界29，則不再繼續(xù)分枝。，則不再繼續(xù)分枝。 上界上界=下界，得整數(shù)規(guī)劃問題的最優(yōu)解：下界，得整數(shù)規(guī)劃問題的最優(yōu)解：x1=4，x2 =1，Z=2940 分枝定界過程分枝定界過程7232,76

49、2, 3 221Zxx：問題9532,972,913 121Zxx：問題29, 1,4 321Zxx：問題28,2,3421Zxx：問題5431,3,542521Zxx：問題7629,743,2621Zxx：問題無可行解：問題727,3,2821Zxx：問題5228,4,521921Zxx：問題x13x1 4x22x2 3x12x1 3x23x2 409532下界：上界：297232下界：上界：295431下界：上界：297629下界：上界：2929下界：上界：41 z 從以上解題過程可得用分枝定界法求解目標函數(shù)值最大的整數(shù)規(guī)劃的從以上解題過程可得用分枝定界法求解目標函數(shù)值最大的整數(shù)規(guī)劃的步驟

50、，我們將求解的整數(shù)規(guī)劃問題稱為步驟，我們將求解的整數(shù)規(guī)劃問題稱為A，將與其相對應(yīng)的線性規(guī)劃問題，將與其相對應(yīng)的線性規(guī)劃問題稱為稱為B： 第一步：第一步：求解問題求解問題B，可得以下情況之一：，可得以下情況之一： 1.B沒有可行解，則沒有可行解，則A也沒有可行解，求解過程停止。也沒有可行解，求解過程停止。 2.B有最優(yōu)解，且符合問題有最優(yōu)解，且符合問題A的整數(shù)條件，則的整數(shù)條件，則B的最優(yōu)解即為的最優(yōu)解即為A的最優(yōu)的最優(yōu)解，求解過程停止。解，求解過程停止。 3.B有最優(yōu)解，但不符合有最優(yōu)解，但不符合A的整數(shù)條件，記其目標函數(shù)值為的整數(shù)條件，記其目標函數(shù)值為z1。 第二步：第二步：確定確定A的最優(yōu)

51、目標函數(shù)值的最優(yōu)目標函數(shù)值z*的上下界，其上界即為的上下界，其上界即為 =z1,再用再用觀察法找到觀察法找到A的一個整數(shù)可行解，求其目標函數(shù)值作為的一個整數(shù)可行解，求其目標函數(shù)值作為z*的下界，記為的下界，記為z 。 第三步：第三步：判斷判斷 是否等于是否等于z 。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標函數(shù)值等于函數(shù)值等于z的的A的那個整數(shù)可行解；否則進行第四步。的那個整數(shù)可行解；否則進行第四步。z42zz 第四步：第四步：在在B的最優(yōu)解中選一個最遠離整數(shù)要求的變量，不妨設(shè)此變量的最優(yōu)解中選一個最遠離整數(shù)要求的變量，不妨設(shè)此變量為為xj=bj，以，以bj表示小于

52、表示小于bj的最大整數(shù)，構(gòu)造以下兩個約束條件，并加入問的最大整數(shù)，構(gòu)造以下兩個約束條件，并加入問題題B，得到，得到B的兩個分枝的兩個分枝B1和和B2。xj bj和和xj bj+1 第五步：第五步：求解求解B1和和B2 。修改。修改A問題的最優(yōu)目標函數(shù)值問題的最優(yōu)目標函數(shù)值z*的上下界，的上下界， 和和z 。 第六步：第六步：比較和剪枝。各分枝的最優(yōu)目標函數(shù)值中若有小于比較和剪枝。各分枝的最優(yōu)目標函數(shù)值中若有小于z者，則剪者，則剪掉這枝（用打掉這枝（用打表示），即以后不再考慮了。若大于表示），即以后不再考慮了。若大于z ，則不符合整數(shù)條件，則不符合整數(shù)條件，則重復第三步至第六步，直至則重復第三步

53、至第六步，直至 ，求出最優(yōu)解為止。，求出最優(yōu)解為止。 對于求目標函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。對于求目標函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。z43例例9 用分枝定界法求解整數(shù)規(guī)劃用分枝定界法求解整數(shù)規(guī)劃Max 2Max 2x x1 1+3+3x x2 2s.t. 195s.t. 195x x1 1+273+273x x2 213651365 4 4x x1 1+ 40+ 40 x x2 2140140 x x1 1 4 4 x x1 1,x,x2 2 0 0且且x x1 1,x,x2 2為整數(shù)為整數(shù)解解: : ( (一一) )先求出以下線性規(guī)劃的解：先求出以下線性規(guī)劃的解： Max 2Max 2x x1 1+3+3x x2 2 s.t. 195 s.t. 195x x1 1+273+273x x2 213651365 4