Transportation

Transportation

LP problem formulation

Example

4 buyers (or destination): 1, 2, 3, 4

3 suppliers (or origin): A, B, C

Cost of transportation:

1 2 3 4 Supply

A 12 13 4 6 500

B 6 4 10 11 700

C 10 9 12 4 800

Demand 400 900 200 500

Objective -- to minimize total cost of transporting goods from suppliers to buyers such that all demands are met

LP formulation:

Let Xij: amount of goods shipped from supplier i to buyer j, where i=A, B, C and j=1, 2, 3, 4

Minimize C = 12X_A1+13X_A2+4X_A3+6X_A4+6X_B1+4X_B2+10X_B3+11X_B4+10X_C1+9X_C2+12X_C3+4X_C4

3 types of constraints:
1. Amount shipped cannot exceed what is available

X_A1+X_A2+X_A3+X_A4 <= 500

X_B1+X_B2+X_B3+X_B4 <= 700

X_C1+X_C2+X_C3+X_C4 <= 800

2. Demand must be met

X_A1+X_B1+X_C1 = 400

X_A2+X_B2+X_C2 = 900

X_A3+X_B3+X_C3 = 200

X_A4+X_B4+X_C4 = 500

3. Non-negativity

Xij = 0

Excel:
1. Set up the transportation grid.
2. Set up the solution grid.
3. Set up the cost grid.
4. Use Solver to find the optimal solution.

Special considerations
1. Solving maximization problem (e.g., maximizing profit)

2. Total Supply > Total Demand
Add a dummy destination with 0 cost (any item sent to the dummy destination remains at the origin)

3. Total Demand > Total Supply
Add a dummy origin with 0 cost (any supply allocated from the dummy origin represents unfilled demand)

4. Unacceptable routes
Assign a sufficiently high cost

5. Must-use routes
Assign a sufficiently low cost

Exercise:
Pg. 387, Problems 3, 4