2014年西北工业大学《814运筹学》冲刺串讲及模拟题解析讲义(1).pdf

西北工业大学 自动控制原理 冲刺串讲及模拟题解析第 讲冲刺串讲（一）本讲中，我们将给同学们分析到的考点主要是针对线性规划及其对偶问题的。该部分是历年运筹学考试的重点考查内容，对于该部分内容，同学们一定要熟练掌握，并且能够灵活运用。在该部分内容中，需要同学们重点掌握的知识点具体如下：【考点一】线性规划的标准形式线性规划的标准形式为：目标函数 满足约束条件 ，其具备的基本特征为：（）目标函数是实现最大化；（）约束条件均为线性等式；（）各约束条件的右端项 ；（）决策变量均为非负。【考点二】将线性规划问题变换为标准型的步骤（）若要求目标函数实现最小化，即 。这时只需将目标函数最小化变换求目标函数最大化，即令 ，于是得到 。这就同标准型的目标函数的形式一致了。（）约束方程为不等式。这里有两种情况：一种是约束方程为“”不等式，则可在“”不等式的左端加入非负松弛变量，把原“”不等式变为等式；另一种是约束方程为“”不等式，则可在“”不等式的左端减去一个非负剩余变量，把不等式约束条件变为等式约束条件。（）当某一约束条件的右端项 时，在等式两端同乘以“”即可。（）若存在取值非正的变量，可令 ，则 ；若存在取值无约束的变量，可令 ，其中 ，。通过上述变换，任何形式的数学模型都可化为标准型。【考点三】有关线性规划解的几个重要结论（）线性规划问题的可行解是基可行解的充要条件是其正分量的系数列向量是线性独立的。（）线性规划问题的基可行解 对应于可行域 的顶点。（两层含义：若 不是基可行解，则它一定不是可行域 的顶点；若 不是可行域 的顶点，则它一定不是基可行解。即线性规划问题的基可行解与其可行域的顶点是一一对应的。）（）若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。（说明在线性规划的所有基可行解中，必定能找到该问题的最优解。）（）如果线性规划问题有唯一最优解，则该最优解必在可行域的某个顶点处取得，即该最优解必为线性规划问题的一个基可行解。（）若线性规划问题在其可行域的两个顶点处同时得到最优解，则这两个顶点连线上的任意一点都是该线性规划问题的最优解，也就是，该问题有无穷多最优解。（）若某线性规划的可行域无界，则其可能出现无界解的情况，但也可能有最优解，若有也必定在某顶点上得到。【考点四】解线性规划的单纯形法单纯形法的计算步骤（假设目标函数是求极大值）（）找出初始可行基，确定初始基可行解，建立初始单纯形表；找初始可行基的方法如下：对所有约束条件为“”的不等式，在不等式左端加上松弛变量 ；对所有约束条件为“”的不等式，在不等式左端减去剩余变量 后，再加上人工变量 ；对所有等式约束方程，在等式左端加上人工变量 。这样，总能找到一个单位矩阵 （，），以它作为初始可行基，即可确定初始基可行解（）（，）。（）检验各非基变量 的检验数 ；若 ，则已得到最优解，停止计算；若存在某个非基变量的检验数 ，则转入下一步；（）在 ，中，若有某个 对应的 的系数列向量 ，则此问题有无界解，停止计算，否则，转入下一步；（）根据 （），确定 为换入变量，按 规则计算 （），确定 为换出变量；西北工业大学 自动控制原理 冲刺串讲及模拟题解析（）以 为主元素进行迭代，即进行初等行变换，把 对应的系数列向量 ：变换为：将 列中的 替换为，得到新的单纯形表。（）重复上述步骤（）（），直至出现 （，）注：若目标函数为求极小值，只需将最优解的判别准则变为 （，）；根据 （），确定 为换入变量；换出变量仍按 规则确定。若在确定初始可行基时引入了人工变量，那么由于人工变量是虚拟的变量，因此要求经过基变换后要将它们从基变量中逐个换出来，基变量中不再含有非零的人工变量，表示原问题有解；若在最终表中当所有 （，）时，在其中还有某个非零的人工变量，表示原问题无可行解。在迭代过程中，人工变量一旦出基后将不会再进基，所以当某个人工变量出基后，其对应的系数列向量可以不再参与计算，以减少计算量。【考点五】大 法的基本思想大 法的基本思想是：在约束条件中引入人工变量后，若目标函数是求极大值，则人工变量在目标函数中的系数为 ；若目标函数是求极小值，则人工变量在目标函数中的系数为，其中 为任意大的正数。如此以来，在迭代过程中，目标函数要实现最优化，人工变量就会迅速出基。【考点六】单纯形法中解的判别定理（假设目标函数为求极大值）（）最优解的判别定理若 （，）为一个基可行解，且对于一切 ，有 ，则 为最优解。（）无穷多最优解判别定理若 （，）为一个基可行解，对于一切 ，有 ，又存在某个非基变量的检验数 ，则线性规划问题有无穷多最优解。（）无界解判别定理若 （，）为一个基可行解，有一个 ，并且对 ，有，那么该线性规划问题具有无界解。【考点七】线性规划的建模需要重点掌握的为题类型有：排班问题；合理利用线材问题；配料问题等。【考点八】原问题与对偶问题的变换关系（历年考试常有涉及）原问题与对偶问题的变换关系可归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数 目标函数 变量（，）个无约束约束条件 个约束条件个变量（，）个无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项【考点九】对偶问题的基本性质（）对称性对偶问题的对偶是原问题（）弱对偶性若 是原问题的可行解，是对偶问题的可行解，则存在 。（原问题目标函数为求最大值，对偶问题目标函数为求最小值）（）无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解注意这个问题的性质不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。（）可行解是最优解时的性质设是原问题的可行解，是对偶问题的可行解，当 时，是最优解。（）对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。（若原问题无最优解，那么对偶问题也无最优解）（）互不松弛性若，分别是原问题和对偶问题的可行解，那么 和 ，当且仅当，为最优解。西北工业大学 自动控制原理 冲刺串讲及模拟题解析（）设原问题是 ；，它的对偶问题是 ；，则原问题单纯性表的检验数行对应其对偶问题的一个基解，其对应关系如下表所示：这里 是对应原问题中基变量 的剩余变量，是对应原问题中非基变量 的剩余变量。【考点十】影子价格的经济解释（本部分内容在历年试题的判断题中出现频率极高）（）在对偶问题中，对偶变量 表示各种资源的增值价格，在最优解中，的经济意义是在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，是根据资源在生产中作出的贡献而作的估价，称为影子价格。（）影子价格是一种边际价格，变量 相当于在给定的生产条件下，每增加一个单位，使目标函数 的增加量。（）影子价格是一种机会成本企业可以根据现有资源的影子价格，对资源的使用作两种考虑：第一，是否将资源用于外加工或出租。若某种资源的租费高于它的影子价格，可考虑出租该资源，否则不宜出租。第二，是否将投资用于购买资源，以扩大生产能力。若某种资源的市价低于它的影子价格，可考虑买进该资源，否则不宜买进。（）影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。（）影子价格 对偶问题最优解。根据对偶问题的互补松弛性可知，当某种资源的影子价格时，表示其对应的资源 已经在生产中耗尽；当某种资源 未被充分利用时，该资源的影子价格 。第 讲冲刺串讲（二）本讲中，我们首先要承接上一讲，继续给大家分析关于线性规划及其对偶问题的几个相关考点，接着将给大家介绍到运输问题和目标规划中的需要同学们重点掌握的知识点。首先，我们来看线性规划及其对偶问题中剩余的几个考点：【考点十一】对偶单纯形法（一般不会单独考查，会与灵敏度分析结合在一起）对偶单纯形法的计算步骤如下（针对原问题目标函数求最大值，对偶问题目标函数求最小值的情况而言）（）根据线性规划问题，列出初始单纯形表。检验 列的数字，若都为非负，检验数都为非正，则问题已得到最优解，停止计算。若检查 列的数字时，至少还有一个负分量，检验数保持非正，那么进行一下计算。（）确定换出变量按 （）（）（）对应的基变量 为换出变量。（）确定换入变量在单纯形表中检查 所在行各系数 （，）。若所有 ，则无可行解，停止计算。若存在 （，），计算 按 规则所对应的列的非基变量 为换入变量，这样才能保持得到的对偶问题解仍为可行解。（）以 为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤（）（）。【考点十二】关于对偶单纯形法的几点说明（）对偶单纯形法是求解线性规划问题的一种方法，并不是求解对偶问题的单纯形法。（）在运用对偶单纯形法求解线性规划问题时，初始解可以是非可行解，当检验数都为非正数时，就可以进行基的变换，这时不需要再引入人工变量，因此可以简化计算。（）对偶单纯形法在计算过程中与一般单纯形法的一个明显差别是：一般单纯形法中，我们是先确定换入变量，后确定换出变量，而对偶单纯形法恰巧相反，它是先确定换出变量，后确定换入变量的。（）在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可以使问题的处理简化。西北工业大学 自动控制原理 冲刺串讲及模拟题解析【考点十三】资源和价值系数的灵敏度分析一、资源限量 的灵敏度分析设第 种资源数量 增加 ，线性规划的其他系数不变。这样就使得在最终单纯性表中原问题的解相应地变化为 （），其中 （，）当 ，因最终表中检验数没有发生变化，故最优基不变，但最优解的值发生变化，所以 为新的最优解。令最优基不变的 的变化范围为 当 的元素不全为非负时，这时最终单纯形表中的原问题为非可行解，对偶问题仍为可行解，可用对偶单纯形法继续迭代求最优解。价值系数 的灵敏度分析对于价值系数，可以分别就 是对应的非基变量和基变量两种情况来讨论。（）若 是非基变量 的系数，这时它在计算表中所对应的检验数是 。当 变化 后，要保证最终表中这个检验数仍小于或等于零，则由 ，易得 的取值范围为 当 变化 后，若出现对应的检验数 ，则最终单纯形表中原问题为可行解，对偶问题为非可行解，可用单纯形法继续迭代求最优解。（）若 是基变量 的系数。因 ，当 变化 时，就引起 的变化，这时最终表中的所有检验数都会发生变化，（），若要使得原问题的最优解不变，则要求所有检验数仍小于等于零，由 （）（，）可得原问题最优解不变的 的取值范围为 若变化后的检验数中存在大于零的，则在最终单纯性表中原问题为可行解，对偶问题为非可行解，可利用单纯形法继续迭代求最优解。关于运输问题，需要同学们重点掌握的就是解运输问题的表上作业法，这里关于产销不平衡问题的处理办法要引起同学们的重视。具体内容如下：【考点十四】产销不平衡运输问题的处理方法表上作业法都是以产销平衡为前提的，当遇到产销不平衡的问题时，要把产销不平衡的问题化成产销平衡的问题，再利用表上作业法进行求解，具体处理方法如下：当总产量大于总销量时，只要增加一个假想的销地 （实际上是就地储存），该销地的总需求量为实际总产量与总销量的差额，而在单位运价表中从各产地到假想销地的单位运价为 ，这样就将问题转化成了一个产销平衡的运输问题。当总销量大于总产量时，可以在产销平衡表中增加一个假想的产地 ，该产地的产量为实际总销量与总产量的差额，在单位运价表中令该假想产地到各销地的运价 ，同样可以将问题转化为一个产销平衡的运输问题。需要注意的是，尽管 ，（或 ，），但在用最小元素法确定问题的初始基可行解是，并不将其视作最小元素而优先考虑。【考点十五】求解运输问题的表上作业法表上作业法的计算步骤如下：（）如果原问题为产销不平衡的运输问题，首先应将问题转化为产销平衡的运输问题，再进行求解；（）找出初始基可行解。即在（）产销平衡表上给出 个数字格（可采用最小元素法或伏格尔法确定初始基可行解；给出的 个数字格不能构成闭回路）；（）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解（因目标函数求最小值，故当检验数全部大于等于零时达到最优），如已是最优解，则停止计算，否则转到下一步（计算空格检验数时，可采用闭回路法或位势法）；（）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整；（）重复（），（）直到得到最优解为止。对于目标规划这部分内容，同学们一方面要深刻理解目标规划的相关概念，另一方面就是要熟练掌握目标规划的建模问题。具体考查内容如下：【考点十六】目标规划的相关概念（）正、负偏差变量，正偏差变量 表示决策值超过目标值得部分；负偏差变量 表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有 。（目标规划的数学模型中一定包含有偏差变量）（）绝对约束和目标约束绝对约束是必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划所特有的，可把约束右端项看作要追求的目标值，在达到此目标值是允许发生正或负偏差，因此在这些约束中加入正、负偏差西北工业大学 自动控制原理 冲刺串讲及模拟题解析变量，它们是软约束。有时可根据问题的需要将绝对约束变换为目标约束。（）优先因子（优先等级）与权系数一个规划问题常常有若干个目标，但决策者在要求达到这些目标时，是有主次或轻重缓急的不同的。要求第一位达到的目标赋予优先因子，次位的目标赋予优先因子，并规定?，。表示 比 有更大的优先权。即首先保证 级目标的实现，这时可不考虑次级目标，而 级目标是在实现 级目标的基础上考虑的，以此类推。若要区别具有相同优先因子的两个目标的差别，这是可分别赋予它们不同的权系数，这些都由决策者按具体情况而定。（）目标规划的目标函数目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是 （，）（因而，目标规划的目标函数中必不含决策变量）。（）目标规划目标函数的三种基本形式：要求恰好达到目标值，即正、负偏差变量都要尽可能地小。这时 （）；要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小。这时 （）；要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小。这时 （）。【考点十七】目标规划的建模问题该考点虽然在往年考题中鲜少出现，但就近两年的考试趋势来看，其关注度一直很高，希望能够引起同学们的重视。目标规划的建模关键在于对题意的正确理解，然后在熟练掌握上一考点中提到的目标规划的各个要素的含义的基础上构建目标规划模型。主要还是要靠同学们平时多加练习并且勤于积累，才能在考试中轻松应对。第 讲冲刺串讲（三）本讲中，我们将给大家重点剖析整数规划和动态规划中的重要考点。在整数规划中，需要大家熟练掌握的考点有：分支定界法的基本原理、割平面法的基本原理、型整数规划的建模问题以及指派问题的建模与求解；在动态规划中，同学们要在熟练掌握相关概念的基础上，理解动态规划的建模思想，并能够根据题目要求建立问题的动态规划模型。整数规划部分的具体考点内容如下：【考点十八】分支定界法的基本思路（）依据：整数规划的目标函数的最优值不会优于与之相应的线性规划目标函数的最优值。（）基本思路：设有最大化整数规划问题 ，与它相应的线性规划为问题 ，从问题 开始，若其最优解不符合 的整数条件，那么 的最优目标函数值必是 的最优目标函数值 的上界，记作；而 的任意可行解的目标函数值将是 的一个下界。分支定界法就是将 的可行域分成子区域（称为分支）的方法，逐步减少 和增大，最终求到 。【考点十九】分支定界法的求解整数规划（最大化）问题的一般步骤将要求的整数规划问题称为问题 ，将与之相应的线性规划问题称为问题 。（）解问题 ，可能得到以下情况之一：没有可行解，这时 也没有可行解，则停止计算。有最优解，并符合问题 的整数条件，的最优解即为 的最优解，则停止。有最优解，但不符合问题 的整数条件，记它的目标函 数值为。（）用观察法找问题 的一个整数可行解，一般可取 ，试探，求得其目标函数值，并记作。以 表示问题 的最优目标函数值；这时有 。进行迭代。第一步，分支。在 的最优解中任选一个不符合整数条件的变量，其值为，以 表示小于的最大整数。构造两个约束条件 和?将这两个约束条件，分别加入问题 ，得到两个后继规划问题 和。不考虑整数条件解这两个后继问题。定界。以每个后继问题为一个分支表明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界西北工业大学 自动控制原理 冲刺串讲及模拟题解析，若无可行解，。第二步，比较与剪支。各分支的最优目标函数值中若有小于 者，则剪掉这支（用打 表示），即以后不再考虑了。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到 为止，得到最优整数解，。【考点二十】割平面法的基本思路割平面法的基础仍然是用解线性规划的方法去解整数规划问题。其基本思路是：增加合适的线性约束（用几何术语，称为割平面），对相应线性规划问题的可行域进行切割，形成割平面，使切割后的可行域有一个整数坐标的极点（顶点），该极点恰好是原整数规划问题的最优解。【考点二十一】割平面法解整数规划问题的一般步骤（）暂不考虑取整的约束，求解相应的线性规划问题，若线性规划问题无可行解或最优解恰为整数解，则停止；否则转下步。（）对线性规划问题的可行域进行“切割”，即增加线性约束条件，切掉原可行域中的一部分，这部分中只包含非整数解，而没有切掉任何整数可行解；返回 。求一个切割方程（即新增约束条件）的步骤为：第一步，令 是相应线性规划最优解中为分数值得一个基变量，由单纯形表的最终表得到 其中，（指构成基变量下标的集合），（是构成非基变量下标的集合）。第二步，将 和 都分解成整数部分 与非负真分数 之和，即 ，其中 ，其中 代入式得 第三步，现在提出变量（包括松弛变量）为非负整数的条件，这时，上式由左边看必须是整数，但由右边看，因 ，所以不能为正，即 这就是一个切割方程。【考点二十二】型整数规划建模问题关于 型整数规划的建模问题中，需要同学们重点掌握的问题类型就是，当存在两种互相排斥的选择时，可以引入 型变量分别表示不同的选择，然后再根据题意建立相应的线性规划模型。根据具体问题的不同，所建立的模型中可能仅含有 型变量，也可能含有其他类型的变量，这个要 具体问题具体分析。【考点二十三】指派问题的模型指派问题的一般描述：现有 个人去完成 项任务，如何分配任务，使完成 项任务的总效率最高（所需总时间最少）。指派问题的一般数学模型：，第 项任务只能由 个人完成 ，第 个人只能完成 项任务 或由此可见，指派问题既是 规划的特例，也是运输问题的特例，即 。指派问题的最优解具有这样的性质：若从系数矩阵（）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（），那么以（）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。【考点二十四】指派问题的求解方法求解指派问题的匈牙利法（针对目标函数求极小化，且人数与任务数平衡的指派问题）（）依据（康尼格定理）：系数矩阵中独立 元素的最多个数等于能覆盖所有 元素的最少直线数。（）匈牙利法的计算步骤第一步变换指派问题的系数矩阵，使在各行各列都出现零元素。从系数矩阵的每行元素减去该行的最小元素。再从系数矩阵的每列元素中减去该列的最小元素。第二步进行试指派从有零元素最少的行（列）开始，圈出一个零元素，用表示，然后划去同行同列的其他零元素，用表示。若最少零元素行（列）同时有几行（列），则从零元素所在列（行）中最少的开始。依次类推。若矩阵中的个数等于 （矩阵的阶数），则对应的指派方案就是最优方案。若矩阵中的个数小于 ，则进行第三步。第三步作最小的能覆盖所有零元素的直线集合。为此，按如下步骤进行：对没有的行打号；对 已打行上所有 元素所在的列打号；西北工业大学 自动控制原理 冲刺串讲及模拟题解析 再对已打号的列上有的行打号；重复，直到得不出新的打号的行列为止；对没有打号的行划横线，所有打号的列划纵线，这就是能覆盖所有零元素的最小直线集合。第四步进行调整在没有被直线覆盖的部分元素中找出最小元素，对没有划直线的行的各元素都减去这个最小元素，对已划直线的列的各元素都加上这个最小元素。转第二步。【考点二十五】变异型指派问题的处理方法（）极大化指派问题 令 （是一个足够大的常数，通常可选 中最大元素为）。这时系数矩阵变为 （），目标函数变为 ，符合匈牙利算法的条件，运用匈牙利算法所得最小解就是原问题的最大解。（）人数与工作数不相等的问题对于人数与工作数不相等的指派问题，设分配问题中人数为 ，工作数为 。当 时，增设 项虚拟工作，对应的效率为零；当 时，增设 个虚拟的人，对应的效率为零，化为人数与工作数相等的平衡问题后再求解。对于虚拟的工作或人，其中的 元素必须在其他 元素使用完后，再给予考虑，与运输问题中相同，该 元素首先不作为最小元素考虑。（）不可接受的配置当某人不能完成某项任务时，令对应的效率为一个大 即可。下面我们来总结一下动态规划的主要考查内容：【考点二十六】动态规划模型中的基本要素一个动态规划模型一般要包含以下要素：阶段的划分、状态的选取、阶段决策、状态转移方程、指标函数和最优值函数的构造以及动态规划的基本方程。这里需要同学们重点注意一下几点：（）阶段的划分一般是根据时间和空间的自然特征来划分，有时也要靠划分者平时的经验积累，阶段划分的原则是要便于把问题的过程能转化为多阶段决策的过程。（）在建立动态规划模型时，所选取的状态应具有无后效性：即如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各段状态的影响。亦即过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的一个总结。所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意是否满足无后效性的要求。如 果状态的某种规定方式可能导致不满足无后效性，应适当地改变状态的规定方法，使它满足无后效性的要求。（）对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。即 ，（，），（，）（）常见的指标函数形式有：过程和它的任一子过程的指标是它所包含的各阶段的指标的和。即，（，）（，）其中（，）表示第 阶段的阶段指标。这时有，（，）（，），（，）过程和它的任一子过程的指标是它所包含的各阶段指标的乘积。即，（，）（，）这时有，（，）（，），（，）（）最优值函数（）表示从第 阶段的状态 开始到第 阶段的终止状态的过程，采取最优策略所得到的指标函数值。即（）（，），（，）（）动态规划的基本方程：动态规划的逆推解法的基本方程为：（）（）（，）（），（）（，）动态规划的顺推解法的基本方程为：（）（）（，）（），（）（，）【考点二十七】动态规划的基本思想动态规划的基本思想可归纳如下：（）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件，也就是要正确地写出基本方程。要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界西北工业大学 自动控制原理 冲刺串讲及模拟题解析 条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。（）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最有选择答案一般是不同的。（）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态变量的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。【考点二十八】建立动态规划模型的一般步骤（）将问题的过程划分成恰当的阶段；（按时间、空间的自然特征进行划分，或者靠平时的经验积累）（）正确选择状态变量，使它既能描述过程的演变，又要满足无后效性；（）确定决策变量 及每阶段的允许决策集合（）；（）正确写出状态转移方程（逆推：（，）；顺推：（，）（）正确写出指标函数 ，的关系，它应满足下面三个性质：是定义在全过程和所有后部子过程上的数量函数；要具有分离性，并满足递推关系。即 ，（，），（，）；函数（，）对于变量 ，要严格单调。（）写出动态规划基本方程（若初始状态已知，一般采用逆推方程；若终止状态已知，一般采用顺推方程）。【考点二十九】典型的动态规划应用问题常见的利用动态规划模型解决的问题有最短路问题、资源分配问题、背包问题、生产存储问题、系统可靠性问题、设备更新问题等。这里需要同学们特别注意的是如何建立最短路问题、资源分配问题以及系统可靠性问题的动态规划问题。其中，最短路问题虽然是一类比较简单的动态规划问题，但能够帮助同学们更加直观地理解动态规划的基本思想，更加清晰地掌握建立动态规划模型的整个过程，对于初学动态规划的同学来说，掌握这类问题的模型建立是深入学习动态规划方法的基础；对于资源分配问题，一定要一起同学们的高度重视，这类问题在历年考试中出现的频率一直很高，尤其是在近两年，试题越来越关注同学们对连续型资源分配问题的掌握情况，希望同学们在课下能加强这方面的学习，一定要亲自动笔写一写，光靠看书很难掌握这部分内容；系统可靠性问题是目前为止，我们碰见的少有的一类指标函数是乘积形式的问题，这点希望同学们可以稍加重视，可能称为之后动态规划建模考查的一个方向。第 讲冲刺串讲（四）该讲中，主要给大家总结了图与网络分析中的重要考查内容。图与网络分析中主要包括两大部分，一是图与网络优化，二是网络计划。在图与网络优化中，重点需要同学们掌握的问题有：图的基本概念、最短路问题以及最大流问题。在网络计划中，同学们要掌握的内容有：双代号网络计划图的绘制、时间参数的计算以及简单的优化过程。图与网络优化的具体考查内容可归纳如下：【考点三十】无向图中的重要概念与定理定理 图 （，）中，所有点的次之和是边数的两倍，即 （）。定理 任一个图中，奇点的个数为偶数。给了一个图 （，），如果图 （，），使 及?（，）（），则称 是 的一个支撑子图。【考点三十一】树与最小支撑树的概念及重要定理（）树：一个无圈的连通图称为树。（）图的支撑树：设图 （，）是图 （，）的支撑子图，如果图 （，）是一个树，则称 是 的一个支撑树。（）最小支撑树：设有一个连通图 （，），每一边 ，有一个非负权 （）（）。如果 （，）是 的一个支撑树，称 中所有边的权之和为支撑树 的权，记为 （）。即 （）（）！。如果支撑树 的权 （）是 的所有支撑树的权中最小者，则称 是 的最小支撑树（简称最小树），即 （）（）。（）树的相关定理定理 设图 （，）是一个树，（），则 中至少有两个悬挂点。定理 图 （，）是一个树的充分必要条件是 不含圈，且恰有 条边。定理 图 （，）是一个树的充分必要条件是 是连通图，并且 （）（）。定理 图 是树的充分必要条件是任意两个顶点之间恰有一条链。【考点三十二】最短路问题求非负赋权图（）的 算法：西北工业大学 自动控制原理 冲刺串讲及模拟题解析（）算法基本思想：从 出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为 标号），或者是从 到该点的最短路的权的上界（称为 标号），方法的每一步是去修改 标号，并且把某一个具有 标号的点改变为具有 标号的点，从而使 中具有 标号的顶点数多一个，这样，至多经过 步，就可以求出从 到各点的最短路。（）算法的具体步骤：给定非负赋权有向图 （，）说明：在介绍 方法的具体步骤中，用 、分别表示某个点的 标号、标号，表示第 步时，具有 标号的点的集合，为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 （），表示在从 到 的最短路上，的前一个点是；如果 （），则表示 中不含从 到 的路；（）表示 。算法的具体步骤如下：开始（）令 ，（），（），对每一个 ，令 （），（），令 。如果 ，算法终止，这 是，对每个 ，（，）（）；否则转入。考查每个使（，）且 的点。如果 （）（），则把 （）修改为 （），把 （）修改为 ；否则转入。令 （）（）。如果 （），则把 的标号变为标号（）（），令 ，把 换成 ，转入；否则终止，这时对每一个 ，（，）（），而对每一个 ，（，）（）。注：在一个有向图中，（，）与 （，）不一定相等。在一个赋权无向图中，如果所有的 ，只要把 算法中的“考查每个使（，）且 的点”改为“考查每个使，且 的点”，同样地可以求出从 到各点的最短路（对于无向图，即最短链），这时有 （，）（，）。【考点三十三】最大流问题中的几个重要概念（）可行流：满足下述条件的流 称为可行流容量限制条件：对每一弧（，）；平衡条件：对于中间点：流出量等于流入量，即对每个 （，）有（，）（，）对于发点，有（，）（，）（）对于收点，有（，）（，）（）式中 （）称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。说明：可行流总是存在的，比如令所有弧的流量 ，就得到一个可行流，称之为零流，其流量为（）。（）增广链：设 是一个可行流，是从 到 的一条链，若 满足下列条件，称之为（关于可行流 的）增广链。在弧（，）上，即 中每一条弧是非饱和弧；在弧（，）上，即 中每一条弧是非零流弧。（）截集：给网络 （，），若点集 被剖分为两个非空集合 和 ，使 ，则把弧集（，）称为是（分离 和 的）截集。（注：截集是一个弧的集合）（）截量：给一个截集（，（，），把截集（，（，）（，）（，）中所有弧的容量之和称为这个截集的容量，简称为截量，记为（，），即（，）（，）（，）说明：任何一个可行流的流量 （）都不会超过任一截集的容量。（）最大流量最小截量定理：任一个网络 中，从 到 的最大流的流量等于分离，的最小截集的容量。【考点三十四】寻求最大流的标号法从一个可行流出发（若网络中没有给定 ，则可以设 是零流），经过标号过程和调整过程。（）标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找到增广链；第二个标号是为确定增广链的调整量 用的。标号过程开始，总先给 标上（，），这时 是已标号而未检查的点，其余都是未标号的点。一般地，取一个已标号而未检查的点，对一切未标号的点：若在弧（，）上，则给 标号（，（）。这里 （）（），。这时点 成为标号而未检查的点。若在弧（，）上，则给 标号（，（）。这里 （）（），。这时点 成为标号而未检查的点。于是 成为标号且已检查过的点。重复上述步骤，一旦 被标上号，表明得到一条从 到 的增广链 ，转入调整过程。若所有标号都是已检查过的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。（）调整过程首先按 及其他点的第一个标号，利用“反响追踪”的方法，找出增广链 。令调整量 是 （），西北工业大学 自动控制原理 冲刺串讲及模拟题解析 即 的第二个标号。作如下调整：（，）（，）（，）去掉所有的标号，对新的可行流 ，重新进入标号过程。说明：用标号法找增广链以求最大流的结果，同时得到一个最小截集（，），其中 为标号点的集合，为未标号点的集合。根据最大流最小截量定理可知，最小截集的容量的大小会影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。下面是关于网络计划中的重点考查内容：【考点三十五】绘制双代号网路计划图的基本原则（）节点编号必须按箭尾编号小于箭头编号来标记；（）网络计划图只能有一个起始节点，表示工程项目的开始，一个终点节点，表示工程项目的结束，当工程开始时或完成时有几个平行工作时，可以用虚工作将它们分别与起始节点与终点节点连接起来；（）相邻两节点之间只能有一条箭线连接，否则会造成逻辑上的混乱；（）网络计划图中不能有缺口和回路，无论出现那种现象，都会导致项目永远无法完成；（）绘制网络计划图时，应尽可能将关键路线布置在网络计划图的中心位置，按工作先后顺序将联系紧密的工作布置在邻近的位置。为了便于在网络计划图上标注时间等信息，箭线最好是水平线或具有一段水平线的折线。（）全图要尽量避免重叠，要具有封闭性，连通性，有向性，不可逆性。【考点三十六】网路计划图时间参数的计算（）一个网络计划的时间参数主要包括：工作持续时间（），工作最早开始时间（），工作最早完成时间（），工作最迟开始时间（），工作最迟完成时间（），工作总时差（）和工作自由时差（）等。（）为了计算方便，在网络计划图中每条箭线上引入如下标记（）各时间参数的具体计算方法：工作持续时间 单时估计法：当具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。三时估计法：其中，表示在一切都顺利时，完成工作需要的最少时间；表示在正常条件下，完成工作所需要的的时间；表示在不顺利的条件下，完成工作需要最多的时间。工作最早开始时间 和工作最早完成时间 的计算利用网络计划图，从网络计划图的起始点开始，沿箭线方向依次计算各工作的最早开始时间和最早完成时间。计算公式如下：（）（）；注：从起始节点出发的各项工作的最早开始时间 ，最早完成时间 。工作最迟开始时间 与工作最迟完成时间 的计算利用网络计划图，从网络图的终点节点开始，按逆箭线方向依次计算各工作的最迟完成时间 和最迟开始时间 。计算公式如下：（）（）；箭头节点为终点节点的各项工作的最迟完成时间由工程的计划工期确定，在未给定时，可令其等于项目的最早完成时间，即 （）。工作时差的计算工作总时差 ：是指在不影响工期的前提下，工作所具有的机动时间，其计算公式为：或 。工作自由时差 ：是指在不影响其紧后工作最早开始的前提下，本工作所具有的机动时间，其计算公式为：。说明：工作总时差往往为若干项工作共同拥有的机动时间，当其中某项工作用去一部分机动时间后，其余工作的机动时间将相应地减少；工作自由时差是某项工作单独拥有的机动时间，其大小不受其他工作机动时间的影响；总时差为零的工作的自由时差必为零。【考点三十七】关键路线的确定在双代号网络计划图中，在计算出各项工作的时间参数后，我们可以根据各工作的工作时差确定关键工作，进而确定关键路线。总时差为零的工作为关键工作，网络图中由关键工作组成的从始点到终点的路线即为关键路线。在某些网络计划中，关键路线可能不唯一，并且在采取了一定的技术和组织措施后，关键路线可能发生变化。西北工业大学 自动控制原理 冲刺串讲及模拟题解析【考点三十八】网络计划的优化（）工期优化：若网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度，缩短工程项目的完工工期。主要采取的措施是增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。（）资源优化：在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。即在项目的工期不变的条件下，均衡地利用资源。具体操作如下：优先安排关键工作所需要的资源；利用非关键工作的总时差，错开各工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰；在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当地推迟工程的工期，实现错开高峰的目的。（）时间费用优化：编制网络计划时，要研究如何使完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需要的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间费用优化要解决的问题。时间费用优化的步骤：计算工作费用增加率（简称费用率：是指缩短工作持续时间每缩短一单位时间所需增加的直接费用）；在网络计划图中找出费用率最小的一项关键工作或一组关键工作作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间，不能成为非关键工作；计算工作持续时间每缩短单位时间相应增加的直接费用，然后考虑由于工期缩短使间