Chapter 6: Transportation and Assignment Models

Introduction

The foundation of the Simplex algorithm is a comprehensive approach from which various solution methods are derived from its conceptual properties. These derivations mitigates the burden of hand-processing of the original algorithm for defined types of linear programs, such as the transportation and the assignment models. Introducing these solution methods will improve the understanding of the Simplex Method and its properties.

The Transportation Model

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.

Duality, the Concept and the Properties

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.

Optimality Test for the Transportation Model Using the Properties of Duality

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. According to the explanations in the previous subsection, this process is also applicable to a transportation model. Furthermore, it takes less computational effort when it is applied to a basic feasible solution of a balanced transportation model.

The Solution Method for The Transportation 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 equality, and the total supply equals total demand. Therefore, the model is modified with a slack variable that is a dummy destination representing the number of truckloads remained in stocks. The transportation costs related to the dummy destination are zero, as the amounts allocated to this artificial destination are not transported physically.

Initialization Methods

The solution of a transportation problem begins with determining a basic feasible solution to proceed to the next phase. A balanced transportation problem has m + n – 1 basic variables in its basic feasible solution, whereas the number of the constraint equations is m + n. Therefore, one of the basic variables can be selected arbitrarily. The remainders are selected according to the arbitrary selection of the first one. Selecting a variable to be basic means allocating the greatest value possible to the respective variable, under the constraints of the total supply and demand for the origins and destinations, respectively. There are various methods for selecting an arbitrary variable; the most prominent ones are:

1. Northwest corner method
2. Least-cost method
3. Vogel’s approximation method

Northwest Corner Method: 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.

In a degenerate basic feasible solution, a degenerate basic variable acts as a non-basic variable, however, it does not prevent reaching to the optimal.

Least-cost Method: 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: 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).

To select a variable as the basic, first, determine the row or column having the largest penalty cost. Then, select the variable with the smallest unit cost of transportation in this row (or column). If there are more than one penalty costs sharing the largest value among the rows and columns, then select any of them. The same applies to the selection of the variable in the selected row or column. Allocate to the selected variable the value of the one that is greater among the supply and demand. Recall that the supply and the demand are the values at the right end of the row and the bottom end of a column, respectively.

The rest of the method is the same as the least-cost method. The allocation process is repeated with the remainders of the supply and demand from the previous allocation. If the allocation satisfies the corresponding demand (consumes the corresponding supply), the column (the row) is masked out with grey and ignored for the next allocation. The process continues until the last row or column is satisfied.

Test for Optimality

Testing the optimality of the initial basic feasible solution can be facilitated by the duality properties of the transportation model. Basics of such an application was explained thoroughly in a designated subsection before introducing the solution methods of the transportation model. Here, the application is presented as a standalone method called the Modified Distribution Method (MODI). Also known as the method of simplex multipliers or the uv method, MODI is a tailored version of the simplex method for the transportation model. 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 u _i + v _i = c _ij for each basic variable x _ij
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 c _ij – (u _i + v _i ) for each nonbasic 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

Iteration

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 Solution Method for the Assignment Model

The term “Assignment” refers to the case of job allocations to a group of workers. In general, a worker has a single job and a job is done by a single worker. Similarly, the assignment model has the origin locations from where a single unit can be transported to a dedicated destination, and vice versa—the model has the destinations to which a single unit is sent solely from one origin location. Simply put, the number of the origins (represented by the workers) and the destinations (represented by the jobs) are equal, and the amount to be sent and received is strictly 1.

The assignment model has a tailored solution method such as the transportation model does. 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. I
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.