規(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 ?(?) ?(?含)義；2. ?(?分析正確后，？?(?可參照?(?直接寫出，無需再看網(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；由網(wǎng)絡(luò)圖

2、確定候選設(shè)施點(diǎn)j可覆蓋的需求點(diǎn)集合？?(?和可覆蓋需求點(diǎn)i的設(shè)施節(jié)點(diǎn) 的集合?(?)見候選點(diǎn)服務(wù)范圍村落號(hào)?(?)?(?)11,2,31,2,32124,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，| ?(4)|=5為最大，故首先？4。因無容量約束，指派2,3,4,6,7 歸村落4服務(wù)。此時(shí)N=1,5，M=1,2,3,5,6,7;則更新候選點(diǎn)服務(wù)范圍，見表更新后的候選點(diǎn)服務(wù)范圍村落號(hào)?(?)?(?)111,2,321,5314552,5,665因?yàn)椋?（2）=1,5=N

3、，恰好滿足條件。則？=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ù)過 程中的運(yùn)輸費(fèi)用。因此，用城市距離進(jìn)行考慮，要求新的辦公室到各個(gè)合作

4、伙伴之間運(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)化為 工?=1?點(diǎn)需求的選址問題。2. 笛卡爾距離即直角距離，歐基米德距離即直線距離；3. 重心法：初始化+迭代公式+Excel/C編程/matlab編程迭代+迭代終止條件解：（1）設(shè)新辦公室的地址的坐標(biāo)為（x,y）,給題目已知的5個(gè)點(diǎn)編號(hào)15。由于笛卡爾距離d?=| ?+| ?。則目標(biāo)函數(shù)為時(shí)總運(yùn)輸距

5、離 H最短。?=肓?=1?=肓?=1? ? + 藥?=1? ?Xiwi2Zwiyiwi2Zwi43343342511257272271141111411141127112E?= 12為偶數(shù)，即？?勻在第六個(gè)、第七個(gè)點(diǎn)之間可得? 7, ?7,11。 H = 81。(2) 設(shè)初始點(diǎn)為(x0, yo )有題意得，阿基米德距離為d(0)=V(xo - xj2 + (yo - yj2,目標(biāo)函數(shù)H(運(yùn)輸總費(fèi)用)=豈1 Widi,利用不動(dòng)點(diǎn)算法，取一個(gè)初始的迭代點(diǎn)(x00) ,y00)=(8,7)此時(shí)H°=62.51丁5xi令x(1)-曰Wi可 0V5Xj,齊1石卓吩,4(1)=価xj2 + (y

6、01)yi)2H1 =5=1 Wj dj)=62.14由EXCEL迭代得， 纟出果:口果如ABcDEFGLH1Xydld2d3d4d5H2S755, 6568545. 099025662. 5117537.6512597. 3688954. 9680135.1494295. 40S254.9395336. 35944962.1369S47.585267.4S60795. 0006845. 0201335. Bl 72094” 3998056. 4331362,1090857.5324i7. 5344875. 0325414. 9843415. 56505L 36718643977962.104

7、936匚5922267. 5600375” 0574654* 9736745” 5914884+ 342135氐 43220162. 1034677.6025627.5760535. 0760824.9700975. 6085164. 8234846. 42332162-1027387.6109897.5870335, 0S97984. 968665. 6208424. 809755S. 41592362.1023497,617394：7, 5948595. 0998584. 967955. 6238214. 7996836" 41026662.10213107.622157. 60

8、05255.1072254* 9675345* 6349764. 7923176. 4060662. 10202117.625657.6046525.1126174.9672665. 6394654.7869226. 40296362.10196費(fèi)用結(jié)果保留四位小數(shù)得最優(yōu)解為x=7.6257,y=7.6047,此時(shí)費(fèi)用最小為 H=62.1020(3) 比較兩次結(jié)果可知?dú)W基米德中的費(fèi)用小于笛卡爾距離，因直線距離是V直角距離， 因此用歐基米德距離更為精確。直角距離比較適合于城區(qū)范圍內(nèi)的選址，歐基米德距離 比較適合于遠(yuǎn)距離的選址。12. 一臺(tái)機(jī)器工具小制造商要遷址，并確定了兩個(gè)地區(qū)以供選擇。A地的年

9、固定成本為800000元，可變成本為14000元/臺(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+14000xB地，總成本 C(B)=920000+13000x1) 若兩地成本相等，則C(A)=C(B)解得：x=1202) 若 A 地優(yōu)于 B 地，則 C(A)<C(B)因此得 0<x<120同理，當(dāng)x>120時(shí)，B地優(yōu)于A地。13.

10、利用表2.8所示的因素評(píng)分，以最大綜合得分為基礎(chǔ)，建模分析應(yīng) 選擇地點(diǎn)A B、C中的哪一個(gè)？表2.8因素評(píng)分表解：權(quán)重矩陣設(shè)為 W 則？?= 0,15 0.20 0.18 0.27 0.10 0.10三個(gè)位置的因素評(píng)分作為3行構(gòu)成因素矩陣S。80 72 88 94 98 96?= 70 76 90 86 90 85 60 92 90 80 82 7587.02可得綜合加權(quán)矩陣E=S*Wfe2.62。80.90可知E(A)> E(B)> E(C)。即選擇A點(diǎn)。14. 一個(gè)玩具制造商在全國(guó)的五個(gè)地區(qū)生產(chǎn)玩具，原材料將從一個(gè)新的 中心倉(cāng)庫(kù)運(yùn)出，而此倉(cāng)庫(kù)的地點(diǎn)還有待確定。運(yùn)至各地的原材料數(shù)

11、量相同， 已建立一個(gè)坐標(biāo)城，各地的坐標(biāo)位置如表2.9所示。請(qǐng)確定中心倉(cāng)庫(kù)的坐標(biāo) 位置。表2.9各地的坐標(biāo)位置解：設(shè)倉(cāng)庫(kù)的坐標(biāo)為(X0，y°)，五個(gè)生產(chǎn)地為(Xi,yj,倉(cāng)庫(kù)到各生產(chǎn)地的距離為di, 因運(yùn)至各地的原材料數(shù)量相同，故可設(shè) wi = 1(i = 1,2,5);初始解：x00)1 n 1 n-Xj,y00)-yj，即?(0) = 5，?(0) = 4。n j 1n j 1直線距離為? =V (?- ?2 + (? - ?2目標(biāo)函數(shù)運(yùn)輸總費(fèi)用H=Z5=1 Wi di，其中Wj = 1(i = 1,2,5)5?0 =刀?= 13.6094?=1y5xix(1) =3 肝 y(1)

12、 X0v51, o3=1百根據(jù)下列進(jìn)行迭代:y5 yi_4 珥(1V(1)2 丄 / (1)、2, di=v(x0- Xj)2 + (Yo - yi)2召=1 d；直到運(yùn)費(fèi)無法減小。用MATLAB進(jìn)行編碼：運(yùn)行結(jié)果得，迭代78次得到最優(yōu)解。其中選址坐標(biāo)為(5.6235,4.9918 ),最小運(yùn)費(fèi)為 H=13.4550。 或由EXCEL迭代得，結(jié)果如圖費(fèi)用結(jié)果保留三位小數(shù)得最優(yōu)解為 X=5.5767, y=4.010,H=13.45615. 某物流公司擬建一倉(cāng)庫(kù)負(fù)責(zé)向四個(gè)工廠進(jìn)行物料供應(yīng)配送，各工廠的具體位置與年物料配送量見表2.10，設(shè)擬建物流公司倉(cāng)庫(kù)對(duì)各工廠的單 位運(yùn)輸成本相等。利用重心法計(jì)

13、算確定物流公司的倉(cāng)庫(kù)坐標(biāo)位置為多少。表2.10各工廠的具體位置與年物料配送量解:設(shè)倉(cāng)庫(kù)的坐標(biāo)為(X0，Y0)，4個(gè)工廠的坐標(biāo)為(Xi，Yi),倉(cāng)庫(kù)到各生產(chǎn)地的距離為di = V(>0 - Xi)2 + (y0 - yi)2,目標(biāo)函數(shù)運(yùn)輸總費(fèi)用a?di =Wi di，?為工廠年配送量，？?為單位運(yùn)輸成本，因單位運(yùn)輸成本相等，故令 ?=1,于是有W1 = 2000, w2 = 1200, w3 = 1000, w4 = 25001 1初始解 X0 = n 3xi=37.5, y0 = ； 3yi=42.5 d(0) =V(X0 - Xi)2 + (y0 - yi)2,此時(shí) H0=192249

14、.43yi3,d(1)=V(X01)- Xi)2+(y01)- yi)23=1 dj=3= wi d(1) =190400.4由EXCEL迭代得，結(jié)果如圖結(jié)果保留整數(shù)得最優(yōu)解為(42.22076 , 33.82437) ,H=188709 或用MATLA進(jìn)行編碼(文件見附件)：運(yùn)行結(jié)果得，迭代59次得到最優(yōu)解。其中選址坐標(biāo)為(42.2865, 33.6732 ),最小運(yùn)費(fèi)為 H= 188707.91416. 籌建一農(nóng)副產(chǎn)品流通加工廠，可供選擇的候選廠址有 DE、F三處， 因地址不同各廠加工成本亦有區(qū)別，各廠址每年費(fèi)用如表2.7所示。此外，為決定廠址還考慮了一些重要的非成本因素，如當(dāng)?shù)馗?jìng)爭(zhēng)能力、

15、氣候變化和周圍環(huán)境是否適合農(nóng)副產(chǎn)品流通加工等。對(duì)于競(jìng)爭(zhēng)能力而言，F(xiàn)地最強(qiáng)，DE兩地相平；就氣候來說，D比E好，F(xiàn)地最好；至于環(huán)境，E地最優(yōu)，其次 為F地、D地。如果各主觀因素的重要性指數(shù) a、b、c依次為0.6、0.3和0.1，要求用因次分析法評(píng)定最佳廠址在何處表2.11各候選廠址每年加工成本費(fèi)用要點(diǎn)：P中值法分5個(gè)步驟進(jìn)行。解：4(1) 計(jì)算客觀量度值OMi , OMj = C E-=0.33951 1 1 1OMD=523 ?(52T52T 帝)同理可得：OMe = 0.3382, OMf = 0.3223。(2) 計(jì)算主觀評(píng)比值Sk (有3個(gè)不同的主觀因素) 競(jìng)爭(zhēng)能力(F>D=E

16、注：D=E比較記為0.5兩兩相比廠址FED比重SaD00.50.50.167E00.50.50.167F1120.666 氣候(F>D>E兩兩相比廠址FED比重SaD0110.33E000F1120.67 環(huán)境(E>F>D兩兩相比廠址FED比重SaD0000E1120.67F0110.33(3)計(jì)算主觀量度值SMi , ?= E3?=1 ?其中Ik為各主觀因素的重要性指數(shù)。因素kDEF重要性指數(shù)IkSa0.1670.1670.6660.6Sib0.3300.670.3Sc00.670.330.1計(jì)算可得SMd = 0.167 ?0.6+ 0.33? 0.3+ 0?0.1

17、 = 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è)兩者相等即同種重要，即主 客觀比重值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

18、.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)的條件，如圖2-6所示 已知市場(chǎng)的最大服務(wù)直徑為 3km為保護(hù)該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場(chǎng)。問應(yīng)如何規(guī)劃？圖2-6小區(qū)居民點(diǎn)位置圖解：N= 123,4,5,6,7,8,9, M= 1,2,3,4,5,7,8,9，由圖 2-6 兩點(diǎn)間的最短距離，根據(jù)最大服務(wù)半徑為3km的約束及第6居民點(diǎn)不適合建市場(chǎng)的要求，可確定集合A(j)和B(i)。

19、如表2-3所示。表23候選點(diǎn)服務(wù)范圍因?yàn)?A(4)=1,3,4,5,6,7, A(3)=1,2,3,4,5,6,|A(4)|=|A(3)|=6 為最大,隨機(jī)選取 j '=4。由于無容量約束故依次指派5,7,1,6,3,4點(diǎn)歸節(jié)點(diǎn)4服務(wù)。此時(shí)，N=2,8,9,M =1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表2 4所示。表2 4候選點(diǎn)服務(wù)范圍因?yàn)?A(8) = 8,9，|A(8)| = |A(9)|=2 為最大，故選取 j'= 8 或 j'= 9,并且 8, 9 兩 點(diǎn)歸節(jié)點(diǎn)8或9服務(wù)。同理，再迭代一次，得j'= 2,居民點(diǎn)2歸節(jié)點(diǎn)2服務(wù)。因此

20、, 計(jì)算結(jié)果為(4,8,2 )或(4,9,2 )。若選擇j'= 3,故依次指派1,2,3,4,5,6 點(diǎn)歸節(jié)點(diǎn)3服務(wù)。此時(shí)，N= 7,8,9,M = 1,2,4,5,7,8,9,更新集合A(j)和集合B(i)后如表2 5所示。表25候選點(diǎn)服務(wù)范圍由于|A(8)| = 3最大，選擇j'= &因此計(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è)順序表最小工作數(shù)=28/8=3

21、.5,因此需要4個(gè)工作臺(tái) 根據(jù)作業(yè)的相關(guān)情況進(jìn)行安排，結(jié)果如下表工作站序號(hào)作業(yè)單元工作時(shí)間空閑時(shí)間1H,G,F712E623D, C714B, A80生產(chǎn)線效率=完成作業(yè)所需時(shí)間總和/(實(shí)際工作站總數(shù)*時(shí)間周期)=總=0.875。12. 某流水線有17項(xiàng)作業(yè)需要平衡，其中最長(zhǎng)的作業(yè)為 2.4分鐘，所有 作業(yè)的總時(shí)間為18分鐘。該流水線每天工作 450分鐘。試求：(1) 最大和最小的周期時(shí)間各是多少？(2) 該流水線理論上可能達(dá)到的每日產(chǎn)能是多少？(3) 按最大產(chǎn)能來算，最少需要幾個(gè)工作站？(4) 若每天產(chǎn)能為125分鐘，則周期時(shí)間應(yīng)為多長(zhǎng)？(5) 若周期時(shí)間分別是9分鐘和15分鐘，則產(chǎn)能分別是

22、多少?解：(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)周期時(shí)間為9min時(shí)，產(chǎn)能為450/9=50/天；當(dāng)周期時(shí)間為15min，產(chǎn)能為450/15=30/天。13. 某學(xué)院注冊(cè)有四

23、道手續(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é)生流向表J J45D530昏詢2302000朝班發(fā)卡00000J i要點(diǎn)：1.解題思路：?jiǎn)蜗蛭锪鲝闹帘?T雙向物流從至表 f作業(yè)對(duì)按雙向物流從至表中 強(qiáng)度值排序，劃分物流等級(jí)確定物流路線比例參考相關(guān)圖得接近程度排序表按接近程度得作業(yè)單位位置相關(guān)圖按接近程度排序得作業(yè)單位面積相關(guān)圖

24、2.參考相關(guān)圖:物流強(qiáng)度等級(jí)AEIOUX物流路線比例10%20%30%40%00承擔(dān)的物流量比 例40%30%20%10%00接近程度4321003. 路線比例設(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-D75020%133.3%E2A-B70020%131.1%E3A-C55020%124.4%E4

25、B-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)圖現(xiàn)四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級(jí)卡和確認(rèn)交費(fèi)，分別安排在A、B C D四個(gè)連續(xù)相鄰的同樣大小的房間，即位置為下圖關(guān)系領(lǐng)咨詢領(lǐng)班級(jí)繳費(fèi)該布置可得到改進(jìn)，改進(jìn)方案為咨詢領(lǐng)領(lǐng)班級(jí)繳費(fèi)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ì)6