运筹学习题答案.doc

《运筹学习题答案.doc》由会员分享，可在线阅读，更多相关《运筹学习题答案.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流运筹学习题答案.精品文档.第一章 习题1. 思考题（1）微分学求极值的方法为什么不适用于线性规划的求解？（2）线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？（3）图解法主要步骤是什么？从中可以看出线性规划最优解有那些特点？（4）什么是线性规划的可行解，基本解，基可行解？引入基本解和基可行解有什么作用？（5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来？什么是检验数？它有什么作用？如何计算检验数？（6）确定换出变量的法则是什么？违背这一法则，会发生什么问题？（7）如何进行换基迭代运算？（8）大M法与两阶段法的要点是什

2、么？两者有什么共同点？有什么区别？（9）松弛变量与人工变量有什么区别？试从定义和处理方式两方面分析。（10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解？为什么？2. 建立下列问题的线性规划模型：（1）某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表1-18所示：表1-18产品ABC资源数量原料单耗机时单耗22.5335620002600利润101420另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型。（2）某公司打算利用具有下列成分（见表1-19）的合金配制一种新型合金100公斤，新合金含铅，锌，锡的比例为3：2：5。表1-19合金品

3、种12345含铅%含锌%含锡%306010102070502030101080501040单价（元/kg）8.56.08.95.78.8如何安排配方，使成本最低？（3）某医院每天各时间段至少需要配备护理人员数量见表1-20。表1-20班次时间最少人数1234566:0010:0010:0014:0014:0018:0018:0022:0022:002:002:006:00607060502030假定每人上班后连续工作8小时，试建立使总人数最少的计划安排模型。能否利用初等数学的视察法，求出它的最优解？（4）某工地需要30套三角架，其结构尺寸如图1-6所示。仓库现有长6.5米的钢材。如何下料，使消

4、耗的钢材最少？331.41.41.7图1-63. 用图解法求下列线性规划的最优解：4. 把下列线性规划化为标准形式：5. 判定下列集合是否凸集：（1）R1=(x1,x2)|x12+2x222（2）R2=(x1,x2)|x122x2+30,x20,|x1|1（3）R3=(x1,x2)|x1x21,x11,x206. 求出下列线性规划的所有基本解，并指出其中的基可行解和最优解。7. 求下列线性规划的解：（1）（2）（3）（4）8. 利用大M法或两阶段法求解下列线性规划：（1）（2）（3）（4）9. 对于问题（1）设最优解为X*，当C改为时，最优解为，则。（2）如果X1，X2均为最优解，则对于0，1

5、，X1+（1）X2均为最优解。10. 用单纯形法求解问题2（4）（合理下料问题）。11. 表1-21是一个求极大值线性规划的单纯形表，其中x4，x5，x6是松弛变量。表1-21cj22CBXBbx1x2x3x4x5x62x5x2x12141-12a21-1-1-2-a+8j-1（1）把表中缺少的项目填上适当的数或式子。（2）要使上表成为最优表，a应满足什么条件？（3）何时有无穷多最优解？（4）何时无最优解？（5）何时应以x3替换x1？第二章习题1. 思考题（1）如何在以B为基的单纯形表中，找出B1？该表是怎样由初始表得到的？（2）对偶问题的构成要素之间，有哪些对应规律？（3）如何从原问题最优表

6、中，直接找到对偶最优解？（4）叙述互补松弛定理及其经济意义。（5）什么是资源的影子价格？它在经济管理中有什么作用？（6）对偶单纯形法有哪些操作要点？它与单纯形法有哪些相同，哪些地方有区别？（7）灵敏度分析主要讨论什么问题？分析的基本思路是什么？四种基本情况的分析要点是什么？2. 已知某线性规划的初始单纯形表和最终单纯形表如表2-21，请把表中空白处的数字填上，并指出最优基B及B1。表2-21cj2-11000CBXBbx1x2x3x4x5x6000x4x5x63111-1112-1100010001j2-1100002-1x4x1x210155-11/2-1/2-21/21/2j3. 某个线性

7、规划的最终表是表2-22：表2-22cj01-200CBXBbx1x2x3x4x501-2x1x2x313/25/21/2100010001-1/2-1/2-1/25/23/21/2j000-1/2-1/2初始基变量是x1，x4，x5。（1）求最优基B=（P1，P2，P3）；（2）求初始表。4. 写出下列线性规划的对偶问题：5. 已知线性规划（1）写出它的对偶问题；（2）引入松弛变量，化为标准形式，再写出对偶问题；（3）引入人工变量，把问题化为等价模型：再写出它的对偶问题。试说明上面三个对偶问题是完全一致的。由此，可以得出什么样的一般结论？6. 利用对偶理论说明下列线性规划无最优解：7. 已知

8、表2-23是某线性规划的最优表，其中x4，x5为松弛变量，两个约束条件为型。表2-23cjCBXBbx1x2x3x4x5x3x15/23/2011/2-1/2101/2-1/601/3j0-40-4-2（1）求价值系数cj和原线性规划；（2）写出原问题的对偶问题；（3）由表2-23求对偶最优解。8. 已知线性规划问题（1）写出对偶问题；（2）已知原问题的最优解为X*=（1，1，2，0）T，求对偶问题的最优解。9*. 已知线性规划的最优解为X*=（0，0，4）T。（1）写出对偶问题；（2）求对偶问题最优解。10. 用对偶单纯形法解下列各线性规划：11. 设线性规划问题（2.41）的m种资源的影子

9、价格为y1*，y2*，ym*。线性规划（2.42）与（2.41）是等价的，两者有相同的最优解，请说明（2.42）的m种资源的影子价格为（y1*/，y2*，ym*），并指出这一结果的经济意义。12*. 已知线性规划（1）写出对偶问题，用图解法求最优解；（2）利用对偶原理求原问题最优解。13. 线性规划的最优单纯形表如表2-24所示。表2-24cj2-1100CBXBbx1x2x3x4x520x1x56101013111101j0-3-1-20（1）x2的系数c2在何范围内变化，最优解不变？若c2=3，求新的最优解；（2）b1在何范围内变化，最优基不变？如b1=3，求新的最优解；（3）增加新约束

10、x1+2x32，求新的最优解；（4）增加新变量x6，其系数列向量P6=，价值系数c6=1，求新的最优解。14. 某厂生产甲、乙、丙三种产品，有关资料如表2-25所示。表2-25产品消耗定额原料甲乙丙原料数量AB6334554530产品价格415（1）建立使总产值最大的线性规划模型；（2）求最优解，并指出原料A，B的影子价格；（3）产品甲的价格在什么范围内变化，最优解不变？（4）若有一种新产品，其原料消耗定额为：A为3单位，B为2单位，价格为2.5单位，求新的最优计划。；（5）已知原料B的市场价为0.5单位，可以随时购买，而原料A市场无货。问该厂是否应购买B，购进多少为宜？新的最优计划是什么？（

11、6）由于某种原因，该厂决定暂停甲产品的生产，试重新制定最优生产计划。15*. 分析下列参数规划中，当t变化时，最优解的变化情况。16. 在例14中，原料甲的影子价格为5元/kg，补充20000kg后，产值z*似乎应增加520000=100000（元）；但实际上只增加了88000元。试解释这个“矛盾”现象。第三章 习 题1表335和表336分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。表 335销地 产地B1B2B3B4产量A1A2A3359637267648557075销量40455560200表3-36 销地 产地B1B2B3B4产量A1A2A3

12、978523674768302545销量202025351002试求表3-37给出的产销不平衡运输问题的最优解。表3-37 销地 产地B1B2B3B4产量A1 A2 A32 10 711 3 83 5 14 9 27 5 7销量23463如表3-38所示的运输问题中，若产地I有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为5，4和3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。表338销地 产地ABC产量1 2 31 1 22 4 32 5 320 40 30销量3020204某公司有A1,A2,A3三个分厂已

13、分别制造生产了同一产品3500件，2500件，5000件。在公司生产前已有B1,B2,B3,B4四个客户分别订货1500件，2000件，3000件，3500件。客户B1,B2在了解到公司完成订货任务后，产品有1000件剩余，因此都想增加订货购买剩余的1000件产品。公司卖给客户的产品利润（元/件）见表3-39。公司如何安排供应才能使总利润最大。表3-39客户 产地B1B2B3B4A1 A2 A310 8 95 2 36 7 47 6 85某电站设备制造厂根据合同要从当年起连续三年末各提供三种规格型号相同的大型电站设备。已知该厂这三年内生产大型电站设备的能力及每套电站设备成本如表3-40所示。表

14、3-40年度正常生产时间内可完成的电站设备数加班生产时间内可完成的电站设备数正常生产时每套成本（万元）123500242600313550已知加班生产时，每套电站设备成本比正常生产时高出70万元，又知造出来的电站设备如当年不交货，每套每积压一年造成积压孙视为40万元。在签订合同时，该厂已积压了两套未交货的电站设备，而该厂希望在第三年末完成合同后还能储存一套备用。问该厂如何安排每年电站设备的生产量，使在满足上述各项要求的情况下，总的生产费用为最少？第四章 习 题1.已知条件如表所示工序型号每周最大加工能力AB（小时/台）（小时/台）436215070利润（元/台）300450如果工厂经营目标的期

15、望值和优先等级如下：p1: 每周总利润不得低于10000元；p2: 因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；p3: 希望工序的每周生产时间正好为150小时，工序的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。2.在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。3.用图解法解下列目标规划模型。4.用目标规划的单纯形方法解以下目标规划模型。5.给定目标规划问题：（a）求该目标规划问题的满意解；（b）若约束右端项增加b=(

16、0，0，5)T，问满意解如何变化？（c）若目标函数变为，则满意解如何变化？（d）若第二个约束右端项改为45，则满意解如何变化？6.某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。该厂在制定生产计划时有以下各级目标：p1：每周必须用足80小时的生产时间；p2：每周加班时数不超过10小时；p3：每周销售窗帘布70000米，衣料布45000米；p4：加班时间尽可能减少。试建立这个问题的目标规划模型。第五章 习 题

17、5.1某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为，相应的钻井费用为，并且井位选择上要满足下列限制条件：或选择和，或选择钻探；选择了或就不能选，或反过来也一样；在中最多只能选两个；试建立这个问题的整数规划模型。5.2某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表52所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。表512备选校址代号覆盖的居民小区编号A1，5，7B1，2，5C1，3，5D2，4，5E3，6，F4，6，5.3一货船，有效载重量为24吨，可运输货物重量及运费收入如表5-

18、13所示，现货物2、4中优先运2，货物1、5不能混装，试建立运费收入最多的运输方案。表5-13货物123456重量（吨）59871023收入（万元）1443575.4 用分支定界法求解下列整数规划问题（1） （2）5.5用割平面法求解下列整数规划问题（1） （2）5.6用隐枚举法解下列01规划问题（1） （2）5.7用匈牙利法求解下列指派问题，已知效率矩阵分别如下：5.8已知下列五名运动员各种泳姿的运动成绩（各为50米）如表5-14所示，请问如何从中选择一个参加200米混合泳的接力队，使预期比赛成绩最好。表5-14 单位：秒赵钱张王周仰 泳37.732.933.837.035.4蛙 泳43.4

19、33.142.234.741.8蝶 泳33.328.538.930.433.6自由泳29.226.429.628.531.15.9分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-15所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。表5-15人 任务ABCDE甲2529314237乙3938262033丙3427284032丁24423623455.10 从甲、乙、丙、丁、戊五个人中挑选四人完成四项工作。已知每人完成各项工作的时间如表5-16所示。规定每项工作只能由一个人单独去完成，每个人最多承担一项任务。

20、又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务，在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。表516工作 人甲乙丙丁戊11023159251015243155147154201513685.11 运筹学中著名的旅行商贩（货朗担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序旅行，使总的旅程最短。试对此问题建立整数规划模型。第七章 习题1. 求下列网络图从起点到终点的最短路线及长度。7010604030C2（1）

21、3040D210C1C33020D16020B3B2A40304010E304050301012510（2）4694G3G2F3F23102133E3E2A875815778CD7862. 用动态规划方法求解下列问题：3. 某公司拟投资600万元对下属四个工厂进行技术改造，各工厂改造后的利润与投资额大小关系如表7-22所示，要求确定各厂投资额，使总利润最大。表7-22工厂投资额工厂1工厂2工厂3工厂4012345604010013016017017004080100110120130050120170200220230050801001201301404. 有一部货车沿公路的4个零售店共卸下6

22、箱货物，各零售店因出售货物所得利润如表7-23所示。试求在各零售店各卸下几箱货物，能使获得的总利润最大？最大利润是多少？表7-23零售店箱数12340123456046777702468910035788804566665. 设某机器可在高、低不同负荷下生产。若机器在高负荷下生产，则产品的年产量a和投入生产的机器数量x的关系为a=8x，机器的年折损率=0.3，若机器在低负荷下生产，则产品年产量b和投入生产的机器数量x的关系为b=5x，机器的年折损率=0.1。设开始时有完好机器1000台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年总产量达到最大。6. 某厂生产一种产品，该

23、产品在未来4个月的销售量估计如表7-24所示。该产品的生产准备费为每批500元，每件的生产费用为1元，每件的存贮费为每月1元，假定1月初的存货为100件，5月初的存货为0，求该厂在这4个月内的最优生产计划。表7-24月份1234销售量（百件）45327. 设有一个外贸公司计划在1至4月份从事某种商品的经营。已知它的仓库最多可存储1000件这种商品，该公司开业时有存货500件，根据预测，该种商品从1至4月份进价和售价如表7-25所示。问如何安排进货量和销售量，使该公司获得最大利润（假设四月底库存为零）。表7-25月份1234进价（百元/件）1091115售价（百元/件）12913178. 某人外

24、出旅游，需将5种物品装入包裹，包裹容量有限，总重量不能超过13公斤，物品的单件重量及价值如表7-26所示。试问如何装这些物品使总价值最大？表7-26物品ABCDE单件重量（kg）75431单件价值（元）94320.59. 某厂设计一种电子设备，由三种元件D1，D2，D3组成，已知这三种元件的价格和可靠性如表7-27所示。要求在设计中所使用元件的费用不超过105元，试问应如何设计使设备的可靠性达到最大（不考虑重量的限制）。表7-27元件单价（元）可靠性D1D2D33015200.90.80.5第八章 习 题1. 用破圈法和避圈法求下图的最小生成树7V1V2V3V4V5V6V7V8V9121311

25、91921571011874图828162.求下列各图的最小生成树（2）1（1）（3）图8293写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。V1V2V3V4V5V6(1)V1V2V3V4V5(2)图8304用标号法求图830中从到各顶点的最短距离V1V2V3V4V5V6V7V8V9V10V112635752137234143167384图8315已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。各村镇间距离 （单位：千米） 到从234567811

26、.52.51.02.02.53.51.521.02.01.03.02.51.832.52.02.52.01.042.51.51.51.053.01.81.560.81.070.56用标号法求下面网络的最大流.1215V1Vt81061084910141812813156图832V1Vt4453342535823图8337求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.V1Vt(6,6)(10,5)(5,1)(2,3)(7,4)(8,2)(1)V1Vt(5,6)(9,2)(3,2)(4,1)(3,4)(4,19)(2,3)(1,1)(2)图834A243

27、332422244255222图8358.求解图835中所示的中国邮递员问题（A点是邮局所在地）9如图835，发点S1，S2分别可供应10和15个单位，收点T1和T2可接收10个和25个单位，求最大流，边上的数为。23S1S2v1v2T1T232446786图836第九章 习 题9.1 指出图934中所示网络图的错误，若能够改正，试予以改正。12536（a）abcedf72851364（b）abcdefg35124图934（c）abcdefg9.2 根据表910，表911，所示的作业明细表，绘制网络图。 表910 表911工序紧前工序工序紧前工序 abcdefghacdd , b f ,g ,

28、eabcdefgha a a , bccd , e , f213456abcdefg43453610图9459.3 已知图945所示的网络图，计算各事项的最早与最迟时间。9.4 试画出表912、表913的网络图，并为事项编号。表912工序工时（d）紧前工序工序工时（d）紧前工序ABCDE151010105A，BA，BBFGHI5201015D，EC，FD，EG，H表913工序工时（d）紧前工序工序工时（d）紧前工序ABCDEF325478ABCGHIJKL624526D，BEG，HE，FE，FI，J9.5 已知表914所列资料工序紧前工序工序时间（周）工序紧前工序工序时间（周）工序紧前工序工序

29、时间（周）ABCDAL3443EFGHBHC，BG，M4522IKLMH，LF，I，EB，CB2676要求：（1）绘制网络图；（2）计算各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差，并指出关键工序。（3）若要求工程完工时间缩短2天，缩短哪些工序时间为宜。1012151811111234657108910151020142519567151825图9369.6 设有如图936的网络图，计算时间参数，并求出关键路线。9.7如图937所示的网络图，计算各事项的最早时间和最迟时间，各工序的最早开始、最早结束、最迟开始及最迟结束时间，计算各工序的总时差和单时差，找出关键路线。2147925

30、736383473482175图9379.8某项工程各工序的工序时间及所需人数如表915所示，现有人数为10人，试确定工程完工时间最短的各工序的进度计划。表915工序代号紧前工序工序时间（天）需要人员数ABCDEFGHBCF，DE，G42223234936487219.9已知下列网络图有关数据如表916，设间接费用为15元天，求最低成本日程。表916工序代号正常时间特急时间工时（天）费用（元）工时（天）费用（元）693078214510020080015025012010018013045205311321202801100180375170100200220 9.10生产某种产品，生产过程所

31、经过的工序及作业时间如表917所示，作业时间按常数和均值计算，试绘制这一问题的随机网络图，并假设生产过程经过工序G 即为正品，试计算产品的成品率与产品完成的平均时间。表917工序概率作业时间（常数或期望值）（h）紧后工序ABCDEFG10.70.70.310.3125643462B或FC或DGECG第十一章 习 题1. 某单位每年使用某种零件10万件，每件每年的保管费为3元，每次订购费为60元，试求（1）经济订购批量；（2）每次订购费为0.6元时，每次应订购多少件？2. 企业生产某种产品，正常条件下每天可生产10件。根据合同要求，需按每天7件供货，存贮费每件每天0.13元，缺货费每件每天0.5

32、元，每次生产准备费用为80元，求最优存贮策略。3. 设某工厂生产某种零件，每年需要量为18000个，该厂每月可生产3000个，每次生产的装配费为500元，每个零件的存贮费为0.15元，求每次生产的最佳批量。4. 某种电子元件每月需求量为4000件，每件成本为150元，每年的存贮费为成本的10%，每次订购费为500元，求（1）不允许缺货条件下的最优存贮策略；（2）允许缺货，缺货费为每件每年100元，求最优存贮策略。5. 设某车间每月需要某种零件30000个，每次的订购费为500元，每月每件的存贮费为0.2元，零件批量的单价如下：若不允许缺货，且一订货就进货，试求最佳的订货批量。6. 设某货物的需

33、要量在17件至26件之间，已知需求量r的概率分布如下表：需求量r17181920212223242526概率P(r)0.120.180.230.130.100.080.050.040.040.03已知其成本为每件5元，售价为每件10元，处理价为每件2元，问1）应进货多少，能使总利润期望值最大？2）若因缺货造成的损失为每件25元，则最佳经济批量又该为多少？7. 某人经营某种杂志，每册进价0.8元，售价1.0元，如当期不能售出则削价处理，处理价为0.5元，根据以往经验，杂志销售量服从均匀分布，最高需求量b=1000册，最低需求量a=500册，问应进货多少，才能使获得的利润期望值最大？8. 某公司使用某种原料，每箱进价为900元，订购费为100元，每箱货物存贮一个周期的存贮费为40元，缺货费为每箱1200元，初始库存为10箱，已知该原料的需求概率分布为：P(r=30)=0.2，P(r=40)=0.25，P(r=50)=0.3，P(r=60)=0.25，求该公司的（s，S）存贮策略。9. 某商店经销一种电子产品，每台进货价为4000元，单位存贮费为60元，如果缺货，缺货费为4300元，每次订购费为5000元，根据资料分析，该产品销售量服从区间75，100内的均匀分布，即：期初库存为零，试根据模型九中（s，S）型存贮策略确定s及S的值。