西安建筑科技大学运筹学习题集

1、考试点西安科技大筹学习题集第一章 线性规划1、写出下列问题的模型（1）一家玩具公司三种桌上玩具，每一种要求不同的技术。高级的一种需要 17 小时装配劳动力，8 小时检验，每台利润 300 元。中级的需要 10 小时劳动力，4 小时检验，利润 200 元。低级的需要 2 小时劳动力，2 小时检验，利润 100 元。可供利用的劳动力为 1000 小时，检验 500 小时。其次，有市场表明，对高级的需求量不超过 50 台，中级的不超过 80 台，低级的不超过 150 台。商决定采用一个能使总利润为最大的最优生产计划。（2）某材料预制厂生产 A1 、 A2 两种，现有两种原料，第一种有 72 立方米，

2、第二种有 56 平方米 ，假设生产每种都需要两种原材料。生产每件所需原料如表1-1 所示。每生产一件 A1 可获得利润 60 元，生产一件 A2 可获得利润 1000 元，预制厂在现有原料的条件下， A1 、 A2 各应生产多少，才能使获得利润最大。表 1-1（3） 用长度为 500 厘米的条材，截成长度分别为 98 厘米和 78 厘米的两种毛坯，要求共截出长 98 厘米的毛坯 10000 根，78 厘米的 20000 根，问怎样截取，才能使用料最少？（4） 某商店制定某商品 7-12 月的进货收货计划，已知商店仓库容量不得超过 500 件，底已存货 200 件，以后每月初进货一次，假设各月份

3、某商品买进、售出所示，问各月进货售货各多少，才能使总收入最多?如下表 1-2表 1-2789101112月买进（元）282425272323292426282225售出（元）（5）某厂生产 A 、 B 、C 三种A 需要 1 小时技术准备（指设针、B 需要 2 小时技术准备、4 小时劳动。每试验等）、10 小时直接劳动和 3 公斤材料。每C 需要 1 小时技术准备、5 小时劳动和 1 千克材料。可利用的技和 2 千克材料。每术准备时间为 100 小时，劳动时间为 700 小时，材料为 400 千克。原料（：立方米）第一种第二种A10.180.09A20.070.68考试点公司对大量购买提供较大

4、的折扣，利润数字如下表 1-3 所示。试列出使利润最大的数模。表 1-3ABC销售量（件）利润（元）销售量（件）利润（元）销售量（件）利润（元）04040100100150150 以上109805050100100 以上6430100100 以上54（6）某一市政建设工程项目在随后的四年中需分别拨款 200、400、800 万和500，要求拨款在该年年初提供，市拟以卖长期公债的筹款。长期公债在筹款的四年中市场利息分别预计为 9%，8%，8.5%和 9.5%，并约定公债利息在工程完工后即开始付息，连续付 20 年之后还本。在工程建设的头三年，卖公债的多余部分投入银行作为当年有期储蓄，以便用于随后

5、的几年（显然第四年无有期储蓄），银行的有期储蓄利息率分别预计为 8%，7.5%和 6.5%。现在的问题是求项市政建设工程得以完成，且付息最低。最优的卖公债和尤有期储蓄方案，使该（7）某钢铁公司有三个铁矿，他们日产矿石分别为 5000，3000 和 1000 吨。该公司有四个炼钢厂，他们每天所需的矿石量分别为 4000，25000，1000 和 15000 吨。这三个铁矿与四个炼钢厂的距离间下表 1-4。问该公司应如何安排使吨公里数最小。，既能满足各炼钢厂的需要，又能表 1-42、用图解法解下列线性规划问题（1） min z = -x1 + 2x2x1 - x2 -2 x1 + 2x2 6 x1

6、 ， x2 0（3） max z = -x1 + 2x2x1 - x2 -2（2） max z = -x1 + 2x2x1 - x2 -2 x1 + 2x2 6 x1 ， x2 0（4） max z = 3x1 + 6x2x1 - x2 -2炼钢厂距离（公里）矿山B1B2B3B4A1 A3 A3163041503430324555402433考试点x1 + 2x2 6x1 ， x2 0x1 ， x2 0（5） max z = 3x1 + 6x2x1 - x2 -2 x1 + x2 -5 x1 ， x2 03、有两个变量的线性规划问题max z = x1x1 + x2 a-x1 + x2 -1

7、x1 0， x2 0（1） 证明本题当且仅当 a 1 时为可行（2） 应用图解法，对 a 1 的一切值，求线性规划以 a 表示的最优值。4、考虑标准线性规划问题max z = CXAX = bX 0设 x(1) 和 x(2) 是上述问题的两个最优解。求证向量解，l为 0 与 1 之间的任意值。5、用单纯形法求解以下问题(2 ) 是最优（1） max z = x1 + 32 x1 5x1 + 2x2 10x2 4x1 ， x2 0（3） max z =（2） min z = 3-2 33 + x43 = 44 =6x j 0， j =1，2，3，4（4） min z = -223 + 4x433

8、 + 2x4 203 + 2x4 203 303 -203 152x j 0， j =1，2，3，4最优解是否唯一，为什么？4x j 0， j =1，2，3，4（5）用单纯形法证明下列问题无最优解：max z = x1 + 2x2-23 2考试点-13x1 ， x2 ， x3 0（6） 应用大 M 法，证明下列线性规划为不可行：min z = 2x1 + 4x2 2x1 - 3x2 2-x1 + x2 3 x1 ， x2 0（7） 应用大 M 单纯法解：min z = 6x1 x2 x343050203 = 120x1 ， x2 ， x3 0单纯形法解：（8）用min z = 633 + x4

9、 303 - 2x4 03x1 ， x2 ， x3 ， x4 06、选择填空（1）若 LP 最优解不唯一，则在最优单纯表上（）。A、变量的检验数必有为零；B、变量的检验数不必有为零者。（2）极小化（ min z ）线性规划标准化为极大化问题后，原规划与的最优解（），目标函数值（）。A、相差一个负号B、相同C、没有确定的（3）大 M 法和两阶段法是用来（）的，当用两阶段法求解 LP 问题时，第一阶段建立的辅助 LP的目标函数为（）。D、 Z ' = -cZA、简化计算；E、进行灵敏度分析B、处理人工变量；C、人工变量之和；F、松弛变量、剩余变量和人工变量之和G、人工变量之和的相反数（4）

10、线性规划问题的A、目标要求是极小化； C、变量可以取任意值；最本质的特点是（）。B、变量和右端常数要求非负；D、约束条件一定是等式形式。考试点（5）求解线性规划模型时，人工变量是为了（）。A、使该模型B、确定一个初始的基可行解C、使该模型标准化可行解第二章对偶线性规划1、写出下列规划的对偶规划(1)min z = 3(2) max z = -253 + x4 - x53 - 3x4 63 + 2x5 = 73 + 2x4 + x5 5363s ×t-3-s ×t3x1 ， x2 ， x3 0x1 ， x2 ， x4 0； x3 ， x52、考虑线性规划max z =33 2

11、3 = 13 2s ×t2x1 0， x3 0， x2（1）写出本规划的对偶规划。（2）应用对偶理论，证明原规划的最大值 Z 不能超过 1。3、用对偶单纯形法求解下列线性规划（1） min z = 4x1 + x3 2（2） max z = -23 - 6x43 + x4 23 + 3x4 -33s ×tx2 + 2x3 5x1 ， x2 ， x3 0s ×t-2x j 0， j =1，2，3，44、求规划max z = -5-33 203 90s ×t12x j 0， j =1，2，3的最优解。并分别说明，下列变化对最优解有何影响。（1） 约束条件 1

12、）的右边常数由 20 变到 30；（2） 约束条件 2）的右边常数由 90 变到 70；（3） 目标函数中 x3 的系数由 13 变为 8；考试点é-1ùé0ù） x 的系数列向量由4（变为；êêúú1125ëëûû（5）增加约束条件（3）： 2第三章50。3问题及其求解1、砂石从 A1 , A2 L, A6 产地运往 B1 , B2 , B3 , B4 四个工地的交通路线图如图 1，求最优调运方案。A57B38A42B4A6B2A1A2A3B1图 12、根据交通图 2 种的

13、收量和发量，做出吨公里数最小的流向图（发量、收量：吨）B1A42B22BCA14B5A3D45A33A223BB35图 23、根据下列物资平衡表 1 及交通图 3，求出物资调运最优方案及最小吨公里数。表 1收点发点发量B1B2B3B4B5B6B7B8（吨）A145考试点 www.65155011867BA3411816520B570B624610B225252B3B4B7A4234664915358645753535AA6012图 3线路如下图4、设有一个钢筋调运平衡表 2，其公里数。表 2所示，试用图上作业法求最小吨20B2 30A201254013 B32图 45

14、、把钢筋从 A1 ， A2 ， A3 调运到 B1 ， B2 ， B3 ， B4 ， B5 平衡表和运价表如表 8 所示， 问怎样调运才使运费最少？6、令 f ( x ) 的系数矩阵为C = (cij ) = (i +条件为：j ) ， i =1，2，3； j =1，2，3，4，5。其约束3å xiji=1å x1 j j =15= j表 35= 3å x2 j= 2j =1 5å x3 j j =1xij 0= 10收点发点发量B1B2B3B4B5（吨）A1 A21064375165277收点发点B1B2B3发量A1 A22040收量(吨）133017

15、A2 A3 A4606535收量（吨）5010151520253535考试点依照上面的条件，求出其初始方案及最小费用。7、水泥厂调运的产销不平衡表及运价表如表 4 所示，求最小调运方案。表 4不平衡表及运价第四章整数规划1、用分枝界定法虬下列整数规划max z = 2x1 + x2x1 + x2 5-x1 + x2 0max z = x1 + x29（1）（2）£ 51x +x121414s ×t13s ×t-2x1 + x2 £+ 2x6x2112x1 ， x2 0，整数x1 ， x2 0，整数max z = 4max z = 40x1 + 90x29

16、x1 + 7x2 56（3）（4）33x1 + 2x2 10x1 + 4x2 11s ×t7x1 + 20x2 70x1 ， x2 0，整数s ×t33 1x1 ， x2 ， x3 0，整数2、用割平面法求下列整数规划（1）max z = 3x1 + 2x22x1 + 3x2 14max z = 7x1 + 9x2-x1 + 3x2 6（2）s ×t2x1 + x2 9x1 ， x2 0，整数s ×t7x1 + x2 35x1 ， x2 0，整数收点发点B1B2B3B4发量（吨）A1 A2 A321134103597812757收量（吨）23461915

17、A3543988收量(吨)2254720考试点max z = 103 -11x4max z = 3x23x1 + 2x2 7（3）（4）-12£15.53s ×tx1 - x2 -2193 - 2 x4 £ 4x ， x 0， x整数s ×t122x1 ， x2 ， x3 ， x4 0x1 ， x2 ， x3 整数3、解下列0 -1 规划max z = 23s ×t3 - 5x4 + 4x53 - 5x4 + 4x5 63 - 4x4 + 2x5 0（1）x j = 0 或 1， j = 1，2，5max z = 4（2）323 43 342x

18、2 + x3 1s ×tx1 ， x2 ， x3 且为 0 或 1（3） max z = -7-33 - 5x4 - 6x53 + 3x4 - 3x5 14 - 2x5 43 -1s ×tx1 ， x2 ， x5 且为 0 或 1max z = 33-(4)33 43 5s ×tx2 + x3 2 x1 + x3 3x1 ， x2 ， x3 且为 0 或 14、解下列指派问题考试点（1）五个电工组成一个维修组，规定每人负责厂区的 1/5，每个电工上班到工厂区的五个分区时间如表 4-20 所示，问怎样分派任务，才能使他们的上班需要的时间最少？表 4-20(2)有四个

19、工人去完成四项任务，每人完成各项任务所消耗的时间如表 4-21 所示，问指派哪个人去完成哪项任务可使总消耗时间最少？表 4-21（3）某公司希望建造五个小型工厂，现在有六个地方的地皮可以购置，供建厂用，已：），由表 4-22 给出，问应当怎样选厂才能使费用最小？表 4-22知不同地点的建厂费用（工厂地点abcdeA B CDE F181522252191110158121014161791010212014182626241419232025任务工人ABCD甲乙丙丁15182124192322182617161919212317上电班用 时工间厂分区abcdeA B CDE2124302029

20、2429273822322517262931393825383135212927考试点第五章 动态规划QLOB1、用动态规划求下面交通图由 A 到 B 的最短时间。PEIMCNJFADGK图 1注：各点之间的连线旁边数字，表示时间。2、设有三种机器，使用也分三个时期。第一个时期使用三种机器的耗费分别为 6，8，9；第二个时期使用三种机器的耗费分别为 10，12，8；第三个时期使用三种机器的耗费分别为 2，5，6。但是机器的使用不是任意的，只能按图的顺序使用。问题是如何安排机器使总耗费最小？（化为网络最短路问题求解）时期 1机器 1时期 2时期 3机器 2机器 3图 23、某工厂进行甲、乙、表

21、1丙三种新的试制，估计新的概率增加研制费这些新试制的概率分别为 0.6，0.4 和 0.3。由于工厂急于推出新，故厂方领导决定再拨 2制费，以期提高新的研研制的概率。据有关估计，把增加的研制费用于各种新试制时，试制概率如表 1 所示。试把这批研制费分配给各新试制项目（不分配，分配给 1或分配给 2），以使这三种新均研制成功的概率最大。（）甲乙丙0120.600.800.850.400.700.900.300.600.70考试点4、用动态规划表 2求max约束条件：f (2x1 £ 32x1 + 5x2 £ 15x1 , x2 ³ 05、某厂生产一种在未来四的销售量

22、估计如表 2 所示。该项，该的生1 月初产准备费用为每批 5 百元，每件的生产费用 1 元，每件的费用每月为 1 元。的存货为 1 百件。5 月初的存货为 0。试求该厂在四内的最优生产计划。6、现有一批资金，总额为 5拟投资于改造三个工厂。先对三个工厂拟订了几个不同的技术改造方案，其所需资金和投产后新增如表 3 所示。各工厂改造所需资金和投产后新增表 3问总投资额 5应如何分配使用，才能使三个工厂改造后的新增最大？7、用动态规划max f (约束条件：求+ 2x2233 = 103 ³ 0, 且为整数8、写出下列问题的动态规划的基本方程。nmax Z = åfi (xi )

23、i=1约束条件：nå xi= b,(b > 0)i=1xi ³ 0, (i = 1, 2,., n)投资（）各工厂改造投产后新增年值（）工厂 1工厂 2工厂 30123401.52.6001.3月 份销 售 量（百件）12344532考试点第六章 目标规划1、用图解法求解以下目标规划问题min Z = d -1x + d - - d + =x +1x1 +211x2 £x1 + 4x2 £ 48x , x , d -, d + ³ 0121min Z = p (d - + d + ), p (d - + d + + d

24、+ )1112223+12x + d - - d + = 7510x1211+ 2x + d - - d + = 10x1222+ x + d - - d + = 82x1233x , x ³ 0, d -, d + ³ 0, i = 1, 2, 31i2i2、用单纯形法求解目标规划min Z = p d -, p (d - + d + )1 12222x + 3x + d - - d + = 601211x + 2x + d - - d + = 2012220.5x1 + 0.25x2 £ 9x1 + x2 £ 22x , x ³ 0, d

25、-, d + ³ 0, i = 1, 212ii3、先列出下列各题的数模，然后求解 某家俱厂生产桌子椅子两种，售出桌子的利润 80 元，售出椅子利润40 元，该厂要求下周获利 640 元，两种各应销售多少？ 某车间计划生产 A、B 两种其所需工时定额如表 1，它们分别要经过粗和精两道工序的，在生产中不超过各工序的有效工时，车间决策者首先考虑两种的产量之和尽量超过 10kg；其次是B 可略微超过 7kg，再次希望A 不超过 8kg。表 1工序A（h/kg）B（h/kg）有效工时(h)粗精63246060考试点4、写出下列目标规划模型对偶形式min= Pd - + 5P d - + 3P

26、 d - + P d + + P d +f113 23 34 12 4+ d - - d + =x + x1x211+ d - =12+ d + =x23d + + d - - d += 10x , x , d -, d + ³ 0(i = 1, 2, 3, 4)ii5、在上题中，若增加约束条件+ 2x + d - - d + £ 90x1211试进行灵敏度分析。第七章论1、某工程队一条工厂铁路线，假设平均每天需要 8 根钢筋混忱轨，每根30 元。轨忱由预制厂运往工地需要动用预制厂的吊车，吊车是按台班收费，300 元一个台班，因此，工程队采用分批集中的办法向工地轨忱，但暂不

27、使用的必须积压资金，如果资金的月利（息）率为 7.2%，试问在不缺货的情况下，一年修成线所需的轨忱分几批、每批需用吊车几个台班为最理想？2、某每月用量 40 件，建立费。15 元，每月每件 8 元，试求批量和相应3、某公司根据投标情况，予计在一年之内需用门窗平板300 箱假设每箱价 200元，每箱每年的保管20 元，采购费平均每次 120 元，问几次采购最好？若缺货时，设缺货损失每箱每月 2 元，试求合理采购次数。4、某公司准备进口一台新型计算机，其中有一种零件构造复杂，因此需要和主机一起 购买一些这种零件以备后用、假设该种零件同主机一起购买时，单价为 2000 元，如果以后单独购买这种零件时

28、，加上停机的损失费可达 16000 元，今有如下表 1 统计资料供参考，问需买几个零件作备用？表 1购买备件数损坏第一列备件数的机器台数概率估计值112348584210.850.080.040.020.01考试点5 个以上00.005、某厂采购生产原料情况如下：采购（吨）单元）9992000 以上10080假设年需要量为 10000 吨，每次采购定货费用需 2000 元，原料每次的采购量。又知该厂的原料需求如表 2。为 20%，试求表 2需要量R(吨)8090100110120概 率P（r）0.30.1在每吨价格为 850 元，法，求合适的 S、s 值。每吨 45 元，缺货

29、损失每吨 1250 元的情况下，试用Ss6、某图书报刊零售点的电视报很畅销，根据已知的经验，每百份电视报可获得利 x 元， 如果销售不出去则赔y 元。每周销售的概率为已知，试求每次的电视报购入量。若x=1.5元，y=3.5元p(0)=0,p(1)=0.10,p(2)=0.10,p(3)=0.25p(4)=0.35,p(5)=0.15,p(6)=0.057、某工厂生产中，每年需要某种机器配件 5000 件，不缺货，每件价格为 20 元，每次订购费用 200 元，年度存费用为库存物资资金的 10%，试求：订购批量及最小平均总费用；如果每次订购费用为 10 元，每次订购多少为佳？最小平均总费用是多少

30、？若上题中缺货，求订购批量最小平均费用及最大缺货量，没缺货费用为 3 元/（件.月）。第八章对策论1、求下列矩阵对策-3 64-6ùé 9é 16 ù7（1） A = ê 5-7ú（2） A = ê-43-5úêêë-4é0ú-5úûêêë 0é3ú7 úû-21022ù120ù（3） A = ê21ú（4） A = ê13&#

31、250;êêë1ú0úûêêë2ú71úû考试点2、试求以下矩阵对策的最优策略和对策值（1） æ 0（2） æ 31 ö6 öç 1ç 24 ÷4 ÷èé2èé2øø0322ù31035ù（3） ê0（4） ê21ú7úêêë1êê

32、;ë0ú1úûú8úû3、用线性规划法求解下题-3ùé10ê-201-1-3é0êé2ê4132ùú21026ùú2 ú（3） êú4 ú（1） ê2（2） ê24ú2úê 3ê 5ê3ê81ú2úëë6 úûûë

33、51;4、从前齐王和他的大臣田忌约定，各处的上、中、下三马进行比赛，一马输者，付给对方 1 千金，赢者得 1 千金。已知田忌的上、中、下三马分别不如齐王的上、中、下三马跑的快，但田忌的中齐王的下马快，上齐王的中马好。试用矩阵对策求解齐王和田忌赛马的决策之最优策略。5、某市有两家超市相互竞争，超市 A 有三种广告策略，超市 B 也有三种广告策略，据表 1试将此对策问题表示为一线性规划模型。A，B 两人分别为 1 角、5 分和 1 分的硬币各一枚。在双方互不知道的情况下，各出一枚硬币，并规定当和为奇数时，A 赢得所出硬币；当和为偶数时，B 赢得所出硬币。试列出两人零和对策的模型，并说明该游戏对双方

34、是否公平合理。第九章 排队论1、某混搅拌站只有一套搅拌，一直平均每小时有 4 辆浇灌车来装搅拌混，并且每车混平均需要 6 分钟搅好装上车。浇灌车的到达次数服从泊松分布，服务时间服从负指数分布。试求：策 略B123A1233020202-14考试点（1）搅拌站空闲时间的概率；（2）站上有三辆车的概率；（3）站上至少有一辆车的概率；（4）在系统中的平均车辆；（5）在系统中的平均等待装车的车辆；（6）平均逗留时间；（7）车辆平均到达间隔时间；（8）平均等待时间。2、某工地修理部只有一个修理工人，来修理的顾客到达数服从泊松分布，平均每小时 5 人，修理时间服从负指数分布，平均需 8 分钟。试求修理部不

35、空闲的概率，修理部至少有一个顾客的概率，修理部顾客的平均数，在修 理部内平均逗留时间，必须在修理部内逗留 12 分钟以上的概率。3、某生，给公司自设卫生所。每小时到达该所看病的平均为 4 人，而所中仅一位医治病的速率平均为每小时 5 人。若到达过程为泊松过程。服务时间服从负指数分布。试计算平均在卫生所里等待看病及看病的人数，平均在卫生所里等待看病的人数，平均每位来看病的职工需消耗的时间，平均每位来看病的职工需消耗的等待看病时间，没有职工来看病的概率。4、设有两个售票亭，现考虑每分钟平均到达 6.4 人的最简单流，服务时间服从负指数分布，平均每分钟可服务 4 人。试均人数，顾客等候的平均时间。中

36、无人的概率，系统中的平均人数，排队等候的平5、某电信局准备在新建成的国际机场装设亭，而电信局的目标是每一个等候的概率不超过 0.10；使用的平均需求率为每小时 30 人，且为最简单流，使用的平均时间为 5 分钟，且为负指数分布。应该置多少个亭？6、设有两个修理工人，其责任是保证 5 台灵敏的机器能正常运行。每台机器平均损坏率为每小时一次，这两位工人能以相同的平均修复率 4 小时修理机器，求等待修理的机器平均数；机器在系统中的平均台逗留时间。7、设某间顾客按泊松流到达，平均每小时到达 6 人，每次通话时间平均为 8 分钟，方差为 16 分钟，通话时间服从爱分布。求平均等待长度；顾客的平均等待时间。8、某工程公司所属碎石场，其任务是将大石块轧碎成各种规格的碎石。碎石场的工艺过程是：在大石块堆积地（距轧石机水平距离 30 至 200 米），由小车装料用人工推至轧石机的料斗前，将块石装入料斗，开动卷扬机提升料斗，将料倾卸于斜面槽而置于料台，然后