题目
例4.7(集合覆盖和布点问题)某市消防队布点问题.该市共有6个区,每个区都可以建-|||-消防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时,消防车要在-|||-15min内赶到现场.据实地测定,各区之间消防车行驶的时间见表.请制定一个布点最少的-|||-计划.-|||-地区1 地区2 地区3 地区4 地区5 地区6-|||-地区1 0 10 16 28 27 20-|||-地区2 10 0 24 32 17 10-|||-地区3 16 24 0 12 27 21-|||-地区4 28 32 12 0 15 25-|||-地区5 27 17 27 15 0 14-|||-地区6 20 10 21 25 14 0
题目解答
答案
解析
步骤 1：定义变量
引入0-1变量 ${x}_{i}$，其中 ${x}_{i}=1$ 表示在第i个区建立消防站，${x}_{i}=0$ 表示不建立消防站，i=1,2,3,4,5,6。
步骤 2：建立目标函数
目标是使建立的消防站数量最少，因此目标函数为：
$$
\min z = {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} + {x}_{5} + {x}_{6}
$$
步骤 3：建立约束条件
根据题目要求，每个区必须在15分钟内到达最近的消防站。根据给定的消防车行驶时间表，可以建立以下约束条件：
$$
\begin{align*}
x_{1} + x_{2} &\geq 1 \\
x_{1} + x_{2} + x_{6} &\geq 1 \\
x_{3} + x_{4} &\geq 1 \\
x_{3} + x_{4} + x_{5} &\geq 1 \\
x_{4} + x_{5} + x_{6} &\geq 1 \\
x_{2} + x_{5} + x_{6} &\geq 1
\end{align*}
$$
这些约束条件确保了每个区至少有一个消防站在15分钟内可以到达。
步骤 4：求解
通过求解上述整数规划问题，可以得到最优解。根据题目给出的解，最优解为：
$$
X = (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}) = (0, 1, 0, 1, 0, 0)
$$
即在地区2和地区4建立消防站，最少需要建立2个消防站。
引入0-1变量 ${x}_{i}$，其中 ${x}_{i}=1$ 表示在第i个区建立消防站，${x}_{i}=0$ 表示不建立消防站，i=1,2,3,4,5,6。
步骤 2：建立目标函数
目标是使建立的消防站数量最少，因此目标函数为：
$$
\min z = {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} + {x}_{5} + {x}_{6}
$$
步骤 3：建立约束条件
根据题目要求，每个区必须在15分钟内到达最近的消防站。根据给定的消防车行驶时间表，可以建立以下约束条件：
$$
\begin{align*}
x_{1} + x_{2} &\geq 1 \\
x_{1} + x_{2} + x_{6} &\geq 1 \\
x_{3} + x_{4} &\geq 1 \\
x_{3} + x_{4} + x_{5} &\geq 1 \\
x_{4} + x_{5} + x_{6} &\geq 1 \\
x_{2} + x_{5} + x_{6} &\geq 1
\end{align*}
$$
这些约束条件确保了每个区至少有一个消防站在15分钟内可以到达。
步骤 4：求解
通过求解上述整数规划问题，可以得到最优解。根据题目给出的解，最优解为：
$$
X = (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}) = (0, 1, 0, 1, 0, 0)
$$
即在地区2和地区4建立消防站，最少需要建立2个消防站。