《2011年管理运筹学总复习教程》由会员分享，可在线阅读，更多相关《2011年管理运筹学总复习教程（103页珍藏版）》请在金锄头文库上搜索。
1、学期总评=平时成绩30%+期末成绩70%,一、模型建立 二、线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析 三、运输问题 四、整数规划 五、动态规划 六、图与网络 七、矩阵对策,复习提纲,第一部分 模型建立,掌握工商管理领域实际线性规划问题的数学模型的建立方法和步骤，特别是整数规划模型（重点是0，1变量）的建立 （数学模型的三要素）,1、能将一般线性规划模型化为标准形式； 2、理解线性规划基本概念：可行解、可行域、最优解、退化解、基解、基可行解、基矩阵、可行基、最优基、基变量、非基变量、基向量、非基向量等； 3、掌握初始基可行解的确定方法，单纯形表的最优性检验与解类型（唯一最优解、无
2、穷多最优解、无界解、无可行解）的判别方法，基变换与迭代方法；,第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析,4、掌握线性规划问题的求解方法：单纯形表与计算步骤；处理人工变量的大M法和两阶段法；采用对偶单纯性法的目的和前提条件以及对偶单纯形法的步骤；处理退化与防止死循环的方法。,第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析,5、了解单纯形法的矩阵描述； 理解对偶问题和原问题的内在关系，特别是从单纯形表格上找出二者解的情况； 6、能直接写出线性规划模型（对称性和非对称形）的对偶模型 7、从单纯形表格上充分理解对偶性质（弱对偶性、强对偶性、互补松弛性）,第
3、二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析,8、结合实际问题熟练掌握单纯性表的灵敏度分析及其经济解释： 价值系数的灵敏度分析 资源拥有量的灵敏度分析 技术系数的灵敏度分析 增加和减少产品的灵敏度分析 增加和减少约束条件的灵敏度分析 影子价格、机会成本、市场价格、吸引力,第二部分 线性规划问题、对偶问题、对偶理论、单纯形法及其灵敏度分析,1、理解什么是运输问题，能够建立实际运输问题的数学模型； 2、掌握产销平衡运输问题的表上作业法； 3、能够将产销不平衡的运输问题转换为产销平衡的运输问题进行求解。,第三部分 运输问题,1、了解什么是整数规划问题； 2、理解分枝定界法，掌握分
4、枝、定界、剪枝； 3、理解0-1型整数规划问题，会建立0-1模型 4、会用匈牙利法求解指派问题（标准和非标准）,第四部分 整数规划,1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分配问题。,第五部分 动态规划,第五部分 动态规划 1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分配问题。 第六部分 图与网络分析 1、了解图与网络的基本概念； 2、理解树、最小生成树的概念； 3、能求解最短路问题、最小树问题、最大流问题、最小费用
5、最大流问题。 第七部分 对策论 1、掌握对策问题的三要素(会建立对策模型) 2、能判断矩阵对策是否存在纯策略意义下的平衡解(鞍点),并求解； 3、能将矩阵对策表示为一对互为对偶的对称型线性规划问题。,第五部分 动态规划 1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分配问题。 第六部分 图与网络分析 1、了解图与网络的基本概念； 2、理解树、最小生成树的概念； 3、能求解最短路问题、最小树问题、最大流问题、最小费用最大流问题。 第七部分 对策论 1、掌握对策问题的三要素(会建立对策模型) 2、能判断矩阵对策是
6、否存在纯策略意义下的平衡解(鞍点),并求解； 3、能将矩阵对策表示为一对互为对偶的对称型线性规划问题。,第五部分 动态规划 1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分配问题。 第六部分 图与网络分析 1、了解图与网络的基本概念； 2、理解树、最小生成树的概念； 3、能求解最短路问题、最小树问题、最大流问题、最小费用最大流问题。 第七部分 对策论 1、掌握对策问题的三要素(会建立对策模型) 2、能判断矩阵对策是否存在纯策略意义下的平衡解(鞍点),并求解； 3、能将矩阵对策表示为一对互为对偶的对称型线性规划
7、问题。,管理运筹学总复习,典型案例,单纯形法的灵敏度分析与对偶,一、灵敏度分析典型例题,佳美公司计划制造、两种产品，已知各制造一个单位产品时，分别占用的设备A、B的台时、调试时间、每天设备A、B的台时、调试工序可用于这两种产品的能力及各售出一单位时的获利情况，如表所示。,1、问应怎样组织生产才能使总利润最多？ 2、如果产品的利润降至1.5百元/单位，而产品的利润增至2百元/单元时，最优生产计划有何变化？ 3、如果产品的利润不变，则产品的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？ 4、若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化； 5
8、、若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变. 6、设该公司又计划推出新产品，生产一单位产品，所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3百元/单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化 。,7、若产品每单位需设备A、B和调试工时8小时、4小时、1小时，该产品的利润变为3百元/单位，试重新确定该公司最优生产计划. 8、 假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力为12小时，试分析增加该工序后的佳美公司最优生产计划.
9、9、假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力至少为15小时，试分析增加该工序后的佳美公司最优生产计划.,，,解：设分别表示、两种产品的生产数量，可建立如下线性规划模型：,maxZ=2x1+x2 5x215 s.t. 6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2+0x3 +0x4 +0x5 5x2+x3 =15 s.t. 6x1+2x2 +x4 =24 x1+x2 +x5 = 5 x1,x2 ,x3 ,x4,x5 0,y,Y1 Y2 y3, j ,x3 x1 x2,0 2 1,15/2
10、 0 0 1 5/4 -15/2,7/2 1 0 0 1/4 -1/2,3/2 0 1 0 -1/4 3/2,0 0 0 -1/4 -1/2,可见原问题具有唯一最优解：,思考：对偶问题的最优解和最优值？,x1 x2 x3 x4 x5,CB XB b,CB , j ,2 1 0 0 0,x3 x4 x5,0 0 0,15 0 5 1 0 0,24 6 2 0 1 0,5 1 1 0 0 1,0 0 0 -1/4 -1/2,初表,终表,将产品、的利润变化直接反映到最终单纯形表中得表，,因非基变量的检验数大于零，故需继续用单纯形法迭代计算,2、如果产品的利润降至1.5百元/单位，而产品的利润增至2百
11、元/单元时，最优生产计划有何变化？,x1 x2 x3 x4 x5,CB XB b,CB , j ,0 0 0,x3 x1 x2,0 2 1,15/2 0 0 1 5/4 -15/2,7/2 1 0 0 1/4 -1/2,3/2 0 1 0 -1/4 3/2,0 0 0 -1/4 -1/2,2 1,1.5 2,0 1.5 2,0 0 0 1/8 -9/4,CB XB b,CB , j ,0 0 0,x3 x1 x2,15/2 0 0 1 5/4 -15/2,7/2 1 0 0 1/4 -1/2,3/2 0 1 0 -1/4 3/2,1.5 2,0 1.5 2,0 0 0 1/8 -9/4,x1
12、x2 x3 x4 x5,6 14 -, j ,x4 x1 x2,6 0 0 4/5 1 -6,2 1 0 -1/5 0 1,3 0 1 1/5 0 0,0 1.5 2,0 0 -1/10 0 -3/2,可见变化后的问题具有唯一最优解,X*=(2,3)T,3、如果产品的利润不变，则产品的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,x1 x2 x3 x4 x5,CB XB b,CB , j ,2 0 0 0,x3 x1 x2,0 2 1,15/2 0 0 1 5/4 -15/2,7/2 1 0 0 1/4 -1/2,3/2 0 1 0 -1/4 3/2,0 0 0 -1/4 -1/
13、2,1,解：设产品的利润为c2元，反映到最终单纯形表中，得表：,c2,c2,0 0 0 -1/2+1/4 c2 1-3/2 c2,为使表中的解仍为最优解，应有： -1/2+1/4 c2 0 1-3/2 c2 0,即产品的利润的变化范围是：2/3，2,解得：2/3 c 22,4、若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化；,解：（1）由题意得变化后的b为b:,所以有,B-1 b=,B-1 =,由最终单纯形表得原最优基的逆矩阵:,b=,=,将其反映到最终单纯形表中,CB XB b,CB , j ,x3 x1 x2,0 2 1,0 0 1 5/4 -15/2,1 0 0 1/4 -1/2,0 1 0 -1/4 3/2,0 0 0 -1/4 -1/2,x1 x2 x3 x4 x5,2 1 0 0 0, j ,15 0 5 1 0 0,5 1 1 0 0 1,2 0 -4 0 1 -6,0 -1 0 0 - 2,x3 x1 x4,0 2 0,35/2 11/2 -1/2,可见变化后的问题具有唯一最优解: X*=(5,0)T Z*=10,第二
