第8章整數(shù)規(guī)劃ppt課件

1、管管 理理 運運 籌籌 學學第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1整數(shù)規(guī)劃的圖解法 2整數(shù)規(guī)劃的計算機求解 3整數(shù)規(guī)劃的應用 4整數(shù)規(guī)劃的分枝定界法1管管 理理 運運 籌籌 學學第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。在整數(shù)規(guī)劃中，如果所有的變量都為非負整數(shù)，則稱為純整數(shù)規(guī)劃問題；如果有一部分變量為負整數(shù)，則稱之為混合整數(shù)規(guī)劃問題。在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱之為0-1變量。在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題中，如果所有的變量都為0-1變量，則稱之為0-1規(guī)劃。2管

2、管 理理 運運 籌籌 學學1 1整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法例例1. 1. 某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大。解：解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運的件數(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ù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題。利用圖解法，3貨物每件體積（立方英尺）每件重量（百千克）每件利潤（

3、百元）甲乙19527344023托運限制1365140管管 理理 運運 籌籌 學學1 1整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標函數(shù)值為14。性質(zhì)性質(zhì)1 1：任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值。412341232x1+3x2=14.66x22x1+3x2=142x1+3x2=61 1 整數(shù)規(guī)劃的圖

4、解法整數(shù)規(guī)劃的圖解法x10管管 理理 運運 籌籌 學學例例2 2： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 x1,x3為整數(shù)例3： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x3 1 x1,x2,x3 0 x1為整數(shù),x3為0-1變量5用管理運籌學軟件求解得： x1 = 5 x2 = 2 x3 = 2 用管理運籌學軟件求解得： x1 = 4 x2 = 1.25 x3 =

5、 1 z = 16.252 2整數(shù)規(guī)劃的計算機求解整數(shù)規(guī)劃的計算機求解管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用一、投資場所的選擇一、投資場所的選擇 例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置 aj (j1，2，3，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由a1 ， a2 ，a3 三個點至多選擇兩個； 在西區(qū)由a4 ， a5 兩個點中至少選一個； 在南區(qū)由a6 ， a7 兩個點中至少選一個； 在北區(qū)由a8 ， a9 ， a10 三個點中至少選兩個。 aj 各點的設(shè)備投資及每年可獲利潤由于地點不同都是

6、不一樣的，預測情況見表所示 (單位：萬元)。但投資總額不能超過720萬元，問應選擇哪幾個銷售點，可使年利潤為最大?6管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用解：解：設(shè)：0-1變量 xi = 1 (ai 點被選用）或 0 (ai 點沒被選用）。 這樣我們可建立如下的數(shù)學模型：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. 10010

7、0 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 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0,且xi 為0-1變量,i = 1,2,3,10把上述模型輸入管理運籌學軟件,即得到此問題的最優(yōu)解如下:最優(yōu)目標函數(shù)值為245.最優(yōu)解為: x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,

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

9、規(guī)劃的應用整數(shù)規(guī)劃的應用解：這是一個整數(shù)規(guī)劃的問題。 設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè) yi = 1(當生產(chǎn)第 i種容器, 即 xi 0 時) 或0（當不生產(chǎn)第 i種容器即 xi = 0 時）。 引入約束 xi m yi ，i =1，2，3，m充分大，以保證當 yi = 0 時，xi = 0 。 這樣我們可建立如下的數(shù)學模型：max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x

10、2 + 4x3 300 x1 + 2x2 + 3x3 100 xi m yi ，i =1，2，3，m充分大 xi 0 yi 為0-1變量，i = 1,2,39管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用三、指派問題三、指派問題 有 n 項不同的任務，恰好 n 個人可分別承擔這些任務，但由于每人特長不同，完成各項任務的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個人去完成一項任務，怎樣把 n 項任務指派給 n 個人，使得完成 n 項任務的總的效率最高，這就是指派問題。 例6有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應如何指派工作，才能總的消耗時

11、間為最少。10 工作工人abcd甲15182124乙19232218丙26171619丁19212317管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用解解：引入01變量 xij，并令 xij = 1(當指派第 i人去完成第j項工作時)或0（當不指派第 i人去完成第j項工作時)這可以表示為一個0-1整數(shù)規(guī)劃問題：min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33 +19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一

12、項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( a工作只能一人干) x12+ x22+ x32+ x42= 1 ( b工作只能一人干) x13+ x23+ x33+ x43= 1 ( c工作只能一人干) x14+ x24+ x34+ x44= 1 ( d工作只能一人干) xij 為0-1變量，i,j = 1,2,3,4 * * * 求解可用管理運籌學軟件中整數(shù)規(guī)劃方法。 11管管 理理 運

13、運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用四、分布系統(tǒng)設(shè)計四、分布系統(tǒng)設(shè)計例例7 7某企業(yè)在 a1 地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為 30 千箱，為了擴大生產(chǎn)，打算在 a2，a3，a4，a5地中再選擇幾個地方建廠。已知在a2 ， a3，a4，a5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外， a1產(chǎn)量及a2，a3，a4，a5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價(每千箱運費)如下表所示。 a) 問應該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最小? b) 如果由于政策要求必須在a2，a3地建一個廠，應在哪幾個地

14、方建廠? 12管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用解：解： a) 設(shè) xij為從ai 運往bj 的運輸量(單位：千箱)，yk = 1(當ai 被選中時)或0（當ai 沒被選中時),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+

15、 x22+ x23 10y2 ( 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,且為整數(shù)，i = 1,2,3,4,5；j = 1,2,3， yk 為0-1變量，k =2

16、,3,4,5。 * * * 求解可用管理運籌學軟件中整數(shù)規(guī)劃方法。 13管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用五、投資問題五、投資問題 例例8 8某公司在今后五年內(nèi)考慮給以下的項目投資。已知：項目a：從第一年到第四年每年年初需要投資，并于次年末回收本利 115%， 但要求第一年投資最低金額為4萬元，第二、三、四年不限；項目b：第三年初需要投資，到第五年末能回收本利1投資金額為3萬元，最高金額為5萬元； 項目 c：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或為2萬元或為4萬元，或為6萬元或為8萬元。 項目 d：五年內(nèi)每年初可購買公債，于當年末歸還，并加

17、利息6%，此項投資金額不限。 該部門現(xiàn)有資金10萬元，問它應如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大?14管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用解：解：1) 設(shè)xia、xib、xic、xid ( i 1，2，3，4，5)分別表示第 i 年年初給項目a，b，c，d的投資額； 設(shè)yia， yib，是01變量，并規(guī)定取 1 時分別表示第 i 年給a、b投資，否則取 0（ i = 1, 2, 3, 4, 5）。 設(shè)y2c 是非負整數(shù)變量，并規(guī)定：第2年投資c項目8萬元時，取值為4；第 2年投資c項目6萬元時，取值3；第2年投資c項目4萬元時，取值2；

18、第2年投資c項目2萬元時，取值1；第2年不投資c項目時，取值0； 這樣我們建立如下的決策變量： 第1年 第2年 第3年 第4年 第5年 a x1a x2a x3a x4a b x3b c x2c=20000y2c d x1d x2d x3d x4d x5d 15管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用2 2）約束條件：）約束條件：第一年：年初有100000元，d項目在年末可收回投資，故第一年年初應把全部資金投出去，于是 x1a+ x1d = 100000；第二年：a的投資第二年末才可收回，故第二年年初的資金為1.06x1d，于是x2a+x2c+x2d = 1.06x1d；

19、第三年：年初的資金為 1.15x1a+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。 關(guān)于項目a的投資額規(guī)定: x1a 40000y1a ，x1a 200000y1a ，200000是足夠大的數(shù)；保證當 y1a = 0時， x1a = 0 ；當y1a = 1時，x1a 40000 。 關(guān)于項目b的投資額規(guī)定: x3b 30000y3b

20、，x3b 50000y3b ； 保證當 y3b = 0時， x3b = 0 ；當y3b = 1時，50000 x3b 30000 。 關(guān)于項目c的投資額規(guī)定: x2c = 20000y2c ，y2c = 0，1，2，3，4。16管管 理理 運運 籌籌 學學3 3整數(shù)規(guī)劃的應用整數(shù)規(guī)劃的應用3 3）目標函數(shù)及模型：）目標函數(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 =

21、 1.15x2a+ 1.06x3d； x5d = 1.15x3a+ 1.06x4d； x1a 40000y1a ， x1a 200000y1a ， 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） 17管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法 18 分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決混合整數(shù)規(guī)劃的問題

22、。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法而編制成的。 分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。 下面以例9予以說明。管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法例9 用分枝定界法求解整數(shù)規(guī)劃 max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1,x2 0且x1,x2為整數(shù)解: (一)先求出以

23、下線性規(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)目標函數(shù)值z*初始上界 和下界z。 分析后，知道 =14.66，由觀察法得下界z=13（當x1=2,x2=3時）。z19z管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(三)將一個線性規(guī)劃問題分為兩枝，并求解。 可由x12或x13中取值。將線性規(guī)劃1分解為兩支，如下： 線性規(guī)劃2：max 2x1+3x2 s.t. 195x1+273x21365 4x1+

24、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.8620管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(四)修改整數(shù)規(guī)劃的最優(yōu)目標函數(shù)的上下界。 經(jīng)分析，將上界 =14.66修改為 =14.58，z=13。(五)在線性規(guī)劃2和線性規(guī)劃3中選擇一個上界最大的線性規(guī)劃，即線性規(guī)劃3，進行分枝。 線性規(guī)劃3分解為線性規(guī)劃4和線性規(guī)劃5，如

25、下： 線性規(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 4 x1 3 x2 3 x1,x2 0 無可行解zz21管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(六)進一步修改整數(shù)規(guī)劃最優(yōu)目標函數(shù)值z*的上下界。 從線性規(guī)劃2，4，5中修改z*的上下界。分析后，可得=14， z=14。都取線性規(guī)劃2，4，5中的整數(shù)可行解的目標函數(shù)值的最大值。性質(zhì)2： 當整數(shù)規(guī)劃的最優(yōu)目標函數(shù)值z*的上界 等于其下界z時，該整數(shù)規(guī)劃的最優(yōu)解已經(jīng)被求出。這個整數(shù)規(guī)劃的最優(yōu)解即為其目標函數(shù)值取此下界的對應線性規(guī)劃的整數(shù)可行解。zz22管管 理理 運運 籌籌 學學4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法用圖8-2表示例9的求解過程與求解結(jié)果zz2