B运筹学课后习题.pdf

苏州科技大学苏州科技大学 2016秋秋1 苏州科技大学 商学院 范克危 2016B2016B- -运筹学运筹学 课后习题课后习题 苏州科技大学苏州科技大学 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 1章章运筹学的思想与方法运筹学的思想与方法 苏州科技大学苏州科技大学 2016秋秋4 作业 ? 电影电影 ?战国 ?伦敦上空的鹰 ? 阅读阅读 ?天空教室-OR in China ?天空教室-物流与运筹学的关系 苏州科技大学苏州科技大学 2016秋秋5 第第2 2章章 线性规划问题的数学模型线性规划问题的数学模型 苏州科技大学苏州科技大学 2016秋秋6 ? 习题习题1 ?P59 习题1(建立数学模型，不需要求解) ? 习题习题2 ?P61 习题6(建立数学模型，不需要求解) 作业 苏州科技大学苏州科技大学 2016秋秋7 第第3 3章章 线性规划问题解的性质线性规划问题解的性质 苏州科技大学苏州科技大学 2016秋秋8 ? 习题习题1：把下列：把下列LP问题化为标准型问题化为标准型 (1) maxS=-3x1+4x2-2x3+5x4 (2) maxS=2x1+3x2-4x3 + + =+ 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=2x1+3x2 (2) minS=2x1+x2 + + 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 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可用工时 机加工 51060 总装 4440 利润(元件)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 5章章 对偶对偶LPLP问题及对偶单纯形法问题及对偶单纯形法 苏州科技大学苏州科技大学 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元。而存放每吨 玉米，烟草和花生需要仓库分别为4m2、5m2和6m2。共有仓 库1000m2。贮存每吨玉米、烟草和花生分别需要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)以y1，y2为对偶变量写出其对偶问题； ? (2)证明(y1，y2)=(6/5，1/5)是对偶问题的一个可行解； ? (3)利用(2)的结果分别对原问题及对偶问题求出最优解。 + + += 0, 20232 20322 432 4321 4321 4321 4321 xxxx xxxx xxxx xxxxSmax 苏州科技大学苏州科技大学 2016秋秋25 第第6 6章章运输问题运输问题 苏州科技大学苏州科技大学 2016秋秋26 作业 ? 习题习题1 ?设某市有三家面粉厂A1，A2，A3，每天生产的面粉运往 四家粮店B1，B2，B3，B4，其产量、销量及其运价如表 所列，试求总运费最省的调运方案。 表 单位：元/吨 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 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 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 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 某县有三个新建水电站A1，A2 ，A3 ，根据有关资料，在雨季各发电站发电量 分别为a1=300，a2=200，a3=80(单位均为万度)；而供电区有：B1锰矿，B2 水泥厂，B3造纸厂，B4电气化乡，各需电区分别需电量为：b1=250， b2=150，b3=130，b4=50(单位均为万度)。由于各发电站的发电成本不同，再 考虑线路及维修管理费用，所以从各发电厂到供电区每度电的电价是不同 的，如表所示： 习题习题5 问如何编制供电计划，使总成本最少？ 单位电价表 单位：分/度 用电单位 发电站 B1B2B3B4 A1 A2 A3 5 7 5.5 5.5 6.5 6 6 5.8 5 5 5 5 习题课二 苏州科技大学苏州科技大学 2016秋秋33 第第7 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 8章章图与网络图与网络 苏州科技大学苏州科技大学 2016秋秋37 习题 ? 习题习题1：写出下面各图的关联矩阵和邻接矩阵：写出下面各图的关联矩阵和邻接矩阵 v1 v2