规划计算题整理

1、第二章设施选址10. 一家银行准备在某县的农村地区投放一批 ATM自动取款机, 以方便农村的用户取款.该农村地区的村落座落情况和相对距离如图2.13所示.为了能保证任一村的人都可以在 20分钟之内到达自动取款机取款,银行需要多少台自动取款机？它们的位置又在哪里图2.13村落座落情况和相对距离要点：1.明确N, M , 含义；2 .分析正确后,可参照直接写出,无需再看网络图；3 .熟悉最少点覆盖启发式算法的步骤,考虑是否有容量约束.解：【集合覆盖模型】区域中需求点集合N=1,2,3,4,5,6,7;ATM取款机设施候选点集合 M=1,2,3,4,5,6,7;由网络图确定候选设施点j可覆盖的需求点

2、集合和可覆盖需求点i的设施节点的集合,见表2.10.1.2.10.1 候选点效劳范围村落号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由于 =2,3,4,6,7, |=5为最大,故首先=4.因无容量约束,指派2,3,4,6,7归村落4效劳.止匕时N=1,5 , M=1,2,3,5,6,7;那么更新候选点效劳范围,见表 2.10.2.2.10.2 更新后的候选点效劳范围村落号111,2,321,5314552,5,6657由于 =1,5=N,恰好满足条件.那么 =2.综上

3、所述,银行需要2台自动取款机,分别至于村落号为 2和4的位置,2号为1,5村落效劳,4号为2,3,4,6,7村落效劳.11.一个临时帮助效劳中央方案在一个大城市的郊外开设一个新 的办公室.在经过一定的精简之后,该公司有5个大的合作伙伴.在 一个以km为单位的笛卡尔坐标系中,它们的坐标分别为：(4, 4),(4, 11), (7 , 2), (11, 11), (14, 7).它们的效劳需求量的权重分 别为：wl=3, w2=2, w3=2, w4=4, w5=1.对于该效劳中央来说, 主要的日常费用是他们员工完成任务过程中的运输费用.因此,用城市距离进行考虑,要求新的办公室到各个合作伙伴之间运

4、输的运输费 用最小.1)请确定一个新办公室的地址,用笛卡尔坐标来表达相应 结果.2)如果由于该地区的人口稀少,城市还没有到达一定的规模, 可以用欧几米德距离进行计算,新办公室又得在哪里投建？青比拟两次结果,分析它们之间的关系c 要点：1.补充交叉中值模型知识点"VI2 3.6两卢尼的左空靛考踏获的曜蒯m剧毛加.wswsixjh般g等储 数精抬趣髓.,目相弼加p/也加卜加卜小卜讣小川叫加四讪华示.花窗士酊/建由由跑用工力轲但蹴即孙:Mk-0+卜一工厂u 二号班r【M土战士卜爆Bt,贮莪哥犯污型加赧SH正施如桩b耳柄脖踵超 班旦土轼卜厂讣“-汕,上述原理可以推广到多个需求点时的情形*洽定

5、叱t点的坐标(工)4工2,为)一,与,力), 确定设谑的坐标使该点至所有给定点的总折至距离量短,目标函数为N3川三K 一工小二|7 一 M |< 3-2 >2l?-1求馨方法如下.将与巧与遂行排序.找出中间值.当再为奇数H,那么最优的'就等 于该中同值.W叶为何象时1记两个中间度为勺和三中那么最优的了为修网如给定 (3, i). (14, 5). (A 9)三个点1将工型标排序后为九九14f那么量寰的工坐标为T,如果给定 (23?普、(6： 2)、(11*孔)、(*25)四个点,将k坐标排序后为人6. 1K 23,那么辘最优打 T樊标为6占万£1】*对于里忧的y坐

6、标的璃定,与上述方法完全一样, 一考志豪莪点的物范量的不司,晨设霍求点注勺物流量为喉,那么目标函数为中 工M£w：|x工小£唧卜-坊|0-3)i*1J1如果当为整物那么可以认为磔标点(三明)处有增企需求？将n点簸的选址问题转换成 EL吗点通索药选址问题然后利用前面的方法获得嘘的最优的坐标萤.如果崂为小数,H目 相其处理为变数形式,例如,假设叫等于03我们可以取% = 3,然后将目粽函数缩小1ZL0, 4 样就可以选用前面的方法求解.,|关键句：将n点需求的选址问题转化为点需求的选址问题.2 .笛卡尔距离即直角距离,欧基米德距离即直线距离；3 .重心法：初始化+迭代公式+Ex

7、cel/C编程/matlab编程迭代+迭代终止条件解：1设新办公室的地址的坐标为x,y,给题目的5个点编号15 由于笛卡尔距离 =| - |+| - |.那么目标函数为时总运输距离H最短.|43343342511257272271141111411141127112为偶数,即 均在第六个、第七个点之间可得,O02设初始点为有题意得,阿基米德距离为目标函数H运输总费用尸,利用不动点算法,取一个初始的迭代点,=8,7此时=62.51令 =,=62.14由EXCELS代得,结果如图dl234567391011S 7.6512597. 535267. 582M 592226 7. 602562 7.

8、6109S9 7, 6173947. 622157. 6256577.3688957.4860797. 5344077. 5600377.5760537.EB70337, 5948597. 6005257. 60465254, 9630135. 0006845. 0325415. 0574655. 0760825. 0897985. 0998585.1072255.11261Yd25.6568545.1494295. 0202134 9843414.9736744.9700974. 968664, 967954. 9675344. 967266d35. 099025. 408255. 5172

9、095. 56505 5.591486 5.608516 5. 620342 5. 623821 5. 634976 5. 639465d454, 9395334. 399S05 4 8671364. 8421354. 8234844. 8097554, 7996884. 7923174. 786922d566. 3594496. 433136. 4397796. 4822016. 4233216. 4159236. 4102666. 406066. 402963H62, 5117562.1369862.1090862,1049362,1034662,1027362.1023462.10213

10、62,1020262.10196费用结果保存四位小数得最优解为x=7.6257,y=7.6047,止匕时费用最小为 H=62.1020(3)比拟两次结果可知欧基米德中的费用小于笛卡尔距离,因直线距离是(直 角距离,因此用欧基米德距离更为精确.直角距离比拟适合于城区范围内的选址, 欧基米德距离比拟适合于远距离的选址.12 .一台机器工具小制造商要迁址,并确定了两个地区以供选择.A地的年固定本钱为800000元,可变本钱为14000元/台；B地的年固定本钱为920000元,可变本钱为13000元/台.产品最后售价为17000 元/台.(1)当产量为多少时,两地的总本钱相等？(2)当产量处于什么范围

11、时,A地优于B地？当产量处于什么范围时,B地优于A地？解：答：设x为之制造商的年产量A地,总本钱 C(A)=800000+14000xB地,总本钱 C(B)=920000+13000x1)假设两地本钱相等,那么 C(A)=C(B)解得：x=1202)假设A地优于B地,那么C(A)<C(B)因此得0Vx<120同理,当x>120时,B地优于A地.13 .利用表2.8所示的因素评分,以最大综合得分为根底,建模分析应选择地点A、B、C中的哪一个？表2.8因素评分表因素?每项总分】皿分)权重一位置A B C便利设施(U5807060停车场727692显示区域0J88S90顾客交通0.

12、2794一86加卜运营本钱1LH)98一90«2临近0.1096P75解：权重矩P$设为W,那么三个位置的因素评分作为3行构成因素矩阵S可得综合加权矩阵E=S*W= o可知E(A)> E(B)> E(C).即选择A点.14 .一个玩具制造商在全国的五个地区生产玩具, 原材料将从一个 新的中央仓库运出,而此仓库的地点还有待确定.运至各地的原材料 数量相同,已建立一个坐标城,各地的坐标位置如表 2.9所示.请确 定中央仓库的坐标位置.表2.9各地的坐标位置地点ABCDE(M)(3,7)(8.2)(4,6)4,1)解：设仓库的坐标为(,五个生产地为,仓库到各生产地的距离为,因运

13、至各地的原材料数量相同,故可设)1 n1 n初始解：x00)Z Xj,y00)y即,.n j in j d直线距离为目标函数运输总费用H=,其中根据以下进行迭代:直到运费无法减小.用MATLAB!行编码:cleai cIlt 11：- 3844 5 .i-lIQe j- i 54 jl-(ri(i).)2+4川 J 2) 0.5.x=K r值最小直最大值7.2/. L417E.&44.63313.455013.455013,45505557979791x79 ddz13,45501 1 60943.98393.0.37653.933515.647615.647615,64763.610

14、13.91013.91011x79 do.44.09622L9&3521gBs521.9&S5lx7S dott. 55.6235H d c B b AyXJ fur i-1:5A=A+±(r/d(j)：B=E+L/l(j)；C=C+yj;tnd；i«i+l ：息b i .1 =C：f B ；for j=I:SSOJr t j)找MMiJ-F?厂 216 6;ndRHa4d+d(3Hd艰;运行结果得,迭代78次得到最优解.其中选址坐标为(5.6235,4.9918),最小运费为 H=13.4550.EXCE迭代得,结果如图.也d.AECDEFH1Xydld2

15、dSd4芯H2543, 6055513. 6055512. 2360683.162273113. 6094535.221694. 0962383. 6561923. 4804052. 2620423.3285460. 78423713, 5114245, 3287094. 0887133. 7280673. 3909462. 3277653. 3623820. 67712713.4862955.3969464.0657293. 7887753. 3231982. 3859133. 3689370.60672513. 4735765, 4462644. 047031834613. 2729042

16、, 4301793* 3728440, 55572913. 4662775. 4836174. 0340953. 8684553. 2356952. 4629053. 3774030. 51750313. 4619785. 51234.0253563. 3936043. 2079152. 4872213.3822820. 48835913, 4593895. 534554工 0193643. 9125643. 1868882. 505549& 3869480. 4B584913. 4578105. 5519774. 0151493. 9270753. 1707482. 5195763.

17、 3911290. 44827913. 45681115. 5657234. 0121073. 9383333.1582042. 5304593, 3947450, 43444113. 45618125? 5766594.009863, 9471653.1483522.5389983. 39781042345513. E578或由费用结果保存三位小数得最优解为 X=5.5767 , y=4.010,H=13.45615.某物流公司拟建一仓库负责向四个工厂进行物料供给配送,各工厂的具体位置与年物料配送量见表2.10,设拟建物流公司仓库对各 工厂的单位运输本钱相等.利用重心法计算确定物流公司的仓库

18、坐标 位置为多少.表2.10各工厂的具体位置与年物料配送量工厂及其位置坐标P1P2P3P4XIY1X2¥2X3Y3X4Y42070&06020205020年配送病200.120010002500解：设仓库的坐标为(,个工厂的坐标为,仓库到各生产地的距离为,目标函数运输总费用H=, 为工厂年配送量,为单位运输本钱,因单位运输本钱相等,故令 =1,于是有初始解 -=37.5,-=42.5止匕时 =192249.4=190400.4由EXCE迭代得,结果如图ABCDHFG1xydld2d3d4H237. 5包532. 5960128. 5043928. 5043925. 73908

19、192249.4339. 5097820.1632535. 6-t91528. 5192228. 0568822, 72887190400-4440. 4371238, 40831机 6259429.1360127. 505320. 74402189580. 41 510. 9500337,1375133, 9723929, 7589527, 0665519 38031189172.8641. Zm M36. 2232839. 9242430. 2582126, 7632918. 41562188960. 774L 5274635, 5630240. 6120330. 6333326. 563

20、8717. 71981188847.48M, 708735, 082354L 115®.30. 9105326, 4337817. 21113183785. 93*1.弘62934：. 7293441. 4883131.1153326, 3479416. 83557188751. 91.041, 9510834. 46841. 7656931.2673426. 2901816. 55621188732. 91142. 0309284, 273234L 9733731, 380826, 2504516. 34721188722. 2124:2. 0917434,12734Z 12951

21、31. 465926, 2226116.19015188716.11342. 138083i. 017542. 2473131. 5299726. 2027616. 07172189712.61442. 1733833. 9346242. 3363931.5783526. 188415. 98217183710.6L542.2002733, 8719112,403931.6149926. 1778915. 91433188709. 516-1 FT42. 2ZH633, 824=3742. 43551331. 6427726. 1701315. 36234188708.8结果保存整数得最优解为

22、(42.22076, 33.82437) ,H=188709或用MATLAB进行编码(文件见附件)七二 m; tieh (1)-42. 5z-2020 Sd,产AD >0 20;*=2000 1 200 1000 2500：0 ；-tor j=i：cAt; i-''-> <jj)'"i>. 5.营ndH i_w I) *d L)+h (1) *d (2) i A td (1) aJ OJjileHACi. E-0 CO .三far j=l：131x60 do.3Z5OOO422M5j)/d j)A11935%,11935.1.1935/

23、04E二E-w j)/d (j>1x60 dd*.33.573342,5000j)/d j)F.2&2.23S528223852821238s二«rid-=C生503%9.5039“,9.5039/03W-H(i).L-i M42.51 限.“1x60 do.15,69891.6871.42,6183L9225e+05|-3-Tor j=l：4j)= 4(ai)f厂2+£1»£-下仃 p) ,2) '0.5;j MSO41.807 le.604 1.&871.5041.8871e+05*nd w2000.12.100025g

24、田/二浦口小-口hrfUdf", X固60.20,“20SO-d'y70r60.2.,“2070运行结果得,迭代59次得到最优解其中选址坐标为(42.2865, 33.6732),最小运费为H= 188707.914.E、16.筹建一农副产品流通加工厂,可供选择的候选厂址有 D、F三处,因地址不同各厂加工本钱亦有区别,各厂址每年费用如表2.7所示.止匕外,为决定厂址还考虑了一些重要的非本钱因素,如当 地竞争水平、气候变化和周围环境是否适合农副产品流通加工等.对于竞争水平而言,F地最强,D、E两地相平；就气候来说,D比E 好,F地最好；至于环境,E地最优,其次为F地、D地.如果

25、各主 观因素的重要性指数a、b、c依次为0.6、0.3和0.1,要求用因次分 析法评定最正确厂址在何处.表2.11各候选厂址每年加工本钱费用选址本钱 本钱因素本钱/千元DEF工资250230248运输费用181203190租金r 75P 8391其他费用r 17922523525551要点：P中值法分5个步骤进行解：1计算客观量度值同理可得：2计算主观评选值竞争水平F>D=E0有3个不同的主观因素注：D=E,比拟记为0.5两两相比厂址FED比重D00.50.50.167E00.50.50.167F1120.666气候F>D>E两两相比厂址FED比重D0110.33E000F1

26、120.67环境E>F>D两两相比厂址FED比重D0000E1120.67F0110.33(3)计算主观量度值,其中 为各主观因素的重要性指数.因素kDEF重要性指数0.1670.1670.6660.60.3300.670.300.670.330.1计算可得(4)计算位置量度值,()由于题中没有给出主观因素与客观因素的相互比重,假设两者相等即同种重要,即主客观比重值0(5)决策根据各位置量度值的大小,F厂址所得位置量度值在3个候选地址中最高,应选F为建厂厂址.17.在某区域需规划建设假设干个农贸市场为将来该区 9个主要居民点提供效劳,除第6居民点外,其他各点均有建设市场的条件,如图

27、2-6所示.市场的最大效劳直径为 3km,为保护该区域的环境,希望尽可能少地建造农贸市场.问应如何规划?图26小区居民点位置图解：N = 1,2,3,4,5,6,7,8,9, M =1,2,3,4,5,7,8,9,由图 2 6两点间的最短距离, 根据最大效劳半径为3km的约束及第6居民点不适合建市场的要求,可确定集 合A(j)和B(i)0如表2 3所示.表2 3候选点效劳范围居民点号A(j)B(i)112"L2A4午 Ml12331 二5,6123T54L3<4,53,43643.7,874,6,7.84J,887,859不氏9由于 A(4)=1,3,4,5,6,7 , A(3

28、)=1,2,3,4,5,6,|A(4)|= |A(3)|=6 为最大,随机选取 j '=4.由于无容量约束故依次指派5,7,1,6,3,4点归节点4效劳.此时,N = 2,8,9,M=1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表2-4所示表2 4候选点效劳范围居民点号A(j)B(i)个个勺3456r 1888,9gX98.9由于A(8)=8,9 , |A(8)| =|A(9)|=2 为最大,应选取j' =8或上=9,并且8, 9两点归节点8或9效劳.同理,再迭代一次,得j' =2,居民点2归节点 2效劳.因此,计算结果为(4,8,2 )或(4,9,2

29、 ).假设选择j ' =3,故依次指派1,2,3,4,5,6 点归节点3效劳.此时,N= 7,8,9,M =1,2,4,5,7,8,9,更新集合A(j)和集合B(i)后如表2-5所示.表2 5候选点效劳范围居民点号A(i)B(01)3477567,87,877,87,887,比998J由于|A(8)| = 3最大,选择j'= 8.因此计算结果为(3,8)第三章设施规划11 .某生产线共有8项作业,其工作周期为8分钟.各项作业的装配顺序和时间如表3.30所示.请根据周期时间和作业顺序限制,确定最少工作站数和各项作业的安排,并算出此安排下生产线的效率.表3,30周期时间和作业顺序表

30、柞业ABCDEFGH完成时同一53436142续后作业无ABBCC0EFG解：由题意得网络活动图Job on nodes：由题意各作业所需时间之和=5+3+4+3+6+1+4+2=28最小工作数=28/8=3.5,因此需要4个工作台根据作业的相关情况进行安排,结果如下表工作站序号作业单元工作时间空闲时间1H,G,F712E623D, C714B, A80生产线效率=完成作业所需时间总和/实际工作站总数*时间周期尸012 .某流水线有17项作业需要平衡,其中最长白作业为2.4分钟, 所有作业的总时间为18分钟.该流水线每天工作450分钟.试求：(1)最大和最小的周期时间各是多少？(2)该流水线理

31、论上可能到达的每日产能是多少？(3)按最大产能来算,最少需要几个工作站？(4)假设每天产能为125分钟,那么周期时间应为多长？(5)假设周期时间分别是9分钟和15分钟,那么产能分别是多少?解：(1)当17项作业只能串行依次进行时,可得最大周期为18min.当17项作业均并行进行时,可得最小周期为 2.4min.(2)产能为单位时间生产的产品数量.以最大周期计算,得最小产能为 1/18min=0.056/min；以最小周期计算,得最大产能为 1/2.4min=0.417/min；综上所述,每日可能产能为25,187.5.(3)依题意有需要18/2.4=7.5,所以最少需要8个工作站.(4)周期时

32、间为 450/125=3.6min.(5)当周期时间为9min时,产能为450/9=50/天；当周期时间为15min,产能为450/15=30庆.13 .某学院注册有四道手续：领取表格、咨询、领取班级卡和确 认交费,分别安排在A、B、C、D四个连续相邻的同样大小的房间, 由于同时有新老学生,如果450名新学生领表后去咨询,550名老学 生领表后直接去领班级卡,而毕业班学生已经注册过,领表后直接去 缴费,详细学生流向如表3.31所示.试问已有布置是否可以改良, 假设能,该如何改良？表3.31学生流向表咨询击费领表4组5刃5 口自询2302000战笠蹶噌007500|a要点：1.解题思路：单向物流

33、从至表 双向物流从至表 作业对按双向物流从至表中强度值排序,划分物流等级确定物流路线比例参考相关图得接近程度排序表按接近程度得作业单位位置相关图按接近程度排序得作业单位面积相关图2.参考相关图:物流强度等级r aEIOUP X物流路线比例10%20%30%40%00承当的物流量比 例40%30%20%10%00接近程度432 ：1003.路线比例设计=线路条数/总线路条数 解：由学生流向表得到双向物流表如下：双向物流表领表(A)咨询(B)领班级卡(C)缴费(D)领表(A)700 (2)550 (3)50 (5)咨询(B)200 (4)领班级卡(C) 1750 (1)缴费(D)根据学生流量划分物

34、流等级确定物流路线比例如下:厅P作业单位对强度值路线比例设计路线条数物流强度比例强度等级1C-D75020%133.3%E2A-B70020%131.1%E3A-C55020%124.4%E4B-C20040%211.1%O5A-D50O合计2250由以上关系图得接近程度排序表领表A咨询B领班级卡C缴费D领表A3/E3/E1/O咨询B3/E1/O0/U领班级卡C3/E1/O3/E缴费D1/O0/U3/E合计7474排序2413作业单位位置相关图和作业单位面积相关图分别安排在A、B、C、现四道手续：领取表格、咨询、领取班级卡和确认交费, D四个连续相邻的同样大小的房间,即位置为以下图关系领表咨询领班级卡缴费该布置可得到改良,改良方案为咨询领表领班级卡缴费图3.28习题14作业相关图解：由该作业相关图可得接近程度排序表如下：ABCDEA4/A2/I0/U0/UB4/A2/I3/E3/EC2/I2/I0/U0/UD0/U3/E0/UI/OE0/U3/E0/UI/O合计612444排序21534可得作业单位位置相关图如下:14 .根据作业相关图,绘制作业单位位置相关图.15 .某工厂有ABCDE