运筹学基础复习要点

1《运筹学基础》复习要点一、基本概念与理论1．任意多个凸集的交集还是凸集。2．任意多个凸集的并集不一定是凸集3．给定1Rb及非零向量nRa，称集合}|{bxaRxHTn是nR的一个超平面。4．由超平面}|{bxaRxHTn的两个半平面}|{bxaRxHTn和}|{1bxaRxHTn都是凸集。5．设S是凸集，Sx。若对任何zySzSy,,，以及任何10，都有zyx)1(，则称x为S的顶点。6．如果一个LP问题无界，则它的对偶问题必无可行解。7．设wx,分别为原始LP问题、对偶问题的可行解，若bwxcTT，则原始LP问题、对偶问题的最优解分别为wx,。8.可行解x是基本可行解的充分必要条件是x的正分量，所对应的A中列向量线性无关。9.写出LP问题的对偶问题0..minxbAxxctsT的对偶问题是：0..minwcwAwbtsTT10．设一个标准形式的LP问题的基为B，右端向量为b，则对应的基本解是01bBx。11．线性规划问题的可行域是凸集。12．设线性规划问题LP为0..minxbAxtsxcTB为一个基，对应的典式为0..min111xbBNxBxtsxbBczNBTTB其中),0(1TNTBTcNBc。213.线性规划问题的规范形式为0..minxbAxxctsT14.线性规划问题的标准形式为0..minxbAxtsxcT15.线性规划问题的一般形式为nqjxqjxmpibxapibxatsxcjjiTiiTiT,,1,,2,10,,1,,2,1..min为自由变量16.对线性规划问题，关于它的解分三种情况：问题无解、问题无界和问题有最优解。17.如果一个LP问题有最优解，则它的对偶问题必有最优解。18.一个标准形式的LP问题，若有可行解，则至少有一个基本可行解。19.若标准形式的LP问题有有限最优解，则一定存在一个基本可行解是最优解。20．原始LP问题的任一可行解的目标函数值不小于其对偶问题任一可行解的目标函数值。21．可行解x是基本可行解的充分必要条件是x为可行域的顶点。22．设简单图无向),(EVG，则)()(GVvvd||2E。23．设简单图有向),(EVD，则||)()(EvdGVv，||)()(EvdGVv。24.握手定理：设G无向图，则)()(GVvvd|)(|2EV（或所有顶点的度数之和等于边数的两倍）。25．每个树至少有两个次数为1的点。26．G有支撑树当且仅当G是连通的。27．设T为G的一个支撑树，则T是G的最小树当且仅当对任意边*Te（T的补树）有)(max)()(eWeWeCe其中eTeC)(为唯一的回路。28．设T为G的一个支撑树，则T是G的最小树当且仅当对任意边Te有)(max)()(eWeWee其中eTe*)(为唯一割集。29．一个排队系统由三个基本部分组成：输入过程、排队规则和服务机构。330．最简单流满足三个条件：平稳性、无后效性和普通性。31．设有某系统，具有状态集},2,1,0{S，若系统的状态随时间t变化的过程}0);({ttN满足以下条件，则称为一个生灭过程。设在时刻t系统处于状态n的条件下，再经过长为t（微小增量）的时间。（1）转移到1n（n0）的概率为)(totn；（2）转移到1n（n0）的概率为)(totn；（3）转移到}1,,1{nnnS的概率为)(to，其中0n，0n为与t无关的固定常数。32.一个生灭过程}0);({ttN，则生灭过程在t时的概率为01101011nnnnnp，,2,1,011021nppnnnnn。33．决策问题通常分为三种类型：确定型决策、风险型决策和不确定型决策。34.一个决策模型主要由四个部分组成：状态集、决策集、报酬函数和决策准则35.风险型决策的主要方法有最大可能法和期望值法两种。36．最大可能法是在风险型决策中选择一个概率最大的自然状态进行决策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。37．不确定型决策的主要方法有乐观法、悲观法、乐观系数法、后悔值法和等可能法等。38．一个对策模型由三个部分组成：局中人、策略集和支付函数。39．矩阵对策},,{21ASS，等式ijijijjiaamaxminminmax成立的充要条件是存在局势),(**ji，使njmiaaajijiij,,2,1,,,2,1,****。40．矩阵对策在它的混合扩充中存在解。41.工件的加工时间（单位：分钟）如下：4735742763M其中M中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为24531。42.工件的加工时间（单位：分钟）如下：44331742562M其中M中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为25314。43.工件的加工时间（单位：分钟）如下：4635142342M其中M中的第一行表示各零件在甲车床上的加工时间，第二行是各零件在乙车床上的加工时间。按最短总加工时间给出确定零件的加工顺序为3245144．对标准形式的线性规划，叙述单纯形法的步骤：第1步找一个初始可行基B；第2步求出对应的典式及检验数向量；第3步求},,2,1|max{njjk；第4步若0k，停止；已找到最优解01bBxxxNB及最优值bBczTB1；第5步若0kA，停止。原问题无解；第6步求rkrikikiabmiaab},,2,1,0|min{；第7步以kA代替rBA得到新的基，转到第2步。45．对ILP问题(P)，Gomory割平面法的计算步骤：第1步用单纯形法解ILP问题(P)的松弛问题(P0)。若(P0)没有最优解，则计算停止，问题(P)也没有最优解。若(P0)有最优解0x，假如0x是整数向量，则0x是(P)的最优解，计算停止，输出0x；否则转到第2步；第2步求割平面方程任选0x的一个非整数分量)0(mlbl，按Sjfaaljljlj,][，Sjfbblll,][（其中S为非基变量下标集合），得到割平面方程5ljSjljfsxf（*）第3步将割平面方程（*）加到第1步所得到的最优单纯形表中，用对偶单纯形法求解这个新的松弛问题。若其最优解为整数解，则是问题（P）的最优解，计算停止，输出这个最优解；否则将这个最优解重新记为0x，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时原ILP是不可行的，计算停止。46.叙述求最小树的Kruskal算法的基本思想和步骤。Kruskal算法的基本思想是从G的m条边中选取1n条权尽可能小的边，并且使得不构成回路，从而构成一个最小树。Kruskal算法的步骤：第1步从)(GE中选一条权最小的边1e；第2步若ieee,,,21已选出，则从},,,{)(21ieeeGE中选1ie，使得（1）}],,,[{121ieeeG中无圈，（2）min)(eW。第3步反复执行上述过程直至选出1ne止。47.叙述求最小树的Dijkstra算法的基本思想和步骤。Dijkstra算法的基本思是从G的1n个独立割集中的每一个都选一条权最小的边，从而构成一个最小树。Dijkstra算法的步骤：第1步置jjwu1，T，}1{R，},,3,2{nS；第2步取ikjSjkwuu}{min，置}{ikeTT，}{kRR，}{\kSS；第3步若S，则停止；否则，置Sjwuukjjj},,{min，返回地2步。二、名词解释1．互补松紧性：设wx,分别为原始和对偶问题的可行解，则它们分别是原始和对偶问题的最优解的充要条件是，对一切mi,,2,1和一切nj,,2,1有0)(iTiiibxawu，0)(jjTjixAwcv。2．动态规划的最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对于第一个决策所形成的状态作为初始状态而言，必须构成最优策略。3．无向图),(EVG的边割与割集6对于V的两个不相交子集S和T表示一个端点在S中，另一个端点在T中的边的集合。所谓),(EVG的边割指的是E的形如},{SS的子集，其中SVS\，从),(EVG中删除这些边后，),(EVG的连通分支数严格增加。),(EVG的极小边称为割集。4．乐观法决策者从最乐观的观点出发，对每个方案按最有利的状态发生来考虑问题，即求出每个方案在各自然状态下的最大报酬值。然后从选取最大报酬值最大的方案为最优方案，即决策准则为})},(min{{max:SxAaxaR。5．生灭过程设有某系统，具有状态集},2,1,0{S，若系统的状态随时间t变化的过程}0);({ttN满足以下条件，则称为一个生灭过程。设在时刻t系统处于状态n的条件下，再经过长为t（微小增量）的时间。（1）转移到1n（n0）的概率为)(totn；（2）转移到1n（n0）的概率为)(totn；（3）转移到}1,,1{nnnS的概率为)(to，其中0n，0n为与t无关的固定常数。6．最大可能法最大可能法是在风险型决策中选择一个概率最大的自然状态进行决策，把这种自然状态发生的概率看作1，而其他自然状态发生的概率看作0，将风险型决策转化为确定型决策。三、计算题1.某工厂医院的一个科室，有一个医生值班。经长期观察，每小时平均有4个病人，医生每小时可诊5个病人。假设病人到达服从泊松分布，医生的诊病时间服从指数分布。试分析该科室的工作状况。如要满足99%以上的病人有座位，此科室至少应设多少个座位。如果该工厂24小时上班，病人看病1小时因误工，工厂要损失30元，这样工厂平均每天损失多少元？若该科室提高看病速度，每小时平均可诊6个病人，工厂可减少损失多少元？解：由已知，8.0,5,4，从而排队系统的稳态概率为,2,1,0,8.02.0)1(npnnn所以)(2.3)(41人，人系队系LLL)(8.01)(1小时，小时系队系系WWLW7为满足99%以上的病人有座，设该科室有m个座位，则有P{科室的病人数m}99.0即99.01)1(100mmnnmnnp可解得20m，因此，该科室至少应设20个座位。如果该工厂24小时上班，则每天平均有病人)(96424人，病人看病所花去的总时间为)(96196小时，所以工厂平均每天损失)(28809630元。如果每小时平均可诊6个病人，类似地计算有)(34)(2人，人队系LL，)(31)(5.0小时，小时队系WW这样单位损失为)(1440305.096元，因此，工厂减少损失)(144014402880元。2.假设有外表相同的木盒150只，将其分为两组，一组内装白球，有90盒。一组内装黑球，有60盒。现从150只木盒中任取一盒，请你猜。如这盒内装的是白球，猜对得800分，猜错罚500分；如这盒内装的是黑球，猜对得2000分，猜错罚300分。为使期望收益最大，应选哪一个方案？并对最优方案进行灵敏度分析。2.解：由已知，可得收益矩阵见表3。表3概率方案自然状态白0.6黑0.4猜白800-300猜黑