运筹学胡运权第五版课件

《运筹学胡运权第五版课件》由会员分享，可在线阅读，更多相关《运筹学胡运权第五版课件（90页珍藏版）》请在金锄头文库上搜索。

1、运 筹 学 Operations Research 一 古代朴素的运筹学思想 例如 田忌赛马 二 运筹学的起源 国外 英文原名 Operations Research 简称 O R 直译为 运用研究或作业研究 正式出现于1938年7月英国一份关于防空作战系统运 行的研究报告中 二战后运筹学的发展经历了三个阶段 绪 论 国内 1956年成立第一个运筹学小组 1957年从 夫运筹策帷幄之中 决胜于千里之外 中 摘取 运筹 二字 将O R 正式翻译为 运筹学 三 运筹学的定义 研究工具 数学 计算机科学及其他相关科学 研究目的 对有限资源进行合理规划 使用 并提供 优化决策方案 研究对象 复杂系统的

2、组织和管理 参考 大英百科全书 辞海 中国企业管理百科全书 等 四 运筹学研究的基本特点 系统的整体优化 多学科的配合 模型方法的应用 五 运筹学研究的基本步骤 分析与表述问题 建立数学模型 对问题求解 对模型和模型导出的解进行检验 建立对解的有效控制 方案的实施 六 本课程的主要学习内容 第一章 线性规划及单纯形法 第二章 线性规划的对偶理论 第三章 运输问题 第四章 整数规划与分配问题 第六章 图与网络分析 第一章 线性规划及单纯形法 Linear Programming and Simplex Method x a 此为无约束的极值问题 1 1 一般线性规划问题的数学模型 1 1 问题的

3、提出 例1 用一块边长为a的正方形铁皮做一个无盖长方体容器 应如何裁剪可使做成的容器的容积最大 解 如图设四个角上减去的小正方形边 长为x 则容器体积为 时 容积最大 例2 常山机器厂生产 I II 两型产品 这两型 产品都分别要在A B C三种不同设备上加工 按 工艺规定 生产每件产品的单位利润 消耗三种设 备的工时以及各种设备工时的限额如下表 如何安排生产才能使总的利润最大 如何安排生产才能使总的利润最大 单单位产产品消耗 设备设备 工时时 III设备设备 工时时限量 小时时 设备设备 A 设备设备 B 设备设备 C 2 4 0 2 0 5 12 16 15 单单位利润润 元 23 解 设

4、计划期内两种产品的数量分别为x1 x2 则总利润为 maxz 2 x1 3 x2 2 x1 2 x2 12 4x1 16 5 x2 15 x1 0 x2 0 简记为 s t 约束于 z 2 x1 3 x2在满足限制条件下求z的最大值 此为有约束极值问题 1 2 线性规划问题的数学模型 原型模型 数学模型 提炼数学工具 1 原型 现实世界中人们关心 研究的实际对象 模型 将某一部分信息简缩 提炼而构造的原型替代物 数学模型 对现实世界的一个特定对象 为达到一定目的 根据内在规律做出必要的简化假设 并运用适当数学工具得 到的一个数学结构 3 规划问题数学模型的三要素 2 目标函数 问题要达到的目标

5、要求 表示为决策变量的 函数 用 z f x1 x2 xn 表示 1 决策变量 决策者为实现规划目标采取的方案 措施 是问题中要确定的未知量 用x1 x2 xn表示 3 约束条件 决策变量取值时受到的各种可用资源的限制 表示为含决策变量的等式或不等式 2 规划问题 即求目标函数在若干约束条件下的最值 4 线性规划问题 Linear Programming 的数学模型 2 一般形式 1 条件 决策变量为可控的连续变量 目标函数和约束条 件都是线性的 简记为 L P max 或 min z c1x1 c2x2 cnxn s t a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2

6、nxn b2 am1x1 am2x2 amnxn bm x1 x2 xn 0 3 其他形式 连加形式 向量形式 其中 称为价值行向量 决策列向量系数列向量右端列向量 矩阵形式 其中 称为价值行向量 决策列向量右端列向量约束矩阵或系数矩阵 1 3 线性规划问题的标准形式 1 标准形式 或 2 条件 目标函数求极大值 约束条件全是等式 线性方程组 决策变量全非负 右端常数全非负 3 标准化方法 1 若目标函数求极小值 即 则令 转化为 2 若约束条件为不等式 则依次引入松弛变量或剩余变量 统称为松弛变量 转化为等式约束条件 注意 松弛变量在目标函数中系数全为0 约束为 不等式 减去松弛变量 化为等

7、式约束条件 约束为 不等式 加上松弛变量 化为等式约束条件 多退少补 例 max z 2 x1 3 x2 2 x1 2 x2 12 4x1 16 5 x2 15 x1 0 x2 0 s t 标准化 3 若决策变量xj 0 则令 4 若决策变量xj取值无限制 则令 5 若约束等式的右端常数bi 0 则等式两边同时乘以 1 其中 一分为二 例 将下列线性规划模型化为标准形式 则问题化为标准形式 并引入松弛变量x4 x5 1 4 线性规划问题的解 已知线性规划的标准形式 或 1 求解线性规划问题 从满足 2 3 的方程组中找出一个解使目标函 数 1 达到最大值 2 可行解 所有可行解的集合 可行域

8、满足约束条件 2 3 的解 记做 最优解 使目标函数达到最大值的可行解 1 基 设A为线性规划问题约束条件的 m n 系数矩阵 m0 有如下结论 1 若对所有j m 1 有 j 0 则z 1 z 0 即z 0 为 最优函数值 X 0 为唯一最优解 2 若对所有j m 1 有 j 0 且存在某个非基变量的检验数 k 0 则将Pk作为新的基向量得出新的基可行解X 1 满足z 1 z 0 故z 1 也为最优函数值 从而 X 1 也为最优解 X 0 X 1 连线上所有点均为最优解 因此该线性规 划模型具有无穷多最优解 3 若存在某个 j 0 但对应的第j列系数全非正 即aij 0 则 当 时 有z 1

9、 该线性规划模型具有无界解 1 4 单纯形法的计算步骤 1 前提 标准化的线性规划问题的系数矩阵含有单位子矩阵 不妨假设A中前m列对应的子矩阵是单位 矩阵 取其为基B 得到初始基可行解 m 3行 n 4列 第1行 价值行 cj 第2行 变量行 xj 最后一行 检验数行 j 第1列 基价值列 CB 第2列 基变量列 XB 第3列 基解列 b 最后一列 比值列 主体 系数矩阵Am n 2 单纯形表的结构 3 初始单纯形表 含初始基可行解的单纯形表 最优单纯形表 含最优解的单纯形表 4 单纯形法 Simplex MethodSimplex Method 利用单纯形表求解线性规划问题的方法 5 单纯形

10、法的计算步骤 1 化 L P 问题为标准形式 建立初始单纯形表 3 计算 4 以alk为主元素 简称主元 用 表示 进行线性方程组 的初等行变换 将主元列Pk化为单位向量得到新的单纯形表 转入 2 最大正检验数决定换入变量 最小比值 决定换出变量 例 用单纯形法求解下列线性规划问题 max z 2 x1 3 x2 2 x1 2 x2 12 4x1 16 5 x2 15 x1 0 x2 0 s t 解 先标准化 Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 再列初

11、始单纯形表 6 3 2 3 0 0 0 Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 6 4 0 0 1 0 0 5 0 0 1 3 2 3 0 0 0 以 5 为主元进 行初等行变换 Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 2 0 1 0 2 5 3 4 0 0 1 0 4 0 1 0 0 1 5 2 0 0 0 3 5 x1为换入变量 下面开始单纯形法迭代 x5为换出变量 x2为换入变量 以 2 为主元进 行初等行变换 x

12、3为换出变量 主元化为1 主元列 的其他元素化为0 Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 1 5 0 0 2 1 4 5 0 1 0 0 1 5 0 0 1 0 1 5 此时得到唯一最优解X 3 3 T Zmax 15 6 单纯形法中存在的问题 1 存在两个以上的最大正检验数 任取一个最大正检验数对应的变量作为换入变量 2 出现两个以上相同的最小值 任取一个最小 对应的变量作为换出变量 此时L P 问题出现退化现象 练习 用单纯形法求解下列线性规划问题 解 先标准化 2 1 0 0 5 4 x3 x4 0

13、0 x1 x2 x3 x4bxBcB 2 1 0 0cj 24 15351 0 6 201 0 0 x3 x1 0 2 x1 x2 x3 x4bxBcB 2 1 0 0cj 4 30 1 4 1 01 3 1 2 1 6 1 3 1 3 3 4 12 0 0 1 12 7 24 x2 x1 1 2 x1 x2 x3 x4bxBcB 2 1 0 0cj 15 4 3 4011 4 1 8 10 1 125 24 唯一最优解 5 1 人工变量法 大M法 1 5 单纯形法的进一步讨论 例 用单纯形法求解下列线性规划问题 解 先标准化为 系数矩阵 但是A中没有单位矩阵 在A中人为的增加两列 此时 对应

14、的约束方程组为 该问题新增加了两个变量 x4 x5 称为人工变量 A有单位子矩阵 选择这个单位矩阵作为基 称为人工基 为使 必须保证在可行解中人工变量x4 x5 0 故令x4 x5在目标函数中的系数为 M 其中M表示任意大的正数 这种添加人工变量求解LP的方法称为人工变量法 计算过程中出现了M 这种方法也称为大M法 等价于 于是 这个线性规划问题转化为 以下可用单纯形法继续求解 Cj x1x2x3x4 XBbCB 1 1 1 1 0 1 2 0 0 1 2 3 0 M M 3 4 x4 x5 M M cj zj 2 2M 3 3M M0 3 1 3 4 2 2 1 2 0 1 1 1 2 1

15、2 1 0 0 1 2 x4 x2 1 2 cj zj 1 2 M 2 0 M 0 3 2 3M 2 M 3 2 4 1 0 2 2 1 0 1 1 1 1 x1 x2 2 1 cj zj 0 0 1 1 M 1 M 2 3 x5 0 唯一最优解故 zmin 7 注意 此时人工变量x4 x5 0 说明 若表中所有 j 0 但存在非0的人工变量 则该模 型无可行解 采用大M法求解线性规划模型时 如果模型中 各个系数与M的值非常接近或相差很大 若用手工计算 不会出现问题 但是若利用计算机求解 则容易引起混 淆 使得机器判断出错 从而使大M法失效 在这种情况下 可采用下面的两阶段法进行计算 5 2

16、两阶段法 将L P 问题分成两个阶段来考虑 第一阶段 判断原L P 问题是否存在可行解 给原L P 问题加入人工变量 并构造仅含人工变量的目标 函数w 人工变量在w中的系数一般取为1 并求w的最小值 然后用单纯形法求解 若求得wmin 0 则该问题有可行解 进 入第二阶段 否则该问题无可行解 结束 第二阶段 将第一阶段得到的最终表去掉人工变量 并 将目标函数还原为原L P 问题的目标函数 即修改最终表中 的第一行和第一列 以此作为第二阶段的初始表 继续 用单纯形法求解 例 用两阶段法求解下列线性规划问题 标准化 引入人工变量 z 1 第一阶段 构造判断是否存在可行解的模型 用单纯形法求解这个问题 先标准化为 Cj x1x2x3x4 XBbCB 1 1 1 1 0 1 2 0 0 1 0 0 0 1 1 3 4 x4 x5 1 1 cj zj 2 3 10 3 1 3 4 2 2 1 2 0 1 1 1 2 1 2 1 0 0 1 2 x4 x2 1 2 cj zj 1 2 0 1 0 3 2 1 0 2 4 1 0 2 2 1 0 1 1 1 1 x1 x2 2 1 cj zj 0 0