《运筹学》习题集汇总.doc

1、第一章 线性规划11 将下述线性规划问题化成标准形式 1 min z 3x 1 4x 2 2x 3 5 x 4st.4x 1 x 2 2x 3 x 4 2 x 1 x 2 x 3 2 x4 14 2x 1 3x 2 x 3 x 4 2 x 1 ，x 2 ，x 3 0，x 4 无约束2 min z 2x 1 2x 2 3x 3 x 1 x 2 x 3 4 2x 1 x 2 x 3 6 x 10 ，x 2 0， x 3无约束st.12用图解法求解LP 问题，并指出问题具有唯一最 优解、无 穷多最优解、无界解还是无可行解。1 min z 2x 13x 24x 16x 26st 2x 12x 24 x

2、 1，x 202 max z 3x 12x 2 2x 1x 22 st 3x 14x 212x 1，x 203 max z 3x 15x 2 6x 110x 2120 st 5x 1103x 284 max z 5x 16x 2 2x 1x 2213 找出下述LP 问题所有基解，指出哪些是基可行解，并确定最优解 （1）min z 5x 12x 23x 32x 41st 2x 13x 22 x 1，x 20x 12x 23x 34x 47 st 2x 12x 2x 3 2x 43x 1，x 2，x 3，x 4014 分别用图解法与单纯形法求解下列LP 问题，并 对照指出最优解所 对应的顶点。 1

3、 maxz 10x 15x 23x 14x 29 st 5x 12x 28 x 1， x 202 maxz 2x 1x 23x 15x 215 st 6x 12x 224x 1，x 2015 分别用大M 法与两阶段法求解下列LP 问题。 1 minz 2x 13x 2x 3 x 14x 22x 38st 3x 12x 2 6 x 1，x 2 ，x 302 max z 4x 15x 2 x 3. 3x 12x 2 x 318St. 2x 1 x 2 4x 1 x 2 x 353 maxz 5x 13x 2 +6x3 x 12x 2 x 3 18 st 2x 1x 2 3 x3 16 x 1x 2

4、 x 310 x 1，x 2 ，x 304 max z =10x 1+15x 2+12x 395x 1+3x 2+x 3-5x +6x +15x 15123st . x 352x 1+x 2+x , x , x 01231621.7某班有男生30人，女生20人，周日去植 树。根据经验 ，一天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽 树20棵，或给15棵树浇水。 问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。1.8某糖果厂用原料A 、B 、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A 、B

5、、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线性规划的数学模型。甲 乙 丙 原料成本(元/千克 每月限量（千克）A 6015 2.00 2000 B 1.50 2500 C 206050 1.00 1200 加工费（元/ 千克 0.50 0.40 0.30 售 价 3.40 2.85 2.251.9某商店制定712月进货售货计划，已知商店仓库容量不得超过500件，6月底已存货200件，以后每月初 进货一次，假 设各月份此商品买进售出单价如下表所示，问各月 进货售货各多少，才能使总

6、收入最多？请建立此问题的线性规划模型。 月 份 7 8 9 10 11 12 买进单价 28 24 25 27 23 231.10某厂接到生产A 、B 两种产品的合同，产品A 需200件， 产品B 需300件。 这两种产品的生 产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段，产 品A 每件需要2小 时， 产品B 每件需要4小时。机械加工 阶段又分粗加工和精加工两道工序，每件产品A 需粗加工4小时，精加工10 小时；每件产品B 需粗加工7小时，精加工12 小时。若毛坯生 产阶段能力 为1700小时，粗加工 设备拥有能力为1000小时，精加工设备拥有能力为3000小时。又加工费用在毛坯、粗

7、加工、精加工时分别为每小时3元、 3元、 2元。此外在粗加工阶段允许设备可进行500小时的加班生产，但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料， 为该厂制订一个成本最低的生产计划。1.11某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务，该公司需要每周总有效工作

8、小时数为：第一项工作10000小时。第二项工作20000小时，第三项工作30000小时。又能招收到的工人数为技工不超过400人，力工不超过800人。试建立数学模型，确定招收技工和力工各多少人。使总的工资支出为最少(3第二章 对偶与灵敏度分析21 写出以下线性规划问题的DLP 1 minz 2x 12x 24x 3stx 13x 24x 3 2 2x 1 x 23x 3 3 x 14x 23x 3 5 x 1，x 20， x 3无约束 x 12x 22x 3 5 x 15x 2 x 3 3 4x 17x 23x 3 8 x 1无约束，x 20，x 302 max z 5x 16x 23x 3st

9、3 max z c 1x 1c 2x 2c 3x 3sta 11x 1a 12x 2a 13x 3 b 1a 21x 1a 22x 2a 23x 3 b 2 a 31x 1a 32x 2a 33x 3 b 3 x 10，x 20 ，x 3无约束22 st对于给出的LP ：minz 2x 13x 25x 36x 4 x 12x 23x 3x 4 2 2x 1x 2x 33x 4 3x j 0 （j=1,2,3,4） 1 写出DLP ；2 用图解法求解DLP ；3 利用2）的结果及根据对偶性质写出原问题的最优解。23 对于给出LP ： maxz x 12x 2x 3stx 1 x 2 x 3 2

10、x 1 x 2 x 3 1 2x 1 x 2 x 3 2 x 10， x 20， x 3无约束1 写出DLP ；2 利用对偶问题性质证明原问题目标函数值Z 124 已知LP ： max z x 1x 2st x 1 x 2 x 3 22x 1 x 2 x 3 1 x j 04试根据对偶问题性质证明上述线性问题目标函数值无界。25 给出LP ： maxz 2x 14x 2x 3x 4 x 1 3x 2 x 4 82x 1 x 2 6 st. x 2 x 3 x 46x 1 x 2 x 3 9 x j 01 写出DLP ；2 已知原问题最优解X （2,2， 4,0），试根据对偶理论，直接求出 对偶

11、问题 的最优解。26 用对偶单纯形法求解下列线性规划问题 1 minz 4x 112x 218x 3stx 1 3x 3 32 x22x 3 5 x j 0 (j=1,2,32 min z =5x 1+2x 2+4x 33x 1+x 2+2x 34st . 6x 1+3x 2+5x 310x , x , x 012327 考虑如下线性规划问题minz 60x 140x 280x 3 3x 12x 2 x 3 2st4x 1 x 23x 3 42x 12x 22x 3 3 x j 01 写出DLP ；2 用对偶单纯形法求解原问题； 3 用单纯形法求解其对偶问题； 4 对比以上两题计算结果。28

12、已知LP ：maxz 2x 1x 2x 3 x 1 x 2 x 36st x 12x 2 4 x 1，x 2，x 301 用单纯形法求最优解2 分析当目标函数变为maxz 2x 13x 2x 3时最优解的变化； 3 分析第一个约束条件右端系数变为3时最优解的变化。529 给出线性规划问题 maxz 2x 13x 2x 31/3x11/3x21/3x31 st 1/3x1 4/3x27/3x33 x j 01 目标函数中变量x 3的系数变为6；2 分别确定目标函数中变量x 1和x 2的系数C 1、 C 2在什么范围内变动时最优解不变； 3 约束条件的右端由 1 变为 2 ； 3 32.10 某厂

13、生产甲、乙两种产品，需要 A 、B 两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。（2）原料A 、 B 的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A 和4千克原料B ，问该产 品的销售价格至少 为多少时才值得投产。（4）工厂可在市场上买到原料A 。工厂是否应该购买该原料以 扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？3. 5 某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、 2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同, 见下表。又知丙百货商店要求至少供应C 玩具1000 件，而拒绝进A 玩具。求满足上述条件下使 总盈利额最大的供销分配方案。甲 乙 丙 可供量A 5 4 1000B 16 8 9 2000 C 12 10 11 2000第三章 运输问题3132333.4 某市有三个面粉厂，他们供 给三个面食加工厂所需的面粉，各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均式于下表。假定在第1， 2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元， 试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。