运筹学 Operational Research

Presentation on theme: "运筹学 Operational Research"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

14 1、和式

15 2、向量式

16 3、矩阵式

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

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

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

20 变换的方法： 目标函数为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，代入非标准型

21 变换举例：

22 关于标准型解的若干基本概念： 标准型有 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 最多有 个基

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

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

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

26 1.2.2 单纯型法的基本思路

27 1.2.3 单纯型表及其格式

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

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

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

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

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

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

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

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

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

37 1.3.2 大M法的求解过程 例1.3.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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