2015年运筹学补考复习知识点归纳及样题

《运筹学》补考复习知识点归纳及样题总体要求：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万件，可建立如下线性规划模型：11121321222331323311121321222331323311213112223213233387448542535333===0123≤≤≤≥ijmiinzxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxi,j,,（2）∵总产量=8+7+4=19总销量=4+8+5=17，所以这是产大于销的非标准运输问题。可增加虚拟销地即库存积压仓库B4，各个产地到它的单位运价都是0，它的虚拟销量即生产过剩量为2万件（=19-17）。（3）第一步：用最小元素法确定初始方案，如下所示：622540425086035307204013304852(0)(2)(0)(0)(0)0622540初始调运方案X第二步：求非基变量检验数，验证初始方案是否最优。法一：用位势法求检验数。求解见表2所示：表2销地产地B1B2B3B4UiA130500A2-100-33A301300Vj1200因为min(σ11,σ13,σ21,σ24,σ33,σ34|σij0)=σ24=-30，所以初始方案并非最优方案，需进一步调整，x24为进基变量。σ24表示如果产地A2增运1万件物品给虚拟销地B4，将导致初始方案总运费减少3百元。法二：用闭回路法求非基变量检验数622540425035301330σ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。过程如下：+--1628025+=524040X以X24作为进基变量，由其所在闭回路的偶数序号格调运量确定调整量θ＝min(2,2)=2，按照“奇加偶减”的原则所示进行调整，选择x22作为出基变量但保留调整后为0运量的x14。用伏格尔法求出的初始方案就是调整方案X1。用位势法可求出方案二X1的非基变量检验数，如表3所示：425035301330表3销地产地B1B2B3B4UiA130200A223000A301000Vj1230因为所有非基变量检验数都不小于0但σ33=0，所以本题有无穷多最优解。再以x33为进基变量比照上述方法进行方案调整，可得到另一个最优方案，如下：2805240*X，这个方案实际上与调整方案X1是相同的。决策结论：产地A1向销地B2调运物品8万件；产地A2向销地B3调运物品5万件；产地A3向销地B1调运物品4万件；产地A2存在过剩生产物品2万件，存放在积压仓库B4。最小总运费=8×2+5×3+2×0+4×1=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所在425035301330位置），减去θ值进行调整后得到多个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解：（1）标准化以后的效率矩阵见表5：表5由于任务数5多于人数4，所以本题并非标准指派问题。增添一名假想的人戊。其完成各项工作的效率为甲、丙完成同一项工作效率的最小值。求解过程如下：-min0451772529314237-2504617123938262033-201918601319185083427284332-277011657002442362330-2311913072527284232-250231771601191202022172-min00-10-5045177191850870016011912020min023175-21916306-2900-2-222172√√√√1801171000000170023175191630690或01801171000000170+2+2√√结论：最优分配方案：甲――A；乙――D；丙――B和C；丁――E。最少的总时间为：25+20+28+30+27=130小时。人任务ABCDE甲乙丙丁2539342429382742312628364220432337333230任务人ABCDE甲2529314237乙3938262035丙3427284332丁2442362330戊2527284232∵m=n=35∴试指派不成功∵m=n=5∴指派结束（2）设j1ij0，表示指派第人做第项任务，否则ixi=1,2,3,4;j=1,2,...,5。该问题的0-1整数规划模型如下：451112345123412341113251(i1,2,3,4)1(j1,2)1(j3,4,5)..+1=001≤++++++++++或ijijijiiiiijjjjjjjjijminzcxxxxxxxxxxxxxxstxxxx由于任务数5多于人数4，所以本问题不是标准指派问题。增添一名假想的人，设为戊。其完成各项工作的效率分别为M、M、0、0、0。（注解：完工效率M(一个很大的正数)说明任务A、B不能交给虚拟人戊来做，甲肯定不能做任务B、D和E，乙不能做任务E）。效率矩阵如表6所示：表62、知识点：（1）人多任务少、人少任务多两种非标准指派问题的建模；（2）上述两种非标准指派问题的标准化方法；（3）会用0-1变量表达式写出某人不能完成某些任务、或者某人必须完成某项任务、或者某任务可完成也可不完成的约束条件；在效率矩阵中，会应用大M处理这些情况。（4）熟练掌握用匈牙利法求解指派问题最优解法方法和步骤；并且可以求出最优分配方案和最小总时间（或总费用）。注解：上述知识复习，请看第三版126~130页有关内容或者第4版146~151页有关内容，其中的定理证明可不看，可比照例题以及本样题掌握解题方法和步骤。三、动态规划之“一维资源连续分配问题”的建模与求解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|0≤uk≤sk}。人任务ABCDE甲乙丙丁戊25393424MM382742M312628360M2043230MM32300④状态转移方程：sk+1=auk+bvk=2/3uk+9/10(