运筹学2011春总复习

1 运筹学期末总复习运筹学期末总复习 第第 1 章章 线性规划及其对偶问题线性规划及其对偶问题 数学建模数学建模 建模步骤 建模步骤 1 科学选择决策变量 2 找出所有约束条件 3 明确目标要求 4 非负变量的选择 单纯形法 单纯形法 例题 1 某旅馆在不同时段所需服务员数如表所示 每班服务员从开始上班到下班连续工作 8 小时 为满足每班所需要的最少服务员数 这个 旅馆至少需要多少服务员 列出该问题线性规划模型 不求解 时间段最少服务员数 106 00 10 0020 210 00 14 0030 314 00 18 0025 418 00 22 0030 522 00 02 0010 602 00 06 0010 例题 2 用单纯形法求解线性规划问题 1 2 123 123 12 1 3 max524 345 6340 0 zxxx xxx stxx x 123 123 123 1 3 max225 2315 2520 0 zxxx xxx stxxx x 练习 1 某厂利用原料 A B 生产甲 乙 丙 3 种产品 已知生产单位产品所需原料 数 单件利润及有关数据如表所示 试建立该问题线性规划模型 并用单纯形法求解 2 甲乙丙原料拥有量 A B 6 3 3 4 5 5 45 30 单件利润415 练习 2 求解 LP 1 2 1 12 12 12 max45 228 3210 0 zx xx stxx x x 123 123 123 1 3 max524 3245 63560 0 zxxx xxx stxxx x 第第 2 章章 整数规划与分配问题整数规划与分配问题 0 1 变量的用法及建模变量的用法及建模 理解 0 1 变量的用途 其中 1 4 重点掌握 1 n 中取 k 1 0 1 n jj j xkx 或 n 中至少取 k 改为 1 0 1 n jj j xkx 或 n 中最多取 k 改为 1 0 1 n jj j xkx 或 2 变量取离散数值 1 1 1 01 m ii i m ii i xc y yy 或 3 选甲必须选乙 选乙不一定选甲 或 1 xxxx 乙乙甲甲 0 4 选了甲或乙 丙就不能入选 选了丙 甲 乙都不能入选 1 1 xx xx xxx 甲丙 乙丙 乙甲丙 0或1 5 两个约束条件只需满足一个 或 121 122 1212 2 3210 1 01 xxy M xxy M yyy y 或 12 12 2 1 3210 01 xxy M xxyM y 或 式中 M 为任意大正数 6 n 个约束条件中满足 k 个 3 1 1 1 2 01 m i jjii j n ii i a xby Min ynky 或 7 若 则 否则 4 2 x0 5 x4 2 x3 5 x 或 Myx Myx Myx Myx 25 22 15 12 3 4 0 4 1 0 1 2 1 21 y yy Myx Myx yMx yMx 1 3 1 4 0 4 5 2 5 2 1 0 y 8 对 可表述为 0 0 0 x f x kcxx 当 当 f xykcx yMx xMy 例题 1 某公司有 5000 万元可用于投资 有 6 个投资方案 其投资额 安排员工数和年 利润额如表所示 方案投资额 万元 可安排员工数 人 年利润额 万元 1200050150 2200060200 33500100150 4100020100 54000100200 6150050100 要求 1 投资额不超过 5000 万元 2 至少安排 150 人员就业 3 年利润额尽可能地多 试建立该问题 0 1 规划数学模型 不求解 例题 2 某企业接受订货 产品需求量为 6000 公斤 可由 3 种设备进行生产 其成本与 产量如下 设备设备调整费 元 生产成本 元 公斤 生产能力 公斤 A B C 2000 2500 3000 6 5 4 3000 4000 5000 企业如何组织生产才能使总成本最小 试列出该问题的整数规划数学模型 不求解 例题 3 集合覆盖问题 某区有城区有 10 个街道 欲建消防站 有下列 6 个地点可供选 择 在规定时间可到达的地点如下表 问应设几个 可以以最少数量的消防站可满足消防 任务的需要 建模 不求解 4 备选校址代号覆盖的居民小区编号 A B C D E F 1 5 7 1 2 5 8 1 3 5 2 4 5 3 6 8 4 6 8 例题 4 练习 1 某校排球队准备从以下 8 名预备队员中选拔 4 名正式队员 并使平均身高尽可 能高 这 8 名预备队员情况如下表所示 预备队员号码身高 厘米 位置 A B C D E F G H 1 2 3 4 5 6 7 8 197 194 189 196 188 180 183 185 主攻 主攻 副攻 副攻 二传 二传 接应 接应 要求 1 8 名预备队员选 4 名 2 最多补充 1 名主攻 3 最多补充 1 名副攻 4 至少补充 1 名二传 5 至少补充 1 名接应 6 A 和 E 只能入选 1 名 7 无论 B 或 D 入选 A 都不能入选 5 建立数学模型 不求解 匈牙利法匈牙利法 例题 6 用匈牙利法求解分配问题 1 2 37333837 43334234 33293930 30262929 C 181619 211820 19181721 102019 M M C M 练习 2 用匈牙利法求解分配问题 1 2 46810 7357 2326 8677 C 127999 89777 71112129 151414710 4101079 C 例题 7 某公司准备资金 600 万元 以 100 万元为单位 有四项可选择投资的工程 A B C D 现决定每项工程至少要投资 100 万元 各项工程投资不同资金后可获得的 期望利润如下 利润分配的 投资金额 工程 A工程 B工程 C工程 D 100150167164158 200169189190185 300185204226215 试确定如何安排对各项工程的投资数 可使获得的总期望利润最大 第第 3 章章 运输问题运输问题 6 数学模型数学模型 1 产销平衡运输问题数学模型 11 1 1 min 1 2 1 2 0 mn ijij ij n iji j m ijjij i zc x xaim st xbjn x 2 产销不平衡的运输问题标准化 表上作业法表上作业法 7 例题 1 1 由表上作业法求最优解 2 单位运价 c11 在什么范围变动 最优基 不变 例题 2 标准化如下运输问题 练习 1 求下题最优解 最优解唯一吗 8 第第 4 章章 目标规划目标规划 例题 某公司通过混合牛肉 猪肉 羊肉和水淀粉生产香肠 下表给出数据资料 该公司需要生产 200 公斤香肠 并按优先顺序制订下列目标 练习 某公司计划生产甲 乙两种产品 它们分别要经过设备 A 和设备 B 两道工序的 加工 其所需工时定额如下表 产品 工序 甲 小时 千克 乙 小时 千克 有效工时 小时 设备 A 设备 B 5 2 3 7 80 72 单位盈利100 元 千克120 元 千克 系统约束 两种设备已满负荷 不能加班 目标要求 P1 盈利达到 150 元 并尽可能地超过 P2 两种产品的产量之和尽可能超过 10 千克 P3 产品乙不少于 6 千克 试建立此问题的数学模型 不求解 9 第第 6 章章 图与网络模型图与网络模型 基本方法基本方法 最小支撑树的避圈法与破圈法 最短路的 dijkstra 标号算法 最大流的 Ford Fulkerson 标号算法 中国邮路问题 结论 1 若无奇点 则邮递员可以走遍所有街道 做到每条街道只走一次而不重复 结论 2 1 有奇点的连线的边最多重复一次 2 在该网络图的每个回路上 有重复的边的长度不超过回路总长的一半 例题 1 用避圈法或破圈法求下图所示最小支撑树 例题 2 用 dijkstra 标号算法求上图所示从 v1 到 v12 的最短路 例题 3 求解上图中国邮路问题 例题 4 求 v1 到 v8 最大流 练习 1 1 求下图最小支撑树 2 求下图 v1 到 v7 最短路 3 求下图中国邮 路问题 10 练习 2 求例 4 中从 v1 到 v8 最短路问题 第第 8 章章 对策论对策论 矩阵对策最优纯策略 矩阵对策最优纯策略 超优原则或最大最小原则 练习 求赢得矩阵 A 的最优纯策略 1234 1 2 3 4 2344 6425 4333 2324 A 第第 9 章章 决策分析决策分析 不确定型决策 不确定型决策 乐观主义准则 悲观主义准则 等概率准则 乐观系数法 最小后悔值准 则 例题 已知面对四种自然状态的三种备选行动方案的公司收益如下表所示 自然状态 方案 N1N2N3N4 S11580 6 S241483 S3141012 假定不知道各种自然状态出现的概率请分别用乐观准则 悲观准则 乐观系数准则 取 0 6 等概率准则和最小后悔值准则选择最优行动方案 练习 根据以往的资料 一家面