运筹学知识重点、重要结论.doc

第一章线性规划问题
知识重点:
1 .将给定的线性规划问题化为标准型
2 .能根据简单的实际问题,建立线性规划问题的数学模型,并用单纯形法求解
3 .几个重要结论
1 )若线性规划问题存在最优解,它一定在可行域的某个顶点得到。
2 )若在两个顶点同时得到最优解,则它们连线上的任意一点都是最优解,即有无穷多最优解。
3 )线性规划问题的每个基可行解对应可行域的一个顶点。
4 )线性规划问题的可行解如为最优解,则该可行解一定是基可行解。
第二章对偶理论与灵敏度分析
知识重点:
1 .对于给定的线性规划问题,能写出它的对偶问题
2 .给定原问题(或对偶问题)的最优解,求对偶问题(或原问题)的最优解。
3 .对偶单纯形法
4 .对偶问题的经济解释,影子价格
5 .几个重要结论
1 )若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。
2 )若原问题有最优解,那么对偶问题也有最优解;且目标函数值相等。
3 )若线性规化的原问题有无穷多最优解,则其对偶问题也一定具有无穷多最优解。
4 )当对偶问题无可行解时,其原问题无最优解。
5 )若线性规划问题和对偶问题都具有可行解,则该线性规划问题一定具有无限最优解或有限最优解。
第三章运输问题
知识重点:
•  平衡问题的求解方法————表上作业法
•  不平衡问题的求解方法:
先将其转换为平衡问题,然后用表上作业发求解。
3 .表上作业法分三个步骤:
1 )确定初始方案————最小元素法
2 )进行最优性检验—————位势法
3 )调整、改进非最优方案——闭回路法
4 .几个重要结论
•  运输问题是一种特殊的线性规划问题,它一定有最优解
•  用表上作业法求解运输问题时要求:产、销平衡
•  当所有产地的产量和销地的销量均为整数值时,运输问题的最优解也为整数值
•  表上作业法与单纯形法在求解最优解的问题上没有本质的区别
第四章目标规划
知识重点:
•  根据简单的实际问题,建立目标规划模型
•  目标规划模型的求解方法:图解法,单纯形法
•  分析目标规划的优先因子变化对原满意解的影响
•  重要结论
线性规划问题是目标规划问题的一种特殊形式。
第五章整数规划
知识重点:
•  求解纯整数规划问题和混合整数规划问题的方法——分枝定界法
•  纯整数规划的求解方法——割平面法
•  0 - 1 型整数规划求解方法——隐枚举法
•  极小化指派问题的求解方法——匈牙利法
5 .几个重要结论
1 )分枝定界法既可以用来求解纯整数规划问题,也可以用来求解混合整数规划问题
2 )割平面法只能用来求解纯整数规划问题
3 )用割平面法求解纯整数规划时,构造的割平面不会切割掉不属于最优解的整数解
第六章图与网络分析
知识重点