整數(shù)規(guī)劃應(yīng)用案例分析

1、一、投資項(xiàng)目的選擇一、投資項(xiàng)目的選擇 利用線性規(guī)劃可以來(lái)完成資金預(yù)算決策，決定對(duì)利用線性規(guī)劃可以來(lái)完成資金預(yù)算決策，決定對(duì) 不同項(xiàng)目投資額各是多少。但實(shí)際中，一些資金預(yù)算決不同項(xiàng)目投資額各是多少。但實(shí)際中，一些資金預(yù)算決策不是決定投資多少，而是是否進(jìn)行一些固定金額的投策不是決定投資多少，而是是否進(jìn)行一些固定金額的投資。資。 管理層必須經(jīng)常面對(duì)的是：在預(yù)投入資金額度一定管理層必須經(jīng)常面對(duì)的是：在預(yù)投入資金額度一定的情況下，是否進(jìn)行一項(xiàng)或幾項(xiàng)固定投資。的情況下，是否進(jìn)行一項(xiàng)或幾項(xiàng)固定投資。 對(duì)每個(gè)是或否的決策：對(duì)每個(gè)是或否的決策： 1 1，是，是 引入決策變量引入決策變量x=x= 0 0，否，否第

2、四章第四章 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用例例1 1 投資問(wèn)題投資問(wèn)題 設(shè)某公司在設(shè)某公司在m m個(gè)時(shí)段里有個(gè)時(shí)段里有n n項(xiàng)投資計(jì)劃，由于資金限制不能項(xiàng)投資計(jì)劃，由于資金限制不能全部進(jìn)行。已知全部進(jìn)行。已知 1)1)第第i i個(gè)時(shí)段里該公司可動(dòng)用的資金個(gè)時(shí)段里該公司可動(dòng)用的資金是是b b i i， 2)2)第第j j項(xiàng)投資計(jì)劃所需要的資金是項(xiàng)投資計(jì)劃所需要的資金是a a ijij , , 3) 3)能夠得到的利潤(rùn)能夠得到的利潤(rùn)是是c c ijij。 問(wèn)該公司如何選擇投資計(jì)劃，使問(wèn)該公司如何選擇投資計(jì)劃，使m m個(gè)時(shí)段內(nèi)的總利潤(rùn)最大個(gè)時(shí)段內(nèi)的總利潤(rùn)最大。解：解：設(shè)設(shè)x x ijij表示在第表示在

3、第i i個(gè)時(shí)段內(nèi)對(duì)第個(gè)時(shí)段內(nèi)對(duì)第j j個(gè)投資計(jì)劃的決策變量。個(gè)投資計(jì)劃的決策變量。建立該投資問(wèn)題的數(shù)學(xué)模型為建立該投資問(wèn)題的數(shù)學(xué)模型為： 表示第表示第i i個(gè)時(shí)段內(nèi)選中第個(gè)時(shí)段內(nèi)選中第j j個(gè)投資計(jì)劃，個(gè)投資計(jì)劃，表示第表示第i i時(shí)段內(nèi)未選中第時(shí)段內(nèi)未選中第j j個(gè)投資計(jì)劃。個(gè)投資計(jì)劃。01ijx1 , 0, 2 , 1. .max11ijnijiijijmiijijnjxmibxatsxcz投資項(xiàng)目的選擇投資項(xiàng)目的選擇例例2. 2. 1,2,31,2,3必須有一項(xiàng)選中必須有一項(xiàng)選中3,43,4只能選中一項(xiàng)只能選中一項(xiàng)5 5被選中前提是被選中前提是1 1選中選中二、分布系統(tǒng)設(shè)計(jì)二、分布系統(tǒng)設(shè)

4、計(jì)- -選址問(wèn)題選址問(wèn)題 在如今的全球經(jīng)濟(jì)中，許多公司正在全世界各個(gè)地在如今的全球經(jīng)濟(jì)中，許多公司正在全世界各個(gè)地方建立新工廠，為的是獲得低勞動(dòng)力成本等好處。方建立新工廠，為的是獲得低勞動(dòng)力成本等好處。 在為新工廠選址之前，需要分析和比較地點(diǎn)。每個(gè)在為新工廠選址之前，需要分析和比較地點(diǎn)。每個(gè)可供選擇的地點(diǎn)都涉及一個(gè)是或否的決策?？晒┻x擇的地點(diǎn)都涉及一個(gè)是或否的決策。 對(duì)每個(gè)是或否的決策：對(duì)每個(gè)是或否的決策： 1 1，是，是 引入決策變量引入決策變量 x=x= 0 0，否，否 在許多案例中，目標(biāo)是地點(diǎn)的選擇以使新建設(shè)施的在許多案例中，目標(biāo)是地點(diǎn)的選擇以使新建設(shè)施的總的成本最小化，且這新設(shè)施能滿足

5、生產(chǎn)的需要?？偟某杀咀钚』?，且這新設(shè)施能滿足生產(chǎn)的需要。分布系統(tǒng)設(shè)計(jì)分布系統(tǒng)設(shè)計(jì)- -選址問(wèn)題選址問(wèn)題例例3 3某企業(yè)在某企業(yè)在 A A1 1 地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為 30 30 千千箱，為了擴(kuò)大生產(chǎn)，打算在箱，為了擴(kuò)大生產(chǎn)，打算在 A A2 2，A A3 3，A A4 4，A A5 5地中再選擇幾個(gè)地地中再選擇幾個(gè)地方建廠。已知在方建廠。已知在 A A2 2 ，A A3 3，A A4 4，A A5 5地建廠的固定成本分別為地建廠的固定成本分別為175175千千元、元、300300千元、千元、375375千元、千元、500500千元，另外，千元，另

6、外， A A1 1產(chǎn)量及產(chǎn)量及A A2 2，A A3 3，A A4 4，A A5 5建成廠的產(chǎn)量，各銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)建成廠的產(chǎn)量，各銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)( (每每千箱運(yùn)費(fèi)千箱運(yùn)費(fèi)) )如下表所示。如下表所示。 a) a) 問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小固定成本和總的運(yùn)輸費(fèi)用之和最小? ? 解解： a) a) 設(shè)設(shè) x xijij為從為從A Ai i 運(yùn)往運(yùn)往B Bj j 的運(yùn)輸量的運(yùn)輸量( (單位千箱單位千箱) )， y yk k = 1(= 1(當(dāng)當(dāng)A

7、Ak k 被選被選中時(shí)中時(shí)) )或或0 0（當(dāng)（當(dāng)A Ak k 沒(méi)被選中時(shí)沒(méi)被選中時(shí)),),k k =2,3,4,5 =2,3,4,5這可以表示為一個(gè)整數(shù)規(guī)這可以表示為一個(gè)整數(shù)規(guī)劃問(wèn)題：劃問(wèn)題：Min z = 175Min 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 x4

8、343+10+10 x x51 51 +4+4x x5252+2+2x x5353（其中前（其中前4 4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。）項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。）s.ts.t. . x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x2121+ + x x2222+ + x x2323 10 ( A 10 ( A2 2 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x3131+ + x x3232+ + x x33 33 20 ( A 20 ( A3 3 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x4141+ +

9、 x x4242+ + x x43 43 30 30 ( A ( A4 4 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x5151+ + x x5252+ + x x53 53 40 40 ( A ( A5 5 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) 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 x1

10、313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 銷地的限制銷地的限制) ) x xijij 0 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。 模型檢查！是否有問(wèn)題？模型檢查！是否有問(wèn)題？解：解： a) a) 設(shè)設(shè) x xijij為從為從A Ai i 運(yùn)往運(yùn)往B Bj j 的運(yùn)輸量的運(yùn)輸量( (單位千箱單位千箱) )， y yk k = 1(= 1(當(dāng)當(dāng)A Ak k

11、 被選中時(shí)被選中時(shí)) )或或0 0（當(dāng)（當(dāng)A Ak k 沒(méi)被選中時(shí)沒(méi)被選中時(shí)),),k k =2,3,4,5 =2,3,4,5這可以表示這可以表示為一個(gè)整數(shù)規(guī)劃問(wèn)題：為一個(gè)整數(shù)規(guī)劃問(wèn)題：Min z =175Min 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+1

12、0+10 x x51 51 +4+4x x5252+2+2x x5353（其中前（其中前4 4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。）項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。）s.t. s.t. x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x3131+ + x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x

13、4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) x x5151+ + x x5252+ + x x53 53 40 40y y5 5 ( A ( A5 5 廠的產(chǎn)量限制廠的產(chǎn)量限制) ) 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

14、 銷地的限制銷地的限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 銷地的限制銷地的限制) ) x xijij 0 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。 b) 如果由于政策要求必須在如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠? 練習(xí)練習(xí) 例例4.4.某鉆井隊(duì)要人以下某鉆井隊(duì)要人以下1010

15、個(gè)可供選擇的井位中確定個(gè)可供選擇的井位中確定5 5個(gè)個(gè)鉆井探油鉆井探油, ,使總的鉆探費(fèi)用為最小使總的鉆探費(fèi)用為最小, ,若若1010個(gè)井位的代號(hào)個(gè)井位的代號(hào)為為 , ,相應(yīng)的鉆探險(xiǎn)費(fèi)用為相應(yīng)的鉆探險(xiǎn)費(fèi)用為 , ,并且并且井位選擇上要滿足下列限制條件井位選擇上要滿足下列限制條件: :w 或選擇或選擇 和和 , ,或選擇或選擇w 選擇了選擇了 或或 就不能選就不能選 , ,或反過(guò)來(lái)也一或反過(guò)來(lái)也一w 樣樣w 在在 中最多只能選兩個(gè)中最多只能選兩個(gè). .w 試建成立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型試建成立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型101,ss 101,cc 1s7s8s3s4s5s8765,ssss解: 設(shè)決策

16、變量目標(biāo)函數(shù)為約束條件:1)從10個(gè)可供選擇的井位中確定5個(gè)探油,則2)或選擇 和 ,或選擇 可表示為否則井位選擇鉆探第, 0, 1jjsx101minjjjxcZ5101jjx1s7s8s1, 18781xxxx3)選擇了 或 就不能選 ,反過(guò)來(lái)也一樣,可表示為4)在 中最多只能選兩個(gè)可表示為 綜上所述,該問(wèn)題的整數(shù)規(guī)劃模型如下:3s4s5s1, 15453xxxx8765,ssss28765xxxx101minjjjxcZ1021, 11, 15. .876554875381101或取jjjxxxxxxxxxxxxxxts 例例5. 5. 某部隊(duì)為了完成某項(xiàng)特殊任務(wù)某部隊(duì)為了完成某項(xiàng)特殊任

17、務(wù), ,需要晝夜需要晝夜2424小時(shí)小時(shí)不間斷值班不間斷值班, ,但每天不同的階段所需要的人數(shù)不同但每天不同的階段所需要的人數(shù)不同, ,具具體情況如下體情況如下. .假設(shè)值班人員分別在各時(shí)間段開始時(shí)上假設(shè)值班人員分別在各時(shí)間段開始時(shí)上班班, ,并連續(xù)工作并連續(xù)工作8 8小時(shí)小時(shí). .該部隊(duì)要完成這項(xiàng)任務(wù)至少需該部隊(duì)要完成這項(xiàng)任務(wù)至少需要配備多少名值班人員要配備多少名值班人員? ? 班次班次 時(shí)間段時(shí)間段 需要人數(shù)需要人數(shù) 1 6:00-10:00 601 6:00-10:00 60 2 10:00-14:00 70 2 10:00-14:00 70 3 14:00-18:00 60 3 14:

18、00-18:00 60 4 18:00-22:00 50 4 18:00-22:00 50 5 22:00-2:00 20 5 22:00-2:00 20 6 2:00-6:00 30 6 2:00-6:00 30三、值班安排三、值班安排解:設(shè)分別表示第i個(gè)班次開始上班的人數(shù),每個(gè)人連續(xù)值班8小時(shí).根據(jù)題意所求問(wèn)題歸結(jié)為如下整數(shù)規(guī)劃的數(shù)學(xué)模型:).6,.,2 , 1(, 0,30,20,50,60,70,60. .min65544332211661ixxxxxxxxxxxxxtsxziii且為整數(shù)w MODEL:w Sets:w Num/1.6/:b,x;w Endsetsw Data:w b

19、=60,70,60,50,20,30;w Enddataw OBJmin=sum(num(i):x(i);w x(1)+x(6)=60;w x(1)+x(2)=70;w x(2)+x(3)=60;w x(3)+x(4)=50;w x(4)+x(5)=20;w x(5)+x(6)=30;for(num(i):GIN(x(i);x(i)=0;);END練習(xí) (兼職值班) 例例6.6.東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4 4名大學(xué)生名大學(xué)生( (代號(hào)代號(hào)1,2,3,4)1,2,3,4)和和2 2名研究生名研究生( (代號(hào)代號(hào)5,6)5,6)值班答疑值班答疑. .已知每人已知每人從周一至

20、周五每天最多可安排的值班時(shí)間及每人每小從周一至周五每天最多可安排的值班時(shí)間及每人每小時(shí)的值班報(bào)酬如下時(shí)的值班報(bào)酬如下: : 班次班次 報(bào)酬報(bào)酬 每天最多可安排的值班時(shí)間每天最多可安排的值班時(shí)間 (元元/時(shí)時(shí)) 周一周一 周二周二 周三周三 周四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 w 該實(shí)驗(yàn)室開放時(shí)間為上午該實(shí)驗(yàn)室開放時(shí)間為上午8:008:00至晚上至晚上10:00,10:00,開放時(shí)間開放時(shí)間內(nèi)須有且僅須一名學(xué)生值班

21、內(nèi)須有且僅須一名學(xué)生值班. .規(guī)定大學(xué)生每周值班不規(guī)定大學(xué)生每周值班不少于少于8 8小時(shí)小時(shí), ,研究生每周不少于研究生每周不少于7 7小時(shí)小時(shí), ,每名學(xué)生每周值每名學(xué)生每周值班不超過(guò)班不超過(guò)3 3次次, ,每次值班不少于每次值班不少于2 2小時(shí)小時(shí), ,每天安排的值班每天安排的值班學(xué)生不超過(guò)學(xué)生不超過(guò)3 3人人, ,且其中必須有一名研究生且其中必須有一名研究生. .試為該實(shí)試為該實(shí)驗(yàn)室安排一張人員值班表驗(yàn)室安排一張人員值班表, ,使總支付的報(bào)酬最少使總支付的報(bào)酬最少, , 班次班次 報(bào)酬報(bào)酬 每天最多可安排的值班時(shí)間每天最多可安排的值班時(shí)間 (元元/時(shí)時(shí)) 周一周一 周二周二 周三周三 周

22、四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 解解: 設(shè)設(shè) 為學(xué)生為學(xué)生 i在周在周j的值班時(shí)間的值班時(shí)間,分析約束條件分析約束條件: 否則的值班時(shí)間在周安排學(xué)生, 0, 1jiyij不超過(guò)可安排的時(shí)間)5,.,1; 6,.,1(2. .jiyaxytsijijijijijx小時(shí)大學(xué)生每周值班不少于8)4,.,1(851jijix小時(shí)研究生每周值班不少于7)6 , 5(751jijix小時(shí)實(shí)驗(yàn)室每天開放14)5,.,1(14

23、61iijjx次每名學(xué)生一周不超過(guò)3)6,.,1(351jijiy人每天值班不超過(guò)3)5,.,1(361iijjy每天有一名研究生值班)5,.,1( 165jyyjj)5,.,1; 6,.,1( 10, 0jiyxijij或最多可安排的值班時(shí)間在周表示學(xué)生其中或每天有一名研究生值班人每天值班不超過(guò)次每名學(xué)生一周不超過(guò)小時(shí)實(shí)驗(yàn)室每天開放小時(shí)研究生每周值班不少于小時(shí)大學(xué)生每周值班不少于不超過(guò)可安排的時(shí)間jiajiyxjyyjyiyjxixixjiyaxytsxczijijijjjiijjijiijjijjijijijijijijijij)5,.,1; 6,.,1( 10, 0)5,.,1( 13)

24、5,.,1(33)6,.,1(314)5,.,1(147)6 , 5(78)4,.,1(8)5,.,1; 6,.,1(2. .min6561516151516151四、固定成本問(wèn)題四、固定成本問(wèn)題 例例7 7高壓容器公司制造小、中、大三種尺寸的金屬高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4 4萬(wàn)元、萬(wàn)元、5 5萬(wàn)元、萬(wàn)元、6 6萬(wàn)元，

25、可使用的金屬板有萬(wàn)元，可使用的金屬板有500500噸，勞噸，勞動(dòng)力有動(dòng)力有300300人人/ /月，機(jī)器有月，機(jī)器有100100臺(tái)臺(tái)/ /月，此外不管每種月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是小號(hào)是l00l00萬(wàn)元，中號(hào)為萬(wàn)元，中號(hào)為 150 150 萬(wàn)元，大號(hào)為萬(wàn)元，大號(hào)為200200萬(wàn)元。萬(wàn)元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。 解：這是一個(gè)整數(shù)規(guī)劃的問(wèn)題。解：這是一個(gè)整數(shù)規(guī)劃的問(wèn)題。 設(shè)設(shè)x x1 1，x x2 2， x x3 3 分別為小號(hào)容器、中號(hào)容器和大

26、號(hào)容器的生分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè) y yi i = 1( = 1(當(dāng)生產(chǎn)第當(dāng)生產(chǎn)第 i i種容器種容器, , 即即 x xi i 0 0 時(shí)時(shí)) ) 或或0 0（當(dāng)不生產(chǎn)第當(dāng)不生產(chǎn)第 i i種容器即種容器即 x xi i = 0 = 0 時(shí)）。時(shí)）。 引入約束引入約束 x xi i M M y yi i ，i =1i =1，2 2，3 3，M M充分大，以保證充分大，以保證當(dāng)當(dāng) y yi i = 0 = 0 時(shí)，

27、時(shí)，x xi i = 0 = 0 。 可建立如下的數(shù)學(xué)模型：可建立如下的數(shù)學(xué)模型： Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3 s.t s.t. 2. 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 x xi i M M y yi i ，i

28、 =1i =1，2 2，3 3，M M充分大充分大 x xj j 0 0 y yj j 為為0-10-1變量變量，i i = 1,2,3= 1,2,3五、五、 有有 n n 項(xiàng)不同的任務(wù)，恰好項(xiàng)不同的任務(wù)，恰好 n n 個(gè)人可分別承擔(dān)這些任務(wù)，但由個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把 n n 項(xiàng)任務(wù)指派給項(xiàng)任務(wù)指派給 n n 個(gè)人，使個(gè)人，使得完成得完成 n n 項(xiàng)任務(wù)的總的效率最高，這就是項(xiàng)任務(wù)的總的效率最高，這就是指派問(wèn)

29、題。指派問(wèn)題。例例8. 48. 4個(gè)人完成個(gè)人完成4 4項(xiàng)工作任務(wù)，由于個(gè)人的技術(shù)專長(zhǎng)不同，他們完成項(xiàng)工作任務(wù)，由于個(gè)人的技術(shù)專長(zhǎng)不同，他們完成4 4項(xiàng)工作任務(wù)所獲得的收益如下表所示，且規(guī)定每人只能做一項(xiàng)工項(xiàng)工作任務(wù)所獲得的收益如下表所示，且規(guī)定每人只能做一項(xiàng)工作，一項(xiàng)工作任務(wù)只需一人操作，試求使收益最大的分派方案？作，一項(xiàng)工作任務(wù)只需一人操作，試求使收益最大的分派方案？解：引入解：引入0 01 1變量變量 x xijij，并令并令 x xijij = 1(= 1(當(dāng)指派第當(dāng)指派第 i i名隊(duì)員游第名隊(duì)員游第j j種姿勢(shì)種姿勢(shì)) )或或0 0（當(dāng)不指派第（當(dāng)不指派第 i i名隊(duì)員游第名隊(duì)員游第

30、j j種姿勢(shì)種姿勢(shì)) )這可以表示為一個(gè)這可以表示為一個(gè)0-10-1整數(shù)規(guī)劃問(wèn)題：整數(shù)規(guī)劃問(wèn)題：Min Min z=56z=56x x1111+74+74x x1212+61+61x x1313+63+63x x1414+63+63x x2121+69+69x x2222+65+65x x2323+71+71x x2424+57+57x x3131+77+77x x3232+ +6363x x3333+67+67x x3434+55+55x x41 41 +76+76x x4242+62+62x x4343+62+62x x4444s.t. s.t. x x1111+ + x x1212+ +

31、 x x1313+ + x x1414= 1 (A= 1 (A只能游一種姿勢(shì)只能游一種姿勢(shì)) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (B= 1 (B只能游一種姿勢(shì)只能游一種姿勢(shì)) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (C= 1 (C只能游一種姿勢(shì)只能游一種姿勢(shì)) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (D= 1 (D只能游一種姿勢(shì)只能游一種姿勢(shì)) ) x x1111+ + x x2121+ + x x3131+ + x x4141=

32、 1 ( = 1 ( 自由泳只能一人游自由泳只能一人游) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( = 1 ( 蛙泳只能一人游蛙泳只能一人游) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( = 1 ( 蝶泳只能一人游蝶泳只能一人游) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( = 1 ( 仰泳只能一人泳仰泳只能一人泳) ) x xijij 為為0-10-1變量變量，i,j i,j = 1,2,3,4= 1,2,3,4 Model:sets:

33、num_i/1.4/;num_j/1.4/;link(num_i,num_j):a,x;endsetsdata:a=56,74,61,63,63,69,65,71,57,77,63,67,55,76,62,62;enddataOBJmin=sum(link(i,j):a(i,j)*x(i,j);for(num_i(i):sum(num_j(j):x(i.j)=1;);for(num_j(j):sum(num_i(i):x(i,j)=1;);for(link(i,j):BIN(x(i,j); x(i,j)=0;);END備用備用 例例9.9.某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：某公司在

34、今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目項(xiàng)目A A：從第一年到第四年每年年初可以投資，并于次年末回收本：從第一年到第四年每年年初可以投資，并于次年末回收本利利115%115%， 但第一年如果投資則最低金額為但第一年如果投資則最低金額為4 4萬(wàn)元，第二、三、萬(wàn)元，第二、三、四年不限；四年不限；項(xiàng)目項(xiàng)目B B：第三年初可以投資，到第五年末能回收本利：第三年初可以投資，到第五年末能回收本利128128，但規(guī)定，但規(guī)定最低投資金額為最低投資金額為3 3萬(wàn)元，最高金額為萬(wàn)元，最高金額為5 5萬(wàn)元；萬(wàn)元； 項(xiàng)目項(xiàng)目 C C：第二年初可以投資，到第五年末能回收本利：第二年初可以投資，到第五年末能回收本利1

35、40%140%，但規(guī)，但規(guī)定其投資額或?yàn)槎ㄆ渫顿Y額或?yàn)? 2萬(wàn)元或?yàn)槿f(wàn)元或?yàn)? 4萬(wàn)元或?yàn)槿f(wàn)元或?yàn)? 6萬(wàn)元或?yàn)槿f(wàn)元或?yàn)? 8萬(wàn)元。萬(wàn)元。 項(xiàng)目項(xiàng)目 D D：五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息：五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6%6%，此項(xiàng)投資金額不限。此項(xiàng)投資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金1010萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大年投資額，使到第五年末擁有的資金本利總額為最大? ?解：解：1) 設(shè)xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分別表示第 i 年年初給項(xiàng)目A，B，C，D的投資額； 設(shè)yiA， yiB