1、运筹学习题集二 习题一 1.1 用法求解下列线性规划问题并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 (1) min z 6x1 4x2 (2) max z 4x1 8x2 st. 2x1 x2 1 st. 2x1 2x2 10 3x1 4x2 1.5 x1 x2 8 x1, x2 0 x1, x2 0 (3) max z x1 x2 (4) max z 3x1 2x2 st. 8x1 6x2 24 st. x1 x2 1 4x1 6x2 12 2x1 2x2 4 2x2 4 x1, x2 0 x1, x2 0 (5) max z 3x1 9x2 (6) max z 3x1
2、4x2 st. x1 3x2 22 st. x1 2x2 8 x1 x2 4 x1 2x2 12 x2 6 2x1 x2 16 2x1 5x2 0 x1, x2 0 x1, x2 0 1.2. 在下列线性规划问题中找出所有基本解指出哪些是基本可行解并分别代入目标函数比较找出最优解。 (1) max z 3x1 5x2 (2) min z 4x1 12x2 18x3 st. x1 x3 4 st. x1 3x3 x4 3 2x2 x4 12 2x2 2x3 x5 5 3x1 2x2 x5 18 xj 0 （ j 1, ,5） xj 0 （ j 1, ,5） 1.3. 分别用法和单纯形法求解下列线
3、性 规划问题并对照指出单纯形法迭代的每一步相当于法可行域中的哪一个顶点。 (1) max z 10x1 5x2 st. 3x1 4x2 9 5x1 2x2 8 x1, x2 0 (2) max z 100x1 200x2 st. x1 x2 500 x1 200 2x1 6x2 1200 x1, x2 0 1.4. 分别用大 M 法和两阶段法求解下列线性规划问题并指出问题的解属于哪一类： (1) max z 4x1 5x2 x3 (2) max z 2x1 x2 x3 st. 3x1 2x2 x3 18 st. 4x1 2x2 2x3 4 2x1 x2 4 2x1 4x2 20 x1 x2 x
4、3 5 4x1 8x2 2x3 16 xj 0 （ j 1,2,3） xj 0 （ j 1,2,3） (3) max z x1 x2 (4) max z x1 2x2 3x3 x4 st. 8x1 6x2 24 st. x1 2x2 3x3 15 4x1 6x2 12 2x1 x2 5x3 20 2x2 4 x1 2x2 x3 x4 10 x1, x2 0 xj 0 （ j 1, ,4） (5) max z 4x1 6x2 (6) max z 5x1 3x2 6x3 st. 2x1 4x2 180 st. x1 2x2 x3 18 3x1 2x2 150 2x1 x2 3x3 16 x1 x2
5、 57 x1 x2 x3 10 x2 22 x1, x2 0x3 无约束 x1, x2 0 1.5 线性规划问题 max z CXAX bX 0如 X*是该问题的最优解又0 为某一常数分别讨论下列情况时最优解的变化： （ 1） 目标函数变为 max z CX； （ 2） 目标函数变为 max z（ C） X； （ 3） 目标函数变为 max z X 约束条件变为 AX b。 1.6 下表中给出某求极大化问题的单纯形表问表中 a1, a2, c1, c2, d 为何值时以及表中变量属于哪一种类型时有： （ 1） 表中解为唯一最优解； （ 2） 表中解为无穷多最优解之一； （ 3） 表中解为退化的
6、可行解； （ 4） 下一步迭代将以 x1 替换基变量 x5 ； （ 5） 该线性规划问题具有无界解； （ 6） 该线性规划问题无可行解。 x1 x2 x3 x4 x5 x3 d 4 a1 1 0 0 x4 2 1 5 0 1 0 x5 3 a2 3 0 0 1 cj zj c1 c2 0 0 0 1.7 战斗机是一种重要的作战工具但要使战斗机发挥作用必须有足够的驾驶员 。因此生产出来的战斗机除一部分直接用于战斗外需抽一部分用于驾驶员。已知每年生产的战斗机数量为 aj（ j 1, ,n）又每架战斗机每年能出 k 名驾驶员问应如何分配每年生产出来的战斗机使在 n 年内生产出来的战斗机为空防作出最大
7、贡献？ 1.8. 某石油管道公司希望知道在下图所示的管道络中可以流过的最大流量是多少及怎样输送弧上数字是容量限制。请建立此问题的线性规划模型不必求解。 2 5 4 10 3 11 1 4 3 6 5 6 8 7 3 5 1.9. 某昼夜服务的公交线每天各时间区段内所需司机和乘务人员数如下： 班次时间所需人数 1 6:00-10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 50 5 22:00-2:00 20 6 2:00-6:00 30 设司机和乘务人员分别在各时间区段一开始时上班并连续工作八小时问该公交线至少配备多少名司机和乘务
8、人员。列出此问题的线性规划模型。 1.10 某班有男生 30 人女生 20 人周日去植树。根据经验一天男生平均每人挖坑 20 个或栽树 30 棵或给 25 棵树浇水；女生平均每人挖坑10 个或栽树 20 棵或给 15 棵树浇水。问应怎样安排才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线 性规划模型不必求解。 1.11.某糖果用原料 A、 B、 C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中 A、 B、 C含量原料成本各种原料的每月限制用量三种牌号糖果的单位加工费及售价如下表所示。 问该每月应生产这三种牌号糖果各多少千克使该获利最大？试建立此问题的线性规划的数学模型。 甲乙丙
9、原料成本 (/千克 ) 每月限量（千克） A 60 15 2.00 2000 B 1.50 2500 C 20 60 50 1.00 1200 加工费（ /千克） 0.50 0.40 0.30 售价 3.40 2.85 2.25 1.12. 某商店制定 7 12 月进货售货计划已知商店仓库容量不得超过500件 6月底已存货 200件以后每月初进货一次假设各月份此商品买进售出单价如下表所示问各月进货售货各多少才能使总收入最多？请建立此问题的线性规划模型不必求解。 月份 7 8 9 10 11 12 买进单价 28 24 25 27 23 23 售出单价 29 24 26 28 22 25 1.1
10、3 .某农场有 100 公顷土地及 15000 资金可用于发展生产。农场劳动力情况为秋冬季 3500人日春夏季 4000人日如劳动力本身用不了时可外出干活春夏季收入为 2.1人日秋冬季收入为 1.8人日。该农场种植三种作物：大豆、玉米、小麦并饲养奶牛和鸡。种作物时不需要专门投资而饲养动物时每头奶牛投资 400每只鸡投资 3。养奶牛时每头需拨出 1.5公顷土地种饲草并占用人工秋冬季为 100人日春夏季为50人日年净收入 400每头奶牛。养鸡时不占土地需人工为每只鸡秋冬季需 0.6 人日春夏季为 0.3 人日年净收人为 2每只鸡。农场现有鸡舍允许最多养 3000 只鸡牛栏允许最多养 32 头奶牛。
11、三种作物每年需要的人工及收人情况如下表所示。 大豆 玉米 麦子 秋冬季需人日数 20 35 10 春夏季需人日数 50 75 40 年净收入 (公顷 ) 175 300 120 试决定该农场的经营方案使年净收人为最大。 (建立线性规划模型不需求解 ) 习题二 2.1 写出下列线性规划问题的对偶问题 (1) max z 10x1 x2 2x3 (2) max z 2x1 x2 3x3 x4 st. x1 x2 2 x3 10 st. x1 x2 x3 x4 5 4x1 x2 x3 20 2x1 x2 3x3 4 xj 0 （ j 1,2,3） x1 x3 x4 1 x1x3 0x2x4 无约束
12、(3) min z 3x1 2 x2 3x3 4x4 (4) min z 5 x1 6x2 7x3 st. x1 2x2 3x3 4x4 3 st. x1 5x2 3x3 15 x2 3x3 4x4 5 5x1 6x2 10x3 20 2x1 3x2 7x3 4x4 2 x1 x2 x3 5 x1 0x4 0x2x3 无约束 x1 0 x2 0x3 无约束 2.2 已知线性规划问题 max z CXAX=bX 0。分别说明发生下列情况时其对偶问题的解的变化： （ 1）问题的第 k个约束条件乘上常数（ 0）； （ 2）将第 k 个约束条件乘上常数（ 0）后加到第 r个约束条件上； （ 3）目标函
13、数改变为 max z CX（ 0）； （ 4）模型中全部 x1用 3 代换。 2.3 已知线性规划问题 min z 8x1 6x2 3x3 6x4 st. x1 2x2 x4 3 3x1 x2 x3 x4 6 x3 x4 2 x1 x3 2 xj 0（ j 1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为 x*（ 1120）试根据对偶理论直接求出对偶问题的最优解。 2.4 已知线性规划问题 min z 2x1 x2 5x3 6x4 对偶变量 st. 2x1 x3 x4 8 y1 2x1 2x2 x3 2x4 12 y2 xj 0（ j 1,2,3,4） 其对偶问题的最优解
14、 y1*=4； y2*=1 试根据对偶问题的性质求出原问题的最优解。 2.5 考虑线性规划问题 max z 2x1 4x2 3x3 st. 3x1 4 x2 2x3 60 2x1 x2 2x3 40 x1 3x2 2x3 80 xj 0 （ j 1,2,3） （ 1）写出其对偶问题 （ 2）用单纯形法求解原问题列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （ 3）用对偶单纯形法求解其对偶问题并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （ 4）比较（ 2）和（ 3）计 算结果。 2.6 已知线性规划问题 max z 10x1 5x2 st. 3x1 4x2 9 5x1 2x2 8 xj 0（ j 1,2）
