概要信息：

　目　　录　
第一章　线性规划与单纯形法 （１）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第二章　对偶问题与灵敏度分析 （２４）
!!!!!!!!!!!!!!!!!!!!!!!!!!
第三章　运输问题 （６２）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第四章　目标规划 （７９）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第五章　整数规划 （９０）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第六章　动态规划 （１０８）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第七章　图与网络优化 （１４０）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第八章　网络计划技术 （１７４）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第九章　存储论 （１９５）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第十章　排队论 （２１１）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第十一章　决策论 （２２７）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第一章　线性规划与单纯形法
一、本章考情分析：
常考题型：选择、填空、简答、判断和计算
分值：必考知识点，分值占３０分以上
重要性：作为前五章的基础铺垫，非常重要！
重要程度：★★★★★
二、本章基本内容：
１）掌握线性规划的数学模型的标准型；
２）掌握线性规划的图解法及几何意义；
３）了解单纯形法原理；
４）熟练掌握单纯形法的求解步骤；
５）能运用大Ｍ法与两阶段法求解线性规划问题；
６）熟练掌握线性规划几种解的性质及判定定理．
三、本章重难点：
重点：
１）单纯形法求解线性规划问题；
２）解的性质；
３）线性规划问题建模．
难点：
１）单纯形法原理的理解；
２）线性规划问题建模．
四、本章要点精讲：
·要点１　化标准型
·要点２　图解法
·要点３　单纯形法的原理
·要点４　单纯形法的计算步骤
·要点５　单纯形法的进一步讨论
要点１　化标准型
线性规划的数学模型
—１—
《运筹学》考点精讲及复习思路
线性规划的共同特征
决策变量１：每个问题都用一组决策变量表示某个方案
决策变量２：决策变量的取值一般都是非负且连续的
约束条件３：与决策变量不矛盾的条件，用线性等式或不等式表示
目标函数４：决策变量与价值系数组成，一般要求实现最大或最小化
【建模思路】
确定决策变量
写出目标函数
找出约束条件
线性规划的标准型可简化为
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　ｉ＝１，２，…，ｍ
ｘｊ≥０　ｊ＝１，２，…，
{
ｎ
经典例题［１－１］　胡运权，运筹学教程（三）Ｐ１５，例３
与南京航空航天大学２００５年，第四题类似，１０分
ｍｉｎＺ＝ｘ１＋２ｘ２＋３ｘ３
ｓ．ｔ．
－２ｘ１＋ｘ２＋ｘ３≤９
－３ｘ１＋ｘ２＋２ｘ３≥４
４ｘ１－２ｘ２－３ｘ３ ＝－６
ｘ１≤０，ｘ２≥０，ｘ３







取值无约束
—２—
【１】目标函数最大
【２】资源限量（右端项）非负
【３】约束条件等式
松弛变量与剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为
价值和利润，所以引进模型后它们在目标函数中的系数均为零。
【４】决策变量非负
整理，得
ｍａｘＺ′＝ｘ１′－２ｘ２－３ｘ３′＋３ｘ３″＋０ｘ４＋０ｘ５
ｓ．ｔ．
２ｘ１′＋ｘ２＋ｘ３′－ｘ３″＋ｘ４ ＝９
３ｘ１′＋ｘ２＋２ｘ３′－２ｘ３″－ｘ５ ＝４
４ｘ１′＋２ｘ２＋３ｘ３′－３ｘ３″＝６
ｘ１′，ｘ２，ｘ３′，ｘ３″，ｘ４，ｘ５≥







０
　　　　　
目标函数最大
约束条件等式
决策变量非负
资源限量非负
经典例题［１－２］　天津大学２００４，二，（１），约５分
—３—
《运筹学》考点精讲及复习思路
某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规
模的广告行动．表１给出了公司准备做广告的三种产品名称、估计每做一单位广告使每种产品的市
场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的
单价．
现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量分别为
１．请写出此问题的线性规划模型，并将模型化为标准型．
其中洗衣粉的市场份额出现负值是由液体洗涤剂的份额增加造成的．
电视 印刷媒体 广告后市场份额最低增量
去污剂 ０％ １％ ３％
液体洗涤剂 ３％ ２％ １８％
洗衣粉 －１％ ４％ ４％
广告单位成本（万元） １００ ２００
解：设电视的广告数量为ｘ１，印刷媒体的广告数量为ｘ２
ｍｉｎＺ＝１００ｘ１＋２００ｘ２
ｓ．ｔ．
ｘ２≥３
３ｘ１＋１２ｘ２≥１８
－ｘ１＋４ｘ２≥４
ｘ１，ｘ２≥







０
化为标准型后
ｍａｘＺ′＝－１００ｘ１－２００ｘ２＋０ｘ３＋０ｘ４＋０ｘ５
ｓ．ｔ．
ｘ２－ｘ３ ＝３
３ｘ１＋１２ｘ２－ｘ４ ＝１８
－ｘ１＋４ｘ２－ｘ５ ＝４
ｘ１，ｘ２，ｘ３，ｘ４，ｘ５≥







０
复习思路提示：
·初学时，化标准型可按“目标函数—资源限量—约束条件—决策变量”的顺序进行，化完后默念
四句口诀验证；
·化标准型是用单纯形法求解线性规划问题的第一步，非常重要！而单纯形法求解线性规划问
题是每年必考大题，此步错，后面展开步步错！
要点２　图解法
图解法求解步骤：
—４—
经典例题［１－３］　胡运权，运筹学教程（三）Ｐ１６，例１
ｍａｘＺ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
【详见课程视频】
图解法的几点启示：
线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；
若线性规划的可行域存在，则可行域一定是个凸集；
若线性规划的最优解存在，则最优解或最优解之一（无穷多解时）一定是可行域的凸集的某个
顶点；
解题思路：找出凸集的顶点，计算其目标函数值，比较即得。
图解法启示的解题思路
经典例题［１－４］　天津大学２００６，一、选择（１），２分
用图解法解线性规划时，以下几种情况不可能出现的是（　　）
Ａ．可行域有界，无有限最优解（或称无界解）　　　　Ｂ．可行域无界，有唯一最优解
Ｃ．可行域是空集，无可行解 Ｄ．可行域有界，有多重最优解
复习思路提示：
·要会用图解法来分析线性规划的几种解的情况，如唯一最优解、无穷多解、无界解和无可行解；
—５—
《运筹学》考点精讲及复习思路
·图解法容易在确定可行域的范围和等值线移动方向上犯错；
·图解法的知识点通常出现在选择、填空、判断等小题型中！大致分值在１０分以内．
思考题［１－１］　（留待以后课程讲解）
南京航空航天大学２００４，一、多项选择２、３，各５分
２．线性规划的最优解可在（　　）
Ａ．可行集内 Ｂ．可行集边界上
Ｃ．可行集顶点上 Ｄ．满足其约束条件的区域上
３．线性规划的可行集可以（　　）
Ａ．不含有任何可行解 Ｂ．恰含有一个可行解
Ｃ．恰含有两个可行解 Ｄ．含有无数个可行解
思考题［１－２］　（留待以后课程讲解）
南京航空航天大学２００６，第二题，１０分
二、（１０分）用图解法求解线性规划问题．
ｍａｘｚ＝４０ｘ１＋８０ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤３０
３ｘ１＋２ｘ２≤６０
２ｘ２≤２４
ｘ１，ｘ２≥







０
要点３　单纯形法原理
·解的概念与关系
·单纯形法迭代原理
［１］解的概念与关系
线性规划的标准型为
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ
ｘｊ≥０　　ｊ＝１，２，…，
{
ｎ
【向量形式】
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ　　ｉ＝１，２，…，ｍ
ｘｊ≥０　　ｊ＝１，２，…，
{
ｎ
—６—
【矩阵形式】
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
ＡＸ＝ｂ
Ｘ≥{ ０
线性规划问题解的概念
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ （１）
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ　　　　（２）
ｘｊ≥０　　　ｊ＝１，２，…，ｎ　　　　　　（３
{
）
可行解：满足约束条件（２）和（３）的解Ｘ＝（ｘ１，…，ｘｎ）
Ｔ全部可行解的集合称为可行域。
最优解：使目标函数（１）达到最大值的可行解。
基：设Ａ是约束方程组（２）的ｍ×ｎ阶系数矩阵（设ｎ＞ｍ），其秩为ｍ，Ｂ是Ａ中的一个ｍ×ｍ阶
的满秩子矩阵（Ｂ≠０的非奇异子矩阵），称Ｂ是线性规划问题的一个基．不失一般性，设
除基变量以外的变量称为非基变量
基解：在约束方程组（２）中，令所有的非基变量ｘｍ＋１＝ｘｍ＋２＝… ＝ｘｎ＝０，又因为 Ｂ≠０，据克
莱姆法则，对于
ａ１１ｘ１＋ａ１２ｘ２＋… ＋ａ１ｍｘｍ ＝ｂ１
ａ２１ｘ１＋ａ２２ｘ２＋… ＋ａ２ｍｘｍ ＝ｂ２
…
ａｍ１ｘ１＋ａｍ２ｘ２＋… ＋ａｍｍｘｍ ＝ｂ







ｍ
　　　Ｘ＝ ｘ１，ｘ２，…，ｘｍ，０，０，…，( )０Ｔ－基解
可以求出唯一解ＸＢ ＝ ｘ１，ｘ２，…，ｘ( )
ｍ
Ｔ
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ　　　　　　　　　　　（１）
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ　　（２）
ｘｊ≥０　　ｊ＝１，２，…，ｎ　　　　　（３
{
）
基可行解：满足变量非负约束条件（３）的基解．
可行基：对应基可行解的基．
经典例题［１－５］　胡运权，运筹学教程（三）Ｐ１９，例４
找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解．
—７—
《运筹学》考点精讲及复习思路
ｍａｘＺ＝２ｘ１＋３ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ３ ＝５
ｘ１＋２ｘ２＋ｘ４ ＝１０
ｘ２＋ｘ５ ＝４
ｘｊ≥０，ｊ＝１，２，…，







５
　　Ａ＝
１ ０ １ ０ ０
１ ２ ０ １ ０







０ １ ０ ０ １
【详见课程视频】
凸集、顶点及几个定理
设Ｋ是ｎ维欧氏空间的一点集，若Ｘ（１）∈Ｋ，Ｘ（２）∈Ｋ的连线上的所有点αＸ（１）＋（１－α）Ｘ（２）∈
Ｋ，０≤α≤１），则称Ｋ为凸集．
设Ｋ是凸集，Ｘ∈Ｋ；若Ｘ不能用不同的两点Ｘ（１）∈Ｋ和Ｘ（２）∈Ｋ的线性组合表示为Ｘ＝αＸ（１）
＋（１－α）Ｘ（２），（０＜α＜１）则称Ｘ为Ｋ的一个顶点（或极点）．
定理１　若线性规划问题存在可行解，则问题的可行域是凸集．（天津大学２００６年第三题证明，６
分）
引理　线性规划问题的可行解为基可行解的充要条件是Ｘ的正分量所对应的系数列向量是线性
独立的．
定理２　线性规划问题的基可行解Ｘ对应线性规划问题可行域（凸集）的顶点．
定理３　若线性规划问题有最优解，一定存在一个基可行解是最优解．
几个定理考察的通常是小题型，需要牢记结论，且理解各个解之间的关系。
几点结论：
【１】可行域若有界则是凸集，也可能是无界域；
【２】每个基可行解对应可行域的一个顶点；
【３】可行域有有限多个顶点；
【４】如果有最优解，必在某个顶点上得到．
线性规划解之间的关系归纳
“箭尾的解一定是箭头的解，反之不一定成立．”
当最优解唯一时，最优解也是基最优解；
当最优解不唯一时，最优解不一定是基最优解．
经典例题［１－６］　南京航空航天大学，２０１１，一、判断（１），３分
一、判断下列说法是否正确．
—８—
１）若线性规划问题的可行解为最优解，则该可行解必定是基可行解．（　　）
经典例题［１－７］　北京交通大学，２０１０，一、判断（１），２分
一、判断下列说法是否正确．
１）线性规划问题的每一个基解对应可行域的一个顶点．（　　）
单纯形法的迭代思路：
［２］单纯形法的迭代原理
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ
ｘｊ≥０　　ｊ＝１，２，…
{
ｎ
【１】构造初始可行基
Ｂ＝ Ｐ１，Ｐ２，…，Ｐ( )
ｍ ＝
１ ０ … ０
０ １ … ０
  
０ ０ …











１
·直接观察一个可行基 Ｂ≠０
·≤约束，加松弛变量；
·≥约束，加人工变量（后面会讨论）
（为讨论方便，设均为≤约束）
【２】基变换：两个基可行解相邻，两者可变换且仅变换一个基变量
—９—
《运筹学》考点精讲及复习思路
设初始基可行解为：
写出系数矩阵的增广矩阵：
可得Ｐｊ＝∑
ｍ
ｉ＝１
ａｉｊＰｉ
［移项得
→
］
Ｐｊ－∑
ｍ
ｉ＝１
ａｉｊＰｉ＝０
上式乘以一个正数θ＞０，得
θＰｊ－∑
ｍ
ｉ＝１
ａｉｊＰ( )ｉ ＝０
　　　　 ＋
∑
ｍ
ｉ＝１
Ｐｉｘｉ
０







＝ｂ
∑
ｍ
ｉ＝１
ｘ０ｉ－θａ( )
ｉｊＰｉ＋θＰｊ＝ｂ
由∑
ｍ
ｉ＝１
ｘ０ｉ－θａ( )
ｉｊＰｉ＋θＰｊ＝ｂ
可找到满足原约束方程组∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ的另一个点：
Ｘ( )１ ＝ ｘ０１－θａ１ｊ，…，ｘ
０
ｍ －θａｍｊ，０，…，θ，…，( )０Ｔ
要使Ｘ( )１ 是一个基可行解，则应对所有ｉ＝１，２，…，ｍ存在ｘ０ｉ－θａｉｊ≥０（先要使其可行）
令这ｍ个不等式至少有一个等号成立，且当ａｉｊ≤０时，上式显然成立，故可令
θ＝ｍｉｎ
ｉ
ｘ０ｉ
ａｉｊ
ａｉｊ＞{ }０ ＝ｘ
０
ｌ
ａｌｊ
可确保ｘ０ｉ－θａｉｊ
＝０，ｉ＝ｌ
≥０，ｉ≠{ ｌ
是可行解。
此时与ｘ１
１，…，ｘ１ｌ－１，ｘ
１
ｌ＋１，…，ｘ
１
ｍ，ｘ
１
ｊ对应的向量：
—０１—
【３】最优性检验和解的判别
将上述Ｘ（０），Ｘ（１）分别代入目标函数ｚ＝∑
ｎ
ｊ＝１
ｃｊｘｊ，得
ｚ( )０ ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０
ｚ( )１ ＝∑
ｍ
ｉ＝１
ｃｉ ｘｉ
０－θａ( )
ｉｊ ＋θｃｊ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ ＝ｚ
( )０ ＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ
ｚ( )０ ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０　　ｚ( )１ ＝ｚ( )０ ＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ
（１）当所有σｊ≤０，当前顶点（基可行解）的目标函数值已是最大，即为最优解；
（２）当所有σｊ≤０，又某个非基变量ｘｊ的检验数为０，则在另一个顶点也使目标函数达到最大，两
点连线上的所有点都是最优解，即无穷多最优解．当所有非基变量的σｊ＜０时，有唯一最优解；
（３）若存在某个σｊ＞０，而其对应的非基向量Ｐｊ≤０，则从θ值和ｚ
（１）的表达式可看出，线性规划
有无界解．
ｘ０ｉ－θａｉｊ≥０
线性规划解的判别定理归纳：
最优解判别定理
若Ｘ（０） ＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ≤０，ｊ＝ｍ＋１，…，ｎ，则Ｘ
（０）为最优解．
唯一最优解判别定理
若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ＜０，ｊ＝ｍ＋１，…，ｎ，则Ｘ
（０）为唯一最优解．
无穷多最优解判别定理
若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ≤０，ｊ＝ｍ＋１，…，ｎ，且存在一个非基
—１１—
《运筹学》考点精讲及复习思路
变量ｘｍ＋ｋ的σｍ＋ｋ ＝０，则存在无穷多最优解．
无界解判别定理
若有一个非基变量ｘｍ＋ｋ的σｍ＋ｋ ＞０，而其对应非基变量的所有系数ａ′ｉ，ｍ＋ｋ≤０，ｉ＝１，２，…，ｍ，则
具有无界解。
复习思路提示：
·掌握线性规划几个解的概念及几何意义，会用该知识点求解考研试题中的各类小题型；
·会在简答题中对单纯形法的迭代思路进行描述；
·了解单纯形法的迭代原理，牢记解的判别定理．
思考题［１－３］　（留待以后课程讲解）
中山大学２０１２，一、选择（３）１分
在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系数
列向量（　　）时，则此问题是无界的。
Ａ．≥０　　　　　　　Ｂ．＜０　　　　　　　Ｃ．＝０　　　　　　　Ｄ．≤０
北京交通大学２０１０，一、判断（２）２分
单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。
１）写出该线性规划的标准型（１０分）；
２）求原规划的最优解和最优目标函数值（１５）．
要点４　单纯形法的计算步骤
为书写规范和便于计算，对单纯形法的计算设计了单纯形表。
每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯
形表称为最终单纯形表。
本节介绍用单纯形表计算线性规划问题的步骤。
【１】求初始基可行解，列出初始单纯形表
ｃｊ→ ｃ１ … ｃｍ … ｃｊ … ｃｎ
ＣＢ ＸＢ ｂ ｘ１ … ｘｍ … ｘｊ … ｘｎ
ｃ１ ｘ１ ｂ１ １ … ０ … ａ１ｊ … ａ１ｎ
ｃ２ ｘ２ ｂ２ ０ ０ ａ２ｊ ａ２ｎ
      
ｃｍ ｘｍ ｂｍ ０ … １ … ａｍｊ … ａｍｎ
ｃｊ－ｚｊ ０ … ０ … ｃｊ－∑
ｍ
ｉ＝１
ｃｉａｉｊ … ｃｎ－∑
ｍ
ｉ＝１
ｃｉａｉｎ
—２１—
【２】最优性检验
【３】基变换
１）确定换入基的变量
只要有检验数大于０，对应的变量就可作为换入变量，当有一个以上检验数大于０时，一般从中选
取最大的一个：σｋ ＝ｍａｘｊ σｊ｜σｊ＞{ }０
其对应的变量ｘｋ作为换入变量。
２）确定换出基的变量
根据确定θ最小比值规则，对Ｐｋ列计算可得：θ＝ｍｉｎ
ｂｉ
ａｉｋ
ａｉｋ ＞{ }０ ＝ｂｌａｌｋ
其对应的变量ｘｌ作为换出变量。元素ａｌｋ决定了从一个基可行解到相邻基可行解的转移去向，称
之为主元素。
３）迭代变换
用换入变量ｘｋ去替换基变量中的换出变量 ｘｌ，得到一个新的基 （Ｐ１，…，Ｐｌ－１，Ｐｋ，Ｐｌ＋１，…，Ｐｍ）。
对应这个基可以找出一个新的基可行解，并相应地可以画出一张新的单纯形表。
【详见课程视频】
经典例题［１－８］　南航，２０１２，二、计算题，１．（１）１０分
二、１．（２０分）已知线性规划问题：
ｍａｘｚ＝８ｘ１＋６ｘ２
—３１—
《运筹学》考点精讲及复习思路
ｓ．ｔ．
ｘ１＋ｘ２≤８
２ｘ１＋ｘ２≤１０
ｘ１≤４
ｘ１，ｘ２≥







０
１）用单纯形法求解；
【详见课程视频】
在上面的例题［１－８］中，考虑以下两个问题：
１）若初始单纯形表中，若用检验数６对应的ｘ２作为换入变量会带来什么样的结果？
２）用图解法求解该题，看每张单纯形表对应的解与可行域中的顶点如何对应？基变换是否是相
邻的顶点间进行变换？最优解在哪个顶点取得？
复习思路提示：
·正确的标准型是单纯形法求解线性规划问题的前提；
·会依据标准型列出初始单纯形表（重点是正确找出初始基及对应的初始基变量）；
·熟练运用矩阵的初等行变换进行单纯形表迭代（最容易犯计算错误）；
·牢记最优性检验的几个解的判别定理（当遇到无穷多最优解和无界解的情况）。
思考题［１－４］　（留待以后课程讲解）
中山大学２０１２，三，１１分
用单纯形表求解以下线性规划问题：
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３≤１２
２ｘ１＋ｘ２－ｘ３≤６
－ｘ１＋３ｘ２≤９
ｘ１≥０，ｘ２≥０，ｘ３≥







０
要点５　单纯形法的进一步讨论
考虑：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可
行基？
ＭａｘＺ＝ｃ１ｘ１＋ｃ２ｘ２＋… ＋ｃｎｘｎ
—４１—
ｓ．ｔ．
ａ１１ｘ１＋ａ１２ｘ２＋… ＋ａ１ｎｘｎ ＝ｂ１
ａ２１ｘ１＋ａ２２ｘ２＋… ＋ａ２ｎｘｎ ＝ｂ２
…………………
ａｍ１ｘ１＋ａｍ２ｘ２＋… ＋ａｍｎｘｎ ＝ｂｍ
ｘ１，ｘ２，…，ｘｎ≥









０
线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，添加人工变量！
“惩罚”人工变量！———大Ｍ法和两阶段法
【１】大Ｍ法
人工变量在目标函数中的系数为－Ｍ，其中Ｍ为任意大的正数。
经典例题［１－９］　清华大学运筹学编写组（三）Ｐ３３例８
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３≤１１
－４ｘ１＋ｘ２＋２ｘ３≥３
－２ｘ１＋ｘ３ ＝１
ｘ１，ｘ２，ｘ３≥







０
—５１—
《运筹学》考点精讲及复习思路
解：１）首先化标准型，
２）添加人工变量，构造初始可行基
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３＋０ｘ４＋０ｘ５－Ｍｘ６－Ｍｘ７
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３＋ｘ４ ＝１１
－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６ ＝３
－２ｘ１＋ｘ３＋ｘ７ ＝１
ｘｊ≥０，ｊ＝１，２，…，







７
其中，Ｍ为任意大的正数。
求解结果出现所有检验数非正σｊ≤０，若基变量中含非零的人工变量，则无可行解；否则，有最优
解。
３）列初始单纯形表如下
第一步迭代，得表２
第二步迭代，得表３
—６１—
第三步迭代得最终表（所有检验数小于等于０）
【２】两阶段法
第一阶段：加入人工变量后，构造仅含人工变量的目标函数，并要求其实现最小化；
第二阶段：将一阶段得到的最终表除去人工变量。将目标函数行的系数换成原问题的目标函数
系数，作为二阶段的初始表。
同上例：
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３≤１１
－４ｘ１＋ｘ２＋２ｘ３≥３
－２ｘ１＋ｘ３ ＝１
ｘ１，ｘ２，ｘ３≥







０
解：１）添加人工变量，给出一阶段的数学模型
ｍｉｎω＝ｘ６＋ｘ７
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３＋ｘ４ ＝１１
－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６ ＝３
－２ｘ１＋ｘ３＋ｘ７ ＝１
ｘｊ≥０，ｊ＝１，２，…，







７
—７１—
《运筹学》考点精讲及复习思路
Ｘ ＝ ０，１，１，１２，( )０Ｔ是原线性规划问题的基可行解。
２）将一阶段最终表中的人工变量取消填入原问题的目标函数的系数，进行第二阶段计算。
单纯形法中的几个问题：
退化
基可行解中存在基变量等于０的解（退化解），迭代后目标函数值不变，即不同的基表示为同一个
顶点。
勃兰特（ｂｌａｎｄ）规则：
１）当遇到相同检验数时，选取对应下标最小的非基变量作为换入变量；
２）当存在两个及以上相同的最小比值时，选取下标最小的基变量作为换出变量。
检验数的几种判别形式
—８１—
复习思路提示：
·人工变量是人为加入的，与决策变量、松弛变量有本质的区别，若线性规划有最优解，人工变
量必为０，以保持原约束条件不变。为了使人工变量为０，就要使人工变量从基变量中换出成非基
变量；
·大Ｍ法和两阶段法通常不会直接出成计算大题，会在一些小题型中考察这两种方法的注意事
项。大致分值１０分以内。
思考题［１－５］
１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 。【北京科技大学】
２．简述大Ｍ法的算法步骤。【南京航空航天大学】
经典试题讲解与本章小结
一、经典试题讲解
思考题［１－１］
２．线性规划的最优解可在（　　）。【南京航空航天大学】
Ａ．可行集内 Ｂ．可行集边界上
Ｃ．可行集顶点上 Ｄ．满足其约束条件的区域上
３．线性规划的可行集可以（　　）。【南京航空航天大学】
Ａ．不含有任何可行解 Ｂ．恰含有一个可行解
Ｃ．恰含有两个可行解 Ｄ．含有无数个可行解
４．线性规划问题的每一个基解对应可行域的一个顶点。【北京交通大学，判断】
５．下面命题正确的是（　　）【昆明理工大学，单选】
Ａ．线性规划的最优解是基可行解 Ｂ．基可行解不一定是基本解
Ｃ．线性规划一定有可行解 Ｄ．线性规划的最优值至多有一个
思考题［１－２］
１．（１０分）用图解法求解线性规划问题。【南京航空航天大学】
ｍａｘｚ＝４０ｘ１＋８０ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤３０
３ｘ１＋２ｘ２≤６０
２ｘ２≤２４
ｘ１，ｘ２≥







０
２．若线性规划的可行解为最优解，则该可行解必定是基可行解。【南京航天航空大学，判断】
３．若Ｘ１，Ｘ２分别是某一线性规划问题的最优解，则Ｘ＝λ１Ｘ１＋λ２Ｘ２也是该线性规划问题的最优
解，其中λ１，λ２为正实数。【南京航天航空大学，判断】
—９１—
《运筹学》考点精讲及复习思路
思考题［１－３］
１．在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系
数列向量（　　）时，则此问题是无界的。【中山大学】
Ａ．≥０ Ｂ．＜０ Ｃ．＝０ Ｄ．≤０
２．单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。【北京交通大学判断】
分析：
ｘ１ ＝ｂ１′－ａ′１ｍ＋ｋｘｍ＋ｋ
ｘ２ ＝ｂ２′－ａ′２ｍ＋ｋｘｍ＋ｋ
………………
ｘｍ ＝ｂｍ′－ａ′ｍｍ＋ｋｘ







ｍ＋ｋ
≥０
∵ａ′ｉｍ＋ｋ≤０，对任意ｘｍ＋ｋ ＞０，即解都可行，
Ｚ＝Ｚ０＋（ｃｊ－ｚｊ）ｘｍ＋ｋ ＝Ｚ０＋σｍ＋ｋｘｍ＋ｋ
∴当ｘｍ＋ｋ→＋!
，Ｚ→＋!
．
思考题［１－４］
１．用单纯形表求解以下线性规划问题：【中山大学】
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３≤１２
２ｘ１＋ｘ２－ｘ３≤６
－ｘ１＋３ｘ２≤９
ｘ１≥０，ｘ２≥０，ｘ３≥







０
解：化标准型，并列出初始单纯形表
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３＋０ｘ４＋０ｘ５＋０ｘ６
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３＋ｘ４ ＝１２
２ｘ１＋ｘ２－ｘ３＋ｘ５ ＝６
－ｘ１＋３ｘ２＋ｘ６ ＝９
ｘｊ≥０，ｊ＝１，２，…，







６
—０２—
迭代得表２
迭代得最终表
Ｘ ＝ ６，０，６，０，０，( )１５Ｔ　　ｚ ＝１２
思考题［１－５］
１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 【北京科技大学】
２．简述大Ｍ法的算法步骤。【南京航空航天大学】
二、本章小结
【１】标准型
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ＝ｂ
Ｘ≥{ ０
　　
目标函数最大
约束条件等式
资源限量非负
决策变量非负
【２】图解法
—１２—
《运筹学》考点精讲及复习思路
可行域若有界则是凸集，也可能是无界域；
每个基可行解对应可行域的一个顶点；
可行域有有限多个顶点；
如果有最优解，必在某个顶点上得到．
……
【３】线性规划解之间的关系归纳
“箭尾的解一定是箭头的解，反之不一定成立．”
·当最优解唯一时，最优解也是基最优解；
·当最优解不唯一时，最优解不一定是基最优解．
进行标准化，列初始单纯形表方法
【４】单纯形法计算步骤框图
—２２—
【５】人工变量法———大Ｍ法
【６】人工变量法———两阶段法
一阶段目标函数最优值为０，则去掉人工变量转入第二阶段；不为０，则原问题无可行解，停止
计算。
本章涉及的知识点大部分是每年的必考题，分值约占２０％，其中解的性质及判定通常会出现在填
空、选择或简答、判断等小题型中，而单纯形法求解是每年必考的一道大题，常与第二章对偶问题联合
出题，涉及分值有时高达５０分以上。
—３２—
《运筹学》考点精讲及复习思路
第二章　对偶问题与灵敏度分析
一、本章考情分析：
常考题型：选择、填空、简答、判断和计算
分值：必考知识点，分值在２０－２５分之间
重要性：每年必考，影子价格及灵敏度分析实际应用很多
重要程度：★★★★★
二、本章基本内容：
１）熟练掌握原问题与对偶问题的转化关系（记忆转化关系表或用对称形式推导）；
２）熟练掌握单纯形法的矩阵描述；
３）掌握对偶问题的几条基本性质；
４）熟练掌握影子价格的经济意义；
５）能运用对偶单纯形法求解线性规划问题；
６）熟练掌握灵敏度分析，包括ａ，ｂ，ｃ和增加约束条件的变化。
三、本章重难点：
重点：
１）根据原问题写出对偶问题；
２）能通过单纯形法的矩阵描述，从单纯形表求原问题和对偶问题的最优解；
３）灵敏度分析中，分析各系数在什么范围内变化，最优解不变，或各系数变化后，最优解是否
改变。
难点：
对偶问题的性质的理解。
四、本章要点精讲：
·要点１　线性规划的对偶问题
·要点２　单纯形法的矩阵描述
·要点３　线性规划的对偶理论
·要点４　影子价格
·要点５　对偶单纯形法
·要点６　灵敏度分析
—４２—
要点１　线性规划的对偶问题
·对偶问题的提出
·原问题与对偶问题的数学模型
·原问题与对偶问题的对应关系
对偶问题的提出
经典例题［２－１］　胡运权主编《运筹学教程》第三版，Ｐ４８，例１
美佳公司利用现有资源生产两种产品，有关数据如下
产品Ⅰ 产品Ⅱ 资源限量
设备Ａ
设备Ｂ
调试工序
０
６
１
５
２
１
１５时
２４时
５时
利润（元） ２ １
美佳公司考虑：如何安排生产，使获利最多？
设：Ⅰ产量———ｘ１；Ⅱ产量———ｘ２
ｍａｘｚ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
收购方：收购美佳公司的资源，付出多少代价才能使美佳公司愿意放弃生产活动出让自己的资源呢？
美佳公司：出让代价应不低于同等数量的资源自己生产的利润。
设：设备Ａ———ｙ１元／时
设备Ｂ———ｙ２元／时
调试工序———ｙ３元／时
　
建立如下线性规划问题：
—５２—
《运筹学》考点精讲及复习思路
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３
ｓ．ｔ．
６ｙ２＋ｙ３≥２
５ｙ１＋２ｙ２＋ｙ３≥１
ｙ１，ｙ２，ｙ３≥
{
０
　　　　
ｍａｘｚ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
特点：
１．ｍａｘｍｉｎ
２．限定向量ｂ价值向量（资源向量）Ｃ
３．一个约束一个变量
４．ｍａｘｚ的ＬＰ约束“≤”的ＬＰ是“≥”的约束。
５．变量都是非负限制。
原问题与对偶问题的数学模型
【１】对称形式的对偶
原问题和对偶问题只含有不等式约束。
情形一：
情形二：
将原问题化成标准对称型
—６２—

ｍａｘｚ＝ＣＸ
ｓ．ｔ－ＡＸ≤－ｂ
Ｘ≥
{
０
根据标准对称型写出对偶

ｍｉｎｗ＝－Ｙ′ｂ
ｓ．ｔ　 －Ｙ′Ａ≥Ｃ
Ｙ′≥
{
０
　　
　Ｙ＝－Ｙ′
→
　
　　
ｍｉｎｗ＝Ｙｂ
ｓ．ｔ　ＹＡ≥Ｃ
Ｙ≤
{
０
【２】非对称形式的对偶
原问题的约束是等式
推导过程
原问题
　
ｍａｘｚ＝ＣＸ
ＡＸ≥ｂ
ＡＸ≤ｂ
Ｘ≥







０
　　
ｍａｘｚ＝ＣＸ
Ａ[ ]
－Ａ
Ｘ≤
ｂ[ ]
－ｂ
Ｘ≥







０
ｍｉｎｗ＝（Ｙ１，Ｙ２）·
ｂ[ ]
－ｂ
ｓ．ｔ．
（Ｙ１，Ｙ２）·
Ａ[ ]
－Ａ
≥Ｃ
Ｙ１≥０，Ｙ２≥
{
０

ｍｉｎｗ＝（Ｙ１－Ｙ２）·ｂ
（Ｙ１－Ｙ２）·Ａ≥Ｃ
Ｙ１≥０，Ｙ２≥
{
０
令Ｙ＝Ｙ１－Ｙ２，得对偶问题为：

ｍｉｎｗ＝Ｙｂ
ＹＡ≥Ｃ
Ｙ
{
无约束
证毕。
—７２—
《运筹学》考点精讲及复习思路
原问题和对偶问题的对应关系
经典例题［２－２］　北京交通大学２００９，一、５０分
已知线性规划问题如下：
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
１．求该问题的最优解；
２．写出该线性规划问题的对偶问题，并求对偶问题的最优解；
３．分别确定ｘ２，ｘ３的目标函数系数ｃ２，ｃ３在什么范围内变化最优解不变？
４．求约束条件右端值由 ( )３９ 变为
２( )１５ 时的最优解；
５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３≤５时的最优解。
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
　　

　　
ｍａｘω＝３ｙ１＋９ｙ２
ｓ．ｔ．
ｙ１≤２
２ｙ１＋ｙ２≤５
１
２ｙ１＋３ｙ２≤
１
２
ｙ１，ｙ２≥







０
复习思路提示：
·一定要掌握根据线性规划原问题写对偶问题，建议先根据原约束条件的个数确定对偶问题变
量数，再写出对偶问题的目标函数和约束条件（留待最后判别约束条件和变量的符号）；
·写对偶问题方式一是通过标准对称形式进行推导，方式二则可通过记忆对应关系表来直接
写出。
—８２—
·一定要记住数学题多是按步骤给分的，能写多少是多少。
思考题［２－１］　（留待以后课程讲解）
北京科技大学２０１１，三，１８分
对于线性规划问题：
ｍａｘＳ＝１０ｘ１＋５ｘ２
ｓ．ｔ．
３ｘ１＋４ｘ２≤９
５ｘ１＋２ｘ２≤８
ｘ１≥０，ｘ２≥
{
０
１．用单纯形法求解最优解，最优值；
２．写出最优基，最优基的逆阵；
３．写出对偶规划，对偶规划的最优解。
要点２　单纯形法的矩阵描述
·单纯形法的矩阵描述
·单纯形法计算的矩阵描述
单纯形法的矩阵描述
设线性规划问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ
ＡＸ＝ｂ
Ｘ≥{ ０
不妨设基为
Ｂ＝ Ｐ１ Ｐ２ … Ｐ( )ｍ
则Ａ＝（Ｐ１ Ｐ２ … Ｐｎ）＝（Ｂ  Ｎ）
约束方程组
ＡＸ＝ｂ（Ｂ Ｎ）
ＸＢ
Ｘ





Ｎ
＝ＢＸＢ＋ＮＸＮ ＝ｂ
ＸＢ ＝Ｂ
－１（ｂ－ＮＸＮ）＝Ｂ
－１ｂ－Ｂ－１ＮＸＮ
令ＸＮ ＝０得
目标函数
—９２—
《运筹学》考点精讲及复习思路
令ＸＮ ＝０得
检验数
线性规划问题可以等价写成：
此形式为线性规划对应于基Ｂ的典则形式（典式）。
矩阵描述时的常用公式
ＸＢ ＝Ｂ
－１ｂ
Ｎ＝Ｂ－１Ｎ
σＮ ＝ＣＮ －ＣＢＢ
－１Ｎ
ｚ０ ＝ＣＢＢ
－１







ｂ
当已知一个线性规划的可行基 Ｂ时，先求出 Ｂ－１，再用这些运算公式可得到单纯形法所要求的
结果。
单纯形法计算的矩阵描述
线性规划问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
化为标准型，引入松弛变量Ｘｓ
—０３—
ｍａｘｚ＝ＣＸ＋０Ｘｓ
ｓ．ｔ．
ＡＸ＋ＩＸｓ＝ｂ
Ｘ≥０，Ｘｓ≥
{ ０
标准型
ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ ＋０ＸＳ
ｓ．ｔ．
ＢＸＢ＋ＮＸＮ ＋ＩＸＳ ＝ｂ
ＸＢ，ＸＮ，ＸＳ≥
{ ０
　列初始单纯形表
→
　
初始单纯形表
ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ ＋０ＸＳ
ｓ．ｔ．
ＢＸＢ＋ＮＸＮ ＋ＩＸＳ ＝ｂ
ＸＢ，ＸＮ，ＸＳ≥
{ ０
初始单纯形表：
迭代后单纯形表
—１３—
《运筹学》考点精讲及复习思路
检验数应都小于等于０，即
ＣＮ －ＣＢＢ
－１Ｎ≤０
－ＣＢＢ
－１≤０
又因为基变量的检验数可写成ＣＢ－ＣＢ·Ｉ＝０
则可将检验数统一写为
Ｃ－ＣＢＢ
－１Ａ≤０
－ＣＢＢ
－１≤０
　
　令Ｙ＝ＣＢＢ
－１
→
　
　
Ｃ－ＹＡ≤０
－Ｙ≤０
　　
ＹＡ≥Ｃ
Ｙ≥{ ０
ｚ＝ＣＢＢ
－１ｂ＝Ｙｂ　　
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
从上述推导可看出，检验数行的相反数恰好是其对偶问题的一个可行解。
经典例题［２－３］　胡运权主编《运筹学教程》第三版，Ｐ５４，例３
两个互为对偶的线性规划问题，分别再加上了松弛变量和剩余变量后：
ｍａｘｚ＝２ｘ１＋ｘ２＋０ｘ３＋０ｘ４＋０ｘ５
ｓ．ｔ．
５ｘ２＋ｘ３ ＝１５
６ｘ１＋２ｘ２＋ｘ４ ＝２４
ｘ１＋ｘ２＋ｘ５ ＝５
ｘｊ≥０，ｊ＝１，２，３，４，







５
　　　　　
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３＋０ｙ４＋０ｙ５
ｓ．ｔ．
６ｙ２＋ｙ３－ｙ４ ＝２
５ｙ１＋２ｙ２＋ｙ３－ｙ５ ＝１
ｙｉ≥０，ｉ＝１，２，３，４，
{
５
用单纯形法和两阶段法求得两个问题的最终单纯形表如下：
原问题的最终单纯形表
—２３—
对偶问题的最终单纯形表
经典例题［２－２］　北京交通大学２００９，一、５０分
已知线性规划问题如下：
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
１．求该问题的最优解；
２．写出该线性规划问题的对偶问题，并求对偶问题的最优解；
３．分别确定ｘ２，ｘ３的目标函数系数ｃ２，ｃ３在什么范围内变化最优解不变？
４．求约束条件右端值由 ( )３９ 变为
２( )１５ 时的最优解；
５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３≤５时的最优解。
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
　　
ｍａｘω＝３ｙ１＋９ｙ２
ｓ．ｔ．
ｙ１≤２
２ｙ１＋ｙ２≤５
１
２ｙ１＋３ｙ２≤
１
２
ｙ１，ｙ２≥







０
单纯形法求解原问题的最终表如下：
—３３—
《运筹学》考点精讲及复习思路
Ｘ ＝ ０，０，６，０，( )９Ｔ　　Ｚ＝３　　Ｙ ＝ １，０，１，３，( )０　　ω＝３
复习思路提示：
·从上表中可以清楚地看出两个问题变量之间的对应关系。只需求解其中一个问题，从最优解
的单纯形表中即可同时得到另一个问题的最优解；
·注意单纯形乘子为 Ｙ＝ＣＢＢ
－１，其与对偶变量之间的关系，经常会考察“相差一个负号”的
理解；
·单纯形法的矩阵描述将广泛地应用到灵敏度分析部分中，要学会用Ｂ－１来求解每张表中的未知
数值。
思考题［２－２］　（留待以后课程讲解）
昆明理工大学２０１２，二，２５分
对于线性规划问题：
ｍａｘＳ＝１０ｘ１＋５ｘ２
ｓ．ｔ．
３ｘ１＋４ｘ２≤９
５ｘ１＋２ｘ２≤８
ｘ１≥０，ｘ２≥
{
０
１．写出此问题的对偶问题；
２．求出此问题和它的对偶问题的最优解和最优值。
要点３　线性规划的对偶理论
·对称性
·弱对偶性
·最优性
·对偶定理（强对偶性）
·互补松弛性
经典例题［２－４］　清华大学教材编写组《运筹学》第三版Ｐ５４，例２
原问题
ｍａｘｚ＝２ｘ１＋３ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤８
４ｘ１　　≤１６
４ｘ２≤１２
ｘ１，ｘ２≥







０
　　　　
对偶问题
ｍｉｎｗ＝８ｙ１＋１６ｙ２＋１２ｙ３
ｓ．ｔ．
ｙ１＋４ｙ２≥２
２ｙ１＋４ｙ３≥３
ｙ１，ｙ２，ｙ３≥
{
０
原问题化为极小问题，初始单纯形表：
—４３—
迭代至最终单纯形表：
对偶问题用两阶段法求解的最终单纯形表：
原问题化为极小化的最终单纯形表：
两个问题作一比较：
１．两者的最优值相同ｚ＝ｗ＝１４
２．变量的解在两个单纯形表中互相包含
原问题最优解（决策变量）
ｘ１ ＝４，ｘ２ ＝２←→对偶问题的剩余变量的检验数
对偶问题最优解（决策变量）
—５３—
《运筹学》考点精讲及复习思路
ｙ１ ＝
３
２，ｙ２ ＝１／８，ｙ３ ＝０←→原问题的松弛变量的检验数
从引例中可见：
原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另
一种表达而已。
理论证明：
原问题与对偶问题解的关系
对偶问题的基本性质
设原问题（１）
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
　　　　
对偶问题（２）
ｍｉｎｗ＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
一、对称定理
定理：对偶问题的对偶是原问题。
证对称性
原问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
　　
　对偶
→
　
　　
对偶问题
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
将对偶问题两边同时取负号，得
ｍａｘ（－ω）＝－Ｙｂ
ｓ．ｔ．
－ＹＡ≤－Ｃ
Ｙ≥{ ０
　　
　据对称标准形　
ｍａｘω′＝ｍａｘｚ＝ＣＸ
ｓ．ｔ．ＡＸ≤ｂＸ≥{
→
０
　　
ｍｉｎ（－ω）＝－ＣＸ
ｓ．ｔ．
－ＡＸ≥－ｂ
Ｘ≥{ ０
二、弱对偶性定理
若Ｘ
－
和Ｙ
－
分别是原问题（１）及对偶问题（２）的可行解，则有ＣＸ
－
≤Ｙ
－
ｂ
证明：
ＡＸ
－
≤ｂＹ
－
ＡＸ
－
≤Ｙ
－
ｂ
　　 Ｙ
－
Ａ≥ＣＹ
－
ＡＸ
－
≥ＣＸ}
→
－
ＣＸ
－
≤Ｙ
－
ＡＸ
－
≤Ｙ
－
ｂ
从弱对偶性ＣＸ
－
≤Ｙ
－
ｂ可得到以下重要结论：
（１）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的
下界。
—６３—
（２）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的
上界。
（３）若原问题可行，但其目标函数值无界，则对偶问题无可行解。
（４）若对偶问题可行，但其目标函数值无界，则原问题无可行解。
（５）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。
（６）若原问题无可行解，则其对偶问题具有无界解或无可行解。
三、最优性定理
若Ｘ 和Ｙ 分别是（１）和（２）的可行解，且有ＣＸ ＝Ｙｂ，则Ｘ，Ｙ 分别是（１）和（２）的最优解。
证明：因为（１）的任一可行解Ｘ
－
均满足ＣＸ
－
≤Ｙｂ
∵ＣＸ ＝Ｙｂ　　∴ＣＸ
－
≤ＣＸ
则Ｘ 为（１）的最优解，
反过来可知：Ｙ 也是（２）的最优解。
四、对偶定理（强对偶性）
若原问题有最优解，那么对偶问题也有最优解，且两者的目标函数值相等。
证明：设Ｘ 是原问题的最优解，则其对应的基Ｂ必存在Ｃ－ＣＢＢ
－１Ａ≤０．
∵Ｙ ＝ＣＢＢ
－１　　　∴ＹＡ≥Ｃ
即Ｙ 使对偶问题的可行解，则
ω＝Ｙｂ＝ＣＢＢ
－１ｂ
Ｘ ＝Ｂ－１ｂｚ＝ＣＸ ＝ＣＢＢ
－１ｂ
∴ＣＸ ＝ＣＢＢ
－１ｂ＝Ｙｂ
∴据最优性定理可知，Ｙ 是对偶问题的最优解。
原问题与对偶问题的解，一般有三种情况：
· →一个有有限最优解 另一个有有限最优解。
· →一个有无界解 另一个无可行解。
·两个均无可行解。
五、互补松弛性
若Ｘ
＾
，Ｙ
＾
分别是原问题（１）与对偶问题（２）的可行解，ＸＳ，ＹＳ分别为（１）、（２）的松弛变量，则：Ｙ
＾
ＸＳ
＝０，ＹＳＸ
＾
＝０Ｘ
＾
，Ｙ
＾
为最优解
—７３—
《运筹学》考点精讲及复习思路
证：设原问题和对偶问题的标准型是
原问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＹＡ－ＹＳ ＝Ｃ
Ｘ，ＸＳ≥
{ ０
　　　　
对偶问题
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＡＸ＋ＸＳ ＝ｂ
Ｙ，ＹＳ≥
{ ０
ｚ＝ ＹＡ－Ｙ( )
Ｓ Ｘ＝ＹＡＸ－ＹＳＸ
ω＝ＹＡＸ＋Ｘ( )
Ｓ ＝ＹＡＸ＋ＹＸＳ
若ＹＳＸ
∧
＝０，Ｙ
∧
ＸＳ ＝０；则ω＝Ｙ
∧
ｂ＝Ｙ
∧
ＡＸ
∧
＝ＣＸ
∧
＝ｚ，
由最优性质，可知Ｘ
∧
，Ｙ
∧
是最优解。
又若Ｘ
∧
，Ｙ
∧
分别是原问题和对偶问题的最优解，根据最优性质有，ＣＸ
∧
＝Ｙ
∧
ｂ
ｚ＝ＣＸ
∧
＝ Ｙ
∧
Ａ－Ｙ( )
Ｓ Ｘ
∧
＝Ｙ
∧
ＡＸ
∧
－ＹＳＸ
∧
ω＝Ｙ
∧
ｂ＝Ｙ
∧
ＡＸ
∧
＋Ｘ( )
Ｓ ＝Ｙ
∧
ＡＸ
∧
＋Ｙ
∧
ＸＳ
→ＹＳＸ
∧
＝Ｙ
∧
ＸＳ ＝０
经典例题［２－５］
南京航天航空大学２０１０，一、简答，５分
１．简述互补松弛性的内涵。
南京航天航空大学２０１１，一、简答，５分
２．简述对偶问题的互补松弛性
南京航天航空大学２０１２，一、简答，５分
４．何谓互补松弛性。
经典例题［２－５］：清华大学教材编写组《运筹学》第三版Ｐ５９，例５
已知线性规划问题
ｍｉｎω＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋３ｘ５
ｓ．ｔ．　ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３
ｘｊ≥０，ｊ＝１，２，…，５
已知其对偶问题的最优解为ｙ１ ＝
４
５，ｙ

２ ＝
３
５；ｚ＝５。试用对偶理论找出原问题的最优解。
解：先写出其对偶问题
ｍａｘｚ＝４ｙ１＋３ｙ２
ｓ．ｔ．　
ｙ１＋２ｙ２≤２
ｙ１－ｙ２≤３
２ｙ１＋３ｙ２≤５
ｙ１＋ｙ２≤２
３ｙ１＋ｙ２≤３
ｙ１，ｙ２≥









０
—８３—
由互补松弛性，可知
ＹＳＸ ＝０ｙｓｉｘｉ ＝０
∵ｙｓ２，ｙｓ３，ｙｓ４ ＞０
∴ｘ２ ＝ｘ３ ＝ｘ４ ＝０
∵ｙｓ１，ｙｓ５ ＝０　　∴ｘ１ ＞０，ｘ５ ＞０
由题可知
ｙ１ ＝
４
５ ＞０，ｙ

２ ＝
３
５ ＞０
由互补松弛性，
ＹＸＳ ＝０ｙｉｘｓｉ＝０
∴ｘｓ１ ＝ｘｓ２ ＝０
原问题
ｍｉｎω＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋３ｘ５
ｓ．ｔ．　ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３
ｘｊ≥０，ｊ＝１，２，…，５
ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５ ＝４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５ ＝３
因此，得到
ｘ１ ＋３ｘ５ ＝４
２ｘ１ ＋ｘ５ ＝３

ｘ１ ＝１
ｘ５ ＝
{ １
原问题的最优解为Ｘ ＝ １，０，０，０，( )１Ｔ　　ω ＝５
说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件
为严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。
复习思路提示：
（１）对偶问题的性质通常用小题型来考察，如选择、判断和填空等，分值大致在５分左右；
—９３—
《运筹学》考点精讲及复习思路
（２）若考察大题，则通常也只作为大题中的一个小题，考察内容可能是：
·从已知的对偶问题的最优解，求原问题最优解，反之亦然。
·证实原问题可行解是否为最优解。
（３）牢记定理，证明过程略懂即可，以防万一出相关证明题。
思考题［２－３］　（留待以后课程讲解）
北京科技大学２０１１，一、（１）填空，２分
若对偶问题为无界解，则原问题 。
中山大学２００９，一、（３）多项选择，５分
２．下列说法正确的有（　　）
Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；
Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；
Ｃ．已知ｙｉ 为线性规划对偶问题的最优解，若ｙｉ ＞０则说明在最优生产计划中第ｉ种资源已完全耗尽；
Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增大ｋ；
Ｅ．任何线性规划问题具有唯一的对偶问题。
要点４　影子价格
在单纯形法的每步迭代中，目标函数取值 ｚ＝ＣＢＢ
－１ｂ，和检验数 ＣＮ －ＣＢＢ
－１Ｎ中都有乘子 Ｙ＝
ＣＢＢ
－１，那么Ｙ的经济意义是什么？
影子价格
当线性规划原问题求得最优解ｘｊ（ｊ＝１，…，ｎ）时，其对偶问题也得到最优解ｙｉ（ｉ＝１，…，ｍ），
且代入各自的目标函数后有：
ｚ ＝∑
ｎ
ｊ＝１
ｃｊｘｊ ＝∑
ｍ
ｉ＝１
ｂｉｙｉ ＝ｗ
ｂｉ———是线性规划原问题约束条件的右端项，它代表第ｉ种资源的拥有量；
影子价格的定义（对偶变量ｙｉ 的意义）
代表在资源最优利用条件下对单位第ｉ种资源的估价，这种估价不是资源的市场价格，而是根据
资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（ｓｈａｄｏｗｐｒｉｃｅ）。
经典例题［２－６］　
深圳大学２０１１，一、填空（１），２分
线性规划最优生产计划中第 ｉ种资源有剩余，则该资源的影子价格为 。北京交通大学
２０１０，一、判断（３），２分
３．影子价格大于０，表示其对应资源已完全消耗完。
南京航天航空大学２０１１，二、简答（１），５分
１．简述影子价格及其经济意义。
南京航天航空大学２０１２，一、简答（１），５分
—０４—
１．简述影子价格的含义。
原问题化为极小化的最终单纯形表：
影子价格的经济意义
【１】影子价格是一种边际价格。
在ｚ ＝∑
ｎ
ｊ＝１
ｃｊｘｊ ＝∑
ｍ
ｉ＝１
ｂｉｙｉ ＝ｗ 中，
ｚ
ｂｉ
＝ｙｉ
说明ｙｉ 的值相当于在资源得到最优利用的生产条件下，ｂｉ每增加一个单位时目标函数 ｚ的
增量。
几何解释：图解法分析
ｍａｘｚ＝２ｘ１＋３ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤８
４ｘ１≤１６
４ｘ２≤１２
ｘ１，ｘ２≥







０
【详见课程视频】
【２】影子价格又是一种机会成本ｙ１ ＝
３
２，ｙ

２ ＝
１
８，ｙ

３ ＝０
·在纯市场经济条件下，当第２种资源的市场价格低于１／８时，可以买进这种资源；
·当市场价格高于影子价格时，就会卖出这种资源。
·随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等
水平时，才处于平衡状态。
【３】在对偶问题的互补松弛性质中有
—１４—
《运筹学》考点精讲及复习思路
当∑
ｎ
ｊ＝１
ａｉｊｘ
＾
ｊ＜ｂｉ时，ｙ
＾
ｉ＝０；
当 ｙ^ｉ＞０时，∑
ｎ
ｊ＝１
ａｉｊｘ
＾
ｊ＝ｂｉ
这表明生产过程中如果某种资源ｂｉ未得到充分利用时，该种资源的影子价格为零；又当资源的影
子价格不为零时，表明该种资源在生产中已耗费完毕。
复习思路提示：
（１）影子价格考察的内容通常就两部分：
·影子价格大于或等于０所代表的资源消耗情况；
·简述影子价格的经济意义。
（２）考察分值在５分以内，以选择和判断多见。
思考题［２－３］　（留待以后课程讲解）
中山大学２００９，一、（３）多项选择，５分
３．下列说法正确的有（　　）
Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；
Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；
Ｃ．已知ｙｉ为线性规划对偶问题的最优解，若ｙｉ ＞０则说明在最优生产计划中第ｉ种资源已完全
耗尽；
Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增大
ｋ；
Ｅ．任何线性规划问题具有唯一的对偶问题。
要点５　对偶单纯形法
·对偶单纯形法的基本思路
·对偶单纯形法的计算步骤
原问题每次迭代的单纯形表的检验数行对应其对偶问题的一个基解。
设原问题和对偶问题的标准型是
原问题 　　　　 对偶问题
ｍａｘｚ＝ＣＸ ｍｉｎω＝Ｙｂ
ｓ．ｔ．　
ＡＸ＋ＸＳ ＝ｂ
Ｘ，ＸＳ≥
{ ０
ｓ．ｔ．　
ＹＡ－ＹＳ ＝Ｃ
Ｙ，ＹＳ≥
{ ０
决策变量 ＸＢ ＸＮ ＸＳ
检验数 ０ ＣＮ －ＣＢＢ
－１Ｎ －ＣＢＢ
－１
对应 ＹＳ１ －ＹＳ２ －Ｙ
对偶单纯形法的基本思路
—２４—
对偶单纯形法的计算步骤
线性规划问题
ｍａｘｚ＝ＣＸ
ＡＸ＝ｂ
Ｘ≥{ ０
不妨设Ｂ＝（Ｐ１，Ｐ２，…，Ｐｍ）为对偶问题的初始可行基，则Ｃ－ＣＢＢ
－１Ａ≤０。
若 ｂ
～
ｉ≥０，ｉ＝１，２，…，ｍ，即表中原问题和对偶问题均为最优解，否则换基。
【１】列初始单纯形表，检查ｂ列的数字
·若都为非负，检验数都为非正，则已得到最优解。停止计算。
·至少还有一个负分量，检验数保持非正，转２；
【２】确定换出变量
ｍｉｎ Ｂ－１( )ｂｉ Ｂ
－１( )ｂｉ＜{ }０ ＝ Ｂ－１( )ｂｌ对应的ｘｌ为换出变量。
【３】确定换入变量
在单纯形表中检查ｘｌ所在行的各系数ａｌｊ，ｊ＝１，…，ｎ．若所有ａｌｊ≥０，则无可行解，停止计算。若存
在ａｌｊ＜０，计算θ＝ｍｉｎｊ
σｊ
ａｌｊ
ａｌｊ＜{ }０ ＝σｋａｌｋ对应的ｘｋ为换入变量。
【４】以ａｌｋ为主元素，按原单纯形表的迭代在表中进行迭代运算。
经典例题［２－７］　胡运权《运筹学教程》第三版，Ｐ６１，
例４　用对偶单纯形法求解线性规划问题：
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３
ｓ．ｔ
６ｙ２＋ｙ３≥２
５ｙ１＋２ｙ２＋ｙ３≥１
ｙ１，ｙ２，ｙ３≥
{
０
　　　
ｍａｘｗ＝－１５ｙ１－２４ｙ２－５ｙ３
ｓ．ｔ
６ｙ２＋ｙ３－ｙ４ ＝２
５ｙ１＋２ｙ２＋ｙ３－ｙ５ ＝１
ｙ１，ｙ２，…，ｙ５≥
{
０
【详见课程视频】
对偶单纯形法的优点
·不需要人工变量；
·当变量多于约束时，用对偶单纯形法可减少迭代次数；
·在灵敏度分析中，有时需要用对偶单纯形法处理简化。
对偶单纯形法缺点
—３４—
《运筹学》考点精讲及复习思路
·在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯
形法一般不单独使用。
复习思路提示：
（１）对偶单纯形法很少出单独的一道大计算题，考察分值通常在５分以内，也有可能不考察；
（２）要充分理解对偶单纯形法的算法思路，它也是单纯形法的一种。
思考题［２－４］　南京航天航空大学２０１０，一、简答（２），５分
２．简述对偶单纯形法的算法步骤。
要点６　灵敏度分析
·灵敏度问题
·四种情况分析
本节内容
灵敏度问题的分析背景
线性规划问题中，ａｉｊ，ｂｉ，ｃｊ都是常数，但这些系数是估计值和预测值。
市场的变化ｃｊ值变化；
工艺的变化ａｉｊ值变化；
资源的变化ｂｉ值变化。
问题是：
·当这些系数中的一个或多个发生变化时，原最优解会怎样变化？
·当这些系数在什么范围内变化时，原最优解仍保持不变？
·若最优解发生变化，如何用最简单的方法找到现行的最优解？
灵敏度分析的研究内容
研究线性规划中，ａｉｊ，ｂｉ，ｃｊ的变化对最优解的影响。
灵敏度分析的研究方法
经典例题［２－７］　胡运权《运筹学教程》第三版，Ｐ６３，例５
美佳公司利用现有资源生产两种产品，有关数据如下：
—４４—
产品Ⅰ 产品Ⅱ 资源限量
设备Ａ
设备Ｂ
调试工序
０
６
１
５
２
１
１５时
２４时
５时
利润（元） ２ １
厂家如何安排生产，使获利最多？
设：Ⅰ产量———ｘ１，Ⅱ产量———ｘ２
ｍａｘｚ＝２ｘ１＋ｘ２
ｓ．ｔ．　
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
原问题的最终单纯形表：
【１】分析ｂｉ的变化
ｂｉ的变化仅影响 ｂ
～
ｉ＝Ｂ
－１ｂｉ，即原最优解的可行性可能会变化：
可行性不变，则原最优解不变。
可行性改变，则原最优解改变，
用对偶单纯形法，找出最优解
{
。
问题１：设备Ｂ的能力增加到３２小时（增加了８小时），原最优计划有何变化？
ｂ
～
＝Ｂ－１ｂ′＝
１ ５／４ －１５／２
０ １／４ －１／２
０ －１／４ ３／







２
·
１５
３２







５
＝
３５／２
１１／２
－１／







２
代入最终单纯形表中
—５４—
《运筹学》考点精讲及复习思路
换基迭代得：
问题２：设设备Ｂ的能力为２４＋λ小时（增加了 λ小时），新最优解的值的可允许变化范围是
多少？
ｂ
～
＝Ｂ－１ｂ＋Ｂ－１
０
λ







０
＝
１５















２
７
２
３
２
＋
１ ５／４ －１５／２
０ １／４ －１／２
０ －１／４ ３／







２
·
０
λ







０
≥０
计算，得 －６≤λ≤６ｂ２∈ １８，[ ]３０
【２】分析ｃｊ的变化
ｃｊ的变化仅影响σｊ＝ｃｊ－ｚｊ的变化。
Ⅰ Ⅱ Ｄ
设备Ａ
设备Ｂ
调试工序
０
６
１
５
２
１
１５时
２４时
５时
利润（元） ２ １
问题３：当ｃ１ ＝１．５，ｃ２ ＝２该公司最优生产计划有何变化？
代入最终单纯形表
新的单纯形表
—６４—
换基后单纯形表为
问题４：设产品Ⅱ利润为（１＋λ），求原最优解不变时λ的范围。
方法：
·ｃ２的变化仅影响σｊ的变化；
·在最后一张单纯形表中求出变化的σｊ；
·原最优解不变，即σｊ≤０；
由上述不等式可求出λ的范围。
产品Ⅱ利润为（１＋λ）时的最终单纯形表
【３】分析ａｉｊ的变化
增加一种新产品，即增加一个新变量ｘｊ；
若ａｉｊ对应的变量ｘｊ为基变量，Ｂ将改变。
１）迭代后原问题和对偶问题都是可行解；
２）原问题和对偶问题均非可行解时，需引入人工变量求出可行解，再用单纯形法求解










 。
产品甲 产品乙 资源限量
设备 １ ２ ８台时
原材料Ａ ４ ０ １６千克
原材料Ｂ ０ ４ １２千克
利润 ２元 ３元
—７４—
《运筹学》考点精讲及复习思路
ｍａｘｚ＝２ｘ１＋３ｘ２＋０ｘ３＋０ｘ４＋０ｘ５
ｘ１＋２ｘ２＋ｘ３ ＝８
４ｘ１＋ｘ４ ＝１６
４ｘ２＋ｘ５ ＝１２
ｘ１，ｘ２，ｘ３，ｘ４，ｘ５≥







０
最终单纯形表：
１）增加一个变量ｘｊ的分析
增加一个变量相当于增加一种产品。
分析步骤：
１．计算σ
～
ｊ＝ｃｊ－ｚｊ＝ｃｊ－ＹＰｊ
２．计算Ｐ
～
ｊ＝Ｂ
－１Ｐｊ
３．若σ
～
ｊ≤０，原最优解不变；
若σ
～
ｊ＞０，则按单纯形表继续迭代，计算找出最优解。
问题５：设生产第三种产品，产量为ｘ６件，对应的ｃ６ ＝５，Ｐ６ ＝（２，６，３）
Ｔ，求最优生产计划。
解：σ
～
６ ＝５－（３／２，１／８，０）·（２，６，３）
Ｔ ＝５／４＞０
Ｐ
～
６ ＝
０ １／４ ０
－２ １／２ １
０．５ －１／







８ ０








２
６
３
＝
３／２
２
１／







４
代入原最终单纯形表中
换基后有：
—８４—
所以应该每隔６．３２天就进货，每次进货批量为６３２件。
每次花费的成本３．１６元／天。
模型二：允许缺货，补充时间较长
所谓允许缺货是指企业在存贮量降至０时，不急于补充，等一段时间，然后订货。顾客遇到缺货
也不受损失或损失很小，并假设顾客会耐心等待，直到新的补充到来。当新的补充一到，企业立即将
所缺的货物交付给这些顾客，即缺货部分不进入库存。如果允许缺货，对企业来说除了支付少量的缺
货费用外另无其他的损失，这样企业就可以利用“允许缺货”这个宽松条件，少付几次订货费用，少付
一些存贮费用，从经济观点出发这样的允许缺货现象对企业是有利的。
假设条件：
需求是连续均匀的，需求速度是Ｒ为常数；
补充需要一定时间，不考虑拖延时间，只考虑生产（装配）时间，生产速度是连续均匀的周期性
的，生产速度为Ｐ常数（Ｐ＞Ｒ）；
单位存储费为Ｃ１，单位缺货费Ｃ２，单位订购费为Ｃ３。
存储状态图
（图见视频）
Ｂ＝Ｒｔ１ ＝（Ｐ－Ｒ）（ｔ２－ｔ１）ｔ１ ＝
Ｐ－Ｒ
Ｐ ｔ２
Ａ＝（Ｐ－Ｒ）（ｔ３－ｔ２）＝Ｒ（ｔ－ｔ３）ｔ３－ｔ２ ＝
Ｒ
Ｐ（ｔ－ｔ２）
计算０－ｔ时间内的总费用：
【详见视频课程】
经典例题［９－２］　胡运权主编《运筹学教程》第三版，Ｐ３５１，例２
企业生产某种产品，正常生产条件下可生产１０件／天。根据供货合同，需要按７件／天供货。存
储费每件０．１３元／天。缺货费每件０．５元／天，每次生产准备费用为８０元，求最优存储策略？
解：Ｐ＝１０件／天，Ｒ＝７件／天
Ｃ１＝０．１３元／天件，Ｃ２＝０．５元／天件
Ｃ３＝８０元／次
ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
—９９１—
《运筹学》考点精讲及复习思路
＝ ２×８０
０．１３×槡 ７·
０．１３＋０．５
０．槡 ５ ·
１０
１０－槡 ７＝２７．６（天）
Ｑ ＝Ｒ×ｔ ＝７×２７．６＝１９３．２（件 ／次）
ｔ２ ＝
Ｃ１
Ｃ１＋Ｃ２
×ｔ ＝ ０．１３
０．１３＋０．５×２７．６＝５．５（天）
ｔ１ ＝
Ｐ－Ｒ
Ｐ ×ｔ２ ＝
１０－７
１０ ×５．５＝１．７（天）
ｔ３ ＝
Ｒ
Ｐ×ｔ
 ＋（１－ＲＰ）×ｔ

２ ＝
７
１０×２７．６＋（１－
７
１０）×５．５＝２１．０（天）
Ａ ＝Ｒ（ｔ －ｔ３）＝７×（２７．６－２１．０）＝４６．２（件）
Ｂ ＝Ｒ×ｔ１ ＝７×１．７＝１１．９（件）
Ｃ ＝２Ｃ３／ｔ ＝２×８０÷２７．６＝５．８（元 ／天）
思考：对比模型一和模型二的假设条件的区别？
Ｃ２→ !
，Ｐ→ !
模型一 模型二
ｔ ＝
２Ｃ３
Ｃ１槡Ｒ ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
Ｑ ＝Ｒｔ Ｑ ＝Ｒｔ
模型一和模型二的区别
Ｃ２→ !
，Ｐ→ !
ｔ２ ＝（
Ｃ１
Ｃ１＋Ｃ２
）ｔ ＝０　　ｔ１ ＝
Ｐ－Ｒ
Ｐ ｔ２ ＝０
ｔ３ ＝
Ｒ
Ｐｔ
 ＋（１－ＲＰ）ｔ

２ ＝０
Ａ ＝Ｒ（ｔ －ｔ３）＝Ｑ 　　Ｂ ＝Ｒｔ１ ＝０
复习思路提示：
１）模型二是确定性存储模型的最基本模型，模型一可以看做是模型二的特殊情况，而下一讲的模
型三和模型四都可以由模型二直接导出；
２）模型二由于最复杂，考试时考察频率并不高，以考察其他模型为主；
３）考试时若无明确标注不能直接套用公式，只要判断属于何种模型并套入公式求解即可。
４）简单理解公式的推导过程即可。
思考题［９－１］　江苏大学２０１１，六、计算题，１５分
某企业对某种外购件的需求速度为Ｒ＝３６５００件 ／年，订货提前期为０，每次订货费为５０元。该外
购件的价格为３０元，年存储费为１０元 ／件 ／年。如发生供应短缺，可在下批货到达时补上，但缺货损失
为４０元每件。试求：
１）经济订货批量及全年的最小总费用；（５分）
—００２—
２）如不允许发生缺货，重新求经济订货批量；（５分）
３）将１和２的结果进行比较，并解释其理由。（５分）
模型三：不允许缺货，补充时间较长
与模型二比较，取消缺货条件！最优策略可以由模型二直接导出。
Ｃ２→ !
　　ｔ２ ＝０
模型二的最优存储策略
最优存储周期：
ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
经济生产批量：
Ｑ ＝Ｒｔ ＝
２Ｃ３Ｒ
Ｃ槡 １
·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
缺货补货时间：ｔ２ ＝（
Ｃ１
Ｃ１＋Ｃ２
）ｔ
开始生产时间：ｔ１ ＝
Ｐ－Ｒ
Ｐ ｔ２
结束生产时间：ｔ３ ＝
Ｒ
Ｐｔ
 ＋（１－ＲＰ）ｔ

２
最大存储量：Ａ ＝Ｒ（ｔ －ｔ３）
最大缺货量：Ｂ ＝Ｒｔ１
平均总费用：Ｃ ＝２Ｃ３／ｔ
模型三的最优存储策略
最优存储周期：ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｐ
槡Ｐ－Ｒ
经济生产批量：Ｑ ＝Ｒｔ ＝
２Ｃ３Ｒ
Ｃ槡 １
·
Ｐ
槡Ｐ－Ｒ
缺货补货时间：ｔ２ ＝０不允许缺货！
开始生产时间：ｔ１ ＝０
结束生产时间：ｔ３ ＝
Ｒ
Ｐｔ

—１０２—
《运筹学》考点精讲及复习思路
不允许缺货！
最大存储量：Ａ ＝Ｒ（ｔ －ｔ３）
最大缺货量：Ｂ ＝０
平均总费用：Ｃ ＝２Ｃ３／ｔ 不允许缺货！
经典例题［９－３］　胡运权主编《运筹学教程》第三版，Ｐ３５２，例３
商店经销某商品，月需求速度为３０件，需求速度为常数，该商品每件进价３００元，月存储费为进
价的２％。向工厂定货该商店的订货费每次为２０元，订购后需５天才开始到货，到货速度为常数，即
每天２件。求最优存储策略。
解：需要考虑拖后时间。
Ｐ＝２件／天，Ｒ＝１件／天
Ｃ１＝３００×２％×１／３０＝０．２元／天件
Ｃ３＝２０元，ｔ０＝５天，Ｌ＝５件
订货需要５天，那么订货时间前的存储量Ｌ要能满足这５天的需求，因为不允许缺货。
存储状态图
在本例中，Ｌ称为订货点，即每当发现存储量降到 Ｌ或更低时就订购。在存储管理中，这样的存
储策略称为“定点订货”。
代入模型公式后得：
最佳存储周期ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｐ
槡Ｐ－Ｒ
＝２０天
经济生产批量Ｑ ＝
２Ｃ３Ｒ
Ｃ槡 １
·
Ｐ
槡Ｐ－Ｒ
＝２０件
结束生产时间ｔ３ ＝
Ｒ
Ｐｔ
 ＝１０天
最大存储量Ａ ＝Ｒ（ｔ －ｔ３）＝１０件
平均总费用Ｃ ＝２Ｃ３／ｔ ＝２元
模型四：允许缺货，补充时间极短
与模型二相比：取消补充需要一定时间的条件。
—２０２—
模型二的最优存储策略
最优存储周期：ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
经济生产批量：Ｑ ＝Ｒｔ ＝
２Ｃ３Ｒ
Ｃ槡 １
·
Ｃ１＋Ｃ２
Ｃ槡 ２
·
Ｐ
槡Ｐ－Ｒ
模型四的最优存储策略
最优存储周期：ｔ ＝
２Ｃ３
Ｃ１槡Ｒ·
Ｃ１＋Ｃ２
Ｃ槡 ２
经济生产批量：Ｑ ＝Ｒｔ ＝
２Ｃ３Ｒ
Ｃ槡 １
·
Ｃ１＋Ｃ２
Ｃ槡 ２
模型二的最优存储策略
缺货补货时间：ｔ２ ＝（
Ｃ１
Ｃ１＋Ｃ２
）ｔ
开始生产时间：ｔ１ ＝
Ｐ－Ｒ
Ｐ ｔ２
结束生产时间：ｔ３ ＝
Ｒ
Ｐｔ
 ＋（１－ＲＰ）ｔ

２
模型四的最优存储策略
缺货补货时间：ｔｐ ＝ｔ１ ＝ｔ２ ＝ｔ３ ＝（
Ｃ１
Ｃ１＋Ｃ２
）ｔ
模型二的最优存储策略
最大存储量：Ａ ＝Ｒ（ｔ －ｔ３）
最大缺货量：Ｂ ＝Ｒｔ１
平均总费用：Ｃ ＝２Ｃ３／ｔ
模型四的最优存储策略
最大存储量：Ａ ＝Ｒ（ｔ －ｔ３）＝Ｒ（ｔ －
Ｃ１
Ｃ１＋Ｃ２
ｔ）＝
２Ｃ２Ｃ３Ｒ
Ｃ１（Ｃ１＋Ｃ２槡 ）
最大缺货量：Ｂ ＝Ｒｔ１ ＝Ｒ·
Ｃ１
Ｃ１＋Ｃ２
ｔ ＝
２Ｃ１Ｃ３Ｒ
Ｃ２（Ｃ１＋Ｃ２槡 ）
—３０２—
《运筹学》考点精讲及复习思路
平均总费用：Ｃ ＝２Ｃ３／ｔ
模型五：价格与订货批量有关的存储模型
所谓货物单价有“折扣”是指供应方采取的一种鼓励用户多订货的优惠政策，即根据订货量的大
小规定不同的货物单价。
通常，订货越多购价越低。我们常见的所谓零售价、批发价、和出厂价，就是供应方根据货物的订
货量而制订的不同的货物单价。
模型假设：
需求是连续的、均匀的。需求速度是常数；
补充可以瞬时实现，补充时间近似为０；
单位存储费不变
每次订货量不变，订购费不变；
缺货成本为无穷大；
货物单价随订购数量而变化。
设订货批量为Ｑ，对应的货物单价为Ｋ（Ｑ）
０＜Ｑ１ ＜… ＜Ｑｎ
Ｋ１ ＞Ｋ２ ＞… ＞Ｋｎ
Ｋ（Ｑ）＝
Ｋ１　　０≤Ｑ＜Ｑ１
Ｋ２　　Ｑ１≤Ｑ＜Ｑ２

Ｋｊ　　Ｑｊ－１≤Ｑ＜Ｑｊ

Ｋｍ　　Ｑｍ－１≤











Ｑ
一个存储周期内的总费用：Ｃ（ｔ）＝１２Ｃ１Ｒｔ＋
Ｃ３
ｔ＋ＲＫ（Ｑ）
其中：Ｑ＝Ｒｔ
模型一的费用曲线图例
模型五的费用曲线图例（ｎ＝３）
—４０２—
模型五的算法步骤：
１．计算经济订购批量：Ｑ′＝Ｒｔ′＝
２Ｃ３Ｒ
Ｃ槡 １
２．如果：Ｑｉ－１≤Ｑ′＜Ｑｉ
则总的平均费用：Ｃ′＝ ２Ｃ１Ｃ３槡 Ｒ＋ＲＫｉ
３．计算每个批量的单位货物费用Ｃ（Ｑｊ）＝
１
２Ｃ１
Ｑｊ
Ｒ＋
Ｃ３
Ｑｊ
＋Ｋｊ ＝ｉ＋１，…，ｎ
４．ｍｉｎ｛Ｃ′，Ｃ（ｉ＋１），…，Ｃ（ｎ）｝＝Ｃ
则Ｃ 对应的批量为最小费用订购批量Ｑ ，对应的最小订购周期：ｔ ＝Ｑ／Ｒ。
经典例题［９－３］　胡运权主编《运筹学教程》第三版，Ｐ３５２，例３
工厂每周需要零配件３２箱，存储费每箱每周１元，每次订购费２５元，不允许缺货。零配件进货
时若：
（１）订货量１～９箱时，每箱１２元；
（２）订货量１０～４９箱时，每箱１０元；
（３）订货量５０～９９箱时，每箱９．５元；
（４）订货量１００箱以上时，每箱９元。
求最优存储策略。
解：可看出
需求速度Ｒ＝３２箱／周
存储费Ｃ１＝１元／周／箱
订购费Ｃ３＝２５元／次
Ｋ１＝１２，Ｋ２＝１０，Ｋ３＝９．５，Ｋ４＝９
先求出经济订货批量
Ｑ′＝
２Ｃ３Ｒ
Ｃ槡 １
＝ ２×２５×３２
槡 １ ＝４０（箱）
１０＜４０＜４９属于第二个订货批量范围
则该批量下的单位货物订购总费用为：
—５０２—
《运筹学》考点精讲及复习思路
Ｃ′( )４０ ＝
１
２Ｃ１
Ｑ′
Ｒ＋
Ｃ３
Ｑ′＋Ｋ２ ＝
１
２×１×
４０
３２＋
２５
４０＋１０＝１１．２５（元）
其次求出各批量订货下的单位货物总费用（经济订货批量已经在第二个范围内，就不再考虑第一
个订货数量了）
Ｃ（５０）＝１２Ｃ１
Ｑ３
Ｒ＋
Ｃ３
Ｑ３
＋Ｋ３ ＝
１
２×１×
５０
３２＋
２５
５０＋９．５≈１０．３９（元）
Ｃ（１００）＝１２Ｃ１
Ｑ４
Ｒ＋
Ｃ３
Ｑ４
＋Ｋ４ ＝
１
２×１×
１００
３２＋
２５
１００＋９≈１０．８１（元）
因此，Ｃ ＝ｍｉｎ｛１１．２５，１０．３９，１０．８１｝＝１０．３９＝Ｃ（５０）
故：Ｑ ＝５０（箱）
ｔ ＝Ｑ／Ｒ＝５０／３２≈１．５６≈１１（天）
复习思路提示：
１）每个模型的最优存储策略的各个参数中，最优存储周期 ｔ 是最基本的参数，其他各个参数与
它的关系在各个模型中都是相同的。
２）根据模型假设条件的不同，各个模型的最优存储周期 ｔ 之间也有明显的规律性。因子
Ｃ１＋Ｃ２
Ｃ( )
２
对应了是否允许缺货的假设条件，因子 Ｐ( )Ｐ－Ｒ
对应了补充是否需要时间的假设条件。
３）考试是请牢记公式！！！或会用状态图推导。
思考题［９－２］　暨南大学２０１１，四、计算题，２５分
某厂每年需要某种元件５０００个，每次订购费为５０元，保管费每件每年１元，不允许缺货，元件单价
ｋ随采购数量的不同而变化，问公司每次应该订购多少？总采购成本是多少？
ｋ（Ｑ）＝
２．０元，Ｑ＜１５００
１．９元，Ｑ≥{ １５００
经典试题讲解与本章小结
一、经典例题精讲
思考题［９－１］　江苏大学２０１１，六、计算题，１５分
某企业对某种外购件的需求速度为Ｒ＝３６５００件 ／年，订货提前期为０，每次订货费为５０元。该外
购件的价格为３０元，年存储费为１０元 ／件 ／年。如发生供应短缺，可在下批货到达时补上，但缺货损失
为４０元每件。试求：
１）经济订货批量及全年的最小总费用；（５分）
２）如不允许发生缺货，重新求经济订货批量；（５分）
３）将１和２的结果进行比较，并解释其理由。（５分）
解：需求速度Ｒ＝３６５００件／年
存储费Ｃ１＝１０元／年／件
—６０２—
订购费Ｃ３＝５０元／次
货物单价Ｋ＝３０元
缺货费Ｃ２＝４０元／件
１）经济订货批量及全年的最小总费用；
此问题属于模型四，允许缺货，且补充时间极短
Ｑ ＝
２Ｃ３ＲＣ１＋Ｃ( )
２
Ｃ１Ｃ槡 ２
＝
２×５０×３６５００× １０＋( )４０
１０×槡 ４０ ≈６７５．４６（件）
ｔ ＝
２Ｃ３ Ｃ１＋Ｃ( )
２
Ｃ１Ｃ２槡 Ｒ ＝
２×５０× １０＋( )４０
１０×４０×槡 ３６５００ ≈０．０１８５
Ｃ ＝２Ｃ３／ｔ ＝
２×５０
０．０１８５≈５４０５．４１（元）
２）如不允许发生缺货，重新求经济订货批量；
此问题属于模型一，不允许缺货，且补充时间极短
Ｑ ＝
２Ｃ３Ｒ
Ｃ槡 １
＝ ２×５０×３６５００
槡 １０ ＝６０４．１５（件）
ｔ ＝
２Ｃ３
Ｃ１槡Ｒ＝
２×５０
１０×槡 ３６５００≈０．０１６５
Ｃ ＝２Ｃ３／ｔ ＝
２×５０
０．０１６５≈６０６０．６１（元）
３）将１和２的结果进行比较，并解释其理由。
因为不允许缺货，即缺货的成本无穷大，那么不允许缺货时订货周期短一些（０．０１６５＜０．０１８５），
每次的订货量也相应减少了一些（６０４．１５＜６７５．４６），但是较允许缺货时，订购频繁了，且订购费用增
加了，从５４０５．４１元增加到了６０６０．６１元。
思考题［９－２］　暨南大学２０１１，四、计算题，２５分
某厂每年需要某种元件５０００个，每次订购费为５０元，保管费每件每年１元，不允许缺货，元件单
价ｋ随采购数量的不同而变化，问公司每次应该订购多少？总采购成本是多少？
ｋ( )Ｑ ＝
２．０元，Ｑ＜１５００
１．９元，Ｑ≥{ １５００
解：可看出
需求速度Ｒ＝５０００个／年
存储费Ｃ１＝１元／年／件
订购费Ｃ３＝５０元／次
Ｋ１＝２，Ｋ２＝１．９
需求速度Ｒ＝５０００个／年
存储费Ｃ１＝１元／年／件
—７０２—
《运筹学》考点精讲及复习思路
订购费Ｃ３＝５０元／次
Ｋ１＝２，Ｋ２＝１．９
先求出经济订货批量
Ｑ′＝
２Ｃ３Ｒ
Ｃ槡 １
＝ ２×５０×５０００
槡 １ ＝ 槡５００２≈７０７（个）
其次，因为７０７＜１５００，则求第二个批量订货下的单位订购费用：
Ｃ（７０７）＝１２Ｃ１
Ｑ‘
Ｒ＋
Ｃ３
Ｑ’
＋Ｋ１ ＝
１
２×１×
７０７
５０００＋
５０
７０７＋２≈２．１４（元 ／个）
Ｃ（１５００）＝１２Ｃ１
Ｑ
Ｒ＋
Ｃ３
Ｑ＋Ｋ２ ＝
１
２×１×
１５００
５０００＋
５０
１５００＋１．９≈２．０８（元 ／个）
∵Ｃ( )７０７ ＞Ｃ( )１５００∴最佳订购批量为１５００个。
总采购费用：
Ｃ ＝１２Ｃ１Ｑ＋
Ｃ３Ｒ
Ｑ ＋Ｋ２Ｒ＝
１
２×１×１５００＋
５０×５０００
１５００ ＋１．９×５０００≈１０４１６．６７（元）
二、本章小结
存储模型基本要素：
Ｃ１———单位存储费用
Ｃ２———单位缺货费用
Ｃ３———单位订货费用
Ｑ———平均存储量／经济订货批量
Ｒ———需求速度
Ｐ———生产速度／装配速度
ｔ———存储周期
Ｋ———货物单价
确定性存储的四种模型：
模型一：不允许缺货，补充时间极短
Ｃ２→ !
Ｐ→ !
模型二：允许缺货，补充时间较长
最大缺货量Ｂ，最大存储量Ａ
模型三：不允许缺货，补充时间较长
Ｃ２→ !
最大存储量Ａ
模型四：允许缺货，补充时间极短
—８０２—
Ｐ→ !
最大缺货量Ｂ，最大存储量Ａ
确定性存储模型的公式汇总：
确定性存储的四种模型：
模型五：价格与订货批量有关的存储模型
模型假设：
需求是连续的、均匀的。需求速度是常数；
补充可以瞬时实现，补充时间近似为０；
单位存储费不变
每次订货量不变，订购费不变；
缺货成本为无穷大；
货物单价随订购数量而变化。
一个存储周期内的总费用：
设订货批量为Ｑ，对应的货物单价为Ｋ（Ｑ）
Ｋ（Ｑ）＝
Ｋ１　　０≤Ｑ＜Ｑ１
Ｋ２　　Ｑ１≤Ｑ＜Ｑ２

Ｋｊ　　Ｑｊ－１≤Ｑ＜Ｑｊ

Ｋｍ　　Ｑｍ－１≤











Ｑ
一个存储周期内的总费用：
Ｃ（ｔ）＝１２Ｃ１Ｒｔ＋
Ｃ３
ｔ＋ＲＫ（Ｑ）　　其中：Ｑ＝Ｒｔ
模型五的算法步骤：
１．计算经济订购批量：Ｑ′＝Ｒｔ′＝
２Ｃ３Ｒ
Ｃ槡 １
—９０２—
《运筹学》考点精讲及复习思路
２．如果：Ｑｉ－１≤Ｑ′＜Ｑｉ
则该批量下的单位货物总费用：Ｃ′( )Ｑ′＝
１
２Ｃ１
Ｑ′
Ｒ＋
Ｃ３
Ｑ′＋Ｋ
( )Ｑ′
３．计算每个批量的单位货物费用
Ｃ（Ｑｊ）＝
１
２Ｃ１
Ｑｊ
Ｒ＋
Ｃ３
Ｑｊ
＋Ｋｊ ＝ｉ＋１，…，ｎ
４．ｍｉｎ｛Ｃ′，Ｃ（ｉ＋１），…，Ｃ（ｎ）｝＝Ｃ
则Ｃ 对应的批量为最小费用订购批量Ｑ ，对应的最小订购周期：ｔ ＝Ｑ／Ｒ。
—０１２—
第十章　排队论
一、本章考情分析：
常考题型：计算题
分值：１５分左右
重要性：考察该知识点的学校较少
重要程度：★★
二、本章基本内容：
１）了解排队系统的基本概念；
２）了解生灭过程及状态转移图的推演；
３）掌握排队系统的主要数量指标和记号；
４）熟练掌握常见排队模型及其求解方法，重点掌握单服务台排队模型。
三、本章重难点：
重点：单服务台排队模型
难点：
１）状态转移图的理解；
２）状态概率公式的推演。
四、本章要点精讲：
·要点１　排队系统的基本概念
·要点２　生灭过程
·要点３　单服务台排队模型
要点１　排队系统的基本概念
常见的排队系统
到达的顾客 要求的服务 服务机构
不能运转的机器 修理 修理工人
修理工人 领取修配零件 管理员
病人 就诊 医生
打电话 通话 交换台
—１１２—
《运筹学》考点精讲及复习思路
文稿 打字 打字员
录入计算机中的文件 打印 打印机
提货单 提取货物 仓库管理员
待降落的飞机 降落 跑道指挥机构
到达港口的货船 装货或卸货 码头（泊位）
河水进入水库 放水、调整水位 水闸管理员
进入餐馆的顾客 就餐 餐位服务员
来到路口的汽车 通过路口 交通管理员或红绿灯
来到车站的乘客 乘车 公交车管理员
排队系统的基本构成
一个排队系统包括：
在一定时间内顾客平均到达多少？
按什么规律到达（输入过程服从什么分布）？
进入系统的顾客按照什么规则排队？
服务机构设置多少服务设施？排列形式？
服务时间服从什么分布？
排队系统的三大特征
输入过程、排队规则、服务机构。
【１】输入过程
输入是指顾客到达服务系统的情况。
可能有下列情况，但并不相互排斥：
（１）按顾客源总数划分为有限和无限两大类。如工厂需要检修的机器是有限的，准备进京观光旅
游的游客是无限的。
（２）按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商品的顾客是单个的，到
港国际航班等待安检的旅客是成批的。
（３）按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运行的班车、班轮、班机
是确定的，到加油站加油的汽车是随机的。对随机的顾客到达需要知道单位时间到达的顾客数或时
间间隔的概率分布。
（４）按接受过服务的顾客对顾客到达数是否有影响，划分为相互独立到达和非相互独立到达。如
—２１２—
提供优质服务的餐饮业所产生了大量“回头客”，就属于非相互独立到达。我们只讨论独立到达情况。
（５）按顾客相继到达间隔时间的分布及其数字特征是否与时间有关可分为平稳与非平稳的。相
继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，称为平稳的，否则是非平稳的。
一般非平稳情况的数学处理很困难，我们只讨论平稳状况。
【２】排队规则
排队规则指到达排队系统的顾客按怎样的规则排队等待。
（１）按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制，等待制和混合制
三种。
当顾客到达时，所有的服务台均被占用，顾客随即离去，称为损失制（或称即时制、消失制）；
当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去，称为等待制，
例如出故障的机器排队等待维修就是这种情况；
介于损失制和等待制之间的是混合制。
等待制的服务规则：先到先服务（ＦＣＦＳ）、先到后服务（ＬＣＦＳ）、带优先服务权（ＰＲ）、随机服务
（ＳＩＲＯ）等。在后面研究的问题中均假设采取ＦＣＦＳ服务规则。
（２）按队列长度是否有限，可分为队长有限和队长无限两种情况。在限度以内就排队等待，超过
一定限度就离去。
（３）按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移，有的则不能（用栏杆等
隔开）；有的排队顾客因等候时间过长而离开，有的则不能（如在高速公路行驶的汽车必须坚持到高速
出口）。
我们所讨论的问题限制在队列间不能相互转移，中途不能退出的情形。
【３】服务机构
从机构形式和工作情况来看有以下几种：
（１）服务机构可以没有服务员，也可以有一个或多个服务员（服务台、窗口）。如超市的货架可以
没有服务员，但交款时可能有多个服务员。
（２）多个服务台的情况中，可以是平行排列的（并联），也可是前后排列的（串联），也可以是混
合的。
—３１２—
《运筹学》考点精讲及复习思路
（３）服务方式可以对单个顾客进行，也可成批进行。我们只讨论单个服务情况。
（４）服务时间可分为确定型的和随机型的。如旅客列车对乘客的服务是按列车时刻表进行位移
服务的，是确定型的；因患者病情不同，医生诊断的时间不是确定的，是随机型的。
（５）服务时间的分布总假定是平稳的，即分布的期望值、方差等参数不受时间的影响。
排队模型的表示
肯德尔（Ｋｅｎｄａｌ）记号
肯德尔（Ｋｅｎｄａｌ）于１９５３年提出排队系统的分类记号：
输入分布／输出分布／并联的服务站数（Ｘ／Ｙ／Ｚ）
１９７１年国际排队符号标准会上肯德尔将上述分类记号扩充到六项，记为（Ｘ／Ｙ／Ｚ／Ａ／Ｂ／Ｃ）：
输入分布／输出分布／并联的服务站数／系统容量（队长）／系统状态（顾客源数）／服务规则
如Ｍ／Ｍ／１／
!
／
!
／ＦＣＦＳ
排队问题的求解
求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决
定系统结构是否合理、研究设计改进措施等。因此必须确定用以判断系统运行优劣的基本数量指标，
也称为系统运行指标。
这些数量指标一般来说都是随机变量，并且和系统运行的时间 ｔ有关。这里主要研究平稳状态，
此时系统处于平衡状态，数量指标的分布等与时间无关，此时求得的结果为系统处于统计平衡下
的解。
排队问题的常用指标
１）队长（Ｌｓ）和排队长（Ｌｑ）
队长指系统内顾客数，包括正在接受服务的顾客与排队等待服务的顾客数（排队长），即
—４１２—
系统中的顾客数 ＝排队等候服务的顾客数 ＋正在接受服务的顾客数
２）逗留时间（Ｗｓ）和等待时间（Ｗｑ）
逗留时间指顾客在排队服务系统中从进入到服务完毕离去的平均逗留时间；
等待时间指顾客排队等待服务的平均等待时间。这是顾客最关心的，每个顾客希望逗留时间或
等待时间越短越好。
服务机构工作强度：指服务机构累计工作时间占全部时间的比例，是衡量服务机构利用效率的指
标。即：
服务机构
工作强度
＝ 用于服务顾客的时间
服务设施总的服务时间
＝１－服务设施总的空闲时间
服务设施总的服务时间
忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间的长度，即服务机构连续繁忙
的时间长度，它关系到服务员的工作强度。忙期和一个忙期中平均完成服务顾客数都是衡量服务机
构效率的指标。
排队系统运行指标间的关系
设：
λ表示单位时间内顾客的平均到达数，则１／λ表示相邻两个顾客到达的平均间隔时间；
μ表示单位时间内被服务完毕离去的平均顾客数，则１／μ表示对每个顾客的平均服务时间；
ｓ表示服务系统中并联的服务台数，
Ｐｎ（ｔ）在时刻ｔ系统中恰好有ｎ个顾客的概率。
排队系统的输入与输出（即到达与服务的规律）
顾客到达流和服务时间流的分布一般都是非负的随机变量。最常见的是泊松分布、指数分布和
埃尔朗分布。然而在研究具体问题时，究竟是服从哪种分布呢？通常抽取到达时间间隔和服务时间
样本，统计其分布（经验分布），并按照统计学的方法进行检验（如检验），以确定服从哪种理论分布。
考试基本只涉及到泊松分布和负指数分布的情况。
排队系统的输入与输出（即到达与服务的规律）
【１】泊松分布
—５１２—
《运筹学》考点精讲及复习思路
泊松分布（最简单流）需要满足以下三个条件：
（１）平稳性：指在一定时间间隔内，来到服务系统有 ｋ个顾客的概率仅与这段时间间隔的长短有
关，而与这段时间的起始时刻无关；
（２）无后效性：指在不相交的时间区间内到达的顾客数是相互独立的，或者说在区间［ａ， ＋ｔ］来
到ｋ个顾客的概率与时间ａ之前来到多少个顾客无关；
（３）普通性（稀有性）：指在足够小的时间区间内只能有一个顾客到达，不可能有两个以上顾客同
时到达。
所谓最简单流，是指在ｔ这段时间内有ｋ个顾客来到服务系统的概率服从泊松（Ｐｏｉｓｓｏｎ）分布，故
也称为泊松流。即：
Ｐｋ( )ｔ＝ｅ－λｔ λ
( )ｔｋ
ｋ！ 　　 ｋ＝０，１，２( )，…
当ｋ＝０时，有Ｐ０( )ｔ＝ｅ－λｔ
其均值和方差为Ｅ( )Ｔ ＝Ｖａｒ( )Ｔ ＝λｔ
【２】负指数分布
如果随机变量Ｔ的概率密度为：ｆ( )ｔ＝μｅ－μｔｔ≥０
则称Ｔ服从指数分布，其分布函数是：
Ｆ( )ｔ＝ＰＴ≤( )ｔ＝１－ｅ－μｔｔ≥０
数学期望和方差为：
Ｅ( )Ｔ ＝
１
μ
　　Ｖａｒ( )Ｔ ＝
１
μ２
均值１／μ表示对每个顾客的平均服务时间；
μ表示服务率，即单位时间内平均服务完多少人。
复习思路提示：
１）现有的排队系统理论只针对顾客独立到达、平稳状态的对单个顾客服务的情况，且队列间不能
相互转移，中途不能退出的情形；
２）考试通常只考察输入服从泊松分布或负指数分布，输出服从负指数分布的情况，通常只要判断
出题目属于何种排队模型，并套用ｌｉｔｌｅ公式求解即可；
３）要理解各系统运行指标的含义。
要点２　生灭过程
生灭过程（生死过程）
是用来处理输入为最简单流，服务时间为指数分布这类最简单排队模型的方法。它是分析后面
各类排队问题的方法论，在排队论中有重要意义。
如，某地区当前人口数为ｎ，该年人口出生数λｎ，则根据泊松流的性质，在 Δｔ时间内出生一个人
的概率为λｎΔｔ＋ｏΔ( )ｔ；μｎ为该年人口死亡数，则根据指数分布的性质，在Δｔ时间内死亡一个人的概
—６１２—
率为μｎΔｔ＋ｏΔ( )ｔ，那么在经过Δｔ间后，人口将变成多少？
生灭过程状态转移图
【详见课程视频】
复习思路提示：
１）生灭过程是分析后面各类排队问题的方法论，理解生灭过程有助于理解排队系统运行指标的
推导求解；
２）掌握根据状态转移图得出任一状态下的平衡方程，即对任一状态来说，单位时间内进入该状态
的平均次数和单位时间内离开该状态的平均次数应该相等，这就是系统在统计平衡下的“输入 ＝输
出”原理。
要点３　单服务台模型
·Ｍ／Ｍ／１／
!
／
!
·Ｍ／Ｍ／１／Ｎ／
!
·Ｍ／Ｍ／１／
!
／ｍ
【１】Ｍ／Ｍ／１／
!
／
!
标准的Ｍ／Ｍ／１／∞／∞模型需要满足的条件
输入过程：顾客源无限，单个到来，相互独立，到达平均数为常数，且服从泊松分布，到达过程是平
稳的。
排队规则：单队，系统容量无限，队长不受限制，先到先服务。
服务机构：单服务台、平均服务率为常数，对各顾客服务时间相互独立，服从相同的指数分布，服
务过程也是平稳的。
这是一类最简单的排队系统。
Ｍ／Ｍ／１／∞／∞模型的状态转移图
Ｍ／Ｍ／１／∞／∞系统运行指标
由于到达平均数和服务平均数均为常数，即
λ０ ＝λ１ ＝… ＝λｎ－１ ＝λ，μ１ ＝μ２ ＝… ＝μｎ ＝μ
于是有Ｃｎ ＝
λｎ－１…λ１λ０
μｎ…μ２μ１
＝ λ( )μ
ｎ
＝ρｎ
式中ρ＝λμ
＜１称为业务密度 ／服务强度
∑
!
ｎ＝０
Ｃｎ ＝∑
!
ｎ＝０
ρｎ ＝ １
１－ρ
Ｐ０ ＝１／∑
!
ｎ＝０
Ｃｎ ＝１－ρ
—７１２—
《运筹学》考点精讲及复习思路
依次推导，有
Ｐｎ ＝ＣｎＰ０ ＝ρ
ｎＰ０ ＝ρ
ｎ（１－ρ）
系统内的顾客数，队长期望值
依次推导，有
顾客在系统内的逗留时间
Ｗｓ＝
Ｌｓ
λ
＝ １
μ－λ
顾客排队的等待时间
Ｗｑ ＝Ｗｓ－
１
μ
＝ １
μ－λ
－１
μ
＝ λ
μ（μ－λ）
＝ ρ
μ－λ
系统中排队长度的期望值
Ｌｑ ＝λＷｑ ＝
ρλ
μ－λ
Ｌｉｔｌｅ公式
Ｌｓ＝λＷｓＷｓ＝
Ｌｓ
λ
Ｌｑ ＝λＷｑＷｑ ＝
Ｌｑ
λ
Ｗｓ＝Ｗｑ＋
１
μ
Ｌｓ＝Ｌｑ＋
λ
μ
经典例题［１０－１］　胡运权主编《运筹学教程》第三版，Ｐ３１８，例１
某修理店只有一个修理工，要求提供服务的顾客到达过程为泊松流，平均４人／小时；修理时间服
从负指数分布，平均需要６分钟。试求：１）修理店空闲的概率；２）店内恰有３个顾客的概率；３）店内至
少有１个顾客的概率；４）在店内的平均顾客数；５）每位顾客在店内的平均逗留时间；６）等待服务的平
均顾客数；７）每位顾客平均等待服务时间。
解：这属于Ｍ／Ｍ／１／∞／∞排队模型，其中
λ＝４μ＝ １０．１＝１０ρ＝
λ
μ
＝２５
１）修理店空闲的概率
Ｐ０ ＝１－ρ＝１－
２
５ ＝０．６
—８１２—
２）店内恰有３个顾客的概率
Ｐ３ ＝ρ
３ １－( )ρ＝( )２５
３
１－( )２５ ＝０．０３８
３）店内至少有１个顾客的概率
ＰＮ≥{ }１ ＝１－Ｐ０ ＝０．４
４）在店内的平均顾客数
Ｌｓ＝
ρ
１－ρ
＝０．４０．６≈０．６７（人）
５）每位顾客在店内的平均逗留时间
Ｗｓ＝
Ｌｓ
λ
＝０．６７４ （ｈ）≈１０
( )ｍｉｎ
６）等待服务的平均顾客数
Ｌｑ ＝Ｌｓ－ρ＝
ρ２
１－ρ
＝０．１６０．６≈０．２６７
( )人
７）每位顾客平均等待服务时间
Ｗｑ ＝
Ｌｑ
λ
＝０．２６７４
( )ｈ≈４( )ｍｉｎ
【２】Ｍ／Ｍ／１／Ｎ／
!
模型需要满足的条件
输入过程：顾客源无限，服从泊松分布。
排队规则：系统最大容量为Ｎ，排队等候的顾客最多为Ｎ－１，至某时刻一顾客到达时，如系统中已
有Ｎ个顾客，那么这个顾客就被拒绝进入系统。
服务机构：单服务台，服从相同的指数分布。
状态转移图
状态概率的稳态方程
μＰ１ ＝λＰ０
μＰｎ＋１＋λＰｎ－１ ＝ λ＋( )μＰｎ，ｎ≤Ｎ－１
μＰＮ ＝λＰＮ－
{
１
Ｐ０＋Ｐ１＋… ＋ＰＮ ＝１
系统稳态概率ρ＝λμ
—９１２—
《运筹学》考点精讲及复习思路
Ｐ０ ＝
１－ρ
１－ρＮ＋１
，ρ≠１
Ｐｎ ＝
１－ρ
１－ρＮ＋１
ρｎ，ｎ≤Ｎ
系统运行指标
１）系统中的平均顾客数（队长期望值）
Ｌｓ＝
ρ
１－ρ
－（Ｎ＋１）ρ
Ｎ＋１
１－ρＮ＋１
２）系统中排队等待服务的平均顾客数（排队长期望值）
Ｌｑ ＝Ｌｓ－ １－Ｐ( )
０
３）系统中顾客逗留时间的期望值
Ｗｓ＝
Ｌｓ
μ１－Ｐ( )
０
４）队列中顾客等待时间的期望值
Ｗｑ ＝Ｗｓ－
１
μ
经典例题［１０－２］　清华大学教材编写组《运筹学》第三版，Ｐ３２１，例４
单人理发馆有６个椅子接待人们排队等待理发。当６个椅子都坐满时，后来到的顾客不进店就
离开。顾客平均到达率为 ３人／小时，理发需时平均 １５分钟。则 Ｎ＝７为系统中最大的顾客数。
试求：
１）某顾客一到达就能理发的概率；
２）需要等待的顾客数的期望值；
３）有效到达率；
４）一顾客在理发馆内逗留的期望时间；
５）可能到来的顾客不等待就离开的概率。
解：这属于Ｍ／Ｍ／１／Ｎ／∞排队模型，其中
Ｎ＝７λ＝３人 ／( )小时 μ＝４人 ／( )小时 ρ＝λμ
＝３４
１）某顾客一到达就能理发的概率；———相当于理发馆没客人
Ｐ０ ＝
１－ρ
１－ρＮ＋１
＝ ０．２５
１－０．７５８
≈０．２７７８
２）需要等待的顾客数的期望值；
Ｌｓ＝
ρ
１－ρ
－（Ｎ＋１）ρ
Ｎ＋１
１－ρＮ＋１
＝０．７５０．２５－
８×０．７５８
１－０．７５８
≈２．１１
Ｌｑ ＝Ｌｓ－ １－Ｐ( )
０ ＝２．１１－ １－０．( )２７７８≈１．３９
３）有效到达率；
—０２２—
λｅ ＝μ１－Ｐ( )
０ ＝４× １－０．( )２７７８ ＝２．８９人 ／( )小时
平均到达率是指系统有空时的平均到达率，当系统满员，到达率为０，因此要求有效到达率。
４）一顾客在理发馆内逗留的期望时间；
Ｗｓ＝
Ｌｓ
λｅ
＝２．１１２．８９＝０．７３（小时）
５）可能到来的顾客不等待就离开的概率。———系统满员（理发馆的损失率）
Ｐ７ ＝
１－ρ
１－ρ７＋１
ρ７ ＝ ０．２５
１－０．７５８
×０．７５７≈３．７％
【３】Ｍ／Ｍ／１／
!
／ｍ
模型需要满足的条件
输入过程：顾客总体为 ｍ个，每个顾客到达并经过服务后，仍然回到原来总体，所以仍然可以到
来，服从泊松分布。
排队规则：系统容量无限。
服务机构：单服务台，服从相同的指数分布。
状态转移图
状态概率的稳态方程
μＰ１ ＝ｍλＰ０
μＰｎ＋１＋ ｍ－ｎ＋( )１λＰｎ－１ ＝ ( )ｍ－ｎλ＋[ ]μＰｎ，ｎ≤ｍ－１
μＰｍ ＝λＰｍ－
{
１
∑
ｍ
ｉ＝０
Ｐｉ＝１
系统稳态概率
Ｐ０ ＝
１
∑
ｍ
ｉ＝０
ｍ！
( )ｍ－ｉ！
λ( )μ
ｉ
Ｐｎ ＝
ｍ！
( )ｍ－ｎ！
λ( )μ
ｎ
Ｐ０，１≤ｎ≤ｍ
系统运行指标
１）系统中的平均顾客数（队长期望值）
Ｌｓ＝ｍ－
μ
λ １－Ｐ
( )
０
２）系统中排队等待服务的平均顾客数（排队长期望值）
—１２２—
《运筹学》考点精讲及复习思路
Ｌｑ ＝Ｌｓ－ １－Ｐ( )
０ ＝ｍ－
λ＋( )μ １－Ｐ( )
０
λ
３）系统中顾客逗留时间的期望值
Ｗｓ＝
Ｌｓ
μ１－Ｐ( )
０
＝ ｍ
μ１－Ｐ( )
０
－１
λ
４）队列中顾客等待时间的期望值
Ｗｑ ＝Ｗｓ－
１
μ
有效到达率
平均到达率是在无限源的情形是按全体顾客来考虑的；在有限源的情形必须按照每个顾客来考
虑。若每个顾客的到达率都是λ，则此时系统外的顾客平均数为ｍ－Ｌｓ，对系统的有效到达率则为：
λｅ ＝λｍ－Ｌ( )
ｓ
经典例题［１０－３］　清华大学教材编写组《运筹学》第三版，Ｐ３２３，例５
某车间有５台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间１５分钟，有一
个修理工，每次修理时间服从负指数分布，平均每次１２分钟。试求：１）修理工空闲的概率；２）５台机
器都出故障的概率；３）出故障的平均台数；４）等待修理的平均台数；５）平均停工时间；６）平均等待修
理时间；７）评价这些结果。
解：这属于Ｍ／Ｍ／１／∞／ｍ排队模型，其中
ｍ＝５λ＝１１５μ＝
１
１２
λ
μ
＝０．８
１）修理工空闲的概率；
Ｐ０ ＝
１
∑
ｍ
ｉ＝０
ｍ！
( )ｍ－ｉ！
λ( )μ
ｉ
≈０．００７３
２）５台机器都出故障的概率；
Ｐ５ ＝
ｍ！
ｍ－( )５！
λ( )μ
５
Ｐ０≈０．２８７
３）出故障的平均台数；
Ｌｓ＝ｍ－
μ
λ １－Ｐ
( )
０ ≈３．７６
４）等待修理的平均台数；
Ｌｑ ＝Ｌｓ－ １－Ｐ( )
０ ＝２．７７
５）平均停工时间；
Ｗｓ＝
Ｌｓ
μ１－Ｐ( )
０
＝ ｍ
μ１－Ｐ( )
０
－１
λ≈
４６( )ｍｉｎ
６）平均等待休息时间；
Ｗｑ ＝Ｗｓ－
１
μ
＝３４( )ｍｉｎ
—２２２—
７）评价上述结果。
机器停工时间过长（４６分钟），修理工几乎没有空闲时间（空闲概率０．００７３），应该提高服务率减
少修理时间或增加修理工人。
复习思路提示：
１）排队论考察以单服务台模型为主，其中又以标准的 Ｍ／Ｍ／１／∞／∞模型考察频率最高，必 牢
记该模型的系统运行指标和稳态概率的公式；
２）与存储论类似，考试时首先要准确判断问题属于哪一类排队系统，然后套用公式计算即可，但
要知晓关于各系统运行指标的不同表达方式；
３）存储论和排队论章节的考点更像考记忆力，而不是推理能力。建议按模型间联系找准记忆
窍门。
思考题［１０－１］　北京交通大学２０１２，六，计算题，１４分
某修理店只有一个修理工，来修理的顾客到达过程为ｐｏｉｓｓｏｎ流，平均４人／小时；修理时间服从负
指数分布，平均需要１０分钟。求：１）修理店忙的概率；２）店里恰有两个顾客的概率；３）店里有两个以
上顾客的概率；４）在店内的平均顾客数；５）每位顾客在店内的平均逗留时间；６）等待服务的平均顾客
数；７）每位顾客平均等待时间。
思考题［１０－２］　北京交通大学２０１０，六，计算题，１４分
某理发店只有一个理发员，来理发的顾客到达过程为ｐｏｉｓｓｏｎ流，平均５人／小时；理发时间服从负
指数分布，平均需要１０分钟；店内备有５把椅子供顾客等候，多余顾客将到其他理发店理发。求：１）
该理发店忙的概率；２）店里恰有两个顾客的概率；３）在店内的平均顾客数；４）每位顾客在店内的平均
逗留时间；５）等待服务的平均顾客数；６）每位顾客平均等待时间；７）顾客损失的概率。
经典试题讲解与本章小结
一、经典例题精讲
思考题［１０－１］　北京交通大学２０１２，六，计算题，１４分
某修理店只有一个修理工，来修理的顾客到达过程为ｐｏｉｓｓｏｎ流，平均４人／小时；修理时间服从负
指数分布，平均需要１０分钟。求：１）修理店忙的概率；２）店里恰有两个顾客的概率；３）店里有两个以
上顾客的概率；４）在店内的平均顾客数；５）每位顾客在店内的平均逗留时间；６）等待服务的平均顾客
数；７）每位顾客平均等待时间。
解：这属于Ｍ／Ｍ／１／∞／∞排队模型，其中
λ＝４人 ／( )小时 μ＝１１０
６０
＝６人 ／( )小时 ρ＝λμ
＝２３
１）修理店忙的概率
空闲的概率Ｐ０ ＝１－ρ＝１－
２
３ ＝
１
３忙的概率１－Ｐ０ ＝
２
３
２）店内恰有２个顾客的概率
Ｐ２ ＝ρ
２ １－( )ρ＝( )２３
２
１－( )２３ ＝４２７
—３２２—
《运筹学》考点精讲及复习思路
ＰＡ
－
Ｂ( )
－
＝０．８
画决策树
求期望值
【详见视频课程】
所以，根据ＥＭＶ准则对决策树计算，应在大量销售前先进行试销。在试销成功条件下进行大量
销售；在试销失败时，应取消销售计划。
二、本章小结
一、基本概念
１．决策问题的组成
决策者：决策的主体，一个人或团体；
决策：两个以上可供选择的行动方案，记为Ａｊ；
状态：决策实施后可能遇到的自然状况，记为Ｓｉ；
状态概率：对各状态发生可能性大小的主观估计，记为ＰＳ( )
ｉ ；
结局（损益）：当决策方案Ａｊ实施后遇到状态Ｓｉ时所产生的效益（利润）或损失（成本），记为ｕｉｊ。
２．决策问题的分类
确定型：状态只有一种；
不确定型：状态不只一种；又可分为完全不确定型（状态概率未知）和风险型（状态概率可知）。
二、不确定型决策
１．悲观法———小中取大原则
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍｉｎｉ ｕｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘｊ ｍｉｎｉ ｕｉｊ
基本步骤：
１）计算每个方案的评价值，即为每个方案在各自然状态下的最小收益值；
２）根据方案评价值选择最优方案，即从各最小收益值中求最大值。
２．乐观法———大中取大原则
—５４２—
《运筹学》考点精讲及复习思路
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｕｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘｊ ｍａｘｉ ｕｉｊ
基本步骤：
１）计算每个方案的评价值，即为每个方案在各自然状态下的最大收益值；
２）根据方案评价值，选择评价值最大的方案为最优方案。
３．最小后悔值法———大中取小原则
决策过程：在状态Ｓｉ下，选择方案Ａｊ的后悔值为ｒｉｊ＝ｍａｘｊ ｕｉｊ－ｕｉｊ
所有后悔值构成后悔值矩阵。
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｒｉｊ
ｍｉｎｆＡ( )
ｊ ＝ｍｉｎｊ ｍａｘｉ ｒｉｊ
基本步骤：
１）计算出后悔矩阵；
２）计算每一个方案评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｒｉｊ；
３）选择最小评价值ｍｉｎｆＡ( )
ｊ ，确定最优方案。
４．等可能性方法———平均原则
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝∑
ｍ
ｉ＝１
１
ｍａｉｊ＝
１
ｍ∑
ｍ
ｉ＝１
ａｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘ
１
ｍ∑
ｍ
ｉ＝１
ａ{ }ｉｊ
基本步骤：
１）计算每一个方案评价值；
２）选择最大评价值，确定最优方案。
５．乐观系数法———折衷原则
确定一个数字表示乐观程度，称为乐观系数。用α表示，并规定０≤α≤１。
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝α·ｍａｘｉ ｕｉｊ＋ １－( )αｍｉｎ
ｉ
ｕｉｊ
ｍａｘ
ｊ
ｆＡ( ){ }
ｊ
＝ｍａｘ
ｊ
α·ｍａｘ
ｉ
ｕｉｊ＋ １－( )αｍｉｎ
ｉ
ｕ{ }ｉｊ
基本步骤：
１）选择乐观系数为α，计算各方案评价值；
２）比较各方案的评价值ｍａｘｆＡ( ){ }
ｊ
，选择最优方案。
三、风险型决策
１．最大期望效益准则
思路步骤：
求期望效益值ＥＭＶ。期望效益值＝∑条件效益值×概率，
—６４２—
即ＥＭＶｉ＝∑
ｎ
ｊ＝１
ｐｊａｉｊ
选择最大期望效益值所对应的方案为决策方案
ＥＭＶ ＝ｍａｘ｛ＥＭＶｉ｝
２．贝叶斯决策准则及信息价值
贝叶斯决策（ＢａｙｅｓｉａｎＤｅｃｉｓｉｏｎＴｈｅｏｒｙ）就是在不完全情报下，对部分未知的状态用主观概率估
计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。
贝叶斯决策属于风险型决策，决策者虽不能控制客观因素的变化，但却掌握其变化的可能状况及
各状况的分布概率，并利用期望值即未来可能出现的平均状况作为决策准则。
贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：
１）已知类条件概率密度参数表达式和先验概率。
２）利用贝叶斯公式转换成后验概率。
３）根据后验概率大小进行决策分类。
３．决策树法
□：表示决策点，也称为树根，由它引发的分枝称之为方案分枝，方案节点被称为树枝．ｎ条分枝表
示有ｎ种供选方案。
：表示策略点，其上方数字表示该方案的最优收益期望值，由其引出的 ｍ条线称为概率枝表示
有ｍ种自然状态，其发生的概率已标明在分枝上。
△：表示每个方案在相应自然状态的效益值。
!
：表示经过比较选择此方案被删除掉了，称之为剪枝。
①根据题意作出决策树图；
②从右向左计算各方案期望值，并进行标注；
③对期望值进行比较，选出最大期望效益值，写在□上方，表明其所对应方案为决策方案，同时在
其它方案上打上
!
删除．
Ｅ（Ｈｉ）＝
ｎ
ｊ＝１
ｐｊＶｉｊ　　　　ｉ＝１，…，ｎ
—７４２—
《运筹学》考点精讲及复习思路