运筹学讲义（考研）.doc

研究生入学考试辅导运筹学讲义1. 线线规划与单纯形法l 线性规划问题和数学模型；l 线性规划图解法l 线性规划解的概念和单纯形法l 单纯形法的一些具体问题2. 对偶理论与灵敏度分析l 线性规划问题的对偶及其变换；l 线性规划的对偶定理；l 对偶单纯形法；l 线性规划的灵敏度分析写出规划模型和标准化问题；指出解的类型；和对偶问题结合的题目；求解的问题；1. 某饲料厂用原料A、B、C加工成三种不同牌号的饲料甲、乙、丙。已知各种牌号饲料中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-1】所示。表1-1甲乙丙原料成本（元/千克）每月限制用量（千克）ABC60%20%15%60%10%50%2.001.501.00200025001200加工费（元/千克）0.500.400.30售价3.402.852.25问该厂每月应生产这三种牌号饲料各多少千克，使该厂获利最大？试建立这个问题的的线性规划的数学模型。2. 有如下线性规划问题，令X6,X7分别为约束条件（1）和（2）的松弛变量，指出下表各组解的类型（可行解、非可行解、基础可行解、基础非可行解）解X1X2X3X4X5X6X71200704000-109020000036072030024000-120040001601000051030105002205503. 设某投资者有30000元可供为期四年的投资。现有下列五项投资机会可供选择：A:在四年内，投资者可在每年年初投资，每年每元投资可获得0.2元，每年获利后可将本利重新投资；B：在四年内，投资者应在第一年年初或第三年年初投资，每年每元获利0.5元，两年后获利。然后再将本利投资；C：在四年内，投资者应在第一年年初投资，三年后每元获利0.8元。获利后可将本利重新投资，这项投资最多不超过20000元；D：在四年内，投资者应在第二年投资，两年后获利每元投资可获利0.6元，获利后可将本利和投资，这项投资最多不超过20000元；E：在四年内，投资者应在第一年投资，四年后获利每元1.7元，最大投资不超过20000元；求：四年后，投资获利最大？不求解。4. 某公司计划在三年的计划期内，有四个项目可以投资：项目一从第一年到第三年年初都可以投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目二需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目三需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额不得超过15万元；项目四需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样投资方案，才能使得该公司在这个计划期内获得最大利润？5. 将下列线性规划问题变换成标准型，并列出初始单纯形表。6. 求下面线性规划的最优解，并给出资源A和B的影子价格。7. 有一线性规划，原问题为目标函数为MAX型，有三个决策变量，其第一行约束为型，对应松弛变量为，其第二行约束为型，对应剩余变量为，其第三行约束为型，对应松弛变量为。用原单纯形求解得到最优单纯形表如下，问：CCB XB 10 5 1 0 0 0X1 X2 X3 X4 X5 X65 X2 51 X3 010 X1 00 1 0 1 0 -1/20 0 1 -1 -2 -11 0 0 0 1 1OBJ25, ZJ CJ-ZJ10 5 1 4 8 6.50 0 0 -4 -8 -6.5(1) 该问题最优解出现什么问题？(2) 求X1,X2,X3对应的原技术系数矩阵A？(3) 通过单纯形表直接给出对偶变量Y1,Y2,Y3的最优解？8. (1)完成下面的未完成的单纯形表CJ CBXB 20 8 6 0 0 0X1 X2 X3 X4 X5 X6 50/3 50/30 1/3 0 1 -8/3 -2/31 1/2 0 0 1/2 00 -2/3 1 0 -2/3 1/3OBJ25, ZJ CJ-ZJ20 6 0 6 20 0 0 -6 -2(2) 若上表中X4 ，X5， X6为松弛变量，请写出当前基的逆矩阵和对应的基变量。9. 有一线性规划，原问题为目标函数为MAX型，有三个决策变量，其第一行约束为型，对应松弛变量为，其第二行约束为型，对应剩余变量为，其第三行约束为型，对应松弛变量为。用原单纯形求解得到最优单纯形表如下，问：CCB XB 10 5 1 0 0 0X1 X2 X3 X4 X5 X65 X2 51 X3 010 X1 00 1 0 1 0 -1/20 0 1 -1 -2 -11 0 0 0 1 1OBJ25, ZJ CJ-ZJ10 5 1 4 8 6.50 0 0 -4 -8 -6.5（） C2的灵敏度范围；（）10. 下表是一线性规划最优解的单纯形表Cj 2194000CBXBbx1x2x3x4x5x621x14101/32/301/30x5200-2/3-4/311/39x223011/3-1/30-2/3zj219101101cj - zj00-6-110-1原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题：（） 资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量)（） 求C1, C2 和C3的灵敏度范围；（） 求Db1，Db2的灵敏度范围。11. 用原单纯形求解下面的线性规划，并讨论其对偶规划的解。12. 写出下列线性规划问题的对偶问题：13. 写出下列线性规划问题的对偶问题：14. 下表是某求极大化线性规划问题计算得到单纯形表。表中无人工变量，a1, a2, a3, d, c1, c2为待定常数。试说明这些常数分别取何值时，以下结论成立。1) 表中解为唯一最优解；2) 表中解为最优解，但存在无穷多最优解；3) 该线性规划问题具有无界解；4) 表中解非最优，为对解进行改进，换入变量为x1，换出变量为x6。基bx1x2x3x4x5x6x3x4x6d2341a3a135100010a214001c1c2003015. 考虑下列问题（） 建立此问题的对偶问题，然后以观察法求出其最优解。（） 使用主对偶原理及对偶问题的最优解求出原问题的最优解目标函数值。（） 假设原问题中x1的系数为c1（c1可为任意实数）。当c1为何值时，此对偶问题无可行解？对这些值而言，原问题的解有什么意义？16. 写出下问题的对偶问题，解对偶问题，并证明原问题无可行解17. 某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下：表1-8 产品 项目ABCD单位产值 (元)1681401050406单位成本 (元)4228350140单位纺纱用时 (h)32104单位织带用时 (h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h。（） 列出线性规划模型，以便确定产品的数量使总利润最大；（） 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？18. 求下列问题的对偶问题1)2)3. 运输问题l 运输问题的数学模型的特点及其求解；l 运输问题迭代计算中的具体问题19. 在运输问题中，采用位势法获取检验数。设uij（i1,2,3,m）为运输问题产地约束对应的对偶变量，vj（j1,2,3m）为销地约束的对偶变量，wij为产地到销地j的单位运费。（） 请给出理论上的解释：为什么说，当存在uivjwij时，运输问题当前解不是最优解；（） 用西北角法求解运输问题的初始解，从该初始解出发求最佳运输方案，并讨论问题的解？20. 求解下表给出的运输问题的最优解，初始解必须用西北角法求出。W1W2W3AiA13319215A220283210A319303415Bj5101721. 求解下表给出的运输问题的最优解，初始解必须用最小元素法求出。W1W2W3AiA159215A231718A362817Bj1812164. 整数规划l 整数规划问题数学模型的特点及其求解思路；l 任务分配问题及其求解方法22. 有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h)如下表，问如何分派工作，使总的消耗时间最少？23. 下表给出了使用各台设备完成各种工作的生产费用。试确定最优的指派方案，使总的生产费用最低。 24. 用匈牙利算法求解下述任务分配问题。1)2)3)4)25. 学生A，B，C，D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。据竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，应如何指派最有利？表3-2 课程学生数学物理化学外语A89926881B87886578C95908572D7578899626. 下表给出了使用各台设备完成各种工作的生产费用。试确定最优的指派方案，使总的生产费用最低。表3-3 工作设备甲乙丙丁A25293142B22193518C39382620D34372840E2442362327. 某设备公司有三台设备可以租给A，B，C和D四项工程使用，各台设备用于各工程创造的利润如下表所示，问怎样分配设备才能使创造的总利润最大？表3-4 工程设备ABCDM141085M2982M31237428. 已知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。表3-5 赵钱孙李周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.129. 现在有五项任务让甲、乙、丙、丁四个人去完成。其中一个人要完成两项任务，每人完成各项任务的时间如下表所示。试确定总的花费时间为最少的分配方案。表3-6 工作工人ABCDE甲2529314237乙3938262033丙3427284032丁244236234530. 从甲、乙、丙、丁、戊五个人中挑选四个人去完成四项工作。已知每人完成各项工作的时间如下表所示。规定每项工作只能有一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第四项任务，在满足上述条件下，如何分配工作，使完成四项工作的总的花费时间为最少。表3-7工人工作甲乙丙丁戊110231592510152431551471542015136831. 6个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需要1人操作，试求使总收益最大的指派方案？表3-8 工人工作ABCDEF136810121325791011123468910114581011121332. 有四项工作要交给甲、乙、丙、丁四个人去完成，以致每个人完成各项工作的时间如下表所示，问应该怎样指派才能使总的消耗时间为最少。表3-9 工作工人ABCD甲15182124乙19232218丙26171619丁192123175. 动态规划l 动态规划模型的最优性原理及其算法基本思路；l 离散型动态规划模型特点及其求解；l 连续型动态规划模型特点及其求解33. 有给定厚度的金属板材28cm2，通过裁剪可焊接成如图的封闭的长方体。设该长方体可承受的压力F与图中三个面的面积X1，X2, X3有如下关系： x1 X3 x2求最优的裁剪方案使F最大。（） 建立该问题的数学模型（） 用连续型的动态规划方法求最优方案34. 请严格地采用动态规划的方法和步骤求解下述非线性规划35. 用动态规划求解下题动态规划36. 用动态规划求解37. 用动态规划求解下面非线性规划问题38. 用动态规划求解下面非线性规划问题。39. 设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12-x1)和(13-2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。(要求用连续变量的动态规划方法求解)40. 如果原料总数量为10，用于生产3种产品。3种产品的营业利润分别为g1（x1）4x12 ， g2（x2）x22，g3（x3）2x3212，其中生产第2种产品实际上不盈利。问应该如何生产，才能使总收入最大？41. 一个设备由三个元件串联，其可靠性可由每种元件上装得并联得备用元件来改进。设总投资为10，对第i中（i1, 2, 3）元件配个并联单件（1, 2, 3）后得可靠性与成本的数据如表所示，求在投资范围内得总可靠性达到最高。42. 某工厂共有5单位的资源供给3个车间，由于各车间的设备条件不同，使用资源获得的收益的情况也不同，具体数据如表所示，为使工厂获得收益最大，每个车间应分配的资源数为多少？43. 设某厂生产A、B两种产品，由于条件限制，这两种产品日产量分别为x1和x2，日生产成本为；，两产品的销售单价分别为10元和5元，工时消耗定额均为1小时每件，若每天工作不超过8小时，求产品A、B每天各应生产多少小时才能使总利润最大？44. 某厂新购某种新机床125台。据估计，该设备5年后将被其他心设备所代替，此机床如在高负荷下工作，年损坏率为1/2，年利润为10万元，如在低负荷下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产，才能使5年内获得的利润最大？45. 某公司将在一个竞争激烈的市场推出一种新产品。该公司已经决定分三个阶段进行营销策略。第一阶段以低价向大家推销，以吸引初买者；第二阶段大举从事广告，以促使初买者以正常价格购买该产品，约于第二阶段末期另一公司将推出一种竞争性新产品，故在第三阶段从事加强性广告策略，以使购买者不转而购买竞争对手的产品。该公司已经拨出四百万元的预算用于此项活动。现求如何在这三个阶段分配款项使该产品获得最大的市场占有率。令m表示第一阶段达成的最初市场占有率，f2、f3分别为第二、三阶段策略对市场占有率的影响，也即求得m f2f3最大。1) 假定该款项以一百万元的整数倍用于每一阶段，表示各阶段的支出效果。2) 假定在四百万元预算额度内各阶段支出额可以为任意实数，而在阶段k (k1, 2, 3)支出xk百万元的支出效果为：46. 某厂生产一种产品，以后四个月的订单如表所示。合同规定在月底前缴获，生产每批产品的固定成本为3千元，每批生长的产品件数不限。每件产品的可变成本为1千元，每批产品的最大生产能力是5件。产品每级每月的存储费为0.5千元。设1月初又库存产品1件，4月底不再留下产品。试求在满足需求的前提下，如何组织生产才能使总的成本费用最低。月 份1月2月3月4月订货量bk（个）332447. 某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。推销员市场01234567891203247576671829010011024050607182931041151251353506172849710912013114015048. 用动态规划的方法求点A到点H的最短路径和最短路长，路径上的数字表示两点之间的距离。AEFCDCBH101262243546736. 图与网络分析l 图和网络的基本概念；l 树图和最小生成树；l 最短路径问题的求解；l 网络最大流、最小截集的求解49. 已知9个人v1，v2，v9，其中v1与两个人握过手，v2，v3各与4个人握过手，v4，v5，v6，v7各与5个人握过手， v8，v9各与6个人握过手，证明：9个人中至少有3个人相互握过手。50. 某软件公司生产4种系统的软件，每种软件的型号、计算速度、需求量及生产一件的可变费用（元/件）如下表所示。不同规格的软件生产时需调整设备，其固定费用为2000万元。当某种软件不能满足需求时，可用更新型号的软件替代。问在满足需求的情况下如何组织生产，使总费用最小。软件型号ABCD计算速度（次/秒）15000250004000060000需求量（万件）1000120027001800可变费用（元/件）4561051. 运输公司接到任务需将产地P1，P2两地所产的物质经S1，S2，S3三个中转站运往用户U1，U2两处；公司所获利润与运输总量成正比。已知P1，P2有物资分别为120吨和240吨，U1，U2各需180吨和200吨，全部交通网络布置与交通干线容量见下图6-4-4，问：运输公司应如何制定运输方案？52. 某公司有3套设备，拟分配给下属三个工厂。已知各个工厂得到不同数量设备后的利润如表所列。试用动态规划求解最大投资方案。设备数工厂0123甲25414860乙30425060丙3464687853. 用标号法求下图S到t的最短路径1S643t52108920301584722754. 用标号法求下图S到t的最大流S643t52688109108475655. 如下图S到t点间可进行邮政运输的公路网，弧旁边的数字为两点间的距离。为了保证在某些道路出险故障和拥塞时，仍能尽量及时将邮件运出，要求在S和t点间规划至少2条路由，试给出你的规划。S532t41442462103533656. 如图，在给定的初始流（Cij，fij）下，求该网络的最大流和最小截集。（10，10）S523t41（13，11）（6，4）（5，5）（3，1）（8，4）（10，6）（6，5）（4，4）（6，6）（3，0）57. （2003年第9题）；如右边的网络图（每边上标的是流量），我们希望简化该网络结构（即删去一些流量小的边），一般可采用限界值法，即给定一个值，若，则删去边。显然，大到一定程度就会使网络不连通。（1）采用系统的算法求使网络保持连同的最大界限制（采用试凑法或琼剧发不给分，即你的算法可以适用于很大的网络）（2）证明你的算法满足题目的要求。58. （2004年第8题）从现有的可行流开始进行标记，下图中边上所标为（支路容量，支路流量），求如下图网路的最大流及最小截集523417458466359. （2006年第5题）要将物品从始点S通过如下网络（图中边上标记的是距离）运到终点T，现有两种收费方案可供选择：方案1，单位距离运费C1=3；方案2，单位距离运费C2=2，但是在终点T收取附加费，请问应该如何选择运输方案？S523T411153427623547. 随机服务理论概述l 随机服务系统的基本组成；l 负指数分布定义和特点；l 泊松输入定义和特点；l 生灭过程的概念及其稳态解60. 某计算中心信息交换站接受到的信息流为泊松流，每秒钟到达15份信息，信息从交换站输出服从负指数分布，平均每秒处理完信息20份，但每次仅处理一份信息，试求(1)若缓冲器的存储空间仅可存储4份信息，则平稳时的概率分布、信息损失率、及相应的排队参数各为何？ (2)若要求平稳时任何时刻缓冲器充满的概率不大于0.001，问缓冲器应设置多大？61. 某自动交换台有4条外线，打外线的呼叫为泊松流，强度为2次/分钟，通话时长服从负指数分布，平均通话时长为2分钟。当4条外线全忙时，用户呼叫接预忙音。假设用户遇忙音后立即停止呼叫。问：i. 用户拨外线遇忙音的概率为多大？ii. 损失的话务量为多大？iii. 外线的利用率为多少？iv. 过负荷为100时，外线的利用率为多少？62. （2003年第10题；）某排队系统的稳态转移图如下图，试推导该系统的稳态概率。2010.5l0.5lmmba63. （2005年第10题；）某车间及其故障率5台/小时，为一泊松流。车间现有一名机修工，平均每10分钟可修复一台机器，修理时长为负指数分布，机器的停工损失为10元/小时。若增加一名同样水平的机修工，可将修复一台机器的平均时间缩短到8分钟，问：（1）求车间有一名和二名机修工时分别的工时利用率。（2）只有一名机修工时，一台机器停工损失费超过10元的概率为多少？（3）机修工每日报酬为多少时增加一名才是合算的（每日工作8小时）？提示：可能用到下面某些公式：，64. （2006年第7题）有一个M/M/N：等待制排队系统，增加一名服务员的单位时间成本为C1=5，每个顾客单位时间的逗留成本为C2=25，求系统稳态时使总成本最小所需要配置的服务员数。提示：为了较少运算时间，现给出该系统的平均等待是队长的部分数据43295065601970068. 生灭服务系统l M/M/n 损失制系统特点及其计算；l M/M/n 等待制系统特点及其计算65. 某电话亭有一部电话，来打电话的顾客数服从泊松分布，相继两个人到达的平均时间为10min，通话时间服从指数分布，平均数为3min，求（1）顾客到达电话亭要等待的概率；（2）等待打电话的平均顾客数；（3）当一个顾客至少要等3min才能打电话时，电信局打算增设一部电话机，问到达速度增加到多少时，装第二台电话机才是合理的；（4）打一次电话要等10min以上的概率是多少；（5）第二台电话机安装后，顾客平均等待时间是多长。 66. 某售票点有两个售票窗口，顾客总到达流是参数为=8人/min的泊松过程，每个窗口售票时间均服从负指数分布，平均服务速度为5人/min。试比较以下两种排队方案的运行指标：a.顾客到达后，按泊松流分解为两个M/M/排队系统，每一单服务系统的到达速率1=/2=4人/min；b.顾客以=8人/min到达后，按先来先服务规则排队等待，当待服务顾客发现哪个窗口空闲时，就接受该服务台的服务。67. 某博物馆有4个大小一致的展厅。来到该博物馆参观的游客服从泊松分布，平均每小时96人。观众大致平均分散于各个展厅，且在各展厅停留时间服从1/=15min的负指数分布，在参观完4个展厅后离去。问该博物馆的每个展厅应按多大容量设计，使在任何时间内观众超员的概率小雨5%。68. （2005年第8题；）设一损失制的随即服务系统，有N个并联的服务台，有两类顾客以独立的泊松过程到达，到达率分别为 ，服务时长都服从参数为的负指数分布；N个服务台保留M个为第一类顾客服务，即空闲服务台数小于等于M时则拒绝第二类顾客进入，而使得第二类顾客损失。试画出系统稳定状态的状态转移图，并推导出两种顾客（按时间计算）的损失概率公