# Transformation Algorithms - Linear Programming Models

Problem:

This question involves formulating a linear programming model a transportation problem where demand exceeds supply. The question has four parts: (a) to (d).

Please see the attachment for full details of the question.

a) Write down a linear programming model of the transportation problem in the case when demand exceed supply.

b) Describe an algorithm to find the closed path of stepping-stones required by the transportation algorithm.

c) Apply Vogel's rule to the following transportation problem and then perform ONE iteration of the transportation algorithm. State the resulting basic feasible solution and whether or not it is optimal.

See attachment for table

d) Write down three advantages the transportation algorithm has over the Simplex method for solving Transportation problems.

#### Solution Preview

(a). MODEL

Lest us assume sources are S1, S2, S3, ..., Sm which supply s1, s2, s3, ..., sm units to Destinations D1, D2, D3, ..., Dn of which demands are d1, d2, d3, ..., dn.

if S1 supplies x11, x12, x13, ..., x1n units, S2 supplies x21, x22, x23, ..., x2n units, ..., Sm supplies xm1, xm2, xm3, ..., xmn units to D1, D2, D3, ..., Dn destinations respectively such that:

For supply less than demand,

s1 + s2 + s3 + ... + sm < d1 + d2 + d3 + ... dn

To balance, the unsatisfied demand , add a dummy source Sz. Let us assume Sz supplies xz1, xz2, xz3, ..., xzn units to D1, D2, D3, ..., Dn destinations, with zero costs.

Hence,

s1 + s2 + s3 + ... + sm + sz = d1 + d2 + d3 + ... dn

x11 + x12 + x13 + ... + x1n = s1

x21 + x22 + x23 + ... + x2n = s2

...

xm1 + xm2 + xm3 + ... + xmn = sm

xz1 + xz2 + xz3 + ... + xzn = sz

And,

x11 + x21 + x31 + ... + xm1 + xz1 = d1

x12 + x22 + x32 + ... + xm2 + xz2 = d2

...

x1n + x2n + x3n + ... + xmn + xzn = dn

If costs of supply from ith source to jth destination is cij/unit, then function

S = sum(i=1,m; j = 1,n) (cij * xij) [Note: czj = 0]

Objective is to find non-negative values of xij such that function S is minimized.

(b). ALGORITHM

1. Determine an initial basic feasible solution using a method like Vogel Approximation Method.

2. Make sure number of occupied cells is exactly = m+n-1, where m = number of rows and n = number of columns.

3. Select an unoccupied cell. Beginning at this cell, trace a closed path, starting from the selected unoccupied cell until finally returning to that same unoccupied cell.

4. Assign plus (+) and minus (-) signs alternatively on each corner cell of the closed path just ...

#### Solution Summary

Vogel's rule linear programming method applied to solve a transportation problem.Also, linear programming model for demand exceeding supply, algorithm of closed path o stepping-stones, comparison of simplex and transportation algorithms are described.