运筹学资料:8图与网络模型
- 格式:ppt
- 大小:732.00 KB
- 文档页数:51
《运筹学》综合练习题第一章 线性规划及单纯形法1、教材43页——44页题2、教材44页题3、教材45页题4、教材46页题5、教材46页题6、补充:判断下述说法是否正确LP 问题的可行域是凸集。
LP 问题的基本可行解对应可行域的顶点。
LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。
若LP 问题有两个最优解,则它一定有无穷多个最优解.求解LP 问题时,对取值无约束的自由变量,通常令"-'=j j j x x x ,其中∶≥"'j j x x ,在用单纯形法求得的最优解中,不可能同时出现0"'j j x x .当用两阶段法求解带有大M 的LP 模型时,若第一阶段的最优目标函数值为零,则可断言原LP 模型一定有最优解。
7、补充:建立模型(1)某采油区已建有n 个计量站B 1,B 2…B n ,各站目前尚未被利用的能力为b 1,b 2…b n (吨液量/日)。
为适应油田开发的需要,规划在该油区打m 口调整井A 1,A 2…A m ,且这些井的位置已经确定。
根据预测,调整井的产量分别为a 1,a 2…a m (吨液量/日)。
考虑到原有计量站富余的能力,决定不另建新站,而用原有老站分工管辖调整井。
按规划要求,每口井只能属于一个计量站。
假定A i 到B j 的距离d ij 已知,试确定各调整井与计量站的关系,使新建集输管线总长度最短。
(2)靠近某河流有两个化工厂(见附图),流经第一个工厂的河流流量是每天500万立方米;在两个工厂之间有一条流量为每天200万立方米的支流。
第一个工厂每天排放工业污水2万立方米;第二个工厂每天排放工业污水1.4万立方米 。
从第一个工厂排出的污水流到第二个工厂之前,有20%可自然净化。
根据环保要求,河流中工业污水的含量不应大于%,若这两个工厂都各自处理一部分污水,第一个工厂的处理成本是1000元/万立方米,第二个工厂的处理成本是800元/万立方米。
运筹学:应用分析、试验、量化的方法,对经济管理系统中人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。
第一章、线性规划的图解法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种原料的量。
1预测就是对未来的不确定的时间进行估量或推断2宏观经济预测:是指对整个国民经济范围的经济预测,如国民收入增长率3微观经济预测:是指对单个经济实体的各项经济指标及其所涉及到国内外市场经济形势的预测,如市场需求。
4科技预测:分为科学预测和技术预测。
科学预测包含:科学开展趋势和制造等。
技术预测包含:新技术制造可能应用的领域5社会预测:研究社会开展有关的问题,如人口增长预测,社会购置心理的预测等。
6军事预测:研究与战争、军事有关的问题。
6定性预测:是指利用直观材料,依靠个人经验的主观推断和分析能力,对未来的开展进行预测,又称之为直观预测8定量预测:根据历史数据和资料,应用数理统计方法来预测事物的未来的方法。
9专家小组法:是在接受咨询的专家之间组成一个小组,面对面地进行商量与磋商,最后对需要预测的课题得出比拟一致的意见10时间序列:就是将历史数据按时间顺序排列的一组数字序列。
11时间序列分析法:又称外推法,就是根据预测对象的这些数据,利用数理统计方法加以处理,来预测事物的开展趋势。
12回归分析法:又称回归模型预测法、因果法。
就是依据事物开展的内部因素变化的因果关系来预测事物未来的开展趋势,它是研究变量间相互关系的一种定量预测方法13一元线性回归:它是描述一个自变量与一个因变量间线性关系的回归方程,又称单回归。
14多元线性回归:它是描述一个因变量与多个因变量间线性关系的回归方程,又称复回归。
15最小二乘法:是指寻求使误差平方总和为最小的配合趋势线的方法16决策:就是针对具有明确目标的决策问题,经过调查研究,根据实际与可能,拟定多个可行方案,然后运用统一的标准,选定最正确方案的全过程。
17常规性决策:是例行的、重复性的决策。
18特别性决策:是对特别的、无先例可循的新问题的决策19方案性决策:类似法治系统中的立法工作。
国家或组织的方针政策以及较长方案等都可视为方案性决策的对象。
20操纵性决策:是在执行方针政策或实施方案的过程中,需要作出的决策。
-68-第五章 图与网络模型及方法§1 概论图论起源于18世纪。
第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。
1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。
1857年,凯莱在计数烷22+n n H C 的同分异构物时,也发现了“树”。
哈密尔顿于1859年提出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈、近几十年来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学,生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。
如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。
图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。
哥尼斯堡七桥问题就是一个典型的例子。
在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图1 哥尼斯堡七桥问题当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。
欧拉为了解决这个问题,采用了建立数学模型的方法。
他将每一块陆地用一个点来代替,将每一座桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。
欧拉考察了一般一笔画的结构特点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问题,而且开创了图论研究的先河。
图与网络是运筹学(Operations Research )中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。
《运筹学》第八章图与网络分析习题1.思考题(1)解释下列名词,并说明相互之间的区别与联系:①顶点,相邻,关联边;②环,多重边,简单图;③链,初等链;④圈,初等圈,简单拳;⑤ 回 路,初等路;⑥节点的次,悬挂点,孤立点;⑦)连通图,连同分图, 支 撑子图;⑧有向图,基础图,赋权图。
⑨子图,部分图,真子图.(2)通常用记号G=(V,E)表示一个图,解释V及E的涵义及这个表达式 的涵义.(3)通常用记号D=(V,A)表示一个有向图,解释V及A的涵义及这个表 达式的涵义.(4) 图论中的图与一般几何图形的主要区别是什么? (5) 试述树与图的区别与联系.(6) 试述 求最短路问题的Dijkstra 算法的基本思想及其计算步骤. (7) 试述寻求最大流的标号法的步骤与方法.(8) 简述最小费用最大流的概念及其求解的基本思想和方法.(9) 通常用记号N=(V,A,C)表示一个网络,试解释这个表达式的涵义. (10) 在最大流问题中,为什么当存在增广链时,可行流不是最大流? (11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。
2.判断下列说法是否正确(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系,它与图的几何形状无关。
(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。
(3) 如果一个图G 从V 1到各点的最短路是唯一的,则连接V 1到各点的最短路,再去掉重复边,得到的图即为最小支撑树。
(4 )图G 的最小支撑树中从V 1到V n 的通路一定是图G 从V 1到V n 的最短路。
(5) {f ij =0}总是最大流问题的一个可行流。
(6 )无孤立点的图一定是连通图。
(7) 图中任意两点之间都有一条简单链,则该图是一棵树。
(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。
(9)在图中求一点V1到另一点Vn 的最短路问题总可以归结为一个整数规划问题 (10) 图G 中的一个点V 1总可以看成是G 的一个子图。