집합덮개문제와 시설결정문제 예제

이번에는 집합덮개문제(Set covering problem)와 시설 결정 문제의 예제들을 해결해보자. 경찰서 위치 결정 문제 주 정부에서는 새로운 경찰서를 열려고 한다. 주는 총 7개의 구역으로 나누어져 있고 각각의 경찰서는 주변 30마일 반경을 커버할 수 있다. 모든 구역은 최소한 하나 이상의 경찰서에게 커버되어야 한다. 최소 경찰서수를 구해보자. 이때 어느 도시에서 어느 도시 까지의 거리는 위와 같다. 위는 공분산 행렬 처럼 대각행렬을 기준으로 대칭이 아니다. 우선 문제를 위와 같이 단순화해서 30 이상인 경우 0, 30 이하일 경우 1로 하였다. 먼저 목표값을 경찰서의 수, 결정변수를 각 지역에 두는 경찰서의 수이다. 당연히 한 지역에는 하나의 경찰서만 들어서게 될 것이다. 엑셀로 만들면 위와 같다. 커버되는지에 대한 여부는 위와 같이 계산했다. 이번에는 택시 회사가 택시를 각 고객에게 배치하는 경우가 있다. 택시의 위치는 모두 다르고 각 고객의 위치도 다 다르다. 이를 표로 ...