Transformation Algorithms - Linear Programming Models

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 ...