Université d’Ottawa Faculté de génie
École de science d’informatique
et de génie électrique
University of Ottawa Faculty of Engineering
School of Electrical Engineering and Computer Science
Assignment 0
CSI2120 Programming Paradigms
Winter 2019
Part 1 due on February 15th before 11:00 pm in Virtual Campus Part 2,3 due on March 15th, 2018 before 11:00 pm in Virtual Campus Part 4 due on April 5th before 11:00 pm in Virtual Campus
[12 marks in total]
Problem Description
In this assignment, we study the classic problem of transporting goods to places where they are in demand. Suppose we have a number of factories, located in different locations and each having a certain production capacity. The goods produced must be sent to warehouses that are also located around the world and that, depending on demand, require a certain amount of goods. This problem is usually represented by a table.
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
($6)
($8)
($10)
30
Factory 2
($7)
($11)
($11)
40
Factory 3
($4)
($5)
($12)
50
The above table contains the number of units produced by each factory and requested by each warehouse. The numbers in parentheses indicate the cost of transporting a unit from a factory to a warehouse. The problem is to find out how many goods are to be sent to each warehouse from each factory in order to minimize transportation costs. Note that we consider here the case where supply and demand are balanced.
This problem can be solved in different ways. In this assignment, you must use the solution described here, which proceeds in two steps: i) the first step is to find an initial solution then ii) in the second step, the optimal solution is found by iteratively improving the current solution until an optimal solution is reached.
Step 1: Minimum Cell Cost Method
The principle is simple, goods are first allocated through the least expensive route. In the example above, this is the route from Factory 3 to Warehouse A.
CSI 2120 page 2 _________________________________________________________________________________________________
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
(8)
(10)
30
Factory 2
(7)
(11)
(11)
40
Factory 3
40 (4)
(5)
(12)
50
The next allocation is made using the least expensive remaining route, knowing that Factory 3 has only 10 units left.
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
(8)
(10)
30
Factory 2
(7)
(11)
(11)
40
Factory 3
40 (4)
10 (5)
(12)
50
The process continues by identifying the next lower cost route by noting that Warehouse A has received all the goods requested (so the cells in the first column can no longer be used) and that Factory 3 has already committed all its goods (so cells in the last row can no longer be used). The next assignment is therefore:
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
10 (8)
(10)
30
Factory 2
(7)
(11)
(11)
40
Factory 3
40 (4)
10 (5)
(12)
50
Which only leaves the demand at warehouse C:
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
10 (8)
20 (10)
30
Factory 2
(7)
(11)
40 (11)
40
Factory 3
40 (4)
10 (5)
(12)
50
CSI 2120 page 3 _________________________________________________________________________________________________
When all the goods of the factories have been assigned to warehouses, an initial solution is found. However, this solution is not optimal. Some roads are not used. The second step is therefore to determine whether the use of these unused roads would reduce the total cost of transportation.
Step 2: Stepping-stone Method
To determine if an unused route would be more beneficial, one needs to calculate its cost of use. Let us first consider the route from Factory 1 to Warehouse A (1-A) of the previous solution and calculate what it would cost to transport a unit by this route. If a unit was to be transported by this route from Factory 1 to Warehouse A, then a unit from Plant 1 to another warehouse (either B or C) would have to be removed, since Factory 1 produces only 30 units. So let’s remove a unit from Route 1-B. This means that warehouse B loses a unit that will have to be moved by another road, say 3-B. In order to respect the production constraints of Factory 3, one unit must be removed from road 3-A. And since we have added a unit to warehouse A, we are in balance again. The re-routing of a unit as described is thus represented on our board:
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
+1 (6)
-1 10 (8)
20 (10)
30
Factory 2
(7)
(11)
40 (11)
40
Factory 3
-1 40 (4)
+1 10 (5)
(12)
50
This makes it possible to calculate the cost of this re-routing of one unit: +6-8+5-4 = -1. That means we save $ 1 for each unit redirected by that route. The ‘marginal cost’ of the 1-A route is therefore -1 considering the current solution.
Formally, the marginal cost of an unused road is calculated as follows: Starting from an empty cell, you have to jump to a non-empty cell on the same row. From this cell, we then move to a non-empty cell of the same column, then to a non-empty cell of the same row and so on until we fall back on the empty cell of departure and this without ever landing two times on the same cell. The cost is then calculated by alternating subtractions and additions along the route.
Next we calculate the marginal cost of cell 2-A, i.e., the cost of transporting one unit via this route. The sequence is a little more complex this time: 2-A, 2-C, 1-C, 1-B, 3-B, 3-A, 2-A.
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
-1 10 (8)
+1 20 (10)
30
CSI 2120 page 4 _________________________________________________________________________________________________
This gives the following marginal cost: +7-11+10-8+5-4 = -1, i.e., the same cost as before, so this route is also advantageous. Now let’s explore Route 2-B:
Factory 2
+1 (7)
(11)
-1 40 (11)
40
Factory 3
-1 40 (4)
+1 10 (5)
(12)
50
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
-1 10 (8)
+1 20 (10)
30
Factory 2
(7)
+1
(11)
-1 40 (11)
40
Factory 3
40 (4)
10 (5)
(12)
50
The marginal cost of Route 2-B is +11-11+10-8 = +2. This route is more expensive, so it will not be considered. The last unused route is Route 3-C.
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
(6)
+1 10 (8)
-1 20 (10)
30
Factory 2
(7)
(11)
40 (11)
40
Factory 3
40 (4)
-1 10 (5)
+1
(12)
50
The marginal cost of 3-C is +12-10+8-5 = 5. Only the first two roads are advantageous. We take one of them, for example 1-A (If these negative cost routes would not be equal, we would of course the route with the largest reduction in cost – the most negative value). One then assigns the maximum transport of units by this selected route:
Demand ►
Warehouse A 40
Warehouse B 20
Warehouse C 60
Production
▼
Factory 1
10 (6)
(8)
20 (10)
30
Factory 2
(7)
(11)
40 (11)
40
Factory 3
30 (4)
20 (5)
(12)
50
CSI 2120 page 5 _________________________________________________________________________________________________
This is a cheaper solution than the one initially found. We start again with the same procedure considering all empty cells and calculate the marginal cost. This continues until no new route can be found that result in a saving of transport costs.