当前位置：文档之家 › 吴祈宗：运筹学培训教程.ppt

吴祈宗：运筹学培训教程.ppt

  • 格式：ppt
  • 大小：1.48 MB
  • 文档页数：128

下载文档原格式

  / 128

合集下载

大学课件运筹学 PPT_绪论

大学课件运筹学 PPT_绪论
必要的。
3） 数量化的分析方法有助于我们得到正确结论，做出 科学决策。
§0.2 运筹学的产生和发展
0.2.1古代的运筹学思想
●田忌赛马
——对策博奕
●都江堰水利工程 ——功能组织
●北宋丁渭修复皇宫——系统思想
●明代铸造永乐大钟——过程安排
●哥尼斯堡七桥问题——图论方法
0.2.2运筹学学科的产生
●第二次世界大战——军事目的
§0.1 引例
分钱游戏
有一慈善者拿出100元拟分给A和B，分配规 则是：由A提出分配方案，B同意分配方案，则 执行分配方案，B反对时则慈善者收回这100元。 假设A和B都是理性的，则A应该提出什么样的 方案，B怎么办？
§0.1 引例
0.1.3 启示
1） 解决管理问题要有整体意识或系统观念。 2） 建立研究对象各部分之间的联系对解决问题是非常
（2,1） （1,2）
-,+
+,-
+,-
-,+
最优方案 红军：集中兵力进攻。蓝军：分兵把守
§0.1 优化
蓝军
方案1 方案2 方案3 方案4
（3,0） （0,3） （2,1） （1,2）
红 方案A（2,0） -,+
+,-
-,+
+,-
军
方案B（0,2） +,-
-,+
+,-
-,+
方案C（1,1） +,-
0.3.1§运0.筹3学的运定义筹学的研究对象
4、运筹学的研究对象
各类有组织系统的管理问题及其生产经营活动。
0.3.1§运0.筹3学的运定义筹学的研究对象
5、运筹学的基本方法 定量化和模型化方法。

最优化方法PPT

最优化方法PPT

共117页第8页
同时太阳系这个"整体"又是它所属的"更大整 体"--银河系的一个组成部分。世界上的具体系统是 纷繁复杂的，必须按照一定的标准，将千差万别的 系统分门别类，以便分析、研究和管理，如：教育 系统、医疗卫生系统、宇航系统、通讯系统等等。 如果系统与外界或它所处的外部环境有物质、能量 和信息的交流，那么这个系统就是一个开放系统， 否则就是一个封闭系统。开放系统具有很强的生命 力，它可能促进经济实力的迅速增长，使落后地区 尽早走上现代化。如改革开放以来已大大增强了我 们的综合国力。而我国的许多边远山区农村，由于 交通不便，相对封闭，还处于比较落后的状态。
会科学和思维科学的相互渗透与交融汇流，产生了 具有高度抽象性和广泛综合性的系统论、控制论和 信息论。
系统论是研究系统的模式、性能、行为和规律 的一门科学。它为人们认识各种系统的组成、结构、 性能、行为和发展规律提供了一般方法论的指导。 系统论的创始人是美籍奥地利理论生物学家和哲学 家路德维格·贝塔朗菲。系统是由若干相互联系的 基本要素构成的，它是具有确定的特性和功能的有 机整体。如太阳系是由太阳及其围绕它运转的行星 （金星、地球、火星、木星等等）和卫星构成的。
从数学上比较一般的观点来看，所谓最优化问题可 以概括为这样一种数学模型：给定一个“函数”，F(X)， 以及“自变量”X应满足的一定条件，求X为怎样的值时， F(X)取得其最大值或最小值。这里在函数和自变量两个 词上之所以打上引号，是想强调它们的含意比中学数学 和大学微积分中函数的定义要广泛得多。通常，称F(X) 为“目标函数”，X应满足的条件为“约束条件”。约 束条件一般用一个集合D表示为：X∈D。求目标函数 F(X)在约束条件X∈D下的最小值或最大值问题，就是一 般最优问题的数学模型，它还可以利用数学符号更简洁 地表示成：Min F(X)或Max F(X)。

运筹学课件汇总

运筹学课件汇总
其中， A为 mn矩阵，d为m维向量
F(x)=( f1(x), f2(x), … , fm(x) )T 记 aiT为A的第i行向量，f(x) = aiTx
1.5基本概念和符号
(2) 梯度（一阶偏导数向量）： f (x)＝( f / x1 , f / x2 , … , f / xn )TRn 线性函数：f (x) = cTx + b , f (x) = c
d =(d1 ,d2 ,…,dn)T 表示从0指向d 的方 向
实用中，常用 x + d 表示从x 点出发沿d 方向
移动d 长度得d 到的点。
x+(1/2)d
0
x
1.5 基本概念和符号
(2) 向量运算：x , y Rn
x
,
y
的内积：xTy
=
n
xi
yi
=
x1y1+
x2y2+
…+
xn
yn
i =1
x , y 的距离： ‖x－y ‖= [(x － y)T(x － y)](1/2)
1.1 什么是运筹学
• 运筹学是为决策机构在对其控制下的业 务活动进行决策时，提供一门以量化为 基础的科学方法。
• 运筹学是一门应用科学，它广泛应用现 有的科学技术知识和数学方法，解决实 际中提出的专门问题，为决策者选择最 优决策提供定量依据。
• 运筹学是一种给出问题坏的答案的艺术， 否则的话，问题的结果会更坏。
• 一个有用的定理
设 xRn，R，L为Rn 的线性子空间。 若 xTy ≤ , yRn 且 y ≥ 0， 则
x ≤ 0， ≥ 0 若 xTy ≤ , y L Rn ， 则
x L， ≥ 0 (特别地, 当L＝Rn时,x =0)

北京理工大学运筹学 吴祈宗 第2章

北京理工大学运筹学 吴祈宗 第2章
26
设备能力 （h） 65 40 75
2.线性规划的图解法
问题：工厂应如何安排生产可获得 最大的总利润？用图解法求解。
解：设变量xi 为第i种（甲、乙）产 品的生产件数（i＝1，2）。根据前面分 析，可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2
s.t. 3x1+ 2x2 ≤ 65 (A)
目标函数随着取值不同，为一 族相互平行的直线。 首先，任意给定目标函数一个 值，可作出一条目标函数的等值线 （直线）； 然后，确定该直线平移使函数 值增加的方向； 最后，依照目标的要求平移此 直线。
24
2.线性规划的图解法
结果
若目标函数等值线能够移动 到既与可行域有交点又达到最 优的位置，此目标函数等值线 与可行域的交点即最优解（一 个或多个），此目标函数的值 即最优值。 否则，目标函数等值线与可 行域将交于无穷远处，此时称 无有限最优解。
29
2.线性规划的图解法

例题作图（2）
第2步图示(1) 分别作出各约束半平面
3x1+ 2x2 ≤ 65
2x1+ x2 ≤ 40
3x2 ≤ 75
x1 ≥ 0
X2 ≥ 0
30
2.线性规划的图解法

例题作图（3）
第2步图示(2) 各约束半平面的交－可行域
31
2.线性规划的图解法
（3）任意给定目标函数一个值（例 如37500）作一条目标函数的等值 线，并确定该等值线平移后值增加 的方向（向上移动函数值增大）， 平移此目标函数的等值线，使其达 到既与可行域有交点又不可能使值 再 增 加 的 位 置 ， 得 到 交 点 (5,25)T ，即最优解。此目标函数 的值为70000。

运筹学ppt课件

运筹学ppt课件
– 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解；
– 无界解。即可行域的范围延伸到无穷远，目标 函数值可以无穷大或无穷小。一般来说，这说 明模型有错，忽略了一些必要的约束条件；
– 无可行解。若在例1的数学模型中再增加一个约 束条件4x1+3x2≥1200，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了。
• 交叉学科 --涉及经济、管理、数学、工程和系统等 多学科
• 开放性 --不断产生新的问题和学科分支
• 多分支 --问题的复杂和多样性
2
运筹学的主要内容
线性规划
数 非线性规划
学
整数规划
规
动态规划
划
多目标规划
学
双层规划
最优计数问题
科
组 合
网络优化
内
优 排序问题 化 统筹图
容
对策论
随 排队论
机 优 化
13
组织 宝洁公司 法国国家铁路
应用
Interface 每年节支 期刊号 （美元）
重新设计北美生产和分销系统以 1-2/1997 2亿 降低成本并加快了市场进入速 度
制定最优铁路时刻表并调整铁路 1-2/1998 1500万更多
日运营量
年收入
Delta航空公司 IBM
进行上千个国内航线的飞机优化 配置来最大化利润
负。当某一个右端项系数为负时，如 bi<0，则把该 等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2… -ain xn = -bi。
30
例：将以下线性规划问题转化为标准形式
则该极小化问题与下面的极大化问题有相同的最优解，

运筹学讲义完整版

运筹学讲义完整版
第35页
等可能准则
n
max{
i
1 n
Vij
j=1
}
S1 A1 20 A2 9 A3 6
S2
S3
Vi =
1 3
Vij
1 -6
5
80
5
2 3
max=5
2 3
54
5
选 A2
第36页
5.后悔值准则（Savage原则 ） （最小机会损失决策）
定义：称每个方案aj在结局Si下的最大可能 收益与现收益的差叫机会损失，又称后悔值 或遗憾值。记Rij(si,aj)=MaxQij(si,aj)-Qij(si,aj)
第27页
收益矩阵
事件 高
方案
S1
A1
20
A2
9
A3
6
中
低
S2 S3(万元)
1
-6
8
0
5
4
第28页
1.乐观准则（Hurwicz原则、MaxMax ） （冒险型决策）
对于任何行动方案 ，都认为将是最好的状态发 生，即益损值最大的状态发生。然后，比较各 行动方案实施后的结果，取具有最大益损值的 行动为最优行动的决策原则，也称为最大最大 准则。
第39页
（3）在机会损失表中，从每一行选一 个最大的值，即每一方案的最大机会损 失值 Max Rij(si,aj) （4）再在选出的 Max Rij(si,aj)选择最 小者：
第37页
对于任何行动方案aj ,都认为将是 最大的后悔值所对应的状态发生。然后， 比较各行动方案实施后的结果，取具有 最小后悔值的行动为最优行动的决策原 则，称为后悔值准则。记
R (s,aopt) = Min Max Rij(si,aj) ji

运筹学课件


25
如何学习运筹学课程
在建数学模型 时，要结合实 际应用。 际应用
26
据美劳工局1992年统计预测:社会 对运筹学应用分析人员的需求从1990 年到2005年，其增长百分比预测为73%, 增长速度排到各项职业的前三位。
18
运筹学的推广应用前景
结论: --运筹学在国内或国外的推广应 用前景是非常广阔的。 --工商企业对运筹学应用的需求 是很大的。 --在工商企业推广运筹学方面有 大量的工作要做。
的管理，库存方式、库存量等。
运输问题：确定最小成本的
运输线路、物资的调拨、运输工具 的调度以及建厂地址的选择等。
8
运筹学在工商管理中的应用
人事管理：对人员的需求和使 用的预测，确定人员编制、人员合 理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择 定价、产品开发与销售计划制定等。
9
运筹学在工商管理中的应用
21
如何学习运筹学课程
学习运筹学要把重点放在分 析、理解有关的概念、思路上。 在自学过程中，应该多向自己提 问，例如一个方法的实质是什么， 为什么这样进行，怎么进行等。 自学时要掌握三个重要环节：
22
如何学习运筹学课程
1.认真阅读教材和参考资料， 以指定教材为主，同时参考其他有 关书籍。一般每一本运筹学教材都 有自己的特点，但是基本原理、概 念都是一致的。注意主从，参考资 料会帮助你开阔思路，使学习深入。 但是，把时间过多放在参考资料上， 会导致思路分散，不利于学好。
财务和会计：包括预测、贷款、 成本分析、定价、证券管理、现金 管理等。 其他： 设备维修、更新，项 目选择、评价，工程优化设计与管 理等。
10
运筹学的产生和发展
运筹学思想的出现可以追溯到很 早—“田忌齐王赛马”（对策论）、孙 子兵法等都体现了优化的思想。 “运筹学”这一名词最早出现在 第二次世界大战期间—— 美、英等国 家的作战研究小组为了解决作战中所 遇到的许多错综复杂的战略、战术问 题而提出的。

北京理工大学运筹学 吴祈宗 第5章


x1
x2
x3
xk
xk+1
xn
n+1
T1
T2
Tk
Tn
2
1.多阶段决策过程的最优化
动态规划方法与“时间”关系很 密切，随着时间过程的发展而决定各 时段的决策，产生一个决策序列，这 就是“动态”的意思。然而它也可以 处理与时间无关的静态问题，只要在 问题中人为地引入“时段”因素，就 可以将其转化为一个多阶段决策问题。 在本章中将介绍这种处理方法。
2.动态规划的基本概念
（四）、策略和允许策略集合 策 略 (Policy) 也 叫 决 策 序 列．策略有全过程策略和 k 部子策略 之分，全过程策略是指由依次进行的 n 个阶段决策构成的决策序列，简称 策 略 ，表示 为 p1,n{u1,u2,…,un}。 从 k 阶段到第 n 阶段，依次进行的阶段决 策构成的决策序列称为k部子策略,表 示 为 pk,n{uk,uk+1,…,un} ，显然当 k=1 时的k部子策略就是全过程策略。
5
1.多阶段决策过程的最优化
3)连续生产过程的控制问题： 一般化工生产过程中，常包含一系列 完成生产过程的设备，前一工序设备 的输出则是后一工序设备的输入，因 此，应该如何根据各工序的运行工况， 控制生产过程中各设备的输入和输出， 以使总产量最大。
6
1.多阶段决策过程的最优化
许多问题的发展过程都与时间因素有关。 在这类多阶段决策问题中，阶段的划分 常取时间区段来表示，并且各个阶段上 的决策往往也与时间因素有关。这就使 它具有了“动态”的含义，所以把处理 这类动态问题的方法称为动态规划方法。 实际中尚有许多不包含时间因素的一类 “静态”决策问题，就其本质而言是一 次决策问题，是非动态决策问题，但是 也可以人为地引入阶段的概念当作多阶 段决策问题，应用动态规划方法加以解 决。

运筹学教程 (7)

13
2.决策的分类与过程

4.方案实施。这是决策过程的最终 阶段。这个过程解决的主要有追踪协 调和反馈控制。追踪协调是对决策方 案的实施偏离决策目标时要进行根本 性修正，并对目标之间、系统之间、 方案之间的不一致现象给予协调和调 整。反馈控制是对方案实施中主客观 情况的变化，及时对决策方案和行为 进行修正，以保证决策目标的顺利实 现。
5
2.决策的分类与过程
战术决策是为了保证完成战略决策 规定的目标而进行的决策。比如对一个 企业来说，产品规格的选择、工艺方案 的制定、厂区的合理布置等等。 执行决策是按照战术决策的要求对 执行方案的选择。比如产品合格标准的 选择制定，日常生产调度等等。
6
2.决策的分类与过程
2.按决策的结构分类。可以分 为程序性决策和非程序决策。 程序性决策一般是有章可循，规 格化，可以重复的决策。 非程序性决策一般是无章可循， 凭借经验和直觉等，往往是一次 性的，有战略性的决策。
结果选择方案k2 。很明显如果 取值不同，可以得到不同的结果。 当情况比较乐观时，应取的大一些， 反之，应取的小一些。
27
i
4.不确定型的决策问题
四.等可能准则 等可能准则也叫做Laplace准则， 它是十九世纪数学家Laplace提出来的。 他认为，当决策者无法事先确定每个 自然状态出现的概率时，就可以把每 个状态出现的概率定为 1/n ， n 是自然 状态数，然后按照最大期望值准则决 策。见表7.6。
31
4.不确定型的决策问题ቤተ መጻሕፍቲ ባይዱ
表7.7
决
1
策
表
j
自然状态
2
5 4 7 5 5
aij
Ki
决 策 方 案
3

运筹学PPT

线性规划
线性规划研究的主要问题


一类是已有一定数量的资源（人力、物质、 时间等），研究如何充分合理地使用它们， 才能使完成的任务量为最大。 另一类是当一项任务确定以后，研究如何统 筹安排，才能使完成任务所耗费的资源量为 最少。

—— 实际上，上述两类问题是一个问题 的两个不同的方面，都是求问题的最优 解（ max 或 min ）。
模型特点
1 都用一组决策变量X = (x1,x2,…,xn)T表示某一方案，且 决策变量取值非负； 2 都有一个要达到的目标，并且目标要求可以表示成决 策变量的线性函数； 3 都有一组约束条件，这些约束条件可以用决策变量的 线性等式或线性不等式来表示。
——— 满足以上三个条件的数学模型称 为线性规划
基本定理





定理 1 若线性规划问题存在可行解，则问题的可行 域是凸集。 引理1 线性规划问题的可行解为基可行解的充要条 件是X的正分量所对应的系数列向量是线性无关的。 定理 2 线性规划问题的基可行解X对应线性规划问 题可行域（凸集）的顶点。 引理2 若K是有界凸集,则K中任意一点可以表示为K 的顶点的凸组合. 定理3 若线性规划问题有最优解，一定存在一个基 可行解是最优解。
价值系数
a1n a2 n aij mn amn
系数矩阵
C c1 c2 cn
x1 x2 决策变量 X x n
b1 b2 b b n
单纯形法的思想



考虑：若线性规划问题有最优解， 必有一个基可行解是最优解。 思路：找出一个基可行解，判断是 否最优，否则，换一个基可行解。 几何意义
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
x1 , x2 ≥ 0
**看 p 7--9 例1-1，1-2
.....
12
1、 线 性 规 划 （续1.1）
1. 1 线性规划的概念 • 线性规划的组成：
目标函数 Max f 或 Min f 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素
• 一般形式 ( p10-- p 11)
• 库存管理：多种物资库存量的管理，库存方式、库存 量等
• 运输问题：确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等
• 人事管理：对人员的需求和使用的预测，确定人员编 制、人员合理分配，建立人才评价体系等
• 市场营销：广告预算、媒介选择、定价、产品开发与 销售计划制定等
• 财务和会计：预测、贷款、成本分析、定价、证券管 理、 1 1 1 100元
资 源 限 制 300台 时 400千 克 250千 克
问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？
线性规划模型： 目标函数：Max 约束条件：s.t.
z = 50 x1 + 100 x2 x1 + x2 ≤ 300
2 x1 + x2 ≤ 400 x2 ≤ 250
4
运筹学的分支
• 线性规划 • 非线性规划 • 整数规划 • 动态规划 • 多目标规划 • 随机规划 • 模糊规划等
• 图与网络理论 • 存储论 • 排队论 • 决策论 • 对策论 • 排序与统筹方法 • 可靠性理论等
5
运筹学在工商管理中的应用
• 生产计划：生产作业的计划、日程表的编排、合理下 料、配料问题、物料管理等
0
从不使用 有时使用 经常使用
8
统计 计算机模拟
网络计划 线性规划
排队论 非线性规划
动态规划 对策论
运筹学的推广应用前景
• 据美劳工局1992年统计预测: 运筹学应用分析人员需求从1990年到2005
年的增长百分比预测为73%,增长速度排到各 项职业的前三位.
结论:
• 运筹学在国内或国外的推广前景是非常广阔的 • 工商企业对运筹学应用和需求是很大的 • 在工商企业推广运筹学方面有大量的工作要做
*** 设备维修、更新，项目选择、评价，工程优化设计与管理等
6
运筹学方法使用情况(美1983)（%）
70 60 50 40 30 20 10
0
从不使用 有时使用 经常使用
7
统计 计算机模拟
网络计划 线性规划
排队论 非线性规划
动态规划 对策论
运筹学方法在中国使用情况(随机抽样)（%）
90 80 70 60 50 40 30 20 10
9
如何学习运筹学课程
• 学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程 中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎 么做等。
• 自学时要掌握三个重要环节：
1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运 筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助 你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于 学好。 2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论 的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做 题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联 系，只要学到一定程度，知识融会贯通起来，你做题的正确性自己就有判断。 3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该书所学内容。这 样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读 薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进 行论述，则称之为“把书读厚”
目标函数： 约束条件：
Max （Min） z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0
运筹学
北京理工大学 管理与经济学院
吴祈宗教授
1
运 筹 学 ——目录
1、绪 论 2、线 性 规 划 3、运 输 问 题 4、动 态 规 划 5、图与网络分析 6、排 队 论 7、教学日历
说明
本教学课件是与教材紧密配合 使用的，教材为： 《运筹学》 杨民助编著 西安交通大学出版社，2000年6月
参考书： 《运筹学》 清华大学出版社 或其他的《运筹学》方面本科教材 的相关内容
• 在建数学模型时要结合实际应用，要学会用计算机软件解决问题。
返回目录
10
各章节的重点、难点 及注意事项
11
1、 线 性 规 划
例1. 某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时 及A、B两种原材料的消耗以及资源的限制，如下表：
设 备 原 料A 原 料B 单 位 产 品 获 利
3
运筹学解决问题的过程
1）提出问题：认清问题 2）寻求可行方案：建模、求解 3）确定评估目标及方案的标准或方法、途径 4）评估各个方案：解的检验、灵敏性分析等 5）选择最优方案：决策 6）方案实施：回到实践中 7）后评估：考察问题是否得到完满解决
1）2）3）：形成问题；4）5）分析问题：定性分 析与定量分析。构成决策。
下面所标注的页号，均为本 课程教材的页号。例如：
p123 表示第123页
p31-34 表示从第31页到第34页
2
绪论
运筹学（Operational Research) 直译为“运作研究”
运筹学是运用科学的方法（如分析、试验、 量化等）来决定如何最佳地运营和设计各种系 统的一门学科。运筹学对经济管理系统中的人 力、物力、财力等资源进行统筹安排，为决策 者提供有依据的最优方案，以实现最有效的管 理。 • 运筹学有广泛应用（可以自己找一些参考书看） • 运筹学的产生和发展（可以自己找一些参考书看）