运筹学图与网络分析例题

第5章 图论与网络分析

图的基本概念 最小支撑树问题 网络分析 最短路径问题 网络最大流问题

图论起源： 图论起源：哥尼斯堡七桥问题

A C B D C

A D B

问题：一个散步者能否从任一块陆地出发， 问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？ 座桥，且每座桥只走过一次，最后回到出发点？ 结论： 结论：每个结点关联的边数均为偶数

§1 图的基本概念

1. 图 由点和边组成，记作 由点和边组成，记作G=(V，E)，其中 ， ， V=(v1，v2，……，vn)为结点的集合， 为结点的集合， ， 为结点的集合 E=(e1，e2，……，em) 为边的集合。 为边的集合。 ， 点表示研究对象 边表示研究对象之间的特定关系

p114

2、图的分类 、

无向图，记作 无向图，记作G=(V，E) ， 图 有向图，记作 有向图，记作D=(V，A) ， 例1：哥尼斯堡桥问题的图为一个无向图。 ：哥尼斯堡桥问题的图为一个无向图。 例2：五个球队的比赛情况，v1 ：五个球队的比赛情况， v2 表示v1胜v2。 表示 有向图的边 称为弧 称为弧。

v5 v1 v4

v2

v3

e1

例

v1 e10 v6 e9 e8

e2 e5 e6 v5

v2 e3

最短路问题最短(通)路问题是最重要 的优化问题之一，例如各种管道 的铺设、线路的安排、厂区的布 局、设备的更新及运输网络的最 小费用流等。(最短距离、费时 最少、费用最省)

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

一般的最短路问题描述：给定一个赋权有向图D=(V,A),对每一个弧a=(vi,vj),相应 地有权w(a)=wij,又给定D中的任何两个顶点vs和vt ,设P是 从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P), 最短路问题就是要在所有从vs到vt的路中，求一条权最小的路， 即一条从vs到vt的路P0使得：

(P0 ) min (P)P

路P0的权称为从vs到vt的距离，记为d(vs,vt)。

求网络上的一点到其它点 的最短路 Dinkstra标号法

这是解决网络中某一点到其它点的最 短路问题时目前认为的最好方法。 适用于有向图权值非负的情况

有向图权值非负---- Dijkstra算法

Dijkstra算法的基本步骤(权值非负) 1、给顶点v1标号(0),v1称为已

一、绪论

一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不连续参加考试，试设计一个考试日程表。 二、图解法

例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？ 3.1 产品 工时单耗 生产能力 2.1 车间 甲 乙 设备 原料A 原料B 单位产品获利 Ⅰ 1 2 0 50元 Ⅱ 1 1 1 100元 资源限制 300台时 400千克 250千克 A B C 1 0 0 2 3 4 8 12 36 单位产品获利 3 5 例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小

第6章 图与网络分析 §6.1 图的基本概念

§6.2 树图和图的最小部分树 §6.3 最短路问题

§6.4 网络的最大流 §6.5 最小费用流

第1页

引 言图论是运筹学的一个经典和重要的分支，它起源于欧拉 (Euler)对七桥问题的抽象和论证。 1936年，匈牙利数学家柯尼希(Kö nig)出版了图论的 第一部专著《有限图与无限图理论》,竖立了图论发展的第 一座里程碑。 此后，图论进入发展与突破的快车道，所研究的问题涉 及经济管理、工业工程、交通运输、计算机科学与信息技术、 通讯与网络技术等诸多领域。近几十年来，由于计算机技术 和科学的飞速发展，大大地促进了图论研究和应用，图论的 理论和方法已经渗透到物理、化学、通讯科学、建筑学、生 物遗传学、心理学、经济学、社会学等学科中。

图论研究点与边的连接关系、一笔画问题、通路、最短 路、最大流量。而诸如“四色问题”,“旅行商问题”等世 界著名的难题都属于图论的研究范畴。第2页

§6.1 图的基本概念运筹学中研究的图是生活中各类图的抽象概括, 它表明一些研究对象和这些对象之间的相互关系。 用点表示研究对象，用边表示这些对象之间的联 系，

图与网络分析

第5章 图与网络分析( Graph Theory and Network Analysis )

图的基本概念与模型树 最短路问题

网络的最大流最小费用流 应用举例

图与网络分析

第一节 图的基本概念与模型近代图论的历史可追溯到18世纪的七桥问题—穿过 Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不 可能存在这样的路线。

Kö nigsberg桥对应的图

图与网络分析

一、图基本概念例1、有甲、乙、丙、丁、戊五个球队， 它们之间比赛的情况也可以用图表示出来。V5 e5 e4 e6 e7 e2 e3 V3 V4

V1e1 V2

图与网络分析

例2 某单位储存八种化学药品，其中某些 药品是不能存放在同一个库房里的。为了反映 这个情况可以用点V1,V2,……V8分别代表这八 种药品，若药品Vi和药品Vj是不能存放在同 一个库房的，则在Vi和Vj之间连一条线。V2 V1 · V8 V3 V4 V5

V6 V7

图与网络分析

一般地，当用图论研究一个实际问题时， 常以顶点(Vertex)表示要研究的对象，以 它们之间的连线，表示

管理运筹学案例分析

产品产量预测

一、问题的提出

2007年，山西潞安矿业集团与哈密煤业集团进行重组，成立了潞安新疆煤化工（集团）有限公司。潞安新疆公司成立后，大力加快新项目建设。通过技术改造和加强管理，使煤炭产量、销售收入、利润、职工收入等得到了大幅提高，2007年生产煤炭506万吨，2008年煤炭产量726万吨，2009年煤炭产量956万吨。三年每月产量见下表，请预测2010年每月产量。

表1 2007—2009年每月产量表 单位：万吨

2007年 一月 二月 三月 四月 五月 六月 七月 八月 九月 十月 十一月 十二月 合计 产 量 46.84 51.52 36.46 26.23 34.15 44.26 32.43 46.52 44.13 51.69 46.78 45.12 506.13 2008年 一月 二月 三月 四月 五月 六月 七月 八月 九月 十月 十一月 十二月 合计 产 量 53.82 68.98 52.22 43.33 51.12 63.72 51.58 65.62 69.55 70.12 68.33 67.45 725.84 200

《运筹学与系统分析》课程习题集

【说明】：本课程《运筹学与系统分析》（编号为02627）共有单选题,多项选择题,计算题,判断题等多种试题类型 一、单选题

1. 一个线性规划问题（P）与它的对偶问题（D）不存在哪一个关系 【 】

A.(P)可行（D）无解，则（P）无有限最优解 B.(P)、(D）均有可行解，则都有最优解 C.(P)有可行解，则（D）有最优解 D.(P)(D)互为对偶

2.3.

当线性规划问题的一个基本解满足下列哪项要求时称之为一个基本可行解

【 】

A.大于0 B.小于0 C.非负 D.非正

在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中

【 】

A.b列元素不小于零 B.检验数都大于零 C.检验数都不小于零 D.检验数都不大于零

4.

若运输问题已求得最优解，此时所求出的检验数一定是全部

【 】

A.大于或等于零 B.大于零 C.小于零 D.小于或等于零

5.

在线性规划模型中，没有非负约束的变量称为

【 】

第 1 页 共 39 页

运筹学(专升本)阶段性作业4 总分: 100分 考试时间:分钟 判断题

1. 存储由于需求而不断减少，所以在一定的时候必须进货，也即对存储进行补充。(5分) 正确错误 参考答案：正确 解题思路：

2. 存储系统是一个由订货、存储、需求三个环节紧密构成的现实运行系统。(5分) 正确错误 参考答案：正确 解题思路：

3. 按性质分类，可将决策分为程序化决策和非程序化决策。(5分) 正确错误 参考答案：错误 解题思路：

4. 运筹学的目的在于针对所研究的系统求得一个合理应用人才，物力和财力的最佳方案。(5分) 正确错误 参考答案：正确 解题思路：

5. 运筹学的主要研究对象是各种有组织系统的管理问题及生产经营活动。(5分) 正确错误 参考答案：正确 解题思路：

6. 风险型决策问题是指决策者对某一自然因素发生的概率是未知的。(5分) 正确错误 参考答案：错误 解题思路：

7. 在风险型决策问题中，如果自然因素出现的概率为0，而其他自然因素出现的概率为1，即为确定性决策问题。(5分) 正确错误 参考答案：错误 解题思路：

8. 对于同一个目标，虽然决策者“选优”原则不同，但所选的最优方案相同。(5分)

正确错误 参考答案：错误 解题思路：

填空题

运筹学

沈轶

华中科技大学控制科学与工程系

目录

第一章 线性规划的单纯形法 ....................................................................................................... 1 §1.1 线性规划的基本概念 ............................................................................................................ 1 §1.2 线性规划的基本定理 ............................................................................................................ 4 §1.3 线性规划的图解法（变量?2个） ..................................................................................... 7 §1.4 单纯形法

运筹学(专升本)阶段性作业4 总分: 100分 考试时间:分钟 判断题

1. 存储由于需求而不断减少，所以在一定的时候必须进货，也即对存储进行补充。(5分) 正确错误 参考答案：正确 解题思路：

2. 存储系统是一个由订货、存储、需求三个环节紧密构成的现实运行系统。(5分) 正确错误 参考答案：正确 解题思路：

3. 按性质分类，可将决策分为程序化决策和非程序化决策。(5分) 正确错误 参考答案：错误 解题思路：

4. 运筹学的目的在于针对所研究的系统求得一个合理应用人才，物力和财力的最佳方案。(5分) 正确错误 参考答案：正确 解题思路：

5. 运筹学的主要研究对象是各种有组织系统的管理问题及生产经营活动。(5分) 正确错误 参考答案：正确 解题思路：

6. 风险型决策问题是指决策者对某一自然因素发生的概率是未知的。(5分) 正确错误 参考答案：错误 解题思路：

7. 在风险型决策问题中，如果自然因素出现的概率为0，而其他自然因素出现的概率为1，即为确定性决策问题。(5分) 正确错误 参考答案：错误 解题思路：

8. 对于同一个目标，虽然决策者“选优”原则不同，但所选的最优方案相同。(5分)

正确错误 参考答案：错误 解题思路：

填空题