B运筹学课后习题.pdf

苏州科技大学 2016秋1 苏州科技大学商学院范克危 2016B-运筹学 运筹学 课后习题 课后习题 苏州科技大学 2016秋2 七次作业 七次作业， A4纸规格，手写 第4周交Chap 2-1,2-2,Chap 3-1(1)(2) 第6周交Chap 3-2(1)(2),Chap 3-3 第8周交Chap 4-1(1)(2),Chap 4-2, Chap 4-3 第10周交Chap 4-4(1)(2),Chap 5-1(1)(2) 第12周交Chap 5-2,Chap5-3(1)(2),Chap5-4,Chap 6-1 第14周交Chap 6-2(1)(2),Chap 7-1,Chap 7-2, Chap 8-1 第16周交Chap 8-2,Chap 8-3,Chap 8-4 按学号选做 Chap 7-2 习题课一，习题课二 自己做，不作要求！ 苏州科技大学 2016秋3 第 第 1章 章 运筹学的思想与方法 运筹学的思想与方法 苏州科技大学 2016秋4 作业 电影 战国 伦敦上空的鹰 阅读 天空教室-OR in China 天空教室-物流与运筹学的关系 苏州科技大学 2016秋5 第 第 2章 章 线性规划问题的数学模型 线性规划问题的数学模型 苏州科技大学 2016秋6 习题 1 P59 习题1(建立数学模型，不需要求解) 习题 2 P61 习题6(建立数学模型，不需要求解) 作业 苏州科技大学 2016秋7 第 第 3章 章 线性规划问题解的性质 线性规划问题解的性质 苏州科技大学 2016秋8 习题 1：把下列LP问题化为标准型 (1) maxS=-3x 1 +4x 2 -2x 3 +5x 4 (2) maxS=2x 1 +3x 2 -4x 3 + + =+ 0, 2232 143 224 321 4321 4321 4321 xxx xxxx xxxx xxxx + + 束约无 321 321 321 ,0,0 6 43 xxx xxx xxx 作业 苏州科技大学 2016秋9 习题 2：用图解法解下列LP问题 (1) maxS=2x 1 +3x 2 (2) minS=2x 1 +x 2 + + 0, 82 2 3 4 21 21 21 2 1 xx xx xx x x + + 0, 3 22 92 21 1 21 21 xx x xx xx 作业 苏州科技大学 2016秋10 习题 3 某纺织厂生产甲、乙两种新织物，甲织物所含羊毛和 化纤成份分别为1和2个单位；乙织物羊毛和化纤成份 分别为2和1个单位。甲、乙两种织物每米可得利润分 别为40元和30元，而现有羊毛和化纤分别为400单位和 500单位。 (1)试列出使利润最大的数学模型； (2)把所得的LP模型化成标准形式； (3)用图解法求出最优解。 作业 苏州科技大学 2016秋11 第 第 4章 章 单纯形方法 单纯形方法 苏州科技大学 2016秋12 作业 习题 1：用大 M法求解下列 LP问题 (1) (2) + + += 0, 10536 422 425 321 321 321 321 xxx xxx xxx xxxSmin + + += 0 10 0 102 3032 32 2 1 21 21 21 21 x x xx xx xx xxSmin 苏州科技大学 2016秋13 习题 2：将下列LP问题标准化，并用单纯形法求解 + + + += 无正负号限制 321 21 321 321 321 , 63 44 532 2 xxx xx xxx xxx xxxSmax 习题 3：用大 M法及两阶段法求解下列LP问题 = = + + =+ 作业 += 0, 4 2 3 2 2 3 3 1459 321 3 3 2 2 1 1 21 321 xxx x x x x x x xx xxxSmin 苏州科技大学 2016秋14 习题 4：用两阶段法求解下列LP问题 (1) (2) + + += 0, 8243 22 323 321 321 321 321 xxx xxx xxx xxxSmax =+ + += 0, 6 5 32 21 321 321 321 xx xxx xxx xxxSmin 作业 苏州科技大学 2016秋15 习题课一 习题课一 苏州科技大学 2016秋16 习题 1 列出下列问题的线性规划数学模型：某一贸易公司专门经 营某种杂粮的批发业务。公司现有一个库存容量为5000担 的仓库。1月1日，公司拥有库存1000担的杂粮，并拥有资 金200，000元。估计第一季度杂粮价格如表1所示。如买 进的杂粮当月到货，则需到下月才能卖出，且规定“货到 付款”。公司希望本季末库存为2000担，问应采取什么样 的买进与卖出的策略使三个月总的获利最大？ 表 1 进货价(元)出货价(元) 一月 二月 三月 28.5 30.5 29.0 31.0 32.5 29.5 习题课一 苏州科技大学 2016秋17 习题 2 用图解法求解下列LP问题： 某厂生产A，B两种产品，须经过机加工和总装两道 工序完成。根据该厂的技术水平和设备能力，每件产 品的工时定额、利润、可用的工时如表2所示。问如 何安排生产，才能使所获利润最大？ 表 2 产品 项目 AB 可用工时 机加工 510 60 总装 44 40 利润 ( 元件 ) 68 习题课一 苏州科技大学 2016秋18 用大M法解LP问题： 习题 3 + += 0, 4.1 2 6.18.0 1 8001000 21 2 1 21 1 21 xx x x xx x xxSmin 习题 4 用大M法及两阶段法求解LP问 题： + =+ += 0,0 6 4 22 321 321 321 321 xxx xxx xxx xxxSmin 习题课一 苏州科技大学 2016秋19 用大M法解LP问题： 习题 6 + + + + + 习题 5 += 0, 5 15156 2 5 935 121510 321 3 3 2 2 1 1 321 321 xxx x x x x x x xxx xxxSmax + + += 0, 623 824 32 321 21 321 321 xxx xx xxx xxxSmin 用大M法解LP问题： + + += 0, 0 2 2 2 6 22 321 3 3 2 1 321 321 xxx x x x x xxx xxxSmax 用两阶段法求解LP问题： 习题 7 习题课一 苏州科技大学 2016秋20 第 第 5章 章 对偶 对偶 LP问题及对偶单纯形法 问题及对偶单纯形法 苏州科技大学 2016秋21 作业 习题 1：写出下列问题的对偶问题 (1) (2) + + += 0, 2010 102 10 321 321 321 321 xxx xxx xxx xxxSmax + =+ + += 0, 1 432 5 32 31 431 321 4321 4321 xx xxx xxx xxxx xxxxSmax 苏州科技大学 2016秋22 作业 习题 2：某农贸公司专门经管收购玉米，烟草和花生三种农作 物，每吨可得利润分别为100元，180元和70元。而存放每吨 玉米，烟草和花生需要仓库分别为4m 2 、5m 2 和6m 2 。共有仓 库1000m 2 。贮存每吨玉米、烟草和花生分别需要3、6和2个 工时，该农贸公司共可提供600个工时，预测玉米、烟草和花 生的收购量不大于130吨、80吨和200吨。 (1)试列出使利润达到最大的线性规划模型； (2)写出它的对偶问题； (3)求出它们的最优解； (4)解释对偶问题最优解的影子价格的经济意义； (5)根据影子价格的经济意义，在什么条件下可扩大经营？ 苏州科技大学 2016秋23 作业 习题 3：用对偶单纯形法求解下列LP问题 (1) (2) + + += 0, 77 44 23 21 21 21 21 xx xx xx xxSmin + += 0, 3 4 6 32 321 3 3 2 1 321 321 xxx x x x x xxx xxxSmin 苏州科技大学 2016秋24 作业 习题 4：对下列LP问题 (1)以y 1 ，y 2 为对偶变量写出其对偶问题； (2)证明(y 1 ，y 2 )=(6/5，1/5)是对偶问题的一个可行解； (3)利用(2)的结果分别对原问题及对偶问题求出最优解。 + + += 0, 20232 20322 432 4321 4321 4321 4321 xxxx xxxx xxxx xxxxSmax 苏州科技大学 2016秋25 第 第 6章 章 运输问题 运输问题 苏州科技大学 2016秋26 作业 习题 1 设某市有三家面粉厂A 1 ，A 2 ，A 3 ，每天生产的面粉运往 四家粮店B 1 ，B 2 ，B 3 ，B 4 ，其产量、销量及其运价如表 所列，试求总运费最省的调运方案。 表 单位：元/吨 销地 产地 B 1 B 2 B 3 B 4 产量 A 1 A 2 A 3 50 10 90 110 70 120 60 20 40 100 30 80 1700 1400 1600 销量 1000 1000 1200 1500 苏州科技大学 2016秋27 作业 习题 2 试用表上作业法求解，并用计算机软件验证结果。 (1) (2) 销地 产地 甲 乙 丙 丁 产量 1 2 3 11 16 5 6 13 4 7 5 14 12 9 10 40 90 40 销量 50 20 40 60 销地 产地 B 1 B 2 B 3 B 4 产量 A 1 A 2 A 3 100 80 90 50 20 30 60 70 40 70 60 80 3 4 5 销量 1 2 3 4 苏州科技大学 2016秋28 习题课二 习题课二 苏州科技大学 2016秋29 一家昼夜服务的饭店，24小时中需要的服务员数如表所示： 习题 1 起迄时间服务员的最少人数 2-6 6-10 10-14 14-18 18-22 22-2 4 8 10 7 12 4 每个服务员每天连续工作8小时，且在时段开始时上班。问题 的目标是要求满足以上要求的最少上班人数。(1)试把这个问 题表示成一个LP模型；(2)写出对偶LP；(3)求原始和对偶问 题的最优目标函数值的一个上界和下界。 习题课二 苏州科技大学 2016秋30 写出下列LP问题的对偶问题： + + =+ 习题 2 += 制限号负正无 543 2 1 431 4321 5432 54321 ,0,0 255 102 522 2332 643 87523 xxx x x xxx xxxx xxxx xxxxxSmax (2)运输问题。 (1) 习题课二 苏州科技大学 2016秋31 应用对偶单纯形法，证明下面的LP问题无解： 习题 4 考虑习题1的模型。要求： (1)通过解对偶问题求出原始问题的最优解； (2)说明用这种方法解这个问题比直接求解原问题有何优越 之处。 + 习题 3 += 0, 3 4 6 23 321 32 31 321 321 xxx xx xx xxx xxxSmin 习题课二 苏州科技大学 2016秋32 某县有三个新建水电站A 1 ，A 2 ，A 3 ，根据有关资料，在雨季各发电站发电量 分别为a 1 =300，a 2 =200，a 3 =80(单位均为万度)；而供电区有：B 1 锰矿，B 2 水泥厂，B 3 造纸厂，B 4 电气化乡，各需电区分别需电量为：b 1 =250， b 2 =150，b 3 =130，b 4 =50(单位均为万度)。由于各发电站的发电成本不同，再 考虑线路及维修管理费用，所以从各发电厂到供电区每度电的电价是不同 的，如表所示： 习题 5 问如何编制供电计划，使总成本最少？ 单位电价表 单位：分/度 用电单位 发电站 B 1 B 2 B 3 B 4 A 1 A 2 A 3 5 7 5.5 5.5 6.5 6 6 5.8 5 5 5 5 习题课二 苏州科技大学 2016秋33 第 第 7章 章 整数规划 整数规划 苏州科技大学 2016秋34 习题 = =+ =+ += 为整数 53 5321 4321 321 , )5,2,1(0 22 2 7 22 8235 xx jx xxxx xxxx xxxSmax j L 习题 1 分枝定界方法可以推广到混合整数规划( MIP)问题。试利 用分枝定界法求解： 苏州科技大学 2016秋35 习题 2 课本P195 习题2 学号尾数0，1 课本P195 习题3 学号尾数2，3 课本P195 习题4 学号尾数4，5 课本P196 习题5 学号尾数6，7 课本P197 习题6 学号尾数8，9 要求：列出IP模型，用EXCEL规划求解进行求解。 习题 苏州科技大学 2016秋36 第 第 8章 章 图与网络 图与网络 苏州科技大学 2016秋37 习题 习题 1：写出下面各图的关联矩阵和邻接矩阵 v 1 v 2 v 3 v 4 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 v 5 v 6 v 1 v 2 v 3 v 4 e 1 e 2 e 3 e 4 e 5 e 6 e 7 苏州科技大学 2016秋38 习题 习题 2：设有邮路图如下，问邮递员应按怎样的路线行 走才可使所行走路程最少（设邮局为A）？ A邮局 5 4 3 3 2 3 2 3 4 BCD EF 苏州科技大学 2016秋39 习题 3： P.269第 2题 习题 苏州科技大学 2016秋40 习题 习题 4：下图所示的有向网络，节点 1为发点，节点 5为收 点，弧上的数字为弧的容量，问题是求节点 1到节点 5的 最大流。 (1)建立此问题的 LP模型； (2)用标号法求最大 流； (3)求最小截集，并验证最大流最小截定理。 v 1 v 2 v 3 v 4 3 v 5 9 7 4 3 1 4 7