工商管理中的运筹学问题—建模及求解
项目报告
姓名：
课题组的分工或贡献：
课程名称：运筹学
指导教师：
2019年6月
前言
工商管理中的运筹学问题—建模及求解项目报告主要内容为（1）运输问题建模与管理运筹学软件求解及分析；（2）目标规划问题建模与管理运筹学软件求解及分析；（3）整数规划问题建模与管理运筹学软件求解及分析；（4）图论问题与管理运筹学软件求解及分析。范围为运筹学第五版教程中的线性规划、运输问题、目标规划、整数规划和图论等章节。本次项目的实施旨在更好的了解运筹学的理论，学会将运筹学的各种方法应用到实际问题中去，做到学以致用。
4.1研究内容
图论最吸引人的特色是它蕴含着大量有趣的思想、漂亮的图形和巧妙的方法，使非常困难的问题也易于表达。最短路问题是图与网络知识中的经典问题之一，生活中如选址、石油运输管道铺设时的选线、设备更新等问题，都可以归结为最短路问题。此外，图论问题中还包括最大流问题和网络计划问题等。
4.2问题描述
石油管道铺设最优方案的选择问题: 如下图所示，其中v1为出发点，v10为目的地，v2、v3、v4、v5、v6、v7、v8、v9分别为可供选择的各站站点，图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道线路才使总费用最小?
图中各点之间的距离如下: ( 1) V1—V2：3、V1—V3∶5、V1—V4∶4;
( 2) V2—V5∶6、V2—V6∶3、V2—V7∶5、V3—V5∶3、V3-V6∶2、V3-V7∶4、V4-V5∶4、V4— V6∶1、V4—V7∶5；
( 3) V5—V8∶2、V5—V9∶5、V6—V8∶7、V6— V9∶4、V7—V8∶5、V7—V9∶4；
( 4) V8—V10∶3、V9—V10∶4.
4.3求解步骤（Dijkstra 算法）
4.3.1.给v s以P标号，P(v s)=0，其余各点均给T标号，T（v s）=+∞。
4.3.2.若v i点为刚得到P标号的点，考虑这样的点v j:(v i，v j)属于E，且v j为T标号点。
对v j的T标号点进行以下的修改：T（v j）=min[T（v j）,P（v j）+l ij].
4.3.3.比较所有具有T标号的点，把最小的改为P标号，即P（v i'）=min[T（v i）]，
当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则
用v i'代替v i转回4.3.2。
4.5过程分析
4.5.1题目分析
题目为管道铺设求最小费用的问题，即为最短路径问题，求出铺设管道的最短路径，
则管道沿其铺设就是最省钱的铺设方法。
4.5.2方法分析
最短路径问题的解决方法有三种：一Dijkstra算法，计算两个指定点间的最短路，并且权值为非负值；二Ford算法，计算某点到其余各点的最短路，并且权值可为
负数；三Floyd算法，计算任意两点间的最短路，并且权值非负。
Dijkstra 的算法逻辑为贪心算法，贪心算法在对问题求解时，它所做出的每一个选
择都是在当前看来是最好的选择，它不存在回溯的过程，因此它不可用来计算负权
图，这是它的一个缺陷。它所能解决的问题规模都比较小，如应用在导航中解决某
地到其它地方的最短路径等小问题。
而Floyd 的算法逻辑为动态规划算法，动态规划不仅可以得到原问题的最优解，
还可以得到各个子问题的解，它存在回溯的过程，因此它可用来计算负权图，但不
能计算负权回路。解决的问题规模都比较大，如应用到某个城市的规划建设中等大
问题
本例中不存在负权值，且问题规模较小，因此选用Dijkstra算法计算更加简单。
4.5.3结果分析
由软件结果可知，最短路径为v1 -> v3 -> v5 -> v8 -> v10，铺设管道的最小费用为13。
参考文献：
[1]浅谈Dijkstra算法与Floyd算法_黄杭.pdf
[2]管理运筹学中最短路问题的两种算法研究_邱慧.pdf
070105运筹学与控制论 一、专业介绍 1、学科简介 运筹学与控制论是研究各种系统的结构、运作、设计和调控的现代数学学科，是应用数学与系统科学、信息科学的结合点。运筹学与控制论是数学的二级学科，本学科所研究的问题是从众多的可行方案中优选某些目标最优的方案，在社会与经济生活的合理规划、最优设计、最优控制和科学管理中起着十分重要的作用。在自然科学、社会经济中有广泛的应用。 2、培养目标 在政治上培养学生有坚定的政治方向，热爱祖国，坚持四项基本原则，具有全心全意为人民服务的思想。在业务上系统掌握本专业的基本理论，在所研究方向上了解国内外学术动态，具有一定的独立开展科研的能力，并能熟练地运用一门外语阅读专业书刊和撰写论文，成为德、智、体全面发展的运筹学与控制论专业的高级人才。 3、专业方向 01 最优控制理论及其应用 02 随机控制理论与数学金融 4、考试科目 ①101思想政治理论②201英语一③719分析④835代数与几何 (注：各个学校专业方向、考试科目有所不同，以上以复旦大学数学科学学院大学为例) 二、就业前景 1.运筹学 该学科已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制; 运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效; 它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。因此运筹学是很有前景的，今后也可以转管理方向。 2. 控制论 随着自动化水平的不断提高，控制系统本身也日渐复杂，系统中的控制变量数也随之增多，对控制性能的要求也逐步提高，很多情况都要求系统的性能是最优的，如时间最短，误差最小、燃料最省、产量最高、成本最低、效益最大等，而且要求对环境的变化有较强的适应能力，但现在所依据的稳定性、快速性和准确性等设计指标难以满足新的控制要求。所以现在社会对控制人才的要求也越来越高，该专业的毕业生就业前景也是很好的。 三、就业方向 学生毕业后能在科研、教育等部门从事学术研究、技术管理、教学工作，以及在生产、设计、开发等企事业单位从事应用技术研究和管理决策等工作。 四、推荐院校 山东大学、复旦大学、上海大学、浙江大学、大连理工大学、南开大学、重庆大学、四川大学、北京交通大学、清华大学、西安交通大学、哈尔滨工业大学、东北大学、华东师范大学、中国科学技术大学 五、相近专业 相同一级学科下的其他专业有：基础数学、计算数学、概率论与数理统计、应用数学。 六、课程设置(以华东师范大学为例) (一)必修课程 1. 学位公共课 政治理论、外国语、计算机应用、专业外语、教育实习或专业实习; 2. 学位基础课
运筹学（yùnchóuxué）简介 英语全称为：Operational?Research(英国)或者是Operations?Research(美国) 在中国战国时期，曾经有过一次流传后世的赛马比赛，相信大家都知道，这就是田忌赛马。田忌赛马的故事说明在已有的条件下，经过筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。 现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。 运筹学的思想在古代就已经产生了。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法，这就是“运筹帷幄之中，决胜千里之外”的说法。 但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是晚多了。也可以说，运筹学是在二十世纪四十年代才开始兴起的一门分支。 运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，已达到最好的效果。 运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。 虽然不大可能存在能处理及其广泛对象的运筹学，但是在运筹学的发展过程中还是形成了某些抽象模型，并能应用解决较广泛的实际问题。 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 运筹学有广阔的应用领域，它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。 运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。 [编辑本段]运筹学的历史 运筹学作为一门现代科学，是在第二次世界大战期间首先在英美两国发展起来的，有的学者把运筹学描述为就组织系统的各种经营作出决策的科学手段。?P.M.Morse与G.E.Kimball在他们的奠基作中给运筹学下的定义是：“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”运筹学的另一位创始人定义运筹学是：“管理系统的人为了获得关于系统运行的最优解而必须使用的一种科学方法。”它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期发挥最大效益。 现代运筹学的起源可以追溯到几十年前，在某些组织的管理中最先试用科学手段的时候。可是，现在普遍认为，运筹学的活动是从二次世界大战初期的军事任务开始的。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组。 第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。
第5章 运筹学模型 5.2 图论模型 图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。 5.2.1 图的基本概念 城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。 1.图 图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接 起来。 图5-1 由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且 使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1也可以画成图5-2的形式。 图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作 ) , (E V G =。这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序 的。如果边e 连接顶点u 和v ，则记作e = {v u ,}。u 和v 称作e 的端点，e 称作u 和v 的关联边。如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之间可以有不止一条
工商管理中的运筹学问题—建模及求解 项目报告 姓名： 课题组的分工或贡献： 课程名称：运筹学 指导教师： 2019年6月
前言 工商管理中的运筹学问题—建模及求解项目报告主要内容为（1）运输问题建模与管理运筹学软件求解及分析；（2）目标规划问题建模与管理运筹学软件求解及分析；（3）整数规划问题建模与管理运筹学软件求解及分析；（4）图论问题与管理运筹学软件求解及分析。范围为运筹学第五版教程中的线性规划、运输问题、目标规划、整数规划和图论等章节。本次项目的实施旨在更好的了解运筹学的理论，学会将运筹学的各种方法应用到实际问题中去，做到学以致用。
4.1研究内容 图论最吸引人的特色是它蕴含着大量有趣的思想、漂亮的图形和巧妙的方法，使非常困难的问题也易于表达。最短路问题是图与网络知识中的经典问题之一，生活中如选址、石油运输管道铺设时的选线、设备更新等问题，都可以归结为最短路问题。此外，图论问题中还包括最大流问题和网络计划问题等。 4.2问题描述 石油管道铺设最优方案的选择问题: 如下图所示，其中v1为出发点，v10为目的地，v2、v3、v4、v5、v6、v7、v8、v9分别为可供选择的各站站点，图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道线路才使总费用最小? 图中各点之间的距离如下: ( 1) V1—V2：3、V1—V3∶5、V1—V4∶4; ( 2) V2—V5∶6、V2—V6∶3、V2—V7∶5、V3—V5∶3、V3-V6∶2、V3-V7∶4、V4-V5∶4、V4— V6∶1、V4—V7∶5； ( 3) V5—V8∶2、V5—V9∶5、V6—V8∶7、V6— V9∶4、V7—V8∶5、V7—V9∶4； ( 4) V8—V10∶3、V9—V10∶4. 4.3求解步骤（Dijkstra 算法） 4.3.1.给v s以P标号，P(v s)=0，其余各点均给T标号，T（v s）=+∞。 4.3.2.若v i点为刚得到P标号的点，考虑这样的点v j:(v i，v j)属于E，且v j为T标号点。 对v j的T标号点进行以下的修改：T（v j）=min[T（v j）,P（v j）+l ij]. 4.3.3.比较所有具有T标号的点，把最小的改为P标号，即P（v i'）=min[T（v i）]， 当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则 用v i'代替v i转回4.3.2。