用线性规划解决《戴森球计划》中的生产规划问题

李辰剑 2023-6-16 定稿

一、问题引入

《戴森球计划》相信大家都很熟悉啦，它是一款科幻主题的模拟经营游戏。在《戴森球计划》中，玩家需要在宇宙中采集材料、解锁科技、进行工业生产，最终建造出一个包裹恒星的戴森球，通过戴森球大量收割恒星的太阳能。然而，《戴森球计划》中科技产品的生产和建造极其复杂（配方很复杂，供应链更复杂）；而建造整个戴森球（包裹整个恒星，物资消耗能不大吗）又需要大量物资，对生产的规模和效率提出了很高的要求。因此，玩家常常需要花费大量时间来设计、建造、调整各种科技产品的生产线，非常痛苦。这也是《戴森球计划》被许多玩家诟病“费肝”的原因。

于是我就想，能否用计算机科学中一些成熟的优化算法来帮忙设计生产线呢？我初步筛选出了三个可以用计算机算法优化的任务：

(1) 用线性规划求解最优的资源、产品分配。《戴森球计划》中的产业链很长，一些产品的生产配方较为复杂，需要经过多道生产步骤。例如，以下是低阶科技产品电动马达的生产线路图：

如何合理分配资源（例如，以合适的比例将铁矿分配到铁块和磁铁的生产中）以最大化目标产出（例如，最大化马达的生产速率）是一个麻烦的问题。但这一步骤恰好可以用线性规划（Linear Programming）模型求解。

(2) 用集成芯片设计算法优化工厂和物流的布局布线。 《戴森球计划》中的工厂输入输出和布局可以非常复杂… 其实这和集成芯片物理设计中的元件布局和布线有许多相似之处。

(3) 用非线性模型优化工厂位置和物流。这个我懂，区位条件嘛！哪颗星球铁矿多、就着重生产钢铁、马达；哪颗星球石油多，就着重搞能源工业和石油化工。如果有市场经济，每个工厂的厂长就会自己搬去离原料最近的工厂，从而最小化物流开销。——可惜《戴森球计划》中的所有生产都由玩家一人负责，因此需要玩家自己优化所有工厂的位置，相当繁琐。如果能写出一个目标函数，以工厂选址为输入变量变量、以物流成本为函数值、再对该函数进行最优化，就可以得到最优的工厂选址，从而将玩家从繁琐的工厂规划中解放出来。

虽然三个想法都很诱人，但是布局布线和非线性优化都过于复杂…… 于是我决定先尝试基于线性规划的想法(1)。也许以后可以试试另两个想法 :-)

《戴森球计划》游戏内截图。上：《戴森球计划》中的生产线；下：正在建造中的戴森球。