运筹学期末考试题.pdf

运筹学考试复习题运筹学考试复习题 一一、线性规划问题 消防车调度问题。 消防站到三个火警地点所需要的时间 时间（分钟） 火警地点 1 火警地点 2 火警地点 3 消防站 1 6 7 9 消防站 2 5 8 11 消防站 3 6 9 10 如果三处火警地点的损失分别为：4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？ 解：把 7 辆车看成 7 个需求点。设 xij表示消防站 i 是否向第 j 个需求点派车，1 表示派车，0 表示不 派车。 经计算可得损失矩阵 损失矩阵 Cij 火警地点 1 火警地点 2 火警地点 3 J=1 J=2 J=3 J=4 J=5 J=6 J=7 消防站 i=1 36 24 49 21 81 72 45 消防站 i=2 30 20 56 24 99 88 55 消防站 i=3 36 24 63 27 90 80 50 是总损失最小的决策目标为：min z= 7 1 3 1 *cij ji xijj 约束条件：(1)消防站拥有消防车数量的限制：X11+X12+X13+X14+X15+X16+X17=3; X21+X22+X23+X24+X25+X26+X27=2; X31+X32+X33+X34+X35+X36+X37=2 (2)各个需求点对消防车的数量限制， 即为每个需求点只需要一辆消防车： 3 1i xij=1， j=1,2,3,4,5,6,7 (3)X14 X13; X24 X13+X23; X22 X21; X16 X15; X17 16; X36 X15+X35; 2X37 X15+X16+X35+X36 第二问：如果三处火警地点的损失分别为：4t11+6t12，3t21+7t22，5t31+8t32+9t33， 则只需要修改损失矩阵： 损失矩阵 Cij 火警地点 1 火警地点 2 火警地点 3 J=1 J=2 J=3 J=4 J=5 J=6 J=7 消防站 i=1 24 36 21 49 45 72 81 消防站 i=2 20 30 24 56 55 88 99 消防站 i=3 24 36 27 63 50 80 90 二二、参数规划 1、某线性规划问题如下： max z()=(4+)+(8-)+(7+2) s.t. 解：首先令=0，将模型转化为标准型后，应用单纯形法求解得到最优单纯行表，如表 1 所示，其中， 为松弛变量。 表 1 =0 时的最优单纯形表 C C 4 8 7 0 0 b 7 8 20 20 0 1 0 1 1 0 2 -1 -1 1 Z=300 -4 0 0 -6 -1 将含有参数的系数代入到上表中的第一行，得表 2。 表 2 代入后的单纯形表 C C 4+ 8- 7+2 0 0 b 7+2 8- 20 20 0 1 0 1 1 0 2 -1 -1 1 Z=300+20 -4+2 0 0 -6-5 -1+3 随着的增加，也逐渐变大，当1/3 时，的检验数最先为正，即=-1+30，最优解也 会发生改变，所以=1/3 为一个临界点。当时，最优解为=20，=20，目标值为 300+20。当1/3 时，由于0，所以选择入基，出基，继续计算，得到表 3。 表 3 最优单纯形表 C C 4+ 8- 7+2 0 0 b 7+2 0 40 20 1 1 1 1 1 0 1 -1 0 1 Z=280+80 -3- 1-3 0 -7-2 0 所有检验数都小于等于零，所以最优解为=40，=20，目标值为 z()=280+80 综上，目标值为的分段函数： z()= 2、b 中含有参数的线性规则 某线性规划问题如下： max z()=2+ s.t. 其中为参数。试分析当0 时，最优解的变化情况。 解：首先令=0，计算线性规划问题，得到最优单纯形表如表 1 所示，其中为松弛变量。 表 1 =0 时的最优单纯形表 C C 2 1 0 0 0 b 0 1 2 1.6 3.6 4.8 0 0 1 0 1 0 1 0 0 -0.2 0.3 -0.1 -0.2 -0.2 0.4 Z=13.2 0 0 0 -0.1 -0.6 由上表可知，最优基矩阵为 = 令 b = 与求 b 的灵敏度范围相同，通过计算b，得到 = b = * = 将代入上表，得表 2。 表 2 代入后的单纯形表 C C 2 1 0 0 0 b 0 1 2 1.6+2 3.6-0.5 4.8+0.5 0 0 1 0 1 0 1 0 0 -0.2 0.3 -0.1 -0.2 -0.2 0.4 Z=13.2+0.5 0 0 0 -0.1 -0.6 令的取值增加，当=7.2 时，为零，即 3.6-0.5=0。所以当时，最优解为 =1.6+2，=3.6-0.5，=4.8+0.5，目标值为 13.2+0.5。 当时，2n 时，算法需要 (n2n)计算时间。 五五、 某铁路部门拟铺设铁路线 9 个城镇连接起来， 修建各城镇间铁路的费用如图所示， 顶点 v1,v2v9 表示九个城镇；每条边表示铁路，边上的权值代表修建该铁路需要花费的费用。问铁路部门应修建哪 几条铁路才能保证连接各城镇的前提下，总费用最低？ 解：该问题可转化为求最小生成树问题，用 Kruskal 算法求解。 将VG 的n 顶点看成n 个孤立的连通分支，将所有的边按权从小到大排序，然后从第一条边开始，依 边权递增的顺序查看每一条边，并按下述方法连接2 个不同的连通分支，当查看到第k 条边（v，w） 时，如果端点V 和W 分别是当前2 个不同的连通分支T1 和T2 中的顶点时，就用边（v，w）将T1 和 T2 连接成一个连通分支，然后继续查看第K+1 条边；如果端点V 和W 在当前的同一个连通分支中， 就直接查看第k+1 条边，这个过程一直进行到只剩下一个连通分支时为止。 求的所示最小生成树 T，w(T)=2+3+1+2+1+2+2+4=17. 六六、下表表示一个单位时间任务调度问题，要求任务 ai 在 di 前完成，如果任务 ai 没在时间 di 之前 结束则导致罚款 wi，请设计算法找出一个调度，使之最小化总的惩罚（15 分） ai 1 2 3 4 5 6 7 3 s 33333322 ( ,)( ,)( )f s xd s xf s * 3 x 33 ( )f s 3 0x 3 1x 14 5 5 0，1 5 di 4 2 4 3 1 4 6 wi 70 60 50 40 30 20 10 解：运用贪婪算法思想设计算法如下： Step1：按误工惩罚的降序对任务进行排序。 Step2：选取惩罚值最大的任务 a1 将其排在第 di=4 位。 a1 Step3：取出下一个任务 a2 将其置于第 di=2 位。 a2 a1 Step4：取出下一个任务 a3，因其截至时间为 4，但第 4 位已经安排了 a1 故将其安排在第 di=3 位。 a2 a3 a1 Step5：取出下一个任务 a4，因其截至时间为 3，只能将其安排在第一位 a4 a2 a3 a1 Step6：取出下一个任务 a5，因其截至时间为 1，但第 1 位已经安排任务 a4，只能将其安排在第 di=7 位，此任务误工。 a4 a2 a3 a1 a5 Step7：取出下一个任务 a6，因其截至时间为 4，但第 4 位已经安排任务 a1，只能将其安排在第 di=6 位，此任务误工。 a4 a2 a3 a1 a6 a5 Step8：取出下一个任务 a7，因其截至时间为 6，将其安排在第 di=5 位。 a4 a2 a3 a1 a7 a6 a5 Step9：算法结束，最优调度问题为 4,2,3,1,7,6,5。总误工惩罚为 50 七、具有时间约束的奇异现象七、具有时间约束的奇异现象 在上述经典的统筹网络图中加入下列时间约束： 1. “A 工序结束后至少 10 天，B 工序才能结束”结束-结束型最小时间约束； 2. “B 工序开始后至少 8 天，C 工序才能开始”开始-开始型最小时间约束。 先转换最小时间约束类型： 1.“A 工序结束后至少 10 天，B 工序才能结束”转换为“A 工序结束后至少 10 - TB 天，B 工序才能 开始” 。 2.“B 工序开始后至少 8 天，C 工序才能开始”转换为“B 工序结束后至少 8 - TB 天，C 工序才能开 始” 。 计算出时间参数，得到关键路线为： 当 TB 增大t 时，10- TB 和 8- TB 都分别减小 ，整条路线增加一个 t ，减少 2t ，因此，总 工期会减少 2 t - t = t 。所以， TB 增大，关键路线的长减小，总工期不但不延长，反而减 小。反之， TB 减少，10- TB 和 8- TB 都分别增大t ，总工期不但不减少，反而会延长。 八八、现有两个人赌博(A 和 B)每人 2 美元，每次赌注为 1 美元直到有人输完，已知 A 赢的几率为 1/3， B 赢得几率为 2/3，A 每次赌博前的美元数（1、2、3 或 4）提供马尔科夫链的状态转移方程。 解：此问题中两个游戏者都有 5 个状态，即 0,1,2,3,4 分别表示每 4 个人手中的钱还剩多少，已知 A 赢的概率是 13，B 赢的概率是 23，则可得如下一步转移矩阵 p 状态 0 1 2 3 4 0 1 0 0 0 0 1 2/3 0 1/3 0 0 P= 2 0 2/3 0 1/3 0 3 0 0 2/3 0 1/3 4 0 0 0 0 1 从状态 2 开始，吸收的概率状态 0（A 输光所有的钱）可以取得： 综上所述,可将配车计划的优化描述为如下的线性整数规划模型,记为(I): min Z= s.t. 上述模型的最优解即的取值便给出一个最优的配车方案。 调车场集结的待编现车记作，其余到达列车按到达的先后顺序分别记作，m为到达 列车的列数。本阶段出发列车按时间先后分别记作 ， ，n为出发列车的列数。 为到达列 车i的车流量（i=0,1,n）； 为出发列车j 的车流量( j= 1, 2, n). 设表示到达列车i的到达时刻，表示出发列车j 的出发时刻；表示到达列车i最早开始解体的 时刻，表示到达列车i最早解体结束的时刻，表示到达列车i解体的时间；表示出发列车j 最迟开始编组的时刻，表示出发列车j最迟编组结束的时刻，表示出发列车j的编组时间；表 示到达列车i到达技术作业的时间。表示出发列车j出发技术作业的时间。 为本阶段开始时刻； 为到达列车i编入出发列车j 的第k 号车流量( k=