运筹学补考复习知识点归纳及样题.docx

运筹学补考复习知识点归纳及样题总体要求：1、2小时，闭卷考试；2、只需带黑色签字笔、铅笔、橡皮，不要带书包、纸来。绘图部分可以用铅笔，其余部分不得用铅笔、圆珠笔答题。3、五道题目，每题20分，每题小问可能包含计算、简答、填空、作图。比照样题答题，解题步骤不规范、说明不清楚要扣分。4、以下给出的全部是样题，而不是原题。需要你比照样题复习、掌握课件中讲过的所有知识点。样题中不可能将所有考点都告诉你。填空填写计算表达式而非公式。5、考试时间和地点：开学的第一周，地点等候通知；6、考试无须带计算器，但你自己还是需要有一定的笔算能力。7、遵守考试纪律，作弊严惩不贷。一、线性规划之“运输问题”的建模与求解1、样题：已知某运输问题其供销关系及单位运价、各产地产量、各销地销量如表1所示，问如何调运物品，使得总运输费用（单位：百元/万件）最小？表1 产销平衡表和单位运价表 销地Bj产地AiB1B2B3产量（万件）A14258A23537A31334销量（万件）485要求：（1）请建立该问题的线性规划模型；（2）如果有必要再化为标准问题。（3）用表上作业法求解：用最小元素法确定初始方案（如果每一步划线之初同时有多个最小运价元素，请从行、列标号最小的元素开始进行分配；如果未进行到最后一步但需要补充0元素作为基变量，请加在与该剩余最小元素所画十字线上运价最小且未分配运量的位置）；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整（如果调整后得到多个0元素，将对应运价最小的0元素保留为基变量），直至求出最优方案。解：（1）设从产地Ai调运到销地Bj的物品为xij万件，可建立如下线性规划模型： （2） 总产量=8+7+4=19总销量=4+8+5=17，所以这是产大于销的非标准运输问题。可增加虚拟销地即库存积压仓库B4，各个产地到它的单位运价都是0，它的虚拟销量即生产过剩量为2万件（=19-17）。（3）第一步：用最小元素法确定初始方案，如下所示： 第二步：求非基变量检验数，验证初始方案是否最优。法一：用位势法求检验数。求解见表2所示： 表2销地产地B1B2B3B4UiA14320550 00A2-1053030-33A3013331000Vj1200 因为min(11,13,21,24,33,34|ij0)=24= -30，所以初始方案并非最优方案，需进一步调整，x24为进基变量。24表示如果产地A2增运1万件物品给虚拟销地B4，将导致初始方案总运费减少3百元。法二：用闭回路法求非基变量检验数11=4-0+0-1=3；13=5-3+5-2=5；21=3-5+2-0+0-1=-1；24=0-5+2-0=-3 32=3-2+0-0=1；33=3-3+5-2+0-0=3（注：图中画出了非基变量x21的闭回路）；下面“验证初始方案是否最优”的分析同“法一”。第三步：求值，调整初始方案，得到改进方案二X1。过程如下：以X24作为进基变量，由其所在闭回路的偶数序号格调运量确定调整量min(2,2)=2，按照“奇加偶减”的原则所示进行调整，选择x22作为出基变量但保留调整后为0运量的x14。用伏格尔法求出的初始方案就是调整方案X1。用位势法可求出方案二X1的非基变量检验数，如表3所示：表3销地产地B1B2B3B4UiA14320520 00A2235303000A3010331000Vj1230因为所有非基变量检验数都不小于0但33=0，所以本题有无穷多最优解。再以x33为进基变量比照上述方法进行方案调整，可得到另一个最优方案，如下：，这个方案实际上与调整方案X1是相同的。决策结论：产地A1向销地B2调运物品8万件；产地A2向销地B3调运物品5万件；产地A3向销地B1调运物品4万件；产地A2存在过剩生产物品2万件，存放在积压仓库B4。最小总运费=82+53+20+41=35（百元）。2、复习知识点：（1）产大于销、或者销大于产的运输问题建模（第三版89页（第4版104页）“模型可写成”一直到“由于总的产量”之前的模型这是“产大于销”的情形；如果是第二种情况，则模型约束条件中的符号变为:“=ai”、“bj”，其余与前者相同）；（2）判断题目中的运输问题是否为标准运输问题（判别方法见第三版89页（第4版104页）“前面讲的表上作业法”那一段文字，标准化一定是产销平衡，不平衡就是非标准运输问题）。如果不是，请转化为标准问题，要掌握“（1）中”所述两种非标准运输问题进行标准化的方法（见第三版90页（第4版105页）从“若当产大于销时”到“同样可以转化为一个产销平衡的运输问题。”为止的叙述。）。（3）熟练掌握用表上作业法求标准运输问题最优解的方法：用最小元素法确定初始方案；用位势法或者闭回路法求变量检验数并能据此判别当前解是哪一种情形（唯一最优解还是多个最优解？）；用闭回路求值法调整初始方案。（4）下结论，会求最小总费用会判断是哪一个产地产量过剩或者哪一个销地销量未满足。（5）应该知道ij=某个值的经济涵义。以下这两个知识点你在做考试题时会用上，当然不会出简单题，而是融入具体做法来考。（6）在用最小元素法确定初始方案的过程中，如果某元素对应的行产量和列销量相等，该如何处理？ 答：如果每一步划线之初同时有多个最小运价元素，请从行、列标号最小的元素开始进行分配（如样题首先选择了第1行第4列的0元素进行分配）；如果未进行到最后一步但需要补充0元素作为基变量，请加在与该剩余最小元素（如运价为“1”的元素）所画十字线上（样题中即是划去了第1列和第3行的十字线）运价最小（样题中可以添0的位置有5个，即x11、x21、x32、x33、x34，但x34对应的运价c34=0是这五个位置中最小的，所以选择在x34位置添加0将其作为基变量）且未分配运量（如样题中x34在添0之前并未分配运量）的位置。（7）在用闭回路求值的过程中，如果最小值对应多个基变量，又该如何处理？ 答：如果进基变量所在闭回路上的顶点偶数序号格（如在本样题中即是x14和x22所在位置），减去值进行调整后得到多个0元素（本样题中：x14-2=x22-2=0，所以得到两个0元素），将对应运价最小的0元素保留为基变量（在本样题中，将x34=0明确写出来而非变成非基变量即空格，因为c34=0c22=5。也就是说：x34仍保留为基变量，但x22为出基变量变为空格（实际上取值还是0，非基变量取值一律等于0但不写出来）。）二、线性整数规划之“指派问题”的建模与求解1、样题分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间（单位：小时）如表4所示。如果：a.甲或丙之中有一人完成两项任务，乙和丁各完成一项；b.每人只能完成一项，其中A和B必须完成，C、D、E中可以有一项不完成，甲必须做任务A或C，E不能交给乙来做。要求：（1）对于问题a请给出标准化以后的效率矩阵并用匈牙利法求出最优分配方案；（2）对于问题b建立线性整数规划模型，然后写出标准化以后的效率矩阵，但不必求解。表4人 任务ABCDE甲乙丙丁2539342429382742312628364220432337333230解：（1）标准化以后的效率矩阵见表5：表5 任务人ABCDE甲2529314237乙3938262035丙3427284332丁2442362330戊2527284232 由于任务数5多于人数4，所以本题并非标准指派问题。增添一名假想的人戊。其完成各项工作的效率为甲、丙完成同一项工作效率的最小值。求解过程如下：m=n=35试指派不成功指派 结束m=n= 5结论：最优分配方案：甲A；乙D；丙B和C；丁E。最少的总时间为：25+20+28+30+27=130小时。（2）设i=1,2,3,4;j=1,2,.,5。该问题的0-1整数规划模型如下：由于任务数5多于人数4，所以本问题不是标准指派问题。增添一名假想的人，设为戊。其完成各项工作的效率分别为M、M、0、0、0。（注解：完工效率M(一个很大的正数)说明任务A、B不能交给虚拟人戊来做，甲肯定不能做任务B、D和E，乙不能做任务E）。效率矩阵如表6所示：表6人 任务ABCDE甲乙丙丁戊25393424MM382742M312628360M2043230MM323002、知识点：（1）人多任务少、人少任务多两种非标准指派问题的建模；（2）上述两种非标准指派问题的标准化方法；（3）会用0-1变量表达式写出某人不能完成某些任务、或者某人必须完成某项任务、或者某任务可完成也可不完成的约束条件；在效率矩阵中，会应用大M处理这些情况。（4）熟练掌握用匈牙利法求解指派问题最优解法方法和步骤；并且可以求出最优分配方案和最小总时间（或总费用）。 注解：上述知识复习，请看第三版126130页有关内容或者第4版146151页有关内容，其中的定理证明可不看，可比照例题以及本样题掌握解题方法和步骤。三、动态规划之“一维资源连续分配问题”的建模与求解1、样题（注解：考试时题目计算量比样题要小，可能只有三个阶段）某厂有100台设备，可用于加工甲，乙两种产品。据以往经验，这些设备加工甲产品每季末损坏1/3，而加工乙产品每季末损坏1/10，损坏的设备当年不能复修。每台机器一季全加工甲或乙产品，其创利为10或7百元。问如何安排各季加工任务，能使全年获利最大？请建立该问题的动态规划模型并用逆序解法求解，画出状态转移图得出结论。解：（1）将问题按季度数分为4个阶段，k=1,2,3,4。设状态变量 sk ：表示第k季度初拥有的完好设备的台数。s1=100。设决策变量uk：表示第k季度初投入甲产品生产的设备台数，则投入乙产品生产的设备台数vk =sk -uk。显然uk Dk(sk) =uk|0uksk。 状态转移方程：sk +1=auk+bvk =2/3uk+9/10(sk -uk) 。指标函数：阶段指标函数dk(Sk,uk)表示第k期从Sk台设备中抽出uk台投入甲产品生产、sk -uk台投入乙产品生产时得到的利润。dk(Sk,uk)10uk+7(sk -uk) ；最优指标函数fk(sk)表示sk台设备从第k至第4期分配时所得到的最大利润总和.逆序解法的基本方程如下：（2）用逆序解法求解第4阶段，k=4 s5= 2/3u4+9/10(s4 u4)u4*=s4时f4(s4)=10s4。第3阶段，k=3 s4= 2/3u3+9/10(s3 u3)u3*=s3时f3(s3)=50/3s3。第2阶段，k=2 s3= 2/3u2+9/10(s2 u2)u2*=0时f2(s2)=22s2。第1阶段，k=1 s2= 2/3u1+9/10(s1 u1)u1*=0时f1(s1)=134/5100=2680百元，这就是四期的最大总利润和。U4*(54)=54U3*(81)=81U2*(90)=0U1*(100)=0状态转移图如图1所示：k=4s5=2/3u4+9/10(s4-u4)k=3s4=2/3u3+9/10(s3-u3)k=2s3=2/3u2+9/10(s2-u2)k=1s2=2/3u1+9/10(100-u1)S1*=100S5*=36S2*=90S3*=81S4*=54d3*(81,81)=810d3*(54,54)=504d2*(90,0)=630d1*(100,0)=700图1 一维资源连续分配问题的状态转移图由状态转移图得出结论：全年最大获利即f1(s1)=2680百元。最优分配方案如下：四个季度投入甲产品生产的设备数量分别为0、0、81、54台。2、知识点：（1）“一维资源连续分配”问题的动态规划建模。可见讲课课件、本样题求解第一部分或者课本：第三版217页（或第四版253254页）从“设阶段序数k”一直到“从第5年度开始”之前的叙述。（2）掌握用逆序解法求解动态规划模型的方法和步骤。可比照本样题求解第二部分、讲课课件或者课本：第三版217218页（或第四版254255页）从“当k=5时，有”下面进一步来讨论始端固定”之前的叙述。（3）掌握用状态转移图来顺向推到最优决策变量、状态变量、阶段指标函数的方法，请看样题求解第二部分的图，或者课本第三版203页图8-6（或第四版238页图9-6）。（4）会求出全过程最优指标值，并且知道其确定的依据。请看本样题的结论部分就有说明。四、图论之“最小费用最大流”问题的求解1、样题：试用对偶法求图2所示的最小费用最大流。图中数字（cij,bij, fij）分别代表弧（vi,vj）容量、单位流量费用（元）和当前可行流。(6,2,4)(10,3,4)(10,4,6)(8,1,5)(1,5,1)(7,1,7)(2,8,0)v3v2vsvtv1图2 v1v1解：用对偶法求解（费用路a、c、e中标记“”的为最短路），如图3(a)(e)所示：(7,1,7)(10,4,7)vtvsv2v3-1-4-1(a)W(f(0)23814vtv3v2vs(b)f(1)=7+5=12(10,3,5)(6,2,5)(2,8,0)(1,5,0)(8,1,5)-5-2-3(vs,+)v11-1-3(c)W(f(1)vtvsv1v2v38-1432-4(7,1,7)vsv2v3(1,5,0)(8,1,6)(10,4,7)(10,3,6)(d)f(2)=7+6=13vt(6,2,6)(2,8,0)-25(vs,+)(v1,+)(vs,+)-2-3(e)W(f(2)vtvsv1v2v38-1-143-415图3因为图e中找不到从vs到vt的费用路，所以f(2)为最小费用最大流。 Max f=fs1+fs2=7+6=13，最小总费用=47+16361726=71（元）。在图（d）中用ford-fulkerson标号法求从vs到vt的流量增广路，过程如下：给vs标（vs,+）检查vs：给v1标（vs,+），因为fs1=7cs1=10；给v2标（vs,+），因为fs2=6cs2=8。检查完毕，vs标（vs,）。检查v1：vt不标，因为f1t=7=c1t；给v3标（v1,+），因为f13=00.4；当m=4时，P0=0.31070.4。故取m=3，即至多只能设置3个通道,P0=0.4507。各状态间概率强度的转移图如图4所示：=12=203=3132444图4状态转移概率的差分方程，如下： -3P0+4P1=0 (3-n+1)Pn-1+4Pn+1=(3-n)+4Pn (n=1,2) P2-4P3=0（2）在正常导通状态下所有通道都发生故障的概率：发生故障通道的平均数：（3）在正常导通状态下每个通道的平均损坏时间：通道发生故障后等待修理的平均等待时间：（4）当=5时，租用该种先进设备是划算的。2、补考复习知识点及要求（1）会判断排队系统属于哪一种类型，明确各种基本参数（，和m）的值。能够画出系统生灭过程状态转移图并写出稳态时系统状态转移差分方程（要求带入和具体值）。（2）记住计算公式，会求基本效率参数：P0、Pn（i=1,2.,m）、Ls、Lq、Ws、Wq、有效达到率e。但考试书写时不能写计算公式而只能写计算表达式。（3）会进行排队系统的运行效率和成本费用优化（参看上述第（4）问解答）。（4）课本：第三版323324页或第4版371页例5。