《运筹学习题.doc》由会员分享，可在线阅读，更多相关《运筹学习题.doc（15页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上运筹学习题1线性规划数学模型的结构及各要素的特征。2什么是线性规划问题的标准型式，如何将一个非标准型的线性规划问题转化为标准型式。3试说明线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。4如何从单纯形表上来判别该线性规划问题具有唯一最优解、无穷多个最优解、无界解或无可行解。5判断下列说法是否正确 ：（1）图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的；（2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；（3）线性规划问题的每一个基可行解对应于可行域的一个顶点，如果线性规划问
2、题存在最优解，则最优解一定对应可行域边界上的一个点；（4）用单纯形法求解标准型式的线性规划问题时，检验数sj0对应的非基变量xj都可以被选作为换入变量；（5）在单纯形法计算中，选取最大正检验数sk对应的变量xk作为换入变量，将使目标函值得到最快的增长；（6）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；（7）线性规划问题的任一可行解都可以用全部基可行解的线性组合来表示；（8）X1、X2 分别是某线性规划问题的最优解，则X=l1X1 + l2X2也是该线性规划问题的最优解，其中l1、l2为正的实数；（9）有n个变量、m个约束条件的标准型线性规
3、划问题，其可行域的顶点恰好为Cnm 个。（10）在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；（11）任何线性规划问题存在并具有唯一的对偶问题；（12）对偶问题的对偶问题一定是原问题；（13）线性规划的原问题有无穷多个最优解，则其对偶问题也一定具有无穷多个最优解；（14）已知yi*0为线性规划问题的对偶问题的最优解，若yi*0，则说明在最优生产计划中第i种资源已完全耗尽；（15）已知yi*为线性规划问题的对偶问题的最优解，若yi*=0，则说明在最优生产计划中第i种资源一定有剩余；（参考下面的举例说明）（16）若某种资源的影子价格等于k0，在其他条件不
4、变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；（参考下面的举例说明）（17）当用对偶单纯形算法求解线性规划时，若单纯形表中某一基变量xi0，现在我们增加5个机器台时，则上述问题变成：我们仍然利用单纯形算法求解此问题得如下表：CBXBbx1x2x3x4x50x313121000x416400100x5804001检验数230000x391010-1/20x416400103x2201001/4检验数2000-3/40x35101-1/4-1/22x140001/403x2201001/4检验数000-1/2-3/4即原问题的最优解为（x1，x2，x3，x4，x5）=（4，2，
5、5，0，0），最优目标函数值仍然为Z=24+33=1414+y15=14+25=24。(20) 运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列情况之一 ：有唯一最优解、有无穷多最优解、无界解和无可行解；()(21) 在运输问题中，只要给出一组含（m + n 1）个非负的xij，且满足 ，就可以作为一个初始基可行解；()(22)表上作业法实质上就是求解运输问题的单纯形法；()(23)按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；()(24)如果运输问题的单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化；
6、()(25)如果运输问题的单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；()(26)当所有产地产量和销地的销量均为整数时，用表上作业法求得的运输问题的最优解也为整数解。()二应用题：2.1已知某工厂计划生产I、II、III三种产品，各产品需要在A、B 、C三种设备上加工，各有关数据见如下表，试回答：（1） 如何充分发挥设备能力，使生产盈利最大？（2） 若为了增加产量，可借用别的工厂的设备B，每月可借用60台时，租金为1.8万元，问借用设备B是否合算？（3） 若另有两种新产品IV、V，其中IV需用设备A12台时，B5台时，C10台时,单位产品盈利2.1千元；V
7、需用设备A4台时，B4台时，C12台时,单位产品盈利1.87千元。如果A、B 、C三种设备台时不增加，分别回答这两种新产品投产在经济上是否合算？（4） 若对产品工艺重新进行设计和结构改造，而改进后生产每件产品I需用设备A9台时，设备B12台时，设备C4台时,单位产品盈利4.5千元，问这对原计划有何影响？IIIIII设备有效台时（每月）A8210300B1058400C21310420单位产品利润（千元）322.9解：设每月生产产品I、II、III的数量分别为x1、x2、x3。依题意，本问题的线性规划模型为：（1） 利用单纯形法求解如下：CBXBbx1x2x3x4x5x60x4300821010
8、00x540010580100x642021310001检验数322.90003x137.510.251.250.125000x52502.5-4.5-1.25100x6345012.57.5-0.2501检验数01.25-0.85-0.375003x135101.70.25-0.102x21001-1.8-0.50.400x622000306-51检验数001.40.25-0.503x1338/15100-9/10011/60-17/3002x2116/5010-7/501/103/502.9x322/30011/5-1/61/30检验数000-3/100-4/15-7/150即原问题的最优
9、解为（x1，x2，x3，x4，x5）=（338/15，116/5，22/3，0，0）。目标函数的最优值为：Z=3338/15+2116/5+2.922/3=135.27（千元）。对偶问题的最优解应对应于原问题松弛变量x4，x5，x6的检验数，所以为：（y1，y2，y3）=（3/100，4/15，7/150）。（2）CBXBbx1x2x3x4x5x63x1503/15100-9/10011/60-17/3002x2146/5010-7/501/103/502.9x3-8/30011/5-1/61/30检验数000-3/100-4/15-7/1503x1153/51011/1013/1000-1/
10、502x2138/5013/5-1/5002/250x51600-6-6/51-1/5检验数00-8/5-7/200-1/10这时的最优解为：（x1，x2，x3，x4，x5）=（153/5，138/5，0，0，16）。目标函数的最优值为：Z=3153/5+2138/5=147，147-18=129135.27（千元）。此时，增加第V种产品的生产在经济上是合算的。（4） 假设工艺重新进行设计和结构改造后产品I的产量为x1/，计算：又，所以在原问题最优单纯形表中增加一列得下表：CBXBbx1x2x3x4x5x6x1/3x1338/15100-9/10011/60-17/300349/3002x21
11、16/5010-7/501/103/509/502.9x322/30011/5-1/61/30-1/15检验数000-3/100-4/15-7/150253/300CBXBbx1/x2x3x4x5x64.5x1/6760/349100-27/34955/349-17/3492x26880/349010-44/34925/34924/3492.9x33010/34900168/349-109/69821/698检验数000123/3490-2789/6980-39/6980CBXBbx1/x2x3x4x5x64.5x1/775/341027/6800.220.0372x2430/170122/3
12、40-1/343/340x41505/3400349/681-109/13621/136检验数00-123/6800-101/272-0.015这时的最优解为：（x1/，x2，x3，x4，x5，x6）=（775/34，430/17，0，0，0，0）。目标函数的最优值为：Z=4.5775/34+2430/17=153.16135.27（千元）。改进结构后，只生产产品I、II，盈利更多。2.2 一贸易公司专门经营某种杂粮的批发业务。公司线有库容为5000担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表1所示： 表1进 货 价 格 (元)出 货 价 格
13、(元)一 月2.853.10二 月3.053.25三 月2.902.95 如买进的杂粮当月到货，但需要到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000担，问应采取什么样的买进与卖出的策略使三个月总的获利最大？（列出求解的线性规划模型，不用求解） 提示：三个存货限制，三个库容限制，三个资金限制，一个期末库存限制。2.3某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季节3500人日，春夏季节4000人日，如劳动力本身用不了时可外出打工，春夏季收入为2.1元/人日，秋冬季收入为1.8元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时
14、不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5 公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收入为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡。牛栏允许最多养32头奶牛。三种农作物每年需要的人工及收入情况如表2所示。 表2大 豆玉 米小 麦秋冬季需人日数203510春夏季需人日数507540年净收入(元/公顷)175300120试决定该农场的经营方案，使年净收入为最大。（建立线性规划模型，不求解）提示：1个土地限制、1个资金
15、限制、2个劳动力限制、1个牛栏限制、1个鸡舍限制2.4市场对I、II两种产品的需求量为：产品I在14月每月需10000件，59月每月需30000件，1012月每月需件；产品II在39月每月需15000件，其它月份每月需50000件。某厂生产这两种产品成本为：产品I在15月内生产每件5元，612月内生产每件4.50元；产品II在15月内生产每件8元，612月内生产每件7元。该厂每月生产两种产品能力总和应不超过件。产品I容积每件0.2立方米，产品II容积每件0.4立方米，而该厂仓库容积为15000立方米，要求：(a)说明上述问题无可行解；(b)若该厂仓库不足时，可从外厂借。若占用本厂每月每平方米库
16、容需1元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂应如何安排生产，使总的生产加库存费用为最少。（建立模型，不需求解）提示：2.5对某厂I、II、III三种产品下一年各季度的合同预订数如表3所示。 表3产 品季 度1234I1500100020001200II1500150012001500III1000200015002500该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时为15000小时，生产I、II、III产品每件分别需要2、4、3小时。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季
17、度赔偿20元，产品III赔10元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5元。问该厂应如何安排生产，使总的赔偿加库存的费用为最小。（要求建立模型，不需要求解）提示：设xij为第j季度生产的产品i的数量，sij代表j季度需库存的产品i的数量，fij为第j季度末交货的产品i的数量，rij为第j季度对产品i的预订数，则有：2.6厂生产I、II两种食品，现有50名熟练工人，已知一名熟练工人每小时可生产10千克食品I或6千克食品II。据合同预订，该两种食品每周的需求量急剧上升，见表4。为此该厂决定到第8周末需培训出50名新的工人，两班生产。已知一名工人每周工作40小时，一名熟练工人用两周
18、时间可培训出不多于三名新工人（培训期间熟练工人和培训人员均不参加生产）。熟练工人每周工资360元，新工人培训期间每周工资120元，培训结束参加工作后每周工资240元，生产效率同熟练工人。在培训的过度期间，很多熟练工人愿意加班工作，工厂决定安排部分工人每周工作60小时，工资每周540元。又若预订的食品不能按期交货，每推迟交货一周的赔偿费为食品I0.5元/千克，食品II0.6元/千克。在上述各种条件下，工厂应如何作出全面安排，使各项费用的总和为最小。（建立模型，无需求解）表4 单 位： 吨 / 周 周 次食 品12345678I1010121216162020II67.28.410.810.812
19、1212提示：设xi，yi分别为第i周内用于生产食品和的工人数；zi为第i周内加班工作的工人数；wi为从i周开始抽出来培训新工人的原来工人数；ni为从i周起开始接受培训的新工人数；fi1和fi2分别为第i周末未能按期交货的食品和的数量；ri1和ri2分别为第i周内对食品和的需求量，则有：2.8如表所示的运输问题中，若产地i有一个单位物资未运出，则将发生存储费用。假定1、2、3产地单位物资的存储费用分别为5、4和3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。 销 地产 地ABC产 量112220214540323330销 量302020提示：
20、增加假想地D，销量为20。将产地分别列为1，2，2，3，其中2，3的物资必须全部运出，不可以分给D，如下图，再用表上作业法求出最优解。 销 地产 地ABCD产 量112202021450221 45M383233033233M27销 量302020302.8已知A1，A2，A3三个矿区可分别供应煤炭200，300，400（万吨/年）。下述地区需调入煤炭：B1：100200万吨/年，B2：200300万吨/年，B3：为不低于200万吨/年，最高不限，B4：180300万吨/年，已知单位运价表如表6所示。如要求把所有煤炭分配出去，满足上述需求，又使总运费为最少的调运方案，试列出用运输问题模型求解时
21、的产销平衡表及单位运价表（不必求解）。 表6 销 地产 地B1B2B3B4A14365A271056A3891217 2.9用匈牙利算法求解下述指派问题，已知效率矩阵分别如下： （a） （b）提示：（a)最优指派方案为X13=X22=X34=X41=1,最优值为48.(b)最优指派方案为X15=X23=X32=X44=X51=1,最优值为21.2.10分配甲、乙、丙、丁四个人去完成五项任务。每人完成任务的时间如表7所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 表7 任 务人ABCDE甲2529314237乙39382620
22、33丙3427284032丁2442362345提示：加上假设的第五个人是戊，她完成各项工作的时间取甲乙丙丁中最小者，如下表 任 务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032用匈牙利法求解，的最优分配方案为：甲，乙和，丙，丁，总计需要h2.11某彩色电视机组装工厂，生产A，B，C三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台、10台、6台。
23、该厂经营目标如下： p1：利润指标定为每月1.6 104元； p2：充分利用生产能力； p3：加班时间不超过24小时； p4：产量以预计销量为标准。 为确定生产计划，试建立该问题的目标规划的数学模型。提示：生产电视机A型为X1台，B型为X2台，C型为X3台，该问题的目标规划模型为：2.12 友谊农场有3万亩农田，今欲种植玉米、大豆和小麦等三种农作物。各种农作物每亩需施化肥分别为0.12吨、0.20吨和0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克，大豆每亩可收获200千克，售价为1.20元/千克，小麦每亩可收获300千克，售价为0.70元/千克 。农场年初规划时依目标重要
24、性顺序考虑如下几个方面：（1） 年终总收益不低于350万元，赋予优先权P1 ；（2） 年总产量不低于1.25万吨，赋予优先权P2 ；（3） 小麦产量以0.5万吨为宜，赋予优先权P3 ；（4） 大豆产量不少于0.2万吨，赋予优先权P4 ；（5） 玉米产量不超过0.6万吨，赋予优先权P5 ；（6） 农场现能提供5000吨化肥，若不够，可在市场上高价购买，但希望高价采购量愈少愈好；赋予优先权P6 。试就该农场年生产计划建立目标规划的数学模型。提示：设种玉米X1亩，大豆X2亩，小麦X3,则数学模型为：2.13 某地方书店希望订购最新出版的好的图书。根据以往经验，新书的销售量可能为50、100、150或
25、200本。假定每本新书的订价为4元，销售价格为6元，剩书的处理价为每本2元。要求：1）建立益损矩阵；2）分别用悲观法、乐观法及等可能法决定该书店应订购的新书数量；3）建立后悔矩阵，并用后悔值法决定书店应订购的新书数量。提示：(b)悲观法S1,悲观法S4,等可能法S2和S3 (c)后悔值法决策：S2和S3 2.14 某决策者的效用函数可由下式表示：如决策者面临如下两份合同（见表8所示）：表8概 率合 同 P1 = 0.6P2 = 0.4A（元）65000B（元）40004000 问决策者倾向于签订哪份合同？答案：B2.15 某企业生产一种新产品，为了满足可能出现的高需求，可以增添某些附加设备。但
26、一旦出现高需求后，不能确切知道高需求是否长期持续。根据对今后八年市场需求的预测，对该种新产品的需求估计见表9。表9需求（前三年）需求（后五年）可 能 性高高0.4高低0.2低高0.3低低0.1 据此有两种投资方案：方案A为一次投资10万元，碰到高需求时每年盈利40000元，低需求时每年盈利5000元；方案B为分阶段投资，开始投一笔，三年后再根据情况确定是否投。执行方案B，在碰到高需求时头三年每年盈利30000元，如不增加投资，后五年每年盈利20000元，如增加投资，后五年每年盈利40000元；在碰到低需求时，头三年每年盈利30000元，不增加投资时后五年每年仍为30000元，增加投资时后五年每
27、年盈利10000元。又分阶段投资时，期初投资额为70000元，后期增加额应为45000元。试用决策树法确定最优的投资策略。 答案：采用方案 B。具体最优决策就是第一阶段投资 7 万元，第二阶段不增加投资，预期盈利八年累计为 13.5 万元。2.16已知建设一个汽车库及引道的作业明细表如表10所示。表10工序代号工 序 名 称工序时间（天）紧 前 工 序a清理场地，准备施工10b备 料8c车库地面施工6a、bd预制墙及房顶的桁架16be车库混凝土地面保养24cf立 墙 架4d、eg立房顶桁架4fh装窗及边墙10fi装 门4fj装天花板12gk油 漆16h、i、jl引道混凝土施工8cm引道混凝土保
28、养24ln清理场地，交工验收4k、m要求：a) 绘制网络图并计算网络时间；b) 根据网络图，找出关键工序和关键路线；c) 若要求该项工程在70天内完工，又知各道工序按正常进度的工序时间与每天的费用以及赶工作业的工序时间与每天的费用如表11所示，试确定在保证70天内完成，又使全部费用最低的施工方案。 表11工序代号正 常 工 作赶 工 作 业工序时间（天）每天费用（元）工序时间（天）每天费用（元）a1050675b840840c640460d16601285e245245f440270g420230h1030840i430345j1225840k16501280l840660m245245n410410答案：a）总工期为80天；b)关键路线是由工序：a、c、e、f 、g、j、k、n八道工序组成；c)工序g（立房顶桁架）、工序j（装天花板）及工序c（车库地面施工）全部赶工作业。工序a（清理场地，准备施工）5天正常工作，3天赶工作业。其它工序一律按正常施工。专心-专注-专业
