第四章 非线性规划
教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。
教学难点：约束最优化问题的最优性条件。 教学课时：24学时
主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。
第一节 基本概念
教学重点：非线性规划问题的引入，非线性方法概述。 教学难点：无。 教学课时：2学时
主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。
1、非线性规划问题举例 例1 曲线最优拟合问题 已知某物体的温度?
与时间t 之间有如下形式的经验函数关系：
3
12c t c c t e φ=++ （*）
其中1c ，2c ，3c 是待定参数。现通过测试获得n 组?与t 之间的实验数据),(i i t ?，
i=1，2，…,n 。试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点
),(i i t ?拟合。
∑=++-n
1i 221)]([ min 3i t c i i e t c c ?
例 2 构件容积问题
通过分析我们可以得到如下的规划模型：
???
????≥≥=++++=0
,0 2 ..)3/1( max 212
121222211221x x S x x x x a x x t s x x a V ππππ 基本概念
设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i :,...,1),(;,...,1),();(==, 如下的数学模型称为数学规划(Mathematical Programming, MP)：
??
?
??===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..)
( min 约束集或可行域
X x ∈? MP 的可行解或可行点
MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划
令 T p x g x g x g ))(),...,(()(1=
T p x h x h x h ))(),...,(()(1=，
其中，q n p n
R R h R R
g :,:，那么(MP )可简记为
??
?
??≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X
x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。
否则，称为约束非线性规划或者约束最优化问题。 定义4.1.1 对于非线性规划(MP )，若X x ∈*，并且有
X ),()(*∈?≤x x f x f
设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S ， 圆锥部分的高h 和圆柱部分的高x 2之 比为a 。确定构件尺寸，使其容积最 大。
则称*x 是(MP )的整体最优解或整体极小点，称)(*x f 是 (MP )的整体最优值或整体极小值。如果有
** ),()(x x X,x x f x f ≠∈?<
则称*x 是(MP )的严格整体最优解或严格整体极小点，称
)(*x f 是(MP )的严格整体最优值或严格整体极小值。
定义 4.1.2 对于非线性规划(MP )，若X x ∈*，并且存在*x 的一个 领域}
{),0( )(**R x x R x x N n ∈><-∈=δδδδ，使
X x N x x f x f )( ),()(**δ∈?≤，
则称*x 是(MP )的局部最优解或局部极小点，称)(*x f 是(MP )的局部 最优值或局部极小点。如果有
*** ,)( ),()(x x X x N x x f x f ≠∈?<δ，
则称*x 是(MP )的严格局部最优解或严格局部极小点，称)(*x f 是(MP ) 的严格局部最优值或严格局部极小点。
定义 4.1.3 设0,,,:≠∈∈p R p R x R R f n n n ，若存在0>δ ，使
),0( ),()(δ∈?<+t x f tp x f
则称向量p 是函数f(x)在点x 处的下降方向。
定义 4.1.4 设0,,,≠∈∈?p R p X x R X n n ，若存在0>t ，使
X tp x ∈+
则称向量p 是函数f(x)在点x 处关于X 的可行方向。 一般解非线性规划问题的迭代方法的步骤：
第一步：选取初始点0,:0x k =； 第二步：构造搜索方向k p ； 第三步：根据k p ，确定步长k t ；
第四步：令1k k k k x x t p +=+若1k x +已满足某种终止条件，停止迭代，输出近似最优解1k x +，否则令:1k k =+，转回第二步。
常用规则：
1、相邻两次迭代点的绝对差小于给定误差，即1k k x x ε+-<；
2、相邻两次迭代点的相对差小于给定误差，即1k k
k
x x x ε+-<；
3、()k f x ε?<；
4、1()()k k f x f x ε+-<
第二节 凸函数和凸规划
教学重点：凸函数的概念及性质，凸规划的概念、性质及判定。 教学难点：凸规划的概念及性质。 教学课时：4学时
主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。
凸函数的定义及性质：
定义 4.2.1 设n R S ?是非空凸集，R S f :，如果对任意的)1,0(∈α有
)()1()())1((2121x f x f x x f αααα-+≤-+，S x x ∈?21,
则称f 是S 上的凸函数，或f 在S 上是凸的。如果对于任意的)1,0(∈α有
)()1()())1((2121x f x f x x f αααα-+<-+，21x x ≠
则称f 是S 上的严格凸函数，或f 在S 上是严格凸的。
若-f 是S 上的（严格）凸函数，则称f 是S 上的（严格）凹函数， 或f 在S 上是（严格）凹的。
凸函数的性质：
定理 4.2.1 设n R S ?是非空凸集。
（1）若R R f n :是S 上的凸函数，0≥α，则 f α是S 上的凸函数； （2）若R R f f n :,21都是S 上的凸函数，则21f f +是S 上的凸函数。 定理 4.2.2 设n R S ?是非空凸集，R R f n :是凸函数，R c ∈，则集合
}{c x f S x c f H S ≤∈=)(),(
是凸集。
注：一般来说上述定理的逆是不成立的。
(a) 凸函数 (b)凹函数
定理 4.2.3 设n R S ?是非空开凸集，R S f :可微，则 （1） f 是S 上的凸函数的充要条件是
)()()()(12121x f x f x x x f T -≤-?， S x x ∈?21,
其中T n
x
x f x x f x f ))(,....,)(()(1111
????=?是函数f 在点1
x 处的一阶 导数或梯度。
（2） f 是S 上的严格凸函数的充要条件是
)()()()(12121x f x f x x x f T -<-?， 2121,, x x S x x ≠∈?
证明
（1）. 必要性.设f 是S 上的凸函数，对(0,1)α?∈有：
212112((1))()(1)(),,f x x f x f x x x S αααα+-≤+- ?∈
故
121121(())()
()()f x x x f x f x f x αα
+--≤-
（4.2.3）
由多元函数Taylor 展开式可知：
121112121(())()()()(())T f x x x f x f x x x x x ααοα+--=?-+-
将其带入（4.2.3）并令αο+→便便可得到
12121()()()()T f x x x f x f x ?-≤-
充分性.设
1212112()()()(),T f x x x f x f x x x S ?-≤- ?∈
对(0,1),α?∈取12(1)x x x αα=+-，由S 凸知x S ∈，对12,,x x S x x S ∈∈和分别有： 111()()()(),T f x f x x x f x x S +?-≤ ?∈
（4.2.4）
和
222()()()(),T f x f x x x f x x S +?-≤ ?∈ （4.2.5）
将（4.2.4）乘以α，（4.2.5）乘以(1)α-，两式相加得到
12121212((1))()()()((1))()(1)(),,T f x x f x f x f x x x x f x f x x x S
αααααα+-==+?+--≤+- ?∈
（2）. 证明和（1）类似.
定理 4.2.4 设n R S ?是非空开凸集，R S f :二阶连续可导，则f 是S 上的凸函数的充要条件是f 的Hesse 矩阵)(2x f ?在S 上是半正定的。
当)(2x f ?在S 上是正定矩阵时，f 是S 上的严格凸函数。（注意：该逆命题不成立。）
??
?
??
??
?
??
?
?
????????????????????????????????????=?2
2221
2
222
221
22
122122
122
)()()(....)(...)()()(....)()
()(n n n n n x x f x x x f x x x f x x x f x x f x
x x f x x x f x x x f x x f x f 凸规划及其性质
??
?
??===≤q
j x h p i x g t s x f j i ,...10,)( (MP) ,...,1,0)( ..)
( min ??
????????===≤∈=q j x h p i x g R x X j i n
,...,1,0)(,...,1,0)( 约束集
如果(MP)的约束集X 是凸集，目标函数f 是X 上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。 凸规划的性质
定理 4.2.5 对于非线性规划(MP)，若p i x g i ,...,1),(= 皆为n R 上的凸函数，q j x h j ,...,1),(=皆为线性函数， 并且f 是X 上的凸函数，则(MP)是凸规划。
定理 4.2.6 凸规划的任一局部最优解都是它的整体最优解。
证明：设*x 是凸规划（MP ）的一个局部解，存在则*x 的临域*()N x δ使得
**()(),()f x f x x X
N x δ≤ ?∈
若*x 不是（MP ）的整数最优解，则存在x X ∈，使
*()()f x f x <
又因为f 是凸函数，有
*****((1))()(1)()()(1)()()f x x f x f x f x f x f x αααααα+-≤+-<+-=
显然，当α充分小时，有
**(1)()x x X
N x δαα+-∈
出现矛盾。
例 4.2.3 验证下列（MP ）是凸规划 解答：将二次目标函数改写为：
1112312322334111(,,)(,,)120(1,2,0)2104x x f x x x x x x x x x x -??????
??? ?
=-+ ??? ? ??? ?
??????
由例4.2.2知f 的 Hesse 矩阵为：
2411120104f -?? ?
?=- ? ???
2f ?的一、二、三阶顺序主子式分别为：
411
41
40,70,1202612
104
--> => -=-
2f ?正定，f 为凸函数。
而21200()020000g x ?? ?
?= ? ???
半正定，1g ()x 是凸函数。其他约束条件均为线性。故改
（MP ）为凸规划。
第三节 一维搜索
教学重点：0.618法，牛顿法，非精确一维搜索方法。 教学难点：0.618法和牛顿法。 教学课时：4学时
主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。
目标函数为单变量的非线性规划问题称为一维搜索问题(或线性搜索问题)，其数学模型为
(t) min )
0(0 max ?t t t ≤≤≥，
其中R t ∈。 1、0.618法
函数)(t ?称为在[a,b]上是单谷的，如果存在一个],[*b a t ∈，使得)(t ?在],[*t a 上严格递减，且在],[*b t 上严格递增。区间[a,b]称为)(t ?的单谷区间。 第一步： 插入[][]1221,,,t t a t t b 使等长度，令
21
12(1)(),()t a b t w t a w b a t a w b a b a b a
--=
=?=+-- =+--- 第二步： 使区间缩小同样的比例w ，不妨设新区间为[]2,a t 设插入12,t t ''，则
212212222()()
()
t a w b a w b a t a t t w t a t a t a w b a ?'''=+-----?==??
--'=+-?? 若令11t t '=，则有1w =；若令21t t '=，则有0.618w = 以后类似迭代
算法的具体步骤：
第1步 确定单谷区间[a,b]，给定最后区间精度0>ε; 第2步 计算最初两个探索点
)(618.0)(382.01a b b a b a t --=-+= )(618.02a b a t -+=
并计算)(11t ??=，)(22t ??=；
第3步 若21??≤，转第4步。否则转第5步；
第4步 若ε≤-a t 2，停止迭代，输出1t 。否则令2:t b =，
12:t t =，)(618.0:1a b b t --=，12:??=，计算)(11t ??=，转第3步；
第5步 若ε≤-1t b ，停止迭代，输出2t 。否则令1:t a =，
21:t t =，)(618.0:2a b a t -+=，21:??=，计算)(22t ??=，转第3步。
? 例4.3.1 用0.618法求解的单谷区间为[0,3]，
所要求的区间精度，需要的迭代次数是可以预估的。另外若每次每次迭代按不同比例缩小搜索区间，但仍要求每次迭代只计算一个函数值，且希望在搜索点个数相同的情况下使最终的搜索区间的长度最小，按此要求设计的方法是Fibonacci 法
2、牛顿法
考虑一维搜索问题)( min t ?，其中)(t ?是二次可微的，且0)(≠''t ?。 Newton 法的基本思想是：用)(t ?在探索点k t 处的二阶泰勒展开式()g t 来替代
)(t ?，然后用()g t 的最小点作为新的探索点1k t +.据此，可得：
11()
()
k k k k t t t t ??++'=-
''
开始时给定一个初始点1t ，然后按照上式进行迭代计算，当()k t ?ε'<时，终止迭代，k t 为()t ?的最小点的近似。 Newton 法步骤
第1步 给定初始点1t ，0,:1k ε>=；
第2步 如果()k t ?ε'<，停止迭代，输出k t .否则，当()0k t ?''=时，停止，
解题失败；当()0k t ?''≠时，转下一步；
第3步 计算1()
()
k k k k t t t t ??+'=-''，如果1k k t t ε+-<，停止迭代，输出1k t +，
否则1k k :=+，转至第2步；
例 用牛顿法求下题。
解：首先求出
2
1
()arctan ()1t t t t
??'''= =
+， 取11t =，计算结果列于下表
用数学分析方法知，()t
?的精确最优解是*0t =，用Newton 法迭代三此后就已经十分接近该最优解。 但是取12t =，则有：
点列{}k t 不收敛于*0t =
从任意初始点开始的Newton 法产生的点列，一般来说不一定收敛，即使收敛，其极限点也不一定是 的极小点，只能保证它是
的驻点。但当初始点充分接近 时，可以证明Newton 法是收敛的。 非精确一维搜索： 3、Goldstein 法思想
预先指定两个数12,m m 满足1201m m <<<，用一下两个式子限定k t
1()(0)(0)k k t m t ???'≤+ （4.3.10）
2()(0)(0)k k t m t ???'≥+ （4.3.11）
（4.3.10）式所限定的k t 是使()k t ?位于直线1(0)(0)y m t ??'=+之下的点，
用以控制k t 不太大；（4.3.11）用于限定k t 使()k t ?位于直线2(0)(0)y m t ??'=+ 之上的点，用以控制k t 不太小.
第1步 给定满足1021<<
若)0()0()(1???'+≤k k t m t ，进行第3步；否则，令k k k k t b a a ==++:,:11 转第4步；
第3步 若)0()0()(2???'+≥k k t m t ，停止迭代，输出k t 。否则，令
k k k k b b t a ==++:,:11
若+∞<+1k b ，进行第4步；否则，令1:,:1+==+k k t t k k α，转第2步； 第4步 取2
:1
11++++=k k k b a t ，令1:+=k k ，转第2步。
例 用 法 求解下题
解答：取00:0,:,a b ==+∞并且(0)1,(0)2,??'==-因为0()5t ?=，
010()5(0)(0)0.2t m t ???'=>+=
令
1010:0:2a a b t == ==
由于12b =<+∞，选取新探索点
11
112
a B t +=
= 并计算1()0t ?=，因为有
111()0(0)(0)0.6t m t ???'=≤+=
和
121()0(0)(0)0.4t m t ???'=≥+=-
停止迭代，得到非精确解11t =
4.Armijo 法
取定01m M <<<，用以下两个式子限定k t 不太大也不太小： ()(0)(0)k k t mt ???'≤+
(0.0.1)
()(0)(0)k k Mt mMt ???'>+
(0.0.2)
第四节 无约束最优化问题
教学重点：无约束最优化问题的最优性条件，最速下降法。 教学难点：最速下降法。 教学课时：6学时
主要教学环节的组织：首先给出无约束最优化条件，然后介绍无约束最优化问题的两种算法，最速下降法、共轭方向法。 1 无约束问题的最优性条件
定理4.4.1 设R R f n :在点n R x ∈处可微。若存在n R p ∈，使
0)(
则向量p 是f 在点x 处的下降方向。 证：因为f 在点x 处可微，有泰勒展开，
()()()()T f x tp f x t f x p tp ο+=+?+ （4.4.1） 由于()0,0T f x p t ?<>，因而()0T t f x p ?<，则存在0δ>，对
(0,)t δ?∈有
()()0T t f x p tp ο?+<
由（4.4.1）
()(),(0,)f x tp f x t δ+< ?∈
由定义知p 是f 在点x 的处下降方向
定理 4.4.2 设R R f n :在点n R x ∈处可微。若*x 是(UMP)的局部最优解，则
0)(*=?x f
定理4.4.3 设R R f n :在点n R x ∈处的Hesse 矩阵)(*2x f ?存在。若
0)(*=?x f ，并且)(*2x f ?正定
则*x 是(UMP)的局部最优解。
定理4.4.4 设R R f n :，n R x ∈*，f 是n R 上得可微 凸函数。若有0)(*=?x f 则*x 是(UMP)的整体最优解。
证：因为f 是n R 上的可微凸函数，由定理4.2.3知
***()()()(),T n f x x x f x f x x R ?-≤- ?∈
由于*()0f x ?=，因而推知
*()(,)n f x f x x R ≤ ?∈
由此*x 是（UMP ）问题的整数最优解 2 最速下降法
设（NMP ）问题中的目标函数R R f n :一阶连续可微
最速下降法基本思想：从当前点k x 出发，取函数()f x 在点k x 处下降最快的方向作为我们的搜索方向k p ，由()f x 的Taylor 展开式知
()()()()k k k k T k k f x f x tp t f x p tp ο-+=-?+
忽略t 的高阶无穷小项，可见取()k k p f x =-?时，函数值下降的最多。 最速下降法的计算步骤：
第1步 选取初始点0x ，给定终止误差0>ε，令0:=k ；
第2步 计算)(k x f ?，若ε≤?)(k x f ，停止迭代，输出k x 。否则进行第3步； 第3步 取)(k k x f p -?=
第4步 进行一维搜索，求k t ，使得)(min )(0
k k t k k k tp x f p t x f +=+≥
令k k k k p t x x +=+1，1:+=k k ，转第2步。 例4.4.2 用最速下降法求解如下（UMP ）问题
22
1212min (,)25f x x x x =+
取初始点0(2,2),T x =终止误差610ε-= 显然，该问题的整体最优解为*(0,0)T x = 下面用最速下降法求解. 由1212
()(
,)(2,50)T
T f f f x x x x x ???==?? 构造负梯度方向
00()(4,100)T p f x =-?=-
则0022()(24)25(2100)f x tp t t +=-+-
令
00()
0df x tp dt
+=，解得：00.020037t ≈， 所以100024 1.9198780.020********.003070x x t p -??????
=+=+= ? ? ?--??????
重复上述过程，经十轮迭代可得满足误差610ε-=要求的解。
最速下降法算法分析：
1）随着迭代次数的增加，收敛速度越来越慢； 2）最速下降法的相邻两个搜索方向是彼此正交的； 3）具有全局收敛性。 3 共轭方向法
定义 4.4.1 设A 为n 阶实对称，对于非零向量n R q p ∈,，若有
0=Aq p T
则称p 和q 是相互A 共轭的。对于非零向量组1,...,1,0,-=∈n i R p n i ，若有
j i n j i Ap p j T i ≠-== 1,...,1,0, ,0)(
则称n p p p ,...,,10是A 共轭方向组，也称它们为一组A 共轭方向。
定理4.4.5 设A 是n 阶实对称正定矩阵，)1,...,1,0(-=∈n i R p n i 是非零向量。若110,...,,-n p p p 是一组A 共轭方向，则它们一定是线性无关的。 考虑二次严格凸函数的无约束最优化问题：
c x b Ax x x f T T
++=
2
1)( min （AP ） 其中A 是n 阶实对称正定矩阵，n R b ∈，R c ∈
定理 4.4.6 对于问题(AP)，若110,
.,-n p p p 为任意一组A 共轭方向，则由任意
初始点n R x ∈0出发，依次沿110,...,,-n p p p 进行精确一维搜索，则最多经n 次迭代可达(AP)的整体最优解。
共轭方向法-步骤
第1步 选取初始点0x ，给定终止误差0>ε；
第2步 计算)(0x f ?，若ε≤?)(0x f ，停止迭代，输出0x ；否则，进行第3
步；
第3步 取)(00x f p -?=，令0:=k ；
第4步 进行一维搜索求k t 使得)(m i n )(0
k k t k k k tp x f p t x f +=+≥，令
k k k k p t x x +=+1；
第5步 计算)(1+?k x f ，若ε≤?+)(1k x f ，停止迭代，输出1+k x ；否则，进行第6步；
第6步 若k+1=n ，令n x x =:0，转第3步；否则进行第7步；
第7步 用F-R 公式取k k k k p x f p λ+-?=++)(11，其中2
2
1)
()
(k
k k x f x
f ??=+λ。令
k:=k+1，转第4步。
例 用F-R 法求解如下（UMP ）问题
22
1212min (,)25f x x x x =+
取初始点0(2,2),T x =终止误差610ε-=
解： F-R 方法的第一轮迭代与最速下降法相同，由例4.4.2知
00()(4,100)T p f x =-?=-
1
024 1.9198780.020********.003070x x t p -??????
=+=+= ? ? ?--??????
1()(3.83975,0.15359)f x ?=-
下面利用F-R 公式（4.4.9）构造新的共轭方向，其中：2102
()0.001472()
f x f x λ?=
=?
所以1100 3.84565()0.00615p f x p λ-??
=-?+= ???
令
11()0df x tp dt +=，有10.49923t =，因而得到下一个迭代点211
100x x t p ??=+= ???, 由于2()0f x ε?=<，停止迭代，输出整体最优解2(0,0)T x = 共轭方向法-算法分析：
1）F-R法具有二次终止性。对一般可微函数的无约束优化问题，当函数满足一定的条件时，可以证明F-R方法具有全局收敛性其收敛速度比最速下降法快；2）F-R法强烈依赖于一位搜索的精确性。
第五节 约束最优化方法
教学重点：约束最优化问题的最优性条件，简约梯度法和惩罚函数法。 教学难点：约束最优化问题的最优性条件。 教学课时：8学时
主要教学环节的组织：首先给出约束最优化问题的最优性条件即K_T 条件，然后介绍两种约束最优化方法：简约梯度法和惩罚函数法。 1、约束最优化问题的最优性条件
给定约束最优化问题：
??
???===≤
,...,1 0)( 1 0)( ..)
( min q j x h ,...,p i x g t s x f j i 其中 q j R R h p i R R g R R f R x n j n
i n n ,...,1 :,...,1 ,: : ,==∈ }
{
q j x h p i x g R x X j i n
,...,1,0)(,,...,1,0)((MP)===≤∈=问题的可行区域为
设
J
j x h q J X x j ∈==∈? ,0)(},,2,1{, *
*，即满足令对
积极约束：称使(*)0i g x =的约束()0i g x ≤为点*x 的一个积极约束。 我们记积极约束的下标集为：(*){(*)0,}i I x i g x i I ==∈ K-T 条件：
定理 4.5.1 设R R f n :和)(,:*x I i R R g n i ∈ 在点*x 处可微，
)(\,*x I I i g i ∈在点*x 处连续，J j R R h n j ∈,: 在点*x 处连续可微，并且各
J j x h x I i x g j i ∈?∈? ),( ),( ),(***线性无关。若*x 是(MP)的局部最优解，则存
在两组实数)(,**x I i i ∈λ和J j j ∈,*
μ，使得：
????
?∈≥=?+?+?∑∑∈∈)(
,00)()()(****)(**
**x I i x h x g x f i J j j j x I i i i λμλ “向量组J j x h x I i x g j i ∈?∈? ),( ),( ),(***线性无关”—这个条件称为约束规范条件
其几何意义可以用下图来说明。
若定理4.5.1中进一步要求(),i g x i I ∈在点*x 处均可微，则K-T 条件可简便写为
*
*
*
**1
1
***()()()0
()0,1,,0,1,
,p
q
i
i j j i j i i i f x g x h x g x i p
i p
λμλλ==?+?+?=?= =≥ =∑∑ （4.5.8）
其中**()0,i i g x i I λ?= ∈为互补松紧条件 例4.5.1用K-T 条件求解下列问题
解：问题（4.5.1）的Lagrange 函数为：
2212112213212(,,)(1)(2)(2)()()(1)
L x x x x x x x x x λμλλλμ=-+-++-+- +-+-+-
得到K-T 条件如下
图4.5.1
2014年4月高等教育自学考试 运筹学基础试题 课程代码：02375 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.线性规划单纯形法求解时，若约束条件是小于或等于(≤)不等式，则应当在每个不等式中引入一个 A.基变量 B.非基变量 C.松弛变量 D.剩余变量 2.对于供求不平衡的运输问题，若需求量大于供应量，为了转化为供求平衡的运输问题，我们往往虚设一个 A.供应点 B.需求点 C.仓库 D.运输渠道 3.对计划项目进行核算、评价，然后选定最优计划方案的技术，称为 A.网络计划技术 B.计划评核术 C.关键路线法 D.单纯形法 4.在网络图中，两个活动之间的交接点，称之为 A.线路 B.结点(事项) C.活动 D.流量 5.网络图中，正常条件下完成一项活动可能性最大的时间，称为 A.作业时间 B.最乐观时间 C.最保守时间 D.最可能时间 6.在一个网络中，根据问题的需要，我们可以在图的点旁或边旁标上数，这个数也可称之为 A.树 B.杈 C.枝叉 D.最小枝叉树 7.单纯形法作为一种简单解法，常用于求解线性规划的 A.多变量模型 B.两变量模型 C.最大化模型 D.最小化模型 8.对科学发展趋势的预测属于 A.微观经济预测 B.宏观经济预测 C.科技预测 D.社会预测 9.在固定成本中，由所提供的生产能力所决定的费用，称之为 A.总成本 B.可变成本 C.预付成本 D.计划成本 10.每一个随机变量和相关的某个范围内累计频率序列数相应，这个累计频率数称之为 A.随机数 B.随机数分布 C.离散的随机变量 D.连续的随机变量 11.在接受咨询的专家之间组成一个小组，面对面地进行讨论与磋商，最后对需要预测的课题得出比较一致的意见，这种定性预测方法是 A.指数平滑预测法 B.回归模型预测法 C.专家小组法 D.特尔斐法 12.风险条件下的决策是 A.存在一个以上的自然状态，但决策者具有提供将概率值分配到每个可能状态的信息 B.决策者知道所面对的部分自然状态 C.决策者面对的只有一种自然状态，即关于未来的状态是完全确定的 D.决策者所面对的是，存在一个以上的自然状态，而决策者不了解其它状态，甚至不完全了解如何把概率(可能性)分配给自然状态
习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1） min z ＝p 1（+1d ＋+2d ）＋p 2-3d st. －x 1＋ x 2＋ d －1－ d ＋ 1＝1 －0.5x 1＋ x 2＋ d － 2－d ＋ 2＝2 3x 1＋3x 2＋ d －3－ d ＋3＝50 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1，2，3） （2） min z ＝p 1（2+1d ＋3+2d ）＋p 2-3d ＋p 3+4d st. x 1＋ x 2＋d －1－d ＋ 1 ＝10 x 1 ＋d －2－d ＋2 ＝4 5x 1＋3x 2＋d －3－d ＋3 ＝56 x 1＋ x 2＋d －4－d ＋4 ＝12 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p 1（d ＋1＋d ＋2）＋2p 2d －4＋p 2d －3＋p 3d －1 st. x 1 ＋d －1－d ＋1＝20 x 2＋d －2－d ＋2＝35 －5x 1＋3x 2＋d － 3－d ＋ 3＝220 x 1－x 2＋d －4－d ＋4＝60 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化； （3）若增加一个新的目标约束：－4x 1＋x 2＋d －5－d ＋5＝8，该目标要求尽量达 到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x 3，其系数列向量为（0，1，1，－1）T ，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P 1：满足法律规定要求； P 2：每天的纯收入最大。 试建立该问题的目标规划模型。
运筹学第四章习题答案 4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛- d -+d ｝ （2）max ｛-d ++ d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+ d ｝ （1）合理，令f （x ）+- d -+ d =b,当f （x ）取最小值时，- d -+ d 取最大值合理。 (2)不合理，+ d 取最大值时，f （x ）取最大值，- d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，- d 和+ d 都要尽可能的小。 （4）合理，令f （x ）+- d -+ d =b,当f （x ）取最大值时，- d -+ d 取最小值合理。 4.2用图解法和单纯形法解下列目标规划问题 （1）min ｛P 13 +d ，P 2- 2d ，P 3（- 1d ++ 1d ）｝ 24261121=-+++- d d x x 52221=-+++- d d x x 155331=-++-d d x 3,2,1,0,,,21=≥+-i d d x x i i （2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+4 35.1d d )} 401121=-+++-d d x x 1002221=-++--d d x x 30331=-++-d d x 15442=-++-d d x 4,3,2,1,0,,,21=≥+-i d d x x i i (1)图解法
0 A B C X 1 由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a (2)图解法 2 1 由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可 表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a
(一)线性规划建模与求解 B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1 单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？ 要求：1、建立该问题的线性规划模型。 2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。 解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x 1 、x 2 单位 。 (2)目标函数： max z=2 x 1+x 2 (3)约束条件如下：1221 12 25..3,0+≤??≥??≥?x x s t x x x x 2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线， 结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x 1 +x 2 与 约束条件2 x 1+x 2≤5的边界平行 。甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。 （二）图论问题的建模与求解样题 A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例 13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。
全国2004年4月高等教育自学考试 运筹学基础试题 课程代码：02375 第一部分选择题（共15分） 一、单项选择题（更多科目请访问https://www.doczj.com/doc/4e11854309.html,/zikao.htm）（本大题共15小题， 每小题1分，共15分） 1．下列向量中的概率向量是（ A ） A．（0.1,0.4,0,0.5）B．（0.1,0.4,0.1,0.5） C．（0.6,0.4,0,0.5）D．（0.6,0.1,0.8,-0.5） 2．当企业盈亏平衡时，利润为（ C ） A．正B．负C．零D．不确定 3．记M为产品价格，V'为单件可变成本，则边际贡献等于（ B ） A．M+V'B．M-V'C．M*V'D．M/V' 4．在不确定的条件下进行决策，下列哪个条件是不必须具备的（ A ） A．确定各种自然状态可能出现的概率值B．具有一个明确的决策目标 C．可拟订出两个以上的可行方案 D．可以预测或估计出不同的可行方案在不同的自然状态下的收益值 5．下列说法正确的是（ C ） A．期望利润标准就是现实主义决策标准 B．最小最大决策标准是乐观主义者的决策标准 C．确定条件下的决策只存在一种自然状态 D．现实主义决策标准把每个可行方案在未来可能遇到最好的自然状态的概率定为1 6．下述选项中结果一般不为0的是（ D ）
A．关键结点的结点时差B．关键线路的线路时差 C．始点的最早开始时间D．活动的专用时差 7．时间优化就是在人力、材料、设备、资金等资源基本上有保证的条件下，寻求最短的工程周期。下列方法中不能正确缩短工程周期的是（ D ） A．搞技术革新、缩短活动，特别是关键活动的作业时间 B．尽量采用标准件、通用件等 C．组织平行作业D．改多班制为一班制 8．一般在应用线性规划建立模型时要经过四个步骤： （1）明确问题，确定目标，列出约束因素（2）收集资料，确定模型 （3）模型求解与检验（4）优化后分析 以上四步的正确顺序是（ A ） A．（1）（2）（3）（4）B．（2）（1）（3）（4） C．（1）（2）（4）（3）D．（2）（1）（4）（3） 9．求解需求量小于供应量的运输问题不需要做的是（ D ） A．虚设一个需求点B．令供应点到虚设的需求点的单位运费为0 C．取虚设的需求点的需求量为恰当值D．删去一个供应点 10．以下各项中不属于运输问题的求解程序的是（ B ） A．分析实际问题，绘制运输图B．用单纯形法求得初始运输方案 C．计算空格的改进指数D．根据改进指数判断是否已得最优解11．若某类剧毒物品存货单元占总存货单元数的10%，其年度需用价值占全部存货年度需用价值的15%，则由ABC分析法应称该存货单元为（ A ）存货单元。 A．A类B．B类C．C类D．待定
2015年清华大学826运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）考研复习参考书 科目：826 运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）参考书：《运筹学（数学规划）（第3版）清华大学出版社，2004年1月 W.L.Winston 《运筹学》（应用随机模型）清华大学出版社，2004年2月 V.G. Kulkarni 《概率论与数理统计》（第1～9章）高等教育出版社，2001年盛聚等 考研复习方法，这里不详细展开。简单归纳为： 新祥旭考研提醒：首先，清楚考试明细，掌握真题，真题为本。通过真题，了解和熟知：考什么、怎么考、考了什么、没考什么；通过练习真题，了解：目前我的能力、复习过程中我的进步、我的考试目标。提醒一句：千万不要浪费大量时间做不相关的模拟题；千万不要把考研复习等同于做题目，搞题海战术。 其次，把握参考书，参考书为锚。弄懂、弄熟。考研复习如何才能成功？借用《卖油翁》里的一句话，那就是：手熟而已。明确考试之后，考研就基本上是一个熟悉吃透的过程。无论何时，参考书第一，不能轻视。所以，千万不要本末倒置，把做题凌驾于看书之上。如何才叫熟悉？我认为，要打破“讲速度，不讲效率”的做法，看了多少遍并不是检验熟悉与否的指标，合上书本，随时自我检测，能否心中有数、一问便知，这才是关键。 再次，制定计划，合理分配时间。不是每一本参考书都很重要，都一样重要，所以，在了解真题的基础上，要了解每一本书占多少分，如何命题考试，在此基础上，每一本参考书的主次轻重、复习方略也就清楚了，复习才不会像开摊卖药，平均用力。一个月制定一份计划书，每天写一句话鼓励自己，一个月调整一次复习重点，这都是必要的。 最后，快乐复习。考研复习是以什么样状态进行的，根源在于能否克服不良情绪。第一，报考对外汉语，你是因为喜欢这个专业吗？如果是，那么，就继续给自己这种暗示，那么你一定会发现，复习再紧张，也是愉悦的，因为你是为了兴趣而考研的；第二，规律的作息，不大时间战，消耗战，养精蓄锐。运动加休息，如果能每天都很规律，那么成功也就有了保障，负面情绪少了，效率也就高了。 总结为几个关键词，就是：知己知彼、本末分明。
第四章目标规划 一、学习目的与要求 1、掌握目标规划的图解法模型； 2、掌握目标规划的单纯形的求解模型； 3、掌握目标规划的灵敏度分析。 二、课时6学时 第一节目标规划问题及其数学模型 一、问题的提出 应用线性规划可以处理许多线性系统的最优化问题，但线性规划，整数规划和非线性规划都只有一个目标函数，而在实际问题中，常常需要考虑多个目标：如设计一个新产品的工艺过程，不仅希望获利大，而且希望产量高，消耗低，质量好，投入少等。而这些目标之间通常是矛盾的。所以这类问题多目标问题比单目标问题要复杂得多，我们把这一类问题称为目标规划问题。 目标规划与线性规划相比，有以下优点： 1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题。 实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。 2.线性规划是在满足所有约束条件的可行解中求得最优解。而在实际问题 中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。 3.线性规划问题中的约束条件是不分主次、同等对待的，是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。 4.线性规划的最优解可以说是绝对意义下的最优，为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。 因此可以认为，目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。 二、目标规划的数学模型 例1 某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制定一个获利最大的生产计划，具体数据见表：
参考书 1.《运筹学》（科学版精品课程立体化教材·管理学系列）(第2版)，张伯生等编著，科学出版社，2012年； 2.《数据、模型与决策》(第13版)，戴维·R·安德森/丹尼斯·J·斯威尼编著，于淼译，机械出版社，2012年； 3、《运筹学》（新体系经济管理系列教材），李成标，刘新卫主编，清华大学出版社，2012年； 4．《运筹学——优化模型与算法》，（美）拉丁（Rardin，R.L.) 著，电子工业出版社，2007年 5.《Introduction to Operations Research》（第6 版）（外原版经典教材）， F. S. Hillier and G. J. Lieberman 著，McGraw-Hill 出版社； 6. 《运筹学》，党耀国，李帮义等编著，科学出版社，2009年； 7. 《物流运筹学》，刘蓉主编，电子工业出版社，2012年； 8. 《运筹学导论》（第9版）（美国麦格劳-希尔教育出版公司工商管理最新教材（英文版）），（美）希利尔，（美）利伯曼著，清华大学出版社，2010年； 9. 《运筹学》（第4版）（面向21世纪课程教材（信息管理与信息系统专业教材系列），《运筹学》教材编写组编，清华大学出版社，2012年； 10.《运筹学：应用与解决方法》（第4版）（美国商学院原版教材精选系列），（美）温斯顿著，清华大学出版社，2011年； 11.《管理运筹学》（高等学校经济与工商管理系列教材），茹少峰，申卯兴编著，清华大学出版社，2008年； 12.《运筹学》（第3版），刁在筠等编，高等教育出版社，2007年；
13.《实用运筹学：模型、方法与计算》，韩中庚主编，清华大学出版社，2007年； 14.《运筹学》（现代信息管理与信息系统系列教材），李红艳，范君晖主编，清华大学出版社，2012 年； 15.《管理运筹学：管理科学方法》（21世纪管理科学与工程系列教材），谢家平著，中国人民大学出版社，2010年； 16.《运筹学与实验》，薛毅，耿美英编著，电子工业出版社，2008年； 17.《实用运筹学——上机实验指导及习题解答》，叶向编，中国人民大学出版社，2007年； 18.《应用运筹学》（第二版），曹勇，周晓光，李宗元编著，经济管理出版社，2008年； 19.《运筹学导论》（第8版），（美）希利尔（Hillier,F.S.），（美）利伯曼（Lieberman,G.J.）著，胡运权等译，清华大学出版社，2007年； 20.《经济管理运筹学习题集》，王玉梅，孙在东，张志耀编著，中国标准出版社，2012年； 21.《运筹学习题集》(第4版),胡运权主编，清华大学出版社，2010年； 22.《运筹学解题指导》，周华任主编，清华大学出版社，2006年； 23.《运筹学概率模型应用范例与解法》（第4版），（美）温斯顿（Winston，W.L.）著，李乃文等译，清华大学出版社，2006年； 24.《运筹学学习辅导与习题解析》(第3版)，戎晓霞，宿洁，刘桂真编，高等教育出版社，2009年； 25.《管理运筹学习题集》(普通高等学校管理科学与工程类学科核心课程教材辅
运筹学基础课后习题答案 [2002年版新教材] 第一章导论 P5 1.、区别决策中的定性分析和定量分析，试举例。 定性——经验或单凭个人的判断就可解决时，定性方法 定量——对需要解决的问题没有经验时；或者是如此重要而复杂，以致需要全面分析（如果涉及到大量的金钱或复杂的变量组）时，或者发生的问题可能是重复的和简单的，用计量过程可以节约企业的领导时间时，对这类情况就要使用这种方法。 举例：免了吧。。。 2、. 构成运筹学的科学方法论的六个步骤是哪些？ .观察待决策问题所处的环境； .分析和定义待决策的问题； .拟定模型； .选择输入资料； .提出解并验证它的合理性（注意敏感度试验）； .实施最优解； 3、．运筹学定义： 利用计划方法和有关许多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据 第二章作业预测P25 1、. 为了对商品的价格作出较正确的预测，为什么必须做到定量与定性预测的结合？即使在定量预测法诸如加权移动平均数法、指数平滑预测法中，关于权数以及平滑系数的确定，是否也带有定性的成分？ 答：（1）定量预测常常为决策提供了坚实的基础，使决策者能够做到心中有数。但单靠定量预测有时会导致偏差，因为市场千变万化，影响价格的因素很多，有些因素难以预料。调查研究也会有相对局限性，原始数据不一定充分，所用的模型也往往过于简化，所以还需要定性预测，在缺少数据或社会经济环境发生剧烈变化时，就只能用定性预测了。（2）加权移动平均数法中权数的确定有定性的成分；指数平滑预测中的平滑系数的确定有定性的成分。 2.、某地区积累了5 个年度的大米销售量的实际值（见下表），试用指数平滑法，取平滑系数α= 0.9，预测第6年度的大米销售量（第一个年度的预测值，根据专家估计为4181.9千公斤） 年度 1 2 3 4 5 大米销售量实际值 （千公斤）5202 5079 3937 4453 3979 。 答： F6=a*x5+a(1-a)*x4+a(1-a)~2*x3+a(1-a)~3*x2+a(1-a)~4*F1 F6=0.9*3979+0.9*0.1*4453+0.9*0.01*3937+0.9*0.001*5079+0.9*0.0001*4181.9
《运筹学基础》复习要点 一、基本概念与理论 1．任意多个凸集的交集还是凸集。 2．任意多个凸集的并集不一定是凸集 3．给定1R b ∈及非零向量n R a ∈，称集合}|{b x a R x H T n =∈=是n R 的一个超平面。 4．由超平面}|{b x a R x H T n =∈=的两个半平面 }|{b x a R x H T n ≥∈=+和}|{1b x a R x H T n ≤∈= 都是凸集。 5．设S 是凸集，S x ∈。若对任何z y S z S y ≠∈∈,,，以及任何10<<λ，都有 z y x )1(λλ-+≠，则称x 为S 的顶点。 6．如果一个LP 问题无界，则它的对偶问题必无可行解。 7．设w x ,分别为原始LP 问题、对偶问题的可行解，若b w x c T T =，则原始LP 问题、对偶问题的最优解分别为w x ,。 8.可行解x 是基本可行解的充分必要条件是x 的正分量，所对应的A 中列向量线性无关。 9.写出LP 问题的对偶问题 0..min ≥≥?????x b Ax x c t s T 的对偶问题是： 0..min ≥≤?????w c w A w b t s T T 10．设一个标准形式的LP 问题的基为B ，右端向量为b ，则对应的基本解是??? ? ??=-01b B x 。 11．线性规划问题的可行域是凸集。 12．设线性规划问题LP 为 0..min ≥=?? ? ??x b Ax t s x c T B 为一个基，对应的典式为 0..min 111≥=+?? ? ? ?-=---x b B Nx B x t s x b B c z N B T T B ζ 其中),0(1T N T B T c N B c -=-ζ 。
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
第一章导论 一、运筹学与管理决策 1：运筹学是一门研究如何有效地组织和管理人机系统的科学。2：运筹学应用分析的，经验的和数量的方法。为制定最优的管理决策提供数量上的依据。 3：运筹学也是对管理决策工作进行决策的计量方法。4：企业领导的主要职责是作出决策，首先确定问题，然后制定目标，确认约束条件和估价方案，最后选择最优解。 5：分析程序有两种基本形式：定性的和定量的。定性分析的技巧是企业领导固有的，随着经验的积累而增强。 运筹学位管理人员制定决策提供了定量基础。6：运筹学的定义：运筹学利用计划方法和有关多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据。 二、计算机与运筹学计算机是运筹学的不可分割的部分和不可缺少的工具，并且计算机方法和运筹学是并行发展的。计算机是运筹学发展的基本要素。 运筹学和计算机方法的分界线将会消失。 三、决策方法的分类 分类： 1定性决策：基本上根据决策人员的主观经验或感觉或知识制定的决策。 2定量决策：借助于某些正规的计量方法做出的决策。 3混合性决策：必须运用定性和定量两种方法才能制定的决策。作为运筹学应用者，接受管理部门的要求，去收集和阐明数据，建立和试验数学模型。决策人员采用计量方法的几种情况：1 1要解决的问题是复杂的并且具有许多变量。 2说明能决策的问题的各种状况的数据是可以得到的。 3待决策的各项目标可以确定为各种数量关系。 4对应于上述情况，有关的切实可行的模型是当前可以建立起来的。 四、应用运筹学进行决策过程的几个步骤 1.观察待决策问题所处的环境 2.分析和定义待决策的问题 3.拟定模型 符号或抽象模型 4.选择输入资料：保存的记录，当前实验，推测等方式收集这些资料 5提出解并验证它的合理性：要试图改变输入观察发生什么样的输出，叫做敏感度试验。 6实施最优解收益表是现实公司在整个过程中效能的模型，平衡表是现实公司财务情况的模型。第二章预测 一、预测的概念和程序 （一）预测的概念和作用 1：预测就是对未来的不确定的事件进行估计或判断。2：预测是决策的基础，企业预测的目的是为企业决策提供适当的数据或者材料。 （二）预测的方法和分类： 分类（内容）： 1经济预测：它又分为宏观经济预测和微观经济预测，宏观经济是对整个国民经济范围的经济预测，微观经济预测是指对单个经济实体的各项经济指标及其所涉及到国内外市场经济形势的预测。 2科技预测：分为科学预测和技术预测
《物流运筹学》教案 课程名称：物流运筹学 适用专业：物流管理 规定学时：32学时，2学分 开课学期：三年级上学期 任课教师：王金红 《物流运筹学》教案 一、课程说明 《物流运筹学》运筹学是经管类专业本、专科生的主干课、学位课。通过本书学习要求学生掌握线性规划、整数规划、目标规划、图与网络分析、动态规划、存储论、排队论、决策论、博弈论的基本理论及方法，通过案例分析，要求学生学会建模的方法，能用各类模型的建立解决在经济管理中出现的各类问题。 二、教学内容 《物流运筹学》是物流管理专业的专业方向课程，教材涵盖了线性规划、整数规划、目标规划、图与网络分析、动态规划、存储论、排队论、决策论、博弈论的基本理论及方法，讨论了目标规划、图与网络分析在物流中的主要应用领域，探讨了利用线性规划、整数规划、目标规划、图与网络分析、动态规划、存储论、排队论、决策论、博弈论的基本理论及方法解决物流活动中的问题，并对物流运输路线安排、物资调配等专题进行了剖析。 三、本课程的教案主要包括下列教学活动形式
1、本章的教学目标及基本要求 2、本章各节教学内容 3、教学重点与难点 4、本章教学内容的深化和拓宽 5、本章教学方式（手段）及教学过程中应注意的问题 6、本章的主要参考书目 7、本章的思考题和习题 8、教学进程 四、课程教学的基本要求 本课程的教学环节包括：课堂讲授、习题课、课外作业。通过本课程各个教学环节的教学，重点培养学生的学习能力、分析问题解决问题的能力。 （一）课堂讲授 主要教学方法：主要采用教师课堂讲授为主，增加讨论课和习题课，调动学生学习的主观能动性。 （二）习题 习题是本课程的重要教学环节，通过习题巩固讲授过的基本理论知识，培养学生自学能力和分析问题解决问题的能力。 习题课：安排每章后。
《基础运筹学》课程教学大纲 课程编码：12120602207 课程性质：专业必修课 学分：3 课时：54 开课学期：4 适用专业：物流工程 一、课程简介 本课程着重介绍运筹学的基本原理和方法，是物流工程专业必修课程，运筹学注重结合经济管理专业实际和其它实际问题，具有一定的深度和广度。运筹学主要内容包括线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论。 二、教学目标 《运筹学》是应用数学的重要分支和管理类本科重要的学科基础课之一。运筹学教学目标归纳如下： 通过讲授、作业、上机等教学环节，学习理解与经济管理领域密切相关的运筹学基本模型与方法， 掌握运筹学整体优化的思想和若干定量分析的优化技术，能正确应用各类模型分析、解决不十分复杂的实际问题。 三、教学内容 （一）第一章线性规划 主要内容：绪论、线性规划的数学模型、图解法、线性规划的基本概念和基本定理 教学要求：理解线性规划的基本理论；掌握线性规划的数学模型与基本算法；熟练解决线性规划涉及的实际问题。 重点、难点：数学模型的标准型，图解法，线性规划的基与解，线性规划问题解的几种情况。 教学方法：理论讲授、PPT演示、例题演算 （二）第二章单纯形法 主要内容：单纯形法原理、单纯形法的表格形式、大M法和两阶段法 教学要求：理解单纯形法的基本原理；掌握单纯形法的表格形式、大M法和两阶段法；了解退化问题。 重点、难点：单纯性表中的构造初始可行基，并计算出初始检验数，从表中找出基本可行解和相应目标函数值，量忧性检验和基变换。 教学方法：理论讲授、PPT演示、例题演算 （三）第三章线性规划的对偶原理及运输问题 主要内容：线性规划的对偶问题、对偶问题的基本性质和基本定理、对偶单纯形法、灵敏度分析
习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1）min z ＝p1（＋）＋p2 st. －x1＋ x2＋ d－1－ d＋1＝1 －0.5x1＋ x2＋ d－2－d＋2＝2 3x1＋3x2＋ d－3－ d＋3＝50 x1，x2≥0；d－i，d＋i≥0（i =1，2，3） （2） min z ＝p1（2＋3）＋p2＋p3 st. x1＋ x2＋d－1－d＋1 ＝10 x1 ＋d－2－d＋2 ＝4 5x1＋3x2＋d－3－d＋3 ＝56 x1＋ x2＋d－4－d＋4 ＝12 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p1（d＋1＋d＋2）＋2p2d－4＋p2d－3＋p3d－1 st. x1 ＋d－1－d＋1＝20 x2＋d－2－d＋2＝35 －5x1＋3x2＋d－3－d＋3＝220 x1－x2＋d－4－d＋4＝60 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化；
（3）若增加一个新的目标约束：－4x1＋x2＋d－5－d＋5＝8，该目标要求尽量达到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x3，其系数列向量为（0，1，1，－1）T，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P1：满足法律规定要求； P2：每天的纯收入最大。 试建立该问题的目标规划模型。 4.4 某企业生产两种产品，产品Ⅰ售出后每件可获利10元，产品Ⅱ售出后每件可获利8元。生产每件产品Ⅰ需3小时的装配时间，每件产品Ⅱ需2小时装配时间。可用的装配时间共计为每周120小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低1元。加班时间限定每周不超过40小时，企业希望总获利最大。试凭自己的经验确定优先结构，并建立该问题的目标规划模型。 4.5 某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下： A B每周最大加工能力 I 4 6 150 II 3 2 70 利润（元/台）300 450 工厂经营目标的期望值及优先级如下： P1：每周总利润不得低于10000元；
第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下： 2123max x x z += ????? ? ?≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x 4.2 2197max x x z += ??? ??≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。（下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得： 2 7 221227432=++ x x x ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得： ①②③④ ①②③
即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 由x 1行得： 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和： 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4.3 max z ＝4x 1＋3x 2＋2x 3
运筹学试题及答案 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加__人工变量_的方法来产生初始可行基。 2．线性规划模型有三种参数，其名称分别为价值系数、_技术系数__和__限定系数_。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是__无非负约束(或无约束、或自由)_变量。 4．求最小生成树问题，常用的方法有：避圈法和_破圈法__。 5．排队模型M／M／2中的M，M，2分别表示到达时间为__负指数_分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为__不确定__型决策。 7．在风险型决策问题中，我们一般采用__效用曲线_来反映每个人对待风险的态度。 8．目标规划总是追求目标函数的_ 最小__值，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的__ 优先因子(或权重)__。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【 D 】 A．有唯一的最优解B．有无穷多最优解 C．为无界解D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【 D 】 A．b列元素不小于零B．检验数都大于零 C．检验数都不小于零D．检验数都不大于零 11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【 A 】 A．3 B．2 C．1 D．以上三种情况均有可能 12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 B 】 13．在运输方案中出现退化现象，是指数字格的数目【 C 】 A．等于m+n B．等于m+n-1 C．小于m+n-1 D．大于m+n-1 16．关于线性规划的原问题和对偶问题，下列说法正确的是【 B 】 A．若原问题为无界解，则对偶问题也为无界解
《运筹学》作业参考答案 使用教材：汤代焱等编著，《运筹学》，中南大学出版社，2002.9 一、作业题 第1章线性规划基础：1.3题 第2章单纯形法：2.3题(1 第3章对偶问题及对偶单纯形法：3.7题 第5章运输问题与指派问题：5.6题，5.10题 第8章动态规划：8.1题 第9章图与网络分析：9.5题，9.9题 第10章网络计划技术：10.2题 第11章单目标决策：11.1题 二、《运筹学》作业题参考答案 第1章 P7：1.3题，x 1=8，x 2=5，Z max =380 3 第2章 P25：2.3(1题，x 2=5/2，x 4=14，x 7=42，x 1=x3=x5=x6=0，Z max =180 第3章 P40：2.7题 1 Z max =20y 1+12y 2+10y 3 ?y 1+y 2+2y 3≤6??y 1+y 2+y 3≤3 ? 1y +y +y ≤23?122 ?y ≥0, 一切j ?j
2 y *=(1, 2, 0, 3, 0, 0 ，Z max =44 3 X *=(0, 4, 16 ，S min =44 第5章 P85：5.6题，S min =17500(元 P86：5.10题，S=10(小时 第8章 P145：8.1题，S=68 第9章 P182：9.5题，V 1至各点最短路径如下图所示(画双线路线 v 2 1 v 5 2 v 8 v v 1不能到达v 8 v 11 P184：9.9题。目前流量为5，不是网络最大流，因在图中还存在增流链。 第10章网络计划技术，P206：10.2题
第11章单目标决策，P224：11.1题，现在扩大的方案为最优方案。
1 一、运筹学与管理决策 1：运筹学是一门研究如何有效地组织和管理人机系统的科学。 2：运筹学应用分析的，经验的和数量的方法。为制定最优的管理决策提供数量上的依据。 3：运筹学也是对管理决策工作进行决策的计量方法。 4：企业领导的主要职责是作出决策，首先确定问题，然后制定目标，确认约束条件和估价方案，最后选择最优解。 5：分析程序有两种基本形式：定性的和定量的。 定性分析的技巧是企业领导固有的，随着经验的积累而增强。 运筹学位管理人员制定决策提供了定量基础。 6：运筹学的定义：运筹学利用计划方法和有关多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据。 二、计算机与运筹学 计算机是运筹学的不可分割的部分和不可缺少的工具，并且计算机方法和运筹学是并行发展的。 计算机是运筹学发展的基本要素。 运筹学和计算机方法的分界线将会消失。 三、决策方法的分类 分类： 1定性决策： 基本上根据决策人员的主观经验或感觉或知识制定的决策。 2定量决策： 借助于某些正规的计量方法做出的决策。 3混合性决策： 必须运用定性和定量两种方法才能制定的决策。 作为运筹学应用者，接受管理部门的要求，去收集和阐明数据，建立和试验数学模型。 决策人员采用计量方法的几种情况： 1要解决的问题是复杂的并且具有许多变量。 2说明能决策的问题的各种状况的数据是可以得到的。 3待决策的各项目标可以确定为各种数量关系。 4对应于上述情况，有关的切实可行的模型是当前可以建立起来的。 四、应用运筹学进行决策过程的几个步骤 1.观察待决策问题所处的环境 2.分析和定义待决策的问题 3.拟定模型 符号或抽象模型 4.选择输入资料：保存的记录，当前实验，推测等方式收集这些资料 5提出解并验证它的合理性： 要试图改变输入观察发生什么样的输出，叫做敏感度试验。 6实施最优解 收益表是现实公司在整个过程中效能的模型，平衡表是现实公司财务情况的模型。 第二章 预测 一、预测的概念和程序 （一）预测的概念和作用 1：预测就是对未来的不确定的事件进行估计或判断。 2：预测是决策的基础，企业预测的目的是为企业决策提供适当的数据或者材料。 （二）预测的方法和分类： 分类（内容）： 1经济预测：它又分为宏观经济预测和微观经济预测，宏观经济是对整个国民经济范围的经济预测，微观经济预测是指对单个经济实体的各项经济指标及其所涉及到国内外市场经济形势的预测。 2科技预测：分为科学预测和技术预测
第1章导论 【真题演练】 1、（12年4月）借助于某些正规的计量方法而做出的决策，称为( A ) A．定量决策 B．定性决策 C．混合性决策 D．满意决策 2、（12年4月）利用直观材料，依靠个人经验的主观判断和分析能力，对未来的发展进行预测属于( c ) A．经济预测 B．科技预测 C．定性预测 D．定量预测 3、（11年7月）根据决策人员的主观经验或知识而制定的决策，称之为( B ) A.定量决策 B.定性决策 C.混合性决策 D.满意决策 4、（12年4月）对于管理领域，运筹学也是对管理决策工作进行决策的___计量___方法。 5、（11年7月）运筹学应用多种分析方法，对各种可供选择的方案进行比较评价，为制定最优的管理决策提供___数量___上的依据。 6、（11年4月）作为运筹学应用者，接受管理部门的要求，收集和阐明数据，建立和试验_数学模型_，预言未来作业，然后制定方案，并推荐给经理部门。 7、（10年7月）运筹学把复杂的功能关系表示成_数学模型_，以便通过定量分析为决策提供数量依据。 8、（10年4月）在当今信息时代，运筹学和信息技术方法的分界线将会____消失____，并将脱离各自原来的领域，组合成更通用更广泛的管理科学的形式。 9、（09年7月）决策方法一般分为定性决策、定量决策、___混合型决策___三类。 10、（09年4月）运筹学是一门研究如何有效地组织和管理____人机系统____的科学。 11、（09年4月）名词解释：定性预测 12、（11年7月）名词解释：定量预测 【同步练习】 1、运筹学研究和运用的模型，不只限于数学模型，还有用___符号___表示的模型和___抽象___的模型。 2、在某公司的预算模型中，__收益表__是显示公司效能的模型，___平衡表__是显示公司财务情况的模型。 3、运筹学工作者观察待决策问题所处的环境应包括___内部___环境和___外部___环境。 4、企业领导的主要职责是___作出决策___，首先确定问题，然后__制定目标___，确认约束