整數(shù)規(guī)劃習(xí)題

1、第五章 整數(shù)規(guī)劃習(xí)題5。1 考慮下列數(shù)學(xué)模型 且滿足約束條件（1）或,或；(2）下列各不等式至少有一個(gè)成立： （3)或5或10(4），其中 = 將此問題歸結(jié)為混合整數(shù)規(guī)劃的模型.解: 5。2 試將下述非線性的0-1規(guī)劃問題轉(zhuǎn)換成線性的01規(guī)劃問題 解:令故有，又,分別與,等價(jià)，因此題中模型可轉(zhuǎn)換為 5。3 某科學(xué)實(shí)驗(yàn)衛(wèi)星擬從下列儀器裝置中選若干件裝上.有關(guān)數(shù)據(jù)資料見表5-1表 51儀器裝置代號體積重量實(shí)驗(yàn)中的價(jià)值A(chǔ)1A2A3A4A5A6v1v2v3v4v5v6w1w2w3w4w5w6c1c2c3c4c5c6要求：（1)裝入衛(wèi)星的儀器裝置總體積不超過V,總質(zhì)量不超過W；（2）A1與A3中最多安裝

2、一件；（3）A2與A4中至少安裝一件；(4)A5同A6或者都安上，或者都不安?？偟哪康氖茄b上取的儀器裝置使該科學(xué)衛(wèi)星發(fā)揮最大的實(shí)驗(yàn)價(jià)值.試建立這個(gè)問題的數(shù)學(xué)模型。解： 5。4 某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油,使總的鉆探費(fèi)用最小。若10個(gè)井位的代號為s1 ，s2,s10,相應(yīng)的鉆探費(fèi)用為c1 ，c2，,c10，并且井位選擇上要滿足下列限制條件： （1）或選擇s1和s7，或選擇鉆探s8；（2)選擇了s3或s4就不能選擇s5，或反過來也一樣；（3）在s5,s6,s7，s8，中最多只能選兩個(gè);試建立這個(gè)問題的整數(shù)規(guī)劃模型。解： 5。5 用割平面法求解下列整數(shù)規(guī)劃問題（a) （b

3、） (c) （d） 解：(a）不考慮整數(shù)約束,用單純形法求解相應(yīng)線性給華問題得最終單純形表,見表5A1。表5A-1x1x2x3x4x2 7/2x1 9/201107/221/221/223/22cjzj0028/1115/11從表中第1行得 由此 即 將此約束加上，并用對偶單純形法求解得表5A2。表5A-2x1x2x3x4s1x2 7/2x1 9/2s1 -1/20101007/221/227/221/223/221/22001cj-zj0028/11-15/110x2 3 x1 32/7x3 11/701010000101/71/711/7-22/7cjzj000-18由表5A-2的x行可寫

4、出 又得到一個(gè)新的約束 再將此約束加上,并用對偶單純形法求解得表5A-3.表5A-3x1x2x3x4s1s2x2 3 x1 32/7 x3 11/7 s2 -4/701001000001001/71/71/711/7-22/7-6/70001cjzj000-180x2 3x1 4x3 1x4 401001000001000011-1-460117cjzj00002-7因此本題最優(yōu)解為 x1=4，x2=3，z=55（b）本題最優(yōu)解為x1=2，x2=1，z=13(c）本題最優(yōu)解為x1=2，x2=1，x3=6，z=26（d)本題最優(yōu)解為x1=2，x2=3，z=345。6 分配甲、乙、丙、丁四個(gè)人去完

5、成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如表5-2所。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案.表5-2任務(wù)人ABCDE甲乙丙丁2539342429382742312628364220402337333245解：加工假設(shè)的第五個(gè)人是戊,他完成各項(xiàng)工作時(shí)間去甲、乙、丙、丁中最小者，構(gòu)造表為5A4表5A-4任務(wù)人ABCDE甲乙丙丁戊25393424242938274227312628362642204023203733324532對表5A4再用匈牙利法求解，得最優(yōu)分配方案為甲-B，乙D和C，丙E，丁-A，總計(jì)需要131小時(shí)。5.7 某航

6、空公司經(jīng)營A，B,C三個(gè)城市之間的航線，這些航線每天班機(jī)起飛與到達(dá)時(shí)間如表53所示.表5-3航班號起飛城市起飛時(shí)間到達(dá)城市到達(dá)時(shí)間101102103104105106107108109110111112113114AAAAABBBCCBBCC9：0010：0015：0020：0022：004：0011：0015：007：0015：0013：0018：0015：007:00BBBCCAAAAACCBB12：0013：0018:0024:002：007:0014：0018：0011：0019：0018：0023：0020:0012：00設(shè)飛機(jī)在機(jī)場停留的損失費(fèi)用大致與停留時(shí)間的平方成正比，又每架飛

7、機(jī)從降落到下班起飛至少需要2小時(shí)準(zhǔn)備時(shí)間,試決定一個(gè)使停留費(fèi)用損失為最小的飛行方案.解：把從某城市起飛的飛機(jī)當(dāng)作要完成的任務(wù)，到達(dá)的飛機(jī)看作分配去完成任務(wù)的人。只要飛機(jī)到達(dá)后兩個(gè)小時(shí)，即可分配去完成起飛的任務(wù).這樣可以分別對城市A，B,C各列出一個(gè)指派問題。各指派問題效率矩陣的數(shù)字為飛機(jī)停留的損失的費(fèi)用。設(shè)飛機(jī)在機(jī)場停留一小時(shí)損失為a元，則停留2小時(shí)損失為4a元，停留3小時(shí)損失為9a，依次類推。對A，B，C三個(gè)城市建立的指派問題得效率矩陣分別見表5A6，表5A-7，表5A8。表5A5 城市A起飛到達(dá)1011021031041051061071081091104a361a225a484a196a

8、9a400a256a529a225a64a625a441a16a400a169a36a4a81a625a225a64a16a121a9a表5A-6 城市B起飛到達(dá)106107108111112101102103113114256a225a100a64a256a529a484a289a225a529a9a4a441a361a9a625a576a361a289a625a36a25a576a484a36a表5A-7城市C起飛到達(dá)10911011311410410511111249a25a169a64a225a169a441a256a225a169a441a256a49a25a169a64a對上述指派

9、問題用匈牙利法求解,即可得到一個(gè)使停留費(fèi)用損失最小的方案.58 需制造2000件的某種產(chǎn)品,這種產(chǎn)品可利用A，B，C設(shè)備的任意一種加工,已知每種設(shè)備的生產(chǎn)準(zhǔn)備結(jié)束費(fèi)用，生產(chǎn)該產(chǎn)品時(shí)的單件成本，以及每種設(shè)備的最大加工量如表54所示,試對此問題建立整數(shù)規(guī)劃模型并求解。表54設(shè) 備準(zhǔn)備結(jié)束費(fèi)（元）生產(chǎn)成本（元/件)最大加工數(shù)（件）ABC10030020010256008001200設(shè)x為在第j臺設(shè)備上生產(chǎn)的產(chǎn)品數(shù)，j=A,B，C,則問題的數(shù)學(xué)模型可表為: 最優(yōu)解為x1=0，x2=800，x3=1200,z=81005-9 運(yùn)籌學(xué)中著名的旅行商販（貨郎擔(dān)）問題可以敘述如下：某旅行商販從某一城市出發(fā)，到

10、其它幾個(gè)城市去推銷商品,規(guī)定每個(gè)城市均須到達(dá)而且只到達(dá)一次，然后回到原出發(fā)城市。已知城市i和城市j之間的距離為dij，問該商販應(yīng)選擇一條什么樣的路線順序旅行,使總的旅程為最短。試對此問題建立整數(shù)規(guī)劃模型.解：設(shè)由此可寫出其整數(shù)規(guī)劃模型為 5.10 有三個(gè)不同產(chǎn)品要在三臺機(jī)床上加工，每個(gè)產(chǎn)品必須首先在機(jī)床1上加工,然后依次在機(jī)床2,3上加工.在每臺機(jī)床上加工三個(gè)產(chǎn)品的順序應(yīng)保持一樣，假定用tij表示在第j機(jī)床上加工第i個(gè)產(chǎn)品的時(shí)間，問應(yīng)如何安排,使三個(gè)產(chǎn)品總的加工周期為最短。試建立這個(gè)問題的數(shù)學(xué)模型。解：用xij表示第i中產(chǎn)品在j機(jī)床上開始加工的時(shí)刻，則問題的數(shù)學(xué)模型可表示為： 5。11 某電子

11、系統(tǒng)由三種元件組成，為使系統(tǒng)正常運(yùn)轉(zhuǎn)，每個(gè)元件都必須工作良好。如一個(gè)或多個(gè)元件安裝幾個(gè)備用件將提高系統(tǒng)的可靠性。已知系統(tǒng)運(yùn)轉(zhuǎn)可靠性為各元件可靠性的乘積，而每一元件的可靠性則是備用件數(shù)量的函數(shù)，具體數(shù)值見表55。表 55備用件數(shù)元件可靠性1230123450.50.60.70.80。91。00.60.750.951.01.01.00。70.91。01。01.01。0又三種元件分別的價(jià)格和重量如表5-6所示。已知全部備用件的費(fèi)用預(yù)算限制為150元，重量限制為20千克,問每個(gè)元件各安裝多少備用件（每個(gè)元件備用件不得超過5個(gè))，是系統(tǒng)可靠性為最大.試列出這個(gè)問題的整數(shù)規(guī)劃模型。表 56元件每件價(jià)格(元

12、）重量（千克/件）123203040246解：用x，x,x分別表示1，2,3三個(gè)元件安裝的備用件數(shù)量。根據(jù)題中條件及費(fèi)用、重量的限制，元件1的備件最多安裝5個(gè),元件2備件最多5個(gè)，元件3的備件最多安裝3個(gè)。故問題的數(shù)學(xué)模型可表示為： 5。12 用你認(rèn)為合適的方法求解下述問題:解：將問題改寫為 求解得x1=0，x2=0，x3=10，y=1，z=505.13 下述線性規(guī)劃問題 說明能否用先求解相應(yīng)的線性規(guī)劃問題然后湊整的辦法來求得該整數(shù)規(guī)劃的一個(gè)可行解。解：當(dāng)不考慮整數(shù)約束，求解相應(yīng)線性規(guī)劃得最優(yōu)解為x1=10/3，x2=x3=0。用湊整法時(shí)令x1=3，x2=x3=0，其中第2個(gè)約束無法滿足，故不

13、可行.5。14 某市為方便學(xué)生上學(xué)，擬在新建的居民小區(qū)增設(shè)若干所小學(xué)。已知備選校址代號及其能覆蓋的居民小區(qū)編號如表5-7所示,問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)，要求建模并求解。表5-7備選校址代號覆蓋的居民小區(qū)編號ABCDEF1,5，71，2，51,3,52,4,53,64，6解：令 答案為在A,D，E三個(gè)備選校址建校。5。15 已知下列五名運(yùn)動員各種姿勢的游泳成績(各為50米）如表5-8所示，試問如何從中選拔一個(gè)參加200米混合泳的接力隊(duì),使語氣比賽成績?yōu)樽詈?。?8 單位：秒趙錢張王周仰泳蛙泳蝶泳自由泳37.743。433。329。232。933。128。526。433.842.238。

14、929.637.034。730.428。535。441。833.631。1解：由下列運(yùn)動員組成混合接力隊(duì):張游仰泳，王游蛙泳，錢游蝶泳，趙游自由泳，預(yù)期總成績?yōu)?26。2秒。516 用匈牙利法求解下述指派問題,已知效率矩陣分別如下：（a） （b) 解：（a)最優(yōu)指派方案為x13=x22=x34=x41=1， 最優(yōu)值為48； (b）最優(yōu)指派方案為x15=x23=x32=x44=x51=1;最優(yōu)值為21517 從甲、乙、丙、丁、戊五人中挑選四人去完成四項(xiàng)工作。已知每人完成各項(xiàng)工作的時(shí)間如表5-9所示.規(guī)定每項(xiàng)工作只能由一個(gè)人去單獨(dú)完成，每個(gè)人最多承擔(dān)一項(xiàng)任務(wù)。又假定對甲必須保證分配一項(xiàng)任務(wù)，丁因某種原因決定不同意承擔(dān)第4項(xiàng)任務(wù)。在滿足上述條件下，如何分配工作，使完成四項(xiàng)工作總的花費(fèi)時(shí)間為最少.表59人工作甲乙丙丁戊1234105152021051531514131527694158解：先增加一種假想工作5，再據(jù)題中給的條件列出表5A-9表5A8人工作甲乙丙丁戊12345105152021051503151413015270941580對表5A-9用匈牙利法求解得最優(yōu)分配方案為：甲2，乙-3，丙1,戊4，對丁不分配工作.5-18 設(shè)有m個(gè)