运筹学——图与网络模型3
- 格式:ppt
- 大小:1.17 MB
- 文档页数:49
运筹学:应用分析、试验、量化的方法,对经济管理系统中人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。
第一章、线性规划的图解法1.基本概念线性规划:是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。
线性规划的三要素:变量或决策变量、目标函数、约束条件。
目标函数:是变量的线性函数。
约束条件:变量的线性等式或不等式。
可行解:满足所有约束条件的解称为该线性规划的可行解。
可行域:可行解的集合称为可行域。
最优解:使得目标函数值最大的可行解称为该线性规划的最优解。
唯一最优解、无穷最优解、无界解(可行域无界)或无可行解(可行域为空域)。
凸集:要求集合中任意两点的连线段落在这个集合中。
等值线:目标函数z,对于z的某一取值所得的直线上的每一点都具有相同的目标函数值,故称之为等值线。
松弛变量:对于“≤”约束条件,可增加一些代表没使用的资源或能力的变量,称之为松弛变量。
剩余变量:对于“≥”约束条件,可增加一些代表最低限约束的超过量的变量,称之为剩余变量。
2.线性规划的标准形式约束条件为等式(=)约束条件的常数项非负(b j≥0)决策变量非负(x j≥0)3.灵敏度分析:是在建立数学模型和求得最优解之后,研究线性规划的一些系数的变化对最优解产生什么影响。
4.目标函数中的系数c i的灵敏度分析目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时,最优解不变。
5.约束条件中常数项b i的灵敏度分析对偶价格:约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。
当某约束条件中的松弛变量(或剩余变量)不为零时,这个约束条件的对偶价格为零。
第二章、线性规划问题在工商管理中的应用1.人力资源分配问题(P41)设x i为第i班次开始上班的人数。
2.生产计划问题(P44)3.套材下料问题(P48)下料方案表(P48)设x i为按各下料方式下料的原材料数量。
4.配料问题(P49)设x ij为第i种产品需要第j种原料的量。
运筹学概念整理名解5、简答4、建模与模型转换2、计算5~6第1章线性规划与单纯形法(计算、建模:图解法)线性规划涉及的两个方面:使利润最大化或成本最小化线性规划问题的数学模型包含的三要素:一组决策变量:是模型中需要首确定的未知量。
一个目标函数:是关于决策变量的最优函数,max或min。
一组约束条件:是模型中决策变量受到的约束限制,包括两个部分:不等式或等式;非负取值(实际问题)。
线性规划问题(数学模型)的特点:目标函数和约束条件都是线性的。
1.解决的问题是规划问题;2解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;3解决问题的约束条件是多个决策变量的线性不等式或等式。
图解法利用几何图形求解两个变量线性规划问题的方法。
求解步骤:第一步:建立平面直角坐标系;第二步:根据约束条件画出可行域;第三步:在可行域内平移目标函数等值线,确定最优解及最优目标函数值。
LP问题的解:(原因)唯一最优解、无穷多最优解(有2个最优解,则一定是有无穷多最优解)无界解(缺少必要的约束条件)、无可行解(约束条件互相矛盾,可行域为空集)标准形式的LP模型特点:目标函数为求最大值、约束条件全部为等式、约束条件右端常数项bi全部为非负值,决策变量xj的取值为非负●线性规划模型标准化(模型转化)(1) “决策变量非负”。
若某决策变量x k为“取值无约束”(无符号限制),令:x k= x’k–x”k,(x’k≥0, x”k≥0) 。
(2) “目标函数求最大值”。
如果极小化原问题minZ = CX,则令Z’ = – Z,转为求maxZ’ = –CX 。
注意:求解后还原。
(3) “约束条件为等式”。
对于“≤”型约束,则在“≤”左端加上一个非负松弛变量,使其为等式。
对于“≥”型约束,则在“≥”左端减去一个非负剩余变量,使其为等式。
(4) “资源限量非负”。
若某个bi < 0,则将该约束两端同乘“–1” ,以满足非负性的要求。
试题结构:1、判断题(10×2`)2、单选题(10×2`)3、多选题(5 ×2`)4、计算题(5×10`)(第三、五、七、十一、十三章有计算题)第一张:绪论1.定义:运筹学是应用分析、试验、量化的方法,对经济管理系统中人力、物力、财力等资源进行统筹安排,为管理者提供有依据的最优方案,以实现最有效的管理。
2.研究内容:线性规划、整数线性规划、目标规划、图与网络模型、存储论、排队论、对策论、排序与统筹方法、决策分析、动态规划、预测3.运用运筹学解决问题的一般过程(课件答案)(课本答案)规定目标和明确问题认清问题收集数据和建立模型找出一些可供选择的方案求解模型和优化方案确定目标或评估方案的标准检验模型和评价方案评估各个方案方案实施和不断改进选出一个最优的方案执行此方案进行最后评估:问题是否得到圆满解决第二章:线性规划的图解方法1.怎样辨别一个模型是线性模型?其特征是:(1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;(2)问题的约束条件是一组多个决策变量的线性不等式或等式。
2.线性规划三个要素建模步骤决策变量、目标函数、约束条件3.LP 问题的标准型11max .1,2,,0,1,2,,nj jj nij ji j j Z c x a x b s t i m x j n ===⎧=⎪=⎨⎪≥=⎩∑∑ 特点:(1)目标函数求最大值(2)约束条件都为等式方程,且右端常数项b i 都大于或等于零 (3)决策变量x j 为非负。
一般形式目标函数: max (min ) z = c 1 x 1 + c 2 x 2 + … + c n x n约束条件: s.t. a 11 x 1 + a 12 x 2 + … + a 1n x n ≤ ( =, ≥ )b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n ≤ ( =, ≥ )b 2…… …… a m1 x 1 + a m2 x 2 + … + a mn x n ≤ ( =, ≥ )b mx 1 ,x 2 ,… ,x n ≥ 0 标准形式目标函数: max z = c 1 x 1 + c 2 x 2 + … + c n x n 约束条件: s.t. a 11 x 1 + a 12 x 2 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n = b 2 …… …… a m1 x 1 + a m2 x 2 + … + a mn x n = b mx 1 ,x 2 ,… ,x n ≥ 0,b i ≥04.线性问题的性质与判断 (1 )线性规划可行域为凸集(2)最优解在凸集上某一顶点达到(特殊情况下为凸集的某条边)(3 )可行域有界,则一定有最优解5.图解法与解的状况(1)图解法使用范围:仅有两个决策变量的LP(2)基本步骤:a.建立平面直角坐标系;b.将约束条件图解,求得满足约束条件的解的集合;c.作出目标函数的等值线,并根据优化要求,平移目标函数等值线,求出最优解。
运筹学模型的分类和类型运筹学是一门应用于决策制定和问题解决的学科,它通过数学模型和分析方法来优化资源的利用。
运筹学模型是在特定情境中描述问题和优化目标的数学表示。
根据问题的性质和优化目标的类型,运筹学模型可以被分类为多种类型。
在本文中,我将介绍一些常见的运筹学模型分类。
一、线性规划模型:线性规划模型是最基本的运筹学模型之一。
它的特点是目标函数和约束条件均为线性的。
线性规划模型常用于求解资源分配、生产计划、物流运输等问题。
通过线性规划模型,我们可以找到使资源利用最优化的决策方案。
某公司需要确定每种产品的生产数量,以最大化总利润,且需满足各种资源约束条件,这时可以使用线性规划模型进行求解。
二、整数规划模型:整数规划模型是在线性规划模型的基础上引入整数变量的扩展。
在某些情况下,问题的决策变量只能取整数值,这时就需要使用整数规划模型进行求解。
某物流公司需要确定车辆的调度方案,每辆车的装载量可以是整数,这时可以使用整数规划模型来求解最佳调度方案。
三、动态规划模型:动态规划模型是一种考虑时间因素的决策模型。
它通常用于求解多阶段决策问题。
动态规划模型通过将问题划分为多个阶段,并建立各阶段之间的转移方程,来寻找最优决策序列。
在项目管理中,我们需要确定每个阶段的最佳决策,以最小化总工期和成本,这时可以使用动态规划模型进行求解。
四、网络流模型:网络流模型是一种描述网络中资源分配和流量传输的模型。
它通常用于求解网络优化问题,如最小费用流问题、最大流问题等。
网络流模型中,节点表示资源或流量的源点、汇点和中间节点,边表示资源或流量的传输通道。
通过建立网络流模型,我们可以确定资源的最优分配方案,以及网络中的最大流量或最小成本。
在供应链管理中,我们需要确定货物从生产商到消费者的最佳流向,以最小化总运输成本,这时可以使用网络流模型进行求解。
五、排队论模型:排队论模型是一种描述排队系统的模型。
它通常用于评估系统性能指标,如平均等待时间、平均逗留时间等。
数学:运筹学(三)1、判断题凡基本解一定是可行解()正确答案:错2、单选无界解是指()。
A.可行域无界B.目标函数值无界C.两者均无界D.以上均不正确正确答案:B3、填空题运输问题的模型中,含有的方程(江南博哥)个数为()个正确答案:n+M4、单选关于互为对偶的两个模型的解的存在情况,下列说法不正确的是()。
A.都有最优解B.都无可行解C.都为无界解D.一个为无界解,另一个为无可行解正确答案:C5、单选在用对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中()A.b列元素不小于零B.检验数都大于零C.检验数都不小于零D.检验数都不大于零正确答案:D6、填空题目标规划建模中要对多个目标优先等级进行区分,采用给目标赋予()与权系数的方法。
正确答案:优先因子7、名词解释专家小组法正确答案:是在接受咨询的专家之间组成一个小组,面对面地进行讨论与磋商,最后对需要预测的课题得出比较一致的意见。
8、填空题线性规划问题有可行解,则必有()正确答案:基可行解9、单选对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中()A.b列元素不小于零B.检验数都大于零C.检验数都不小于零D.检验数都不大于零正确答案:D10、填空题运筹学的主要研究对象是各种有组织系统的管理问题,()正确答案:经营活动11、填空题特尔斐法和专家小组法都是请一批专家进行判断预测,二者的主要区别是,前者专家们发表意见是背靠背,后者专家们面对面进行讨论与()。
正确答案:磋商12、填空题在解决最大流问题的算法中,图解法引出了()的基本原理正确答案:最大流-最小割集13、判断题如线性规划问题存在最优解,则最优解一定应可行域边界上的一个点。
正确答案:对14、问答题简述应用系统分析的原则。
正确答案:(1)坚持问题导向;(2)以整体为目标;(3)多方案模型分析和优选;(4)定量分析与定性分析相结合;(5)多次反复进行。
15、单选运输问题求解时,得到最优解的条件是数字格的检验数为零,空格的检验数全部()A.非负B.非正C.零D.大于零正确答案:A16、填空题在线性规划问题中,基可行解的非零分量所对应的列向量线性()正确答案:无关17、单选满足线性规划问题全部约束条件的解称为()A.最优解B.基本解C.可行解D.多重解正确答案:B18、名词解释单一时间估计法正确答案:就是在估计各项活动的作业时间时,只确定一个时间值19、填空题运筹学的主要目的在于求得一个合理运用人力、物力和财力的()正确答案:最佳方案20、填空题20世纪40年代后,Dantzig给出线性规划的有效解法称为()正确答案:单纯形法21、单选以下关系中,不是线性规划与其对偶问题的对应关系的是()。
-68-第五章 图与网络模型及方法§1 概论图论起源于18世纪。
第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。
1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。
1857年,凯莱在计数烷22+n n H C 的同分异构物时,也发现了“树”。
哈密尔顿于1859年提出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈、近几十年来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学,生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。
如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。
图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。
哥尼斯堡七桥问题就是一个典型的例子。
在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图1 哥尼斯堡七桥问题当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。
欧拉为了解决这个问题,采用了建立数学模型的方法。
他将每一块陆地用一个点来代替,将每一座桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。
欧拉考察了一般一笔画的结构特点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问题,而且开创了图论研究的先河。
图与网络是运筹学(Operations Research )中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。
项目四图与网络分析任务八图与网络的应用练习1、求下图的最小支撑树。
用破圈法求该图的最小支撑树:(1)(2)(3)(4)2、分别用破圈法和避圈法求下列各个图的最小支撑树。
a-1:用破圈法求图a的最小支撑树:a-2:用避圈法求图a的最小支撑树:b-1:用破圈法求图b 的最小支撑树:b-2:用避圈法求图b 的最小支撑树:3、用标号法求下图中1v 至7v 的最短路。
1)标号过程(1)初始化;令起点v 1的标号为P ,记做P(1) =0;令其余各点的标号为T ,记做T(i)=∞;(2)计算T标号:刚得到P标号的点为v1,考虑所有与v1相邻的T标号点v 2、v3、v5,修改v2、v3、v5的T标号为:T(2)=min[T(2),P(1)+d12]=min[+∞,0+4]=4T(3)=min[T(3),P(1)+d13]=min[+∞,0+3]=3T(5)=min[T(5),P(1)+d15]=min[+∞,0+5]=5 (3)确定P标号:在所有的T标号点中,找出标号值最小的点标上P标号。
T(2)= 4 T(3) =3 T(4) =+∞T(5)=5 T(6)= +∞ T(7)= +∞令P(3)=3。
(4)计算T标号:刚得到P标号的点为v3,考虑所有与v3相邻的T标号点v 6,修改v6的T标号为:T(6)=min[T(6),P(3)+d36]=min[+∞,3+2]=5 (5)确定P标号:在所有的T标号点中,找出标号值最小的点标上P标号。
T(2)= 4 T(4) =+∞ T(5)=5 T(6)= 5 T(7)= +∞令P(2)=4。
(6)计算T标号:刚得到P标号的点为v2,考虑所有与v2相邻的T标号点v 5,修改v5的T标号为:T(5)=min[T(5),P(2)+d25]=min[5,4+1]=5(7)确定P标号:在所有的T标号点中,找出标号值最小的点标上P标号。
T(4) =+∞ T(5)=5 T(6)= 5 T(7)= +∞令P(5)=5。