课程学习指导资料。
第一部分课程的学习目的及总体要求。
一、 课程的学习目的。
教学目的是使学生掌握运筹学的主要模型;初步掌握如何将实际问题形成运筹学的模型的方法和技巧,并能解决一些简单的实际问题。
二、 课程的总体要求。
较深入的了解线性规划、运输问题、动态规划、图与网络分析等运筹学分枝学科的概念、原理和方法,培养学生的自学能力、创造性思维能力及综合运用运筹学知识分析和解决实际问题的能力。
第二部分课程学习的基本要求及重点难点内容分析。
第一章绪论。
1. 本章学习要求:
了解运筹学简史、主要内容及主要特点。
第二章线性规划(一)
1. 本章学习要求:
1) 应熟悉的内容:理解线性规划的意义,理解学习规划的一般形式,理解线性规划问题中的基本概念:可行解,基可行解,最优解,基,可行基,凸集,凸组合,顶点等。
2) 应掌握的内容:掌握线性规划问题的标准形式;掌握解线性规划问题的**法;掌握解线性规划问题的单纯形法及其最优性检验与解的判别方法;能用线性规划方法求解实际问题。
3) 应熟练掌握的内容:熟练掌握如何将线性规划一般问题化为标准形式;熟练准确的用单纯形法列表求解线性规划问题及其最优性检验与解的判别方法。
2. 本章重点难点分析:如何将线性规划一般问题化为标准形式;线性规划问题的单纯形法及其最优性检验与解的判别方法。
3. 本章典型例题(案例)分析。
1) 将下列线性规划问题化为标准形式,并列出初始单纯形表。
解:问题化为:
令则。令,且,其他化为标准形。
再引入人工变量,问题变为。
初始单纯形表。
2) 一极大化线性规划问题的单纯形表见下表,若各变量均为非人工变量,当各在什么范围取值时。
a. 表中的解为唯一最优解;
b. 有多重最优解。
c. 目标函数无上界。
解:a. ≥0, ≤0
b. ≥0, =0
c. ≥0, ,0, >0
3)见书p40例1-8
4. 本章作业。
1- 1(3),1-2(3)并化为标准型,1-5(2),1-7
第三章线性规划(二)
1. 本章学习要求:
1) 应熟悉的内容:熟悉线性规划的对偶理论,理解对偶单纯形法的原理,正确使用此方法,理解对偶问题的经济解释——影子**。了解运输问题模型特点;理解表上作业法与单纯形法的联系。
2) 应掌握的内容:掌握原问题与对偶问题的对应关系,掌握对偶问题的基本性质,掌握对偶单纯形方法,掌握运输问题模型结构;掌握表上作业法的基本原理;掌握产销不平衡运输问题的概念、模型结构;掌握表上作业法求解产销不平衡时的处理方法。
3) 应熟练掌握的内容:熟练的准确的写出一般形式的线性规划的对偶问题;熟练掌握对偶问题的基本性质,并且会应用这些性质;熟练掌握对偶单纯形方法;熟练准确地就c、b、a中的元素发生变化来进行灵敏度分析,求出新的最优;熟练运用表上作业法求解。
2.本章重点难点分析:对偶问题的基本性质,并且会应用这些性质;对偶单纯形方法;运用表上作业法求解。
3.本章典型例题(案例)分析。
a. 原问题化为对偶问题。
原问题对偶问题。
4) 见书p62,例2-4;例2-5。
b. 判断下表中方案是否可作为运输问题的初始方案,为什么?
解:不能作为初始方案,存在全部以数字格为顶点的闭回路。
c. 已知运输问题的产销平衡表与单位运价表如下表所示,用表上作业法求其最优解。
解:用最小元素法确定初始方案;用闭回路法求检验数。
初始方案表。
检验数表。改进方案及检验数表。
注:括号内的数字为检验数。
上表中仍存在负检验数,继续调整方案并计算检验数。
注:括号内的数字为检验数。
上表中所有检验数均非负,所以为最优调运方案表。最小的运费为:
4. 本章作业。
p106:2-1(2);2-2;2-4(2);2-7
第四章图与网络分析。
1.本章学习要求:
1) 熟悉的内容:了解如何用图论的观点去分析解决简单的实际问题;会用避圈法和破圈法求部分树;了解欧拉圈、欧拉图、中国邮路问题的概念,会求解中国邮路问题。
2) 掌握的内容:掌握图的基本概念;掌握树的定义、性质;掌握用矩阵法求图中任意两点间的最短路,对应的,也会求两点间的最长路(如果存在);掌握可行流、可行流的流量、最大流、割、割的容量、最小割、增广链的概念;
3) 熟练掌握的内容:熟练的用标号法求有向图与无向图中从一个点到另一个点的最短路;熟练地用ford-fulkerson标号法求最大流。
2. 本章重点难点分析:用标号法求有向图与无向图中从一个点到另一个点的最短路;用ford-fulkerson标号法求最大流。
3. 本章典型例题(案例)分析。
1) 用dijkstra算法计算下列有向图的最短路。
解:p()=0
t()=2,3…7)
第一步:因为,且,,是t标号,则修改上个点的t标号分别为:
所有t标号中,t()最小,令p()=2
第二步:是刚得到的p标号,考察,且,是t标号。
所有t标号中,t()最小,令p()=3
第三步:是刚得到的p标号,考察。
所有t标号中,t()最小,令p()=4
第四步:是刚得到的p标号,考察。
所有t标号中,t()最小,令p()=7
第五步:是刚得到的p标号,考察。
所有t标号中,t()最小,令p()=8
第6步:是刚得到的p标号,考察。
t()=p()=13
至此:所有的t标号全部变为p标号,计算结束。故至的最短路为13。
2) 见书p143例3-6
4. 本章作业。
p175:3-2(a)和(b);3-4
第五章动态规划。
1. 本章学习要求:
1) 应熟悉的内容:明确什么是多阶段的决策问题;理解动态规划的基本思想和基本方程。理解动态规划的最优性原理和最优性定理。
2) 应掌握的内容:掌握最优化原理的内容;掌握逆序解法与顺序解法。
3) 应熟练掌握的内容:准确、熟练地掌握动态规划的基本概念,包括状态变量、决策变量、状态转移方程、指标函数、基本方程;熟练列出基本方程,并且正确合理地规定其中的状态变量、决策变量、阶段指标函数,过程指标函数、最优指标函数;用逆序法或顺序法熟练计算求解。熟练掌握动态规划在一阶资源分配问题,生产和存贮问题,设备更新问题中的应用。
2.本章重点难点分析: 动态规划的基本概念, 列出基本方程,并且正确合理地规定其中的状态变量、决策变量、阶段指标函数,过程指标函数、最优指标函数;用逆序法或顺序法熟练计算求解。
动态规划在一阶资源分配问题,生产和存贮问题,设备更新问题中的应用。
3.本章典型例题(案例)分析。
1) 书p198(5-1)。
2) 书p206(5-2)
3) 书p216(5-5)
4) 某项工程有三个设计方案。据现有条件,这些方案不能按期完成的概率分别为0.5,0.
7,0.9,即三个方案均完不成的概率为0.5×0.
7×0.9=0.315。
为使这三个方案中至少完成一个的概率尽可能大,决定追加2万元资金。当使用追加投资后,上述方案完不成的概率见下表,问应如何分配追加投资,才能使其中至少一个方案完成的概率为最大。
解:此题目等价于求使各方案均完不成的概率最小的策略。把对第k个方案追加投资看着决策过程的第k个阶段,k=1,2,3。
第k个阶段,可给第k, k+1,…,3个方案追加的投资额。
对第k个方案的投资额。
阶段指标函数,这里的是表中已知的概率值。
过程指标函数。
以上的k=1,2,3
用逆序算法求解。
k=3时, 得表:表1
管理运筹学模拟题
三 计算题 共70分 1 某工厂拥有a,b,c三种类型的设备,生产甲 乙两种产品,每件产品在生产中需要使用的机时数,每件产品可以获得的利润,以及三种设备可利用的机时数见下表 求 1 线性规划模型 5分 4.如图所示的单行线交通网,每个弧旁边的数字表示这条单行线的长度。现在有一个人要从出发,经过这个交...
管理运筹学模拟题
课程学习指导资料。编写 彭盈。第一部分课程的学习目的及总体要求。一 课程的学习目的。教学目的是使学生掌握运筹学的主要模型 初步掌握如何将实际问题形成运筹学的模型的方法和技巧,并能解决一些简单的实际问题。二 课程的总体要求。较深入的了解线性规划 运输问题 动态规划 图与网络分析等运筹学分枝学科的概念 ...
运筹学模拟题答案
一 填空题。1.线性规划问题一般要将根据实际得到的数学模型转换为标准型 对最小目标函数如果令 z z 便可将求最小目标函数问题转换为求最大目标函数问题maxz 2.线性规划问题转换为标准型时,对取值无约束的情形,即对xk 取值 则可令xk 其中,0 3.线性规划问题的数学模型中目标函数和约束函数都是...