运筹学基础复习要点(共13页).doc

《运筹学基础复习要点(共13页).doc》由会员分享，可在线阅读，更多相关《运筹学基础复习要点(共13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上运筹学基础复习要点一、基本概念与理论1任意多个凸集的交集还是凸集。2任意多个凸集的并集不一定是凸集3给定及非零向量，称集合是的一个超平面。4由超平面的两个半平面和都是凸集。5设是凸集，。若对任何，以及任何，都有，则称为的顶点。6如果一个LP问题无界，则它的对偶问题必无可行解。7设分别为原始LP问题、对偶问题的可行解，若，则原始LP问题、对偶问题的最优解分别为。8.可行解是基本可行解的充分必要条件是的正分量，所对应的中列向量线性无关。9.写出LP问题的对偶问题 的对偶问题是： 10设一个标准形式的LP问题的基为，右端向量为，则对应的基本解是。11线性规划问题的可行域是凸

2、集。12设线性规划问题LP为为一个基，对应的典式为其中。13.线性规划问题的规范形式为14. 线性规划问题的标准形式为15.线性规划问题的一般形式为 16.对线性规划问题，关于它的解分三种情况：问题无解、问题无界和问题有最优解。17.如果一个LP问题有最优解，则它的对偶问题必有最优解。18.一个标准形式的LP问题，若有可行解，则至少有一个基本可行解。19.若标准形式的LP问题有有限最优解，则一定存在一个基本可行解是最优解。20原始LP问题的任一可行解的目标函数值不小于其对偶问题任一可行解的目标函数值。21可行解是基本可行解的充分必要条件是为可行域的顶点。22设简单图无向，则。23设简单图有向，

3、则，。24.握手定理：设无向图，则（或所有顶点的度数之和等于边数的两倍）。25每个树至少有两个次数为1的点。26有支撑树当且仅当是连通的。27设为的一个支撑树，则是的最小树当且仅当对任意边（的补树）有其中为唯一的回路。28设为的一个支撑树，则是的最小树当且仅当对任意边有其中为唯一割集。29一个排队系统由三个基本部分组成：输入过程、排队规则和服务机构。30最简单流满足三个条件：平稳性、无后效性和普通性。31设有某系统，具有状态集，若系统的状态随时间变化的过程满足以下条件，则称为一个生灭过程。 设在时刻系统处于状态的条件下，再经过长为（微小增量）的时间。 （1）转移到（）的概率为； （2）转移到（

4、）的概率为；（3）转移到的概率为，其中，为与无关的固定常数。32.一个生灭过程，则生灭过程在时的概率为，。33决策问题通常分为三种类型：确定型决策、风险型决策和不确定型决策。34.一个决策模型主要由四个部分组成：状态集、决策集、报酬函数和决策准则35.风险型决策的主要方法有最大可能法和期望值法两种。36最大可能法是在风险型决策中选择一个概率最大的自然状态进行决策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。37不确定型决策的主要方法有乐观法、悲观法、乐观系数法、后悔值法和等可能法等。38一个对策模型由三个部分组成：局中人、策略集和支付函数。39

5、矩阵对策，等式成立的充要条件是存在局势，使。40矩阵对策在它的混合扩充中存在解。41.工件的加工时间（单位：分钟）如下：其中中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为 。 42. 工件的加工时间（单位：分钟）如下：其中中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为 。 43.工件的加工时间（单位：分钟）如下：其中中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为 44对标准形式的线

6、性规划，叙述单纯形法的步骤： 第1步 找一个初始可行基； 第2步 求出对应的典式及检验数向量；第3步 求；第4步 若，停止；已找到最优解及最优值；第5步 若，停止。原问题无解；第6步 求；第7步 以代替得到新的基，转到第2步。45对ILP问题(P)，Gomory割平面法的计算步骤：第1步 用单纯形法解ILP问题(P)的松弛问题(P0)。若(P0)没有最优解，则计算停止，问题(P)也没有最优解。若(P0)有最优解，假如是整数向量，则是(P)的最优解，计算停止，输出；否则转到第2步； 第2步 求割平面方程任选的一个非整数分量，按，（其中为非基变量下标集合），得到割平面方程 （*）第3步 将割平面方

7、程（*）加到第1步所得到的最优单纯形表中，用对偶单纯形法求解这个新的松弛问题。若其最优解为整数解，则是问题（P）的最优解，计算停止，输出这个最优解；否则将这个最优解重新记为，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时原ILP是不可行的，计算停止。46.叙述求最小树的Kruskal算法的基本思想和步骤。Kruskal算法的基本思想是从的条边中选取条权尽可能小的边，并且使得不构成回路，从而构成一个最小树。 Kruskal算法的步骤：第1步 从中选一条权最小的边；第2步 若已选出，则从中选，使得（1） 中无圈，（2）。第3步 反复执行上述过程直至选出止。47.叙述求最小树的Dijkst

8、ra算法的基本思想和步骤。Dijkstra算法的基本思是从的个独立割集中的每一个都选一条权最小的边，从而构成一个最小树。Dijkstra算法的步骤：第1步 置，；第2步 取，置，；第3步 若，则停止；否则，置，返回地2步。二、名词解释1 互补松紧性：设分别为原始和对偶问题的可行解，则它们分别是原始和对偶问题的最优解的充要条件是，对一切和一切有，。2动态规划的最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对于第一个决策所形成的状态作为初始状态而言，必须构成最优策略。3无向图的边割与割集对于的两个不相交子集和表示一个端点在中，另一个端点在中的边的集合。

9、所谓的边割指的是的形如的子集，其中，从中删除这些边后，的连通分支数严格增加。的极小边称为割集。4乐观法决策者从最乐观的观点出发，对每个方案按最有利的状态发生来考虑问题，即求出每个方案在各自然状态下的最大报酬值。然后从选取最大报酬值 最大的方案为最优方案，即决策准则为。5生灭过程设有某系统，具有状态集，若系统的状态随时间变化的过程满足以下条件，则称为一个生灭过程。 设在时刻系统处于状态的条件下，再经过长为（微小增量）的时间。 （1）转移到（）的概率为； （2）转移到（）的概率为；（3）转移到的概率为，其中，为与无关的固定常数。6最大可能法最大可能法是在风险型决策中选择一个概率最大的自然状态进行决

10、策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。三、计算题1.某工厂医院的一个科室，有一个医生值班。经长期观察，每小时平均有4个病人，医生每小时可诊5个病人。假设病人到达服从泊松分布，医生的诊病时间服从指数分布。试分析该科室的工作状况。如要满足99%以上的病人有座位，此科室至少应设多少个座位。如果该工厂24小时上班，病人看病1小时因误工，工厂要损失30元，这样工厂平均每天损失多少元？若该科室提高看病速度，每小时平均可诊6个病人，工厂可减少损失多少元？解：由已知，从而排队系统的稳态概率为 所以 为满足99%以上的病人有座，设该科室有个座位，则有科

11、室的病人数即 可解得 ，因此，该科室至少应设20个座位。 如果该工厂24小时上班，则每天平均有病人，病人看病所花去的总时间为，所以工厂平均每天损失。如果每小时平均可诊6个病人，类似地计算有，这样单位损失为，因此，工厂减少损失。 2. 假设有外表相同的木盒150只，将其分为两组，一组内装白球，有90盒。一组内装黑球，有60盒。现从150只木盒中任取一盒，请你猜。如这盒内装的是白球，猜对得800分，猜错罚500分；如这盒内装的是黑球，猜对得2000分，猜错罚300分。为使期望收益最大，应选哪一个方案？并对最优方案进行灵敏度分析。2. 解：由已知，可得收益矩阵见表3。表3概 率方案自然状态白0.6黑

12、0.4猜白800-300猜黑-5002000方案“猜白”的期望收益为方案“猜黑”的期望收益为因，所以方案“猜黑”为最优方案。 （5分）设 状态白的概率为，状态黑的概率为，。方案“猜白”的期望收益为 方案“猜黑”的期望收益为 令，由，可解得 。因此，当时，方案“猜黑”为最优方案。 （10分）3.某公司有两种方案：甲方案与乙方案。损失与收益见表1。表1 两方案的损益 单位：万元 概率方案经济繁荣 经济萧条0.70.3甲500-150乙-2001400为使期望收益最大，应选哪个方案？并对最优方案进行灵敏度分析。解：方案甲的期望收益为方案乙的期望收益为因，所以甲方案为最优方案。 设 经济繁荣的概率为，

13、经济萧条的概率为，。方案甲的期望收益为 (1)方案乙的期望收益为 (2)令，由(1),(2)与，解得当时，甲方案为最优方案。 4.某工厂平均每天有一台机器发生故障需修理，故障数服从泊松分布。一台机器因修理，每天工厂平均损失20元。现有技术水平不同的修理工人甲和乙。甲平均每天修1.2台，每天工资12元。乙平均每天修1.5台，每天工资20元。两修理工修理机器的时间服从指数分布，问工厂应录用哪一个修理工？并对最优决策关于每天工资进行灵敏度分析。解：由已知，若录用甲修理工，则， 工厂每天平均费用为元若录用乙修理工，则，工厂每天平均费用为元因，所以录用乙修理工更合算。 设 乙修理工每天的工资为，则录用乙

14、后，工厂每天平均费用为令，可解得 。因此，当乙修理工每天的工资不超过72元时，录用他比甲更合算。 5设某工厂是按批生产某产品并按批销售，每件产品的成本为30元，批发价格为每件35元。若每月生产的产品当月销售不完，则每件损失1元。工厂每投产一批是10件，每月生产能力为40件。决策者可选择的方案为0，10，20，30，40五种。假设决策者对其产品的需求一无所知，试用悲观法和后悔值法进行决策。解：(1)悲观法 计算各策略的损益情况及最小收益，见表1。表1事 件min010203040策略000000010-1050505050-1020-2040100100100-2030-303090150150

15、-3040-402080140200-40根据max min准则，可得 。它对应的策略为，即决策者选择“什么也不生产”，在实际中表示持观望态度。 (2) 后悔值法计算各方案在不同事件中的后悔值及最大后悔值，具体见表2。表2事 件max010203040策略0050100150200200101005010015015020201005010010030302010050504040302010040根据后悔值法，可得即决策者选择生产40件的方案。6用Gomory割平面法求解以下ILP问题解 原问题的松弛问题为增加松弛变量，将问题化为 (1)用单纯形法求得最优解，最优值为。由于最优解不是整数解，

16、所以生成割平面： (2)将(2)添加到(1)中 得到问题P1，再用对偶单纯形法求解得最优解，仍不是整数解。生成割平面 (3)将(3)添加到问题P1中，并用对偶单纯形法求解得最优解，它是原问题的最优解。7. 建立数学模型某厂生产A,B两种产品，每件产品均要在甲、乙、丙各台设备上加工每件第j种产品在第台设备上加工消耗工时为，现在各台设备可用于生产这两种产品的工时分别为每件第j种产品可以提供利润根据需要A,B产品的生产量不能少于件，而生产的A,B产品数量必须取整数问如何安排生产能使该厂利润最大？试建立该问题的数学模型解：设A，B产品的生产量分为和件，该问题的数学模型为8. 下图中的点表示8个城市，它

17、们之间的边表示连接它们的道路，边上的数字表示道路的长度.现在要沿着已有的道路铺设电缆，将8个城市连接起来，使全部通上更新的电话线.问如何铺设电缆使总的线路长度最短？（路长的单位为千米）解.铺设电缆的的道路为12，24，34，46，56，57，68，它们构成图的一棵最小树.总长度为1400公里. （方法不唯一，可以用破圈法或Kruskal算法），计算的迭代结果如下图所示：（15分） 10. 用Ford-Fulkerson算法求下图所示有向网络中从s到t的最大流.解.最大流的值为4，其中其它其迭代结果如下图所示（15分）11.用Kruskal算法求下图所示网络中的最小树.解.所求的最小树为T=G12,45,14,35用Kruskal算法，计算的迭代结果如下图所示：（15分）专心-专注-专业