Transportation problems

Transportation problems

Transportation problems arise when a product is distributed from several sources (e.g., factories or warehouses) to several destinations (e.g., customers or outlets), with the goal of minimizing the total transportation cost.

Key concepts

1. Source (Supply): A location from which products are sent.
2. Destination (Demand): A location where products are needed.
3. Balanced Problem: Total supply = total demand.
4. Unbalanced Problem: Total supply ≠ total demand (must be adjusted).

The transportation problem is a type of linear programming problem designed to minimize the cost of shipping from sources to destinations.

Formulating a transportation problem

Case 1: Two sources and two destinations

Suppose:

• Source $P$ has $k$ units
• Source $Q$ has $h$ units
• Destination $A$ needs $a$ units
• Destination $B$ needs $b$ units

Let the decision variables be:

• $x$: units transported from $P$ to $A$
• $y$: units transported from $P$ to $B$
• $a - x$: units from $Q$ to $A$
• $b - y$: units from $Q$ to $B$

Case 2: Two sources and three destinations

Suppose:

• Source $P$ has $k$ units
• Source $Q$ has $h$ units
• Destination $A$ needs $a$, $B$ needs $b$, and $C$ needs $c$ units

Let the decision variables be:

• $x$: from $P$ to $A$
• $y$: from $P$ to $B$
• $z$: from $P$ to $C$
• $a - x$: from $Q$ to $A$
• $b - y$: from $Q$ to $B$
• $c - z$: from $Q$ to $C$

These variables help us create the constraints to ensure that the total supply from each source is not exceeded, and each destination receives its required demand.

Example

A manufacturer has two warehouses:

• Warehouse $H_1$: 80 units
• Warehouse $H_2$: 70 units

Customer demands:

• Customer $C_1$: 35 units
• Customer $C_2$: 60 units

Transportation cost table (Tanzanian shillings):

From → To	$C_1$	$C_2$
$H_1$	80	100
$H_2$	120	130

Let:

• $x$: units from $H_1$ to $C_1$
• $y$: units from $H_1$ to $C_2$
• $35 - x$: units from $H_2$ to $C_1$
• $60 - y$: units from $H_2$ to $C_2$

Constraints

Supply constraints:

• $x + y \leq 80$
• $(35 - x) + (60 - y) \leq 70$

Demand constraints (automatically satisfied with the above setup):

• $x + (35 - x) = 35$
• $y + (60 - y) = 60$

Objective function

Minimize the total transportation cost:

$$\text{Cost} = 80x + 100y + 120(35 - x) + 130(60 - y)$$

This simplifies to a linear expression in $x$ and $y$ that can be minimized using linear programming techniques.

Transportation problems are structured and solvable using linear programming techniques such as:

• North-West Corner Method
• Least Cost Method
• Vogel's Approximation Method
• Simplex Method

Linear programming problems

1. Two printers N and T produce three types of books. N produces 80 types I books per day, 10 type II books per day and 20 types III books per day, while T produces 20 types I books per day 10 type II books per day and 70 types III books per day. The orders placed are 1600 type I, 500 type II and 2100 type III books. The daily operating costs for N shs. 10,000/=, for Tshs, 20,000/= how many days should each printer operate to meet the orders at a minimum cost.

2. A small textile company manufactures three different size of shirts, Large (L), medium (M) and small (S) at two different plants A and B. The number of shirts of each size produced and the cost of production per day are as follows!

	A	B	Monthly demand
Large size per day	50	60	2500
Medium size per day	100	70	3500
Small size per day	100	200	7000
Production Cost per day Tshs.	2500	3500	_

1. How many days per month should each factory operate in order to minimize total cost.
2. What is the minimum cost of production

Solution 1

Let $x$ be number of days printer N should operate

Let $y$ be number of days printer T should operate

Objective function

$f(x, y) = 10000x + 20000y$

Constraints

• $80x + 20y \geq 1600$
• $10x + 10y \geq 500$
• $20x + 70y \geq 2100$
• $x \geq 0$, $y \geq 0$

Equations

• $80x + 20y \geq 1600$

$80x + 20y = 1600$

$8x + 2y = 160$

When $x = 0$, $y = 80$

$y = 0$, $x = 20$

• $10x + 10y \geq 500$

$10x + 10y = 500$

$x + y = 50$

When $x = 0$, $y = 50$

$y = 0$, $x = 50$

• $20x + 70y \geq 2100$

$20x + 70y = 2100$

$2x + 7y = 210$

When $x = 0$, $y = 30$

$y = 0$, $x = 105$

Corner points	$F(x, y) = 10000x + 20000y$
A (0, 80)	10000 (0) + 20000 (80) = 1,600,000
B (28, 22)	10000 (28) + 20000 (22) = 720,000
C (105, 0)	10,000 (105) + 20000 (0) = 1,050,000

Printer N should be operated for 28 days and printer T should work for 22 days to meet the orders at minimum cost.

Solution 2

Let $x$ be number of days per month factory A should operate

Let $y$ be number of days per month factory B should operate

Objective function

$F(x, y) = 2500x + 3500y$

Constraints

• $50x + 60y \geq 2500$
• $100x + 70y \geq 3500$
• $100x + 200y \geq 7000$
• $x \geq 0$, $y \geq 0$

Minimize $f(x, y) = 2500x + 3500y$

Subject to $50x + 60y \geq 2500$

$100x + 70y \geq 3500$

$100x + 200y \geq 7000$

$x \geq 0$, $y \geq 0$

Equations

• $50x + 60y = 2500$

When $y = 0$, $x = 50$

$x = 0$, $y = 41.7$

• $100x + 70y = 3500$

When $y = 0$, $x = 35$

$x = 0$, $y = 50$

• $100x + 200y = 7000$

When $y = 0$, $x = 70$

$x = 0$, $y = 35$

Corner points	$F(x, y) = 2500x + 3500y$
A (0, 50)	2500 (0) + 3500 (50) = 175,000
B (15, 30)	2500 (15) + 3500 (30) = 142,500
C (20, 25)	2500 (20) + 3500 (25) = 137,500
D (70, 0)	2500 (70) + 3500 (0) = 175,000

Factory A should operate for 20 days and factory B should operate for 25 days in order to minimize total cost.

Minimum cost of production is 137,500

3. In a certain garage the manager had the following facts floor space required for a saloon is 2m2 and for a lorry is 3m2. Four technicians are required to service a saloon car and three technicians for a lorry per day. He has a maximum of 24m2 of a floor space and a maximum of 36 technicians available; in addition he is not allowed to service more Lorries than saloon cars. The profit for serving a saloon car is 40,000/= and a lorry is 60,000/=. How many motor vehicles of each type should be serviced daily in order to maximize the profit?

Solution

Let $x$ be number of saloon cars to be serviced daily

Let $y$ be number of lorries to be serviced daily

Objective function

$F(x, y) = 40000x + 60000y$

Constraints

• $2x + 3y \leq 24$
• $4x + 3y \leq 36$
• $x \geq y$
• $x \geq 0$ and $y \geq 0$

Maximize $f(x, y) = 40000x + 60000y$

Subject to $2x + 3y \leq 24$

$4x + 3y \leq 36$

$x \geq y$

$x \geq 0$ and $y \geq 0$

Equations

• $2x + 3y \leq 24$

When $x = 0$, $y = 8$

$y = 0$, $x = 12$

• $4x + 3y \leq 36$

When $x = 0$, $y = 12$

$y = 0$, $x = 9$

• $x = y$

Corner points	$F(x, y) = 40000x + 60000y$
A (0, 0)	40000 (0) + 60000 (0) = 0
B (4.8, 4.8)	40000 (4.8) + 60000 (4.8) = 480,000
C (6, 4)	40000 (6) + 60000 (4) = 480,000
D (9, 0)	40000 (9) + 60000 (0) = 360,000

6 saloon cars and 4 lorries should be serviced daily to maximize profit to 480,000/=

More example

A builder has two stores, one at S1 and the other at S2. He is building houses at P1, P2, and P3. He needs 5 tons of bricks at P1, 6 tons of bricks at P2 and 4 tons of bricks at P3. The stores contain 9 tons of bricks at S1 and 6 tons of bricks at S2. The transport cost per ton are shown in the diagram

To From	P1	P2	P3
S1	6/=	3/=	4/=
S2	4/=	2/=	6/=

How does the builder send his bricks at a minimum cost? What is the minimum overall cost?

Solution

Let the builder send $x$ tons of bricks from S1 to P1 and $y$ tons of bricks from S1 to P2

Then the transportation of bricks to P1, P2 and P3 will be as follow:

To From	P1	P2	P3
S1	x	y	9 - (x + y)
S2	5 - x	6 - y	4 -

The constraints are obtained as follows

• $x \geq 0$, $y \geq 0$
• $9 - (x + y) \geq 0$ i.e. $x + y \leq 9$
• $5 - x \geq 0$ i.e. $x \leq 5$
• $6 - y \geq 0$ i.e. $y \leq 6$
• $4 -$

The objective function:

$F(x, y) = 6x + 3y + 4(9 - x - y) + 4(5 - x) + 2(6 - y) + 6(4)$

Simplifying:

$F(x, y) = 6x + 3y + 36 - 4x - 4y + 20 - 4x + 12 - 2y + 24$

$F(x, y) = (6x - 4x - 4x) + (3y - 4y - 2y) + (36 + 20 + 12 + 24)$

$F(x, y) = -2x - 3y + 92$

Since we want to minimize, this is equivalent to maximizing $2x + 3y$, or we can rewrite as:

$F(x, y) = 4x + 3y + 38$

Minimize $f(x, y) = 4x + 3y + 38$

Subject to $x + y \leq 9$

$x + y \geq 5$

$x \leq 5$, $y \geq 0$

$y \leq 6$, $y \geq 0$

Equations

• $x + y = 9$

When $x = 0$, $y = 9$

$y = 0$, $x = 9$

• $x + y = 5$

$x = 0$, $y = 5$

$y = 0$, $x = 9$

• $x = 5$

• $y = 6$

Corner points	$F(x, y) = 4x + 3y + 38$
A (0, 5)	4 (0) + 3 (5) + 38 = 53
B (0, 6)	4 (0) + 3 (6) + 38 = 56
C (3, 6)	4 (3) + 3 (6) + 38 = 68
D (5, 4)	4 (5) + 3 (4) + 38 = 70
E (5, 0)	4 (5) + 3 (0) + 38 = 58

The builder should send the bricks of tons as follows:

To From	P1	P2	P3
S1	0	5	4
S2	5	1	0

The overall minimum cost is 53/=