运筹学 Operational Research

Slides:



Advertisements
Similar presentations
1 主讲:寇继虹 2 线性规划及应用简介 线性规划是运筹学的一个最基本的分支, 它已成为帮助各级管理人员进行决策的 · 一 种十分重要的工具.是一种目前最常用而又 最为成功的定性分析和定量分析相结合的管 理优化技术。 其原因有三: 一、应用广泛.管理工作中的大量优化 问题可以用线性规划的模型来表达.
Advertisements

一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
第五节 全微分方程 一、全微分方程及其求法 二、积分因子法 三、一阶微分方程小结. 例如 所以是全微分方程. 定义 : 则 若有全微分形式 一、全微分方程及其求法.
1 热烈欢迎各位朋友使用该课件! 广州大学数学与信息科学学院. 2 工科高等数学 广州大学袁文俊、邓小成、尚亚东.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
运筹学模型与软件实践 Models and Software Practice of the Operations Research
§3.4 空间直线的方程.
3.4 空间直线的方程.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
第3节 二次型与二次型的化简 一、二次型的定义 二、二次型的化简(矩阵的合同) 下页.
一、能线性化的多元非线性回归 二、多元多项式回归(线性化)
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
黄桐城 上海交通大学安泰管理学院 版权所有 侵权必究
第三章 函数逼近 — 最佳平方逼近.
人工智能技术导论 廉师友编著 西安电子科技大学出版社.
《高等数学》(理学) 常数项级数的概念 袁安锋
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
运筹学 Operational Research 数学科学学院 许成.
恰当方程(全微分方程) 一、概念 二、全微分方程的解法.
定积分的换元法 和分部积分法 换元公式 分部积分公式 小结 1/24.
§5.3 定积分的换元法 和分部积分法 一、 定积分的换元法 二、 定积分的分部积分法 三、 小结、作业.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第四节 一阶线性微分方程 线性微分方程 伯努利方程 小结、作业 1/17.
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法
第2章 Z变换 Z变换的定义与收敛域 Z反变换 系统的稳定性和H(z) 系统函数.
第二章 矩阵(matrix) 第8次课.
元素替换法 ——行列式按行(列)展开(推论)
第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析.
计算机数学基础 主讲老师: 邓辉文.
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
第4章 对偶模型 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
第一章 函数与极限.
从物理角度浅谈 集成电路 中的几个最小尺寸 赖凯 电子科学与技术系 本科2001级.
Partial Differential Equations §2 Separation of variables
窗含西岭千秋雪,门泊东吴万里船 对偶是一种普遍现象
线性规 Linear Programming
概 率 统 计 主讲教师 叶宏 山东大学数学院.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
第十章 双线性型 Bilinear Form 厦门大学数学科学学院 网址: gdjpkc.xmu.edu.cn
运 筹 学 运 筹 帷 幄 之 中 决 胜 千 里 之 外 绪 论 Introduction
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
§8.3 不变因子 一、行列式因子 二、不变因子.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
4) 若A可逆,则 也可逆, 证明: 所以.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
学习任务三 偏导数 结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.
1.非线性规划模型 2.非线性规划的Matlab形式
Models and Software Practice of the Operations Research
建模常见问题MATLAB求解  .
一元二次不等式解法(1).
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
§2 方阵的特征值与特征向量.
HULUO Finance and Economics College
滤波减速器的体积优化 仵凡 Advanced Design Group.
我们能够了解数学在现实生活中的用途非常广泛
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
教学大纲(甲型,54学时 ) 教学大纲(乙型, 36学时 )
线性规划 Linear Programming
线性规划 Linear Programming
§4.5 最大公因式的矩阵求法( Ⅱ ).
第三章 线性方程组 §4 n维向量及其线性相关性(续7)
一元一次方程的解法(-).
Cfc Zeilberger 算法 陈焕林 陈永川 付梅 臧经涛 2009年7月29日.
Presentation transcript:

运筹学 Operational Research 运筹帷幄,决胜千里 史记《张良传》

目 录 绪 论 第一章 线性规划问题及单纯型解法 第二章 线性规划的对偶理论及其应用 第三章 运输问题数学模型及其解法 第四章 整数规划 目 录 绪 论 第一章 线性规划问题及单纯型解法 第二章 线性规划的对偶理论及其应用 第三章 运输问题数学模型及其解法 第四章 整数规划 第五章 动态规划 第六章 图与网路分析 第七章 随机服务理论概论 第八章 生灭服务系统 第九章 特殊随机服务系统 第十章 存储理论

绪 论 一、运筹学的起源与发展 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 四、运筹学的发展趋势

一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科 与作战问题相关 战后在经济、管理和机关学校及科研单位继续研究 如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research 战后在经济、管理和机关学校及科研单位继续研究 1952年,Morse 和 Kimball出版《运筹学方法》 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS,并于1999年8月组织了第15届大会

二、运筹学的特点及研究对象 运筹学的定义 为决策机构对所控制的业务活动作决策时,提供以数量为基础的科学方法——Morse 和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题,其方法是发展一个科学的系统模式,并运用这种模式预测,比较各种决策及其产生的后果,以帮助主管人员科学地决定工作方针和政策——英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排,为决策者提供有根据的最优方案,以实现最有效的管理——中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题,称为 Management Science

二、运筹学的特点及研究对象 运筹学的分支 数学规划:线性规划、非线性规划、整数规划、动态规划、目标规划等 图论与网路理论 随机服务理论:排队论 存储理论 决策理论 对策论 系统仿真:随机模拟技术、系统动力学 可靠性理论 金融工程

三、运筹学解决问题的方法步骤 明确问题 明确问题 建立模型 设计算法 建立模型 整理数据 求解模型 评价结果 设计算法 简化? 整理数据 Yes 设计算法 简化? No 整理数据 求解模型 No 评价结果 满意?

四、运筹学的发展趋势 运筹学的危机 IT对运筹学的影响 运筹学与行为科学结合 服务行业中的应用 脱离实际应用,陷入数学陷阱 MIS, DSS, MRP-II, CIMS, ERP OR Dept. --> Dept. Of OR & IS 运筹学与行为科学结合 群决策和谈判 对策理论 多层规划 合理性分析 服务行业中的应用 金融服务业 信息、电信服务业 医院管理

四、运筹学的发展趋势 软计算 面向问题 后勤(Logistics) 随机和模糊 OR 面向强复杂系统的计算、实时控制、知识推理 智能算法:模拟退火、遗传算法、人工神经网络、戒律算法等 系统仿真 面向问题 后勤(Logistics) 全球供应链管理 电子商务:集成特性 随机和模糊 OR 问题本身的不确定性 人类知识的局限性

第一章 线性规划问题及单纯型解法 1.1 线性规划问题及其一般数学模型 1.1.1 线性规划问题举例 例1、多产品生产问题(Max, ) 设x1, x2 分别代表甲、乙两种电缆的生产量,

例2、配料问题(min, ) 设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量

例3、合理下料问题 设 xj 分别代表采用切割方案1~8的套数,

1.1.2 线性规划数学模型的一般表示方式

1、和式

2、向量式

3、矩阵式

1.1.3 线性规划的图解法 f(x)=36

线性规划问题的几个特点: 线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的 最优解只可能在凸集的极点上,而不可能发生在凸集的内部

1.2 线性规划问题的单纯型解法 1.2.1 线性规划问题的标准形式 为了使线性规划问题的解法标准,就要把一般形式化为标准形式

变换的方法: 目标函数为min型,价值系数一律反号。令 f(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f (x) 第i 个约束的bi 为负值,则该行左右两端系数同时反号,同时不等号也要反向 第i 个约束为  型,在不等式左边增加一个非负的变量xn+i ,称为松弛变量;同时令 cn+i = 0 第i 个约束为  型,在不等式左边减去一个非负的变量xn+i ,称为剩余变量;同时令 cn+i = 0 若xj 0,令 xj= -xj ,代入非标准型,则有xj  0 若xj 不限,令 xj= xj - xj, xj  0,xj  0,代入非标准型

变换举例:

关于标准型解的若干基本概念: 标准型有 n+m 个变量, m 个约束行 “基”的概念 在标准型中,技术系数矩阵有 n+m 列,即 A = ( P1, P2 , … , Pn+m ) A中线性独立的 m 列,构成该标准型的一个基,即 B = ( P1 , P2  , … , Pm ), | B |  0 P1 , P2  , … , Pm 称为基向量 与基向量对应的变量称为基变量,记为 XB = ( x1 , x2  , … , xm  )T,其余的变量称为非基变量,记为 XN = ( xm+1 , xm+2 , … , xm+n  ) T , 故有 X = XB + XN 最多有 个基

关于标准型解的若干基本概念: 可行解与非可行解 满足约束条件和非负条件的解 X 称为可行解,满足约束条件但不满足非负条件的解 X 称为非可行解 基础解 令非基变量 XN = 0,求得基变量 XB的值称为基础解 即 XB = B1 b XB 是基础解的必要条件为XB 的非零分量个数  m 基础可行解 基础解 XB 的非零分量都  0 时,称为基础可行解,否则为基础非可行解 基础可行解的非零分量个数 < m 时,称为退化解

线性规划标准型问题解的关系 约束方程的 解空间 非可行解 基础 可行解 可行解 基础解 退化解

可行解、基础解和基础可行解举例

1.2.2 单纯型法的基本思路

1.2.3 单纯型表及其格式

例1.2.2 试列出下面线性规划问题的初始单纯型表

关于检验数的数学解释 设 B 是初始可行基,则目标函数可写为两部分(1) 约束条件也写为两部分,经整理得 XB 的表达式(2),注意 XB中含有非基变量作参数 把 XB 代入目标函数,整理得到(3)式 第 j 个非基变量的机会成本如(4)式 若有cjzj>0, 则未达到最优

1.2.4 标准型的单纯型算法 找初始基础可行基 对于(max,),松弛变量对应的列构成一个单位阵 若有 bi<0,则单位阵也不能构成一个可行基 检验当前基础可行解是否为最优解 所有检验数 cj zj0,则为最优解,否则 确定改善方向 从 (cj zj) > 0 中找最大者,选中者称为入变量, xj* 第j*列称为主列 确定入变量的最大值和出变量 最小比例原则

1.2.4 标准型的单纯型算法 确定入变量的最大值和出变量 设第 i* 行使  最小,则第 i* 行对应的基变量称为出变量,第 i* 行称为主行 迭代过程 主行 i* 行与主列 j* 相交的元素ai*j* 称为主元,迭代以主元为中心进行 迭代的实质是线性变换,即要将主元 ai*j*变为1,主列上其它元素变为0,变换步骤如下: (1)变换主行

1.2.4 标准型的单纯型算法 迭代过程 (2)变换主列 除主元保留为1,其余都置0 (3)变换非主行、主列元素 aij (包括 bi) 四角算法公式:

1.2.4 标准型的单纯型算法 5、迭代过程 (4)变换CB,XB (5)计算目标函数、机会成本 zj 和检验数 cj  zj 6、返回步骤 2

表1.2.4 例1.2.2 单纯型表的迭代过程 答:最优解为 x1=20, x2=20, x3=0, OBJ=1700

单纯型表中元素的几点说明 任何时候,基变量对应的列都构成一个单位矩阵 当前表中的 b 列表示当前基变量的解值,通过变换 B 1 b 得到 (资源已变成产品) 当前非基变量对应的向量可通过变换 B 1 AN 得到, 表示第 j 个变量对第 i 行对应的基变量的消耗率 非基变量的机会成本由 给出 注意基变量所对应的行

1.3 人工变量的引入及其解法 1.3.1 当约束条件为“”型,引入剩余变量和人工变量 1.3 人工变量的引入及其解法 1.3.1 当约束条件为“”型,引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为1,不能作为初始可行基变量,为此引入一个人为的变量(注意,此时约束条件已为“=”型),以便取得初始基变量,故称为人工变量 由于人工变量在原问题的解中是不能存在的,应尽快被迭代出去,因此人工变量在目标函数中对应的价值系数应具有惩罚性,称为罚系数。罚系数的取值视解法而定 两种方法 大M法 二阶段法

1.3.2 大M法的求解过程 例1.3.1

表1.3.1 例1.3.1的单纯型表迭代过程 答:最优解为 x1=2, x2=2, x3=0, OBJ=36

大M法的一些说明 大M法实质上与原单纯型法一样,M 可看成一个很大的常数 人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件,但基变量中仍有人工变量,说明原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易

1.3.3 二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去,从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解,采用原单纯型法求解 若第一阶段结束时,人工变量仍在基变量中,则原问题无解 为了简化计算,在第一阶段重新定义价值系数如下:

表1.3.2 用二阶段法求解例1.3.1的第一阶段

表1.3.2 用二阶段法求解例1.3.1的第二阶段 最优解对应的B–1在哪?

1.5 单纯型法的一些具体问题 1.5.1 关于无界解问题 可行区域不闭合(约束条件有问题) 单纯型表中入变量 xj* 对应的列中所有

表1.5.1 例1.5.1 的单纯型表及其迭代过程 

1.5.2 关于退化问题 退化问题的原因很复杂,当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环,克服死循环的方法有“字典序”法

1.5.3 关于多重解问题 多个基础可行解都是最优解,这些解在同一个超平面上,且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解,即 X=aX1+bX2,a+b=1

表1.5.3 例1.5.3 的单纯型表及其迭代过程

1.5.4 关于无可行解问题 约束条件互相矛盾,无可行域 单纯型表达到最优解检验条件时,人工变量仍在基变量中

表1.5.4 例1.5.4 第一阶段的单纯型表

1.4 修正单纯型法 原单纯型法迭代所需存储量大 原单纯型法有不必要的计算量 1.4.1 修正单纯型的原理

当前基的逆矩阵 B1 在原单纯型表的什么位置上? 在初始可行基向量位置上 1.4.1 修正单纯型的原理 关键是求新基的逆矩阵 B1 仍然可以采用四角算法 混合算法 当前基的逆矩阵 B1 在原单纯型表的什么位置上? 在初始可行基向量位置上 ( AN | I )  ( I | AN1 )