2024年《运筹学基础》复习要点。
一、基本概念与理论。
1．任意多个凸集的交集还是凸集。
2．任意多个凸集的并集不一定是凸集。
3．给定及非零向量，称集合是的一个超平面。
4．由超平面的两个半平面。
和。都是凸集。
5．设是凸集，。若对任何，以及任何，都有，则称为的顶点。
6．如果一个lp问题无界，则它的对偶问题必无可行解。
7．设分别为原始lp问题、对偶问题的可行解，若，则原始lp问题、对偶问题的最优解分别为。
8.可行解是基本可行解的充分必要条件是的正分量，所对应的中列向量线性无关。
9.写出lp问题的对偶问题。
的对偶问题是：
10．设一个标准形式的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．乐观法。
决策者从最乐观的观点出发，对每个方案按最有利的状态发生来考虑问题，即求出每个方案在各自然状态下的最大报酬值。然后从选取最大报酬值最大的方案为最优方案，即决策准则为。
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方案“猜白”的期望收益为。
方案“猜黑”的期望收益为。
因，所以方案“猜黑”为最优方案5分）
设状态白的概率为，状态黑的概率为，。
方案“猜白”的期望收益为。
方案“猜黑”的期望收益为。
令，由，可解得。
因此，当时，方案“猜黑”为最优方案10分）
3.某公司有两种方案：甲方案与乙方案。损失与收益见表1。
表1 两方案的损益单位：万元。
为使期望收益最大，应选哪个方案？并对最优方案进行灵敏度分析。
解：方案甲的期望收益为。
方案乙的期望收益为。
因，所以甲方案为最优方案。
设经济繁荣的概率为，经济萧条的概率为，。
方案甲的期望收益为1)
方案乙的期望收益为2)
令，由(1),(2)与，解得。
当时，甲方案为最优方案。
4.某工厂平均每天有一台机器发生故障需修理，故障数服从泊松分布。一台机器因修理，每天工厂平均损失20元。
现有技术水平不同的修理工人甲和乙。甲平均每天修1.2台，每天工资12元。
乙平均每天修1.5台，每天工资20元。两修理工修理机器的时间服从指数分布，问工厂应录用哪一个修理工？
并对最优决策关于每天工资进行灵敏度分析。
运筹学复习要点
二 线性规划。1 主要内容。线性规划问题的数学模型，可行区域与基本可行解等概念，具有二个决策变量的线性规划问题的 法，单纯形方法，对偶性及对偶单纯形法，灵敏度分析。2 目的和要求 1 掌握建立线性规划问题数学模型的方法。2 理解可行域 基 基本可行解等概念。3 熟练掌握线性规划问题的 法。4 理解单...
运筹学复习要点
运筹学复习范围。考试形式。开卷。考试题形。1 填空题 5题，每题4分，共20分 2 问答题 4题，每题8分，共32分 3 计算题 2题，共48分 复习范围。1 性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2 性规划问题中，法适合用于处理两个变量的线性规划问题。3 线性规划问题的每一个...
运筹学复习要点
第一章，绪论。1 运筹学涵义。目标，约束，系统优化。2 运筹学模型的建立。明确问题 基本元素 决策变量，参数，约束阈值，目标度量 基本元素的结合关系 自然科学原理 工程技术和社会科学原理 第二章，线性规划。1 线性规划的三个要素，目标函数，约束条件，决策变量。2 线性规划的变量类型，决策变量，松弛变...