运筹学运筹演示2.ppt

复习第一章 第二章内容例1 某工厂生产 两种型号计算机 为了生产一台 型和 型计算机 所需要原料分别为2个单位和3个单位 需要的工时分别为4个单位和2个单位 在计划期内可以使用的原料为100个单位 工时为120个单位 已知生产每台 型计算机可获利6个单位和4个单位 试确定获利最大的生产方案 求解线性规划的方法 1 图解法2 单纯形法3 大M法4 对偶单纯形法例2 minZ 15x1 24x2 5x36x2 x3 25x1 2x2 x3 1x1 x2 x3 0 第三章运输问题第一节平衡运输问题的数学模型运输问题的提出例 某公司经销甲产品 该产品有三个加工厂 产量分别为7 4 9吨 该产品有四个销售地点 销售量为3 6 5 6吨 已知单位定价 问如何在满足各销售点的需求量的前提下 使花费最小 一般运输问题的提出 某种物资有m个产地A1 A2 Am 其产量分别为a1 a2 am 有n个销地B1 B2 Bn 其销量分别为b1 b2 bm 现需要把这种物资从各个产地运往各个销地 假设产销平衡 ai bj 且每个产地到每个销地的单位货物运价为Cij 问如何调运 才能使总的运费最省 已知有m个生产地点Ai i 1 2 m 其产量分别为ai 有n个销售地点Bj j 1 2 n 其销量分别为bj 假设产销平衡 且从Ai到Bj运输单位物资运价为Cij 可以汇总数据得到产销平衡表 第二节表上作业法一 基本概念1 闭回路 从起点出发经过另外几个点回到始点的变量集合 2 数字格 基格 在调运方案中 分配运输量的基变量的格 3 空格 在调运方案中 没分配运输量的非基变量的格 4 性质 运输问题的基变量的个数是约束条件的个数减一 即m n 1个 二 表上作业法的基本步骤1 编制初始方案 确定初始可行解 使用方法 最小元素法 伏格尔法 2 最优性检验使用方法 闭回路法 位势法 3 方案的调整使用方法 闭回路法 例 某公司经销甲产品 该产品有三个加工厂 产量分别为7 4 9吨 该产品有四个销售地点 销售量为3 6 5 6吨 已知单位定价 问如何在满足各销售点的需求量的前提下 使花费最小 最小元素法 第二节产销不平衡的运输问题1 产量 销量 虚设一个销地Bn 1 其销地的销量为bn 1 a b 在令各产地到虚拟销地的单位运价为Cin 1 0 i 1 2 m 2 产量 销量 虚设一个产地Am 1 其产地的产量为am 1 b a 在令虚拟产地到各销地的单位运价为Cm 1j 0 j 1 2 n 例 例 已知某运输问题 要求B地区的115个单位必须满足 试求最优的调运方案 例 某化学公司有4个化工厂生产某种产品 产量分别为200 300 400 100吨 供应6个地区的需要 需求量分别为200 150 400 100 150 150吨 由于工艺技术条件的差别有关数据如表所示 要求第三个地区至少供应300单位 第四个地区需要必须满足 试确定该公司获利最大的产品调运方案 运输问题应用 一 生产计划问题某拖拉机厂与某单位签订了生产70台某种型号拖拉机的合同 按合同规定明年每个季度末分别提供10 15 25 20台拖拉机 已知该厂各季度的生产能力及生产每台拖拉机的成本如表所示 如生产出来的拖拉机当季度不交货 每台每积压一个季度需要储存维护费用0 15万元 问该厂怎样安排各季度生产计划 既完成合同又使得总费用最少 二 资源短缺问题 第四节指派问题一 问题的提出有n个人去完成n项任务 每个人只能完成一项任务 且每项任务只能由一个人来完成 每人完成各项任务的效率不同如表 问如何分派任务 才能使总时间最少 二 匈牙利法的基本思想对于同一个人来说 所有的任务的完成效率都提高或降低同一个常数ti 不会影响最优分配 同样对同一个任务来说 让所有人去完成的效率都提高或降低同一常数dj也不会影响其最优分配 从而得到新的效率矩阵为bij cij ti dj 例1 有一份中文说明书 需要翻译成英日德三种文字 记作E J G 有甲 乙 丙三个人他们将中文说明书翻译成不同语种的说明书所需要的时间如表所示 问应指派何人去完成何工作 使所需总时间最短 1 对指派问题的系数矩阵进行变换 使每行每列都出现0元素2 进行试指派 找出独立的0元素 行搜索 从只有一个0元素的行开始 给这个0划圈 并划去该元素所在列的其他0元素 列搜索 从只有一个0元素的列开始 给这个0划圈 并划去该元素所在行的其他0元素 反复行列搜索 直到所有的0元素圈上和划去为止 3 若独立0元素个数 方阵的阶数 则已经找到最优方案 反之 转下步 4 求覆盖0元素的最小直线集合 1 对没有圈0的行的右边打 2 对打 的行上所有0元素的下方打 3 对打 的列上有圈0的行的右边打 4 对没有打 的行划横线 对打 的列划垂线 5 确定调整量 在没有被直线覆盖的部分中找到最小元素Q 没有被直线覆盖的元素 Q 一次被直线覆盖的元素不变 二次被直线覆盖的元素 Q 例2 例3 例4 例5 某公司计划开5家商店 为了尽早完成建设 决定由3家建筑公司分别承建 已知建筑公司Ai i 1 2 3 对新商店Bj j 1 2 3 4 5 的建造费用的报价 商业公司应对3家建筑公司怎样分配建造任务 才能使总的建筑费用最少 允许每家建筑公司承建1 2家商店的建设 0 1整数规划问题1 投资问题 设有n个投资项目 其中第j个项目需要资金aj万元 将来可获得利润cj万元 若现在资金总额为b万元 则应选择哪些投资项目才能获得利润最大 2 背包问题 一个旅行者要在其背包里装一些最有用的旅行物品 背包容积为a 携带物品总重量最多为b 现有物品m件 第i件物品体积为ai 重量为bi i 1 2 m 为了比较物品的有用程度 假设第i件物品的价值为ci 若每件物品只能整件携带 每件物品都能放入背包中 并且不考虑物品放入背包的相互间隙 问旅行者应带携带哪些物品 才能使携带物品的总价值最大 第五章动态规划多阶段决策问题 指这样一类决策过程 它可以把复杂问题按照时间或空间分成若干阶段 每个阶段都需要进行决策 以便得到过程的最优结局 动态规划的基本概念 1 阶段 一个问题需要进行决策的步数 K 1 2 n2 状态 是各个阶段之间信息的传递点和结合点 第k阶段的状态xk表示 3 决策 决策者面临不同选择而作出最后的选择 第k阶段xk状态下的决策用uk xk 表示 允许决策集合 决策变量的取值往往限制在某一范围内 此范围称为允许决策集合 4 状态转移方程 由一个状态到另一个状态的演变过程 5 全过程 由第一阶段开始到终点为止 子过程 由第k阶段开始到终点为止 6 指标函数 用来衡量过程优劣的效益值 阶段指标函数 对应某一阶段的效益值vk 过程指标函数 子过程的效益值vk n 7 最优解 第k子过程指标函数在xk状态下的最优值 用fk xk 表示 最优化原理 作为整个的最优策略具有这样的性质 无论过去的状态和决策如何 对前面形成的状态而言 余下的诸决策必构成最优策略 动态规划的运算步骤 1 将问题按时间和空间的顺序划分若干阶段 2 正确选择状态变量 3 确定决策变量和允许决策集合 4 写出状态转移方程 5 建立指标函数 6 建立基本方程 例 追加投资问题 某公司有四百万元 可以向ABC三个项目追加投资 不同投资额的相应效益如表 问怎样分配资金使总效益值最大 例 某警卫部门共有12只巡逻队负责4个要害部位的巡逻 对每个部位可分派2 4个巡逻队 并且巡逻队数不同 各部位预期在一段时间内可能造成的损失有差别 问该警卫部门应往各部位分派多少巡逻队 使总预期损失最小 例 生产计划问题 某厂与一用户签定合同 在4个月内出售一定数量的某种产品 工厂每月最多生产100个单位 产品可以存储 存储费为每月每单位2元 要求四个月末存储量为0 每月需要量与单位产品成本如表 现确定每月的生产量 要求既满足每月的合同要求又使费用最少 K 1 2 3 4Xk 第k阶段拥有的产品数 存货 Uk 第k阶段的产量Ck 第k阶段的单位成本dk 第k阶段的需求量状态转移方程Xk 1 Xk Uk dk 例 某系统有3个工作部件 ABC串联而成 3个部件的工作是相互独立 据统计资料 各部件的故障率A为0 3 B为0 2 C为0 4 如果三个环节各自配备一个部件 则系统正常工作概率 P 1 0 3 1 0 2 1 0 4 0 336现管理部门决定各环节除工作部件外 可增设备用部件 以提高系统的可靠性 用语购买部件的金额为10万元 各部件的单价A为2万元 B为3万元 C为1万元 问三个环节各应配备多少个部件 才能使系统的正常工作概率达到最大 练习1 匈牙利法 AB1C2D1E2F2G 0 4 3 7 5 9 7 6 8 13 10 9 12 13 18 18 某厂根据市场预测 确定今后四个月该厂的一种主要产品每月需求量如表 已知每月生产固定费用为2千元 但若当月不生产则为0 产品成本为1千元 万件 存储费用为0 2千元 万件 月 每月最大生产能力为5万件 最大存储能力为4万件 若第一月初无库存产品 第四月末也不留库存 则该厂应怎样安排生产 才能使今后四个月的总费用最少 练习3 K 4 K 3 K 2K 1则第1个月生产5万件 第2个月不生产 第3个月生产5万件 第4个月不生产 哥尼斯堡七桥 一笔画问题 第六章图论与网络分析 欧拉 数学家 有六支球队进行足球比赛 我们分别用点v1 v6表示这六支球队 它们之间的比赛情况 也可以用图反映出来 已知v1队战胜v2队 v2队战胜v3队 v3队战胜v5队 如此等等 这个胜负情况 可以用有向图反映出来 v3 v1 v2 v4 v6 v5 第一节图的基本概念一 概念定义1 图 点和边的集合 G V E V v1 v2 vp E e1 e2 eq 定义2 1 顶点数和边数集合V的元素个数成为图G的顶点数 记作P G 集合E的元素个数成为G的边数 记作q G 2 端点 关联边若e vi vj 则称vi vj为边e的端点 e为vi vj的关联边 例 图1 3 环 多重边如果边e的两个端点重合 则称该边为环 如果两点之间多一条边 则称具有多重边 4 次 奇点 偶点 孤立点 悬挂点次 以点V为端点的边的条数称为点V的次 记做d v 奇点 次为奇数的点 偶点 次为偶数的点 孤立点 次为0的点 悬挂点 次为1的点 定理1 图G中 所有顶点的次的和等于所有边数的2倍 定理2 在任意图中 奇数点的个数是偶数个 定义3 链 路 圈 回路链 图中某些点和边交替序列 路 链中点不重复 回路 起点和终点重合的链 圈 回路中的点和边都不重复 定义4 连通图在一个图中任意两点之间存在一条链 定义5设G1 V1 E1 G2 V2 E2 如果V2 V1 E2 E1称G2是G1的子图 如果V2 V1 E2 E1称G2是G1的支撑子图 例1 已知九个人v1 v2 v9中的v1和两个人握过手 v2 v3各和四个人握过手 v4 v5 v6 v7各和五个人握过手 v8 v9各和六个人握过手 证明 九个人中一定可以找到三个人相互握过手 例2 10名研究生参加6门课程的考试 由于选修课不同 考试的门数也不一样 表中给出了每个研究生参加考试的课程 用 表示 规定考试要在三天内结束 每天上午 下午各安排一门 研究生提出希望每人每天只考一门 又课程A必须安排在第一天上午考 课程F必须安排在最后一门 课程B只能安排在下午考 试列出一张满足各方面要求的考试日程表来 第二节树与图的最小支撑树一 树的基本性质定义 无圈的连通图称为树T 已知有六个城市 它们之间要架设电话线 要求任意两个城市均可以互相通话 并且电话线的总长度最短 性质1 树中任意两点之间必有且仅有一条链 性质2 树中任意去掉一条边必成为不连通图 性质3 树中不相邻两点间填上一条边必成为一个圈 性质4 具有P个顶点的树 边数恰好为P 1个 性质5 任何具有P个顶点 P 1条边的连通图是树 二 图的支撑树赋权图 对于图G V E 对G的每条边 vi vj 相应有一数Wij 则称这样的图为赋权图 称Wij为边 vi vj 上的权数 最小支撑树 求树T 使W T 达到最小 两种方法求最小树 避圈法 破圈法 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 破圈法 任选一个圈 从圈中去掉权最大的一条边 在余下的图中重复这个步骤 直到得到一不含圈的图为止 v3 v2 1 v4 2 v5 3 v6 4 v1 5 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 避圈法 开始选一条权最小的边 以后每一步中 总从未被选取的边中选一条权尽可能小 且与已选边不构成圈的边 第三节最短路问题一 Dijkstra算法 TP标号法 基本思路 假想流具体步骤 1 标P Vs 0 其余点标T Vi 2 由刚刚获得P标号的Vi点出发 改善它的相邻点Vj的T标号 即T Vj min T Vj P Vi Wij 3 找出具有最小T标号 将其标号改为P标号 若Vt已经获得P标号 则已经找到最短路 v1 v2 v3 v6 v4 v5 v7 2 3 5 7 2 1 5 3 1 7 5 5 v1 v2 v5 v4 v3 v6 v7 v8 3 5 5 1 3 5 1 5 2 7 6 9 1 例某企业要制定一个五年之内更新某种设备的计划 已知该种设备在各年年初的价格如表 还已知使用不同年的设备所需要的维修费 试确定使总支出费用最小的设备更新方案 W12 11 5 16W13 11 5 6 22W14 11 5 6 8 30W15 11 5 6 8 11 41W16 11 5 6 8 11 18 59 W23 11 5 16W24 11 5 6 22W25 11 5 6 8 30W26 11 5 6 8 11 41 W45 12 5 17W46 12 5 6 23W56 13 5 18 W34 12 5 17W35 12 5 6 23W36 12 5 6 8 31 第四节网络最大流一 基本概念和基本定理1 容量网络 在有向图D V A 中 指定一个点 称为发点记做Vs 指定另一收点记做Vt 其余点叫做中间点 对于A的每条弧 Vi Vj 都对应一个权数Cij 0 称为弧 Vi Vj 的容量 将这样的赋权有向图叫做一个容量网络 记做D V A C 2 可行流 对于容量网络D每条弧 Vi Vj 都给定一个流量fij 当 fij 满足以下条件 该流为可行流 1 容量限制 0 fij cij 2 平衡条件 对于中间点Vi 流入量 流出量 流量 可行流的流量称为V f 最大流 使V f 达到最大的可行流 3 割集 将容量网络中的发点和收点割开 是Vs到Vt的流中断的一个弧的集合 割集的容量 割量 割集中所有弧的容量之和成为这个割集的容量 定理1 任一容量网络D V A C 中从Vs到Vt的最大流量等于它的最小割集容量 二 计算最大流的标号法1 相关概念 1 前向弧 后向弧