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

1、运筹学补考复习知识点归纳及样题总体要求：1、2 小时，闭卷考试；2、只需带黑色签字笔、铅笔、橡皮，不要带书包、纸来。绘图部分可以用铅笔，其余部分不得用铅笔、圆珠笔答题。3、五道题目， 每题 20 分，每题小问可能包含计算、简答、 填空、作图。 比照样题答题，解题步骤不规范、说明不清楚要扣分。4、以下给出的全部是样题，而不是原题。需要你比照样题复习、掌握课件中讲过的所有知识点。样题中不可能将所有考点都告诉你。填空填写计算表达式而非公式。5、考试时间和地点：开学的第一周，地点等候通知；6、考试无须带计算器，但你自己还是需要有一定的笔算能力。7、遵守考试纪律，作弊严惩不贷。一、线性规划之“运输问题”

2、的建模与求解1、样题：已知某运输问题其供销关系及单位运价、各产地产量、各销地销量如表1 所示，问如何调运物品，使得总运输费用（单位：百元/万件）最小？表 1 产销平衡表和单位运价表销地 bj产地 ai b1b2b3产量（万件）a14 2 5 8 a23 5 3 7 a3 1 3 3 4 销量（万件）4 8 5 要求：（1）请建立该问题的线性规划模型；（2）如果有必要再化为标准问题。（3）用表上作业法求解：用最小元素法确定初始方案（如果每一步划线之初同时有多个最小运价元素， 请从行、 列标号最小的元素开始进行分配；如果未进行到最后一步但需要补充0 元素作为基变量， 请加在与该剩余最小元素所画十字

3、线上运价最小且未分配运量的位置）；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整 （如果调整后得到多个0 元素，将对应运价最小的0 元素保留为基变量） ，直至求出最优方案。解： （1）设从产地ai调运到销地bj的物品为xij万件，可建立如下线性规划模型：11121321222331323311121321222331323311213112223213233387448542535333=01 2 3ijmiin zxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxi, j, ,（ 2） 总产量 =8+7+4=19总销量 =4+8+5=17，所以这是产大于

4、销的非标准运输问题。可增加虚拟销地即库存积压仓库b4，各个产地到它的单位运价都是0，它的虚拟销量即生产过剩量为 2 万件（ =19-17） 。（3）第一步：用最小元素法确定初始方案，如下所示：62254042508 6035307 204 01330 4 8 5 2 (0) (2) (0) (0) (0)0622540初始调运方案 x第二步：求非基变量检验数，验证初始方案是否最优。法一 ：用位势法求检验数。求解见表 2 所示：表 2 销地产地b1 b2 b3 b4 ui a1 3 0 5 0 0 a2 -1 0 0 -3 3 a3 0 1 3 0 0 vj 1 2 0 0 因为 min(11,

5、13,21,24,33,34| ij0)=24= -30，所以初始方案并非最优方案，需进一步调整，x24为进基变量。 24表示如果产地a2增运 1 万件物品给虚拟销地b4，将导致初始方案总运费减少3 百元。法二：用闭回路法求非基变量检验数62254042503530133011=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。过程如下：+

6、-1628025+=524040x以 x24作为进基变量，由其所在闭回路的偶数序号格调运量确定调整量min(2,2)=2，按照 “奇加偶减” 的原则所示进行调整，选择 x22作为出基变量但保留调整后为0 运量的 x14。用伏格尔法求出的初始方案就是调整方案x1。用位势法可求出方案二x1的非基变量检验数，如表3 所示：4 2 5 0 3 5 3 0 1 3 3 0 表 3 销地产地b1 b2 b3 b4 ui a1 3 0 2 0 0 a2 2 3 0 0 0 a3 0 1 0 0 0 vj 1 2 3 0 因为所有非基变量检验数都不小于0 但33=0，所以本题有无穷多最优解。再以x33为进基变

7、量比照上述方法进行方案调整，可得到另一个最优方案，如下：2805240*x，这个方案实际上与调整方案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” ，其余与

8、前者相同） ；（2）判断题目中的运输问题是否为标准运输问题（判别方法见第三版89 页（第 4 版 104页） “前面讲的表上作业法”那一段文字，标准化一定是产销平衡，不平衡就是非标准运输问题） 。如果不是，请转化为标准问题，要掌握“（ 1）中”所述两种非标准运输问题进行标准化的方法（见第三版90 页（第 4 版 105 页）从“若当产大于销时”到“同样可以转化为一个产销平衡的运输问题。”为止的叙述。 ） 。（3）熟练掌握用表上作业法求标准运输问题最优解的方法：用最小元素法确定初始方案；用位势法或者闭回路法求变量检验数并能据此判别当前解是哪一种情形（唯一最优解还是多个最优解？） ；用闭回路求值法

9、调整初始方案。（4）下结论，会求最小总费用会判断是哪一个产地产量过剩或者哪一个销地销量未满足。（5）应该知道 ij=某个值的经济涵义。以下这两个知识点你在做考试题时会用上，当然不会出简单题， 而是融入具体做法来考。（6）在用最小元素法确定初始方案的过程中，如果某元素对应的行产量和列销量相等，该如何处理？答：如果每一步划线之初同时有多个最小运价元素，请从行、 列标号最小的元素开始进行分配（如样题首先选择了第1 行第 4 列的 0 元素进行分配） ；如果未进行到最后一步但需要补充 0 元素作为基变量，请加在与该剩余最小元素（如运价为“1”的元素）所画十字线上（样题中即是划去了第1 列和第3 行的十

10、字线）运价最小（样题中可以添0 的位置有5个，即 x11、x21、x32、x33、x34，但 x34对应的运价c34=0 是这五个位置中最小的，所以选择在x34位置添加0 将其作为基变量）且未分配运量（如样题中x34在添 0 之前并未分配运量）的位置。（7）在用闭回路求值的过程中，如果最小值对应多个基变量，又该如何处理？答：如果进基变量所在闭回路上的顶点偶数序号格（如在本样题中即是x14和 x22所在4 2 5 0 3 5 3 0 1 3 3 0 位置） ，减去 值进行调整后得到多个0 元素（本样题中：x14-2=x22-2=0，所以得到两个0 元素） ，将对应运价最小的0 元素保留为基变量（

11、在本样题中，将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 请给出标准化以

12、后的效率矩阵并用匈牙利法求出最优分配方案；（2）对于问题b 建立线性整数规划模型，然后写出标准化以后的效率矩阵，但不必求解。表 4 解： （1）标准化以后的效率矩阵见表5：表 5 由于任务数5 多于人数4， 所以本题并非标准指派问题。增添一名假想的人戊。其完成各项工作的效率为甲、丙完成同一项工作效率的最小值。求解过程如下： -min0451772529314237-2504617123938262033-201918601319185083427284332-277011657002442362330-2311913072527284232-250231771601191202022172 -

13、min 0 0 -1 0 -5 045177191850870016011912020min023175-21916306-2900-2-2221721801171000000170023175191630690或01801171000000170+2 +2结论：最优分配方案： 甲 a；乙 d；丙 b和 c；丁 e。最少的总时间为：25+20+28+30+27=130 小时。人任务a b c d e 甲乙丙丁25 39 34 24 29 38 27 42 31 26 28 36 42 20 43 23 37 33 32 30 任务人a b c d e 甲25 29 31 42 37 乙39 3

14、8 26 20 35 丙34 27 28 43 32 丁24 42 36 23 30 戊25 27 28 42 32 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+或ijijijiiiiijjjjjjjjijminzcxxxxxxxxxxxxxxs txxxx由于任务数5 多于人数 4， 所以本问题不是标准指派问题。增添一名假想的人，

15、 设为戊。其完成各项工作的效率分别为m、m、0、0、0。 （注解：完工效率m(一个很大的正数)说明任务 a、b 不能交给虚拟人戊来做，甲肯定不能做任务b、d 和 e，乙不能做任务e） 。效率矩阵如表 6 所示：表 6 2、知识点：（1）人多任务少、人少任务多两种非标准指派问题的建模；（2）上述两种非标准指派问题的标准化方法；（3）会用0-1 变量表达式写出某人不能完成某些任务、或者某人必须完成某项任务、或者某任务可完成也可不完成的约束条件；在效率矩阵中，会应用大m 处理这些情况。（4）熟练掌握用匈牙利法求解指派问题最优解法方法和步骤；并且可以求出最优分配方案和最小总时间（或总费用）。注解：上述

16、知识复习， 请看第三版126130 页有关内容或者第4 版 146151 页有关内容，其中的定理证明可不看，可比照例题以及本样题掌握解题方法和步骤。三、动态规划之“一维资源连续分配问题”的建模与求解1、样题（注解：考试时题目计算量比样题要小，可能只有三个阶段）某厂有 100 台设备，可用于加工甲，乙两种产品。据以往经验， 这些设备加工甲产品每季末损坏 1/3 ，而加工乙产品每季末损坏1/10，损坏的设备当年不能复修。每台机器一季全加工甲或乙产品，其创利为10 或 7 百元。问如何安排各季加工任务，能使全年获利最大？请建立该问题的动态规划模型并用逆序解法求解，画出状态转移图得出结论。解： （1）

17、将问题按季度数分为4 个阶段， k=1,2,3,4。设状态变量 sk ：表示第k 季度初拥有的完好设备的台数。s1=100。设决策变量uk：表示第 k 季度初投入甲产品生产的设备台数，则投入乙产品生产的设备台数 vk =sk -uk。显然 uk dk(sk) =uk|0 uksk 。人任务a b c d e 甲乙丙丁戊25 39 34 24 m m 38 27 42 m 31 26 28 36 0 m 20 43 23 0 m m 32 30 0 状态转移方程：sk +1=auk+bvk =2/3uk+9/10(sk -uk) 。指标函数：阶段指标函数dk(sk,uk) 表示第k 期从 sk台

18、设备中抽出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) 444444444554440 us0 usf (s )max10u7(su ) f (s )max(3u7s)10su4*=s4时 f4(s4)=10s4。第 3 阶段， k=3 s4=2/3u3+9/10(s3 u3) 33333333333334433340 u

19、s0 us3333333330 us0 usf (s )max 10u7(su )f (s )= max 10u7(su )10s 29250max10u7(su )10u(su )max (u16s )=s31033u3*=s3时 f3(s3)=50/3 s3。第 2 阶段， k=2 s3= 2/3u2+9/10(s2 u2) 22222222222223322230us0us2222222220us0us50f (s )max 10u7(su )f (s )max 10u7(su )s 350298max10u7(su )u(su )max (22su )22s33109u2*=0时 f2

20、(s2)=22s2。第 1 阶段， k=1 s2= 2/3u1+9/10(s1 u1) 11111111111112211120 us0 us111111110 us0 usf (s )max10u7(su )f (s )max10u7(su )22s 2913432max 10u7(su )22u(su )max (su ) 310515u1*=0时 f1(s1)=134/5 100=2680 百元，这就是四期的最大总利润和。状态转移图如图1 所示：图 1 一维资源连续分配问题的状态转移图由状态转移图得出结论：全年最大获利即f1(s1)=2680 百元。 最优分配方案如下：四个季度投入甲产品

21、生产的设备数量分别为0、0、 81、54 台。2、知识点：kkkkkkkkk1k1ud(s)55fsmaxds ,ufs,k4 3, 2,1fs0 ，s4*=54 s3*=81 s1*=100 k=2 s3=2/3u2+ 9/10(s2-u2)k=3 s4=2/3u3+ 9/10(s3-u3)k=1 s2=2/3u1+ 9/10(100-u1)u1*(100)=0 u2*(90)=0 u3*(81)=81 d1*(100,0)=700 d2*(90,0)=630 d3*(81,81)=810 s2*=90 s5*=36 k=4 s5=2/3u4+ 9/10(s4-u4)u4*(54)=54 d

22、3*(54,54)=504 （1） “一维资源连续分配”问题的动态规划建模。可见讲课课件、 本样题求解第一部分或者课本： 第三版 217 页 （或第四版253254 页） 从 “设阶段序数k” 一直到 “从第 5 年度开始”之前的叙述。（2）掌握用逆序解法求解动态规划模型的方法和步骤。可比照本样题求解第二部分、讲课课件或者课本：第三版217218 页（或第四版254255 页）从“当 k=5 时，有”下面进一步来讨论始端固定”之前的叙述。（3）掌握用状态转移图来顺向推到最优决策变量、状态变量、阶段指标函数的方法，请看样题求解第二部分的图，或者课本第三版203 页图 8-6（或第四版238 页图

23、 9-6） 。（4） 会求出全过程最优指标值，并且知道其确定的依据。请看本样题的结论部分就有说明。四、图论之“最小费用最大流”问题的求解1、样题：试用对偶法求图2 所示的最小费用最大流。图中数字 （cij,bij, fij）分别代表弧 （vi,vj）容量、单位流量费用（元）和当前可行流。解：用对偶法求解（费用路a、c、e 中标记“”的为最短路），如图 3(a)(e)所示：(6,2,4)(10,3,4)(10,4,6)(8,1,5)(1,5,1)(7,1,7)(2,8,0)v3 v2 vs vt v1 vt (v1,+)(vs,+)(vs,+)(vs,+)1-2 -1-42341-5-18v3 v2 v1 vs vt (a) w(f(0) (6,2,5)(10,3,5)(10,4,7)(8,1,5)(1,5,0)(7,1,7)(2,8,0)v3 v2 vs vt (b) f(1)=7+5=12 -4234-15-18v3 v2 v1 vs vt (c) w(f