概要信息：

　目　　录　
第一章　线性规划与单纯形法 （１）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第二章　对偶问题与灵敏度分析 （２４）
!!!!!!!!!!!!!!!!!!!!!!!!!!
第三章　运输问题 （６２）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第四章　目标规划 （７９）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第五章　整数规划 （９０）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第六章　动态规划 （１０８）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第七章　图与网络优化 （１４０）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第八章　网络计划技术 （１７４）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第九章　存储论 （１９５）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第十章　排队论 （２１１）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第十一章　决策论 （２２７）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
第一章　线性规划与单纯形法
一、本章考情分析：
常考题型：选择、填空、简答、判断和计算
分值：必考知识点，分值占３０分以上
重要性：作为前五章的基础铺垫，非常重要！
重要程度：★★★★★
二、本章基本内容：
１）掌握线性规划的数学模型的标准型；
２）掌握线性规划的图解法及几何意义；
３）了解单纯形法原理；
４）熟练掌握单纯形法的求解步骤；
５）能运用大Ｍ法与两阶段法求解线性规划问题；
６）熟练掌握线性规划几种解的性质及判定定理．
三、本章重难点：
重点：
１）单纯形法求解线性规划问题；
２）解的性质；
３）线性规划问题建模．
难点：
１）单纯形法原理的理解；
２）线性规划问题建模．
四、本章要点精讲：
·要点１　化标准型
·要点２　图解法
·要点３　单纯形法的原理
·要点４　单纯形法的计算步骤
·要点５　单纯形法的进一步讨论
要点１　化标准型
线性规划的数学模型
—１—
《运筹学》考点精讲及复习思路
线性规划的共同特征
决策变量１：每个问题都用一组决策变量表示某个方案
决策变量２：决策变量的取值一般都是非负且连续的
约束条件３：与决策变量不矛盾的条件，用线性等式或不等式表示
目标函数４：决策变量与价值系数组成，一般要求实现最大或最小化
【建模思路】
确定决策变量
写出目标函数
找出约束条件
线性规划的标准型可简化为
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　ｉ＝１，２，…，ｍ
ｘｊ≥０　ｊ＝１，２，…，
{
ｎ
经典例题［１－１］　胡运权，运筹学教程（三）Ｐ１５，例３
与南京航空航天大学２００５年，第四题类似，１０分
ｍｉｎＺ＝ｘ１＋２ｘ２＋３ｘ３
ｓ．ｔ．
－２ｘ１＋ｘ２＋ｘ３≤９
－３ｘ１＋ｘ２＋２ｘ３≥４
４ｘ１－２ｘ２－３ｘ３ ＝－６
ｘ１≤０，ｘ２≥０，ｘ３







取值无约束
—２—
【１】目标函数最大
【２】资源限量（右端项）非负
【３】约束条件等式
松弛变量与剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为
价值和利润，所以引进模型后它们在目标函数中的系数均为零。
【４】决策变量非负
整理，得
ｍａｘＺ′＝ｘ１′－２ｘ２－３ｘ３′＋３ｘ３″＋０ｘ４＋０ｘ５
ｓ．ｔ．
２ｘ１′＋ｘ２＋ｘ３′－ｘ３″＋ｘ４ ＝９
３ｘ１′＋ｘ２＋２ｘ３′－２ｘ３″－ｘ５ ＝４
４ｘ１′＋２ｘ２＋３ｘ３′－３ｘ３″＝６
ｘ１′，ｘ２，ｘ３′，ｘ３″，ｘ４，ｘ５≥







０
　　　　　
目标函数最大
约束条件等式
决策变量非负
资源限量非负
经典例题［１－２］　天津大学２００４，二，（１），约５分
—３—
《运筹学》考点精讲及复习思路
某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规
模的广告行动．表１给出了公司准备做广告的三种产品名称、估计每做一单位广告使每种产品的市
场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的
单价．
现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量分别为
１．请写出此问题的线性规划模型，并将模型化为标准型．
其中洗衣粉的市场份额出现负值是由液体洗涤剂的份额增加造成的．
电视 印刷媒体 广告后市场份额最低增量
去污剂 ０％ １％ ３％
液体洗涤剂 ３％ ２％ １８％
洗衣粉 －１％ ４％ ４％
广告单位成本（万元） １００ ２００
解：设电视的广告数量为ｘ１，印刷媒体的广告数量为ｘ２
ｍｉｎＺ＝１００ｘ１＋２００ｘ２
ｓ．ｔ．
ｘ２≥３
３ｘ１＋１２ｘ２≥１８
－ｘ１＋４ｘ２≥４
ｘ１，ｘ２≥







０
化为标准型后
ｍａｘＺ′＝－１００ｘ１－２００ｘ２＋０ｘ３＋０ｘ４＋０ｘ５
ｓ．ｔ．
ｘ２－ｘ３ ＝３
３ｘ１＋１２ｘ２－ｘ４ ＝１８
－ｘ１＋４ｘ２－ｘ５ ＝４
ｘ１，ｘ２，ｘ３，ｘ４，ｘ５≥







０
复习思路提示：
·初学时，化标准型可按“目标函数—资源限量—约束条件—决策变量”的顺序进行，化完后默念
四句口诀验证；
·化标准型是用单纯形法求解线性规划问题的第一步，非常重要！而单纯形法求解线性规划问
题是每年必考大题，此步错，后面展开步步错！
要点２　图解法
图解法求解步骤：
—４—
经典例题［１－３］　胡运权，运筹学教程（三）Ｐ１６，例１
ｍａｘＺ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
【详见课程视频】
图解法的几点启示：
线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；
若线性规划的可行域存在，则可行域一定是个凸集；
若线性规划的最优解存在，则最优解或最优解之一（无穷多解时）一定是可行域的凸集的某个
顶点；
解题思路：找出凸集的顶点，计算其目标函数值，比较即得。
图解法启示的解题思路
经典例题［１－４］　天津大学２００６，一、选择（１），２分
用图解法解线性规划时，以下几种情况不可能出现的是（　　）
Ａ．可行域有界，无有限最优解（或称无界解）　　　　Ｂ．可行域无界，有唯一最优解
Ｃ．可行域是空集，无可行解 Ｄ．可行域有界，有多重最优解
复习思路提示：
·要会用图解法来分析线性规划的几种解的情况，如唯一最优解、无穷多解、无界解和无可行解；
—５—
《运筹学》考点精讲及复习思路
·图解法容易在确定可行域的范围和等值线移动方向上犯错；
·图解法的知识点通常出现在选择、填空、判断等小题型中！大致分值在１０分以内．
思考题［１－１］　（留待以后课程讲解）
南京航空航天大学２００４，一、多项选择２、３，各５分
２．线性规划的最优解可在（　　）
Ａ．可行集内 Ｂ．可行集边界上
Ｃ．可行集顶点上 Ｄ．满足其约束条件的区域上
３．线性规划的可行集可以（　　）
Ａ．不含有任何可行解 Ｂ．恰含有一个可行解
Ｃ．恰含有两个可行解 Ｄ．含有无数个可行解
思考题［１－２］　（留待以后课程讲解）
南京航空航天大学２００６，第二题，１０分
二、（１０分）用图解法求解线性规划问题．
ｍａｘｚ＝４０ｘ１＋８０ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤３０
３ｘ１＋２ｘ２≤６０
２ｘ２≤２４
ｘ１，ｘ２≥







０
要点３　单纯形法原理
·解的概念与关系
·单纯形法迭代原理
［１］解的概念与关系
线性规划的标准型为
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ
ｘｊ≥０　　ｊ＝１，２，…，
{
ｎ
【向量形式】
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ　　ｉ＝１，２，…，ｍ
ｘｊ≥０　　ｊ＝１，２，…，
{
ｎ
—６—
【矩阵形式】
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
ＡＸ＝ｂ
Ｘ≥{ ０
线性规划问题解的概念
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ （１）
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ　　　　（２）
ｘｊ≥０　　　ｊ＝１，２，…，ｎ　　　　　　（３
{
）
可行解：满足约束条件（２）和（３）的解Ｘ＝（ｘ１，…，ｘｎ）
Ｔ全部可行解的集合称为可行域。
最优解：使目标函数（１）达到最大值的可行解。
基：设Ａ是约束方程组（２）的ｍ×ｎ阶系数矩阵（设ｎ＞ｍ），其秩为ｍ，Ｂ是Ａ中的一个ｍ×ｍ阶
的满秩子矩阵（Ｂ≠０的非奇异子矩阵），称Ｂ是线性规划问题的一个基．不失一般性，设
除基变量以外的变量称为非基变量
基解：在约束方程组（２）中，令所有的非基变量ｘｍ＋１＝ｘｍ＋２＝… ＝ｘｎ＝０，又因为 Ｂ≠０，据克
莱姆法则，对于
ａ１１ｘ１＋ａ１２ｘ２＋… ＋ａ１ｍｘｍ ＝ｂ１
ａ２１ｘ１＋ａ２２ｘ２＋… ＋ａ２ｍｘｍ ＝ｂ２
…
ａｍ１ｘ１＋ａｍ２ｘ２＋… ＋ａｍｍｘｍ ＝ｂ







ｍ
　　　Ｘ＝ ｘ１，ｘ２，…，ｘｍ，０，０，…，( )０Ｔ－基解
可以求出唯一解ＸＢ ＝ ｘ１，ｘ２，…，ｘ( )
ｍ
Ｔ
ｍａｘＺ＝∑
ｎ
ｉ＝１
ｃｊｘｊ　　　　　　　　　　　（１）
ｓ．ｔ．
∑
ｎ
ｊ＝１
ａｉｊｘｊ＝ｂｉ　　ｉ＝１，２，…，ｍ　　（２）
ｘｊ≥０　　ｊ＝１，２，…，ｎ　　　　　（３
{
）
基可行解：满足变量非负约束条件（３）的基解．
可行基：对应基可行解的基．
经典例题［１－５］　胡运权，运筹学教程（三）Ｐ１９，例４
找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解．
—７—
《运筹学》考点精讲及复习思路
ｍａｘＺ＝２ｘ１＋３ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ３ ＝５
ｘ１＋２ｘ２＋ｘ４ ＝１０
ｘ２＋ｘ５ ＝４
ｘｊ≥０，ｊ＝１，２，…，







５
　　Ａ＝
１ ０ １ ０ ０
１ ２ ０ １ ０







０ １ ０ ０ １
【详见课程视频】
凸集、顶点及几个定理
设Ｋ是ｎ维欧氏空间的一点集，若Ｘ（１）∈Ｋ，Ｘ（２）∈Ｋ的连线上的所有点αＸ（１）＋（１－α）Ｘ（２）∈
Ｋ，０≤α≤１），则称Ｋ为凸集．
设Ｋ是凸集，Ｘ∈Ｋ；若Ｘ不能用不同的两点Ｘ（１）∈Ｋ和Ｘ（２）∈Ｋ的线性组合表示为Ｘ＝αＸ（１）
＋（１－α）Ｘ（２），（０＜α＜１）则称Ｘ为Ｋ的一个顶点（或极点）．
定理１　若线性规划问题存在可行解，则问题的可行域是凸集．（天津大学２００６年第三题证明，６
分）
引理　线性规划问题的可行解为基可行解的充要条件是Ｘ的正分量所对应的系数列向量是线性
独立的．
定理２　线性规划问题的基可行解Ｘ对应线性规划问题可行域（凸集）的顶点．
定理３　若线性规划问题有最优解，一定存在一个基可行解是最优解．
几个定理考察的通常是小题型，需要牢记结论，且理解各个解之间的关系。
几点结论：
【１】可行域若有界则是凸集，也可能是无界域；
【２】每个基可行解对应可行域的一个顶点；
【３】可行域有有限多个顶点；
【４】如果有最优解，必在某个顶点上得到．
线性规划解之间的关系归纳
“箭尾的解一定是箭头的解，反之不一定成立．”
当最优解唯一时，最优解也是基最优解；
当最优解不唯一时，最优解不一定是基最优解．
经典例题［１－６］　南京航空航天大学，２０１１，一、判断（１），３分
一、判断下列说法是否正确．
—８—
１）若线性规划问题的可行解为最优解，则该可行解必定是基可行解．（　　）
经典例题［１－７］　北京交通大学，２０１０，一、判断（１），２分
一、判断下列说法是否正确．
１）线性规划问题的每一个基解对应可行域的一个顶点．（　　）
单纯形法的迭代思路：
［２］单纯形法的迭代原理
ｍａｘＺ＝ＣＸ
ｓ．ｔ．
∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ
ｘｊ≥０　　ｊ＝１，２，…
{
ｎ
【１】构造初始可行基
Ｂ＝ Ｐ１，Ｐ２，…，Ｐ( )
ｍ ＝
１ ０ … ０
０ １ … ０
  
０ ０ …











１
·直接观察一个可行基 Ｂ≠０
·≤约束，加松弛变量；
·≥约束，加人工变量（后面会讨论）
（为讨论方便，设均为≤约束）
【２】基变换：两个基可行解相邻，两者可变换且仅变换一个基变量
—９—
《运筹学》考点精讲及复习思路
设初始基可行解为：
写出系数矩阵的增广矩阵：
可得Ｐｊ＝∑
ｍ
ｉ＝１
ａｉｊＰｉ
［移项得
→
］
Ｐｊ－∑
ｍ
ｉ＝１
ａｉｊＰｉ＝０
上式乘以一个正数θ＞０，得
θＰｊ－∑
ｍ
ｉ＝１
ａｉｊＰ( )ｉ ＝０
　　　　 ＋
∑
ｍ
ｉ＝１
Ｐｉｘｉ
０







＝ｂ
∑
ｍ
ｉ＝１
ｘ０ｉ－θａ( )
ｉｊＰｉ＋θＰｊ＝ｂ
由∑
ｍ
ｉ＝１
ｘ０ｉ－θａ( )
ｉｊＰｉ＋θＰｊ＝ｂ
可找到满足原约束方程组∑
ｎ
ｉ＝１
Ｐｊｘｊ＝ｂ的另一个点：
Ｘ( )１ ＝ ｘ０１－θａ１ｊ，…，ｘ
０
ｍ －θａｍｊ，０，…，θ，…，( )０Ｔ
要使Ｘ( )１ 是一个基可行解，则应对所有ｉ＝１，２，…，ｍ存在ｘ０ｉ－θａｉｊ≥０（先要使其可行）
令这ｍ个不等式至少有一个等号成立，且当ａｉｊ≤０时，上式显然成立，故可令
θ＝ｍｉｎ
ｉ
ｘ０ｉ
ａｉｊ
ａｉｊ＞{ }０ ＝ｘ
０
ｌ
ａｌｊ
可确保ｘ０ｉ－θａｉｊ
＝０，ｉ＝ｌ
≥０，ｉ≠{ ｌ
是可行解。
此时与ｘ１
１，…，ｘ１ｌ－１，ｘ
１
ｌ＋１，…，ｘ
１
ｍ，ｘ
１
ｊ对应的向量：
—０１—
【３】最优性检验和解的判别
将上述Ｘ（０），Ｘ（１）分别代入目标函数ｚ＝∑
ｎ
ｊ＝１
ｃｊｘｊ，得
ｚ( )０ ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０
ｚ( )１ ＝∑
ｍ
ｉ＝１
ｃｉ ｘｉ
０－θａ( )
ｉｊ ＋θｃｊ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ ＝ｚ
( )０ ＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ
ｚ( )０ ＝∑
ｍ
ｉ＝１
ｃｉｘｉ
０　　ｚ( )１ ＝ｚ( )０ ＋θｃｊ－∑
ｍ
ｉ＝１
ｃｉａ( )ｉｊ
（１）当所有σｊ≤０，当前顶点（基可行解）的目标函数值已是最大，即为最优解；
（２）当所有σｊ≤０，又某个非基变量ｘｊ的检验数为０，则在另一个顶点也使目标函数达到最大，两
点连线上的所有点都是最优解，即无穷多最优解．当所有非基变量的σｊ＜０时，有唯一最优解；
（３）若存在某个σｊ＞０，而其对应的非基向量Ｐｊ≤０，则从θ值和ｚ
（１）的表达式可看出，线性规划
有无界解．
ｘ０ｉ－θａｉｊ≥０
线性规划解的判别定理归纳：
最优解判别定理
若Ｘ（０） ＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ≤０，ｊ＝ｍ＋１，…，ｎ，则Ｘ
（０）为最优解．
唯一最优解判别定理
若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ＜０，ｊ＝ｍ＋１，…，ｎ，则Ｘ
（０）为唯一最优解．
无穷多最优解判别定理
若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）
Ｔ为基可行解，且全部σｊ≤０，ｊ＝ｍ＋１，…，ｎ，且存在一个非基
—１１—
《运筹学》考点精讲及复习思路
变量ｘｍ＋ｋ的σｍ＋ｋ ＝０，则存在无穷多最优解．
无界解判别定理
若有一个非基变量ｘｍ＋ｋ的σｍ＋ｋ ＞０，而其对应非基变量的所有系数ａ′ｉ，ｍ＋ｋ≤０，ｉ＝１，２，…，ｍ，则
具有无界解。
复习思路提示：
·掌握线性规划几个解的概念及几何意义，会用该知识点求解考研试题中的各类小题型；
·会在简答题中对单纯形法的迭代思路进行描述；
·了解单纯形法的迭代原理，牢记解的判别定理．
思考题［１－３］　（留待以后课程讲解）
中山大学２０１２，一、选择（３）１分
在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系数
列向量（　　）时，则此问题是无界的。
Ａ．≥０　　　　　　　Ｂ．＜０　　　　　　　Ｃ．＝０　　　　　　　Ｄ．≤０
北京交通大学２０１０，一、判断（２）２分
单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。
１）写出该线性规划的标准型（１０分）；
２）求原规划的最优解和最优目标函数值（１５）．
要点４　单纯形法的计算步骤
为书写规范和便于计算，对单纯形法的计算设计了单纯形表。
每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯
形表称为最终单纯形表。
本节介绍用单纯形表计算线性规划问题的步骤。
【１】求初始基可行解，列出初始单纯形表
ｃｊ→ ｃ１ … ｃｍ … ｃｊ … ｃｎ
ＣＢ ＸＢ ｂ ｘ１ … ｘｍ … ｘｊ … ｘｎ
ｃ１ ｘ１ ｂ１ １ … ０ … ａ１ｊ … ａ１ｎ
ｃ２ ｘ２ ｂ２ ０ ０ ａ２ｊ ａ２ｎ
      
ｃｍ ｘｍ ｂｍ ０ … １ … ａｍｊ … ａｍｎ
ｃｊ－ｚｊ ０ … ０ … ｃｊ－∑
ｍ
ｉ＝１
ｃｉａｉｊ … ｃｎ－∑
ｍ
ｉ＝１
ｃｉａｉｎ
—２１—
【２】最优性检验
【３】基变换
１）确定换入基的变量
只要有检验数大于０，对应的变量就可作为换入变量，当有一个以上检验数大于０时，一般从中选
取最大的一个：σｋ ＝ｍａｘｊ σｊ｜σｊ＞{ }０
其对应的变量ｘｋ作为换入变量。
２）确定换出基的变量
根据确定θ最小比值规则，对Ｐｋ列计算可得：θ＝ｍｉｎ
ｂｉ
ａｉｋ
ａｉｋ ＞{ }０ ＝ｂｌａｌｋ
其对应的变量ｘｌ作为换出变量。元素ａｌｋ决定了从一个基可行解到相邻基可行解的转移去向，称
之为主元素。
３）迭代变换
用换入变量ｘｋ去替换基变量中的换出变量 ｘｌ，得到一个新的基 （Ｐ１，…，Ｐｌ－１，Ｐｋ，Ｐｌ＋１，…，Ｐｍ）。
对应这个基可以找出一个新的基可行解，并相应地可以画出一张新的单纯形表。
【详见课程视频】
经典例题［１－８］　南航，２０１２，二、计算题，１．（１）１０分
二、１．（２０分）已知线性规划问题：
ｍａｘｚ＝８ｘ１＋６ｘ２
—３１—
《运筹学》考点精讲及复习思路
ｓ．ｔ．
ｘ１＋ｘ２≤８
２ｘ１＋ｘ２≤１０
ｘ１≤４
ｘ１，ｘ２≥







０
１）用单纯形法求解；
【详见课程视频】
在上面的例题［１－８］中，考虑以下两个问题：
１）若初始单纯形表中，若用检验数６对应的ｘ２作为换入变量会带来什么样的结果？
２）用图解法求解该题，看每张单纯形表对应的解与可行域中的顶点如何对应？基变换是否是相
邻的顶点间进行变换？最优解在哪个顶点取得？
复习思路提示：
·正确的标准型是单纯形法求解线性规划问题的前提；
·会依据标准型列出初始单纯形表（重点是正确找出初始基及对应的初始基变量）；
·熟练运用矩阵的初等行变换进行单纯形表迭代（最容易犯计算错误）；
·牢记最优性检验的几个解的判别定理（当遇到无穷多最优解和无界解的情况）。
思考题［１－４］　（留待以后课程讲解）
中山大学２０１２，三，１１分
用单纯形表求解以下线性规划问题：
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３≤１２
２ｘ１＋ｘ２－ｘ３≤６
－ｘ１＋３ｘ２≤９
ｘ１≥０，ｘ２≥０，ｘ３≥







０
要点５　单纯形法的进一步讨论
考虑：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可
行基？
ＭａｘＺ＝ｃ１ｘ１＋ｃ２ｘ２＋… ＋ｃｎｘｎ
—４１—
ｓ．ｔ．
ａ１１ｘ１＋ａ１２ｘ２＋… ＋ａ１ｎｘｎ ＝ｂ１
ａ２１ｘ１＋ａ２２ｘ２＋… ＋ａ２ｎｘｎ ＝ｂ２
…………………
ａｍ１ｘ１＋ａｍ２ｘ２＋… ＋ａｍｎｘｎ ＝ｂｍ
ｘ１，ｘ２，…，ｘｎ≥









０
线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，添加人工变量！
“惩罚”人工变量！———大Ｍ法和两阶段法
【１】大Ｍ法
人工变量在目标函数中的系数为－Ｍ，其中Ｍ为任意大的正数。
经典例题［１－９］　清华大学运筹学编写组（三）Ｐ３３例８
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３≤１１
－４ｘ１＋ｘ２＋２ｘ３≥３
－２ｘ１＋ｘ３ ＝１
ｘ１，ｘ２，ｘ３≥







０
—５１—
《运筹学》考点精讲及复习思路
解：１）首先化标准型，
２）添加人工变量，构造初始可行基
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３＋０ｘ４＋０ｘ５－Ｍｘ６－Ｍｘ７
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３＋ｘ４ ＝１１
－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６ ＝３
－２ｘ１＋ｘ３＋ｘ７ ＝１
ｘｊ≥０，ｊ＝１，２，…，







７
其中，Ｍ为任意大的正数。
求解结果出现所有检验数非正σｊ≤０，若基变量中含非零的人工变量，则无可行解；否则，有最优
解。
３）列初始单纯形表如下
第一步迭代，得表２
第二步迭代，得表３
—６１—
第三步迭代得最终表（所有检验数小于等于０）
【２】两阶段法
第一阶段：加入人工变量后，构造仅含人工变量的目标函数，并要求其实现最小化；
第二阶段：将一阶段得到的最终表除去人工变量。将目标函数行的系数换成原问题的目标函数
系数，作为二阶段的初始表。
同上例：
Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３≤１１
－４ｘ１＋ｘ２＋２ｘ３≥３
－２ｘ１＋ｘ３ ＝１
ｘ１，ｘ２，ｘ３≥







０
解：１）添加人工变量，给出一阶段的数学模型
ｍｉｎω＝ｘ６＋ｘ７
ｓ．ｔ．
ｘ１－２ｘ２＋ｘ３＋ｘ４ ＝１１
－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６ ＝３
－２ｘ１＋ｘ３＋ｘ７ ＝１
ｘｊ≥０，ｊ＝１，２，…，







７
—７１—
《运筹学》考点精讲及复习思路
Ｘ ＝ ０，１，１，１２，( )０Ｔ是原线性规划问题的基可行解。
２）将一阶段最终表中的人工变量取消填入原问题的目标函数的系数，进行第二阶段计算。
单纯形法中的几个问题：
退化
基可行解中存在基变量等于０的解（退化解），迭代后目标函数值不变，即不同的基表示为同一个
顶点。
勃兰特（ｂｌａｎｄ）规则：
１）当遇到相同检验数时，选取对应下标最小的非基变量作为换入变量；
２）当存在两个及以上相同的最小比值时，选取下标最小的基变量作为换出变量。
检验数的几种判别形式
—８１—
复习思路提示：
·人工变量是人为加入的，与决策变量、松弛变量有本质的区别，若线性规划有最优解，人工变
量必为０，以保持原约束条件不变。为了使人工变量为０，就要使人工变量从基变量中换出成非基
变量；
·大Ｍ法和两阶段法通常不会直接出成计算大题，会在一些小题型中考察这两种方法的注意事
项。大致分值１０分以内。
思考题［１－５］
１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 。【北京科技大学】
２．简述大Ｍ法的算法步骤。【南京航空航天大学】
经典试题讲解与本章小结
一、经典试题讲解
思考题［１－１］
２．线性规划的最优解可在（　　）。【南京航空航天大学】
Ａ．可行集内 Ｂ．可行集边界上
Ｃ．可行集顶点上 Ｄ．满足其约束条件的区域上
３．线性规划的可行集可以（　　）。【南京航空航天大学】
Ａ．不含有任何可行解 Ｂ．恰含有一个可行解
Ｃ．恰含有两个可行解 Ｄ．含有无数个可行解
４．线性规划问题的每一个基解对应可行域的一个顶点。【北京交通大学，判断】
５．下面命题正确的是（　　）【昆明理工大学，单选】
Ａ．线性规划的最优解是基可行解 Ｂ．基可行解不一定是基本解
Ｃ．线性规划一定有可行解 Ｄ．线性规划的最优值至多有一个
思考题［１－２］
１．（１０分）用图解法求解线性规划问题。【南京航空航天大学】
ｍａｘｚ＝４０ｘ１＋８０ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤３０
３ｘ１＋２ｘ２≤６０
２ｘ２≤２４
ｘ１，ｘ２≥







０
２．若线性规划的可行解为最优解，则该可行解必定是基可行解。【南京航天航空大学，判断】
３．若Ｘ１，Ｘ２分别是某一线性规划问题的最优解，则Ｘ＝λ１Ｘ１＋λ２Ｘ２也是该线性规划问题的最优
解，其中λ１，λ２为正实数。【南京航天航空大学，判断】
—９１—
《运筹学》考点精讲及复习思路
思考题［１－３］
１．在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系
数列向量（　　）时，则此问题是无界的。【中山大学】
Ａ．≥０ Ｂ．＜０ Ｃ．＝０ Ｄ．≤０
２．单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。【北京交通大学判断】
分析：
ｘ１ ＝ｂ１′－ａ′１ｍ＋ｋｘｍ＋ｋ
ｘ２ ＝ｂ２′－ａ′２ｍ＋ｋｘｍ＋ｋ
………………
ｘｍ ＝ｂｍ′－ａ′ｍｍ＋ｋｘ







ｍ＋ｋ
≥０
∵ａ′ｉｍ＋ｋ≤０，对任意ｘｍ＋ｋ ＞０，即解都可行，
Ｚ＝Ｚ０＋（ｃｊ－ｚｊ）ｘｍ＋ｋ ＝Ｚ０＋σｍ＋ｋｘｍ＋ｋ
∴当ｘｍ＋ｋ→＋!
，Ｚ→＋!
．
思考题［１－４］
１．用单纯形表求解以下线性规划问题：【中山大学】
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３≤１２
２ｘ１＋ｘ２－ｘ３≤６
－ｘ１＋３ｘ２≤９
ｘ１≥０，ｘ２≥０，ｘ３≥







０
解：化标准型，并列出初始单纯形表
ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３＋０ｘ４＋０ｘ５＋０ｘ６
ｓ．ｔ．
ｘ１＋ｘ２＋ｘ３＋ｘ４ ＝１２
２ｘ１＋ｘ２－ｘ３＋ｘ５ ＝６
－ｘ１＋３ｘ２＋ｘ６ ＝９
ｘｊ≥０，ｊ＝１，２，…，







６
—０２—
迭代得表２
迭代得最终表
Ｘ ＝ ６，０，６，０，０，( )１５Ｔ　　ｚ ＝１２
思考题［１－５］
１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 【北京科技大学】
２．简述大Ｍ法的算法步骤。【南京航空航天大学】
二、本章小结
【１】标准型
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ＝ｂ
Ｘ≥{ ０
　　
目标函数最大
约束条件等式
资源限量非负
决策变量非负
【２】图解法
—１２—
《运筹学》考点精讲及复习思路
可行域若有界则是凸集，也可能是无界域；
每个基可行解对应可行域的一个顶点；
可行域有有限多个顶点；
如果有最优解，必在某个顶点上得到．
……
【３】线性规划解之间的关系归纳
“箭尾的解一定是箭头的解，反之不一定成立．”
·当最优解唯一时，最优解也是基最优解；
·当最优解不唯一时，最优解不一定是基最优解．
进行标准化，列初始单纯形表方法
【４】单纯形法计算步骤框图
—２２—
【５】人工变量法———大Ｍ法
【６】人工变量法———两阶段法
一阶段目标函数最优值为０，则去掉人工变量转入第二阶段；不为０，则原问题无可行解，停止
计算。
本章涉及的知识点大部分是每年的必考题，分值约占２０％，其中解的性质及判定通常会出现在填
空、选择或简答、判断等小题型中，而单纯形法求解是每年必考的一道大题，常与第二章对偶问题联合
出题，涉及分值有时高达５０分以上。
—３２—
《运筹学》考点精讲及复习思路
第二章　对偶问题与灵敏度分析
一、本章考情分析：
常考题型：选择、填空、简答、判断和计算
分值：必考知识点，分值在２０－２５分之间
重要性：每年必考，影子价格及灵敏度分析实际应用很多
重要程度：★★★★★
二、本章基本内容：
１）熟练掌握原问题与对偶问题的转化关系（记忆转化关系表或用对称形式推导）；
２）熟练掌握单纯形法的矩阵描述；
３）掌握对偶问题的几条基本性质；
４）熟练掌握影子价格的经济意义；
５）能运用对偶单纯形法求解线性规划问题；
６）熟练掌握灵敏度分析，包括ａ，ｂ，ｃ和增加约束条件的变化。
三、本章重难点：
重点：
１）根据原问题写出对偶问题；
２）能通过单纯形法的矩阵描述，从单纯形表求原问题和对偶问题的最优解；
３）灵敏度分析中，分析各系数在什么范围内变化，最优解不变，或各系数变化后，最优解是否
改变。
难点：
对偶问题的性质的理解。
四、本章要点精讲：
·要点１　线性规划的对偶问题
·要点２　单纯形法的矩阵描述
·要点３　线性规划的对偶理论
·要点４　影子价格
·要点５　对偶单纯形法
·要点６　灵敏度分析
—４２—
要点１　线性规划的对偶问题
·对偶问题的提出
·原问题与对偶问题的数学模型
·原问题与对偶问题的对应关系
对偶问题的提出
经典例题［２－１］　胡运权主编《运筹学教程》第三版，Ｐ４８，例１
美佳公司利用现有资源生产两种产品，有关数据如下
产品Ⅰ 产品Ⅱ 资源限量
设备Ａ
设备Ｂ
调试工序
０
６
１
５
２
１
１５时
２４时
５时
利润（元） ２ １
美佳公司考虑：如何安排生产，使获利最多？
设：Ⅰ产量———ｘ１；Ⅱ产量———ｘ２
ｍａｘｚ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
收购方：收购美佳公司的资源，付出多少代价才能使美佳公司愿意放弃生产活动出让自己的资源呢？
美佳公司：出让代价应不低于同等数量的资源自己生产的利润。
设：设备Ａ———ｙ１元／时
设备Ｂ———ｙ２元／时
调试工序———ｙ３元／时
　
建立如下线性规划问题：
—５２—
《运筹学》考点精讲及复习思路
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３
ｓ．ｔ．
６ｙ２＋ｙ３≥２
５ｙ１＋２ｙ２＋ｙ３≥１
ｙ１，ｙ２，ｙ３≥
{
０
　　　　
ｍａｘｚ＝２ｘ１＋ｘ２
ｓ．ｔ．
５ｘ２≤１５
６ｘ１＋２ｘ２≤２４
ｘ１＋ｘ２≤５
ｘ１，ｘ２≥







０
特点：
１．ｍａｘｍｉｎ
２．限定向量ｂ价值向量（资源向量）Ｃ
３．一个约束一个变量
４．ｍａｘｚ的ＬＰ约束“≤”的ＬＰ是“≥”的约束。
５．变量都是非负限制。
原问题与对偶问题的数学模型
【１】对称形式的对偶
原问题和对偶问题只含有不等式约束。
情形一：
情形二：
将原问题化成标准对称型
—６２—

ｍａｘｚ＝ＣＸ
ｓ．ｔ－ＡＸ≤－ｂ
Ｘ≥
{
０
根据标准对称型写出对偶

ｍｉｎｗ＝－Ｙ′ｂ
ｓ．ｔ　 －Ｙ′Ａ≥Ｃ
Ｙ′≥
{
０
　　
　Ｙ＝－Ｙ′
→
　
　　
ｍｉｎｗ＝Ｙｂ
ｓ．ｔ　ＹＡ≥Ｃ
Ｙ≤
{
０
【２】非对称形式的对偶
原问题的约束是等式
推导过程
原问题
　
ｍａｘｚ＝ＣＸ
ＡＸ≥ｂ
ＡＸ≤ｂ
Ｘ≥







０
　　
ｍａｘｚ＝ＣＸ
Ａ[ ]
－Ａ
Ｘ≤
ｂ[ ]
－ｂ
Ｘ≥







０
ｍｉｎｗ＝（Ｙ１，Ｙ２）·
ｂ[ ]
－ｂ
ｓ．ｔ．
（Ｙ１，Ｙ２）·
Ａ[ ]
－Ａ
≥Ｃ
Ｙ１≥０，Ｙ２≥
{
０

ｍｉｎｗ＝（Ｙ１－Ｙ２）·ｂ
（Ｙ１－Ｙ２）·Ａ≥Ｃ
Ｙ１≥０，Ｙ２≥
{
０
令Ｙ＝Ｙ１－Ｙ２，得对偶问题为：

ｍｉｎｗ＝Ｙｂ
ＹＡ≥Ｃ
Ｙ
{
无约束
证毕。
—７２—
《运筹学》考点精讲及复习思路
原问题和对偶问题的对应关系
经典例题［２－２］　北京交通大学２００９，一、５０分
已知线性规划问题如下：
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
１．求该问题的最优解；
２．写出该线性规划问题的对偶问题，并求对偶问题的最优解；
３．分别确定ｘ２，ｘ３的目标函数系数ｃ２，ｃ３在什么范围内变化最优解不变？
４．求约束条件右端值由 ( )３９ 变为
２( )１５ 时的最优解；
５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３≤５时的最优解。
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
　　

　　
ｍａｘω＝３ｙ１＋９ｙ２
ｓ．ｔ．
ｙ１≤２
２ｙ１＋ｙ２≤５
１
２ｙ１＋３ｙ２≤
１
２
ｙ１，ｙ２≥







０
复习思路提示：
·一定要掌握根据线性规划原问题写对偶问题，建议先根据原约束条件的个数确定对偶问题变
量数，再写出对偶问题的目标函数和约束条件（留待最后判别约束条件和变量的符号）；
·写对偶问题方式一是通过标准对称形式进行推导，方式二则可通过记忆对应关系表来直接
写出。
—８２—
·一定要记住数学题多是按步骤给分的，能写多少是多少。
思考题［２－１］　（留待以后课程讲解）
北京科技大学２０１１，三，１８分
对于线性规划问题：
ｍａｘＳ＝１０ｘ１＋５ｘ２
ｓ．ｔ．
３ｘ１＋４ｘ２≤９
５ｘ１＋２ｘ２≤８
ｘ１≥０，ｘ２≥
{
０
１．用单纯形法求解最优解，最优值；
２．写出最优基，最优基的逆阵；
３．写出对偶规划，对偶规划的最优解。
要点２　单纯形法的矩阵描述
·单纯形法的矩阵描述
·单纯形法计算的矩阵描述
单纯形法的矩阵描述
设线性规划问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ
ＡＸ＝ｂ
Ｘ≥{ ０
不妨设基为
Ｂ＝ Ｐ１ Ｐ２ … Ｐ( )ｍ
则Ａ＝（Ｐ１ Ｐ２ … Ｐｎ）＝（Ｂ  Ｎ）
约束方程组
ＡＸ＝ｂ（Ｂ Ｎ）
ＸＢ
Ｘ





Ｎ
＝ＢＸＢ＋ＮＸＮ ＝ｂ
ＸＢ ＝Ｂ
－１（ｂ－ＮＸＮ）＝Ｂ
－１ｂ－Ｂ－１ＮＸＮ
令ＸＮ ＝０得
目标函数
—９２—
《运筹学》考点精讲及复习思路
令ＸＮ ＝０得
检验数
线性规划问题可以等价写成：
此形式为线性规划对应于基Ｂ的典则形式（典式）。
矩阵描述时的常用公式
ＸＢ ＝Ｂ
－１ｂ
Ｎ＝Ｂ－１Ｎ
σＮ ＝ＣＮ －ＣＢＢ
－１Ｎ
ｚ０ ＝ＣＢＢ
－１







ｂ
当已知一个线性规划的可行基 Ｂ时，先求出 Ｂ－１，再用这些运算公式可得到单纯形法所要求的
结果。
单纯形法计算的矩阵描述
线性规划问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
化为标准型，引入松弛变量Ｘｓ
—０３—
ｍａｘｚ＝ＣＸ＋０Ｘｓ
ｓ．ｔ．
ＡＸ＋ＩＸｓ＝ｂ
Ｘ≥０，Ｘｓ≥
{ ０
标准型
ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ ＋０ＸＳ
ｓ．ｔ．
ＢＸＢ＋ＮＸＮ ＋ＩＸＳ ＝ｂ
ＸＢ，ＸＮ，ＸＳ≥
{ ０
　列初始单纯形表
→
　
初始单纯形表
ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ ＋０ＸＳ
ｓ．ｔ．
ＢＸＢ＋ＮＸＮ ＋ＩＸＳ ＝ｂ
ＸＢ，ＸＮ，ＸＳ≥
{ ０
初始单纯形表：
迭代后单纯形表
—１３—
《运筹学》考点精讲及复习思路
检验数应都小于等于０，即
ＣＮ －ＣＢＢ
－１Ｎ≤０
－ＣＢＢ
－１≤０
又因为基变量的检验数可写成ＣＢ－ＣＢ·Ｉ＝０
则可将检验数统一写为
Ｃ－ＣＢＢ
－１Ａ≤０
－ＣＢＢ
－１≤０
　
　令Ｙ＝ＣＢＢ
－１
→
　
　
Ｃ－ＹＡ≤０
－Ｙ≤０
　　
ＹＡ≥Ｃ
Ｙ≥{ ０
ｚ＝ＣＢＢ
－１ｂ＝Ｙｂ　　
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
从上述推导可看出，检验数行的相反数恰好是其对偶问题的一个可行解。
经典例题［２－３］　胡运权主编《运筹学教程》第三版，Ｐ５４，例３
两个互为对偶的线性规划问题，分别再加上了松弛变量和剩余变量后：
ｍａｘｚ＝２ｘ１＋ｘ２＋０ｘ３＋０ｘ４＋０ｘ５
ｓ．ｔ．
５ｘ２＋ｘ３ ＝１５
６ｘ１＋２ｘ２＋ｘ４ ＝２４
ｘ１＋ｘ２＋ｘ５ ＝５
ｘｊ≥０，ｊ＝１，２，３，４，







５
　　　　　
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３＋０ｙ４＋０ｙ５
ｓ．ｔ．
６ｙ２＋ｙ３－ｙ４ ＝２
５ｙ１＋２ｙ２＋ｙ３－ｙ５ ＝１
ｙｉ≥０，ｉ＝１，２，３，４，
{
５
用单纯形法和两阶段法求得两个问题的最终单纯形表如下：
原问题的最终单纯形表
—２３—
对偶问题的最终单纯形表
经典例题［２－２］　北京交通大学２００９，一、５０分
已知线性规划问题如下：
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
１．求该问题的最优解；
２．写出该线性规划问题的对偶问题，并求对偶问题的最优解；
３．分别确定ｘ２，ｘ３的目标函数系数ｃ２，ｃ３在什么范围内变化最优解不变？
４．求约束条件右端值由 ( )３９ 变为
２( )１５ 时的最优解；
５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３≤５时的最优解。
ｍｉｎｚ＝２ｘ１＋５ｘ２＋
１
２ｘ３
ｓ．ｔ．
ｘ１＋２ｘ２＋
１
２ｘ３≥３
ｘ２＋３ｘ３≥９
ｘ１，ｘ２，ｘ３≥





０
　　
ｍａｘω＝３ｙ１＋９ｙ２
ｓ．ｔ．
ｙ１≤２
２ｙ１＋ｙ２≤５
１
２ｙ１＋３ｙ２≤
１
２
ｙ１，ｙ２≥







０
单纯形法求解原问题的最终表如下：
—３３—
《运筹学》考点精讲及复习思路
Ｘ ＝ ０，０，６，０，( )９Ｔ　　Ｚ＝３　　Ｙ ＝ １，０，１，３，( )０　　ω＝３
复习思路提示：
·从上表中可以清楚地看出两个问题变量之间的对应关系。只需求解其中一个问题，从最优解
的单纯形表中即可同时得到另一个问题的最优解；
·注意单纯形乘子为 Ｙ＝ＣＢＢ
－１，其与对偶变量之间的关系，经常会考察“相差一个负号”的
理解；
·单纯形法的矩阵描述将广泛地应用到灵敏度分析部分中，要学会用Ｂ－１来求解每张表中的未知
数值。
思考题［２－２］　（留待以后课程讲解）
昆明理工大学２０１２，二，２５分
对于线性规划问题：
ｍａｘＳ＝１０ｘ１＋５ｘ２
ｓ．ｔ．
３ｘ１＋４ｘ２≤９
５ｘ１＋２ｘ２≤８
ｘ１≥０，ｘ２≥
{
０
１．写出此问题的对偶问题；
２．求出此问题和它的对偶问题的最优解和最优值。
要点３　线性规划的对偶理论
·对称性
·弱对偶性
·最优性
·对偶定理（强对偶性）
·互补松弛性
经典例题［２－４］　清华大学教材编写组《运筹学》第三版Ｐ５４，例２
原问题
ｍａｘｚ＝２ｘ１＋３ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤８
４ｘ１　　≤１６
４ｘ２≤１２
ｘ１，ｘ２≥







０
　　　　
对偶问题
ｍｉｎｗ＝８ｙ１＋１６ｙ２＋１２ｙ３
ｓ．ｔ．
ｙ１＋４ｙ２≥２
２ｙ１＋４ｙ３≥３
ｙ１，ｙ２，ｙ３≥
{
０
原问题化为极小问题，初始单纯形表：
—４３—
迭代至最终单纯形表：
对偶问题用两阶段法求解的最终单纯形表：
原问题化为极小化的最终单纯形表：
两个问题作一比较：
１．两者的最优值相同ｚ＝ｗ＝１４
２．变量的解在两个单纯形表中互相包含
原问题最优解（决策变量）
ｘ１ ＝４，ｘ２ ＝２←→对偶问题的剩余变量的检验数
对偶问题最优解（决策变量）
—５３—
《运筹学》考点精讲及复习思路
ｙ１ ＝
３
２，ｙ２ ＝１／８，ｙ３ ＝０←→原问题的松弛变量的检验数
从引例中可见：
原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另
一种表达而已。
理论证明：
原问题与对偶问题解的关系
对偶问题的基本性质
设原问题（１）
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
　　　　
对偶问题（２）
ｍｉｎｗ＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
一、对称定理
定理：对偶问题的对偶是原问题。
证对称性
原问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＡＸ≤ｂ
Ｘ≥{ ０
　　
　对偶
→
　
　　
对偶问题
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＹＡ≥Ｃ
Ｙ≥{ ０
将对偶问题两边同时取负号，得
ｍａｘ（－ω）＝－Ｙｂ
ｓ．ｔ．
－ＹＡ≤－Ｃ
Ｙ≥{ ０
　　
　据对称标准形　
ｍａｘω′＝ｍａｘｚ＝ＣＸ
ｓ．ｔ．ＡＸ≤ｂＸ≥{
→
０
　　
ｍｉｎ（－ω）＝－ＣＸ
ｓ．ｔ．
－ＡＸ≥－ｂ
Ｘ≥{ ０
二、弱对偶性定理
若Ｘ
－
和Ｙ
－
分别是原问题（１）及对偶问题（２）的可行解，则有ＣＸ
－
≤Ｙ
－
ｂ
证明：
ＡＸ
－
≤ｂＹ
－
ＡＸ
－
≤Ｙ
－
ｂ
　　 Ｙ
－
Ａ≥ＣＹ
－
ＡＸ
－
≥ＣＸ}
→
－
ＣＸ
－
≤Ｙ
－
ＡＸ
－
≤Ｙ
－
ｂ
从弱对偶性ＣＸ
－
≤Ｙ
－
ｂ可得到以下重要结论：
（１）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的
下界。
—６３—
（２）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的
上界。
（３）若原问题可行，但其目标函数值无界，则对偶问题无可行解。
（４）若对偶问题可行，但其目标函数值无界，则原问题无可行解。
（５）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。
（６）若原问题无可行解，则其对偶问题具有无界解或无可行解。
三、最优性定理
若Ｘ 和Ｙ 分别是（１）和（２）的可行解，且有ＣＸ ＝Ｙｂ，则Ｘ，Ｙ 分别是（１）和（２）的最优解。
证明：因为（１）的任一可行解Ｘ
－
均满足ＣＸ
－
≤Ｙｂ
∵ＣＸ ＝Ｙｂ　　∴ＣＸ
－
≤ＣＸ
则Ｘ 为（１）的最优解，
反过来可知：Ｙ 也是（２）的最优解。
四、对偶定理（强对偶性）
若原问题有最优解，那么对偶问题也有最优解，且两者的目标函数值相等。
证明：设Ｘ 是原问题的最优解，则其对应的基Ｂ必存在Ｃ－ＣＢＢ
－１Ａ≤０．
∵Ｙ ＝ＣＢＢ
－１　　　∴ＹＡ≥Ｃ
即Ｙ 使对偶问题的可行解，则
ω＝Ｙｂ＝ＣＢＢ
－１ｂ
Ｘ ＝Ｂ－１ｂｚ＝ＣＸ ＝ＣＢＢ
－１ｂ
∴ＣＸ ＝ＣＢＢ
－１ｂ＝Ｙｂ
∴据最优性定理可知，Ｙ 是对偶问题的最优解。
原问题与对偶问题的解，一般有三种情况：
· →一个有有限最优解 另一个有有限最优解。
· →一个有无界解 另一个无可行解。
·两个均无可行解。
五、互补松弛性
若Ｘ
＾
，Ｙ
＾
分别是原问题（１）与对偶问题（２）的可行解，ＸＳ，ＹＳ分别为（１）、（２）的松弛变量，则：Ｙ
＾
ＸＳ
＝０，ＹＳＸ
＾
＝０Ｘ
＾
，Ｙ
＾
为最优解
—７３—
《运筹学》考点精讲及复习思路
证：设原问题和对偶问题的标准型是
原问题
ｍａｘｚ＝ＣＸ
ｓ．ｔ．
ＹＡ－ＹＳ ＝Ｃ
Ｘ，ＸＳ≥
{ ０
　　　　
对偶问题
ｍｉｎω＝Ｙｂ
ｓ．ｔ．
ＡＸ＋ＸＳ ＝ｂ
Ｙ，ＹＳ≥
{ ０
ｚ＝ ＹＡ－Ｙ( )
Ｓ Ｘ＝ＹＡＸ－ＹＳＸ
ω＝ＹＡＸ＋Ｘ( )
Ｓ ＝ＹＡＸ＋ＹＸＳ
若ＹＳＸ
∧
＝０，Ｙ
∧
ＸＳ ＝０；则ω＝Ｙ
∧
ｂ＝Ｙ
∧
ＡＸ
∧
＝ＣＸ
∧
＝ｚ，
由最优性质，可知Ｘ
∧
，Ｙ
∧
是最优解。
又若Ｘ
∧
，Ｙ
∧
分别是原问题和对偶问题的最优解，根据最优性质有，ＣＸ
∧
＝Ｙ
∧
ｂ
ｚ＝ＣＸ
∧
＝ Ｙ
∧
Ａ－Ｙ( )
Ｓ Ｘ
∧
＝Ｙ
∧
ＡＸ
∧
－ＹＳＸ
∧
ω＝Ｙ
∧
ｂ＝Ｙ
∧
ＡＸ
∧
＋Ｘ( )
Ｓ ＝Ｙ
∧
ＡＸ
∧
＋Ｙ
∧
ＸＳ
→ＹＳＸ
∧
＝Ｙ
∧
ＸＳ ＝０
经典例题［２－５］
南京航天航空大学２０１０，一、简答，５分
１．简述互补松弛性的内涵。
南京航天航空大学２０１１，一、简答，５分
２．简述对偶问题的互补松弛性
南京航天航空大学２０１２，一、简答，５分
４．何谓互补松弛性。
经典例题［２－５］：清华大学教材编写组《运筹学》第三版Ｐ５９，例５
已知线性规划问题
ｍｉｎω＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋３ｘ５
ｓ．ｔ．　ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３
ｘｊ≥０，ｊ＝１，２，…，５
已知其对偶问题的最优解为ｙ１ ＝
４
５，ｙ

２ ＝
３
５；ｚ＝５。试用对偶理论找出原问题的最优解。
解：先写出其对偶问题
ｍａｘｚ＝４ｙ１＋３ｙ２
ｓ．ｔ．　
ｙ１＋２ｙ２≤２
ｙ１－ｙ２≤３
２ｙ１＋３ｙ２≤５
ｙ１＋ｙ２≤２
３ｙ１＋ｙ２≤３
ｙ１，ｙ２≥









０
—８３—
由互补松弛性，可知
ＹＳＸ ＝０ｙｓｉｘｉ ＝０
∵ｙｓ２，ｙｓ３，ｙｓ４ ＞０
∴ｘ２ ＝ｘ３ ＝ｘ４ ＝０
∵ｙｓ１，ｙｓ５ ＝０　　∴ｘ１ ＞０，ｘ５ ＞０
由题可知
ｙ１ ＝
４
５ ＞０，ｙ

２ ＝
３
５ ＞０
由互补松弛性，
ＹＸＳ ＝０ｙｉｘｓｉ＝０
∴ｘｓ１ ＝ｘｓ２ ＝０
原问题
ｍｉｎω＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋３ｘ５
ｓ．ｔ．　ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３
ｘｊ≥０，ｊ＝１，２，…，５
ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５ ＝４
２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５ ＝３
因此，得到
ｘ１ ＋３ｘ５ ＝４
２ｘ１ ＋ｘ５ ＝３

ｘ１ ＝１
ｘ５ ＝
{ １
原问题的最优解为Ｘ ＝ １，０，０，０，( )１Ｔ　　ω ＝５
说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件
为严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。
复习思路提示：
（１）对偶问题的性质通常用小题型来考察，如选择、判断和填空等，分值大致在５分左右；
—９３—
《运筹学》考点精讲及复习思路
（２）若考察大题，则通常也只作为大题中的一个小题，考察内容可能是：
·从已知的对偶问题的最优解，求原问题最优解，反之亦然。
·证实原问题可行解是否为最优解。
（３）牢记定理，证明过程略懂即可，以防万一出相关证明题。
思考题［２－３］　（留待以后课程讲解）
北京科技大学２０１１，一、（１）填空，２分
若对偶问题为无界解，则原问题 。
中山大学２００９，一、（３）多项选择，５分
２．下列说法正确的有（　　）
Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；
Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；
Ｃ．已知ｙｉ 为线性规划对偶问题的最优解，若ｙｉ ＞０则说明在最优生产计划中第ｉ种资源已完全耗尽；
Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增大ｋ；
Ｅ．任何线性规划问题具有唯一的对偶问题。
要点４　影子价格
在单纯形法的每步迭代中，目标函数取值 ｚ＝ＣＢＢ
－１ｂ，和检验数 ＣＮ －ＣＢＢ
－１Ｎ中都有乘子 Ｙ＝
ＣＢＢ
－１，那么Ｙ的经济意义是什么？
影子价格
当线性规划原问题求得最优解ｘｊ（ｊ＝１，…，ｎ）时，其对偶问题也得到最优解ｙｉ（ｉ＝１，…，ｍ），
且代入各自的目标函数后有：
ｚ ＝∑
ｎ
ｊ＝１
ｃｊｘｊ ＝∑
ｍ
ｉ＝１
ｂｉｙｉ ＝ｗ
ｂｉ———是线性规划原问题约束条件的右端项，它代表第ｉ种资源的拥有量；
影子价格的定义（对偶变量ｙｉ 的意义）
代表在资源最优利用条件下对单位第ｉ种资源的估价，这种估价不是资源的市场价格，而是根据
资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（ｓｈａｄｏｗｐｒｉｃｅ）。
经典例题［２－６］　
深圳大学２０１１，一、填空（１），２分
线性规划最优生产计划中第 ｉ种资源有剩余，则该资源的影子价格为 。北京交通大学
２０１０，一、判断（３），２分
３．影子价格大于０，表示其对应资源已完全消耗完。
南京航天航空大学２０１１，二、简答（１），５分
１．简述影子价格及其经济意义。
南京航天航空大学２０１２，一、简答（１），５分
—０４—
１．简述影子价格的含义。
原问题化为极小化的最终单纯形表：
影子价格的经济意义
【１】影子价格是一种边际价格。
在ｚ ＝∑
ｎ
ｊ＝１
ｃｊｘｊ ＝∑
ｍ
ｉ＝１
ｂｉｙｉ ＝ｗ 中，
ｚ
ｂｉ
＝ｙｉ
说明ｙｉ 的值相当于在资源得到最优利用的生产条件下，ｂｉ每增加一个单位时目标函数 ｚ的
增量。
几何解释：图解法分析
ｍａｘｚ＝２ｘ１＋３ｘ２
ｓ．ｔ．
ｘ１＋２ｘ２≤８
４ｘ１≤１６
４ｘ２≤１２
ｘ１，ｘ２≥







０
【详见课程视频】
【２】影子价格又是一种机会成本ｙ１ ＝
３
２，ｙ

２ ＝
１
８，ｙ

３ ＝０
·在纯市场经济条件下，当第２种资源的市场价格低于１／８时，可以买进这种资源；
·当市场价格高于影子价格时，就会卖出这种资源。
·随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等
水平时，才处于平衡状态。
【３】在对偶问题的互补松弛性质中有
—１４—
《运筹学》考点精讲及复习思路
当∑
ｎ
ｊ＝１
ａｉｊｘ
＾
ｊ＜ｂｉ时，ｙ
＾
ｉ＝０；
当 ｙ^ｉ＞０时，∑
ｎ
ｊ＝１
ａｉｊｘ
＾
ｊ＝ｂｉ
这表明生产过程中如果某种资源ｂｉ未得到充分利用时，该种资源的影子价格为零；又当资源的影
子价格不为零时，表明该种资源在生产中已耗费完毕。
复习思路提示：
（１）影子价格考察的内容通常就两部分：
·影子价格大于或等于０所代表的资源消耗情况；
·简述影子价格的经济意义。
（２）考察分值在５分以内，以选择和判断多见。
思考题［２－３］　（留待以后课程讲解）
中山大学２００９，一、（３）多项选择，５分
３．下列说法正确的有（　　）
Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；
Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；
Ｃ．已知ｙｉ为线性规划对偶问题的最优解，若ｙｉ ＞０则说明在最优生产计划中第ｉ种资源已完全
耗尽；
Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增大
ｋ；
Ｅ．任何线性规划问题具有唯一的对偶问题。
要点５　对偶单纯形法
·对偶单纯形法的基本思路
·对偶单纯形法的计算步骤
原问题每次迭代的单纯形表的检验数行对应其对偶问题的一个基解。
设原问题和对偶问题的标准型是
原问题 　　　　 对偶问题
ｍａｘｚ＝ＣＸ ｍｉｎω＝Ｙｂ
ｓ．ｔ．　
ＡＸ＋ＸＳ ＝ｂ
Ｘ，ＸＳ≥
{ ０
ｓ．ｔ．　
ＹＡ－ＹＳ ＝Ｃ
Ｙ，ＹＳ≥
{ ０
决策变量 ＸＢ ＸＮ ＸＳ
检验数 ０ ＣＮ －ＣＢＢ
－１Ｎ －ＣＢＢ
－１
对应 ＹＳ１ －ＹＳ２ －Ｙ
对偶单纯形法的基本思路
—２４—
对偶单纯形法的计算步骤
线性规划问题
ｍａｘｚ＝ＣＸ
ＡＸ＝ｂ
Ｘ≥{ ０
不妨设Ｂ＝（Ｐ１，Ｐ２，…，Ｐｍ）为对偶问题的初始可行基，则Ｃ－ＣＢＢ
－１Ａ≤０。
若 ｂ
～
ｉ≥０，ｉ＝１，２，…，ｍ，即表中原问题和对偶问题均为最优解，否则换基。
【１】列初始单纯形表，检查ｂ列的数字
·若都为非负，检验数都为非正，则已得到最优解。停止计算。
·至少还有一个负分量，检验数保持非正，转２；
【２】确定换出变量
ｍｉｎ Ｂ－１( )ｂｉ Ｂ
－１( )ｂｉ＜{ }０ ＝ Ｂ－１( )ｂｌ对应的ｘｌ为换出变量。
【３】确定换入变量
在单纯形表中检查ｘｌ所在行的各系数ａｌｊ，ｊ＝１，…，ｎ．若所有ａｌｊ≥０，则无可行解，停止计算。若存
在ａｌｊ＜０，计算θ＝ｍｉｎｊ
σｊ
ａｌｊ
ａｌｊ＜{ }０ ＝σｋａｌｋ对应的ｘｋ为换入变量。
【４】以ａｌｋ为主元素，按原单纯形表的迭代在表中进行迭代运算。
经典例题［２－７］　胡运权《运筹学教程》第三版，Ｐ６１，
例４　用对偶单纯形法求解线性规划问题：
ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３
ｓ．ｔ
６ｙ２＋ｙ３≥２
５ｙ１＋２ｙ２＋ｙ３≥１
ｙ１，ｙ２，ｙ３≥
{
０
　　　
ｍａｘｗ＝－１５ｙ１－２４ｙ２－５ｙ３
ｓ．ｔ
６ｙ２＋ｙ３－ｙ４ ＝２
５ｙ１＋２ｙ２＋ｙ３－ｙ５ ＝１
ｙ１，ｙ２，…，ｙ５≥
{
０
【详见课程视频】
对偶单纯形法的优点
·不需要人工变量；
·当变量多于约束时，用对偶单纯形法可减少迭代次数；
·在灵敏度分析中，有时需要用对偶单纯形法处理简化。
对偶单纯形法缺点
—３４—
《运筹学》考点精讲及复习思路
Ｅ（Ａ１）＝０．６×２５＋０．４×（－２０）－１２＝－５
Ｅ（Ａ２）＝０．６×２０＋０．４×（－１２）－８＝－０．８
Ｅ（Ａ３）＝０．６×１５＋０．４×（－８）－５＝０．８
③最大值为Ｅ（Ａ３）
选对应方案Ａ３，即维护机器，并将Ａ１，Ａ２剪枝．
经典例题［１１－５］　自编例题，多级决策问题
某公司由于市场需求增加，使得公司决定要扩大公司规模，供选方案有三种：第一种方案，新建一
个大工厂，需投资２５０万元；第二种方案，新建一个小工厂，需投资１５０万元；第三种方案，新建一个小
工厂，２年后若产品销路好再考虑扩建，扩建需追加１２０万元，后３年收益与新建大工厂相同。如下表
所示，根据预测该产品前三年畅销和滞销的概率分别为０．６，０．４．若前２年畅销，则后３年畅销后滞销
概率为０．８，０．２；若前２年滞销，则后３年一定滞销。请对方案做出选择。
效益值（单位：万元）
【详见课程视频】
复习思路提示：
１）风险型决策中较难的难点在贝叶斯决策准则，因为要计算后验概率，然后再计算在后验概率下
的新期望收益值，这里经常容易混淆，计算时要仔细辨别；
２）决策树法中注意计算分枝的收益值时，别忘了减去该分枝的投资额，尤其在处理多级决策问题时。
３）对于决策论这一章来说，风险型决策时考察频率比较高的知识点，要熟练掌握。
思考题［１１－５］　上海海事大学２０１０，４、计算题，２０分
—０４２—
某工厂面对激烈的市场竞争，拟制定利用先进技术对产品改型的计划。现有三个改型方案可供
选择：ｄ１，ｄ２，ｄ３。根据市场需求调查，该厂产品面临高需求、一般需求与低需求三种自然状态，这三种
自然状态的概率分别为０．５，０．３，０．２。在三种自然状态下不同的改型方案所获得的收益不一样，表２
给出了预期收益的情况（单位：万元）：
１）用期望值准则进行决策（６分）；
２）用决策树方法进行决策（６分）；
３）求完全信息价值ＥＶＰＩ，并说明其意义（８分）。
ｄ１ ｄ２ ｄ３
θ１ ４０ ７０ １１０
θ２ ２０ ３０ １０
θ３ １０ ０ －５０
思考题［１１－６］　天津大学２００７，六、计算题，２５分
某服装厂设计了一款新式服装准备推向全国，如直接大批生产与销售，主观估计成功与失败的概
率各为０．５，其分别获利１２００万元与－５００万元，如取消生产销售计划，则损失设计与准备费用４０万
元。为稳妥起见，可先小批生产试销，试销的投入需４５万元，根据过去情况大批生产销售为成功的例
子中，试销成功的占８４％，大批生产的销售失败的事例中试销成功的占３６％。试根据期望值准则决
定是否要进行试销，如果试销，在试销成功与失败两种情况下的决策各为何？分析过程要求画出决
策树。
经典试题讲解与本章小结
一、经典例题精讲
思考题［１１－１］　中国科学技术大学２０１２，一、简答（２），５分
２．用少于５０个字的篇幅解释不确定型决策问题与风险决策问题的区别。
答：不确定型决策是指决策者对将发生结果的概率一无所知，只能凭决策者的主观倾向进行决
策，而风险型决策是指决策的环境不是完全确定的，而其发生的概率是已知的。
思考题［１１－１］　南京航空航天大学２０１２，一、简述（６），各５分
６．何谓风险型决策。
答：风险型决策是指决策者对客观情况不甚了解，但对将发生各事件的概率是已知的。决策者往
往通过调查，根据过去的经验或主观估计等途径获得这些概率。在风险决策中一般采用期望值作为
决策准则。
思考题［１１－２］　南京航空航天大学２０１２，一、简述（５），各５分
５．简述常用的不确定型决策准则。
答：不确定型决策由决策者的主观态度不同，可分为以下几种：
１．悲观准则：取每个方案在各自然状态下的最小收益值，再从各最小收益值中求最大值；
２．乐观准则：取每个方案在各自然状态下最大收益值，再从各最大收益值中求出最大值；
—１４２—
《运筹学》考点精讲及复习思路
３．最小后悔值准则：计算出每个方案的后悔值，构成后悔值矩阵，然后选出每个方案的最大后悔
值，再从这些后悔值中选取最小的作为最优方案；
４．等可能性准则：每种状态出现的概率为１／ｎ，计算平均期望收益值，再从收益值中选取最大值；
５．乐观系数法：给定一个数字表示乐观系数，通常用α表示，规定０≤α≤１，然后根据
α·ｍａｘ
ｉ
ｕｉｊ＋ １－( )αｍｉｎ
ｉ
ｕｉｊ计算期望值，再从这些期望值中选取最大值。
思考题［１１－３］　自编例题
某决策问题中有５个行动方案Ａ１，Ａ２，Ａ３，Ａ４，Ａ５，四种自然状态θ１，θ２，θ３和θ４，但是不知道它们
发生的概率是多少。各行动方案在不同自然状态下的损益值见表３，试问：
１）在乐观法决策准则下，求出决策方案；
２）在悲观法决策准则下，求出决策方案。
效益表
θ１ θ２ θ３ θ４
Ａ１ ２５ １０ ０ －１５
Ａ２ １０ ６ ５ ３
Ａ３ ４０ ３５ －１５ －１０
Ａ４ ３０ ２５ １０ －２０
Ａ５ ２５ １５ ５ －５
　　【详见课程视频】
思考题［１１－４］　四川大学２００９，２、计算题，３０分
２．某公司设增加一条新的生产线，这一设想的成功依赖于经济条件的好坏，表中给出各种情况下
的收益值（单位：万元）。
Ａ／Ｓ 好 一般 坏
新的生产线 ４８ ３０ １２．５
现有生产线 ３５．７ ２２ １８
设决策者的乐观系数为α，试讨论α在何范围时，用折衷准则选取的最优决策方案为增加新的生
产线。
—２４２—
因为要选择的决策方案为增加新的生产线，则
４８α＋（１－α）１２．５＞３５．７α＋（１－α）１８
∴０．３１＜α≤１
思考题［１１－５］　上海海事大学２０１０，４、计算题，２０分
某工厂面对激烈的市场竞争，拟制定利用先进技术对产品改型的计划。现有三个改型方案可供
选择：ｄ１，ｄ２，ｄ３。根据市场需求调查，该厂产品面临高需求θ１、一般需求 θ２与低需求三种自然状态，
这三种自然状态的概率分别为０．５，０．３，０．２。在三种自然状态下不同的改型方案所获得的收益不一
样，表２给出了预期收益的情况（单位：万元）：
１）用期望值准则进行决策（６分）；
２）用决策树方法进行决策（６分）；
３）求完全信息价值ＥＶＰＩ，并说明其意义（８分）。
表２
ｄ１ ｄ２ ｄ３
θ１ ４０ ７０ １１０
θ２ ２０ ３０ １０
θ３ １０ ０ －５０
解：
１）用期望值准则进行决策（６分）；
状态 ｄ１ ｄ２ ｄ３
０．５ θ１ ４０ ７０ １１０
０．３ θ２ ２０ ３０ １０
０．２ θ３ １０ ０ －５０
Ｅ（ｄｉ） ２８ ４４ ４８
因为ｍａｘ
ｉ＝１，２，３
Ｅｄ( ){ }
ｉ
＝ｄ３，所以应该选择ｄ３方案
２）用决策树方法进行决策（６分）；
—３４２—
《运筹学》考点精讲及复习思路
３）求完全信息价值ＥＶＰＩ，并说明其意义（８分）。
状态 ｄ１ ｄ２ ｄ３
０．５ θ１ ４０ ７０ １１０
０．３ θ２ ２０ ３０ １０
０．２ θ３ １０ ０ －５０
Ｅ（ｄｉ） ２８ ４４ ４８
ＥＰＰＩ＝∑
３
ｉ＝１
Ｐθ( )
ｉｍａｘｊ ｕｉｊ＝０．５×１１０＋０．３×３０＋０．２×１０＝６６
ＥＶＰＩ＝ＥＰＰＩ－ＥＭＶ ＝６６－４８＝１８（万元）
完全信息价值为１８万元，即该工厂若经过市场调查获得完全信息，可使收益比无附加信息时的
最大期望收益增加，故可付费收集完全信息，但不能超过１８万元。
思考题［１１－６］　天津大学２００７，六、计算题，２５分
某服装厂设计了一款新式服装准备推向全国，如直接大批生产与销售，主观估计成功与失败的概
率各为０．５，其分别获利１２００万元与－５００万元，如取消生产销售计划，则损失设计与准备费用４０万
元。为稳妥起见，可先小批生产试销，试销的投入需４５万元，根据过去情况大批生产销售为成功的例
子中，试销成功的占８４％，大批生产的销售失败的事例中试销成功的占３６％。试根据期望值准则决
定是否要进行试销，如果试销，在试销成功与失败两种情况下的决策各为何？分析过程要求画出决
策树。
解：设Ａ表示大批生产销售成功，Ｂ表示试销成功。则
由题可知
ＰＢ( )Ａ ＝０．８４，ＰＢＡ( )
－
＝０．３６
因此可计算：
试销成功的概率
Ｐ( )Ｂ ＝Ｐ( )ＡＰＢ( )Ａ＋ＰＡ( )
－
ＰＢＡ( )
－
＝０．５×０．８４＋０．５×０．３６＝０．６
在试销成功的条件下，大批生产销售成功的概率
ＰＡ( )Ｂ ＝
Ｐ( )ＡＰＢ( )Ａ
Ｐ( )Ｂ
＝０．５×０．８４０．６ ＝０．７
在试销成功的条件下，大批生产销售失败的概率
ＰＡ
－
( )Ｂ ＝０．３
在试销失败的条件下，大批生产销售成功的概率
ＰＡＢ( )
－
＝
Ｐ( )ＡＰＢ
－
( )Ａ
ＰＢ( )
－ ＝
０．５× １－０．( )８４
１－０．( )６ ＝０．２
在试销失败的条件下，大批生产销售失败的概率
—４４２—
ＰＡ
－
Ｂ( )
－
＝０．８
画决策树
求期望值
【详见视频课程】
所以，根据ＥＭＶ准则对决策树计算，应在大量销售前先进行试销。在试销成功条件下进行大量
销售；在试销失败时，应取消销售计划。
二、本章小结
一、基本概念
１．决策问题的组成
决策者：决策的主体，一个人或团体；
决策：两个以上可供选择的行动方案，记为Ａｊ；
状态：决策实施后可能遇到的自然状况，记为Ｓｉ；
状态概率：对各状态发生可能性大小的主观估计，记为ＰＳ( )
ｉ ；
结局（损益）：当决策方案Ａｊ实施后遇到状态Ｓｉ时所产生的效益（利润）或损失（成本），记为ｕｉｊ。
２．决策问题的分类
确定型：状态只有一种；
不确定型：状态不只一种；又可分为完全不确定型（状态概率未知）和风险型（状态概率可知）。
二、不确定型决策
１．悲观法———小中取大原则
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍｉｎｉ ｕｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘｊ ｍｉｎｉ ｕｉｊ
基本步骤：
１）计算每个方案的评价值，即为每个方案在各自然状态下的最小收益值；
２）根据方案评价值选择最优方案，即从各最小收益值中求最大值。
２．乐观法———大中取大原则
—５４２—
《运筹学》考点精讲及复习思路
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｕｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘｊ ｍａｘｉ ｕｉｊ
基本步骤：
１）计算每个方案的评价值，即为每个方案在各自然状态下的最大收益值；
２）根据方案评价值，选择评价值最大的方案为最优方案。
３．最小后悔值法———大中取小原则
决策过程：在状态Ｓｉ下，选择方案Ａｊ的后悔值为ｒｉｊ＝ｍａｘｊ ｕｉｊ－ｕｉｊ
所有后悔值构成后悔值矩阵。
方案Ａｊ←评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｒｉｊ
ｍｉｎｆＡ( )
ｊ ＝ｍｉｎｊ ｍａｘｉ ｒｉｊ
基本步骤：
１）计算出后悔矩阵；
２）计算每一个方案评价值ｆＡ( )
ｊ ＝ｍａｘｉ ｒｉｊ；
３）选择最小评价值ｍｉｎｆＡ( )
ｊ ，确定最优方案。
４．等可能性方法———平均原则
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝∑
ｍ
ｉ＝１
１
ｍａｉｊ＝
１
ｍ∑
ｍ
ｉ＝１
ａｉｊ
ｍａｘｆＡ( )
ｊ ＝ｍａｘ
１
ｍ∑
ｍ
ｉ＝１
ａ{ }ｉｊ
基本步骤：
１）计算每一个方案评价值；
２）选择最大评价值，确定最优方案。
５．乐观系数法———折衷原则
确定一个数字表示乐观程度，称为乐观系数。用α表示，并规定０≤α≤１。
决策过程：
方案Ａｊ←评价值ｆＡ( )
ｊ ＝α·ｍａｘｉ ｕｉｊ＋ １－( )αｍｉｎ
ｉ
ｕｉｊ
ｍａｘ
ｊ
ｆＡ( ){ }
ｊ
＝ｍａｘ
ｊ
α·ｍａｘ
ｉ
ｕｉｊ＋ １－( )αｍｉｎ
ｉ
ｕ{ }ｉｊ
基本步骤：
１）选择乐观系数为α，计算各方案评价值；
２）比较各方案的评价值ｍａｘｆＡ( ){ }
ｊ
，选择最优方案。
三、风险型决策
１．最大期望效益准则
思路步骤：
求期望效益值ＥＭＶ。期望效益值＝∑条件效益值×概率，
—６４２—
即ＥＭＶｉ＝∑
ｎ
ｊ＝１
ｐｊａｉｊ
选择最大期望效益值所对应的方案为决策方案
ＥＭＶ ＝ｍａｘ｛ＥＭＶｉ｝
２．贝叶斯决策准则及信息价值
贝叶斯决策（ＢａｙｅｓｉａｎＤｅｃｉｓｉｏｎＴｈｅｏｒｙ）就是在不完全情报下，对部分未知的状态用主观概率估
计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。
贝叶斯决策属于风险型决策，决策者虽不能控制客观因素的变化，但却掌握其变化的可能状况及
各状况的分布概率，并利用期望值即未来可能出现的平均状况作为决策准则。
贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：
１）已知类条件概率密度参数表达式和先验概率。
２）利用贝叶斯公式转换成后验概率。
３）根据后验概率大小进行决策分类。
３．决策树法
□：表示决策点，也称为树根，由它引发的分枝称之为方案分枝，方案节点被称为树枝．ｎ条分枝表
示有ｎ种供选方案。
：表示策略点，其上方数字表示该方案的最优收益期望值，由其引出的 ｍ条线称为概率枝表示
有ｍ种自然状态，其发生的概率已标明在分枝上。
△：表示每个方案在相应自然状态的效益值。
!
：表示经过比较选择此方案被删除掉了，称之为剪枝。
①根据题意作出决策树图；
②从右向左计算各方案期望值，并进行标注；
③对期望值进行比较，选出最大期望效益值，写在□上方，表明其所对应方案为决策方案，同时在
其它方案上打上
!
删除．
Ｅ（Ｈｉ）＝
ｎ
ｊ＝１
ｐｊＶｉｊ　　　　ｉ＝１，…，ｎ
—７４２—
《运筹学》考点精讲及复习思路