厦门大学运筹学OR课堂练习

1、运筹学课堂练习1 线性规划数学模型的结构及各要素的特征。2 什么是线性规划问题的标准型式，如何将一个非标准型的线性规划问题转化为标准型式。3 试说明线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。4 如何从单纯形表上来判别该线性规划问题具有唯一最优解、无穷多个最优解、无界解或无可行解。5 判断下列说法是否正确 ：(a) 图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的；(b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；(c) 线性规划问题的每一个基可解对应可行域的一个顶点，如果线性规划问题存在最优

2、解，则最优解一定对应可行域边界上的一个点；(d) 用单纯形法求解标准型式的线性规划问题时，检验数sj 0 对应的非基变量xj 都可以被选作为换入变量；(e) 在单纯形法计算中，选取最大正检验数 sk 对应的变量 xk 作为换入变量，将使目标函数值得到最快的增长；(f) 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；(g) 线性规划问题的任一可行解都可以用全部基可行解的线性组合来表示；(h) 若 X1、X2 分别是某线性规划问题的最优解，则 X = l1X1 + l2X2 也是该线性规划问题的最优解，其中 l1、l2 为正的实数；(i) 对于

3、一个有n个变量、m 个约束条件的标准型线性规划问题，其可行域的顶点恰好为 Cnm 个。6 一贸易公司专门经营某种杂粮的批发业务。公司线有库容为5000担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表1所示： 表1进 货 价 格 (元)出 货 价 格 (元)一 月2.853.10二 月3.053.25三 月2.902.95 如买进的杂粮当月到货，但需要到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000担，问应采取什么样的买进与卖出的策略使三个月总的获利最大？（列出求解的线性规划模型，不用求解）7. 某农场有100公顷土地及15000元资

4、金可用于发展生产。农场劳动力情况为秋冬季节3500人日，春夏季节4000人日，如劳动力本身用不了时可外出打工，春夏季收入为2.1元/人日，秋冬季收入为1.8元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5 公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收入为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡。牛栏允许最多养32头奶牛。三种农作物每年需要的人工及收入

5、情况如表2所示。 表2大 豆玉 米小 麦秋冬季需人日数203510春夏季需人日数507540年净收入(元/公顷)175300120试决定该农场的经营方案，使年净收入为最大。（建立线性规划模型，不求解）8. 市场对I、II两种产品的需求量为：产品I在14月每月需10000件，59月每月需30000件，1012月每月需100000件；产品II在39月每月需15000件，其它月份每月需50000件。某厂生产这两种产品成本为：产品I在15月内生产每件5元，612月内生产每件4.50元；产品II在15月内生产每件8元，612月内生产每件7元。该厂每月生产两种产品能力总和应不超过120000件。产品I容积

6、每件0.2立方米，产品II容积每件0.4立方米，而该厂仓库容积为15000立方米，要求：(a)说明上述问题无可行解；(b)若该厂仓库不足时，可从外厂借。若占用本厂每月每平方米库容需1元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂应如何安排生产，使总的生产加库存费用为最少。（建立模型，不需求解）9. 对某厂I、II、III三种产品下一年各季度的合同预订数如表3所示。 表3产 品季 度1234I1500100020001200II1500150012001500III1000200015002500该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生

7、产工时为15000小时，生产I、II、III产品每件分别需要2、4、3小时。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季度赔偿20元，产品III赔10元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5元。问该厂应如何安排生产，使总的赔偿加库存的费用为最小。（要求建立模型，不需要求解）10 厂生产I、II两种食品，现有50名熟练工人，已知一名熟练工人每小时可生产10千克食品I或6千克食品II。据合同预订，该两种食品每周的需求量急剧上升，见表4。为此该厂决定到第8周末需培训出50名新的工人，两班生产。已知一名工人每周工作40小时，一名熟练

8、工人用两周时间可培训出不多于三名新工人（培训期间熟练工人和培训人员均不参加生产）。熟练工人每周工资360元，新工人培训期间每周工资120元，培训结束参加工作后每周工资240元，生产效率同熟练工人。在培训的过度期间，很多熟练工人愿意加班工作，工厂决定安排部分工人每周工作60小时，工资每周540元。又若预订的食品不能按期交货，每推迟交货一周的赔偿费为食品I0.5元/千克，食品II0.6元/千克。在上述各种条件下，工厂应如何作出全面安排，使各项费用的总和为最小。（建立模型，无需求解）表4 单 位： 吨 / 周 周 次食 品12345678I1010121216162020II67.28.410.81

9、0.812121211. 判断下列说法是否正确 ：(a) 运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列情况之一 ：有唯一最优解、有无穷多最优解、无界解和无可行解；(b) 在运输问题中，只要给出一组含（m + n 1）个非负的xij，且满足 ，就可以作为一个初始基可行解；(c) 表上作业法实质上就是求解运输问题的单纯形法；(d) 按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；(e) 如果运输问题的单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化；(f) 如果运输问题的单位运价表的某一行（或某一列）元素

10、分别加上一个常数k，最优调运方案将不会发生变化；(g) 当所有产地产量和销地的销量均为整数时，用表上作业法求得的运输问题的最优解也为整数解。12. 如表5所示的运输问题中，若产地i有一个单位物资未运出，则将发生存储费用。假定1、2、3产地单位物资的存储费用分别为5、4和3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。 表5 销 地产 地ABC产 量112220214540323330销 量30202013已知A1，A2，A3三个矿区可分别供应煤炭200，300，400（万吨/年）。下述地区需调入煤炭：B1：100200万吨/年，B2：2003

11、00万吨/年，B3：为不低于200万吨/年，最高不限，B4：180300万吨/年，已知单位运价表如表6所示。如要求把所有煤炭分配出去，满足上述需求，又使总运费为最少的调运方案，试列出用运输问题模型求解时的产销平衡表及单位运价表（不必求解）。 表6 销 地产 地B1B2B3B4A14365A271056A389121714用匈牙利算法求解下述指派问题，已知效率矩阵分别如下： （a） （b）15分配甲、乙、丙、丁四个人去完成五项任务。每人完成任务的时间如表7所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 表7 任 务人ABCDE

12、甲2529314237乙3938262033丙3427284032丁244236234516某彩色电视机组装工厂，生产A，B，C三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台、10台、6台。该厂经营目标如下： p1：利润指标定为每月1.6 104元； p2：充分利用生产能力； p3：加班时间不超过24小时； p4：产量以预计销量为标准。 为确定生产计划，试建立该问题的目标规划的数学模型。17 友谊农场有3万亩农田，今欲

13、种植玉米、大豆和小麦等三种农作物。各种农作物每亩需施化肥分别为0.12吨、0.20吨和0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克，大豆每亩可收获200千克，售价为1.20元/千克，小麦每亩可收获300千克，售价为0.70元/千克 。农场年初规划时依目标重要性顺序考虑如下几个方面：（1） 年终总收益不低于350万元，赋予优先权P1 ；（2） 年总产量不低于1.25万吨，赋予优先权P2 ；（3） 小麦产量以0.5万吨为宜，赋予优先权P3 ；（4） 大豆产量不少于0.2万吨，赋予优先权P4 ；（5） 玉米产量不超过0.6万吨，赋予优先权P5 ；（6） 农场现能提供5000吨

14、化肥，若不够，可在市场上高价购买，但希望高价采购量愈少愈好；赋予优先权P6 。试就该农场年生产计划建立目标规划的数学模型。18. 某地方书店希望订购最新出版的好的图书。根据以往经验，新书的销售量可能为50、100、150或200本。假定每本新书的订价为4元，销售价格为6元，剩书的处理价为每本2元。要求：1）建立益损矩阵；2）分别用悲观法、乐观法及等可能法决定该书店应订购的新书数量；3）建立后悔矩阵，并用后悔值法决定书店应订购的新书数量。19. 某决策者的效用函数可由下式表示：如决策者面临如下两份合同（见表8所示）：表8概 率合 同 P1 = 0.6P2 = 0.4A（元）65000B（元）40

15、004000 问决策者倾向于签订哪份合同？20. 某企业生产一种新产品，为了满足可能出现的高需求，可以增添某些附加设备。但一旦出现高需求后，不能确切知道高需求是否长期持续。根据对今后八年市场需求的预测，对该种新产品的需求估计见表9。表9需求（前三年）需求（后五年）可 能 性高高0.4高低0.2低高0.3低低0.1 据此有两种投资方案：方案A为一次投资10万元，碰到高需求时每年盈利40000元，低需求时每年盈利5000元；方案B为分阶段投资，开始投一笔，三年后再根据情况确定是否投。执行方案B，在碰到高需求时头三年每年盈利30000元，如不增加投资，后五年每年盈利20000元，如增加投资，后五年每

16、年盈利40000元；在碰到低需求时，头三年每年盈利30000元，不增加投资时后五年每年仍为30000元，增加投资时后五年每年盈利10000元。又分阶段投资时，期初投资额为70000元，后期增加额应为45000元。试用决策树法确定最优的投资策略。21. 已知建设一个汽车库及引道的作业明细表如表10所示。表10工序代号工 序 名 称工序时间（天）紧 前 工 序a清理场地，准备施工10b备 料8c车库地面施工6a、bd预制墙及房顶的桁架16be车库混凝土地面保养24cf立 墙 架4d、eg立房顶桁架4fh装窗及边墙10fi装 门4fj装天花板12gk油 漆16h、i、jl引道混凝土施工8cm引道混凝土保养24ln清理场地，交工验收4k、m要求：a) 绘制网络图并计算网络时间；b) 根据网络图，找出关键工序和关键路线；c) 若要求该项工程在70天内完工，又知各道工序按正常进度的工序时间与每天的费用以及赶工作业的工序时间与每天的费用如表11所示，试确定在保证70天内完成，又使全部费用最低的施工方案。 表11工序代号正 常 工 作赶 工 作 业