南昌大学研究生数学建模竞赛教学案例（库）

Presentation on theme: "南昌大学研究生数学建模竞赛教学案例（库）"— Presentation transcript:

1 南昌大学研究生数学建模竞赛教学案例（库）
案例名称：多波次导弹发射中的规划问题 项目负责人：陈涛 所在学院：理学院

2 一、问题重述 二、模型假设与符号说明 三、问题一 四、问题二 五、问题三 六、问题四 七、问题五 八、总结分析 九、参考文献 目 录

3 一.问题重述 1.1问题背景 随着科学技术的不断发展，导弹武器作为高尖端武器被广泛地运用到现代战争中，导弹作战作为未来战场的主要 作战样式之一，是取得战争胜利的重要因素。为了提高导弹部队的生存能力和机动能力，常规导弹大都使用车载 发射装 置，平时在待机地域隐蔽待机，在接受发射任务后，各车载发射装置从待机地域 携带导弹沿道路机动到各 自指定发射点位实施发射。每台发射装置只能载弹一 枚，实施多波次发射时，完成了上一波次发射任务的车载发 射装置需要立即机动 到转载地域（用于将导弹吊装到发射装置的专门区域）装弹，完成装弹的发射装 置再机动至 下一波次指定的发射点位实施发射。连续两波次发射时，每个发射点 位使用不超过一次。

4 某部参与作战行动的车载发射装置共有 24 台，依据发射装置的不同大致分 为 A、B、 C 三类，其中 A、B、C 三类发射装置的数量分别为 6 台、6 台、12 台，执行任务前 平均部署在 2 个待机地域（D1，D2）。所属作战区域内有 6 个 转载地域（Z01~ Z06）、60 个发射点位（F01~ F60），每一发射点位只能容纳 1 台发射装置。各转载 地域最多容纳 2 台发射装置，但不能同时作业，单台转载作业需时 10 分钟。各转载 地域弹种类型和数量满足需求。相关道路情况如图 1 所示（道路节点 J01~J62），相 关要素的坐标数据如附件 1 所示。图 1 中主干道路（图中红线）是双车道，可以双车 通行；其他道路（图中蓝线）均是单车道，只能在各道路节点处会车。A、B、C 三类 发射装置在主干道路上的平均行驶速度分别是 70 公里/小时、60 公里/小时、50 公里 /小时，在其他道路上的平均行驶速度分别是 45 公里/小时、35 公里/小时、30 公里/ 小时。 部队接受发射任务后，需要为每台车载发射装置规划每个波次的发射点位及 机动路线，要求整体暴露时间（所有发射装置的暴露时间之和）最短。本问题中 的“暴露时间”是指各车载发射装置从待机地域出发时刻至第二波次发射时刻为 止的时间，其中发射装置位于转载地域内的时间不计入暴露时间内。暂不考虑发 射装置在发射点位必要的技术准备时间和发射后发射装置的撤收时间。

5 1.2待解决的问题 围绕多波次导弹发射中的规划问题，本文将按顺序解决如下问题： 问题一：该部接受到实施两个波次的齐射任务（齐射是指同一波次的导弹同一时刻发射），每个波次各发射 24 导弹。给出具体发射点位分配及机动路线方案，使得完成两个波次发射任务的整体暴露时间最短。 问题二：转载地域的合理布设是问题的“瓶颈”之一。除已布设的 6 个转载 地域外，可选择在道路节点 J25、 J34、J36、J42、J49 附近临时增设 2 个转载地域（坐标就取相应节点的坐标）。应该如何布设临时转载地域， 使得完成两个波次发射任务的整体暴露时间最短。 问题三：新增 3 台 C 类发射装置用于第二波次发射。这 3 台发射装置可事先选择节点 J04、J06、J08、J13、 J14、J15 附近隐蔽待机（坐标就取相应节点的坐标），即这 3 台发射装置装弹后从待机地域机动到隐蔽待机点 的时间不计入暴露时间内。每一隐蔽待机点至多容纳 2 台发射装置。待第一波次导弹发射后，这3 台发射装置机 动至发射点位参与第二波次的齐射，同时被替代的 3 台 C 类发射装置完成第一波次齐射后择机返回待机地（返 回时间不计入暴露时间）。转载 地域仍为事先布设的 6 个的前提下，应该如何选择隐蔽待机点，使得完成两个 波 次发射任务的整体暴露时间最短。 问题四：道路节点受到攻击破坏会延迟甚至阻碍发射装置按时到达指定发射 点位。请结合图 1 路网特点，考虑 攻防双方的对抗博弈，建立合理的评价指标，量化分析该路网最可能受到敌方攻击破坏的 3 个道路节点。 问题五：在机动方案的拟制中，既要考虑整体暴露时间尽可能短，也要规避敌方的侦察和打击，采用适当分散机 动的策略，同时还要缩短单台发射装置的最长暴露时间。综合考虑这些因素，重新讨论问题（1）。

6 1.3国内外现状 国内外已有不少学者对多波次导弹火力打击任务的分配进行了不少研究。季 青梅等利用 Dijkstra 算法对较小规模作战区域的多波次导弹火力打击任务进行 了分 析；王梓行等则依据聚类分析和 Floyd 算法对战时导弹火力打击任务分 配与运输决策 模型进行了计算；吴瑞峰、白行等分别通过线性加权法和约束 非线性规划、遗传算 法等方法对于不受道路限制、转载点限制的多波次火力 打击也给出了较有深度的计算。 在作战区域路网节点重要性评价方面，已有 许多学者提出了如度数、介数、接近中心性、 拉普拉斯算子中心性等指标， 并取得了较好地效果。一些国外学者也对多波次 火力打击的相关问题进行了 研究，得到了较为丰富的结果。

7 二.模型假设与符号说明 2.1模型假设 （1）主干道路可以双向通行并超车，其他道路只能单向行驶，但单车道允许 多辆车 同向而行，不能超车，快车可以减速，各道路节点处可以两车交会，允许 车辆在道路 节点停留等候。 （2）忽略车载发射装置同时出发时的碰撞问题。 （3）为了隐蔽发射基地，在实施多波次发射时，不能连续 2 个波次使用同一导弹发 射基地，齐射要求同一拨导弹同一时间发射 （4）每辆导弹发射车只能载弹 1 枚，实施多波次发射时，需前往转载地域重新装载导 弹，发射车战前均已载弹。 （5）发射装置平均部署在两个待机区域，即 A、B、C 三种类型各 3 台，3 台，6 台。 （6）忽略发射装置同时进出转载区域时的碰撞问题，在没有其它发射装置需要重新装 弹时，当前发射装置可以在转载区域停留减少暴露时间

8 2.2符号说明

9 三 问题一 3.1 问题分析 部队接受到实施两个波次的齐射任务，每个波次各发射 24 枚导弹，问题一 需要给出 具体发射点位分配及机动路线方案，使得完成两个波次发射任务的整体 暴露时间最短。 整体暴露时间可以分成两个部分，即发射装置在道路上的行驶时间和在道路 节点等待 的时间。考虑到多波次导弹路线规划过程中复杂的道路节点选择、发射 点位选择和转 载地域选择等问题，我们基于聚类的思想根据 Floyd 最短距离算法 对每个发射装置合 理分配第一次发射点位、转载地域和第二次发射点位，即首先 确定每个发射装置的路 径，再根据车速、单车道、转载地域等限制条件改变各发 射装置在路径中节点处的到 达\离开时刻，以避免各发射装置有可能在道路上发 生超车或相遇的情形。

10 3.2 模型建立 3.2.1 网络拓扑分析 根据题目所给的网路拓扑可以发现，转载地域的分配很不均匀，而且 发射点位对转载地域关于距离聚类的结果也是不均匀的，如果分波次 进行多次优化得到的结果不会是最优的，所以从发射装置出发开始之 后必须考虑到后面的发射波次。考虑到发射装置在单行道和双行道上 速度不同，为了方便聚类分析，在聚类过程中我们将双行道的长度按 照两种路上的速度比进行缩短，并且计算了待机区域到各个转载区域 最短路径的距离，从表一知道大部分转载基地是靠近 D1 的。如图 1 我们根据发射基地到转载区域的最短路径距离对发射基地进行聚类， 图中每一种颜色代表一个转载区域及其所关联的发射基地，很显然转 载区域 Z06 距离 D1 和 D2 都很远，但是其关联的发射基地却是最 多的。在下面建立模型时，我们将根据聚类结果对模型进行一定的约 束。 距离 Z01 Z02 Z03 Z04 Z05 Z06 D1 140.5 71.6 37.2 85.3 82.9 146.4 D2 62.9 117.9 152.4 125.2 191.3 148.1

11 3.2.2 构建目标函数 针对两波次导弹发射，所有发射装置的整体暴露时间可以分为发射装置行驶 时间 和节点处等待时间。因此，需要对整个系统进行综合性分析[6]，将其视为多 目标 优化问题，目标函数为 约束条件为：

12 式（1）为目标函数，其中：T表示整体暴露时间之和（所有发射装置的暴露时 间之和），令 表示第 k 辆导弹装载车路径中在两个波次发 射过程中经过节点的有序集和， 表示第k辆导弹装载车相邻节点的运输 时间 表示第k辆导弹装载车在节点 处停留时间，式（2-4）中 表示 第 i 波次选择导弹发射基地点的总集合， 表示第 k 辆车载发射装置第 i 波次 的导弹发射基地目标，每一波次导弹发射选择 24 个基地且连续两波导弹发射基 地不重复;式(5)中 表示在第i波次使用的属于 Z i 的发射基地数量| Z i | 表示属于第 i 个转载区域的发射装置总数量。式(6-7)对道路会车及追赶问题作 出约束，其中：任意单车道上正反向行驶时间交集为空集 ，以避免在单向道 上 出现无法错车的情况，且单车道上任意两辆车同向行驶时，不允许出现超车的情 况，其中，s表示单车道路径集合 表示第 k 辆车载发射装置从第i节点 出出发到下一节点的到达时间区间， 表示两辆车都从第 i 个 节点到底 i+1 个节点，其中一辆装载装置的时间区间在另一辆装在 装置的时间 区间内，即出现超车情况；式(8)中, 表示第 k 辆车载发射装置到达路径节 点 的时刻，式(9) 表示表示在第 i 个转载区域获得隐蔽状态的 车载发 射装置的数量。

13 因此，约束条件(2)、(3)、(4)对发射基地作出约束，保证两个波次发射不会使用相同的发射基地；约束条件(5)保证保证了在同一波次发射中发射基地不会过于集中；约束条件(6)、(7)保证在单车道没有相向行驶的，且不会出现超车情况；约束条件(8)用来计算每辆发射装置到达各节点的时间；约束条件(9)保证在同一时刻每一个转载区域隐蔽待机点最多只能容纳两辆发射装置。 在整个模型中，总共有三类发射装置，且根据其在不同道路中的形式速度应该分配快车走距离长的路线，慢车走距离短的路线，而且根据每条道路的长度可知车辆走大部分道路都需要超过十分钟的时间，所以在策略规划中我们尽量让发射装置在转载区域等待而不是去更远的转载区域。

14 3.3.1 基于聚类分析的的 Floyd 最短路径综合算法
3.3 模型求解 3.3.1 基于聚类分析的的 Floyd 最短路径综合算法 为了求解两波发射的最优策略，我们在目标函数中添加了聚类结果约束，接下来将根据模型 约束求解最优策略。距离计算采取 Floyd 算法该算法是一种利用动态规划思想寻找给定的 加权图中多源点之间最短路径算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩 阵。算法过程为： 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权 为无穷大 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v比已知的路径更短 。如果是更新它。 把图用邻接矩阵 G 表示出来，如果从 vi 到 vj 有路可达，则 ， 是该路的长度；否 则 定义一个矩阵D用来记录所插入点的信息, 表示从 到 需要经过的点， 初始化 把各个顶点插入图中，比较插点后的距离与原来的距离， 如果 的值变小，则 在 G中包含有两点之间最短道路的信息，而在D中则包含 了最短通路径的信息。Floyd 算法主要用来计算任意两点之间的最短距离，按照发射点位到 不同转载地域的路径长度以及发射点位到待机区域的路径长度进行聚类，首先为发射装置匹 配两个发射波次的行驶路径。再根据路网特点(单车道，双车道，转载地域容纳车辆的隐蔽 效果等)，按照节点调整准则调整每辆发射装置的节点到达时刻和离开时刻

15 3.3.2各阶段时刻调整方案 （1）待机区域出发时刻调整方案
第一次发炮前，在已经分配好每个发射装置前往第一次发炮的目标发射点位后， 先按照各自速度分别计算每个发射装置的所需时间，并对运载时间进行由大到小 进行排序，考虑到总体暴露时间并没有包含发射装置呆在待机地域的时间，因此 ，我们采取运载时间越长，该发射装置先跑的准则，记后跑的发射装置k从待机 地域出发的时间为 式(10)表示后出发的发射装置从待机地域出发时刻为所有发射装置中到达发射点 位所需最长时间与该发射装置不延误出发到达发射点位所需时间之差，其中 表示从第 k 辆发射装置从第 个节点到第 个节点的时间，根据式(10)计算出 每个发射装置的出发时刻，由于已经预先分配好各自的路径和发射点位，可以根 据每个发射装置的速度计算到达每个节点 的时刻 和从该节点离开前往下一 个节点 的时刻 其中， 表示相邻两个节点之间的距离， 表示第 k 辆车载装置的平均速度

16 （2）道路节点到达\离开时刻调整 此时注意到由于没有考虑单车道的问题，所以每个节点的到达时刻与出发时刻相同 。再引入单车道，单车道上的车载装置只能同向行驶，不能反向也不能超车，因此 我们设置如下节点停滞规则：第 k 辆车载装置从某一节点 离开时，判断下一条 路径 上是否有其他车载装置，若有已存在车载装置，将根据该车载装置的 行驶状态(方向、速度)对即将离开 的车载装置调整离开时刻： 1）若 ，即在节点 和 之间的单车道上发生超车（第k2 辆车载 装置超第 k1 辆车载装置)时，令 ，即保持第 k1 辆车的运动状态不变，将 第 k2 辆车载装置到达节点 的时刻调整为第 k1 辆车载装置到达节点 的时刻 。

17 2）若 ，即在节点 和 之间的单车道上发生车辆相向而行 ，这里假设 第 辆车载装置离开节点的时刻小于第k辆车装置离开 的时刻 即我们保持第 k1 辆车载装置的状态不变，将第 k2 辆车载装置离开 的时刻 改为第k1 辆车载装置到达 的时刻 ，同时将第k2 辆车载装置到达 的时刻 调整为该车在装置离开 的时刻加上从节点 到节点 的时间，该准则适用于 两次发炮过程中单车道节点之间行驶过程。在所有发射装置在发射点位，齐射完后 ，各个发射装置需要到合适的转载地域进行填弹，填完弹后再选取道路，到各自的 发射点位进行齐射任务。这里，我们基于聚类约束条件，每一辆发射装置，分别到 其所直属的转载区域内重新装弹，然后选择属于该装载区域的发射基地作为新的发 射基地即可。

18 3）转载地域到达\离开时刻调整 在保持道路节点等待准则不变的情况下，继续引 入转载地域的时刻调整方案准则，考虑到每个转载地域内可容纳发射装置数为 2 个，我们采取当转载地域中已经容纳 2 个发射装置， 且有第三个发射装置前往 该转载地域时，将第三个发射装置到达转载地域的时间作为第一个到达该转载地 域并填完弹的发射装置离开的时刻，当转载地域不再有发射装置前往进行填弹时 ，转载地域中的发射装置离开的时刻取决于其他已经前往发射点位的发射装置到 达发射点位的时刻，应使其尽量满足所有发射装置最终同时到达发射点位进行齐 射。该准则依据转载地域发射装置的总分配数来匹配，可以最大限度地放大发射 装置在转载地域中的隐蔽时间，减小每辆发射装置的暴露时间，具体准则如下： ①第一次发炮后转载区域到达、离开时刻分析(若转载地域 Z 安排 3 辆发 射装置进行装弹，为考虑中途节点处的等待时间

19 ②第二阶段关键点位到达、离开时刻分析(若转载地域 Z 安排 4 辆发射装置进行装 弹）

20 ③第二阶段关键点位到达、离开时刻分析(若转载地域 Z 安排 5 辆发射装 置进行装 弹） 其中， 表示 A 发射装置从发射点位 F 到转载地域 Z 的路径长度， 表示发射装 置离开转载地域 Z 的时刻。若转载地域安排数量大于 5 可依据该准则顺推实际在 进行安排发射装置进行二次发炮路线规划时需要统一两个准则，以达到在限制条件 下，总暴露时间最少的情况。

21 3.3.3解优化路径算法 将上述约束调整方法统一，按照聚类、分配路径、调整时刻顺序依次进行路径规划算 法步骤如下：
Step1: 对所有发射基地关于转载区域的路径长进行聚类，记录聚类结果； Step2: 根据 Floyd 算法计算所有发射中心到待机区域的最短路径距离，构建 距离矩阵； Step3: 从距离矩阵中选取最小距离所表示的发射基地，判断该基地关联的转载地域 Zi 中标记的发射基地数量是否小于其关联基地总数量的一半，如果是， 按顺序从 C、B、A 类车进行分配，标记该发射基地已分配；如果否，对该基地距离赋予最大值，进行下一步；Step4: 判断待机区域 Di 剩余发射装置数量，如果存在某一区域剩余数量大于0，则返回 Step3，否则进行下一步。 Step5: 发射基地分配完成后，以运输时间最长的时间点作为第一波次发射时间，其它发射装置出发时间为发射时间减去各自运输时间；Step6: 判断各路段在不同时刻是否存在车辆交会或超车问题，如果存在则对发射装置按照各阶段时刻调整准则对冲突节点的到达时刻和离开时刻进行调整； Step7: 以第一波次发射时间作为第二波次出发时间，各发射装置到其关联的转载区域重新装弹并确定新的发射基地，首先将各发射装置从发射点位到转载地域的路径上的节点按照节点时刻调整准则进行调整，再根据转载地域时刻调整准则进行转载地域的到达\离开时刻调整，最后再根据节点调整准则调整每辆车载装置在节点处的到达\离开时刻

22

23 3.4结果及分析 对于模型求解的结果，我们分波次将所用到的导弹发射基地显示在地图中。在第 一波导弹发射中（图 2），因为发射装置是从两个待机区域出发的，所有第一波 次用到的发射基地会相对集中在待机区域附近，而从结果来看，由于我们添加了 聚类约束，所以发射基地会尽量向全图扩散，虽然这一波次的整体暴露时间会增 加，在第一波次中的整体暴露时间为 分钟（56.7h），但降低了由于发 射基地的过度聚集对道路通畅和转载地域带来的压力，有利于第二波次的分配策 略，从表 2 中可以看出，考虑到第二波次需要发射装置先到转载区域重新装弹 然后再到发射基地，因此暴露时间相比第一波次已经较短了。在第二波次的分配 中，由于第一波次的聚类，会使得第二波次中重新装载导弹和分配发射基地的压 力降低，达到最优策略。在表 3 中给出了 24 台发射装置到达关键节点的时刻表 ，详细节点的时刻表可以在附件中看到。 综合两波次导弹发射情况，图中左上角处很多发射基地没有被使用，这是由于 整体地理位置分布不均匀造成的，而我们所做的聚类约束条件能有效的利用转载 地域的资源，使得在第一波次时发射装置能较合理的分配到发射基地，减少第二 波次中由于到转载区域运输距离较远而造成整体暴露时间过长，还可以避免由于 发射装置过于集中导致转载区域拥挤而增加暴露时间表

24 表 2. 问题一整体暴露时间 发射波次 整体暴露时间（min） 第一波次 3406.4 第二波次 5131.2 总和 8537.4 表 3. 两个波次导弹发射路径

25 四.问题二 4.1问题分析 问题二需要对除已布设的 6 个转载地域外，在道路节点 J25、J34、J36、J42、 J49 附近临时增设 2 个转载地域，使得完成两个波次发射任务的整体暴露时间最 短。根据问题一中的聚类结果可知，在道路网络结构中转载区域、发射基地相对 于待机区域分布很不均衡，这样在两个波次的导弹发射中容易造成资源的浪费和 发射装置的不合理分分配，所以需要根据问题一的策略，在发射基地集中区域增 设转载区域。从已有转载区域的分布来看，新增的两个转载区域应尽量设置在靠 近待机区域 D2 和发射装置集中的节点处，来缓解从 D2 出发的发射装置在路程 上的运输时间和在已有转载区域的等候时间，由于候选节点十分有限，可以采用 问题一的模型来进行遍历，在所有情况中寻找最优。

26 4.2问题求解 问题一的策略结果来看，由于转载区域不均匀的原因导致被使用的发射基 地相对 比较集中，这样导致整体暴露时间较长，由表 1 可知转载区域距离 D2 都 较远， 所以理想中在靠近 D2 的节点处增加转载区域将有利于减少整体暴露时间， 接下 来对本问题进行求解。本问题中待选的转载区域一共有 5 个节点，共有 10 中组 合，可根据问题一的模型对 10 种情况进行遍历，分别计算整体暴露时间得到表4 节点 整体暴露时间 J25,J34 8160.1 J25,J36 8118.5 J25,J42 8321.5 J25,J49 8291.2 J34,J36 8248.4 J34,J42 8310.8 J34,J49 8294.2 J36,J42 8445 J36,J49 8573.2 J42,J49 8595.8 从表 4 的结算结果可知当选择 J25 和 J36 两个节点作为新增转载区域时，整 体暴露时间能达到最小。选择最优临时转载区域，将两波导弹发射结果显示出来， 如下图所示 表 4. 增加转载区域后整体暴露时间

27

28 4.2.3结果分析 从表 4 的计算结果来看，最优的两个临时转载区域满足我们对问题的假设， 即新增 的转载区域靠近 D2 且处于发射基地聚集区域。另外，从结果来看，整体 暴露时间减 少的并不是很多，从网络结构来看，增设临时转载区域后 D2 都各转 载区域的距离依 然较远，且 D2 处于地图右上角区域，偏离发射基地，所以即使 增设临时转载区域， 整体暴露时间减少有限。 增设临时转载区域后，除了整体暴露时间较少，还有时间增多的情况，如选 择节点 J36 和 J49、J42 和 J49，其整体暴露时间比初始结果还多，分析网络结构 可以发现 J36、J42 和 J49 都是靠近 D1 的，而 D2 对整体暴露时间影响较大，所 以在靠近 D1 的节点增设临时转载区域并不能减少整体暴露时间，反而有可能由 于转载地点过 于集中导致时间增加。

29 五．问题三 5.1问题分析 根据问题一的策略结果，要在节点 J04、J06、J08、J13、J14、J15 附近隐蔽 待 机新增 3 台 C 类发射装置用于第二波次发射，每一隐蔽待机点至多容纳 2 台 发 射装置。待第一波次导弹发射后，这 3 台发射装置机动至发射点位参与第二波 次 的齐射，同时被替代的 3 台 C 类发射装置完成第一波次齐射后择机返回待机 地 域。要使得完成两个波次发射任务的整体暴露时间最短，则需要将问题一中单 车 暴露时间最长或者由于转载区域排队车辆较多造成整体暴露时间加长的 C 发 射装 置替换，以达到整体暴露时间最短。 对于本问题首先我们需要分析对整体暴露时间影响最大的 C 类发射装置， 然后根 据两个波次的导弹发射情况判断适合作为隐蔽待机点的道路节点，考虑到 新增 C 类发射装置参与第二波齐射，则需要对第二波次导弹发射的基地分配作 出合理的 调整。

30 5.2问题求解 用三台隐蔽的 C 类发射装置在第二波次替换参与第一波次发射的 C 类发 射装 置，首先要对问题一中所有 C 类发射装置的路线及单车暴露时间进行综合 分 析，确定三台对整体暴露时间影响最大的 C 类发射装置。 仔细分析问题一模型求解结果，造成整体暴露时间较长的原因是 Z01 区域 聚类 的发射基地之间相距距离较远，如图 6 所示，淡绿色圆点为聚类到 Z01 的 发 射基地。而且在第一波次发射时分配的是 C 类慢车，这就导致第二波次中到 达转载区域然后再到新的发射基地的时间变长，齐射时间延长，导致整体暴露 时 间变长，通过表 2 的导弹发射路径时刻表可知 C8、C9、C11 三辆车经过 转载区 域重新装弹再到达新的发射基地所需要的时间是最长的，所以这三辆 C 类发射 装置是应该被替换的 图 6. Z01 聚类区域分析

31 接下来讨论应该分配给新增三台发射装置的发射基地。从问题一中两个波次 发射的 结果来看图中右侧和双向车道之间的发射基地基本都被使用，只剩余左上 角的发射 基地，所以应在 J13、J14 和 J15 中选取两个隐蔽待机点，此外考虑到 C 类发射装 置速度较慢，所以需要对第二波次发射基地的分配进行调整，将较近的 发射基地分 配给新增发射装置。 根据重新调整后的发射基地分配策略，可得到如图 7 所示的第二波导弹发射 情况示 意图，其中绿色和红色节点为新增隐蔽节点和分配的发射基地，在 J15 分 配了两辆 C 类发射装置，J14 分配了一辆，在表 5 中列出了三辆新增装置的行驶 时刻表，并 且对 A01 和 A02 对应的发射基地作出调整以减少整体暴露时间。从 计算结果来看 ，替换三台 C 类发射装置明显较少了整体暴露时间，该策略适合 于对模型进行优化 装置编号 出发节点 出发时间 到达发射基地及时间 C13 J14 326.2 F07/452.4 C14 J15 373.1 F10/452.4 C15 387.1 F11/452.4 发射波次 整体暴露时间（min） 第一波次 3406.4 第二波次 4373 总和 7779.4 图 7. 新增发射装置后发射基地分配 表 6. 问题三整体暴露时间 表 5. 新增 C 类发射装置运行时刻表

32 5.3结果分析 对于本题中新增三辆 C 类隐蔽发射装置用于第二波发射，从整体暴露时间 的 结果来看，该方法比问题二中的增加临时转载地域的情况更好，所以整体暴 露 时间与行驶时间最长的发射装置有一定的关联，特别是在本问题中，待机 区域 D2 的位置偏离转载区域，并且在所有发射装置中，速度较慢的发射装置 所占比 重较大，这就容易造成多辆发射装置的单车暴露时间较长，从而导致 整体暴露时 间较长，而问题二中增加临时转载区域只能在一定程度上减少暴 露时间，但不能 解决 C 类发射装置到转载区域时间较长的问题。 对于本问题中的道路网络结构，添加转载区域效果有限，而一般来说，增设 转载区域要比隐蔽待机点成本更高，所以最理想的情形就是将 C 类发射装置 隐 蔽在转载区域或发射基地附近，这样利于 C 类发射装置快速到达发射基地 或进 行弹药装填，从而减少整体暴露时间。

33 六．问题四 6.1 问题分析 本问题需要根据路网特点，考虑攻防双方的对抗博弈，建立合理的评价指标， 量化分析该 路网最可能受到敌方攻击破坏的 3 个道路节点。在两波次导弹发射过 程中，有些道路节 点往往是多台发射装置必须要经过的的节点，同时这些道路节 点也和发射点位、转载地 域直接相连。对于我方而言，此类道路节点的破坏会延 迟甚至阻碍发射装置到达指定发 射点位，是策略制定中关键保护节点。但对于敌 方而言，此类道路节点是策略制定中关 键攻击节点。由于我方是根据网路的特点 来制定两波次导弹路径规划，同时发射装置在 大多数情况下是暴露在敌方的视野 下的，因此假设我方可以推测敌方所采取的“策略” 和采取每个策略敌方可以获 得的收益(“支付函数”)，同时敌方也知道我方所采取的“策 略”和“支付函数”。 此外敌我双方都想争得先机，因此，为公平起见，假设敌方双方 同时采取策略， 基于以上分析，采取基于完全信息静态博弈模型进行敌我对抗的任务决 策方法较为合适

34 6.2.1 基于完全信息博弈的敌我对抗 6.2 模型构建 因为敌我双方采取的策略是有限的，因此将其简化为二人有限策略型博弈模型，即
其中 ， 分别为我方和敌方策略集 代表我方策略中可能保护的的道路节点， 代表方策略中可能攻击的的道路 节点。 设 为我方的支付矩阵， 代表我方采取策略 而敌方采取策 略 时我方的收益，具体支付函数为 和 分别表示我方采取策略 时，能够获得的收益和付出的代价； 和 则 分别表示敌方在采取策略 时，能够获得的收益和付出的代价； 同理 敌方的支付矩阵 代表我方采取策略 而敌方采取 策略时我方的收益，具体支付函数为 设我方的混合策略集为 代表我方采取策略 的概率，敌方的混合策略 集为 ， 代表敌方采取策略 的概率。

35 另设 为m维行量， 为n维向量，则在混合策略 下我方期望的支付函数为， 敌方期望支付函数为 对于双矩阵对策，可如下描述其混合策略纳什均衡，对于 ,如果 , 有 则 为双矩阵博弈的混合策略纳什均衡。

36 6.2.2 熵权法确定支付函数(评价指标) 基于完全信息博弈的敌我对抗模型中需要事先确定我方在采取策略时，够获得的收益和 付出的代价，敌方在采取策略 时，能够获得的收益和付出的代价，假设敌我双方破坏任 意节点的代价相同保护任意节点付出的代价也相同，即为常数，也为常数。针对我放采 取策略时获得的收益，利用熵权法计算以下几个指标的最终得分： 1、节点影响的发射站数量； 2、节点与节点的连接数量； 从节点到转载地域的最短距离 4、节点交汇处经过的车辆数量。 而针对敌方在采取策 时，能够获得的收益 ，考虑到敌方并不知道我方转载地域的 位置，利用熵权法计算以下几个指标的最终得分：1、节点影响发射站的数量；2、节点 与节点的连接数量；3、节点交汇处经过的车辆数量。在信息论中，熵是对不确定性地 一种度量。信息量越大，不确定性就越小；信息量越小，不确定性就越大，熵也越大， 在综合评价中所起到的作用也越小。

37 熵权法步骤为： 1.数据标准化 将各指标的数据标准化处理，假定给定了 k 个指标 ,其中 标准化后的数据的值为 ，有 2.求各指标的信息熵 第 j 项指标的信息熵可以这样定义: （18） 其中 ，如果 ，则定义 3.确定各指标权重 计算信息熵冗余度(差异)： 计算各项指标的权重： 计算各样本的综合得分：

38 6.3 模型求解 (1)首先利用熵权法构建每个道路节点的综合得分 (2) 根据 和 分别构建我方采取策略 而敌方采取策略 时我方的收益 ；我 方采取策略 而敌方采取策略 时敌方的收益 (3)分别构建博弈矩阵 和 按照双矩阵博弈的混合策略的纳什均衡准则，得到敌方最有可能攻击的三个道 路节点 J13、J08、J07。 6.4 结果分析 对抗博弈的关键在于敌我双方策略的选择：从我方视角来看，敌方选择攻击 的道路节点并不是我方认为 敌方最有可能攻击的节点；从敌方视角来看，敌方选 择攻击的道路节点也并不是敌方最希望攻击的节点。 这是一种非合作博弈后达到 的一种平衡状态，这种策略组合，反映了同一时间内每个参与人所作出的选 择是 对其他参与人作出的选择的最佳反应。基于纳什均衡得出的最可能受到敌方攻击 破坏的道路节点 并不一定是整体最优决策。其次，道路节点的选取是基于对抗博 弈评判指标的，所以当改变评判准则后， 所选取的节点也有可能发生变化 道路节点 m1 i (a) m2 j (a) J21 J27 J22 J40 J20

39 七 问题五 7.1 问题分析 在本问题中，需要考虑整体暴露时间，也要考虑规避敌方的侦察和打击，这 需要制定合理的机 动方案，采用适当分散机动的策略，同时还要缩短单台发射装 置的最长暴露时间。从问题三种 的结果分析知道单台发射装置的最长暴露时间对 于整体暴露时间有较大的影响，所以在建立模 型时要考虑暴露时间和分散机动的 均衡。 对于分散机动，不仅有地域上的分散，还有时间上的分散，考虑到路线网络 中转载地域分布不 均匀，而要实现分散机动的策略，则需要在两波打击的过程中， 使用到的发射基地尽可能分散，又因为需要单台发射装置最长暴露时间尽可能 短，所以在时间 上的分散要受到一定限制，以地域分散为主进行考虑，因此首先 需要整体考虑两个波次的发射 对发射基地进行分配，建立分散机动评价指标进行 评价，以使得两个波次中使用到的发射基地 尽量分散，然后构建合适的模型达到 最优策略。

40 7.2 模型构建 7.2.1 分散机动评价体 假设敌方对某一点（或区域）进行侦查或打击有一定的作用范围，而我方要尽量分 散机动，即要使得敌方进行侦查或打击的花费最高，如图 10 所示，假设 敌方侦查 范围（假设为飞机侦查，侦察到则会被打击损坏）为以飞机为中心，半 径分别为 R 的圆形区域，圆形区域内认为被敌方侦查到并打击损坏，且敌方针 对道路节点进行 打击。由于对敌方信息掌握不足，不能直接构建敌方侦查或打击 区域，可将问题等 价转变为我方发射装置经过的以道路节点为中心，R 为半径的 圆形辐射区域，敌方 飞机必须经过圆形区域才能侦查到发射装置。以所有发射装 置经过的道路节点的辐 射区域总面积与地图面积的比值作为分散指标 其中 Si 为发射装置经过节点的圆形区域面积， Stotal 为地图总面积

41 7.2.2 分散机动策略 从问题一根据转载区域对发射基地进行聚类的结果可知，发射基地和转载区域的配 置分布极不均匀，考虑敌方的侦查和打击进行分散机动则需要尽可能的将 发射装置 分散到较大范围的发射基地，因此我们根据各转载区域聚集发射基地数 量对发射装 置按下式进行分配 其中 Ni 为分配给第 i 个转载区域的发射装置数量，Si 为第 i 个转载区域聚集的发 射基地数量，发射基地和发射装置的分配如表 2 所示： 数量 发射基地 发射装置 Z01 17 8 Z02 5 2 Z03 1 Z04 3 Z05 6 Z06 22 表 2. 转载区域发射装置分配

42 7.3 结果分析 基于分散机动评判体系，去构建模型使得单车最大暴露时间尽量最短，构建目标函 数为： 约束条件：
其中 T 为单车最大暴露时间，由于分散评价标准和单车暴露时间不是一个量级，增 加权重，约束条件（25）是为了保证发射装置分配策略，约束条件（2） 到（7）与 问题一中相同。 7.3 结果分析 分散机动策略，从根本上是为了扩大发射装置在运输过程中的分布，使 得敌方较难 进行侦查和打击，但是在考虑到道路网络结构和发射装置速度的不一 致，所以构建 最优的分散策略很难。本文基于分散评价体系构建模型，增加了约 束条件，使得模 型容易求解。

43 八 总结分析 8.1 模型评价 8.1.1模型优点 本文针对多波次导弹发射中发射装置的机动路线规划问题，重点考虑了第一波次发 射装置的机动路线对第二波次发射装置整体暴露时间的影响，提出了基于聚类分析 的优化模型，通过设置合理约束条件，得到了第一波次导弹发射、第二波次重新装 弹再发射的综合路径规划策略，相比于直接分多阶段进行单独优化，本模型能通过 约束条件在整体框架中寻找最优策略，要比分段优化达到的整体暴露时间更短。 而且本文结合待机地域和转载地域非暴露的特点，引入两种路线时刻表调整方案： 1)待机区域出发时刻调整方案，2)转载地域到达\离开时刻调整方案，以减少整体暴 露时间。同时对单车道行驶问题，给出了道路节点到达\离开时刻调整方案，以避免 出现超车或相遇情况发生。 除了两波次导弹发射路径规划模型，本文还建立了基于双方对抗博弈的评价体系， 可以通过此体系对敌我双方的决策作出估计，并使我方获取最大收益。在问题五中 的分散机动策略能够有效的增加分散机动范围，并通过构建合理的分散机动评价指 标来进行评价，并根据评价指标来构建了分散机动模型，简化了问题的求解难度。

44 8.1.2模型缺点 在问题一中，由于发射装置速度的差异，在求解基于聚类分析约束的模型后整体暴 露时间仍然很大，可以看出在发射装置速度差异较大时需要考虑更加复杂的约束条 件来弥补快车与慢车之间的速度差距。 对于敌我双方对抗博弈，本文中暂时还未考虑多次博弈的情况，如果综合考虑多次 博弈的情形，结果将会更好。 8.2 模型改进思路 在问题一中，应该更多的考虑发射装置对于模型的影响，如果能添加更加合 理的速 度约束，相信模型会更加完美。 在问题三中，考虑的问题还不够全面，虽然新增的三台 C 类发射装置只参 与第二波 次的发射，但是如果从第一波次开始考虑，分配合适的发射基地，可能 会使得整体 暴露时间更短。 在问题四中，本文中仅仅只是考虑了完全信息静态博弈模型，暂时还未考虑 非完全 信息博弈模型和多次博弈模型，可以建立多个博弈模型相互比较，得出更 好的结果 。

45 九 参考文献 [1]王梓行, 姜大立, 杨李,等. 战时导弹火力打击任务分配与运输决策模型[J]. 后 勤工 程学院学报, 2017, 33(04). [2] 季青梅 , 辛文芳 . 多 波 次 导 弹 火 力 打 击 任 务 研 究 [J]. 信 息 技 术 与 信 息 化 , 2017(z1): [3]金宏, 余跃, 张如飞. 常规导弹联合火力打击统一分配模型[J]. 火力与指挥控 制, 2014(7):27-30. [4]杜正军, 陈超, 王长春. 策略不确定条件下基于高阶超博弈的军事对抗决策方 法[J]. 国防科技大学学报, 2012, 34(06): [5]王晋东, 余定坤, 张恒巍,等. 基于不完全信息攻防博弈的最优防御策略选取 方法[J]. 小型微型计算机系统, 2015, 36(10):

46 参考文献 [6]闫华, 何晓静, 周庆忠,等. 基于保障时间窗的油料调拨运输模型[J]. 后勤工程 学院学报, 2015(4):85-89. [7]张大巧, 鲜勇, 王明海,等. 基于 Floyd 算法的灵活航迹规划方法[J]. 弹箭与制 导学报, 2011, 31(6):55-58. [8]张大巧, 鲜勇, 王明海,等. 基于多路径算法的选飞航迹规划方法研究[J]. 弹箭 与制导学报, 2011, 31(4):69-72. [9]雷刚, 张大巧, 王澈. 无人飞行器延时航迹规划方法[J]. 空军工程大学学报·自 然科学版, 2014, 15(2):20-23.

47 3.3 详细行车方案 综合 节 确定的预定行车方案和 节得到的优化结果，即可得到详细的行 车方案，制成车队行程时刻表如表 3-7 所示，并绘制成详细的行军路线图，如图 所示，途中需要对 Q 型侦察卫星进行规避，对 Q 型卫星的过顶预测情况详见 节。

48

49 3.4 小结 针对问题二，主要做了以下工作： （1）选择星下点轨迹模型；
（1）根据任务要求，利用所给地图以及网络资源（百度地图等），进行机动路线规 划，先确定初步的行军路线，并在行军路线的基础上，进一步选择停车休息点， 即宿营地，给出了粗略的预定行车方案； （2）在确定机动路线的基础上，建立了规避模型，通过差分进化算法进行优化，得 到满足约束条件的机动时机，并建立验证模型，对优化结果进行验证，保证结果 的正确性。同时，建立对 Q 型卫星的预测模型，给定行军方案，即可对 Q 型卫 星的过顶情况进行预测； （3）综合机动路线和机动时机，得到详细的行军方案，包括车队行程时刻表和详细 的行军路线图。

50 THANK YOU

51 南昌大学研究生数学建模竞赛教学案例（库）
案例名称：多波次导弹发射中的规划问题 项目负责人：陈涛 所在学院：理学院