运筹学课程总结

1、xxxx运 筹 学 课姓名：xxx学号：xxxxxx班级：xxxxxxxxx古人云 “运筹帷幄之中， 决胜千里之外”运筹学是 20 世纪三四十年代发展起来的一门新兴交叉学科， 它主要研究人类对各种资源的运用及筹划活动， 以期通过了解和发展这种运用及筹划活动的基本规律， 发挥有限资源的最大效益， 达到总体最优的目标。经过这一个学期的学习， 我们应该熟练地掌握、 运用运筹学的精髓， 用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、 物力等有限资源进行合理的统筹安排。 本着这样的心态， 在本学期运筹学课程将结束之际，我对本学期所学知识作出如下总结。一、线性规划线性规

2、划解决的是： 在资源有限的条件下， 为达到预期目标最优， 而寻找资源消耗最少的方案。而线性规划问题指的是在一组线性等式或不等式的约束下，求解一个线性函数的最大或最小值的问题。 其数学模型有目标函数和约束条件组成。解决线性规划问题的关键是找出他的目标函数和约束方程， 并将它们转化为标准形式。 目前解决线性规划问题的主要方法有： 图解法、 单纯型法、 两阶段法、对偶单纯型法等方法。自 1939 年苏联数学家康托罗维奇提出线性规划问题和1947年美国数学家丹齐格求解线性规划问题的通用方法单纯形法以来，线性规划可以说是研究得最为透彻的一个研究方向。 单纯形法统治线性规划领域达40 年之久，而且至今仍是

3、最好的应用最广泛的算法之一。简单的设计2 个变量的线性规划问题可以直接运用图解法得到。 但是往往在现实生活中， 线性规划问题涉及到的变量很多， 很难用作图法实现， 但是运用单纯形法记比较方便。 在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代， 当所有的变量检验数不大于零， 且基变量中不含人工变量， 计算结束。将所得的量的值代入目标函数，得出最优值。线性规划是这门课程第一章的教学内容， 作为运筹学的基础学习， 因此对于这个知识点的学习还是比较认真的。初步学会如何从实际问题中提炼数学模型，以及解答， 理解了单纯形法的思想并会运用单纯形法解答线性方程组， 但是

4、在学习过程中一些定理比较难以理解。 对此， 需要在课后好好复习， 认真消化课程内容，才能真正理解，熟练应用。二、整数规划整数规划是解决决策变量只能取整数的规划问题， 一个规划问题中要求部分或全部决策变量是整数， 则这个规划称为整数规划； 当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。很多实际规划问题都属于整数规划问题。例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数。 2. 人员的合理安排问题，当变量xij =1 表示安排第 i 人去做 j 工作，xij =0 表示不安排第 i 人去做 j 工作。整数规划的解法有割平面法和分支定界法。 其中

5、分枝定界法的思路是： 首先，不考虑解为整数的要求， 用单纯法求最优解， 以此作为目标函数值的上限或下限；其次， 选择其中一个非整数的变量， 根据与两侧相近的整数划分可行域， 在缩小的可行域 （ 子域 ） 内寻求最优整数解，以此作为目标函数值的上限或下限；最后，不断重复以上过程，直到每一个可能进一步分解的非整数都找到整数解时为止。具体步骤：1. 求整数规划的松弛问题最优解；2. 若松弛问题的最优解满足整数要求， 得到整数规划的最优解， 否则转下一步；3. 任意选一个非整数解的变量xi ,在松弛问题中加上约束xi < xi及xixi+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：

6、当原问题是求最大值时， 目标值是分枝问题的上界； 当原问题是求最小值时， 目标值是分枝问题的下界；4. 检查所有分枝的解及目标函数值， 若某分枝的解是整数并且目标函数值大于（ max） 等于其它分枝的目标值， 则将其它分枝剪去不再计算, 若还存在非整数解并且目标值大于（ma%整数解的目标值，需要继续分枝，再检查，直到得到最优解。整数规划中决策变量全部取0 或 1 的规划称为 0 1 整数规划。在实际问题中，该方法能够解决很多问题，例如，对某一个项目要不要投资的决策问题，可选用一个逻辑变量x ，当 x=1 表示投资， x=0 表，示不投资。此外指派问题就是0-1能糊划嘴阕厂个特例。&1（

7、第数崂的解2f法有枚举法和隐枚举法。完全枚举法是将每个变量都只取0 或 1 两个值， 变量可能取值的 0-1 组合是有限的，并且个数为2n。然后列出各变量分别取0或1的每种组合，然后在满足约束条件变量的 0-1 组合中找出使目标函数达到最优值的组合即是该0-1 规划的最优解。 用这种方法求解变量个数为 n 的 0-1 规划， 通常需要检查2n 个组合。计算量大，随变量数量的增加呈几何级数增长。隐枚举法的步骤：1. 找出任意一可行解，目标函数值为z0。2. 原问题求最大值时，则增加一个约束（过滤条件）当求最小值时，上式改为小于等于约束3. 列出所有可能解，对每个可能解先检验式（ * ） ，若满足

8、再检验其它约束，若不满足式（ * ） ，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值4. 目标函数值最大（最小）的解就是最优解通过本章学习，认识并理解了线性整数规划模型的特征，明白纯整数规划、混合整数规划、 0 1 整数规划之间的区别，学会如何从实际问题中提炼出合理的数学模型。 此外理解了分枝定界的思想含义并掌握分枝定界的方法， 知道如何选择合适的“ 枝”生“ 枝” ，掌握何时停止生“ 枝” 。三、运输与指派问题人们在从事生产活动中， 不可避免地要进行物资调运工作。 如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间

9、的运输费用， 如何制定一个运输方案， 使总的运输费用最小。这样的问题称为运输问题。运输单纯形法也称为表上作业法， 是直接在产销平衡运价表上求最优解的一种方法。它的步骤是：首先确定一个初始调运方案，主要方法有最小元素法、元素差额法、 左上角法； 然后通过非基变量的检验数检验是否为最优方案， 不是就调整运量， 直到选出最优方案停止， 求检验数的常用方法有两种， 闭回路法和位势法。指派问题也称分配或配置问题， 是资源合理配置或最优匹配问题。 例如， 假设m个人恰好做m项工作，第i个人做第j项工作，如何分配工作使效率最佳。解指派问题的有效方法是匈牙利算法， 但是匈牙利法要一定的条件条件： 问题求最小值

10、、人数与工作数相等、效率非负。运输与指问题实质就是整数规划中的特例。 在这一章中我主要学习到了对整数规划中的特例方便解决的方法， 运输单纯形法和匈牙利法， 掌握如何求初始运输方案、求检验数、整运量，理解检验数的经济意义。在运输问题中学会延伸，对于不平衡运输问题学会转化为平衡问题， 极大值问题转化为极小值问题。 对于指派问题掌握匈牙利法的步骤， 了解他的使用条件， 此外掌握解决指派问题的其它变异问题的方法， 如最大化指派问题、 人数和工作数不等的指派问题、 一个人可做几项工作的指派问题、某项工作一定不能由某人做的指派问题。四、网络模型图论是交通系统分析中的重要工具， 在交通系统规划、 管理中作用

11、巨大， 也是对实际交通网络进行抽象分析的重要手段。 在网络模型这一章中我们主要学习了图论有关知识， 学习了如何利用图来解决最小数问题、 最短有向路问题、 最大流问题与最小费用流问题。一个无圈并且连通的无向图称为树图或简称树， 将网络图边上的权看作两点间的长度（距离、费用、时间） , 定义图的部分树的长度等于其中每条边的长度之和， 则图中所有部分树中长度最小的部分树称为最小部分树。 最小部分树可以直接用作图的方法求解。常用的有破圈法和加边法（避圈法） 。最短路问题， 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。 最短路问题是重要的优化问题之一， 在实际中具有广泛的应用， 如

12、管道铺设、线路选择等问题，设备更新、投资等。最短路问题可以作为解决其它优化问题的一种基本工具。 常见的求最短路的两种算法有狄克斯屈拉（dijkstra）标号算法和 floyd（ 弗洛伊德 ） 矩阵算法。标号算法是求两个固定点之间的最短路，矩阵算法则可以求任意点之间的最短路。最大流问题的应用十分广泛， 例如使交通网络的道路通行能力 （车流量） 最大、 使沟渠系统的水流量最大、 使石油管道系统的石油流量最大等等， 解决最大流问题的方法有ford-fulkerson 标号算法，其中关键是找寻找增广链，当且仅当不存在增广链时，可行流为最大流。在这章的学习中， 我们将生活中的实际问题化成简单的图， 利用

13、图的方法进行求解， 找出合理方案， 例如利用最大流解决最大匹配问题和劳动力合理配置问题。 本章节还有两个经典问题旅行售货员问题和中国邮递员问题， 经过本章的学习，我体会到了数学的神奇与强大应用性。五、网络计划网络计划即网络计划技术，是指用于工程项目的计划与控制的一项管理技术，一般项目管理中应用较多。它主要包括计划协调技术（pert与关键路线法（cpm组成。pertfc要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。 cpm以经验数据确定工作时间， 工作时间是确定的数值， 主要研究项目的费用与工期的相互关系。两种方法融为一体，统称为网络计划、网络计划技术。网络计划工作过程就是先编制项目工序， 然后根据工序绘制网络图， 通常分为： 箭线网络图和节点网络图， 接着通过对网络时间参数计算找出关键路线， 主要方法有枚举法、 0-1 规划模型和关键工序法，最后计划时间进行网络优化。在本章节中，我们主要学习了如何利用图来解决生产生活中的人力、物力、财力等资源以及工作时间限制下的生产加工流程的统筹规划。 通过做网络图， 我们可以清晰地求解出每个问题的