規(guī)劃計(jì)算題整理

1、.第二章 設(shè)施選址10.一家銀行準(zhǔn)備在某縣的農(nóng)村地區(qū)投放一批ATM自動(dòng)取款機(jī)，以方便農(nóng)村的用戶取款。該農(nóng)村地區(qū)的村落座落情況和相對(duì)距離如圖2.13所示。為了能確保任一村的人都可以在20分鐘之內(nèi)到達(dá)自動(dòng)取款機(jī)取款，銀行需要多少臺(tái)自動(dòng)取款機(jī)？它們的位置又在哪里?圖2.13 村落座落情況和相對(duì)距離要點(diǎn)： 1. 明確N，M，A(j)，B(i)含義；2. A(j)分析正確后，B(i)可參照A(j)直接寫出，無需再看網(wǎng)絡(luò)圖；3. 熟悉最少點(diǎn)覆蓋啟發(fā)式算法的步驟，考慮是否有容量約束。 解：【集合覆蓋模型】區(qū)域中需求點(diǎn)集合N=1,2,3,4,5,6,7；ATM取款機(jī)設(shè)施候選點(diǎn)集合M=1,2,3,4,5,6,7

2、；由網(wǎng)絡(luò)圖確定候選設(shè)施點(diǎn)j可覆蓋的需求點(diǎn)集合A(j)和可覆蓋需求點(diǎn)i的設(shè)施節(jié)點(diǎn)的集合B(i)，見表2.10.1。2.10.1 候選點(diǎn)服務(wù)范圍村落號(hào)A(j)B(i)11,2,31,2,321,2,4,51,2,4,531,3,41,3,442,3,4,6,72,3,4,6,752,5,62,5,664,5,64,5,674,74,7因?yàn)锳(4)=2,3,4,6,7，| A(4)|=5為最大，故首先j=4。因無容量約束，指派2,3,4,6,7歸村落4服務(wù)。此時(shí)N=1,5，M=1,2,3,5,6,7；則更新候選點(diǎn)服務(wù)范圍，見表2.10.2。2.10.2 更新后的候選點(diǎn)服務(wù)范圍村落號(hào)A(j)B(i)1

3、11,2,321,5314552,5,6657因?yàn)锳(2)=1,5=N，恰好滿足條件。則j=2。綜上所述，銀行需要2臺(tái)自動(dòng)取款機(jī)，分別至于村落號(hào)為2和4的位置，2號(hào)為1,5村落服務(wù)，4號(hào)為 2,3,4,6,7村落服務(wù)。11. 個(gè)臨時(shí)幫助服務(wù)中心計(jì)劃在一個(gè)大城市的郊外開設(shè)一個(gè)新的辦公室。在經(jīng)過一定的精簡(jiǎn)之后，該公司有5個(gè)大的合作伙伴。在一個(gè)以km為單位的笛卡爾坐標(biāo)系中，它們的坐標(biāo)分別為：(4，4)，(4，11)，(7 ，2)，(11，11)， (14，7)。它們的服務(wù)需求量的權(quán)重分別為：wl=3，w2=2，w3=2，w4=4，w5=1。對(duì)于該服務(wù)中心來說，主要的日常費(fèi)用是他們員工完成任務(wù)過程中的

4、運(yùn)輸費(fèi)用。因此，用城市距離進(jìn)行考慮，要求新的辦公室到各個(gè)合作伙伴之間運(yùn)輸?shù)倪\(yùn)輸費(fèi)用最小。1）請(qǐng)確定一個(gè)新辦公室的地址，用笛卡爾坐標(biāo)來表達(dá)相應(yīng)結(jié)果。2）如果由于該地區(qū)的人口稀少，城市還沒有達(dá)到一定的規(guī)模，可以用歐幾米德距離進(jìn)行計(jì)算，新辦公室又得在哪里投建?請(qǐng)比較兩次結(jié)果，分析它們之間的關(guān)系。 要點(diǎn)：1. 補(bǔ)充交叉中值模型知識(shí)點(diǎn) 關(guān)鍵句：將n點(diǎn)需求的選址問題轉(zhuǎn)化為i=1nwi點(diǎn)需求的選址問題。 2.笛卡爾距離即直角距離，歐基米德距離即直線距離； 3.重心法：初始化+迭代公式+Excel/C編程/matlab編程迭代+迭代終止條件解：（1）設(shè)新辦公室的地址的坐標(biāo)為(x,y),給題目已知的5個(gè)點(diǎn)編號(hào)1

5、5。由于笛卡爾距離di=|x-xi|+|y-yi|。則目標(biāo)函數(shù)為時(shí)總運(yùn)輸距離H最短。H=i=15widi=i=15wix-xi +i=15wi|y-yi|xiwiwi yiwiwi 43343342511257272271141111411141127112wi=12為偶數(shù)，即x,y均在第六個(gè)、第七個(gè)點(diǎn)之間?？傻脁=7，y7,11。H=81。（2）設(shè)初始點(diǎn)為（x0， y0）有題意得，阿基米德距離為di(0)=(x0-xi)2+(y0-yi)2, 目標(biāo)函數(shù)H(運(yùn)輸總費(fèi)用)=i=15widi,利用不動(dòng)點(diǎn)算法，取一個(gè)初始的迭代點(diǎn)（x0(0),y0(0)）=(8,7),此時(shí)H0=62.51令x0(1)

6、=i=15wixidii=15xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2H1=i=15widi(1)=62.14由EXCEL迭代得，結(jié)果如圖費(fèi)用結(jié)果保留四位小數(shù)得最優(yōu)解為x=7.6257,y=7.6047,此時(shí)費(fèi)用最小為H=62.1020（3）比較兩次結(jié)果可知?dú)W基米德中的費(fèi)用小于笛卡爾距離，因直線距離是直角距離，因此用歐基米德距離更為精確。直角距離比較適合于城區(qū)范圍內(nèi)的選址，歐基米德距離比較適合于遠(yuǎn)距離的選址。12.一臺(tái)機(jī)器工具小制造商要遷址，并確定了兩個(gè)地區(qū)以供選擇。A地的年固定成本為800000元，可變成本為14

7、000元/臺(tái)；B地的年固定成本為920000元，可變成本為13000元/臺(tái)。產(chǎn)品最后售價(jià)為17000元/臺(tái)。（1） 當(dāng)產(chǎn)量為多少時(shí)，兩地的總成本相等？（2） 當(dāng)產(chǎn)量處于什么范圍時(shí)，A地優(yōu)于B地？當(dāng)產(chǎn)量處于什么范圍時(shí)，B地優(yōu)于A地？解：答：設(shè)x為之制造商的年產(chǎn)量 A地，總成本C(A)=800000+14000x B地，總成本C(B)=920000+13000x1)若兩地成本相等，則C(A)=C(B)解得：x=120 2）若A地優(yōu)于B地，則C(A)C(B),因此得0x120時(shí)，B地優(yōu)于A地。13利用表2.8所示的因素評(píng)分，以最大綜合得分為基礎(chǔ)，建模分析應(yīng)選擇地點(diǎn)A、B、C中的哪一個(gè)? 表2.8 因

8、素評(píng)分表解：權(quán)重矩陣設(shè)為W，則WT=0,15 0.20 0.18 0.27 0.10 0.10三個(gè)位置的因素評(píng)分作為3行構(gòu)成因素矩陣S。S=80 72 88 94 98 9670 76 90 86 90 8560 92 90 80 82 75可得綜合加權(quán)矩陣E=S*W=87.0282.6280.90?？芍狤(A) E(B) E(C)。即選擇A點(diǎn)。14.一個(gè)玩具制造商在全國的五個(gè)地區(qū)生產(chǎn)玩具，原材料將從一個(gè)新的中心倉庫運(yùn)出，而此倉庫的地點(diǎn)還有待確定。運(yùn)至各地的原材料數(shù)量相同，已建立一個(gè)坐標(biāo)城，各地的坐標(biāo)位置如表2.9所示。請(qǐng)確定中心倉庫的坐標(biāo)位置。表2.9 各地的坐標(biāo)位置解：設(shè)倉庫的坐標(biāo)為（x0

9、，y0)，五個(gè)生產(chǎn)地為(xi,yi),倉庫到各生產(chǎn)地的距離為di,因運(yùn)至各地的原材料數(shù)量相同，故可設(shè)wi=1(i=1,2,5）;初始解：，即x0(0)=5，y0(0)=4。直線距離為di(0)=(x0-xi)2+(y0-yi)2目標(biāo)函數(shù)運(yùn)輸總費(fèi)用H=i=15widi ，其中 wi=1(i=1,2,5）H(0)=j=15dj=13.6094根據(jù)下列進(jìn)行迭代：x0(1)=i=15xidii=151di， y0(1)=i=15yidii=151di，di(1)=(x0(1)-xi)2+(y0(1)-yi)2直到運(yùn)費(fèi)無法減小。用MATLAB 進(jìn)行編碼：運(yùn)行結(jié)果得，迭代78次得到最優(yōu)解。其中選址坐標(biāo)為（

10、5.6235,4.9918），最小運(yùn)費(fèi)為H=13.4550?；蛴蒃XCEL迭代得，結(jié)果如圖費(fèi)用結(jié)果保留三位小數(shù)得最優(yōu)解為X=5.5767，y=4.010,H=13.45615.某物流公司擬建一倉庫負(fù)責(zé)向四個(gè)工廠進(jìn)行物料供應(yīng)配送，各工廠的具體位置與年物料配送量見表2.10，設(shè)擬建物流公司倉庫對(duì)各工廠的單位運(yùn)輸成本相等。利用重心法計(jì)算確定物流公司的倉庫坐標(biāo)位置為多少。 表2.10 各工廠的具體位置與年物料配送量解：設(shè)倉庫的坐標(biāo)為（x0，y0)，4個(gè)工廠的坐標(biāo)為(xi,yi),倉庫到各生產(chǎn)地的距離為di=(x0-xi)2+(y0-yi)2,目標(biāo)函數(shù)運(yùn)輸總費(fèi)用H=i=15icidi=i=15widi，

11、i為工廠年配送量，ci為單位運(yùn)輸成本，因單位運(yùn)輸成本相等，故令ci=1，于是有w1 =2000,w2=1200,w3 =1000,w4=2500初始解x0=1nxi=37.5, y0=1nyi=42.5di(0)=(x0-xi)2+(y0-yi)2, 此時(shí)H0=192249.4令x0(1)=i=15wixidii=15xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2H1=i=15widi(1)=190400.4由EXCEL迭代得，結(jié)果如圖結(jié)果保留整數(shù)得最優(yōu)解為（42.22076，33.82437）,H=188709或用MA

12、TLAB進(jìn)行編碼（文件見附件）：運(yùn)行結(jié)果得，迭代59次得到最優(yōu)解。其中選址坐標(biāo)為（42.2865, 33.6732），最小運(yùn)費(fèi)為H= 188707.914。16. 籌建一農(nóng)副產(chǎn)品流通加工廠，可供選擇的候選廠址有D、E、F三處，因地址不同各廠加工成本亦有區(qū)別，各廠址每年費(fèi)用如表2.7所示。此外，為決定廠址還考慮了一些重要的非成本因素，如當(dāng)?shù)馗?jìng)爭(zhēng)能力、氣候變化和周圍環(huán)境是否適合農(nóng)副產(chǎn)品流通加工等。對(duì)于競(jìng)爭(zhēng)能力而言，F(xiàn)地最強(qiáng)，D、E兩地相平；就氣候來說，D比E好，F(xiàn)地最好；至于環(huán)境，E地最優(yōu)，其次為F地、D地。如果各主觀因素的重要性指數(shù)a、b、c依次為0.6、0.3和0.1，要求用因次分析法評(píng)定最佳

13、廠址在何處。表2.11 各候選廠址每年加工成本費(fèi)用要點(diǎn)：P中值法分5個(gè)步驟進(jìn)行。解: （1）計(jì)算客觀量度值OMi ，OMi=Ci1Ci-1 OMD=523*(1523+1525+1551)-1=0.3395同理可得：OME=0.3382,OMF=0.3223。（2）計(jì)算主觀評(píng)比值Sik（有3個(gè)不同的主觀因素） 競(jìng)爭(zhēng)能力（FD=E） 注：D=E，比較記為0.5兩兩相比廠址FED比重SiaD00.50.50.167E00.50.50.167F1120.666 氣候（FDE）兩兩相比廠址FED比重SiaD0110.33E000F1120.67 環(huán)境（EFD）兩兩相比廠址FED比重SiaD0000E1

14、120.67F0110.33（3）計(jì)算主觀量度值SMi， SMi=k=13IkSik，其中Ik為各主觀因素的重要性指數(shù)。因素kDEF重要性指數(shù)IkSia0.1670.1670.6660.6Sib0.3300.670.3Sic00.670.330.1計(jì)算可得SMD=0.167*0.6+0.33*0.3+0*0.1=0.1992SME=0.167*0.6+0*0.3+0.67*0.1=0.1672SMF=0.666*0.6+0.67*0.3+0.33*0.1=0.6336（4）計(jì)算位置量度值LMi，LMi=X*SMi+（1-X）*OMi由于題中沒有給出主觀因素與客觀因素的相互比重，假設(shè)兩者相等即同

15、種重要，即主客觀比重值X=0.5。LMD=0.5*0.3395+0.5*0.1992=0.26935LME=0.5*0.3382+0.5*0.1672=0.2527LMF=0.5*0.3223+0.5*0.6336=0.47795（5）決策根據(jù)各位置量度值LMi的大小，F(xiàn)廠址所得位置量度值在3個(gè)候選地址中最高，故選F為建廠廠址。17.在某區(qū)域需規(guī)劃建設(shè)若干個(gè)農(nóng)貿(mào)市場(chǎng)為將來該區(qū)9個(gè)主要居民點(diǎn)提供服務(wù)，除第6居民點(diǎn)外，其他各點(diǎn)均有建設(shè)市場(chǎng)的條件，如圖26所示。已知市場(chǎng)的最大服務(wù)直徑為3km，為保護(hù)該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場(chǎng)。問應(yīng)如何規(guī)劃？3圖26 小區(qū)居民點(diǎn)位置圖解：N1,2,3,4

16、,5,6,7,8,9，M1,2,3,4,5,7,8,9，由圖26兩點(diǎn)間的最短距離，根據(jù)最大服務(wù)半徑為3km的約束及第6居民點(diǎn)不適合建市場(chǎng)的要求，可確定集合A(j)和B(i)。如表23所示。表23 候選點(diǎn)服務(wù)范圍因?yàn)锳(4)=1,3,4,5,6,7，A(3)=1,2,3,4,5,6,|A(4)|= |A(3)|=6為最大,隨機(jī)選取j4。由于無容量約束故依次指派5,7,1,6,3,4點(diǎn)歸節(jié)點(diǎn)4服務(wù)。此時(shí)，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表24所示。表24 候選點(diǎn)服務(wù)范圍因?yàn)锳(8)8,9，|A(8)|A(9)|=2為最大，故選取j8或j9，并且8，9兩

17、點(diǎn)歸節(jié)點(diǎn)8或9服務(wù)。同理，再迭代一次，得j2，居民點(diǎn)2歸節(jié)點(diǎn)2服務(wù)。 因此，計(jì)算結(jié)果為（4,8,2）或（4,9,2）。若選擇j3，故依次指派1,2,3,4,5,6點(diǎn)歸節(jié)點(diǎn)3服務(wù)。此時(shí)，N7,8,9,M1,2,4,5,7,8,9,更新集合A(j)和集合B(i)后如表25所示。表25 候選點(diǎn)服務(wù)范圍由于|A(8)|3最大，選擇j8。因此計(jì)算結(jié)果為（3,8）。第三章 設(shè)施規(guī)劃11. 某生產(chǎn)線共有8項(xiàng)作業(yè)，其工作周期為8分鐘。已知各項(xiàng)作業(yè)的裝配順序和時(shí)間如表3.30所示。請(qǐng)根據(jù)周期時(shí)間和作業(yè)順序限制，確定最少工作站數(shù)和各項(xiàng)作業(yè)的安排，并算出此安排下生產(chǎn)線的效率。表3.30 周期時(shí)間和作業(yè)順序表解：由題

18、意得網(wǎng)絡(luò)活動(dòng)圖（Job on nodes）：ABCDEFGH由題意各作業(yè)所需時(shí)間之和=5+3+4+3+6+1+4+2=28最小工作數(shù)=28/8=3.5,因此需要4個(gè)工作臺(tái)根據(jù)作業(yè)的相關(guān)情況進(jìn)行安排，結(jié)果如下表工作站序號(hào)作業(yè)單元工作時(shí)間空閑時(shí)間1H,G,F 712E 6 23D，C 7 14B，A 8 0生產(chǎn)線效率=完成作業(yè)所需時(shí)間總和/(實(shí)際工作站總數(shù)*時(shí)間周期)=2848=0.875。12.某流水線有17項(xiàng)作業(yè)需要平衡，其中最長的作業(yè)為2.4分鐘，所有作業(yè)的總時(shí)間為18分鐘。該流水線每天工作450分鐘。試求：（1）最大和最小的周期時(shí)間各是多少？（2）該流水線理論上可能達(dá)到的每日產(chǎn)能是多少？（

19、3）按最大產(chǎn)能來算，最少需要幾個(gè)工作站？（4）若每天產(chǎn)能為125分鐘，則周期時(shí)間應(yīng)為多長？（5）若周期時(shí)間分別是9分鐘和15分鐘，則產(chǎn)能分別是多少？ 解：（1）當(dāng)17項(xiàng)作業(yè)只能串行依次進(jìn)行時(shí)，可得最大周期為18min。當(dāng)17項(xiàng)作業(yè)均并行進(jìn)行時(shí)，可得最小周期為2.4min。（2）產(chǎn)能為單位時(shí)間生產(chǎn)的產(chǎn)品數(shù)量。以最大周期計(jì)算，得最小產(chǎn)能為1/18min=0.056/min；以最小周期計(jì)算，得最大產(chǎn)能為1/2.4min=0.417/min；綜上所述，每日可能產(chǎn)能為25,187.5。（3）依題意有需要18/2.4=7.58，所以最少需要8個(gè)工作站。（4）周期時(shí)間為450/125=3.6min。（5）當(dāng)

20、周期時(shí)間為9min時(shí)，產(chǎn)能為450/9=50/天；當(dāng)周期時(shí)間為15min，產(chǎn)能為450/15=30/天。13. 某學(xué)院注冊(cè)有四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級(jí)卡和確認(rèn)交費(fèi)，分別安排在A、B、C、D四個(gè)連續(xù)相鄰的同樣大小的房間，因?yàn)橥瑫r(shí)有新老學(xué)生，如果450名新學(xué)生領(lǐng)表后去咨詢，550名老學(xué)生領(lǐng)表后直接去領(lǐng)班級(jí)卡，而畢業(yè)班學(xué)生已經(jīng)注冊(cè)過，領(lǐng)表后直接去繳費(fèi)，詳細(xì)學(xué)生流向如表3.31所示。試問已有布置是否可以改進(jìn)，若能，該如何改進(jìn)？表3.31 學(xué)生流向表要點(diǎn)：1.解題思路：?jiǎn)蜗蛭锪鲝闹帘?雙向物流從至表 作業(yè)對(duì)按雙向物流從至表中強(qiáng)度值排序，劃分物流等級(jí)確定物流路線比例 參考相關(guān)圖得接近程度排序表 按

21、接近程度得作業(yè)單位位置相關(guān)圖 按接近程度排序得作業(yè)單位面積相關(guān)圖 2.參考相關(guān)圖：物流強(qiáng)度等級(jí)A E I O U X物流路線比例10% 20% 30% 40% 0 0承擔(dān)的物流量比例40% 30% 20% 10% 0 0接近程度4 3 2 1 0 0 3.路線比例設(shè)計(jì)=線路條數(shù)/總線路條數(shù)解：由學(xué)生流向表得到雙向物流表如下：雙向物流表領(lǐng)表（A）咨詢(B)領(lǐng)班級(jí)卡(C)繳費(fèi)(D)領(lǐng)表（A）700（2）550（3）50（5）咨詢(B)200（4）領(lǐng)班級(jí)卡(C)750（1）繳費(fèi)(D)根據(jù)學(xué)生流量劃分物流等級(jí)確定物流路線比例如下：序號(hào)作業(yè)單位對(duì)強(qiáng)度值路線比例設(shè)計(jì)路線條數(shù)物流強(qiáng)度比例強(qiáng)度等級(jí)1C-D75

22、020%133.3%E2A-B70020%131.1%E3A-C55020%124.4%E4B-C20040%211.1%O5A-D50O合計(jì)2250由以上關(guān)系圖得接近程度排序表領(lǐng)表A咨詢B領(lǐng)班級(jí)卡C繳費(fèi)D領(lǐng)表A3/E3/E1/O咨詢B3/E1/O0/U領(lǐng)班級(jí)卡C3/E1/O3/E繳費(fèi)D1/O0/U3/E合計(jì)7474排序2413作業(yè)單位位置相關(guān)圖和作業(yè)單位面積相關(guān)圖領(lǐng) 表繳 費(fèi)領(lǐng)班級(jí)卡咨 詢領(lǐng)班級(jí)卡繳 費(fèi)領(lǐng) 表咨 詢現(xiàn)四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級(jí)卡和確認(rèn)交費(fèi)，分別安排在A、B、C、D四個(gè)連續(xù)相鄰的同樣大小的房間，即位置為下圖關(guān)系領(lǐng)班級(jí)卡繳 費(fèi)領(lǐng)表咨詢?cè)摬贾每傻玫礁倪M(jìn)，改進(jìn)方案為領(lǐng)班級(jí)卡繳 費(fèi)領(lǐng) 表咨 詢14. 根據(jù)作業(yè)相關(guān)圖，繪制作業(yè)單位位置相關(guān)圖。 圖3.28 習(xí)題14作業(yè)相關(guān)圖解：由該作業(yè)相關(guān)圖可得接近程度排序表如下：ABCDEA4/A2/I0/U0/UB4/A2/I3/E3/EC2/I2/I0/U0/UD0/U3/E0/U1/OE0/U3/E0/U1/O合計(jì)612444排序21534可得作業(yè)單位位置相關(guān)圖如下：BADEC15. 某工廠有ABCDE五個(gè)車間，布置圖如下，其