Set Covering Problem#
이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 405.
해운대구는 최근 신시가지 개발의 완료와 더불어 각종 범죄가 급속도로 지능화, 신속화, 흉악화 되어가고 있다. 따라서 부산시경에서는 수사의 신속성과 기동성을 확보함으로써 수사의 효율성을 제고하기 이ㅜ하여 해운대구에 파출소를 설치하기로 결정하고 해운대구에서 범죄 발생빈도가 높은 파출소의 후보지역을 조사한 결과 9개 지역으로 나타났다. 부산시경에서는 해운대구에서 조사된 범죄 발생빈도가 높은 9개 지역을 파출소의 설치대상 후보지역으로 선정하고 범죄가 발생할 때 최대로 8분 이내에 범죄 현장에 도착할 수 있도록 이 후보지역 중에서 특정 지역을 선정하여 파출소를 설치하려고 한다. Table은 각 후보지역의 파출소 설치비용과 각 후보지역을 기준으로 8분 이내에 범죄현장에 도착할 수 있는 후보지역을 조사한 결과이다.
| 파출소 후보지역 | 파출소 설치비용(천만원) | 8분 이내 도착가능 후보지역 |
|---|---|---|
| 1 | 6 | 1, 2, 3, 4, 5 |
| 2 | 7 | 1, 2, 4, 5, 9 |
| 3 | 5 | 1, 3, 4, 5, 6, 7, 8 |
| 4 | 7 | 1, 2, 3, 4, 5, 6, 9 |
| 5 | 9 | 1, 2, 3, 4, 5, 9 |
| 6 | 10 | 3, 4, 6, 7, 8 |
| 7 | 8 | 3, 5, 7, 8, 9 |
| 8 | 5 | 3, 6, 7, 8, 9 |
| 9 | 11 | 2, 4, 5, 7, 8, 9 |
파출소를 최소의 수로 설치하여 9개의 지역에서 버모지가 발생할 때 8분 이내에 범죄현장에 도착하도록 하고자 할 때 어느 후보지역에 파출소를 설치하면 되겠는가?
최소의 파출소 설치비용으로 파출소를 설치하여 9개의 지역에서 범죄가 발생할 때 8분 이내에 범죄현장에 도착하도록 하고자 할 때 어느 후보지역에 파출소를 설치하면 되겠는가?
최소의 파출소 후보지역을 구하기 위한 0-1정수계획모형#
\[\begin{split}\begin{align*}
& \text{minimize } & Z=7&X_{1} + 8X_{2} + 3X_{3} \\
& \text{subject to } & \, 3&X_{1} + 4X_{2} + 2X_{3} \le 6 \\
& \text{and} & \, &X_{j} = 0 \text{ or } 1 (j=1,2,3)
\end{align*}\end{split}\]
import sys
# Add the parent directory for importing custom library
sys.path.append('../')
from pulp import *
from ortools.utils import output
# Define problem
prob = LpProblem('Set Covering Problem', LpMinimize)
# Create decision variables and non-negative constraint
x1 = LpVariable(name='X1', lowBound=0, cat='Binary')
x2 = LpVariable(name='X2', lowBound=0, cat='Binary')
x3 = LpVariable(name='X3', lowBound=0, cat='Binary')
x4 = LpVariable(name='X4', lowBound=0, cat='Binary')
x5 = LpVariable(name='X5', lowBound=0, cat='Binary')
x6 = LpVariable(name='X6', lowBound=0, cat='Binary')
x7 = LpVariable(name='X7', lowBound=0, cat='Binary')
x8 = LpVariable(name='X8', lowBound=0, cat='Binary')
x9 = LpVariable(name='X9', lowBound=0, cat='Binary')
# Set objective function
prob += x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9
# Set constraints
prob += x1 + x2 + x3 + x4 + x5 >= 1
prob += x1 + x2 + x4 + x5 + x9 >= 1
prob += x1 + x3 + x4 + x5 + x6 + x7 + x8 >= 1
prob += x1 + x2 + x3 + x4 + x5 + x6 + x9 >= 1
prob += x3 + x4 + x6 + x7 + x8 >= 1
prob += x3 + x5 + x7 + x8 + x9 >= 1
prob += x3 + x6 + x7 + x8 + x9 >= 1
prob += x2 + x4 + x5 + x7 + x8 + x9 >= 1
# Solving problem
prob.solve()
output(prob)
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
2 from ortools.utils import output
4 # Define problem
ModuleNotFoundError: No module named 'pulp'
from pulp import *
from ortools.utils import output
# Define problem
prob = LpProblem('Set Covering Problem', LpMinimize)
# Create decision variables and non-negative constraint
x1 = LpVariable(name='X1', lowBound=0, cat='Binary')
x2 = LpVariable(name='X2', lowBound=0, cat='Binary')
x3 = LpVariable(name='X3', lowBound=0, cat='Binary')
x4 = LpVariable(name='X4', lowBound=0, cat='Binary')
x5 = LpVariable(name='X5', lowBound=0, cat='Binary')
x6 = LpVariable(name='X6', lowBound=0, cat='Binary')
x7 = LpVariable(name='X7', lowBound=0, cat='Binary')
x8 = LpVariable(name='X8', lowBound=0, cat='Binary')
x9 = LpVariable(name='X9', lowBound=0, cat='Binary')
# Set objective function
prob += 6*x1 + 7*x2 + 5*x3 + 7*x4 + 9*x5 + 10*x6 + 8*x7 + 5*x8 + 11*x9
# Set constraints
prob += x1 + x2 + x3 + x4 + x5 >= 1
prob += x1 + x2 + x4 + x5 + x9 >= 1
prob += x1 + x3 + x4 + x5 + x6 + x7 + x8 >= 1
prob += x1 + x2 + x3 + x4 + x5 + x6 + x9 >= 1
prob += x3 + x4 + x6 + x7 + x8 >= 1
prob += x3 + x5 + x7 + x8 + x9 >= 1
prob += x3 + x6 + x7 + x8 + x9 >= 1
prob += x2 + x4 + x5 + x7 + x8 + x9 >= 1
# Solving problem
prob.solve()
output(prob)
Status: Optimal
Objective value: 11.0
Variables Values
----------- --------
X1 1
X2 0
X3 0
X4 0
X5 0
X6 0
X7 0
X8 1
X9 0
Statistics:
- Number of variables: 9
- Number of constraints: 8
- Solve time: 0.008s