Linear Programming

Author: Dr. Jean-Paul Rodrigue

---

1. Method

Linear programming aims at minimizing an objective linear function subject to a set of constraints. This methodology has a wide array of applications. For transportation problems, it involves an assignment that considers several origins and destinations with the goal to optimize a solution at minimal cost by minimizing transport costs with fixed origins and destinations. It considers linear transport costs, known surpluses (origins), demands (destinations), and possible paths. Linear programming consequently has a lot of relevance in the field of logistics, as it enables to assess an optimal distribution system that can help setting or improving a real-world distribution system. The linear programming formulation for a distribution problem is basically expressed as:

Where Q(a,b) is the traffic between origin a and destination b and g is a cost function. So g(Q(a,b)) is the transport cost related to traffic Q(a,b). The goal of this equation is to minimize the summation of transport costs of each origin-destination pair. The traffic of each pair must be superior of equal to 0 (rule of non-negativity).

2. Problem

The manager of a distribution system between factories (A, B and C) and distributors (W, X, Y and Z) wishes to minimize the global transport costs between a set of origins (factories) and destinations (distributors). Consider the following two matrices; the supply matrix:

Factories having surpluses	Supply
A	400
B	1500
C	900
Total	2800

And the demand matrix:

Distributors having demands	Demand
W	700
X	600
Y	1000
Z	500
Total	2800

It is worth mentioning that the amount of units produced and demanded is the same, implying a market equilibrium. Any supplementary unit produced will not be transported because there is no supplementary demand and any supplementary demand will not be transported because there is no supplementary supply. We also have the transport cost matrix between factories and distributors in dollars per unit transported:

Costs	W	X	Y	Z
A	20	40	70	50
B	100	60	90	80
C	10	110	30	200

For instance, it costs $20 to transport 1 unit from factory A to distributor W. This problem can be represented as a graphic form where each factory and distributor is a node and where each transport cost pair is a vector between a factory and a distributor.

3. Heuristic Solution

With the data provided, linear programming will determine the traffic assignment having the minimal transport cost. This problem can be solved for instance using the "Solver" add-in in the Excel spreadsheet. Below is the heuristic method where relatively simple problems (grids of about 5 by 5) can be solved "by hand" in several stages:

1. Cost Ranking

Order the transport costs for each cell by beginning by the lowest, which has a rank of 1, to the highest. Assign the same rank to cells having equal costs.

	W	X	Y	Z
A	2	4	7	5
B	10	6	9	8
C	1	11	3	12

2. Traffic Assignment

Take the cell having the lowest transport cost. In this case, it is the C-W cell ($10 per unit). Assign the highest possible number of units on this cell. Subtract this number from the number of surpluses and demands for the respective row and column. Continue the same procedure by order of rank until all surpluses are used and all demands are answered (origins and destinations having 0). The result is the following assignment matrix:

	W	X	Y	Z
A		400			400
B		200	800	500	1500
C	700		200		900
	700	600	1000	500	2800

3. Global Transport Cost

Calculate the transport costs of this assignment by multiplying the traffic of each cell by its cost (transport cost matrix).

	W	X	Y	Z
A		16,000			16,000
B		12,000	72,000	40,000	124,000
C	7,000		6,000		13,000
					153,000

The transport cost of this assignment is $153,000.

4. Estimation Costs Matrix

To find if this assignment is the least cost distribution you must calculate the estimation costs matrix. This process is stepwise. First, write down the transport cost per unit in each cell that is used. Second, put a value of 0 to the summation of the first row. Third, use the values in row 1 for the summation of each column. Fourth, for the summation of succeeding rows enter the difference between 'column 1, row 1' and 'column 1, row n' where 'n' is the number of the current row'. Fifth, fill the empty cells such as each cell must be the summation of the values at the extremity of their respective rows and columns.

	W	X	Y	Z
A	50	40	70	60	0
B	70	60	90	80	20
C	10	0	30	20	-40
	50	40	70	60

5. Cost Comparison

Compare the estimation costs matrix with the transport cost matrix. There can be only two alternatives.

• First, that the estimation costs are higher than the real costs. The solution is not optimal.  A readjustment is thus necessary.
• Second, the estimation costs are equal or smaller than the real costs. No readjustments are necessary and the optimal solution is found.

In this example, cell A-W has higher estimation costs (50) than real costs (20). Cell A-Z has also higher estimation costs (60) than real costs (50). It is not an optimal solution. A readjustment will thus be necessary.

6. Readjustment Cell Selection

If a readjustment is necessary, choose the cell that has the highest difference between its estimation and real costs. If two cells have equal differences, choose the cell that has the smallest real costs. In this example, it is cell A-W having a difference of 30. Cell A-Z has a difference of only 10.

7. Readjustments

Readjustments are done by transferring values between cells. They are performed according to three rules.

• First, transfers are done along a circuit from an unused cell and by altering vertical and horizontal stages and by only using occupied cells.
• Second, each transfer is the exact opposite value of the other.
• Third, the value of a transfer is determined by the maximum value that all cells could subtract while still respecting the supply and demand.

	W	X	Y	Z
A	(+400)	400 (-400)			400
B		200 (+400)	800 (-400)	500	1500
C	700 (-400)		200 (+400)		900
	700	600	1000	500	2800

400 is the highest readjustment possible in cell A-W because cell A-X cannot subtract more. The new traffic assignment matrix is consequently:

	W	X	Y	Z
A	400				400
B		600	400	500	1500
C	300		600		900
	700	600	1000	500	2800

8. Global Transport Costs

Calculate again the costs related to this distribution (as in point 3).

	W	X	Y	Z
A	8,000				8,000
B		36,000	36,000	40,000	112,000
C	3,000		18,000		21,000
					141,000

The transport cost of this new assignment is $141,000, which is lower than the initial figure of $153,000.

9. Estimation Costs Matrix

Calculate again the estimation costs matrix (as in point 4).

	W	X	Y	Z
A	20	10	40	30	0
B	70	60	90	80	50
C	10	0	30	20	-10
	20	10	40	30

10. Costs Comparison

No cell has estimation costs higher than real costs. The solution is thus optimal ($141,000 is the minimal cost) and can be represented as a graphic form.