MA205-Chapter5(5-1)

The Transportation Problem Overview

• A Transportation Problem (TP) involves the distribution of a commodity from multiple supply points to multiple demand points.

Example Problem: PowerCo

Problem Setup

• PowerCo has three electricity generating plants to serve four cities.

• Plant Capacities:

  • Plant 1: 35 million kWh

  • Plant 2: 50 million kWh

  • Plant 3: 40 million kWh

• City Demands:

  • City 1: 45 million kWh

  • City 2: 20 million kWh

  • City 3: 30 million kWh

  • City 4: 30 million kWh

Transmission Costs

• Cost of transmitting one million kWh from plants to cities:

  • From Plant 1:

    • City 1: $8

    • City 2: $6

    • City 3: $10

    • City 4: $9

  • From Plant 2:

    • City 1: $9

    • City 2: $12

    • City 3: $13

    • City 4: $7

  • From Plant 3:

    • City 1: $14

    • City 2: $9

    • City 3: $16

    • City 4: $5

Formulation of the Problem

• Decision Variables: Let (X_{ij}) be the power shipped from Plant i to City j.

Supply Constraints:

• (X_{11} + X_{12} + X_{13} + X_{14} \leq 35) (Plant 1)

• (X_{21} + X_{22} + X_{23} + X_{24} \leq 50) (Plant 2)

• (X_{31} + X_{32} + X_{33} + X_{34} \leq 40) (Plant 3)

Demand Constraints:

• (X_{11} + X_{21} + X_{31} \geq 45) (City 1)

• (X_{12} + X_{22} + X_{32} \geq 20) (City 2)

• (X_{13} + X_{23} + X_{33} \geq 30) (City 3)

• (X_{14} + X_{24} + X_{34} \geq 30) (City 4)

Objective Function

• Minimize the total cost: [ Z = 8X_{11} + 6X_{12} + 10X_{13} + 9X_{14} + 9X_{21} + 12X_{22} + 13X_{23} + 7X_{24} + 14X_{31} + 9X_{32} + 16X_{33} + 5X_{34} ]

Optimal Solution

• Example optimal values:

  • (X_{12} = 10, X_{13} = 25, X_{21} = 45, X_{23} = 5, X_{32} = 10, X_{34} = 30)

• Total cost: (Z = 1020)

General Description of a Transportation Problem

• Components of TP:

  • Supply Points: m supply points with maximum supply (s_i)

  • Demand Points: n demand points requiring at least (d_j)

  • Cost: Cost (C_{ij}) per unit shipped from supply point i to demand point j.

Mathematical Formulation of TP

• Objective: [ min , Z = \sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} X_{ij} ]

• Subject to:

  • Supply constraints: ( \sum_{j=1}^{n} X_{ij} \leq s_i, \forall i )

  • Demand constraints: ( \sum_{i=1}^{m} X_{ij} \geq d_j, \forall j )

  • Non-negativity constraints: ( X_{ij} \geq 0 )

Balancing Transportation Problems

Excess Supply

• When total supply exceeds total demand, create a dummy demand point.

• Costs to dummy point are set to zero.

Excess Demand

• When total demand exceeds total supply, create a dummy supply point.

• Assign penalty costs for unmet demand.

Examples

1. Balanced TP Formulation example with customer demands and warehouse supplies.

2. Purchasing Medicine for a hospital under supply restrictions.

3. Government Auction of land leases with bidder capacity limits.

4. Auditors Allocation to projects maximizing profit based on available hours.