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

1、文档编码 : CO5C7W2P1B2 HF7K1D6J8N10 ZP3I7A6Y1X4运筹学补考复习学问点归纳及样题 总体要求：1、2 小时,闭卷考试；2、只需带黑色签字笔、铅笔、橡皮,不要带书包、纸来；绘图部分可以用铅笔,其余 部分不得用铅笔、圆珠笔答题；3、五道题目, 每题 20 分,每题小问可能包含运算、解题步骤不规范、说明不清楚要扣分；简答、 填空、作图；比照样题答题,4、以下给出的全部是样题,而不是原题；需要你比照样题复习、把握课件中讲过的所有学问点；样题中不行能将全部考点都告知你；填空填写运算表达式而非公式；5、考试时间和地点：开学的第一周,地点等候通知；6、考试无须带运算器,但你

2、自己仍是需要有确定的笔算才能；7、遵守考试纪律,作弊严惩不贷；一、线性规划之“ 运输问题” 的建模与求解1、样题：已知某运输问题其供销关系及单位运价、各产地产量、各销地销量如表 1 所示,问如何调运物品,使得总运输费用（单位：百元 / 万件）最小？表 1 产销平稳表和单位运价表销地 Bj B1 B2 B3 产量（万件）产地 Ai A1 4 2 5 8 A2 3 5 3 7 A3 1 3 3 4 销量（万件）4 8 5 要求：（1）请建立该问题的线性规划模型；（2）假如有必要再化为标准问题；（3）用表上作业法求解：用最小元素法确定初始方案（假如每一步划线之初同时有多个最小运价元素, 请从行、 列

3、标号最小的元素开头进行支配；假如未进行到最终一步但需要补充；0 元素作为基变量, 请加在与该剩余最小元素所画十字线上运价最小且未支配运量的位置）用闭回路法或者位势法验证初始方案是否最优？假如非最优,请用闭回路法调整 （假如调整后得到多个0 元素,将对应运价最小的0 元素保留为基变量） ,直至求出最优方案；解：（1）设从产地Ai 调运到销地Bj 的物品为 xij 万件,可建立如下线性规划模型：miin z4x 112x 125 x 133 x 215x 223x 23x 313 x 323 x 33x 11x 12x 138x 21x 22x 237x 31x 32x 334s.t.x 11x

4、21x 31=4x 12x 22x 32=8x 13x 23x 33=5x ij0i, j1 2 3（ 2） 总产量 =8+7+4=19总销量 =4+8+5=17,所以这是产大于销的非标准运输问题；可增加虚拟销地即库存积压仓库B4,各个产地到它的单位运价都是0,它的虚拟销量即生产过剩量为 2 万件（ =19-17）；（3）第一步：用最小元素法确定初始方案,如下所示：4265028 60初始调运方案X046523523507 201433004 020 4 8 5 2 0 2 0 0 0其次步：求非基变量检验数,验证初始方案是否最优；法一 ：用位势法求检验数；求解见表 2 所示：表 2 产地销地

5、B1 B2 B3 B4 Ui A1 3 4 2 5 5 0 0 0 0 A2 -1 3 5 0 3 -3 0 3 0 A3 0 1 3 3 3 0 0 0 1 Vj 1 2 0 0 由于 min11, 13,21,24,33,34| ij0=24= -30,所以初始方案并非最优方案,需进一步调整, x24 为进基变量； 24表示假如产地A2 增运 1 万件物品给虚拟销地B4,将导致初始方案总运费削减3 百元；法二：用闭回路法求非基变量检验数6 24 2 5 02 53 5 3 0 11=4-0+0-1=3； 13=5-3+5-2=5； 21=3-5+2-0+0-1=-1；4 01 3 3 0

6、24=0-5+2-0=-3 32=3-2+0-0=1； 33=3-3+5-2+0-0=3 （注：图中画出了非基变量 x21 的闭回路）；下面“ 验证初始方案是否最优” 的分析同“ 法一”；第三步：求 值,调整初始方案,得到改进方案二 X1；过程如下：+ 6-280 min2,2=2,0 运量的 x14；X 1-25+=524040以 X24 作为进基变量,由其所在闭回路的偶数序号格调运量确定调整量依据“ 奇加偶减”的原就所示进行调整, 选择 x22 作为出基变量但保留调整后为用伏格尔法求出的初始方案就是调整方案X1；用位势法可求出方案二X1 的非基变量检验数,如表3 所示：表 3 销地产地 B

7、1 B2 B3 B4 Ui A1 4 2 5 0 0 3 0 2 0 A2 2 3 3 5 0 3 0 0 0 1 3 3 0 A3 0 0 1 0 0 Vj 1 2 3 0 由于全部非基变量检验数都不小于 0 但 33=0,所以此题有无穷多最优解；再以 x33为进基变量比照上述方法进行方案调整,可得到另一个最优方案,如下：8 0*X 2 5 2,这个方案实际上与调整方案 X1是相同的；4 0决策结论：产地 A1向销地 B2 调运物品 8 万件；产地 A2 向销地 B3 调运物品 5 万件；产地 A3 向销地 B1 调运物品 4 万件；产地 A2 存在过剩生产物品 2 万件,存放在积压仓库 B

8、4；最小总运费 =8 2+5 3+2 0+4 1=35（百元）；2、复习学问点：（1）产大于销、或者销大于产的运输问题建模（第三版89 页（第 4 版 104 页）“ 模型可写成” 始终到“ 由于总的产量” 之前的模型这是“ 产大于销” 的情形；假如是其次种情形,就模型约束条件中的符号变为 :“=ai”、“ bj” ,其余与前者相同） ；（2）判定题目中的运输问题是否为标准运输问题（判别方法见第三版 89 页（第 4 版 104页）“ 前面讲的表上作业法” 那一段文字,标准化确定是产销平稳,不平稳就是非标准运输问题）；假如不是,请转化为标准问题,要把握“（ 1）中” 所述两种非标准运输问题进行

9、标准化的方法（见第三版 90 页（第 4 版 105 页）从“ 如当产大于销时” 到“ 同样可以转化为 一个产销平稳的运输问题；” 为止的表达； ）；（3）娴熟把握用表上作业法求标准运输问题最优解的方法：用最小元素法确定初始方案；用位势法或者闭回路法求变量检验数并能据此判别当前解是哪一种情形（唯独最优解仍是多 个最优解？） ；用闭回路求 值法调整初始方案；（4）下结论,会求最小总费用会判定是哪一个产地产量过剩或者哪一个销地销量未中意；（5）应当知道 ij=某个值的经济涵义；以下这两个学问点你在做考试题时会用上,当然不会出简洁题, 而是融入具体做法来考；（6）在用最小元素法确定初始方案的过程中,

10、假如某元素对应的行产量和列销量相等,该 如何处理？答：假如每一步划线之初同时有多个最小运价元素,请从行、 列标号最小的元素开头进行支配（如样题第一选择了第 1 行第 4 列的 0 元素进行支配） ；假如未进行到最终一步但需要补充 0 元素作为基变量,请加在与该剩余最小元素（如运价为“1” 的元素）所画十字线上（样题中即是划去了第1 列和第 3 行的十字线）运价最小（样题中可以添0 的位置有5个,即 x11、x21、x32、x33、x34,但 x34 对应的运价c34=0 是这五个位置中最小的,所以选择在x34位置添加 0 将其作为基变量）且未支配运量（如样题中 x34 在添 0 之前并未支配运

11、量）的位置；（7）在用闭回路求 值的过程中,假如最小 值对应多个基变量,又该如何处理？答：假如进基变量所在闭回路上的顶点偶数序号格（如在本样题中即是 x14和 x22所在位置）,减去 值进行调整后得到多个 0 元素（本样题中：x14-2=x22-2=0,所以得到两个 0 元素）,将对应运价最小的 0 元素保留为基变量（在本样题中,将 x34=0 明确写出来而非变成非基变量即空格,由于 c34=0c22=5；也就是说： x34 仍保留为基变量,但 x22 为出基变量变为空格（实际上取值仍是 0,非基变量取值一律等于 0 但不写出来） ；）二、线性整数规划之“ 指派问题” 的建模与求解1、样题支配

12、甲、乙、丙、丁四个人去完成A、B、C、 D、E 五项任务；每个人完成各项任务的时间（单位：小时）如表 4 所示；假如： a.甲或丙之中有一人完成两项任务,乙和丁各完成一项； b.每人只能完成一项,其中A 和 B 必需完成, C、D、E 中可以有一项不完成,甲必需做任务 A 或 C,E不能交给乙来做；要求：（ 1）对于问题 a 请给出标准化以后的效率矩阵并用匈牙利法求出最优支配方案；（2）对于问题 b 建立线性整数规划模型,然后写出标准化以后的效率矩阵,但不必求解；表 4 人任务A B C D E 甲25 29 31 42 37 乙39 38 26 20 33 丙34 27 28 43 32 丁

13、24 42 36 23 30 解：（1）标准化以后的效率矩阵见表5：表 5 人任务A B C D E 由于任务数5 多于人数 4,所以此题并非标准指派问题；增加一名假想的人戊；其完成各项工作的甲25 29 31 42 37 效率为甲、丙完成同一项工作效率的最小值；乙39 38 26 20 35 求解过程如下：丙34 27 28 43 32 丁24 42 36 23 30 戊25 27 28 42 32 -min2529314237-250461712045177m=n=35 19185083938262033-20191860133427284332-27701165试指派7001602442

14、362330-23119130711912022527284232-25023177022172不成功 -min 0 0 -1 0 -5 0 4 5 17 7-2 0 2 3 17 5 0 2 3 17 519 18 5 0 8-2 19 16 3 0 6 19 16 3 0 6m=n= 5 指派7 0 0 16 0 9 0 0 18 0 或 9 0 0 18 0 终止1 19 12 0 2-2 1 17 10 0 0 1 17 10 0 00min 2 2 17 2-2 0 0 0 17 0 0 0 0 17 0+2 +2结论：最优支配方案： 甲 A；乙 D；丙 B 和 C；丁 E；最少的总

15、时间为：25+20+28+30+27=130 小时；1,表示指派第 人做第 项任务（2）设 ix j i=1,2,3,4;j=1,2,.,5 ；该问题的 0-1 整数规划模0,否就4 5min z c ij x iji 1 j 1x i 1 + x i 2 + x i 3 + x i 4 + x i 5 1i 1, 2, 3, 4型如下：x 1 j + x 2 j + x 3 j + x 4 j 1j 1, 2x 1 j + x 2 j + x 3 j + x 4 j1j 3, 4, 5s t . .x 11 + x 13 1x 25 =0 x ij 0 或 1由于任务数 5 多于人数 4,所

16、以本问题不是标准指派问题；增加一名假想的人, 设为戊；其完成各项工作的效率分别为 M、M 、0、0、0；（注解：完工效率 M一个很大的正数 说明任务 A、B 不能交给虚拟人戊来做,甲确定不能做任务 B、D 和 E,乙不能做任务 E）；效率矩阵如表 6 所示：表 6 人任务A B C D E 甲25 M 31 M M 乙39 38 26 20 M 丙34 27 28 43 32 丁24 42 36 23 30 戊M M 0 0 0 2、学问点：（1）人多任务少、人少任务多两种非标准指派问题的建模；（2）上述两种非标准指派问题的标准化方法；（3）会用 0-1 变量表达式写出某人不能完成某些任务、或

17、者某人必需完成某项任务、或者某任务可完成也可不完成的约束条件；在效率矩阵中,会应用大M 处理这些情形；（4）娴熟把握用匈牙利法求解指派问题最优解法方法和步骤；并且可以求出最优支配方案和最小总时间（或总费用）；126130 页有关内容或者第4 版 146151 页有关内容,注解：上述学问复习, 请看第三版其中的定理证明可不看,可比照样题以及本样题把握解题方法和步骤；三、动态规划之“ 一维资源连续支配问题” 的建模与求解1、样题（注解：考试时题目运算量比样题要小,可能只有三个阶段）某厂有 100 台设备,可用于加工甲,乙两种产品；据以往体会, 这些设备加工甲产品每季末损坏 1/3 ,而加工乙产品每

18、季末损坏 1/10 ,损坏的设备当年不能复修；每台机器一季全加工甲或乙产品,其创利为 10 或 7 百元；问如何支配各季加工任务,能使全年获利最大？请建立该问题的动态规划模型并用逆序解法求解,画出状态转移图得出结论；解：（1）将问题按季度数分为 4 个阶段, k=1,2,3,4；设状态变量 s k ：表示第 k 季度初拥有的完好设备的台数；s1=100；设决策变量 uk：表示第 k 季度初投入甲产品生产的设备台数,就投入乙产品生产的设备台数 vk =sk -uk；明显 uk Dksk =uk|0 uksk ；状态转移方程：sk +1=auk+bv k =2/3u k+9/10s k -u k

19、；指标函数：阶段指标函数 dkS k,u k 表示第 k 期从 Sk台设备中抽出 uk台投入甲产品生产、sk -u k台投入乙产品生产时得到的利润；dkS k,u k 10uk+7s k -u k ；最优指标函数 f ks k 表示 sk 台设备从第 k 至第 4 期支配时所得到的最大利润总和 . 逆序解法的基本方程如下：fks kumaxk D k skdks ,ukfk1s k1,k4 3, 2,1f5s 50 （2）用逆序解法求解第 4 阶段, k=4 s5= 2/3 u4+9/10 s4 u4 f s 0 u max10u4 s 4 4 7s 4 u f s 0 u max3u4 s

20、4 4 7s 10s 4u4 * =s4时 f 4s 4=10s 4；第 3 阶段, k=3 s4=2/3u 3+9/10s 3 u3 f s 0 u max10u3 s 3 3 7s 3 u f s = max10u 0 u 3 s 3 3 7s 3 u 10s 2 9 2 500 u max3 s 3 10u 3 7s 3 u 103 u 310 s 3 u 0 u max 3 s 3 3 u 3 16s =3 s 3u3 * =s3时 f 3s 3=50/3 s3；第 2 阶段, k=2 s3= 2/3u 2+9/10s 2 u2 f s max 10u 2 7s 2 u f s max

21、 10u 2 7s 2 u 50 s 0 u 2 s 2 0 u 2 s 2 30 maxu 2 s 2 10u 2 7s 2 u 503 23 u 210 9 s 2 u 0 max 22su 2 s 22 89 u 22s 2u2 * =0 时 f 2s 2=22 s2；第 1 阶段, k=1 s2= 2/3u 1+9/10s 1 u 1 f s 0 u max10u1 s 1 1 7s 1 u f s 0 u max10u1 s 1 1 7s 1 u 22s 2 9 134 320 u max 10u1 s 1 1 7s 1 u 223 u 110 s 1 u 0 u max 1 s 1

22、 5 s 115 u u1 * =0 时 f 1s 1=134/5 100=2680 百元,这就是四期的最大总利润和；状态转移图如图 1 所示：U1 *100=0 U2 *90=0 U3 *81=81 U4 *54=54 S1 *=100 k=1 S2 *=90 k=2 S3 *=81 k=3 S4 *=54 k=4 S5 *=36 s2=2/3u 1+ s3=2/3u 2+ s4=2/3u 3+ s5=2/3u 4+ 9/10100-u 1 9/10s 2-u 2 9/10s 3-u 3 9/10s 4-u4d1 *100,0=700 d2 *90,0=630 d3 *81,81=810 d

23、3 *54,54=504 图 1 一维资源连续支配问题的状态转移图由状态转移图得出结论：全年最大获利即 f 1s 1=2680 百元； 最优支配方案如下：四个季度投入甲产品生产的设备数量分别为 0、0、 81、54 台；2、学问点：（1）“ 一维资源连续支配” 问题的动态规划建模；可见讲课课件、 本样题求解第一部分或者课本：第三版 217 页（或第四版253254 页）从“ 设阶段序数k” 始终到“ 从第 5 年度开头 ”之前的表达；（2）把握用逆序解法求解动态规划模型的方法和步骤；可比照本样题求解其次部分、讲课课件或者课本：第三版217218 页（或第四版254255 页）从“ 当 k=5

24、时,有” 下面进一步来争辩始端固定 ” 之前的表达；（3）把握用状态转移图来顺向推到最优决策变量、状态变量、阶段指标函数的方法,请看样题求解其次部分的图,或者课本第三版 203 页图 8-6（或第四版 238 页图 9-6）；（4）会求出全过程最优指标值,并且知道其确定的依据；请看本样题的结论部分就有说明；四、图论之“ 最小费用最大流” 问题的求解1、样题：试用对偶法求图2 所示的最小费用最大流；图中数字 （cij,bij, fij）分别代表弧 （vi,vj）容量、单位流量费用（元）和当前可行流；v1 10,4,6 7,1,7vt vs 1,5,1 2,8,0 图 26,2,48,1,5 10,3,4v 2 v3 解：用对偶法求解（费用路 a、c、e 中标记“ ” 的为最短路）,如图 3ae所示：v1 v1 -44-1 10,4,7 7,1,7vt v t vs 1-5 82-2 vs 1,5,0 2,8,06,2,5-1 3 8,1,5