运筹学考点精讲及复习思路

提提 第—章线性规划与单纯形法（第二章对偶问题与灵敏度分 （第三章运输问题（第四章目标规划（第五章整数规划（第六章动态规划（第七章图与网络 （第八章网络计划 （第九章存储论（第十章排队论（第十—章决策论（《运筹学》考点精讲及复习思第一 线性规划与单纯形~、本章考情分析常考题型：选择、填空、简答、判断和计算分值：必考知识点，分值占３０分以上重要性：作为前五章的基础铺垫，非常重要！重要程度：★★★★★二、本章基本内容１）掌握线性规划的数学模型的标准型；２）掌握线性规划的图解法及几何意义；３）了解单纯形法原理；４）熟练掌握单纯形法的求解步骤５）能运用大Ｍ法与两阶段法求解线性规划问题；６）熟练掌握线性规划几种解的性质及判定定理．三、本章重难点：重点１）单纯形法求解线性规划问题；２）解的性质；３）线性规划问题建模．难点：１）单纯形法原理的理解；２）线性规划问题建模．四、本章要点精讲要点 化标准要点 图解要点 单纯形法的原要点 单纯形法的计算步要点５ 单纯形法的进一步讨论要点１ 化标准型线性规划的数学模１提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５线性规划的共同特决策变量１：每个问题都用一组决策变量表示某个方案决策变量２：决策变量的取值一般都是非负且连续约束条件３：与决策变量不矛盾的条件，用线性等式或不等式表目标函数４：决策变量与价值系数组成，一般要求实现最大或最小【建模思路】确定决策变量写出目标函数找出约束条线性规划的标准型可简化ｎｍａｘＺ＝∑ｉｓ．ｓ．ｔ．∑ｊ＝ ｉ＝１，２，…，ｊｘｊ≥ ｊ＝１，２，…，经典例题［１－１］ 胡运权，运筹学教程（三）Ｐ１５，例３与南京航空航天大学２００５年，第四题类似，１０分ｍｉｎＺ＝ｘ１＋２ｘ２＋－２ｘ１＋ｘ２＋ｘ３≤－３ｘ１＋ｘ２＋２ｘ３≥４４ｘ１－２ｘ２－３ｘ３＝－ｘ０，ｘ０，ｘ取值无约 ２提《运筹学》考点精讲及复习思【１】目标函数最【２】资源限量（右端项）非【３】约束条件等松弛变量与剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。【４】决策变量非整理，ｍａｘＺ′＝ｘ１′－２ｘ２－３ｘ３′＋３ｘ３″＋０ｘ４＋目标函数最大约束条件等式决策变量非资源目标函数最大约束条件等式决策变量非资源限量非ｘ′＋ｘ＋ｘ′－ｘ″３ｘ１′＋ｘ２＋２ｘ３′ｘ′＋ｘ＋ｘ′－ｘ″４ ２ ３ ３ ｘ′，ｘ，ｘ′，ｘ″，ｘ，ｘ≥ 经典例题［１－ 天津大学２００４，二，（１），约５３提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动．表１给出了公司准备做广告的三种产品名称、估计每做一单位广告使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量分别为１．请写出此问题的线性规划模型，并将模型化为标准型．其中洗衣粉的市场份额出现负值是由液体洗涤剂的份额增加造成的电印刷媒广告后市场份额最低增去污液体洗涤洗衣–广告单位成本（万元解：设电视的广告数量为ｘ１，印刷媒体的广告数量为ｍｉｎＺ＝１００ｘ１＋ｘ２≥３ｘ１＋１２ｘ２≥１８－ｘ１＋４ｘ２≥ 化为标准型 ｍａｘＺ′＝－１００ｘ１－２００ｘ２＋０ｘ３＋０ｘ４＋ｘ２－ｘ３＝３ｘ１＋１２ｘ２－ｘ４＝１８－ｘ１＋４ｘ２－ｘ５＝ｘ，ｘ，ｘ，ｘ，ｘ≥ 复习思路提示初学时，化标准型可按“目标函数 资源限量 约束条件 决策变量”的顺序进行，化完后默念四句口诀验证；化标准型是用单纯形法求解线性规划问题的第一步，非常重要！而单纯形法求解线性规划问题是每年必考大题，此步错，后面展开步步错！要点 图解图解法求解步骤４提《运筹学》考点精讲及复习思经典例题［１－３］ 胡运权，运筹学教程（三）Ｐ１６，例１ｍａｘＺ＝２ｘ１＋ｘ２５ｘ２≤６ｘ１＋２ｘ２≤２４ｘ１＋ｘ２≤ ｘ，ｘ≥ 【详见课程视频图解法的几点启示线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；若线性规划的可行域存在，则可行域一定是个凸集；若线性规划的最优解存在，则最优解或最优解之一（无穷多解时）一定是可行域的凸集的某个顶点；解题思路：找出凸集的顶点，计算其目标函数值，比较即得。图解法启示的解题思路经典例题［１－４］天津大学２００６，一、选择（１），２用图解法解线性规划时，以下几种情况不可能出现的是 Ａ．可行域有界，无有限最优解（或称无界解 Ｂ．可行域无界，有唯一最优Ｃ．可行域是空集，无可行解 Ｄ．可行域有界，有多重最优解复习思路提示：·要会用图解法来分析线性规划的几种解的情况，如唯一最优解、无穷多解、无界解和无可行解５提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５图解法容易在确定可行域的范围和等值线移动方向上犯错图解法的知识点通常出现在选择、填空、判断等小题型中！大致分值在１０分以内．思考题［１－１］ （留待以后课程讲解）南京航空航天大学２００４，一、多项选择２、３，各５２．线性规划的最解可在（）Ａ．可行集Ｂ．可行集边界Ｃ．可行集顶点Ｄ．满足其约束条件的区域３．线性规划的可集可以（）Ａ．不含有任何可解Ｂ．恰含有一个可行Ｃ．恰含有两个可行解 Ｄ．含有无数个可行解思考题［１－２］ （留待以后课程讲解）南京航空航天大学２００６，第二题，１０分二、（１０分）用图解法求解线性规划问题．ｍａｘｚ＝４０ｘ１＋ｘ１＋２ｘ２≤３ｘ１＋２ｘ２≤６０２ｘ２≤ ｘ，ｘ≥ 要点 单纯形法原解的概念与关单纯形法迭代原［１］解的概念与关系线性规划的标准型ｎｍａｘＺ＝∑ｉｓ．ｓ．ｔ．∑ｊ＝ ｉ＝１，２，…，ｊｘｊ≥ ｊ＝１，２，…，ｎ【向量形式】ｍａｘＺ＝ｎｓ．ｉ∑Ｐｊｘｊ＝ ｉ＝１，２，…ｓ．ｉｘｊ≥ｊ＝２，…，６提《运筹学》考点精讲及复习思【矩阵形式】ｍａｘＺ＝ＡＸ＝ｓ．ＡＸ＝Ｘ≥线性规划问题解的概ｎｍａｘＺ＝∑ （ｉｓ．

∑ｊ＝ ｉ＝１，２，…， （ｊｘｊ≥ ｊ＝１，２，…， （ 可行解：满足约束条件（２）和（３）的解Ｘ＝（ｘ，…，ｘ）Ｔ全部可行解的集合称为可行域。最优解：使目标函数（１）达到最大值的可行解 基：设Ａ是约束方程组（２）的ｍｎ阶系数矩阵（设ｎ＞ｍ，其秩为ｍＢ是Ａ中的一个ｍｍ阶的满秩子矩阵（Ｂ０的非奇异子矩阵），称Ｂ是线性规划问题的一个基．不失一般性，设除基变量以外的变量称为非基变基解：在约束方程组（２）中，令所有的非基变量ｘｍ＋１＝ｘｍ＋２＝… ＝ｘｎ＝０，又因为 Ｂ≠０，据克莱姆法则，对于ａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｍｘｍ＝ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｍｘｍ＝ａｍ１

＋ａｍ２ｘ２＋…＋ａｍｍｘｍ＝可以求出唯一解ＸＢ＝ｘ，ｘ，…，ｘ ｎｍａｘＺ＝∑ （ｉｓ．

∑ｊ＝ ｉ＝１，２，…， （ｊｘｊ≥ ｊ＝１，２，…， （基可行解：满足变量非负约束条件（３）的基解．可行基：对应基可行解的基．经典例题［１－ 胡运权，运筹学教程（三）Ｐ１９，例找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解７提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ｍａｘＺ＝２ｘ１＋３ｘ２＋ｘ１＋ｘ３＝ ０１０ｓ．ｔ．ｘ１＋２ｘ２＋ｘ４＝ｘ２＋ｘ５＝ｘｊ≥０，ｊ＝１，２，…，【详见课程视频凸集、顶点及几个定

Ａ＝ １２０１ １００设Ｋ是ｎ维欧氏空间的一点集， Ｘ（１）∈Ｋ，Ｘ（２）∈Ｋ的连线上的所有点Ｘ１）＋（１－αＸ（２）Ｋ，０α１），则称Ｋ为凸集设Ｋ是凸集，ＸＫ；若Ｘ不能用不同的两点Ｘ（１）Ｋ和Ｘ（２）Ｋ的线性组合表示为Ｘ＝Ｘ＋（１－αＸ（２），（０＜α＜１）则称Ｘ为Ｋ的一个顶点（或极点）定理 若线性规划问题存在可行解，则问题的可行域是凸集．（天津大学２００６年第三题证明，分引 线性规划问题的可行解为基可行解的充要条件是Ｘ的正分量所对应的系数列向量是线独立的定理２ 线性规划问题的基可行解Ｘ对应线性规划问题可行域（凸集）的顶点．定理３ 若线性规划问题有最优解，一定存在一个基可行解是最优解．几个定理考察的通常是小题型，需要牢记结论，且理解各个解之间的关系。几点结论：【１】可行域若有界则是凸集，也可能是无界域【２】每个基可行解对应可行域的一个顶点【３】可行域有有限多个顶点【４】如果有最优解，必在某个顶点上得到．线性规划解之间的关系归纳“箭尾的解一定是箭头的解，反之不一定成立．当最优解唯一时，最优解也是基最优解当最优解不唯一时，最优解不一定是基最优解经典例题［１－６］ 南京航空航天大学，２０１１，一、判断（１），３分一、判断下列说法是否正确．８提《运筹学》考点精讲及复习思１）若线性规划问题的可行解为最优解，则该可行解必定是基可行解．（ 经典例题［１－７］ 北京交通大学，２０１０，一、判断（１），２分—、判断下列说法是否正确１）线性规划问题的每一个基解对应可行域的一个顶点．（ 单纯形法的迭代思路：［２］单纯形法的迭代原理ｍａｘＺ＝ＣＸｓ．ｓ．ｔ．∑Ｐｊｘｊ＝ｉｘｊ≥ ｊ＝１，２，…【１】构造初始可行Ｂ＝Ｐ，Ｐ，…，

０ ０ １直接观察一个可行≤约束，加松弛变量

Ｂ≠≥约束，加人工变量（后面会讨论（为讨论方便，设均为≤约束【２】基变换：两个基可行解相邻，两者可变换且仅变换一个基变９提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５设初始基可行解为写出系数矩阵的增广矩阵 ［移项得 可得Ｐｊ＝∑ｊ →Ｐｊ－∑ｊｉ＝ｉ ｉ上式乘以一个正数θ＞０，ｍθＰｊ－∑Ｐｉ＝ｍｉ ∑ｘ０－θａＰｉ＋Ｐ＝ｍ∑Ｐｘ０＝ｉ

ｉｉｍ由∑ｘ０θａＰｉＰ＝ ｉｎ可找到满足原约束方程组∑Ｐｊｘｊ＝ｂ的另一个点ｉＸ１＝ｘ０－θａ，…，ｘ０–ａｊ，０，…，θ…，０ ｉ要使是一个基可行解，则应对所有ｉ＝１，２，…，ｍ存在ｘ０–ａｊ０（先要使其可行ｉ令这ｍ个不等式至少有一个等号成立，且当ａｉｊ０时，上式显然成立，故可θ＝ｍｉｎｘ

ａ> ＝ 可确保ｘ０θａ

＝０，ｉ＝≥０，ｉ≠

此时与ｘ

是可行解，ｘ１，…，ｘ１，ｘ１对应的向量 ｌ１ ｌ 提《运筹学》考点精讲及复习思【３】最优性检验和解的判ｎ将上述Ｘ（０），Ｘ（１）分别代入目标函数ｚ＝∑ｘｊ，ｊｊｚ０

＝∑ｃｘｉｉｚ１＝

ｃｘ０－θａ＋θｃ＝ｍｃｘ０＋θｃ

ｍｃａ＝ｚ０＋θｃ

ｍｃａ ｉｍ

ｉｉｍ

ｉ１

ｉ１ｚ

＝∑ｃｘ ｚ１＝ｚ０＋θｃ ｃａｉ ｉ

ｉ１（１）当所有σ０，当前顶点（基可行解）的目标函数值已是最大，即为最优解ｊ（２）当所有σ０，又某个非基变量ｘｊ的检验数为０，则在另一个顶点也使目标函数达到最大，两点连线上的所有点都是最优解，即无穷多最优解．当所有非基变量的σ＜０时，有唯一最优解；ｊ（３）若存在某个有无界解ｘ０－θａ≥

>０，而其对应的非基向量Ｐ０，则从θ值和ｚ（１）的表达式可看出，线性规 线性规划解的判别定理归纳：最优解判别定理若Ｘ（０）＝（ｂ′，ｂ′，…ｂｍ′，０，…，０）Ｔ为基可行解，且全部σ０，ｊ＝ｍ＋１，…，ｎ，则Ｘ（０）为最优解唯一最优解判别定若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）Ｔ为基可行解，且全部σｊ＜０，ｊ＝ｍ＋１，…，ｎ，则Ｘ（０）为唯一最优解无穷多最优解判别定若Ｘ（０）＝（ｂ′，ｂ′，…ｂｍ′，０，…，０）Ｔ为基可行解，且全部σ≤０，ｊ＝ｍ＋１，…，ｎ，且存在一个非提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５变量ｘｍ＋ｋ的ｍ＋＝０，则存在无穷多最优解无界解判别定若有一个非基变量ｘｍ＋ｋ的ｍ＋＞０，而其对应非基变量的所有系数ａ′ｉ，ｍ＋ｋ０，ｉ＝１，２，…，ｍ则具有无界解。复习思路提示掌握线性规划几个解的概念及几何意义，会用该知识点求解考研试题中的各类小题型会在简答题中对单纯形法的迭代思路进行描述了解单纯形法的迭代原理，牢记解的判别定理．思考题［１－３］ （留待以后课程讲解）中山大学２０１２，一、选择（３）１在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系数列向量（ ）时，则此问题是无界的。Ａ．≥０ Ｂ．＜０ Ｃ．＝０ Ｄ．０北京交通大学２０１０，一、判断（２）２分单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。１）写出该线性规划的标准型（１０分）；２）求原规划的最优解和最优目标函数值（１５）．要点４ 单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤【１】求初始基可行解，列出初始单纯形ｃｊ………ｂ………１…０……０００…１……ｃｊ－０…０…ｍｃｊ－∑ｉ…ｍｃｎ－∑ｉ提《运筹学》考点精讲及复习思【２】最优性检【３】基变１）确定换入基的变只要有检验数大于０，对应的变量就可作为换入变量，当有一个以上检验数大于０时，一般从中选取最大的一个：σ＝ｍａｘσｊ｜σ＞０ｊ其对应的变量ｘｋ作为换入变量２）确定换出基的变根据确定θ最小比值规则，对Ｐｋ列计算可得：θ＝ｍｉｎ

>＝ａ ａ

其对应的变量ｘｌ作为换出变量。元素ａｌｋ决定了从一个基可行解到相邻基可行解的转移去向，称之为主元素。３）迭代变用换入变量ｘｋ去替换基变量中的换出变量ｘｌ，得到一个新的基（Ｐ…，ＰｌＰｋ，Ｐｌ…，Ｐｍ）。对应这个基可以找出一个新的基可行解，并相应地可以画出一张新的单纯形表。【详见课程视频经典例题［１－８］ 南航，２０１２，二、计算题，１．（１）１０分二、１．（２０分）已知线性规划问题：ｍａｘｚ＝８ｘ１＋提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ｘ１＋ｘ２≤２ｘ１＋ｘ２≤１０ｘ１≤ ｘ，ｘ≥ １）用单纯形法求解【详见课程视频在上面的例题［１８］中，考虑以下两个问题１）若初始单纯形表中，若用检验数６对应的ｘ２作为换入变量会带来什么样的结果２）用图解法求解该题，看每张单纯形表对应的解与可行域中的顶点如何对应？基变换是否是相邻的顶点间进行变换？最优解在哪个顶点取得？复习思路提示正确的标准型是单纯形法求解线性规划问题的前提会依据标准型列出初始单纯形表（重点是正确找出初始基及对应的初始基变量）熟练运用矩阵的初等行变换进行单纯形表迭代（最容易犯计算错误）牢记最优性检验的几个解的判别定理（当遇到无穷多最优解和无界解的情况）。思考题［１－４］ （留待以后课程讲解）中山大学２０１２，三，１１用单纯形表求解以下线性规划问题：ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３ｘ１＋ｘ２＋ｘ３≤２ｘ１＋ｘ２－ｘ３≤６－ｘ１＋３ｘ２≤ｘ≥０，ｘ≥０，ｘ≥ 要点 单纯形法的进一步讨考虑：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？ＭａｘＺ＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ＝ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ＝ｓ．ｔ．………………ａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ＝ｘ，ｘ，…，ｘ≥

提《运筹学》考点精讲及复习思线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，添加人工变量“惩罚”人工变量 大Ｍ法和两阶段【１】大Ｍ人工变量在目标函数中的系数为Ｍ其中Ｍ为任意大的正数经典例题［１－ 清华大学运筹学编写组（三）Ｐ３３例Ｍａｘｚ＝３ｘ１－ｘ２－ｘ１－２ｘ２＋ｘ３≤－４ｘ１＋ｘ２＋２ｘ３≥３－２ｘ１＋ｘ３＝ｘ，ｘ，ｘ≥ 提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５解：１）首先化标准型２）添加人工变量，构造初始可行Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３＋０ｘ４＋０ｘ５－Ｍｘ６－ｘ１－２ｘ２＋ｘ３＋ｘ４＝－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６＝３－２ｘ１＋ｘ３＋ｘ７＝ｘｊ０，ｊ＝１，２，…，７其中，为任意大的正数求解结果出现所有检验数非正σ０，若基变量中含非零的人工变量，则无可行解；否则，有最解３）列初始单纯形表如第一步迭代，得表第二步迭代，得表提《运筹学》考点精讲及复习思第三步迭代得最终表（所有检验数小于等于【２】两阶段第一阶段：加入人工变量后，构造仅含人工变量的目标函数，并要求其实现最小化第二阶段：将一阶段得到的最终表除去人工变量。将目标函数行的系数换成原问题的目标函数系数，作为二阶段的初始表。同上例Ｍａｘｚ＝３ｘ１－ｘ２－ｘ１－２ｘ２＋ｘ３≤－４ｘ１＋ｘ２＋２ｘ３≥３－２ｘ１＋ｘ３＝ｘ，ｘ，ｘ≥ 解：１）添加人工变量，给出一阶段的数学模型ｎ＝ｘ６＋ｘ７ｘ１－２ｘ２＋ｘ３＋ｘ４＝－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６＝３－２ｘ１＋ｘ３＋ｘ７＝ｘｊ≥０，ｊ＝１，２，…，提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５Ｘ＝０，１，１，１２，０Ｔ是原线性规划问题的基可行解２）将一阶段最终表中的人工变量取消填入原问题的目标函数的系数，进行第二阶段计算单纯形法中的几个问题：退化基可行解中存在基变量等于０的解（退化解），迭代后目标函数值不变，即不同的基表示为同一个顶点。勃兰特（ｂｌａｎｄ）规则１）当遇到相同检验数时，选取对应下标最小的非基变量作为换入变量２）当存在两个及以上相同的最小比值时，选取下标最小的基变量作为换出变量检验数的几种判别形提《运筹学》考点精讲及复习思复习思路提示人工变量是人为加入的，与决策变量、松弛变量有本质的区别，若线性规划有最优解，人工变量必为０，以保持原约束条件不变。为了使人工变量为０，就要使人工变量从基变量中换出成非基变量；大和两阶段法通常不会直接出成计算大题在一些小题型中考察这两种方法的注意事项。大致分值以内。思考题［１１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 。【北京科技大学】２．简述大Ｍ法的算法步骤。【南京航空航天大学】经典试题讲解与本章小—、经典试题讲解思考题［１１］２．线性规划的最优解可在 ）。【南京航空航天大学Ａ．可行集 Ｂ．可行集边界Ｃ．可行集顶点上 Ｄ．满足其约束条件的区域上３．线性规划的可行集可以（ ）。【南京航空航天大学】Ａ．不含有任何可行 Ｂ．恰含有一个可行Ｃ．恰含有两个可行 Ｄ．含有无数个可行４．线性规划问题的每一个基解对应可行域的一个顶点。【北京交通大学，判断】５．下面命题正确的是（ ）【昆明理工大学，单选】Ａ．线性规划的最优解是基可行 Ｂ．基可行解不一定是基本Ｃ．线性规划一定有可行解 Ｄ．线性规划的最优值至多有一个思考题［１－２］１．（１０分）用图解法求解线性规划问题。【南京航空航天大学】ｍａｘｚ＝４０ｘ１＋８０ｘ２ｘ１＋２ｘ２≤３ｘ１＋２ｘ２≤６０２ｘ２≤ ｘ，ｘ≥ ２．若线性规划的可行解为最优解，则该可行解必定是基可行解。【南京航天航空大学，判断３．若Ｘ１，Ｘ２分别是某一线性规划问题的最优解，则Ｘ＝λＸ１＋λＸ２也是该线性规划问题的最优解，其中λ，λ为正实数。【南京航天航空大学，判断】提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５思考题［１１．在标准形式下线性规划问题的单纯形迭代过程中，若有某个ｃｊ－ｚｊ＞０对应的非基变量ｘｊ的系数列向量（ ）时，则此问题是无界的。【中山大学】Ａ．≥ Ｂ．＜ Ｃ．＝ Ｄ．≤２．单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。【北京交通大学判断分析ｘ１＝ｂ１′－ａ′１ｍ＋ｋｘｍ＋ｋｘ２＝ｂ２′－ａ′２ｍ＋ｋ……………

≥∵ａ′ｉｍ＋ｋ０，对任意ｘｍ＋ｋ＞０，即解都可行Ｚ＝Ｚ０＋（ｃｊ－ｚｊ）ｘｍ＋ｋ＝Ｚ０＋ｍ＋ｋ∴当ｘｍ＋ｋ＋，＋．思考题［１１．用单纯形表求解以下线性规划问题：【中山大学】ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３ｘ１＋ｘ２＋ｘ３≤２ｘ１＋ｘ２－ｘ３≤６－ｘ１＋３ｘ２≤ｘ≥０，ｘ≥０，ｘ≥ 解：化标准型，并列出初始单纯形表ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３＋０ｘ４＋０ｘ５＋０ｘ６ｘ１＋ｘ２＋ｘ３＋ｘ４＝２ｘ１＋ｘ２－ｘ３＋ｘ５＝６－ｘ１＋３ｘ２＋ｘ６＝ｘｊ≥０，ｊ＝１，２，…，提《运筹学》考点精讲及复习思迭代得表迭代得最终 ＝６，０，６，０，０，１５ ｚ＝思考题［１１．两阶段法中，若第一阶段目标函数最优值不为０，则原问题 【北京科技大学】２．简述大Ｍ法的算法步骤。【南京航空航天大学】二、本章小目标函数最大约束条件目标函数最大约束条件等式资源限量非决策变量非ｓ．

ＡＸ＝ｂＸ≥０【２】图解提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５可行域若有界则是凸集，也可能是无界域；每个基可行解对应可行域的一个顶点；可行域有有限多个顶点如果有最优解，必在某个顶点上得到…【３】线性规划解之间的关系归“箭尾的解一定是箭头的解，反之不一定成立．当最优解唯一时，最优解也是基最优解当最优解不唯一时，最优解不一定是基最优解．进行标准化，列初始单纯形表方法【４】单纯形法计算步骤框提《运筹学》考点精讲及复习思【５】人工变量 大Ｍ【６】人工变量 两阶段—阶段目标函数最优值为０，则去掉人工变量转入第二阶段；不为０，则原问题无可行解，停止算本章涉及的知识点大部分是每年的必考题，分值约占２０％，其中解的性质及判定通常会出现在空、选择或简答、判断等小题型中，而单纯形法求解是每年必考的一道大题，常与第二章对偶问题联合出题，涉及分值有时高达５０分以上。提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５第二 对偶问题与灵敏度分~、本章考情分析常考题型：选择、填空、简答、判断和计算分值：必考知识点，分值在２０－２５分之重要性：每年必考，影子价格及灵敏度分析实际应用很多重要程度：★★★★★二、本章基本内容１）熟练掌握原问题与对偶问题的转化关系（记忆转化关系表或用对称形式推导）；２）熟练掌握单纯形法的矩阵描述；３）掌握对偶问题的几条基本性质４）熟练掌握影子价格的经济意义５）能运用对偶单纯形法求解线性规划问题６）熟练掌握灵敏度分析，包括ａ，ｂ，ｃ和增加约束条件的变化三、本章重难点重点１）根据原问题写出对偶问题２）能通过单纯形法的矩阵描述，从单纯形表求原问题和对偶问题的最优解３）灵敏度分析中，分析各系数在什么范围内变化，最优解不变，或各系数变化后，最优解是否改变。难点对偶问题的性质的理解四、本章要点精讲·要１线性规划的对偶问题·要２单纯形法的矩阵描述·要３线性规划的对偶理论·要４影子价格·要５对偶单纯形法·要６灵敏度分析提《运筹学》考点精讲及复习思要点 线性规划的对偶问对偶问题的提原问题与对偶问题的数学模原问题与对偶问题的对应关系对偶问题的提出经典例题［２－１］ 胡运权主编《运筹学教程》第三版，Ｐ４８，例１美佳公司利用现有资源生产两种产品，有关数据如下产品产品资源限设备设备Ｂ调试工５时利润（元２１美佳公司考虑：如何安排生产，使获利最多？设：Ⅰ产量 ｘ１；Ⅱ产量 ｍａｘｚ＝２ｘ１＋５ｘ２≤６ｘ１＋２ｘ２≤２４ｘ１＋ｘ２≤收购方：收购美佳公司的资源，付出多少代价才能使美佳公司愿意放弃生产活动出让自己的资源呢？美佳公司：出让代价应不低于同等数量的资源自己生产的利润。设：设备 ｙ１元／设备 ｙ２元／调试工 ｙ３元／建立如下线性规划问题提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋ ｍａｘｚ＝２ｘ１＋ｓ．１２３ｓ．１２３ ≥≥６ｘ１＋２ｘ２≤１ｙ１，ｙ２，ｙ６ｘ１＋２ｘ２≤１

＋ｘ２≤特点１．ｍａｘ２．限定向量ｂ 价值向量（资源向量）Ｃ３．一个约束 一个变量４．ｍａｘｚ的ＬＰ约束“ 的ＬＰ是“≥的约束５．变量都是非负限制原问题与对偶问题的数学模【１】对称形式的对原问题和对偶问题只含有不等式约束。情形一：情形二将原问题化成标准对称ｍａｘｚ＝ｓ．ｔ－ＡＸ≤－ｂＸ≥０根据标准对称型写出对ｍｉｎｗ＝－ Ｙ＝ ｍｉｎｗ＝

提《运筹学》考点精讲及复习思ｓ． －Ｙ′Ａ≥Ｙ′≥

ｓ．ｔＹＡ≥Ｙ≤【２】非对称形式的对偶原问题的约束是等式推导过原问ｍａｘｚ＝ＡＸ≥ＡＸ≤

ｍａｘｚ＝ Ｘ≤ － －Ｘ≥ Ｘ≥ ｍｉｎｗ＝（Ｙ１，Ｙ２）–Ａｓ．

（Ｙ，Ｙ）

≥– Ｙ１≥０，Ｙ２≥ｍｉｎｗ＝（Ｙ１－Ｙ２）·（Ｙ１－Ｙ２）·Ａ≥Ｙ１≥０，Ｙ２≥令Ｙ＝Ｙ１－Ｙ２，得对偶问题为ｉｗ＝Ｙ无约束证毕提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５原问题和对偶问题的对应关经典例题［２－２］ 北京交通大学２００９，一、５０分已知线性规划问题如下：ｍｉｎｚ＝

＋

＋１２ｘ ＋ｘ

２３ｓ．ｔ．

＋３ｘ３≥ｘ，ｘ，ｘ≥ １．求该问题的最优解２．写出该线性规划问题的对偶问题，并求对偶问题的最优解３．分别确定ｘｘ３的目标函数系数ｃｃ３在什么范围内变化最优解不变９４．求约束条件右端值９

变

时的最优解５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３５时的最优解ｉｎｚ＝２ｘ１＋５ｘ２＋２ｘ３

ｍａｘω＝３ｙ１＋ｙ１≤ｘ＋２ｘ＋ｓ．ｔ．１

１ｘ≥３２３

ｓ．ｔ．２ｙ１＋ｙ２≤ ｘ ＋３ｘ≥ｘ

＋３ｙ２≤ｘ，ｘ，ｘ≥ ｙ，ｙ≥ 复习思路提示一定要掌握根据线性规划原问题写对偶问题，建议先根据原约束条件的个数确定对偶问题变量数，再写出对偶问题的目标函数和约束条件（留待最后判别约束条件和变量的符号）；写对偶问题方式一是通过标准对称形式进行推导，方式二则可通过记忆对应关系表来直接写出。提《运筹学》考点精讲及复习思一定要记住数学题多是按步骤给分的，能写多少是多少。思考题［２－１］ （留待以后课程讲解）北京科技大学２０１１，三，１８分对于线性规划问题：ｍａｘＳ＝１０ｘ１＋ｓ．ｔ．５ｘ１＋２ｘ２≤８ｘ１≥０，ｘ２≥０１．用单纯形法求解最优解，最优值；２．写出最优基，最优基的逆阵；３．写出对偶规划，对偶规划的最优解。要点２ 单纯形法的矩阵描述单纯形法的矩阵描单纯形法计算的矩阵描述单纯形法的矩阵描述ｓ．设线性规划问题ｍａｘｚｓ．ＡＸ＝０不妨设基Ｂ＝Ｐ１Ｐ２ Ｐｍ则Ａ＝（ Ｐｎ）＝（ 约束方程

ＸＢＡＸ＝ｂ（ Ｎ） ＸＮ＝ＢＸＢ＋ＮＸＮ＝ ＝Ｂ－１（ｂ－ＮＸ）＝Ｂ－１ｂ－Ｂ 令ＸＮ＝０目标函提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５令ＸＮ＝０检验线性规划问题可以等价写成此形式为线性规划对应于基Ｂ的典则形式（典式）。矩阵描述时的常用公式ＸＢ＝Ｂ－１Ｎ＝Ｂ－１ｚｚ０

＝ＣＮ–ＣＢＢ－１＝ＣＢＢ－１当已知一个线性规划的可行基Ｂ时，先求出Ｂ－１，再用这些运算公式可得到单纯形法所要求的结果。单纯形法计算的矩阵描述线性规划问题ｍａｘｚ＝ＡＸ≤ｓ．Ｘ≥化为标准型，引入松弛变量提《运筹学》考点精讲及复习思ｍａｘｚ＝ＣＸ＋ＡＸ＋ＡＸ＋ＩＸｓ＝Ｘ≥０，Ｘｓ≥标准ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ＋ＢＸＢＢＸＢ＋ＮＸＮ＋ＩＸＳ＝ＸＢ，ＸＮ，ＸＳ≥列初始单纯形→初始单纯形ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ＋ＢＸＢＢＸＢ＋ＮＸＮ＋ＩＸＳ＝ＸＢ，ＸＮ，ＸＳ≥初始单纯形表迭代后单纯形提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５检验数应都小于等于０， Ｃ－ＣＢ－１Ｎ≤ Ｂ–ＣＢ－１≤ＢＢＢ又因为基变量的检验数可写成ＣＢ·Ｉ＝０则可将检验数统一ＢＢＢＣ－ＣＢ－１ＡＢ００

令Ｙ＝Ｃ

Ｃ－ＹＡ≤ ＹＡ≥→–ＣＢＢ－１≤ｉｎω＝ ｚ＝ＣＢ－１ｂ＝ ｓ．ｔ．ＹＡ≥

–Ｙ≤ Ｙ≥Ｙ≥从上述推导可看出，检验数行的相反数恰好是其对偶问题的一个可行解。经典例题［２－３］ 胡运权主编《运筹学教程》第三版，Ｐ５４，例３两个互为对偶的线性规划问题，分别再加上了松弛变量和剩余变量后ｍａｘｚ＝

＋

＋

＋

＋

ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３＋０ｙ４＋６６ｙ２＋ｙ３－ｙ４５５ｘ２＋ｘ３＝１１

＋２ｘ＋

＝

＋２ｙ

＋

–ｙ５＝ｓ．ｔ．

ｉ ｘ１＋ｘ２＋ｘ５＝ ｘｊ≥０，ｊ＝１，２，３，４，

ｉ≥

１，２，３，４，用单纯形法和两阶段法求得两个问题的最终单纯形表如下：原问题的最终单纯形表提《运筹学》考点精讲及复习思对偶问题的最终单纯形经典例题［２－２］ 北京交通大学２００９，一、５０分已知线性规划问题如下：ｍｉｎｚ＝

＋

＋１２ｘ＋２ｘ＋１ｘ≥ ２ｓ．ｔ．

＋３ｘ３≥ｘ，ｘ，ｘ≥ １．求该问题的最优解２．写出该线性规划问题的对偶问题，并求对偶问题的最优解３．分别确定ｘｘ３的目标函数系数ｃｃ３在什么范围内变化最优解不变９４．求约束条件右端值９

变

时的最优解５．求增加新的约束条件ｘ１＋２ｘ２＋ｘ３５时的最优解ｍｉｎｚ＝２ｘ＋５ｘ＋１ ２ ｍａｘω＝３ｙ１＋ｘ＋

＋１ｘ≥

ｙ１≤ｓ．ｔ．

２

２ｙ１＋ｙ２≤ｘ２＋３ｘ３≥ ｓ．ｔ． ｘ，ｘ，ｘ≥ ２ｙ１＋３ｙ２≤

单纯形法求解原问题的最终表如下提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ ＝０，０，６，０，９ Ｚ＝ Ｙ＝１，０，１，３， ω＝复习思路提示从上表中可以清楚地看出两个问题变量之间的对应关系。只需求解其中一个问题，从最优解的单纯形表中即可同时得到另一个问题的最优解；注意单纯形乘子为Ｙ＝ＣＢＢ－１，其与对偶变量之间的关系，经常会考察“相差一个负号”的理解；单纯形法的矩阵描述将广泛地应用到灵敏度分析部分中，要学会用Ｂ－１来求解每张表中的未知数值思考题［２－２］ （留待以后课程讲解）昆明理工大学２０１２，二，２５分对于线性规划问题：ｍａｘＳ＝１０ｘ１＋５ｘ２３ｘ１＋４ｘ２≤ｘ１≥０，ｘ２≥１．写出此问题的对偶问题２．求出此问题和它的对偶问题的最优解和最优值。要点３ 线性规划的对偶理论对称弱对偶最优对偶定理（强对偶性互补松弛经典例题［２－ 清华大学教材编写组《运筹学》第三版Ｐ５４，例原问ｍａｘｚ＝２ｘ１＋ｘ１＋２ｘ２≤

对偶问ｍｉｎｗ＝８ｙ１＋１６ｙ２＋ ≤

ｙ１＋４ｙ２≥ｓ．ｔ．４ｘ２≤ｘ，ｘ≥

ｙ１，ｙ２，ｙ３≥ 原问题化为极小问题，初始单纯形表迭代至最终单纯形表

提《运筹学》考点精讲及复习思对偶问题用两阶段法求解的最终单纯形表原问题化为极小化的最终单纯形表两个问题作一比较１．两者的最优值相同ｚ＝ｗ＝２．变量的解在两个单纯形表中互相包含原问题最优解（决策变量）ｘ１＝４，ｘ２＝２←→对偶问题的剩余变量的检验对偶问题最优解（决策变量提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ｙ＝３，

＝１／８，

从引例中可见原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明原问题与对偶问题解的关系对偶问题的基本性质设原问题（１）ｍａｘｚ＝ＣＸＡＸ≤ｓ．Ｘ≥

对偶问题（２）ｗ＝ＹＡ≥ｓ．Ｙ≥—、对称定定理：对偶问题的对偶是原问题。证对称性原问

对偶问ｍａｘｚ＝ＡＸ≤ｓ．Ｘ≥

对 ｉｎω＝ ＹＡ≥ＣＹ≥将对偶问题两边同时取负号，ａｘ－ω＝－据对称标准ｓ．ａｘ＝ｍａｘｚｓ．ａｘ＝ｍａｘｚ＝

ｉｎ（－ω＝－ｓ．–ＡＸ≥－ｓ．Ｙ≥

ｓ．

ＡＸ≤ｂＸ≥０

Ｘ≥二、弱对偶性定 若Ｘ和 分别是原问题（１）及对偶问题（２）的可行解，则有ＣＸ≤ － 证明：ＡＸｂＹＡＸ – ＹＡ≥ ＹＡＸ≥ － →ＣＸ≤ＹＡＸ≤ 从弱对偶性ＣＸＹｂ可得到以下重要结论（１）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。提《运筹学》考点精讲及复习思（２）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（３）若原问题可行，但其目标函数值无界，则对偶问题无可行解（４）若对偶问题可行，但其目标函数值无界，则原问题无可行解（５）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界（６）若原问题无可行解，则其对偶问题具有无界解或无可行解三、最优性定若Ｘ和Ｙ分别是（１）和（２）的可行解，且有ＣＸ＝Ｙｂ，则Ｘ，Ｙ分别是（１）和（２）的最优解 证明：因为（１）的任一可行解Ｘ均满足ＣＸＹ–∵ＣＸ＝Ｙ ∴ＣＸ≤则Ｘ为（１）的最优解反过来可知：Ｙ也是（２）的最优解。四、对偶定理（强对偶性）Ｂ若原问题有最优解，那么对偶问题也有最优解，且两者的目标函数值相等。证明：设Ｘ是原问题的最优解，则其对应的基Ｂ必存在ＣＣＢ－１Ａ≤０．Ｂ∵Ｙ＝ ∴ＹＡ≥即Ｙ使对偶问题的可行解，Ｂω＝Ｙｂ＝ＣＢ－１ＢＢＸ＝Ｂ－１ｂｚ＝ＣＸ＝ＣＢ－１ＢＢ∴ＣＸ＝ＣＢ－１ｂ＝ＹＢ∴据最优性定理可知，Ｙ是对偶问题的最优解。原问题与对偶问题的解，一般有三种情况：一个有有限最优 →另一个有有限最优解一个有无界 →另一个无可行解两个均无可行解。五、互补松弛性＾ 若Ｘ，Ｙ分别是原问题（１）与对偶问题（２）的可行解，，ＹＳ分别为（１）、（２）的松弛变量，则： ＾＝０，＝０Ｘ，Ｙ为最优提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５证：设原问题和对偶问题的标准型原问题ＹＡ－ＹＳ＝ｓ．Ｘ，ＸＳ≥

对偶问题ｉｎω＝ＹｂＡＸ＋ＸＳ＝ｓ．Ｙ，ＹＳ≥ｚ＝ＹＡ－ＹＳＸ＝ＹＡＸ－ＹＳω＝ＹＡＸ＋ＸＳ＝ＹＡＸ＋ ∧ 若＝０，ＹＸＳ＝０；则ω＝Ｙｂ＝ＹＡＸ＝ＣＸ＝∧由最优性质，可知Ｘ，Ｙ是最优解∧ 又若Ｘ，Ｙ分别是原问题和对偶问题的最优解，根据最优性质有，ＣＸ＝ ∧ ｚ＝ＣＸ＝ＹＡ－ＹＳＸ＝ＹＡＸ－ＹＳ ∧ ω＝Ｙｂ＝ＹＡＸ＋ＸＳ＝ＹＡＸ＋∧→ＹＳ

＝ＹＸＳ＝经典例题［２南京航天航空大学２０１０，一、简答，５分１．简述互补松弛性的内涵。南京航天航空大学２０１１，一、简答，５分２．简述对偶问题的互补松弛性南京航天航空大学２０１２，一、简答，５分４．何谓互补松弛性。经典例题［２］：清华大学教材编写组《运筹学》第三版Ｐ５９，例５已知线性规划问题ｉｎ＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋ｓ．ｔ．ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３ｘｊ≥０，ｊ＝１，２，…，已知其对偶问题的最优解为 ＝４， ＝３；ｚ＝５。试用对偶理论找出原问题的最优解 解：先写出其对偶问题ｍａｘｚ＝４ｙ１＋３ｙ２ｙ１＋２ｙ２≤ｙ１–ｙ２≤ｓ．

＋３ｙ２≤ｙ１＋ｙ２≤３ｙ１＋ｙ２≤ ｙ，ｙ≥ 提《运筹学》考点精讲及复习思由互补松弛性，可ＹＳＸ＝０ ＝∵ｙｓ２，ｙｓ３，ｙｓ４＞ ５∴ ＝ ＝ ５ ∴由题可

>０， ＞ｙ＝

>０， ＝３＞ 由互补松弛性Ｙ

＝０

ｓｉ∴ｘｓ１＝ｘｓ２＝０原问题ｎ＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋ｓ．ｔ．ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３ｘｊ≥０，ｊ＝１，２，…，ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５＝４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５＝３因此，得到１＋ １４ ＋ ３

＝ ＝ 原问题的最优解为Ｘ＝１，０，０，０，１ ＝说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。复习思路提示（１）对偶问题的性质通常用小题型来考察，如选择、判断和填空等，分值大致在５分左右提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５（２）若考察大题，则通常也只作为大题中的一个小题，考察内容可能是从已知的对偶问题的最优解，求原问题最优解，反之亦然证实原问题可行解是否为最优解（３）牢记定理，证明过程略懂即可，以防万一出相关证明题。思考题［２－３］ （留待以后课程讲解）北京科技大学２０１１，一、（１）填空，２若对偶问题为无界解，则原问题 中山大学２００９，一、（３）多项选择，５分２．下列说法正确的有 Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；Ｃ．已知ｙ为线性规划对偶问题的最优解，若ｙ >０则说明在最优生产计划中第ｉ种资源已完全耗尽； Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增大ｋ；Ｅ．任何线性规划问题具有唯一的对偶问题。要点 影子价 在单纯形法的每步迭代中，目标函数取值ｚ＝ＣＢ－ｂ，和检验数Ｃ－ＣＢ－Ｎ中都有乘子Ｙ＝ＣＢ－１，那么 经济意义是什么Ｂ影子价当线性规划原问题求得最优解ｘ（ｊ＝１，…，ｎ）时，其对偶问题也得到最优解ｙ（ｉ＝１，…，ｍ 且代入各自的目标函数后有ｎｚ＝ｊ

＝ ＝ｉ 是线性规划原问题约束条件的右端项，它代表第ｉ种资源的拥有量影子价格的定义（对偶变量

的意义代表在资源最优利用条件下对单位第ｉ种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（ｓｈａｄｏｗｐｒｉｃｅ）。经典例题［２深圳大学２０１１，一、填空（１），２线性规划最优生产计划中第ｉ种资源有剩余，则该资源的影子价格为 。北京交通大学２０１０，一、判断（３），２分３．影子价格大于０，表示其对应资源已完全消耗完。南京航天航空大学２０１１，二、简答（１），５分１．简述影子价格及其经济意义南京航天航空大学２０１２，一、简答（１），５提《运筹学》考点精讲及复习思１．简述影子价格的含义原问题化为极小化的最终单纯形表影子价格的经济意∑【１】影子价格是一种边际价格∑在ｚ

∑ｃ

＝ｍｂ ＝ｗ中 ＝ｉｂｊ ｉｉｂｊ ｉ 说明增量

的值相当于在资源得到最优利用的生产条件下，ｂｉ每增加一个单位时目标函数ｚ几何解释：图解法分析ｍａｘｚ＝２ｘ１＋３ｘ２ｘ１＋２ｘ２≤４ｘ１≤１６４ｘ２≤【详见课程视频【２】影子价格又是一种机会成本ｙ＝３，ｙ＝１，ｙ＝ 在纯市场经济条件下，当第２种资源的市场价格低于１／８时，可以买进这种资源当市场价格高于影子价格时，就会卖出这种资源随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同水平时，才处于平衡状态【３】在对偶问题的互补松弛性质中提考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课 电话：４００６８８５ 当∑ｊ＜ｂｉ时，ｙｉ＝ｊ 当ｙ＾ｉ＞０时，∑ｊ＝ｊ这表明生产过程中如果某种资源ｂｉ未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。复习思路提示（１）影子价格考察的内容通常就两部分影子价格大于或等于０所代表的资源消耗情况简述影子价格的经济意义（２）考察分值在５分以内，以选择和判断多见。思考题［２－３］ （留待以后课程讲解）中山大学２００９，一、（３）多项选择，５分３．下列说法正确的有（ Ａ．若原问题及其对偶问题均具有可行解，则他们的目标函数值相等Ｂ．若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；Ｃ．已知ｙ为线性规划对偶问题的最优解，若ｙ >０则说明在最优生产计划中第ｉ种资源已完全 耗尽Ｄ．若某种资源的影子价格为ｋ，在其他条件不变时，该种资源增长１个单位，相应目标函数值增ｋＥ．任何线性规划问题具有唯一的对偶问题。要点５ 对偶单纯形法对偶单纯形法的基本思对偶单纯形法的计算步原问题每次迭代的单纯形表的检验数行对应其对偶问题的一个基解。设原问题和对偶问题的标准型是原问 对偶问ｍａｘｚ＝ ｍｉω＝ｓ．

ＡＸ＋ＸＳ＝ｂＸ，ＸＳ≥０

ｓ．

ＹＡ－