運(yùn)籌學(xué)整數(shù)規(guī)劃

1、實(shí)驗(yàn)報(bào)告課程名稱：運(yùn)籌學(xué)項(xiàng)目名稱：整數(shù)規(guī)劃問題姓名： 專業(yè)：、 班級(jí)：1班 學(xué)號(hào)：同組成員： 二實(shí)驗(yàn)準(zhǔn)備注：1注：1、實(shí)驗(yàn)準(zhǔn)備部分包括實(shí)驗(yàn)環(huán)境準(zhǔn)備和實(shí)驗(yàn)所需知識(shí)點(diǎn)準(zhǔn)備。2、若是單人單組實(shí)驗(yàn)，同組成員填無。注：實(shí)驗(yàn)過程記錄要包含實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)原理、實(shí)驗(yàn)步驟，頁碼不夠可自行添加實(shí)驗(yàn)知識(shí)點(diǎn)：在前面我們所研究的線性規(guī)劃問題中，一般問題的最優(yōu)解都是非整數(shù)解，即 為分?jǐn)?shù)和小數(shù)。但是對(duì)于實(shí)際中的具體問題的解常常要求必須取整數(shù)，即稱為 整數(shù)解。為了求整數(shù)解，我們?cè)O(shè)想把所求的非整數(shù)解采用“舍入取整”的方法處 理，似乎是成了整數(shù)解，但事實(shí)上這樣得到的結(jié)果未必是可行的。因?yàn)槿≌缶筒灰欢ㄊ窃瓎栴}的可行解了，或者雖然

2、是可行解，但也不一定是最優(yōu)解。因此， 對(duì)于要求最優(yōu)解整數(shù)解的問題，需要尋求直接的求解方法，這就是整數(shù)規(guī)劃問題。如果一個(gè)數(shù)學(xué)規(guī)劃的某些決策變量或全部決策變量要求必須取整數(shù)，則這樣的問題稱為整數(shù)規(guī)劃問題，相應(yīng)的模型稱為整數(shù)規(guī)劃模型，在整數(shù)規(guī)劃中，如果 所有的決策變量都為非負(fù)整數(shù)，則稱之為純整數(shù)規(guī)劃問題；否則稱之為混合整數(shù) 規(guī)劃問題。如果整數(shù)規(guī)劃的目標(biāo)函數(shù)和約束都是線性的，則稱此問題為整數(shù)線性規(guī)劃問題。實(shí)驗(yàn)環(huán)境：LINGOS件二、實(shí)驗(yàn)過程記錄2:例4.5設(shè)某部隊(duì)為了完成某項(xiàng)特殊任務(wù)，需要晝夜 24小時(shí)不間斷值班，但每天不 時(shí)段所需要的人數(shù)不同，具體情況如表 4-4所示。假設(shè)值班人員分別在各時(shí)間段5

3、時(shí)上班，并連續(xù)工作8h。現(xiàn)在的問題是該部隊(duì)要完成這項(xiàng)任務(wù)至少需要配備多少名 班人員？表番班次的值晚時(shí)間段和人數(shù)4時(shí)間用需要大致a施次時(shí)間厚需要人數(shù)。1d： 00-W： 00邂4IS： M72； QQ5g210： 0014： Q07M522： 00也 00314： 0018； 106加62； ClClYf 003卜解：根據(jù)題意，假設(shè)用xi (i=1,2,3,4,5,6)分別表示第i個(gè)班次開始上班的人數(shù),每個(gè)人都要連續(xù)值班8h,于是根據(jù)問題的要求可歸結(jié)為如下的整數(shù)規(guī)劃模型： TOC o 1-5 h z _6目標(biāo)函數(shù)：min z x i 1x1 + x6 =60 x1 + x2 =70 x2 + x

4、3 =60約束條件：x3 + x4 =50 x4 + x5 =20 x5 + x6 =30 xi0,且為整數(shù)(i16)model :sets :num/1,2,3,4,5,6/:b,x;endsetsdata :b=60,70,60,50,20,30;enddataobj min =sum(num(i):x(i);x+x(6)=60;x(1)+x(2)=70;x(2)+x(3)=60;x(3)+x(4)=50;x(4)+x(5)=20;x(5)+x(6)=30;for (num(i): gin (x(i);x(i)=0);end運(yùn)行該程序得到的結(jié)果為：x1=60,x2=10,x3=50,x4=

5、0,x5=30,x6=0 。即值班安排如下：第 班開始上班的人數(shù)為 60人，第一班開始上班的人數(shù)為10 人，第二班開始上班的人數(shù)為50人，第五班開始上班的人數(shù)為 30人，第四和第 六班無需新上班的人，共計(jì)需要 150人。練習(xí)4.5某小姐服裝加工E以生產(chǎn) A,B,C二種不同服裝，生產(chǎn)不同種類的服裝需要租用不同的加工設(shè)備，設(shè)備的租金、生產(chǎn)成本、銷售價(jià)格等指標(biāo)如表所示。如果各類服裝都有足夠的市場(chǎng)需求，該廠每月可用人工工時(shí)為2000h版廠應(yīng)如何安排生產(chǎn)計(jì)劃可使每月有最大的利潤(rùn)？服裝種類一設(shè)備租金房生產(chǎn)成本/ （元源）E銷售價(jià)格人工I&J7W 件“設(shè)備工時(shí)/設(shè)備可用工 時(shí)W*婷5000-2號(hào)卜1。叩/%

6、,*3 口口2000 媼40*-1 300#c爐20加2003底將*30N解：目標(biāo)函數(shù):max z = (400- 280) * x1 + (40-30) * x2 + (300 - 200) * x3 - 5000 * y1- 2000* y2 - 2000 * y35*x1 +x2 + 4*x3 = 2000約束條件：3*x1= 300*y10.5* x2 = 300* y22*x3 = 300* y3model :sets :num/1,2,3/:x,y;endsetsobjmax =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)

7、-2000*y-2000*y(3);5*x(1)+x(2)+4*x(3)=2000;3*x(1)=300*y(1);0.5*x(2)=300*y(2);2*x(3)=0; bin (y(i););end運(yùn)行該程序得到的結(jié)果是：x1 = 100,x2=600,x3=150,最優(yōu)值z(mì)=24000。即生產(chǎn)第一種服裝A 100件，第二種服裝B 600件，第三種服裝C 150件, 每月的最大利潤(rùn)為24000元。練習(xí)4.9某公司現(xiàn)有資金10萬元，擬在今后五年內(nèi)考慮用于下列項(xiàng)目的投資：項(xiàng)目 A:從第一年到第四年每年年初需要投資，并于次年收回本利115% ,但要求第一年投資最低金額為4萬元，第二、三、四年不限

8、。項(xiàng)目 B:第三年初需要投資， 到第五年末能收回本利128% ,但規(guī)定最低投資額為3萬元，最高金額為5萬 元。項(xiàng)目C:第二年初需要投資，到第五年末能收回本利 140%，但規(guī)定其投資 額或?yàn)?萬元，或?yàn)?萬元，或?yàn)?萬元，或?yàn)?萬元。項(xiàng)目D:五年內(nèi)每年 初都可購買公債，于當(dāng)年末歸還，并獲利息 6%,此項(xiàng)投資金額不限。試問該公 司應(yīng)如何確定這些項(xiàng)目的每年投資金額，使得第五年末擁有最大的資金收益。解：由題意，設(shè)x為項(xiàng)目各年年初投入向量。xj為i種項(xiàng)目j年的年初的投入。(i=1,2,3,4 ; j=1,2,3,4,5 )。向量c中的元素a為i年末j種項(xiàng)目收回本例的百分比。矩陣A中元素ajj為約束條件中

9、每個(gè)變量xj的系數(shù)，Z為第5年末能擁有的資 金本利最大總額。目標(biāo)函數(shù)為：z=1.15*x4a+1.28*x3b+1.40*x2c+1.06*x5dx1a + x1d = 100000-1.06*x1dx2a+ x2c+x2d = 0-1.15* x1a-1.06* x2d + x3a + x3b + x3d = 0-1.15* x2a-1.06* x3d + x4a + x4d = 0約束條件為：-1.15* x3a-1.06* x4d = x5dmodel :max =1.15*x4a+1.28*x3b+1.40*x2c+1.06*x5d;x1a+x1d=100000;-1.06*x1dx2

10、a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0;-1.15*x2a-1.06*x3d+x4a+x4d=0;-1.15*x3a-1.06*x4d=x5d;x1a=40000;x2c=20000;x2c=40000;x2c=60000;x2c=80000;x3b=30000;x3b=0;x2a=0;x3a=0;x4a=0;x5a=0;x1b=0;x2b=0;x3b=0;x4b=0;x5b=0; x1c=0;x2c=0;x3c=0;x4c=0; x5c=0;x1d=0;x2d=0;x3d=0; x4d=0;x5d=0;有資金10萬元，第一年投入項(xiàng)目 A: 40000.00 ,投入項(xiàng)目D: 60000.00 或者22427.91 ;第二年投入項(xiàng)目 A: 22427.91 ,投入項(xiàng)目C: 20000.00 ,投入項(xiàng)目D: 3773.585 ;第三年投入項(xiàng)目B: 50000.00 ;其余年份幾對(duì)應(yīng)項(xiàng)目均沒有投資。得到 五年末擁有最大的資金為60000元三、實(shí)驗(yàn)小結(jié).規(guī)劃中的變量（全部或部分）限制為整數(shù)，稱為整數(shù)規(guī)劃。若在線性模型 中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。.為了滿足整數(shù)的要求，初看起來似乎只要