运筹学基础复习要点

2011年《运筹学基础》复习要点 一、基本概念与理论 1．任意多个凸集的交集还是凸集。 2．任意多个凸集的并集不一定是凸集 3．给定 及非零向量 ，称集合 是 的一个超平面。 4．由超平面 的两个半平面 和 都是凸集。 5．设 是凸集， 。若对任何 ，以及任何 ，都有 ，则称 为 的顶点。 6．如果一个LP问题无界，则它的对偶问题必无可行解。 7．设 分别为原始LP问题、对偶问题的可行解，若 ，则原始LP问题、对偶问题的最优解分别为 。 8.可行解 是基本可行解的充分必要条件是 的正分量，所对应的 中列向量线性无关。 9.写出LP问题的对偶问题 的对偶问题是：    10．设一个 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式的LP问题的基为 ，右端向量为 ，则对应的基本解是 。 11．线性规划问题的可行域是凸集。 12．设线性规划问题LP为 为一个基，对应的典式为 其中 。 13.线性规划问题的规范形式为 14. 线性规划问题的标准形式为 15.线性规划问题的一般形式为 16.对线性规划问题，关于它的解分三种情况：问题无解、问题无界和问题有最优解。 17.如果一个LP问题有最优解，则它的对偶问题必有最优解。 18.一个标准形式的LP问题，若有可行解，则至少有一个基本可行解。 19.若标准形式的LP问题有有限最优解，则一定存在一个基本可行解是最优解。 20．原始LP问题的任一可行解的目标函数值不小于其对偶问题任一可行解的目标函数值。 21．可行解 是基本可行解的充分必要条件是 为可行域的顶点。 22．设简单图无向 ，则 。 23．设简单图有向 ，则 ， 。 24.握手定理：设 无向图，则 （或所有顶点的度数之和等于边数的两倍）。 25．每个树至少有两个次数为1的点。 26． 有支撑树当且仅当 是连通的。 27．设 为 的一个支撑树，则 是 的最小树当且仅当对任意边 （ 的补树）有 其中 为唯一的回路。 28．设 为 的一个支撑树，则 是 的最小树当且仅当对任意边 有 其中 为唯一割集。 29．一个排队系统由三个基本部分组成：输入过程、排队规则和服务机构。 30．最简单流满足三个条件：平稳性、无后效性和普通性。 31．设有某系统，具有状态集 ，若系统的状态随时间 变化的过程 满足以下条件，则称为一个生灭过程。 设在时刻 系统处于状态 的条件下，再经过长为 （微小增量）的时间。 （1）转移到 （ ）的概率为 ； （2）转移到 （ ）的概率为 ； （3）转移到 的概率为 ， 其中 ， 为与 无关的固定常数。 32.一个生灭过程 ，则生灭过程在 时的概率为 ， 。 33．决策问题通常分为三种类型：确定型决策、风险型决策和不确定型决策。 34.一个决策模型主要由四个部分组成：状态集、决策集、报酬函数和决策准则 35.风险型决策的主要方法有最大可能法和期望值法两种。 36．最大可能法是在风险型决策中选择一个概率最大的自然状态进行决策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。 37．不确定型决策的主要方法有乐观法、悲观法、乐观系数法、后悔值法和等可能法等。 38．一个对策模型由三个部分组成：局中人、策略集和支付函数。 39．矩阵对策 ，等式 成立的充要条件是存在局势 ，使 。 40．矩阵对策在它的混合扩充中存在解。 41.工件的加工时间（单位：分钟）如下： 其中 中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件 的加工顺序为    。    42. 工件的加工时间（单位：分钟）如下： 其中 中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件 的加工顺序为    。    43.工件的加工时间（单位：分钟）如下： 其中 中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件 的加工顺序为    44．对标准形式的线性规划，叙述单纯形法的步骤： 第1步 找一个初始可行基 ； 第2步 求出对应的典式及检验数向量 ； 第3步 求 ； 第4步 若 ，停止； 已找到最优解 及最优值 ； 第5步 若 ，停止。原问题无解； 第6步 求 ； 第7步 以 代替 得到新的基，转到第2步。 45．对ILP问题(P)，Gomory割平面法的计算步骤： 第1步 用单纯形法解ILP问题(P)的松弛问题(P0)。若(P0)没有最优解，则计算停止，问题(P)也没有最优解。若(P0)有最优解 ，假如 是整数向量，则 是(P)的最优解，计算停止，输出 ；否则转到第2步； 第2步 求割平面方程 任选 的一个非整数分量 ，按 ， （其中 为非基变量下标集合），得到割平面方程  （*） 第3步 将割平面方程（*）加到第1步所得到的最优单纯形表中，用对偶单纯形法求解这个新的松弛问题。若其最优解为整数解，则是问题（P）的最优解，计算停止，输出这个最优解；否则将这个最优解重新记为 ，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时原ILP是不可行的，计算停止。 46.叙述求最小树的Kruskal算法的基本思想和步骤。 Kruskal算法的基本思想是从 的 条边中选取 条权尽可能小的边，并且使得不构成回路，从而构成一个最小树。                              Kruskal算法的步骤： 第1步 从 中选一条权最小的边 ； 第2步 若 已选出，则从 中选 ，使得 （1） 中无圈， （2） 。 第3步 反复执行上述过程直至选出 止。 47.叙述求最小树的Dijkstra算法的基本思想和步骤。 Dijkstra算法的基本思是从 的 个独立割集中的每一个都选一条权最小的边，从而构成一个最小树。 Dijkstra算法的步骤： 第1步 置 ， ， ， ； 第2步 取 ，置 ， ， ； 第3步 若 ，则停止；否则，置 ，返回地2步。 二、名词解释 1． 互补松紧性： 设 分别为原始和对偶问题的可行解，则它们分别是原始和对偶问题的最优解的充要条件是，对一切 和一切 有 ， 。 2．动态规划的最优化原理： 一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对于第一个决策所形成的状态作为初始状态而言，必须构成最优策略。 3．无向图 的边割与割集 对于 的两个不相交子集 和 表示一个端点在 中，另一个端点在 中的边的集合。所谓 的边割指的是 的形如 的子集，其中 ，从 中删除这些边后， 的连通分支数严格增加。 的极小边称为割集。 4．乐观法 决策者从最乐观的观点出发，对每个 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 按最有利的状态发生来考虑问题，即求出每个方案在各自然状态下的最大报酬值。然后从选取最大报酬值 最大的方案为最优方案，即决策准则为 。 5．生灭过程 设有某系统，具有状态集 ，若系统的状态随时间 变化的过程 满足以下条件，则称为一个生灭过程。 设在时刻 系统处于状态 的条件下，再经过长为 （微小增量）的时间。 （1）转移到 （ ）的概率为 ； （2）转移到 （ ）的概率为 ； （3）转移到 的概率为 ， 其中 ， 为与 无关的固定常数。 6．最大可能法 最大可能法是在风险型决策中选择一个概率最大的自然状态进行决策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。 三、计算题 1.某工厂医院的一个科室，有一个医生值班。经长期观察，每小时平均有4个病人，医生每小时可诊5个病人。假设病人到达服从泊松分布，医生的诊病时间服从指数分布。试分析该科室的工作状况。如要满足99%以上的病人有座位，此科室至少应设多少个座位。如果该工厂24小时上班，病人看病1小时因误工，工厂要损失30元，这样工厂平均每天损失多少元？若该科室提高看病速度，每小时平均可诊6个病人，工厂可减少损失多少元？ 解：由已知， ，从而排队系统的稳态概率为        所以      为满足99%以上的病人有座，设该科室有 个座位，则有 {科室的病人数 } 即          可解得  ，因此，该科室至少应设20个座位。            如果该工厂24小时上班，则每天平均有病人 ，病人看病所花去的总时间为 ，所以工厂平均每天损失 。 如果每小时平均可诊6个病人，类似地计算有 ， 这样单位损失为 ，因此，工厂减少损失 。                                    2. 假设有外表相同的木盒150只，将其分为两组，一组内装白球，有90盒。一组内装黑球，有60盒。现从150只木盒中任取一盒，请你猜。如这盒内装的是白球，猜对得800分，猜错罚500分；如这盒内装的是黑球，猜对得2000分，猜错罚300分。为使期望收益最大，应选哪一个方案？并对最优方案进行灵敏度分析。 2. 解：由已知，可得收益矩阵见表3。 表3 概 率 方案 自然状态 白 0.6 黑 0.4 猜白 800 -300 猜黑 -500 2000       方案“猜白”的期望收益为 方案“猜黑”的期望收益为 因 ，所以方案“猜黑”为最优方案。                          （5分） 设 状态白的概率为 ，状态黑的概率为 ， 。 方案“猜白”的期望收益为 方案“猜黑”的期望收益为 令 ，由 ，可解得 。 因此，当 时，方案“猜黑”为最优方案。                  （10分） 3.某公司有两种方案：甲方案与乙方案。损失与收益见表1。 表1  两方案的损益  单位：万元 概率 方案 经济繁荣 经济萧条 0.7 0.3 甲 500 -150 乙 -200 1400       为使期望收益最大，应选哪个方案？并对最优方案进行灵敏度分析。 解：方案甲的期望收益为 方案乙的期望收益为 因 ，所以甲方案为最优方案。                    设 经济繁荣的概率为 ，经济萧条的概率为 ， 。 方案甲的期望收益为              (1) 方案乙的期望收益为            (2) 令 ，由(1),(2)与 ，解得 当 时，甲方案为最优方案。  4.某工厂平均每天有一台机器发生故障需修理，故障数服从泊松分布。一台机器因修理，每天工厂平均损失20元。现有技术水平不同的修理工人甲和乙。甲平均每天修1.2台，每天工资12元。乙平均每天修1.5台，每天工资20元。两修理工修理机器的时间服从指数分布，问工厂应录用哪一个修理工？并对最优决策关于每天工资进行灵敏度分析。 解：由已知， 若录用甲修理工，则 ， 工厂每天平均费用为 元 若录用乙修理工，则 ， 工厂每天平均费用为 元 因 ，所以录用乙修理工更合算。                设 乙修理工每天的工资为 ，则录用乙后，工厂每天平均费用为 令 ，可解得 。因此，当乙修理工每天的工资不超过72元时，录用他比甲更合算。 5．设某工厂是按批生产某产品并按批销售，每件产品的成本为30元，批发价格为每件35元。若每月生产的产品当月销售不完，则每件损失1元。工厂每投产一批是10件，每月生产能力为40件。决策者可选择的方案为0，10，20，30，40五种。假设决策者对其产品的需求一无所知，试用悲观法和后悔值法进行决策。 解：(1)悲观法        计算各策略的损益情况及最小收益，见表1。 表1 事 件 min 0 10 20 30 40 策略 0 0 0 0 0 0 0 10 -10 50 50 50 50 -10 20 -20 40 100 100 100 -20 30 -30 30 90 150 150 -30 40 -40 20 80 140 200 -40                 根据max min准则，可得  。它对应的策略为 ，即决策者选择“什么也不生产”，在实际中表示持观望态度。            (2) 后悔值法 计算各方案在不同事件中的后悔值及最大后悔值，具体见表2。 表2 事 件 max 0 10 20 30 40 策略 0 0 50 100 150 200 200 10 10 0 50 100 150 150 20 20 10 0 50 100 100 30 30 20 10 0 50 50 40 40 30 20 10 0 40                 根据后悔值法，可得 即决策者选择生产40件的方案。 6．用Gomory割平面法求解以下ILP问题 解 原问题的松弛问题为 增加松弛变量 ，将问题化为 (1) 用单纯形法求得最优解 ，最优值为 。由于最优 解不是整数解，所以生成割平面： (2) 将(2)添加到(1)中 得到问题P1，再用对偶单纯形法求解得最优解 ，仍不是整数解。生成割平面 (3) 将(3)添加到问题P1中，并用对偶单纯形法求解得最优解 ，它是原问题的最优解。 7. 建立数学模型 某厂生产A,B两种产品，每件产品均要在甲、乙、丙各台设备上加工．每件第j种产品在第 台设备上加工消耗工时为 ， ．现在各台设备可用于生产这两种产品的工时分别为 ．每件第j种产品可以提供利润 根据需要A,B产品的生产量不能少于 件， ．而生产的A,B产品数量必须取整数．问如何安排生产能使该厂利润最大？试建立该问题的数学模型． 解：设A，B产品的生产量分为 和 件，该问题的数学模型为 8. 下图中的点表示8个城市，它们之间的边表示连接它们的道路，边上的数字表示道路的长度.现在要沿着已有的道路铺设电缆，将8个城市连接起来，使全部通上更新的电话线.问如何铺设电缆使总的线路长度最短？（路长的单位为千米） 解.铺设电缆的的道路为12，24，34，46，56，57，68，它们构成图的一棵最小树.总长度为1400公里. （方法不唯一，可以用破圈法或Kruskal算法），计算的迭代结果如下图所示：（15分） 10. 用Ford-Fulkerson算法求下图所示有向网络中从s到t的最大流. 解.最大流的值为4，其中 其它 其迭代结果如下图所示．（15分） 11.用Kruskal算法求下图所示网络中的最小树. 解.所求的最小树为T=G[{12},{45},{14},{35}]．用Kruskal算法，计算的迭代结果如下图所示：（15分）