如何帮助普京赢得俄乌战争？

引言

2022 年 2 月 24 日，俄罗斯总统普京授权俄军对乌克兰发动全面战争，并迅速演变为继第二次世界大战以来欧洲最大规模的战争^[1]。战争初期，俄军出其不意攻其不备，打得乌克兰方面措手不及、节节败退。很多人都以为这会是一场闪电战，俄军会迅速拿下基辅、哈尔科夫等大城市。然而随着战争的推进，俄军的优势逐渐丧失。目前，俄军已经从基辅地区撤退，占领基辅的目标基本宣告失败。

图 1: 被俄军控制的乌克兰领土（红色区域）^[2]

从战争开始俄罗斯全面入侵的态势，可以看出俄罗斯原计划是想打下整个乌克兰。俄罗斯“去军事化乌克兰”的战争目标，实际上等同于推翻当前的乌克兰政府，重新建立一个没有军队的亲俄政府。想要达成这样一个目的，也必须打下整个乌克兰。

图 2: 乌克兰苏梅地区俄军丢弃的损毁坦克

但事与愿违，俄罗斯并没有能够快速拿下乌克兰，原因是多方面的。第一，俄军并没有想象得那么强大，俄乌战争中俄军表现非常拉胯、作战意志低下，后勤严重跟不上实际作战的需求。乌克兰各地战场上，到处可见俄军丢弃的装甲坦克（图 2）。

图 3: 泽连斯基前往布查查看战役后的情况

第二，俄罗斯明显低估了乌克兰及其总统。战争的第二天，俄方就认为演员出生的乌克兰总统泽连斯基并没有作战的勇气，并且已经逃离基辅。然而泽连斯基却坚持留守基辅（图 3），表现出了巨大的勇气。甚至在美国提议帮助其撤离基辅时，明确拒绝并表示：“我需要的是弹药，而不是搭车”。战争中，乌军表现出了很强的韧性，就连美国情报人员都承认：开战之初，低估了乌军。第三，以美国为首的西方国家不断向乌克兰提供军事援助。除了拨款援助乌克兰，还一直向乌克兰运送各种反坦克武器、防空导弹，以及轻型武器和弹药军事设备。

图 4: 拜登表示俄不会赢得这场战争的胜利

想要赢得一场战争并不是一件容易的事。俄军在这场战争中的策略是否还有优化的余地？针对这个问题，本文将俄乌战争简化为“坦克输送问题”，并从俄罗斯的角度来优化兵力分布和进攻路线。需要声明的是：本文对战争策略的讨论，纯粹是为了演示图论模型在战争中的应用。本文的标题“如何帮助普京赢得俄乌战争？”，以及本文“从俄罗斯的角度”都不代表本文作者支持俄罗斯发动的这场战争。相反，本文作者认为俄罗斯应该立即停止这场战争。

问题

占领乌克兰基辅在内几个最重要的城市是俄罗斯在俄乌战争中取得胜利的重要标志。所谓的“占领”某个城市，实际上就是将指定数量的兵力（军队、装备、物资等）成功输送到这个城市。这里的“输送”可不是简单的物流问题，因为互为敌对的势力会以战斗的形式相互阻拦这种“输送”。为了简化问题，本文将兵力泛化为坦克（实际上有多种军用车辆）。

图 5: 乌城市道路图和俄军七个集结区

图 5 显示的是乌克兰主要城市和城市间的道路^[3,4]。图中每个节点表示一座城市，节点间的连线（边）表示两座城市间的道路。红色方型节点表示俄乌战争起始阶段俄军的七个集结区。这七个集结区位于乌克兰领土边界附近，是俄军在入侵乌克兰之前占据的阵地，俄军的坦克将由这七个集结区入侵乌克兰。图 5 中每条边最显而易见的一个属性是道路的长度。坦克差不多以固定的速度行驶，因此道路的长度直接决定了坦克通过连接两个城市道路所需的时间。但对于试图通过某条道路的俄军坦克，它们可能面临燃料补给不足而被舍弃或遭乌军攻击而损毁。因此，我们还应该考虑坦克能够顺利通过一条道路的概率。这个概率与以下三个因素相关：

• 道路的长度：道路越长，油箱在沿途某处被伏击的可能性就越高。坦克燃料耗尽或在途中发生故障的可能性就越高。
• 补给站距离：坦克的油箱中如果没有足够的燃料通过一条道路，坦克必需依靠装载燃料的卡车提供补给。如果离最近的补给站距离过远，装载燃料的卡车不能及时提供补给，那么坦克很可能会被迫舍弃。
• 乌军的抵抗：对于俄军的入侵，乌军显然不会坐以待毙。乌军除了有自己的坦克，还有FGM-148标枪导弹、MBT LAW 反坦克导弹、弹簧刀无人机等反击武器。乌军可能会将这些有限资源集中布置于某些重要的道路上。

为了方便显示，本文把图 5 中的节点和边重新绘制在图 6 中，并将每条边代表的道路长度和坦克能够通过的概率标注在了相应的边上。道路的长度是由谷歌地图得到的。坦克通过的概率是人为估计的，其大小并没有太多实际参考价值，但这并不影响本文的“纸上谈兵”。如果俄军真的想要知道这些概率，可以重金聘请大模头这样的军事专家进行评估。

图 6: 乌城市路径长度和坦克通过概率

假设战争开始前，俄军打算投入 5000 辆坦克，并且希望将 3000、1000、500、500 辆坦克分别“输送”到基辅（Kyiv）、哈尔科夫（Kharkiv）、马里乌波尔（Mariupol）、敖德萨（Odesa）这四个最重要的乌克兰城市。俄军该如何分配每个集结区坦克的数量和设计进攻路线，才能以最小的成本将辆坦克成功“输送”到目的地呢？

模型

上述“俄军坦克输送问题”可以转化为图论中的最小费用流问题。接下来本文先简单介绍一下最小费用流问题以及该问题的线性规划模型。在此基础上，将模型应用到“俄军坦克输送问题”。

最小费用流问题

在运输过程中，人们总是希望在完成任务的同时，寻求一个使总的运输费用最小的方案，图论中的最小费用流就是典型的这种问题^[5]。所谓最小费用流问题，就是在指定网络流量的情况下，寻求最小费用的可行流。最小费用流问题的图论提法如下：对于给定的网络  = ， 和  分别为源点和汇点，该网络由有向图  及定义在弧（有方向的边） 上的容量函数  =  和费用函数  =  构成。 和  为弧  上的容量和单位流量费用。最小费用流问题就是寻求从  到  流量为  的一个可行流，使得该可行流费用最小。用线性规划的方法，最小费用流问题可以描述为其中  表示边  上的流量。最小费用流问题可以应用 Busacker-Gowen 等算法来求解，但较之于线性规划，无论是算法的描述还是程序的实现上都烦杂得多。

最小费用流实例

上述最小费用流问题的描述是针对单个汇点的，实际上它很容易扩展到多个汇点。以图 7 为例^[6]，现要将 20 吨货物从 1 号地点（源节点）运送到 4 号和 5 号地点（汇节点），4 号和 5 号节点分别需要 5 吨和 15 吨货物（需求）。

图 7: 容量、单位流量费用、需求和最小费用流

各地点之间道路（弧）的最大运输能力（容量）、每吨运量的费用（单位流量费用）已经标于各条弧上，求完成运输任务需要的最小费用。这个问题的目标函数可表示为其中  及其前面的系数 4 分别表示弧  上的流量（运输的货物量）和单位流量费用，等号右侧其它项的定义类似。为了保证流量的守恒，流入和流出每个节点的流量还要满足一定的约束条件。对于源节点，流出的流量必须等于源提供的流量。因此，1 号节点约束条件为：对于汇节点，流入与流出的流量之差应该等于其需求的流量。例如，5 号节点的约束条件为：类似地，我们也可以列出 4 号节点（另一个汇节点）的约束条件。而对于非源非汇节点，流入每个节点和流出每个节点的流量应该相等。例如，2 号节点约束条件为：类似地，我们也可以列出 3 号节点（另一个非源非汇节点）的约束条件。此外，每条弧上的流量还必需小于每条弧的容量。例如， 还必需满足约束条件：类似地，我们也可以列出其它每条弧的流量约束条件。应用 MATLAB 提供的linprog函数可以很容易地求解由上述目标函数和一系列约束条件构成的线性规划问题，求解得到的每条弧上的流量已经标注在图 7 中，相应的最小费用为 150。

俄军坦克输送问题

尽管上述“最小费用流问题”可以很容易地扩展到多个汇点，并且本文也展示了一个多汇问题的实例（图 7），但仍然针对的是单个源点的问题。“俄军坦克输送问题”涉及七个源点（集结区），而我们又不知道起始应该为每个集结区分配多少辆坦克。如果我们希望算法能自动告诉我们这一点，可以在图 5 中添加一个虚拟源点 （添加后的效果见图 8）。将所有集结区都连接到这个虚拟的 “源点”（可以认为是俄军的大本营），并将虚拟源点  到七个集结区边（红色虚线）的单位流量费用都设置为 0，容量都设置为 。

图 8: 添加源  后转化为最小费用流问题

在此基础上，如果再为其它每条边赋上一个容量和单位流量费用，“俄军坦克输送问题”就转化为了单源多汇的“最小费用流问题”。边的容量表示的是：如果没有乌军的抵抗，可以通过一条边的坦克最大数量。大多数情况下，每条边的容量可以设置为无限。但如果希望在短时间内结束战争，就必须考虑一段时间内道路的通行能力。此外，有限的容量会迫使算法将坦克分散到多条路径上。简单起见，我们假设所有道路的容量相同且都为  = 720， 。对于每条边上的单位流量费用，可以从“通过时间”和“通过概率”这两个角度来考虑。

结果

接下来，本文将分别以每条的“通过时间”和“通过概率”作为该边的单位流量费用来求解最小费用流问题，并讨论其现实意义。

以通过时间为费用

如果将道路的通过时间  作为边的单位流量费用，即  =   （道路的通过时间正比于道路的长度），那么“俄军坦克输送问题”实际上就是要最小化所有坦克行驶的总路程（相当于最省燃料）。这个问题可以直接转化为单源多汇的“最小费用流问题”，并可应用线性规划进行求解，结果如图 9 所示。图 9 中不同粗细的红色箭头表示不同大小的流量，这些流量值也同时标注在了相应的弧上。

图 9: 以道路长度为费用的最小费用流

对照图 5 中城市的名称，可以得到每个集结区应该分配的坦克数量和进攻路线。例如，对于 3 号集结区：720 辆坦克经 Belgorod  Kharkiv（留下 280 辆） Okhtyrka  Pyriatyn  Kyiv（留下 440 辆）。

以通过概率为费用

相比于“如果坦克能到达目的地，需要行驶多长时间”这个问题，俄军可能更关心“坦克能不能到达目的地”。因此，通过某条边  的概率  可能比通过该条边需要花费的时间  更重要。我们总是希望坦克通过一条路径的时间最短、概率最大。如果某条路径由  条边构成，坦克通过该路径的总时间可以表示为通过每条边的时间之和，即 而坦克通过该路径的概率并不等于通过每条边的概率之和，而是等于通过每条边的概率之积，即 标准的最小费用流问题对费用的计算是加法，而不是乘法。因此，不能将  直接作为边  的单位流量费用。可以通过对上式取对数的方式来将乘积转变为加和： 上式中  的最小化等价  的最大化（注意，所有概率值都是小于 1 的）。因此，可以用  作为边的单位流量费用（即  = ），从而可以继续套用最小费用流问题的求解方法，求解结果如图 10 所示。图中不同粗细的红色箭头表示不同大小的流量，这些流量值也同时标注在了相应的弧上。

图 10: 以概率对数为费用的最小费用流

对照图 5 中城市的名称，可以得到每个集结区应该分配的坦克数量和进攻路线。例如，对于 3 号集结区：720 辆坦克经 Belgorod  Kharkiv（留下 100 辆） Okhtyrka  Pyriatyn  Kyiv（留下 620 辆）。

对比以通过时间为费用的结果（图 9），不难发现：两种不同的单位流量费用下，每个集结区应该分配的坦克数量相同，进攻路线相似（略有不同）。这是因为本文在估计坦克通过每条边的概率时，极大地依赖了每条边的长度。

此外，需要注意的是：最小费用流问题暗含着所有坦克都能到达目的地。因此，以  作为边的单位流量费用时，实际上仍然假设了所有坦克都能到达目的地，只是其中一些坦克到达目的地时是损坏的（实际上它们并没有到达，而是被丢弃在途中了）。这些损坏的坦克尸体在目的地不能做任何事情。

结论

2022 年 2 月 24 日，俄罗斯对乌克兰发动了全面战争，然而随着战争的推进，俄军的优势逐渐丧失。战争的策略直接影响着局势的走向。本文将俄乌战争简化为“坦克输送问题”，并从俄罗斯的角度来优化兵力分布和进攻路线。通过添加虚拟源节点，将“坦克输送问题”转化为图论中的最小费用流问题，并采用线性规划进行求解。对于每条边上的单位流量费用，本文分别从“通过时间”（相当于最省燃料）和“通过概率”（相当于坦克最少损毁）这两个角度来考虑，最终得到了两种角度下七个集结区应该分配的坦克数量和进攻路线。

尽管本文是“从俄罗斯角度”讨论和优化战争策略的，但本文的讨论对乌克兰方面也具有同样的参考价值。因为乌克兰方面可以通过预判俄罗斯的策略，重新部署其有限的防守力量，确保没有一条路线能够将大量坦克“运送”到基辅等重要城市。

附录

点击文章左下角“阅读原文”获取本文 PDF 版和附件。

参考资料

[1]

Wikipedia contributors. Russo-ukrainian war, 2022: https://en.wikipedia.org/wiki/Russo-Ukrainian_War

[2]

Wikipedia contributors. File:2022 russian invasion of ukraine.svg, 2022: https://commons.wikimedia.org/wiki/File:2022_Russian_invasion_of_Ukraine.svg

[3]

Pareto Software. Ukraine cities database, 2022: https://simplemaps.com/data/ua-cities

[4]

Rohit Pandey. Data science in battle: Applying graph theory to the ukraine war, 2022: https://medium.com/@rohitpandey576

[5]

周吕文. 图论与网络模型, 2015.

[6]

Google Developers. Minimum cost flows, 2021: https://developers.google.com/optimization/flow/mincostflow