《运筹学》考研考点讲义.pdf

目录第一章线性规划与单纯形法（）?第二章对偶问题与灵敏度分析（）?第三章运输问题（）?第四章目标规划（）?第五章整数规划（）?第六章动态规划（）?第七章图与网络优化（）?第八章网络计划技术（）?第九章存储论（）?第十章排队论（）?第十一章决策论（）?第一章线性规划与单纯形法一、本章考情分析：常考题型：选择、填空、简答、判断和计算分值：必考知识点，分值占 分以上重要性：作为前五章的基础铺垫，非常重要！重要程度：二、本章基本内容：）掌握线性规划的数学模型的标准型；）掌握线性规划的图解法及几何意义；）了解单纯形法原理；）熟练掌握单纯形法的求解步骤；）能运用大 法与两阶段法求解线性规划问题；）熟练掌握线性规划几种解的性质及判定定理三、本章重难点：重点：）单纯形法求解线性规划问题；）解的性质；）线性规划问题建模难点：）单纯形法原理的理解；）线性规划问题建模四、本章要点精讲：要点 化标准型要点 图解法要点 单纯形法的原理要点 单纯形法的计算步骤要点 单纯形法的进一步讨论要点 化标准型线性规划的数学模型 运筹学 考点精讲及复习思路线性规划的共同特征决策变量 ：每个问题都用一组决策变量表示某个方案决策变量 ：决策变量的取值一般都是非负且连续的约束条件 ：与决策变量不矛盾的条件，用线性等式或不等式表示目标函数 ：决策变量与价值系数组成，一般要求实现最大或最小化【建模思路】确定决策变量写出目标函数找出约束条件线性规划的标准型可简化为 ，经典例题 胡运权，运筹学教程（三），例 与南京航空航天大学 年，第四题类似，分 ，取值无约束【】目标函数最大【】资源限量（右端项）非负【】约束条件等式松弛变量与剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。【】决策变量非负整理，得 ，目标函数最大约束条件等式决策变量非负资源限量非负经典例题 天津大学 ，二，（），约 分 运筹学 考点精讲及复习思路某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动 表 给出了公司准备做广告的三种产品名称、估计每做一单位广告使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量分别为 请写出此问题的线性规划模型，并将模型化为标准型其中洗衣粉的市场份额出现负值是由液体洗涤剂的份额增加造成的电视印刷媒体广告后市场份额最低增量去污剂 液体洗涤剂 洗衣粉 广告单位成本（万元）解：设电视的广告数量为，印刷媒体的广告数量为 ，化为标准型后 ，复习思路提示：初学时，化标准型可按“目标函数资源限量约束条件决策变量”的顺序进行，化完后默念四句口诀验证；化标准型是用单纯形法求解线性规划问题的第一步，非常重要！而单纯形法求解线性规划问题是每年必考大题，此步错，后面展开步步错！要点 图解法图解法求解步骤：经典例题 胡运权，运筹学教程（三），例 ，【详见课程视频】图解法的几点启示：线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；若线性规划的可行域存在，则可行域一定是个凸集；若线性规划的最优解存在，则最优解或最优解之一（无穷多解时）一定是可行域的凸集的某个顶点；解题思路：找出凸集的顶点，计算其目标函数值，比较即得。图解法启示的解题思路经典例题 天津大学 ，一、选择（），分用图解法解线性规划时，以下几种情况不可能出现的是（）可行域有界，无有限最优解（或称无界解）可行域无界，有唯一最优解 可行域是空集，无可行解 可行域有界，有多重最优解复习思路提示：要会用图解法来分析线性规划的几种解的情况，如唯一最优解、无穷多解、无界解和无可行解；运筹学 考点精讲及复习思路图解法容易在确定可行域的范围和等值线移动方向上犯错；图解法的知识点通常出现在选择、填空、判断等小题型中！大致分值在 分以内思考题 （留待以后课程讲解）南京航空航天大学 ，一、多项选择 、，各 分 线性规划的最优解可在（）可行集内 可行集边界上 可行集顶点上 满足其约束条件的区域上 线性规划的可行集可以（）不含有任何可行解 恰含有一个可行解 恰含有两个可行解 含有无数个可行解思考题 （留待以后课程讲解）南京航空航天大学 ，第二题，分二、（分）用图解法求解线性规划问题 ，要点 单纯形法原理解的概念与关系单纯形法迭代原理 解的概念与关系线性规划的标准型为 ，【向量形式】，【矩阵形式】线性规划问题解的概念 （），（），（）可行解：满足约束条件（）和（）的解（，）全部可行解的集合称为可行域。最优解：使目标函数（）达到最大值的可行解。基：设 是约束方程组（）的 阶系数矩阵（设 ），其秩为 ，是 中的一个 阶的满秩子矩阵（的非奇异子矩阵），称 是线性规划问题的一个基 不失一般性，设除基变量以外的变量称为非基变量基解：在约束方程组（）中，令所有的非基变量 ，又因为，据克莱姆法则，对于 ，()基解可以求出唯一解，()（），（），（）基可行解：满足变量非负约束条件（）的基解可行基：对应基可行解的基经典例题 胡运权，运筹学教程（三），例 找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解 运筹学 考点精讲及复习思路 ，【详见课程视频】凸集、顶点及几个定理设 是 维欧氏空间的一点集，若（），（）的连线上的所有点（）（）（），），则称 为凸集设 是凸集，；若 不能用不同的两点（）和（）的线性组合表示为 （）（）（），（）则称 为 的一个顶点（或极点）定理 若线性规划问题存在可行解，则问题的可行域是凸集（天津大学 年第三题证明，分）引理线性规划问题的可行解为基可行解的充要条件是 的正分量所对应的系数列向量是线性独立的定理 线性规划问题的基可行解 对应线性规划问题可行域（凸集）的顶点定理 若线性规划问题有最优解，一定存在一个基可行解是最优解几个定理考察的通常是小题型，需要牢记结论，且理解各个解之间的关系。几点结论：【】可行域若有界则是凸集，也可能是无界域；【】每个基可行解对应可行域的一个顶点；【】可行域有有限多个顶点；【】如果有最优解，必在某个顶点上得到线性规划解之间的关系归纳“箭尾的解一定是箭头的解，反之不一定成立”当最优解唯一时，最优解也是基最优解；当最优解不唯一时，最优解不一定是基最优解经典例题 南京航空航天大学，一、判断（），分一、判断下列说法是否正确）若线性规划问题的可行解为最优解，则该可行解必定是基可行解（）经典例题 北京交通大学，一、判断（），分一、判断下列说法是否正确）线性规划问题的每一个基解对应可行域的一个顶点（）单纯形法的迭代思路：单纯形法的迭代原理 ，【】构造初始可行基，()直接观察一个可行基 约束，加松弛变量；约束，加人工变量（后面会讨论）（为讨论方便，设均为约束）【】基变换：两个基可行解相邻，两者可变换且仅变换一个基变量 运筹学 考点精讲及复习思路设初始基可行解为：写出系数矩阵的增广矩阵：可得 移项得 上式乘以一个正数，得 ()()由 ()可找到满足原约束方程组 的另一个点：()，()要使()是一个基可行解，则应对所有 ，存在 （先要使其可行）令这 个不等式至少有一个等号成立，且当 时，上式显然成立，故可令 可确保 ，是可行解。此时与，对应的向量：【】最优性检验和解的判别将上述（），（）分别代入目标函数 ，得()()()()()()()()()()（）当所有 ，当前顶点（基可行解）的目标函数值已是最大，即为最优解；（）当所有 ，又某个非基变量 的检验数为，则在另一个顶点也使目标函数达到最大，两点连线上的所有点都是最优解，即无穷多最优解 当所有非基变量的 时，有唯一最优解；（）若存在某个 ，而其对应的非基向量 ，则从 值和（）的表达式可看出，线性规划有无界解 线性规划解的判别定理归纳：最优解判别定理若（）（，）为基可行解，且全部 ，则（）为最优解唯一最优解判别定理若（）（，）为基可行解，且全部，则（）为唯一最优解无穷多最优解判别定理若（）（，）为基可行解，且全部，且存在一个非基 运筹学 考点精讲及复习思路变量 的 ，则存在无穷多最优解无界解判别定理若有一个非基变量 的 ，而其对应非基变量的所有系数 ，则具有无界解。复习思路提示：掌握线性规划几个解的概念及几何意义，会用该知识点求解考研试题中的各类小题型；会在简答题中对单纯形法的迭代思路进行描述；了解单纯形法的迭代原理，牢记解的判别定理思考题 （留待以后课程讲解）中山大学 ，一、选择（）分在标准形式下线性规划问题的单纯形迭代过程中，若有某个 对应的非基变量 的系数列向量（）时，则此问题是无界的。北京交通大学 ，一、判断（）分单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。）写出该线性规划的标准型（分）；）求原规划的最优解和最优目标函数值（）要点 单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。【】求初始基可行解，列出初始单纯形表 【】最优性检验【】基变换）确定换入基的变量只要有检验数大于 ，对应的变量就可作为换入变量，当有一个以上检验数大于 时，一般从中选取最大的一个：其对应的变量 作为换入变量。）确定换出基的变量根据确定 最小比值规则，对 列计算可得：其对应的变量 作为换出变量。元素 决定了从一个基可行解到相邻基可行解的转移去向，称之为主元素。）迭代变换用换入变量 去替换基变量中的换出变量，得到一个新的基（，）。对应这个基可以找出一个新的基可行解，并相应地可以画出一张新的单纯形表。【详见课程视频】经典例题 南航，二、计算题，（）分二、（分）已知线性规划问题：运筹学 考点精讲及复习思路 ，）用单纯形法求解；【详见课程视频】在上面的例题 中，考虑以下两个问题：）若初始单纯形表中，若用检验数 对应的 作为换入变量会带来什么样的结果？）用图解法求解该题，看每张单纯形表对应的解与可行域中的顶点如何对应？基变换是否是相邻的顶点间进行变换？最优解在哪个顶点取得？复习思路提示：正确的标准型是单纯形法求解线性规划问题的前提；会依据标准型列出初始单纯形表（重点是正确找出初始基及对应的初始基变量）；熟练运用矩阵的初等行变换进行单纯形表迭代（最容易犯计算错误）；牢记最优性检验的几个解的判别定理（当遇到无穷多最优解和无界解的情况）。思考题 （留待以后课程讲解）中山大学 ，三，分用单纯形表求解以下线性规划问题：，要点 单纯形法的进一步讨论考虑：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？，线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，添加人工变量！“惩罚”人工变量！大 法和两阶段法【】大 法人工变量在目标函数中的系数为 ，其中 为任意大的正数。经典例题 清华大学运筹学编写组（三）例 ，运筹学 考点精讲及复习思路解：）首先化标准型，）添加人工变量，构造初始可行基 ，其中，为任意大的正数。求解结果出现所有检验数非正，若基变量中含非零的人工变量，则无可行解；否则，有最优解。）列初始单纯形表如下第一步迭代，得表 第二步迭代，得表 第三步迭代得最终表（所有检验数小于等于 ）【】两阶段法第一阶段：加入人工变量后，构造仅含人工变量的目标函数，并要求其实现最小化；第二阶段：将一阶段得到的最终表除去人工变量。将目标函数行的系数换成原问题的目标函数系数，作为二阶段的初始表。同上例：，解：）添加人工变量，给出一阶段的数学模型 ，运筹学 考点精讲及复习思路，()是原线性规划问题的基可行解。）将一阶段最终表中的人工变量取消填入原问题的目标函数的系数，进行第二阶段计算。单纯形法中的几个问题：退化基可行解中存在基变量等于 的解（退化解），迭代后目标函数值不变，即不同的基表示为同一个顶点。勃兰特（）规则：）当遇到相同检验数时，选取对应下标最小的非基变量作为换入变量；）当存在两个及以上相同的最小比值时，选取下标最小的基变量作为换出变量。检验数的几种判别形式复习思路提示：人工变量是人为加入的，与决策变量、松弛变量有本质的区别，若线性规划有最优解，人工变量必为 ，以保持原约束条件不变。为了使人工变量为 ，就要使人工变量从基变量中换出成非基变量；大 法和两阶段法通常不会直接出成计算大题，会在一些小题型中考察这两种方法的注意事项。大致分值 分以内。思考题 两阶段法中，若第一阶段目标函数最优值不为 ，则原问题。【北京科技大学】简述大 法的算法步骤。【南京航空航天大学】经典试题讲解与本章小结一、经典试题讲解思考题 线性规划的最优解可在（）。【南京航空航天大学】可行集内 可行集边界上 可行集顶点上 满足其约束条件的区域上 线性规划的可行集可以（）。【南京航空航天大学】不含有任何可行解 恰含有一个可行解 恰含有两个可行解 含有无数个可行解 线性规划问题的每一个基解对应可行域的一个顶点。【北京交通大学，判断】下面命题正确的是（）【昆明理工大学，单选】线性规划的最优解是基可行解 基可行解不一定是基本解 线性规划一定有可行解 线性规划的最优值至多有一个思考题 （分）用图解法求解线性规划问题。【南京航空航天大学】，若线性规划的可行解为最优解，则该可行解必定是基可行解。【南京航天航空大学，判断】若，分别是某一线性规划问题的最优解，则 也是该线性规划问题的最优解，其中，为正实数。【南京航天航空大学，判断】运筹学 考点精讲及复习思路思考题 在标准形式下线性规划问题的单纯形迭代过程中，若有某个 对应的非基变量 的系数列向量（）时，则此问题是无界的。【中山大学】单纯形法计算中，取最大正检验数对应变量换出，所得解上升最快。【北京交通大学判断】分析：，对任意 ，即解都可行，（）当?，?思考题 用单纯形表求解以下线性规划问题：【中山大学】，解：化标准型，并列出初始单纯形表 ，迭代得表 迭代得最终表，()思考题 两阶段法中，若第一阶段目标函数最优值不为 ，则原问题【北京科技大学】简述大 法的算法步骤。【南京航空航天大学】二、本章小结【】标准型 目标函数最大约束条件等式资源限量非负决策变量非负【】图解法 运筹学 考点精讲及复习思路可行域若有界则是凸集，也可能是无界域；每个基可行解对应可行域的一个顶点；可行域有有限多个顶点；如果有最优解，必在某个顶点上得到【】线性规划解之间的关系归纳“箭尾的解一定是箭头的解，反之不一定成立”当最优解唯一时，最优解也是基最优解；当最优解不唯一时，最优解不一定是基最优解进行标准化，列初始单纯形表方法【】单纯形法计算步骤框图【】人工变量法 大 法【】人工变量法 两阶段法一阶段目标函数最优值为 ，则去掉人工变量转入第二阶段；不为 ，则原问题无可行解，停止计算。本章涉及的知识点大部分是每年的必考题，分值约占 ，其中解的性质及判定通常会出现在填空、选择或简答、判断等小题型中，而单纯形法求解是每年必考的一道大题，常与第二章对偶问题联合出题，涉及分值有时高达 分以上。运筹学 考点精讲及复习思路第二章对偶问题与灵敏度分析一、本章考情分析：常考题型：选择、填空、简答、判断和计算分值：必考知识点，分值在 分之间重要性：每年必考，影子价格及灵敏度分析实际应用很多重要程度：二、本章基本内容：）熟练掌握原问题与对偶问题的转化关系（记忆转化关系表或用对称形式推导）；）熟练掌握单纯形法的矩阵描述；）掌握对偶问题的几条基本性质；）熟练掌握影子价格的经济意义；）能运用对偶单纯形法求解线性规划问题；）熟练掌握灵敏度分析，包括 ，和增加约束条件的变化。三、本章重难点：重点：）根据原问题写出对偶问题；）能通过单纯形法的矩阵描述，从单纯形表求原问题和对偶问题的最优解；）灵敏度分析中，分析各系数在什么范围内变化，最优解不变，或各系数变化后，最优解是否改变。难点：对偶问题的性质的理解。四、本章要点精讲：要点 线性规划的对偶问题要点 单纯形法的矩阵描述要点 线性规划的对偶理论要点 影子价格要点 对偶单纯形法要点 灵敏度分析要点 线性规划的对偶问题对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的对应关系对偶问题的提出经典例题 胡运权主编 运筹学教程 第三版，例 美佳公司利用现有资源生产两种产品，有关数据如下产品产品资源限量设备 设备 调试工序 时 时时利润（元）美佳公司考虑：如何安排生产，使获利最多？设：产量 ；产量 ，收购方：收购美佳公司的资源，付出多少代价才能使美佳公司愿意放弃生产活动出让自己的资源呢？美佳公司：出让代价应不低于同等数量的资源自己生产的利润。设：设备 元 时设备 元 时调试工序 元 时建立如下线性规划问题：运筹学 考点精讲及复习思路 ，特点：限定向量 价值向量（资源向量）一个约束 一个变量 的 约束“”的 是“”的约束。变量都是非负限制。原问题与对偶问题的数学模型【】对称形式的对偶原问题和对偶问题只含有不等式约束。情形一：情形二：将原问题化成标准对称型 根据标准对称型写出对偶 【】非对称形式的对偶原问题的约束是等式推导过程原问题 （，）（，），（）（），令，得对偶问题为：无约束证毕。运筹学 考点精讲及复习思路原问题和对偶问题的对应关系经典例题 北京交通大学 ，一、分已知线性规划问题如下：，求该问题的最优解；写出该线性规划问题的对偶问题，并求对偶问题的最优解；分别确定，的目标函数系数，在什么范围内变化最优解不变？求约束条件右端值由()变为()时的最优解；求增加新的约束条件 时的最优解。，复习思路提示：一定要掌握根据线性规划原问题写对偶问题，建议先根据原约束条件的个数确定对偶问题变量数，再写出对偶问题的目标函数和约束条件（留待最后判别约束条件和变量的符号）；写对偶问题方式一是通过标准对称形式进行推导，方式二则可通过记忆对应关系表来直接写出。一定要记住数学题多是按步骤给分的，能写多少是多少。思考题 （留待以后课程讲解）北京科技大学 ，三，分对于线性规划问题：，用单纯形法求解最优解，最优值；写出最优基，最优基的逆阵；写出对偶规划，对偶规划的最优解。要点 单纯形法的矩阵描述单纯形法的矩阵描述单纯形法计算的矩阵描述单纯形法的矩阵描述设线性规划问题 不妨设基为()则（）（）约束方程组 （）（）令 得目标函数 运筹学 考点精讲及复习思路令 得检验数线性规划问题可以等价写成：此形式为线性规划对应于基 的典则形式（典式）。矩阵描述时的常用公式 当已知一个线性规划的可行基 时，先求出 ，再用这些运算公式可得到单纯形法所要求的结果。单纯形法计算的矩阵描述线性规划问题 化为标准型，引入松弛变量 ，标准型 ，列初始单纯形表初始单纯形表 ，初始单纯形表：迭代后单纯形表 运筹学 考点精讲及复习思路检验数应都小于等于 ，即 又因为基变量的检验数可写成 则可将检验数统一写为 令 从上述推导可看出，检验数行的相反数恰好是其对偶问题的一个可行解。经典例题 胡运权主编 运筹学教程 第三版，例 两个互为对偶的线性规划问题，分别再加上了松弛变量和剩余变量后：，用单纯形法和两阶段法求得两个问题的最终单纯形表如下：原问题的最终单纯形表对偶问题的最终单纯形表经典例题 北京交通大学 ，一、分已知线性规划问题如下：，求该问题的最优解；写出该线性规划问题的对偶问题，并求对偶问题的最优解；分别确定，的目标函数系数，在什么范围内变化最优解不变？求约束条件右端值由()变为()时的最优解；求增加新的约束条件 时的最优解。，单纯形法求解原问题的最终表如下：运筹学 考点精讲及复习思路，()，()复习思路提示：从上表中可以清楚地看出两个问题变量之间的对应关系。只需求解其中一个问题，从最优解的单纯形表中即可同时得到另一个问题的最优解；注意单纯形乘子为 ，其与对偶变量之间的关系，经常会考察“相差一个负号”的理解；单纯形法的矩阵描述将广泛地应用到灵敏度分析部分中，要学会用 来求解每张表中的未知数值。思考题 （留待以后课程讲解）昆明理工大学 ，二，分对于线性规划问题：，写出此问题的对偶问题；求出此问题和它的对偶问题的最优解和最优值。要点 线性规划的对偶理论对称性弱对偶性最优性对偶定理（强对偶性）互补松弛性经典例题 清华大学教材编写组 运筹学 第三版 ，例 原问题 ，对偶问题 ，原问题化为极小问题，初始单纯形表：迭代至最终单纯形表：对偶问题用两阶段法求解的最终单纯形表：原问题化为极小化的最终单纯形表：两个问题作一比较：两者的最优值相同 变量的解在两个单纯形表中互相包含原问题最优解（决策变量），对偶问题的剩余变量的检验数对偶问题最优解（决策变量）运筹学 考点精讲及复习思路，原问题的松弛变量的检验数从引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系对偶问题的基本性质设原问题（）对偶问题（）一、对称定理定理：对偶问题的对偶是原问题。证对称性原问题 对偶 对偶问题 将对偶问题两边同时取负号，得 （）据对称标准形 （）二、弱对偶性定理若 和分别是原问题（）及对偶问题（）的可行解，则有 证明：从弱对偶性 可得到以下重要结论：（）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（）若原问题可行，但其目标函数值无界，则对偶问题无可行解。（）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（）若原问题无可行解，则其对偶问题具有无界解或无可行解。三、最优性定理若 和 分别是（）和（）的可行解，且有 ，则，分别是（）和（）的最优解。证明：因为（）的任一可行解 均满足 则 为（）的最优解，反过来可知：也是（）的最优解。四、对偶定理（强对偶性）若原问题有最优解，那么对偶问题也有最优解，且两者的目标函数值相等。证明：设 是原问题的最优解，则其对应的基 必存在 即 使对偶问题的可行解，则 据最优性定理可知，是对偶问题的最优解。原问题与对偶问题的解，一般有三种情况：一个有有限最优解另一个有有限最优解。一个有无界解另一个无可行解。两个均无可行解。五、互补松弛性若，分别是原问题（）与对偶问题（）的可行解，分别为（）、（）的松弛变量，则：，为最优解 运筹学 考点精讲及复习思路证：设原问题和对偶问题的标准型是原问题 ，对偶问题 ，()()若 ，；则 ，由最优性质，可知，是最优解。又若，分别是原问题和对偶问题的最优解，根据最优性质有，()()经典例题 南京航天航空大学 ，一、简答，分 简述互补松弛性的内涵。南京航天航空大学 ，一、简答，分 简述对偶问题的互补松弛性南京航天航空大学 ，一、简答，分 何谓互补松弛性。经典例题 ：清华大学教材编写组 运筹学 第三版 ，例 已知线性规划问题 ，已知其对偶问题的最优解为，；。试用对偶理论找出原问题的最优解。解：先写出其对偶问题 ，由互补松弛性，可知 ，由题可知，由互补松弛性，原问题 ，因此，得到 原问题的最优解为 ，()说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。复习思路提示：（）对偶问题的性质通常用小题型来考察，如选择、判断和填空等，分值大致在 分左右；运筹学 考点精讲及复习思路（）若考察大题，则通常也只作为大题中的一个小题，考察内容可能是：从已知的对偶问题的最优解，求原问题最优解，反之亦然。证实原问题可行解是否为最优解。（）牢记定理，证明过程略懂即可，以防万一出相关证明题。思考题 （留待以后课程讲解）北京科技大学 ，一、（）填空，分若对偶问题为无界解，则原问题。中山大学 ，一、（）多项选择，分 下列说法正确的有（）若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；已知为线性规划对偶问题的最优解，若 则说明在最优生产计划中第 种资源已完全耗尽；若某种资源的影子价格为，在其他条件不变时，该种资源增长 个单位，相应目标函数值增大；任何线性规划问题具有唯一的对偶问题。要点 影子价格在单纯形法的每步迭代中，目标函数取值 ，和检验数 中都有乘子 ，那么 的经济意义是什么？影子价格当线性规划原问题求得最优解（，）时，其对偶问题也得到最优解（，），且代入各自的目标函数后有：是线性规划原问题约束条件的右端项，它代表第 种资源的拥有量；影子价格的定义（对偶变量 的意义）代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（）。经典例题 深圳大学 ，一、填空（），分线性规划最优生产计划中第 种资源有剩余，则该资源的影子价格为。北京交通大学 ，一、判断（），分 影子价格大于 ，表示其对应资源已完全消耗完。南京航天航空大学 ，二、简答（），分 简述影子价格及其经济意义。南京航天航空大学 ，一、简答（），分 简述影子价格的含义。原问题化为极小化的最终单纯形表：影子价格的经济意义【】影子价格是一种边际价格。在 中，说明 的值相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数 的增量。几何解释：图解法分析 ，【详见课程视频】【】影子价格又是一种机会成本，在纯市场经济条件下，当第 种资源的市场价格低于 时，可以买进这种资源；当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。【】在对偶问题的互补松弛性质中有 运筹学 考点精讲及复习思路当 时，；当 时，这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。复习思路提示：（）影子价格考察的内容通常就两部分：影子价格大于或等于 所代表的资源消耗情况；简述影子价格的经济意义。（）考察分值在 分以内，以选择和判断多见。思考题 （留待以后课程讲解）中山大学 ，一、（）多项选择，分 下列说法正确的有（）若原问题及其对偶问题均具有可行解，则他们的目标函数值相等；若原问题有无界解，则其对偶问题无可行解；若对偶问题无可行解时，其原问题具有无界解；已知 为线性规划对偶问题的最优解，若 则说明在最优生产计划中第 种资源已完全耗尽；若某种资源的影子价格为 ，在其他条件不变时，该种资源增长 个单位，相应目标函数值增大；任何线性规划问题具有唯一的对偶问题。要点 对偶单纯形法对偶单纯形法的基本思路对偶单纯形法的计算步骤原问题每次迭代的单纯形表的检验数行对应其对偶问题的一个基解。设原问题和对偶问题的标准型是原问题对偶问题 ，决策变量检验数 对应 对偶单纯形法的基本思路对偶单纯形法的计算步骤线性规划问题 不妨设（，）为对偶问题的初始可行基，则 。若 ，即表中原问题和对偶问题均为最优解，否则换基。【】列初始单纯形表，检查 列的数字若都为非负，检验数都为非正，则已得到最优解。停止计算。至少还有一个负分量，检验数保持非正，转 ；【】确定换出变量 ()()()对应的 为换出变量。【】确定换入变量在单纯形表中检查所在行的各系数，若所有 ，则无可行解，停止计算。若存在 ，计算 对应的 为换入变量。【】以 为主元素，按原单纯形表的迭代在表中进行迭代运算。经典例题 胡运权 运筹学教程 第三版，例 用对偶单纯形法求解线性规划问题：，【详见课程视频】对偶单纯形法的优点不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数；在灵敏度分析中，有时需要用对偶单纯形法处理简化。对偶单纯形法缺点 运筹学 考点精讲及复习思路在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。复习思路提示：（）对偶单纯形法很少出单独的一道大计算题，考察分值通常在 分以内，也有可能不考察；（）要充分理解对偶单纯形法的算法思路，它也是单纯形法的一种。思考题 南京航天航空大学 ，一、简答（），分 简述对偶单纯形法的算法步骤。要点 灵敏度分析灵敏度问题四种情况分析本节内容灵敏度问题的分析背景线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化 值变化；工艺的变化 值变化；资源的变化 值变化。问题是：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？灵敏度分析的研究内容研究线性规划中，的变化对最优解的影响。灵敏度分析的研究方法经典例题 胡运权 运筹学教程 第三版，例 美佳公司利用现有资源生产两种产品，有关数据如下：产品产品资源限量设备 设备 调试工序 时 时时利润（元）厂家如何安排生产，使获利最多？设：产量 ，产量 ，原问题的最终单纯形表：【】分析 的变化的变化仅影响 ，即原最优解的可行性可能会变化：可行性不变，则原最优解不变。可行性改变，则原最优解改变，用对偶单纯形法，找出最优解。问题 ：设备 的能力增加到 小时（增加了 小时），原最优计划有何变化？代入最终单纯形表中 运筹学 考点精讲及复习思路换基迭代得：问题 ：设设备 的能力为 小时（增加了 小时），新最优解的值的可允许变化范围是多少？计算，得 ，【】分析 的变化的变化仅影响 的变化。设备 设备 调试工序 时 时时利润（元）问题 ：当 ，该公司最优生产计划有何变化？代入最终单纯形表新的单纯形表换基后单纯形表为问题 ：设产品利润为（），求原最优解不变时 的范围。方法：的变化仅影响 的变化；在最后一张单纯形表中求出变化的；原最优解不变，即 ；由上述不等式可求出 的范围。产品利润为（）时的最终单纯形表【】分析 的变化增加一种新产品，即增加一个新变量；若 对应的变量 为基变量，将改变。）迭代后原问题和对偶问题都是可行解；）原问题和对偶问题均非可行解时，需引入人工变量求出可行解，再用单纯形法求解。产品甲产品乙资源限量设备台时原材料 千克原材料 千克利润元元 运筹学 考点精讲及复习思路 ，最终单纯形表：）增加一个变量 的分析增加一个变量相当于增加一种产品。分析步骤：计算 计算 若 ，原最优解不变；若，则按单纯形表继续迭代，计算找出最优解。问题 ：设生产第三种产品，产量为 件，对应的 ，（，），求最优生产计划。解：（，）（，）代入原最终单纯形表中换基后有：所以应该每隔 天就进货，每次进货批量为 件。每次花费的成本 元 天。模型二：允许缺货，补充时间较长所谓允许缺货是指企业在存贮量降至 时，不急于补充，等一段时间，然后订货。顾客遇到缺货也不受损失或损失很小，并假设顾客会耐心等待，直到新的补充到来。当新的补充一到，企业立即将所缺的货物交付给这些顾客，即缺货部分不进入库存。如果允许缺货，对企业来说除了支付少量的缺货费用外另无其他的损失，这样企业就可以利用“允许缺货”这个宽松条件，少付几次订货费用，少付一些存贮费用，从经济观点出发这样的允许缺货现象对企业是有利的。假设条件：需求是连续均匀的，需求速度是 为常数；补充需要一定时间，不考虑拖延时间，只考虑生产（装配）时间，生产速度是连续均匀的周期性的，生产速度为 常数（）；单位存储费为 ，单位缺货费 ，单位订购费为 。存储状态图（图见视频）（）（）（）（）（）（）计算 时间内的总费用：【详见视频课程】经典例题 胡运权主编 运筹学教程 第三版，例 企业生产某种产品，正常生产条件下可生产 件 天。根据供货合同，需要按 件 天供货。存储费每件 元 天。缺货费每件 元 天，每次生产准备费用为 元，求最优存储策略？解：件 天，件 天 元 天件，元 天件 元 次 槡槡槡 运筹学 考点精讲及复习思路 槡 槡 槡 （天）（件 次）（天）（天）（）（）（天）（）（）（件）（件）（元 天）思考：对比模型一和模型二的假设条件的区别？?，?模型一模型二 槡 槡槡槡 模型一和模型二的区别?，?（）（）（）复习思路提示：）模型二是确定性存储模型的最基本模型，模型一可以看做是模型二的特殊情况，而下一讲的模型三和模型四都可以由模型二直接导出；）模型二由于最复杂，考试时考察频率并不高，以考察其他模型为主；）考试时若无明确标注不能直接套用公式，只要判断属于何种模型并套入公式求解即可。）简单理解公式的推导过程即可。思考题 江苏大学 ，六、计算题，分某企业对某种外购件的需求速度为 件 年，订货提前期为，每次订货费为 元。该外购件的价格为 元，年存储费为 元 件 年。如发生供应短缺，可在下批货到达时补上，但缺货损失为 元每件。试求：）经济订货批量及全年的最小总费用；（分）如不允许发生缺货，重新求经济订货批量；（分）将 和 的结果进行比较，并解释其理由。（分）模型三：不允许缺货，补充时间较长与模型二比较，取消缺货条件！最优策略可以由模型二直接导出。?模型二的最优存储策略最优存储周期：槡槡槡经济生产批量：槡槡槡缺货补货时间：（）开始生产时间：结束生产时间：（）最大存储量：（）最大缺货量：平均总费用：模型三的最优存储策略最优存储周期：槡槡经济生产批量：槡槡缺货补货时间：不允许缺货！开始生产时间：结束生产时间：运筹学 考点精讲及复习思路不允许缺货！最大存储量：（）最大缺货量：平均总费用：不允许缺货！经典例题 胡运权主编 运筹学教程 第三版，例 商店经销某商品，月需求速度为 件，需求速度为常数，该商品每件进价 元，月存储费为进价的 。向工厂定货该商店的订货费每次为 元，订购后需 天才开始到货，到货速度为常数，即每天 件。求最优存储策略。解：需要考虑拖后时间。件 天，件 天 元 天件 元，天，件订货需要 天，那么订货时间前的存储量 要能满足这 天的需求，因为不允许缺货。存储状态图在本例中，称为订货点，即每当发现存储量降到 或更低时就订购。在存储管理中，这样的存储策略称为“定点订货”。代入模型公式后得：最佳存储周期 槡槡 天经济生产批量 槡槡 件结束生产时间 天最大存储量 （）件平均总费用 元模型四：允许缺货，补充时间极短与模型二相比：取消补充需要一定时间的条件。模型二的最优存储策略最优存储周期：槡槡槡经济生产批量：槡槡槡模型四的最优存储策略最优存储周期：槡槡经济生产批量：槡槡模型二的最优存储策略缺货补货时间：（）开始生产时间：结束生产时间：（）模型四的最优存储策略缺货补货时间：（）模型二的最优存储策略最大存储量：（）最大缺货量：平均总费用：模型四的最优存储策略最大存储量：（）（）（槡）最大缺货量：（槡）运筹学 考点精讲及复习思路平均总费用：模型五：价格与订货批量有关的存储模型所谓货物单价有“折扣”是指供应方采取的一种鼓励用户多订货的优惠政策，即根据订货量的大小规定不同的货物单价。通常，订货越多购价越低。我们常见的所谓零售价、批发价、和出厂价，就是供应方根据货物的订货量而制订的不同的货物单价。模型假设：需求是连续的、均匀的。需求速度是常数；补充可以瞬时实现，补充时间近似为 ；单位存储费不变每次订货量不变，订购费不变；缺货成本为无穷大；货物单价随订购数量而变化。设订货批量为 ，对应的货物单价为 （）（）一个存储周期内的总费用：（）（）其中：模型一的费用曲线图例模型五的费用曲线图例（）模型五的算法步骤：计算经济订购批量：槡 如果：则总的平均费用：槡 计算每个批量的单位货物费用 （），（），（）则 对应的批量为最小费用订购批量，对应的最小订购周期：。经典例题 胡运权主编 运筹学教程 第三版，例 工厂每周需要零配件 箱，存储费每箱每周 元，每次订购费 元，不允许缺货。零配件进货时若：（）订货量 箱时，每箱 元；（）订货量 箱时，每箱 元；（）订货量 箱时，每箱 元；（）订货量 箱以上时，每箱 元。求最优存储策略。解：可看出需求速度 箱 周存储费 元 周 箱订购费 元 次 ，先求出经济订货批量 槡 槡 （箱）属于第二个订货批量范围则该批量下的单位货物订购总费用为：运筹学 考点精讲及复习思路()（元）其次求出各批量