Step 1: Understand the given data
We have:
5 clients (customers), labeled \( i = 1, 2, 3, 4, 5 \)
10 candidate sites (possible facility locations), labeled \( j = 1, 2, \dots, 10 \)
p = 4 (we must open exactly 4 facilities)
Distance matrix (rows = clients, columns = sites):
j=1 2 3 4 5 6 7 8 9 10
i=1: 4 6 8 5 9 7 6 3 8 5
i=2: 7 3 6 8 5 4 9 6 7 4
i=3: 5 7 4 6 8 5 3 7 6 9
i=4: 9 6 5 4 7 8 6 5 4 6
i=5: 6 5 7 3 4 6 5 8 6 4
So, for example:
Client 1 to Site 1: distance = 4
Client 1 to Site 2: distance = 6
... and so on.
Step 2: Recall the goal
We want to choose *4 sites* out of 10 to open facilities on, and assign each client to the
nearest open site, so that the sum of distances from each client to its assigned facility is
*minimized*.
Step 3: Try a manual greedy approach (as the project suggests)
The greedy algorithm described says:
1. Start by picking the site with smallest sum of distances to all clients.
2. Then, for each remaining site, compute:
\[
C(j) = \sum_{i=1}^5 \min(d_{it}, d_{ij})
\]
where \( t \) is the already chosen site(s) but wait, the description seems a bit garbled. Let
me interpret carefully:
It says:
After choosing first site t, for each site j not chosen, compute C(j) = sum over clients i of
min( distance from i to t, distance from i to j ). Then pick j that minimizes C(j).
Remember in step 3, they say:
> Pour chaque site \( j \in J-S \), calculer : \( C(j) = i \in I \sum \min( \, d_{it} \, , \, d_{ij} \, ) \).
But we already have some chosen sites in S.
- For each unchosen site j, we compute: for each client i, find the closest distance among:
(distance to closest already chosen site, distance to j), and sum over all i. That's C(j).
- Then pick the unchosen site j with smallest C(j) to add next.
But if we interpret literally: at start, S has 1 site (the first one). For each j not in S,
C(j) = sum over i of min( d(i, chosen site), d(i, j) ).
Then pick j with smallest C(j) as second site.
Then repeat with S having 2 sites: now for each client i, the current "best" distance is min
over all chosen sites. For new j, C(j) = sum over i of min( current_best(i), d(i,j) ).
Step 4: Apply greedy algorithm manually
First, compute *sum of distances for each site j* (sum over i=1..5):
- Site 1: 4+7+5+9+6 = 31
- Site 2: 6+3+7+6+5 = 27
- Site 3: 8+6+4+5+7 = 30
- Site 4: 5+8+6+4+3 = 26
- Site 5: 9+5+8+7+4 = 33
- Site 6: 7+4+5+8+6 = 30
- Site 7: 6+9+3+6+5 = 29
- Site 8: 3+6+7+5+8 = 29
- Site 9: 8+7+6+4+6 = 31
- Site 10: 5+4+9+6+4 = 28
Smallest sum = 26 → *Site 4* is chosen first.
Now S = {4}. For each client, best distance = distance to site 4:
Client 1: d=5
Client 2: d=8
Client 3: d=6
Client 4: d=4
Client 5: d=3
Pick second site:
For each unchosen j (1,2,3,5,6,7,8,9,10), compute C(j) = sum over i of min( current_best(i),
d(i,j) ).
Let’s compute for j=1:
For client 1: min(5, 4) = 4
client 2: min(8, 7) = 7
client 3: min(6, 5) = 5
client 4: min(4, 9) = 4
client 5: min(3, 6) = 3
Sum = 4+7+5+4+3 = 23
j=2:
client 1: min(5,6) = 5
client 2: min(8,3) = 3
client 3: min(6,7) = 6
client 4: min(4,6) = 4
client 5: min(3,5) = 3
Sum=5+3+6+4+3=21
j=3:
client 1: min(5,8) = 5
client 2: min(8,6) = 6
client 3: min(6,4) = 4
client 4: min(4,5) = 4
client 5: min(3,7) = 3
Sum=5+6+4+4+3=22
j=5:
client 1: min(5,9) = 5
client 2: min(8,5) = 5
client 3: min(6,8) = 6
client 4: min(4,7) = 4
client 5: min(3,4) = 3
Sum=5+5+6+4+3=23
j=6:
client 1: min(5,7) = 5
client 2: min(8,4) = 4
client 3: min(6,5) = 5
client 4: min(4,8) = 4
client 5: min(3,6) = 3
Sum=5+4+5+4+3=21
j=7:
client 1: min(5,6) = 5
client 2: min(8,9) = 8
client 3: min(6,3) = 3
client 4: min(4,6) = 4
client 5: min(3,5) = 3
Sum=5+8+3+4+3=23
j=8:
client 1: min(5,3) = 3
client 2: min(8,6) = 6
client 3: min(6,7) = 6
client 4: min(4,5) = 4
client 5: min(3,8) = 3
Sum=3+6+6+4+3=22
j=9:
client 1: min(5,8) = 5
client 2: min(8,7) = 7
client 3: min(6,6) = 6
client 4: min(4,4) = 4
client 5: min(3,6) = 3
Sum=5+7+6+4+3=25
j=10:
client 1: min(5,5) = 5
client 2: min(8,4) = 4
client 3: min(6,9) = 6
client 4: min(4,6) = 4
client 5: min(3,4) = 3
Sum=5+4+6+4+3=22
Smallest C(j) = 21 (for j=2 and j=6). Pick the first one: *Site 2*.
Now S = {4, 2}.
Update current best distances for each client:
Client 1: min(5,6) = 5 (still site 4)
Client 2: min(8,3) = 3 (now site 2 is closer)
Client 3: min(6,7) = 6 (site 4)
Client 4: min(4,6) = 4 (site 4)
Client 5: min(3,5) = 3 (site 4)
Pick third site:
For each j not in {4,2}:
Let’s do a shortcut: Only compute if likely to be small. But we must check all:
j=1:
C(j) = sum over i of min( current_best(i), d(i,j) )
Client 1: min(5,4) = 4
Client 2: min(3,7) = 3
Client 3: min(6,5) = 5
Client 4: min(4,9) = 4
Client 5: min(3,6) = 3
Sum=4+3+5+4+3=19
j=3:
client1: min(5,8)=5
client2: min(3,6)=3
client3: min(6,4)=4
client4: min(4,5)=4
client5: min(3,7)=3
Sum=5+3+4+4+3=19
j=5:
client1: min(5,9)=5
client2: min(3,5)=3
client3: min(6,8)=6
client4: min(4,7)=4
client5: min(3,4)=3
Sum=5+3+6+4+3=21
j=6:
client1: min(5,7)=5
client2: min(3,4)=3
client3: min(6,5)=5
client4: min(4,8)=4
client5: min(3,6)=3
Sum=5+3+5+4+3=20
j=7:
client1: min(5,6)=5
client2: min(3,9)=3
client3: min(6,3)=3
client4: min(4,6)=4
client5: min(3,5)=3
Sum=5+3+3+4+3=18
j=8:
client1: min(5,3)=3
client2: min(3,6)=3
client3: min(6,7)=6
client4: min(4,5)=4
client5: min(3,8)=3
Sum=3+3+6+4+3=19
j=9:
client1: min(5,8)=5
client2: min(3,7)=3
client3: min(6,6)=6
client4: min(4,4)=4
client5: min(3,6)=3
Sum=5+3+6+4+3=21
j=10:
client1: min(5,5)=5
client2: min(3,4)=3
client3: min(6,9)=6
client4: min(4,6)=4
client5: min(3,4)=3
Sum=5+3+6+4+3=21
Smallest C(j) = 18 for *j=7*.
So S = {4, 2, 7}.
Update current best distances:
Client 1: min(5,6) = 5 (still site 4)
Client 2: min(3,9) = 3 (still site 2)
Client 3: min(6,3) = 3 (now site 7 closer)
Client 4: min(4,6) = 4 (site 4)
Client 5: min(3,5) = 3 (site 4)
Pick fourth site:
S = {4,2,7}, need one more.
j=1:
C= sum min(current_best, d(i,j))
client1: min(5,4)=4
client2: min(3,7)=3
client3: min(3,5)=3
client4: min(4,9)=4
client5: min(3,6)=3
Sum=4+3+3+4+3=17
j=3:
client1: min(5,8)=5
client2: min(3,6)=3
client3: min(3,4)=3
client4: min(4,5)=4
client5: min(3,7)=3
Sum=5+3+3+4+3=18
j=5:
client1: min(5,9)=5
client2: min(3,5)=3
client3: min(3,8)=3
client4: min(4,7)=4
client5: min(3,4)=3
Sum=5+3+3+4+3=18
j=6:
client1: min(5,7)=5
client2: min(3,4)=3
client3: min(3,5)=3
client4: min(4,8)=4
client5: min(3,6)=3
Sum=5+3+3+4+3=18
j=8:
client1: min(5,3)=3
client2: min(3,6)=3
client3: min(3,7)=3
client4: min(4,5)=4
client5: min(3,8)=3
Sum=3+3+3+4+3=16
j=9:
client1: min(5,8)=5
client2: min(3,7)=3
client3: min(3,6)=3
client4: min(4,4)=4
client5: min(3,6)=3
Sum=5+3+3+4+3=18
j=10:
client1: min(5,5)=5
client2: min(3,4)=3
client3: min(3,9)=3
client4: min(4,6)=4
client5: min(3,4)=3
Sum=5+3+3+4+3=18
Smallest C(j) = 16 for *j=8*.
So final S = {4, 2, 7, 8}.
Step 5: Assign clients to nearest facility in S
Sites chosen: 4, 2, 7, 8.
Check distances for each client:
Client 1:
d(1,4)=5, d(1,2)=6, d(1,7)=6, d(1,8)=3 → nearest site 8, distance 3
Client 2:
d(2,4)=8, d(2,2)=3, d(2,7)=9, d(2,8)=6 → nearest site 2, distance 3
Client 3:
d(3,4)=6, d(3,2)=7, d(3,7)=3, d(3,8)=7 → nearest site 7, distance 3
Client 4:
d(4,4)=4, d(4,2)=6, d(4,7)=6, d(4,8)=5 → nearest site 4, distance 4
Client 5:
d(5,4)=3, d(5,2)=5, d(5,7)=5, d(5,8)=8 → nearest site 4, distance 3
Step 6: Compute total cost
Sum = 3 (C1→S8) + 3 (C2→S2) + 3 (C3→S7) + 4 (C4→S4) + 3 (C5→S4)
= 3 + 3 + 3 + 4 + 3 = *16*.
Step 7: Interpretation
We’ve manually applied the greedy algorithm and found:
*Selected sites*: 4, 2, 7, 8
*Assignments*:
Client 1 → Site 8
Client 2 → Site 2
Client 3 → Site 7
Client 4 → Site 4
Client 5 → Site 4
*Total cost*: 16
This is an *approximate solution* from the greedy heuristic. The *optimal solution* (using
CPLEX) might be slightly better, but this is a reasonable manual result.
*Visualizing the solution* (drawing the graph):
- Nodes: clients 1–5, facilities 2,4,7,8
- Edges: each client connected to its assigned facility
- Labels show distances
This matches the project’s requirement: show graph and objective function value = 16.