Python解决消防站的选址问题

原文参考该博文

问题描述

源代码

import pulp  # 导入 pulp 库# 主程序
def main():# 问题建模："""决策变量：x(j) = 0, 不选择第 j 个消防站x(j) = 1, 选择第 j 个消防站, j=1,8目标函数：min fx = sum(x(j)), j=1,8约束条件：sum(x(j)*R(i,j),j=1,8) >=1, i=1,8变量取值范围：x(j) = 0,1"""# 消防站的选址问题 (set covering problem, site selection of fire station)# 1.建立优化问题 SetCoverLP: 求最小值(LpMinimize)SetCoverLP = pulp.LpProblem("SetCover_problem_for_fire_station", sense=pulp.LpMinimize)  # 定义问题，求最小值# 2. 建立变量zones = list(range(8))  # 定义各区域x = pulp.LpVariable.dicts("zone", zones, cat="Binary")  # 定义 0/1 变量，是否在该区域设消防站# 3. 设置目标函数SetCoverLP += pulp.lpSum([x[j] for j in range(8)])  # 设置消防站的个数# 4. 施加约束reachable = [[1, 0, 0, 0, 0, 0, 0, 0],[0, 1, 1, 0, 0, 0, 0, 0],[0, 1, 1, 0, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0],[0, 0, 0, 0, 0, 1, 1, 0],[0, 0, 0, 0, 0, 0, 1, 1],[0, 0, 0, 0, 0, 0, 1, 1]]  # 参数矩阵，第 i 消防站能否在 10分钟内到达第 j 区域for i in range(8):SetCoverLP += pulp.lpSum([x[j] * reachable[j][i] for j in range(8)]) >= 1# 5. 求解SetCoverLP.solve()# 6. 打印结果print(SetCoverLP.name)temple = "区域 %(zone)d 的决策是：%(status)s"  # 格式化输出if pulp.LpStatus[SetCoverLP.status] == "Optimal":  # 获得最优解for i in range(8):output = {'zone': i + 1,  # 与问题中区域 1~8 一致'status': '建站' if x[i].varValue else '--'}print(temple % output)print("需要建立 {} 个消防站。".format(pulp.value(SetCoverLP.objective)))returnif __name__ == '__main__':main()

运行结果

要点

temple = “区域 %(zone)d 的决策是：%(status)s”
output = {‘zone’: i + 1, # 与问题中区域 1~8 一致
‘status’: ‘建站’ if x[i].varValue else ‘–’}
print(temple % output)
学习一下使用字典的格式化输出方法。