运筹学课程总结.doc

《运筹学课程总结.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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]及xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题

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

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