Oxbridge Notes

Transportation Problem Revision

Lecture 9: Transportation Problem

Topics Reading Key Points
• Transport formulation • Formulating transportation problems
• Redundant constraint
• Dummy sources and destinations
• More graph theory
• Feasibility • Redundant constraints
• Optimality • Tree graphs
• Moving to another solution • Vertex-arc incidence matrices
• Finding an initial solution • Feasibility of proposed solutions
• Steps of the transport algorithm
• Optimality checking
• Example
• Multiple optimal solutions • Calculating dual values
• Degeneracy • Non-basic variables
• Optimality using cost matrix
• Moving to another solution
• North-west corner rule
Transport Formulation • Least-cost method
• Transport Problem = Given m sources of a homogeneous commodity and n destinations for it with known
• Interpretation of dual values of non-basic variables
quantities of supply and demand, given the cost of transport from each source to each destination, find the
pattern of distribution from sources to destinations which will minimise total transport cost • Degeneracy
• The formulation assumes that the total available amount is equal to the total amount required
○ We can create a dummy source or destination if this is not the case Definitions
 This will have zero cost provided there is no penalty • North-West Corner Rule = A simple method to obtain a first solution of a TP by
selecting the cell in the north-west corner of the matrix, and assigning it the minimum
Example of a transportation formulation of the amount required by destination 1 and the amount available at source 1
• Transport Problem = Given m sources of a homogeneous commodity and n
destinations for it with known quantities of supply and demand, given the cost of
transport from each source to each destination, find the pattern of distribution from
sources to destinations which will minimise total transport cost
• Tree = A graph with n vertices and n-1 arcs which is connected, so that ignoring the
direction of the arcs, it is possible to go from every vertex to every other

Formulae
•
•
• Dual of the destination - Dual of the source = Cost of the route
• Dual value = dual of the destination - dual of the source - cost of the route

• Each column has two non-zero elements, a -1 and a +1
○ In column , the -1 is in the row associated with source i
○ The +1 is in the row associated with destination j
○ This property is true for all transportation problems

Redundant Constraint
• The formulation has m+n equality constraints
○ Because total supply = Total demand
○ This means one of the equality constraints is redundant
• If any one of the constraints were to be deleted from the formulation, then any feasible solution satisfying the
remaining constraints would necessarily satisfy the deleted constraint
○ ∴ there are only m+n-1 independent constraints

More Graph Theory
• Tree = A graph with n vertices and n-1 arcs which is connected, so that ignoring the direction of the arcs, it is
possible to go from every vertex to every other

Example of a tree graph

•

• A way of representing a directed graph is by a vertex-arc incidence matrix
○ The rows of the matrix correspond to the vertices
○ The columns of the matrix correspond to the arcs

Example of a vertex-arc incidence matrix

Course Notes Page 16

****************************End Of Sample*****************************

Buy the full version of these notes and essays alongside much more in our Mathematical Programming Notes.

Related Mathematical Programming Samples:

• Minimalism Notes
• Transportation Problem Notes