管理运筹学总复习.ppt

复习提纲 一、模型建立 二、线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 三、运输问题 四、整数规划 五、动态规划 六、图与网络 七、矩阵对策 第一部分 模型建立 掌握工商管理领域实际线性规划问题的数学模型的建立方法和步骤，特别是整数规划模型（重点是0，1变量）和决策问题模型的建立 （数学模型的三要素） 第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 1、能将一般线性规划模型化为标准形式； 2、理解线性规划基本概念：可行解、可行域、最优解、退化解、基解、基可行解、基矩阵、可行基、最优基、基变量、非基变量、基向量、非基向量等； 3、掌握初始基可行解的确定方法，单纯形表的最优性检验与解类型（唯一最优解、无穷多最优解、无界解、无可行解）的判别方法，基变换与迭代方法； 第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 4、掌握线性规划问题的求解方法： （1）单纯形表与计算步骤； （2）处理人工变量的大M法； （3）对偶单纯性法（采用该法的前提条件以及对偶单纯形法的步骤）； 第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 5、了解单纯形法的矩阵描述； 理解对偶问题和原问题的内在关系，特别是从单纯形表格上找出二者解的情况； 6、能直接写出线性规划模型（对称形和非对称形）的对偶模型 7、从单纯形表格上充分理解对偶性质（弱对偶性、强对偶性、互补松弛性） 第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 8、结合实际问题熟练掌握单纯性表的灵敏度分析及其经济解释： 价值系数的灵敏度分析 资源拥有量的灵敏度分析 技术系数的灵敏度分析 增加和减少产品的灵敏度分析 增加和减少约束条件的灵敏度分析 影子价格、机会成本、市场价格、吸引力 1、理解什么是运输问题，能够建立实际运输问题的数学模型； 2、掌握产销平衡运输问题的表上作业法； 3、能够将产销不平衡的运输问题转换为产销平衡的运输问题进行求解。 1、了解什么是整数规划问题； 2、理解分枝定界法，掌握分枝、定界、剪枝； 3、理解0-1型整数规划问题，会建立0-1模型 4、会用匈牙利法求解指派问题（标准和非标准） 1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分配问题。 1、了解图与网络的基本概念； 2、理解树、最小生成树的概念； 3、能求解最短路问题、最小树问题、最大流问题、最小费用最大流问题。 1、掌握对策问题的三要素(会建立对策模型) 2、能判断矩阵对策是否存在纯策略意义下的平衡解(鞍点),并求解； 3、能求解矩阵对策的混合策略；将矩阵对策表示为一对互为对偶的对称型线性规划问题。 4、能利用优超原则化简矩阵，进而图解法求解混合策略 管理运筹学总复习 典型案例 补充课外作业 星火公司通常生产3种产品：室外椅子、标准长凳和桌子。这些产品生产过程分2个加工阶段，即：弯管车间和焊接车间。在每个车间里，每种产品所需要的时间、每种单位产品销售中所得到的收益如表所示。公司正在计划安排生产。公司了解到这些产品不管生产多少数量都能在市场上销售出去，但材料供应受到限制。公司手头上现有管材、每种产品需要的管材数也如表所示。 请完成以下问题(决策变量不考虑整数要求)： 市场销售部门提出需要一种新的室外帐篷，帐篷需要1.8小时弯管时间、0.5小时焊接时间和1.3公斤金属管材。这些新产品必须有多大的收益，才能使得这一产品对公司产生吸引力？ 该问题相当于增加一个新产品： 设该产品的生产数量为x7，则P7=(1.8,0.5,1.3) T CBB-1P7 =(7/6,0,4/5) (1.8,0.5,1.3)T=12.5元 这些新产品必须有大于12.5元的收益，才能使得这一产品对公司产生吸引力 每只桌子的收益在什么范围内变化，最优生产组合不变，从而对公司的收益没有影响? 假如管材供应减少到1500公斤，那么最优生产组合是否有变化？这对公司收益将会有什么影响?焊接时间在什么范围内变化，最优基不变？ 平衡运输问题的表上作业法基本步骤： 找一个初始基可行解; 方法: 西北角法/最小元素法 最优解的判别（求非基变量的检验数）; 方法:闭回路法/位势法 确定入基变量与出基变量，找出新的基可行解； 方法:闭回路调整法 重复二、三直到得到最优解 例如：喜庆食品公司有三个生产面包的分厂，有四个销售公司，其各分厂每日的产量、各销售公司每日的销售以及各分厂到各销售公司的单位运价如表所示，问该公司应如何调运产品在满足各销点的需求量的前提下，总运费最少？ 1、利用最小元素法求解初始可行解 依次对单位运价最小的变量分配