Transportation Problem Notes

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 

Buy the full version of these notes or essay plans and more in our Mathematical Programming Notes.