Transportation and Assignment Models

A transportation problem is a linear optimization problem, which seeks to minimize the total costs of shipment of items from certain origins to a number of destinations while fulfilling the requirements of destinations and emptying the origins.

The solution of a transportation model follows the steps that the simplex method offers:

1. Determine a basic feasible solution to initiate,

2. Check the optimality of the basic feasible solution as the simplex method does. If it is not, optimal, then move to the next step. If optimal, stop.

3. Iterate to the next basic feasible solution by determining the entering and leaving variable using the rate of improvement on the objective value. Return to step 2.

A linear program can be related to another one reflecting the opposite of itself. These two programs have the same conditions (cost and constraint coefficients), yet they are modeled from counter-viewpoints. Consequently, they reach the same optimal solution mutually. Here, the inversed pair of the original model is called the dual of the original (or primal) model.

The dual model interchanges costs and constraints of the primal model, and converts the objective from maximization to minimization. Moreover, the values of the decision variables of the dual model reveal the prices for the constraints of the original problem for a basic feasible solution. This interpretation provides an economic perspective for solving the primal problem. Combining this economic insight and the properties of duality allows for an easier method altering the regular version of the simplex algorithm for the solution of a balanced transportation model.

Strong duality property refers that the objective value of Z and the objective value of W are equal only if the basic feasible solution is the optimal for the primal as well as the dual model. In the equation below, the asterisk denotes that x and y are the optimum feasible solutions. 

This property allows checking for the optimality of the primal solution by inspecting the feasibility of its dual solution.

The duality properties of a linear model allow determining a basic feasible solution being optimal or not. The process here, the optimality test, is to check the feasibility of the dual solution of a basic feasible solution for the primal model.

The solution of a transportation model follows three steps to reach the optimum. First step is to determine a basis, which is the initial basic feasible solution. There are various ways to initialize the solution process; the notable ones will be introduced in following subsection. The next step is to check the optimality of the solution. The third step is conditional to the second: if the current solution is not optimal, then the process is to iterate to a new basic feasible solution that includes the entering variable determined in the previous step.

A balanced transportation model is a transportation model, where the supply and demand constraints are equal, and the total supply equals total demand.

The first basic variable is the one that is at the northwest on the transportation tableau. The value allocated to this variable is the value of the smaller one of the supply and demand. If the respective origin has any supply remaining after the allocation, then move one column to the right and allocate the value in the same manner as the first one. Otherwise, move one row down and repeat the allocation process with the remaining demand. The process is finalized when there is nothing left to allocate at the last row.

A basic variable with a value of zero is called degenerate basic variable, and the term “degenerate” is applied to the basic feasible solution as well.

The Least-cost method considers the respective costs of the variables so as to find a basic feasible solution that approximates the optimum solution more. Unlike the Northwest Method, the Least- cost algorithm begins with selecting the route that has the smallest unit cost of transportation. If there is more than one variable that has the smallest cost, any variable among these can be selected arbitrarily. The value allocated to the selected route is the greater one of the values of the supply and demand. The satisfied column (corresponding demands) or row (corresponding supplies) is masked out with grey and ignored for the next allocations. Next, subtract the allocation value from the supply and demand and repeat the same allocation process with the remainders of the supply and demand. The process continues until the last row or column is satisfied.

Vogel’s approximation method (VAM) can be regarded as an improved version of the least-cost method. Instead of using the direct cost of the transportation, VAM utilizes the concept of the penalty cost. Each row or column has its own penalty cost, which is used for determining which variables are the basic ones. A penalty cost is the difference between the smallest cost of a row (or column) and the cost that is smaller than the others except the smallest one for that row (or column).

MODI determines whether a basic feasible solution is optimal or not, and if not, identifies the entering variable by following these steps:

1. Denote the simplex multipliers, ui for each row and vi for each column alongside the transportation tableau

2. Write down the equations ui + vi = cij for each basic variable xij

3. Set one of the multipliers to zero and find the values of other multipliers on this system of equations

4. Calculate the values of cij – (ui + vi) for each non-basic variable

5. If any of these values is greater than or equal zero, then the solution is optimal

6. If not, the non-basic variable that has the most negative value is the entering variable

It is also known as the method of simplex multipliers or the u-v method, MODI is a tailored version of the simplex method for the transportation model.

If the initial basic feasible solution is not optimal, the method iterates to the next basic feasible solution. The entering variable was identified in the previous step. In the iteration process, the entering variable will be interchanged with an existing basic variable called leaving variable. The iterative solution is obtained by a chain reaction occurring when the new variable becomes basic. After a sequence of value updates beginning from the entering variable and moving to the existing basic variables, one of the basic variable that decreased to zero is, now, a non-basic variable and therefore, it is “the leaving variable”.

The decision variables of an assignment model can only take a value of either one or zero.

The solution method of the assignment model is called the Hungarian Method, named by the nationality of its developers.

The steps of Hungarian Method is given below.

1. Identify the smallest value of each row for the cost matrix of the assignment problem. Subtract each row’s smallest value from all the costs in the respective row.

2. Identify the smallest value of each column for this altered matrix. Subtract each column’s smallest value from all the costs in the respective column.

3. Mask the columns and rows out that have a zero value. The number of masked out rows and columns must be at a minimum.

4. If the number of masked out rows and columns is equal to n, then the optimum can be obtained from the present matrix; move on to the next step. If not, skip to Step 6.

5. Identify the optimal solution by the coordinates of the zero-valued elements in the present matrix.

6. Identify the smallest value except for the ones in masked out rows and columns. This value is then subtracted from the values of unmasked rows and columns and, added to the intersections of masked out rows and columns. Return to Step 3.