没有合适的资源?快使用搜索试试~ 我知道了~
工程数学中的优化方法(叶峰)
4星 · 超过85%的资源 需积分: 9 13 下载量 90 浏览量
2010-01-05
11:10:16
上传
评论
收藏 446KB PDF 举报
温馨提示
试读
32页
(1) 基本概念:数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法、改进单纯形法。 (2) 建立简单的线性规划数学模型。 (3) 求解线性规划的图解法。 (4) 基、可行基及最优基的定义。 (5) 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。 (6) 有唯一解、有无穷多解、无界解、无可行解的判断。 (7) 求解线性规划的单纯形法。 (8) 求解线性规划的人工变量法。 (9) 单纯形法中的5个计算公式。
资源推荐
资源详情
资源评论
运筹学与最优化
学 时:76
学 分:5
上课地点:J6-01
上课时间:
考试时间:元月 22 日
主 讲:叶峰
西安电子科技大学理学院
课 程 简 介
运筹学是一门以决策支持为目标的学科。运筹学的英文名称是 Operations Research(美)或
Operational Research(英),缩写为 OR,直译是作业研究、操作研究或运作研究。运筹学是 OR
的意译,取自成语“运筹帷幄之中,决胜千里之外”,具有运用筹划,出谋献策,以策略取胜等内
涵。
一、运筹学研究的内容
从运筹学的内涵可以看出,它的内容非常丰富,应用范围非常广泛,从军事、政治到管理、
经济及工程技术等许多领域都能应用到运筹学的思想和方法。构成运筹学的理论大致分 3 个部
分。
1.分析理论。主要研究资源的最优利用、设备最佳运行等问题。常用的数学分析方法有规
划论(如线性规划、非线性规划、整数规划、动态规划、目标规划等)、网络模型、最优控制等。
随着一些新型学科的发展,还衍生了一些诸如不确定规划、灰规划、模糊规划、随机规划等专门
的分析方法。
2.决策理论。主要研究方案或策略的最优选择问题。常用的数学分析方法有博弈论、决策
论、多目标决策、存储论。
3.随机服务理论。主要研究随机服务系统排队和拥挤现象问题,讨论随机服务系统的服务
效率、绩效评价和服务设施的最佳设置等问题。
二、运筹学的分析方法
运筹学是一门定性分析(如建立数学模型)与定量方法(如求解数学模型)相结合的一门综
合应用科学。它广泛应用现有的科学技术和数学方法,解决实际中提出的专门问题,为决策者选
择最优或较优决策提供定量依据。
要掌握好运筹学方法并成功应用于实践,不仅要有丰富的自然科学和社会科学的知识,掌握
一定的数理基础方法,还要用系统的观念去认识问题分析问题,使研究的对象得到最优或满意的
效果。
例如,企业在编制年度计划时,第一步,收集产品市场需求、竞争对手、国内外经济政策环
境、利率变化、环境保护等外部信息,充分了解企业内部的技术力量、设计能力、生产能力和资
源分布等资料;第二步,分析和整理得到的外部信息和内部资料,制定企业的预定目标,建立产
品与资源消耗的关系表达式(即数学模型),充分利用企业资源,使得到最大或较大的收益;第
三步,运用数学分析方法求解数学模型,得到产品的生产量、资源消耗量和收益等理论值;第四
步,分析和运用所求结果,在计划的实施过程中进行有效的监督、控制和调整,尽可能达到预期
目标。由此可以看出,要编制出一个合理优秀的计划,需要多学科的知识和运用系统的方法。运
筹学方法则贯穿上述四个步骤的全过程,即收集资料、建立模型、求解模型和应用。
三、关于运筹学软件
目前国内外各种版本的运筹学软件有数十种之多,到目前为止,还没有一种软件包将运筹学
的所有计算都包含其中,只能根据不同内容使用不同的软件。比较专业的软件如 WinQSB、Lindo、
Lingo、Premium Solver、RiskSim、MS Project 等软件,MS Office 中 Excel 软件也能解决运筹学
的大部分计算。
第 1 章 线性规划
本章介绍了什么是线性规划,线性规划数学模型的概念及其建立数学模型方法;阐述了线性
规划的图解法、解的概念及解的形式;详细介绍了普通单纯形法、人工变量单纯形法及单纯形法
计算公式。
1.考核知识点
(1) 基本概念:数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变
量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可
行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大 M 法、两阶段法、改进单纯形
法。
(2) 建立简单的线性规划数学模型。
(3) 求解线性规划的图解法。
(4) 基、可行基及最优基的定义。
(5) 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。
(6) 有唯一解、有无穷多解、无界解、无可行解的判断。
(7) 求解线性规划的单纯形法。
(8) 求解线性规划的人工变量法。
(9) 单纯形法中的 5 个计算公式。
2.学习要求
(1) 深刻领会线性规划的各种基与解的基本概念,它们之间的相互关系。
(2)掌握图解法的计算步骤,注意怎样将目标函数表达成一条直线,这条直线如何平移使得目
标函数值上升或下降。
(3) 熟练掌握单纯形法计算的全过程,特别应注意如何列出单纯形表,如何由一个基可行解换
到另一个基可行解,基可行解是最优解、无界解或多重解的判断准则。
(4) 理解在什么情况下加入人工变量,人工变量起何作用,用大 M 法计算时目标函数的变化,
两阶段法计算时目标函数的构成,掌握这两种计算方法的全过程,在什么情形下线性规划无可行
解。
(5) 理解用矩阵形式代替单纯形表,并用矩阵公式求解线性规划。
3.重点
建立线性规划数学模型,有关线性规划解的概念、解的形式,单纯形法计算、大 M 法、两阶段法。
4.难点解析
(1)建立线性规划数学模型
建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握 3
个要素:研究的问题是求什么,即设置决策变量;问题要达到的目标是什么即建立目标函数,
目标函数一定是决策变量的线性函数并且求最大值或求最小值;限制达到目标的条件是什
么,即建立约束条件。
(2)图解法
图解法要掌握好 3 个步骤:画出满足每个约束的区域,其交集就是可行域;画出目标函
数增加的矢量,与矢量垂直的直线就是目标函数直线;将目标函数直线平行移动到可行域,
如果求最大值就沿着矢量方向平移到可行域的边界,如果求最小值就沿着矢量的反方向平移
到可行域的边界,直线与可行域边界的交点对应的坐标就是最优解,如果交点无界,则线性
规划无界解。
(3)线性规划有关解的关系
要掌握解的关系首先要理解解的概念。例如,要判断“可行解是基本解”这个命题的正确
性,就应知道可行解和基本解的定义,然后分析两者之间的关系。可行解的定义是满足所有约束
的解,包括等式约束、变量非负约束,基本解是令非基变量等于零、基变量满足等式约束的解,
可行解没有区分基变量和非基变量,基本解不一定满足变量非负条件。因此,两个解没有必然的
包含关系,可以理解为一个解可能包含也可能不包含另一个解。由此,该命题是错
错误的。
(4)单纯形法
第一章讲的所有方法统称为单纯形法,其中分不加人工变量的普通单纯形法和加人工变量时
的大 M 单纯形法、两阶段单纯形法。通常对不加人工变量能通过观察找到一个可行基,列
出单纯形表计算的方法,称为普通单纯形法,而不能观察找到可行基,只能通过加入人工变
量寻找原问题的可行基的计算方法,称为人工变量法,具体地是大 M 单纯形法和两阶段单
纯形法,人工变量法是帮我们寻找原问题的一个可行基,当基变量全部是原问题的变量时,
人工变量的任务也就完成,退出单纯形表。大 M 单纯形法和两阶段单纯形法是将人工变量
作为过渡变量,是一种技术处理,两种方法没有本质区别。
5.考核目标
(1)识记有关基本概念、定义及公式。
(2)掌握求解线性规划的单纯形法、人工变量法。
(3)理解不同算法的条件和过程。
第 1 章 线性规划
线性规划(Linear Programming 缩写为 LP)是运筹学的重要分支之一,在实际中应用得较广
泛,其方法也较成熟,借助计算机,使得计算更方便,应用领域更广泛和深入。
线性规划通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如
何统筹兼顾,合理安排,用最少的资源 (如资金、设备、原标材料、人工、时间等)去完成确
定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产
品量最多 、利润最大)。
1.1 数学模型
1.1.1 应用模型举例
【例 1.1】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别
需要要在设备 A、B 上加工,需要消耗材料 C、D,按工艺资料规定,单件产品在不同设备上加
工及所需要的资源如表 1-1 所示。已知在计划期内设备的加工能力各为 200 台时,可供材料分
别为 360、300 公斤;每生产一件甲、乙、丙三种产品,企业可获得利润分别为 40、30、50 元,
假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大?
表 1-1 单位产品资源消耗
产品
消耗
资源
甲 乙 丙 现有资源
设备 A
3 1 2 200
设备 B
2 2 4 200
材料 C
4 5 1 360
材料 D
2 3 5 300
利润(元/件)
40 30 50
【解】这样一个规划问题可用数学语言来描述,即可以用数学模型表示。设在计划期内生产这三
种产品的产量为待定未知数x
1
、x
2
、x
3
,称为决策变量。产品生产得越多,获利就越多,但受到
设备和生产能力的限制,这种能力的限制就是约束条件。计划期内设备A的有效台时为 200,在
安排三种产品的计划时,不得超过设备A的有效台时,这个条件可用不等式 3x
1
+x
2
+2x
3
≤200 来表
示,类似地,对设备B也有相应的不等式 2x
1
+2x
2
+4x
3
≤200;材料消耗总量不得超过供应量,应有
4x
1
+5x
2
+x
3
≤360,2x
1
+3x
2
+5x
3
≤300。生产的产量不能小于零,用数学式子表示就是x
1
≥0、x
2
≥0、
x
3
≥0。这个条件称为决策变量的非负要求。用Z表示利润,则有Z=40x
1
+30x
2
+50x
3
,这个式子就
是目标函数。企业的目标是要使利润达到最大,即目标函数达到最大值,用数学表达式描述就是
max Z=40x
1
+30x
2
+50x
3
。因此这个问题的数学模型为可归纳为
剩余31页未读,继续阅读
资源评论
- canhuangjiyu2014-08-17很基础的东西 。。实在不值10分。。。
zhuoqq
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功