第五章整數(shù)規(guī)劃習題5.1考慮下列數(shù)學模型minz二f(x)+f(x)1122且滿足約束條件或x1>10，或x2>10；下列各不等式至少有一個成立：2x+x>1512<x+x>1512x+2x>15V12lx1-xJ=0或5或10x>0，x>0其中[20+5x,如x>0<11

f(x)=I0,女口x=011=112+6x,如x>0

J22f(x)=|0,女口x二0222將此問題歸結(jié)為混合整數(shù)規(guī)劃的模型。解.minz二10y+5x+12y+6x1122(0)x<y?M；x<y?M1122x>10-y?M13x>10-(1-y)?M23x+x>15-yM124x+x>15-yM125x+2x>15-yM126y+y+y<2456x-x=0y-5y+5y-10y+11y127891011y+y+y+y+y=17891011x>0,x>0;y=0或1(i=1,.???,11)12i5.2試將下述非線性的0-1規(guī)劃問題轉(zhuǎn)換成線性的0-1規(guī)劃問題maxz=x2+xx-x31233

I—2x+3x+x<3J123|x=0或1,(j=1,2,3)j1，當x=x=1J23解：令y=〔°‘否則故有x2x3=y，又￥，x3分別與x1，x3等價，因此題中模型可轉(zhuǎn)換為maxz=x+y一x13一2x+3x+xW3123ywx2JyWx3x+x<y+123x,x,x‘y均為0-1變量1235.3某科學實驗衛(wèi)星擬從下列儀器裝置中選若干件裝上。有關(guān)數(shù)據(jù)資料見表5-1表5-1儀器裝置代號體積重量實驗中的價值A(chǔ)vwc1111Avwc2222Avwc3333Avwc4444Avwc5555Avwc61616161要求：（1）裝入衛(wèi)星的儀器裝置總體積不超過V,總質(zhì)量不超過W；（2）A與丸

中最多安裝一件；（3）A與A中至少安裝一件；（4）A同A或者都安上，或者都2456不安。總的目的是裝上取的儀器裝置使該科學衛(wèi)星發(fā)揮最大的實驗價值。試建立這個問題的數(shù)學模型。解：maxz=fcxjjj=1fvx<Vjjj=1藝wx<Wjjj=1<x+x<113x+x>124‘安裝A儀器,否則‘安裝A儀器,否則x=JI10〔j〔0

5.4某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油，使總的鉆探費用最小。若10個井位的代號為s,S,…飛,相應的鉆探費用為c,C,…,C,12101210并且井位選擇上要滿足下列限制條件：（1）或選擇S和S,或選擇鉆探S；178（2）選擇了S或s就不能選擇s，或反過來也一樣；345（3）在S,S,S,S,中最多只能選兩個；試建立這個問題的整數(shù)規(guī)劃模型。5678解：10minz=乙cxjjj=1蘭x蘭x=5jj=1x+x=118<x+x=178x+x+xx+x<135x+x<145+x<278,78,選擇鉆探第\井位，否則5.5用割平面法求解下列整數(shù)規(guī)劃問題a）maxza）maxz=7x+9x12-x+3x<612<7x+x<3512x,x,>0且為整數(shù)12b）minzb）minz=4x+5x123x+2x>712x+4x>5<123x+x>212x,x>0且為整數(shù)12（c）maxz=4x+6x+2xC）1234x-4x<512—x+6x<5<12—x+x+x<5123x,x,x,>0且為整數(shù)123d）maxzd）maxz=11x+4x12—x+2x<14125x+2x<16<122x—x<412x,x,>0且為整數(shù)12

717'+-X+X二:——222322-2171‘一3二—X——X22223224711X—X+s——-——22322412xx<0由此解：（a）不考慮整數(shù)約束，用單純形法求解相應線性給華問題得最終單純形表,見表5A-1xx<0由此表5A-1x1x2x3x4x7/2017/221/222x9/210-1/223/22c-z-jj100-28/11-15/11從表中第1行得即將此約束加上，并用對偶單純形法求解得表5A-2。表5A-2xxQxoxsx7/2017/221/220x9/210-1/223/2201s-1/2100[-7/22]-1/221c-z00-28/11-15/110JJx3010012x32/71001/7-1/7x11/730011/7-22/7c-z:J000-1-8由表5A-2的x行可寫出164X+(0+-)X+(-1+-)s二(4+-)174717又得到一個新的約束1-4X-s+s二一一747127再將此約束加上，并用對偶單純形法求解得表5A-3。表5A-3xxcxxsscx30213001202x32/71001/7-1/701x11/70011/7-22/703s-4/72000[-1/7]-6/71c-zJJ1000-1-80

x30100102x41000-111x10010-413x400016-7c-zjj10000-2-7因此本題最優(yōu)解為x=4，x=3，z=5512本題最優(yōu)解為x=2,x=1,z=1312本題最優(yōu)解為x=2,x=1,x=6,z=26123本題最優(yōu)解為x=2,x=3,z=34125.6分配甲、乙、丙、丁四個人去完成五項任務。每人完成各項任務時間如表5-2所。由于任務數(shù)多于人數(shù),故規(guī)定其中有一個人可兼完成兩項任務,其余三人每人完成一項。試確定總花費時間為最少的指派方案。表5-2壬務人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：加工假設(shè)的第五個人是戊,他完成各項工作時間去甲、乙、丙、丁中最小者,構(gòu)造表為5A-4表5A-4、\壬壬務人ABCDE25293142373938262033342728403224423623452427262032對表5A-4再用匈牙利法求解，得最優(yōu)分配方案為甲-B,乙-D和C,丙-E,丁-A,總計需要131小時。5.7某航空公司經(jīng)營A,B,C三個城市之間的航線，這些航線每天班機起飛與到達時間如表5-3所示。表5-3航班號起飛城市起飛時間到達城市到達時間101A9：00B12：00102A10：00B13：00103A15：00B18：00104A20：00C24：00

105A22：00C2：00106B4：00A7：00107B11：00A14：00108B15：00A18：00109C7：00A11：00110C15：00A19：00111B13：00C18：00112B18：00C23：00113C15：00B20：00114C7：00B12：00設(shè)飛機在機場停留的損失費用大致與停留時間的平方成正比，又每架飛機從降落到下班起飛至少需要2小時準備時間，試決定一個使停留費用損失為最小的飛行解：把從某城市起飛的飛機當作要完成的任務，到達的飛機看作分配去完成任務的人。只要飛機到達后兩個小時，即可分配去完成起飛的任務。這樣可以分別對城市A,B,C各列出一個指派問題。各指派問題效率矩陣的數(shù)字為飛機停留的損失的費用。設(shè)飛機在機場停留一小時損失為a元，則停留2小時損失為4a元，停留3小時損失為9a,依次類推。對A,B，C三個城市建立的指派問題得效率矩陣分別見表5A-6，表5A-7，表5A-8。表5A-5城市A起飛到達、、1011021031041051064a9a64a169a225a107361a400a625a36a64a108225a256a441a4a16a109484a529a16a81a121a110196a225a400a625a9a表5A-6城市B起飛到達、106107108111112101256a529a9a625a36a102225a484a4a576a25a103100a289a441a361a576a11364a225a361a289a484a114256a529a9a625a36a表5A-7城市C'''到達起飛10911011311410449a225a225a49a10525a169a169a25a111169a441a441a169a11264a256a256a64a

對上述指派問題用匈牙利法求解，即可得到一個使停留費用損失最小的方案。5-8需制造2000件的某種產(chǎn)品，這種產(chǎn)品可利用A，B，C設(shè)備的任意一種加工，已知每種設(shè)備的生產(chǎn)準備結(jié)束費用，生產(chǎn)該產(chǎn)品時的單件成本，以及每種設(shè)備的最大加工量如表5-4所示，試對此問題建立整數(shù)規(guī)劃模型并求解。表5-4設(shè)備準備結(jié)束費（元）生產(chǎn)成本（兀/件）最大加工數(shù)（件）A10010600B3002800C20051200設(shè)X為在第j臺設(shè)備上生產(chǎn)的產(chǎn)品數(shù)，j=A,B,C,則問題的數(shù)學模型可表為:minz=100y+300y12+200y+10minz=100y+300y123123x+x+x>20001230<x<600yi<0<x<800y0<x<1200yy=0或1最優(yōu)解為x最優(yōu)解為x=0，1X=800,X=1200,z=8100235-9運籌學中著名的旅行商販（貨郎擔）問題可以敘述如下：某旅行商販從某一城市出發(fā),到其它幾個城市去推銷商品,規(guī)定每個城市均須到達而且只到達一次,然后回到原出發(fā)城市。已知城市i和城市j之間的距離為d,問該商販應選擇一條什么樣的路線順序旅行,使總的旅程為最短。試對此問題建立整數(shù)規(guī)劃模型。_J1,旅行商販從i直接去j解：設(shè)ijI0'否則由此可寫出其整數(shù)規(guī)劃模型為nnmmz=乙乙dxijiji=1jx=1(丿=1,???,n)iji=1工x=1(i=1,???,n)ijj<u一u+nx<n一1ijiju為連續(xù)變量(i=1,??，n),也可取整數(shù)值ii,j=1,...,n,i豐j

5.10有三個不同產(chǎn)品要在三臺機床上加工，每個產(chǎn)品必須首先在機床1上加工，然后依次在機床2，3上加工。在每臺機床上加工三個產(chǎn)品的順序應保持一樣，假定用t表示在第j機床上加工第i個產(chǎn)品的時間，問應如何安排，使三個產(chǎn)品總的加工周期為最短。試建立這個問題的數(shù)學模型。解：用X表示第i中產(chǎn)品在j機床上開始加工的時刻，則問題的數(shù)學模型可表示為：minz=max{x+1,x+1,x+1}131323233333'x+1<t(i=1,2,3;j=1,2)加工順序約束TOC\o"1-5"\h\zjji,j+1x+1—x<ijiji+1,ji<x+1一x<M(1—8)'互斥性約束i+1,ji+1,jijii=1,2;j=1,2,3;8=0或1一x>0某電子系統(tǒng)由三種元件組成，為使系統(tǒng)正常運轉(zhuǎn)，每個元件都必須工作良好。如一個或多個元件安裝幾個備用件將提高系統(tǒng)的可靠性。已知系統(tǒng)運轉(zhuǎn)可靠性為各元件可靠性的乘積，而每一元件的可靠性則是備用件數(shù)量的函數(shù)，具體數(shù)值見表5-5。表5-5備用件數(shù)元件可靠性12300.50.60.710.60.750.920.70.951.030.81.01.040.91.01.051.01.01.0又三種元件分別的價格和重量如表5-6所示。已知全部備用件的費用預算限制為150元，重量限制為20千克，問每個元件各安裝多少備用件（每個元件備用件不得超過5個），是系統(tǒng)可靠性為最大。試列出這個問題的整數(shù)規(guī)劃模型。表5-6元件每件價格（元）重量（千克/件）120223043406解：用x,x,x分別表示1,2,3三個元件安裝的備用件數(shù)量。根據(jù)題中條件及費用、重量的限制，元件1的備件最多安裝5個，元件2備件最多5個，元件3的備件最多安裝3個。故問題的數(shù)學模型可表示為：maxz二(0.5y+0.6y+0.7y+0.8y+0.9y+y)x123456(0.6y+0.75y+0.95y+y)x(0.7y+0.9y+y)7891011121320x+30x+40x<1501232x+4x+6x<20123工y=1ii=1<藝y=1ii=7遲y=1ii=11x>0(j=1,2,3)y=0或1(i=1,...,13)i用你認為合適的方法求解下述問題：maxz=x+2x+5xTOC\o"1-5"\h\z123I—x+10x—3xI>15123<2x+x+x<10123x,x,x>0123解：將問題改寫為maxz=x+2x+5xTOC\o"1-5"\h\z123x—10x+3x<—15+My123一x+10x一3x<—15+(1一y)Mv1232x+x+x<10123、x>0(j=1,2,3),y=0或1求解得x=0,x=0,x=10,y=1,z=50123下述線性規(guī)劃問題maxz=20x+10x+10x1232x+20x+4x<15123<6x+20x+4x=20123x,x,x>0,且取整數(shù)值123說明能否用先求解相應的線性規(guī)劃問題然后湊整的辦法來求得該整數(shù)規(guī)劃的一個可行解。解：當不考慮整數(shù)約束，求解相應線性規(guī)劃得最優(yōu)解為x=10/3,x=x=0。用湊整法時令x=3,x=x=0,其中第2個約束無法滿足，故不可行。123某市為方便學生上學，擬在新建的居民小區(qū)增設(shè)若干所小學。已知備選校址代號及其能覆蓋的居民小區(qū)編號如表5-7所示，問為覆蓋所有小區(qū)至少應建多少所小學，要求建模并求解。表5-7備選校址代號覆蓋的居民小區(qū)編號

A1,5,7B1,2,5C1,3,5D2,4,5E3,6F4,61,在第i備選校址建校解：令1°，否則minz=x+x+x+x+x+xABCDEF廠x+x+x>1x+x+x+x>1ABCABCDx+x>15BDx+x>1x+x>1CEEFx+x>1x>1DFA答案為在A,D,E三個備選校址建校。5.15已知下列五名運動員各種姿勢的游泳成績(各為50米)如表5-8所示，試問如何從中選拔一個參加200米混合泳的接力隊,使語氣比賽成績?yōu)樽詈谩１?-8單位：秒趙錢張王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：由下列運動員組成混合接力隊：張游仰泳,王游蛙泳,錢游蝶泳,趙游自由泳,預期總成績?yōu)?26.2秒。a)b)5-16用匈牙利法求解下述指派問題,已知效率矩陣分別如下：a)b)791°121312161715161415111215163821°87296427842391°6937551°解：(a)最優(yōu)指派方案為x=x=x=x=1,最優(yōu)值為48；13223441(b)最優(yōu)指派方案為x=x=x=x=x=1；最優(yōu)值為2115233244515-17從甲、乙、丙、丁、戊15五23人中32挑44選四51人去完成四項工作。已知每人完成各

項