###### Operational Research Notes > Lse Operational Research Notes > Mathematical Programming Notes

# Transportation Problem Notes

This is a sample of our (approximately) 6 page long **Transportation Problem** notes, which we sell as part of the **Mathematical Programming Notes** collection, a 1st Class package written at LSE in 2011 that contains (approximately) ** 42 pages** of notes across **10 different documents.**

### Transportation Problem Revision

* The following is a plain text extract of the PDF sample above, taken from our Mathematical Programming Notes. This text version has had its formatting removed so pay attention to its contents alone rather than its presentation. The version you download will have its original formatting intact and so will be much prettier to look at.*

Lecture 9: Transportation Problem Topics

• Transport formulation

• Redundant constraint

• More graph theory

• Feasibility

• Optimality

• Moving to another solution

• Finding an initial solution

• Steps of the transport algorithm

• Example

• Multiple optimal solutions

• Degeneracy

Reading

Key Points

• Formulating transportation problems

• Dummy sources and destinations

• Redundant constraints

• Tree graphs

• Vertex-arc incidence matrices

• Feasibility of proposed solutions

• Optimality checking

• Calculating dual values

• Non-basic variables

• Optimality using cost matrix

• Moving to another solution

• North-west corner rule

Transport Formulation

• 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

• 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

This will have zero cost provided there is no penalty

Example of a transportation formulation

• Least-cost method

• Interpretation of dual values of non-basic variables

• Degeneracy Definitions

• 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 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 or essay plans and more in our Mathematical Programming Notes.*