当前位置:文档之家› 2019运筹学期末复习试题(考试范围提纲)

2019运筹学期末复习试题(考试范围提纲)

运筹学期末复习范围
第1章 线性规划
1. 线性规划解的分类及判别方法
2. 大M 法求解线性规划目标函数的设法及求解的思想
3. 用单纯形表格求解线性规划 第2章 对偶理论及灵敏度分析 1. 对偶问题的基本性质 2. 已知原问题写出对偶问题
3. 对偶理论:已知对偶问题(原问题)最优解判断原问题(对偶问题)的最优解
4. 灵敏度分析:常数项或者价值系数发生改变时对最优解的影响判别 第3章 运输问题
1. 产销平衡运输问题模型的特点
2. 表上作业法初始基变量的个数的判别
3. 确定初始基可行解的方法:最小元素法(基本思想)和伏格尔法的优缺点比较
最优解的判别方法(检验数的判别) 闭回路法
位势法检验数的求法。

第4章 整数规划
1. 分支定界法如何定界如何分支
2. 0-1整数规划相互排斥的约束条件
3. 最小指派问题 第5章 动态规划
1.动态规划的基本思想(解决哪一类问题)
2.利用动态规划方法求最优解和最优值(顺推法或逆推法) 第6章 图与网络规划
1.图的概念;边和点的关系
2.求最小生成树的方法:破圈法和避圈法的步骤
3.求网络最大流,并找出最小割集。

第7章 无约束极值问题
1.斐波那契法和0.618法两种方法比较的优缺点,以及斐波那契法的区间缩短率。

2.斐波那契法给定两点函数值如何判定保留区间和去掉的区间
3.已知函数,最速下降法求某一点处的搜索方向;共轭梯度法如何确定搜索方向以及迭代终止条件。

第8章 约束极值问题
1.利用K-T 条件求解非线性规划
2.常用的制约函数分类,如何设惩罚函数和障碍函数。

运筹学期末复习试题
1
、内点法求解,构造的障碍函数
()()3
1212
1,131r r P X r x x x x =
+++
+-
2、使用外点法求解非线性规划()()()122
11221min 00
f X x x
g X x x g X x =+⎧⎪=-+≥⎨⎪=≥⎩
,构造的惩罚函数
()()()
(){
}
2
2
212121,min 0,min 0,P X M x x M x x x ⎡⎤=++-++⎡⎤⎣
⎦⎣⎦ 3、试写出下述非线性规划问题的Kuhn-Tucker 条件并进行求解:
()()2min 315f x x x ⎧=-⎪⎨
≤≤⎪⎩
4、如果目标函数或约束条件中含有非线性函数,就称这种问题为非线性规划问题。

( )
5、凸规划问题的局部最小点就是其全局最优点。

( )
6、0.618法以0.618以固定的区间缩短率代替斐波那契法不同的区间缩短率,实施更为容易,但是在相同点数下,比斐波那契法效率低一些。

( )
7、最速下降法求某一点k x 处的搜索方向()k k P f x =-∇ 最佳步长的确定
()
(
)()()()()()()()
()T
k k
k
T
k
k k
f X
f X f X H X f X λ∇∇=
∇∇ 8、共轭梯度法迭代终止条件()
(
)
2
1,1k f X
k n ε+∇≤=-
9、求下图所示的网络最大流(每弧旁的数字是()
,ij ij c f )(P283)
10、用逆推法求解下列问题
2
123
123max 492243100,1,2,3
i z x x x x x x x i =++++≤⎧⎨
≥=⎩
11、求下表所示效率矩阵的指派问题的最小解。

12、求下表所示效率矩阵的指派问题的最小解。

13、写出下列线性规划问题的对偶问题
12341234123412341234max 23435673581299920,0,0,z x x x x x x x x x x x x x x x x x x x x =+++-+--=++-≥--+≤≥≤
14、(P75)已知线性规划问题
12341341234max 25628222120,1,,4j
z x x x x x x x x x x x x j =+++⎧++≤⎪
+++≤⎨⎪≥=⎩L
其对偶问题的最优解为124,1y y **
== ,试应用对偶问题的性质,求原问题的最优解。

15、现有线性规划问题
123
123123123
max 5513320 (1)
1241090 (2),,0z x x x x x x x x x x x x =-++-++≤⎧⎪
++≤⎨⎪≥⎩ 用单纯形法求出最优解,分析在下列各种条件下,最优解分别有什么变化。

(1)约束条件(1)的右端常数由20变成30; (2)约束条件(2)的右端常数由90变成70;
无约束
(3)目标函数中3x 的系数由13变为8; (4)1x 的系数列向量由112-⎛⎫ ⎪⎝⎭ 变为05⎛⎫
⎪⎝⎭。

相关主题