运筹学--第一章 线性规划.doc

第一章 线性规划习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。(1) min z 6x14x2 (2) max z 4x18x2 st. 2x1 x21 st. 2x12x2103x1 4x21.5 x1 x28x1, x20 x1, x20(3) max z x1 x2 (4) max z 3x12x2 st. 8x16x224 st. x1x214x16x212 2x12x242x24 x1, x20x1, x20(5) max z 3x19x2 (6) max z 3x14x2st. x13x222 st. x12x28x1 x24 x12x212x26 2x1 x2162x15x20 x1, x20x1, x201.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。(1) max z 3x15x2 (2) min z 4x112x218x3st. x1 x3 4 st. x1 3x3 x4 32x2 x4 12 2x22x3 x553x1 2x2 x5 18 xj 0 （j1,5）xj 0 （j1,5）1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。(1) max z 10x15x2 st. 3x14x295x12x28x1, x20(2) max z 100x1200x2st. x1 x2500x1 2002x16x21200 x1, x201.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1) max z 4x15x2 x3 (2) max z 2x1 x2 x3st. 3x12x2 x318 st. 4x12x22x342x1 x2 4 2x14x2 20x1 x2 x35 4x18x22x316xj 0 （j1,2,3） xj 0 （j1,2,3）(3) max z x1 x2 (4) max z x12x23x3x4 st. 8x16x224 st. x12x23x3154x16x212 2x1 x25x3202x24 x12x2 x3 x410x1, x20 xj 0 （j1,4）(5) max z 4x16x2 (6) max z 5x13x26x3 st. 2x14x2 180 st. x12x2 x3183x12x2 150 2x1 x23x316x1 x257 x1 x2 x310x222 x1, x20，x3无约束 x1, x201.5 线性规划问题max zCX，AXb，X0，如X*是该问题的最优解，又0为某一常数，分别讨论下列情况时最优解的变化：（1） 目标函数变为max zCX；（2） 目标函数变为max z（C）X；（3） 目标函数变为max zX，约束条件变为AXb。1.6 下表中给出某求极大化问题的单纯形表，问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有：（1） 表中解为唯一最优解；（2） 表中解为无穷多最优解之一；（3） 表中解为退化的可行解；（4） 下一步迭代将以x1替换基变量x5 ；（5） 该线性规划问题具有无界解；（6） 该线性规划问题无可行解。 x1 x2 x3 x4 x5x3 d 4 a1 1 0 0 x4 2 1 5 0 1 0x5 3 a2 3 0 0 1cj zj c1 c2 0 0 01.7 战斗机是一种重要的作战工具，但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外，需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj（j1,n），又每架战斗机每年能培训出k名驾驶员，问应如何分配每年生产出来的战斗机，使在n年内生产出来的战斗机为空防作出最大贡献？1.8. 某石油管道公司希望知道，在下图所示的管道网络中可以流过的最大流量是多少及怎样输送，弧上数字是容量限制。请建立此问题的线性规划模型，不必求解。 2 5 410 3 11 1 4 3 656 8 73 51.9. 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：班 次 时 间 所需人数1 6:00-10:00 602 10:00-14:00 703 14:00-18:00 604 18:00-22:00 505 22:00-2:00 206 2:00-6:00 30设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。1.10 某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线性规划的数学模型。甲 乙 丙 原料成本(元/千克) 每月限量（千克）A 60 15 2.00 2000B 1.50 2500C 20 60 50 1.00 1200加工费（元/千克） 0.50 0.40 0.30售 价 3.40 2.85 2.251.12. 某商店制定712月进货售货计划，已知商店仓库容量不得超过500件，6月底已存货200件，以后每月初进货一次，假设各月份此商品买进售出单价如下表所示，问各月进货售货各多少，才能使总收入最多？请建立此问题的线性规划模型，不必求解。月 份 7 8 9 10 11 12买进单价 28 24 25 27 23 23售出单价 29 24 26 28 22 251.13 .某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日，春夏季4000人日，如劳动力本身用不了时可外出干活，春夏季收入为2.1元人日，秋冬季收入为1.8元人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元每头奶牛。养鸡时不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收人为2元每只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入(元公顷)175300120试决定该农场的经营方案，使年净收人为最大。(建立线性规划模型，不需求解)1.14 某厂接到生产A、B两种产品的合同，产品A需200件，产品B需300件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段，产品A每件需要2小时，产品B每件需要4小时。机械加工阶段又分粗加工和精加工两道工序，每件产品A需粗加工4小时，精加工10小时；每件产品B需粗加工7小时，精加工12小时。若毛坯生产阶段能力为1700小时，粗加工设备拥有能力为1000小时，精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。此外在粗加工阶段允许设备可进行500小时的加班生产，但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料，为该厂制订一个成本最低的生产计划。1.15 对某厂I，三种产品下一年各季度的合同预订数如下表所示。产 品季 度1234I1500100020001200II1500150012001500III1000200015002500该三种产品l季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时为15000小时，生产I、产品每件分别需时2、4、3小时。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I，每件每迟交一个季度赔偿20元，产品赔偿10元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5元。问：该厂应如何安排生产，使总的赔偿加库存的费用为最小(要求建立数学模型，不需求解)。1.16 某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已知技工和力工每周工资