Compute the Dual Variables

The dual variables are associated with the rows and columns of the tableau. They are assigned so that the reduced costs of all basic cells are zero.

The formula for the reduced cost is

d(i,j) = c(i, j) - u(i) - v(j).

In this formula, i is the index of the row and j is the index of the column. c(i, j) is the cost for the cell. u(i) and v(j) are the dual variables associated with row i and column j. This notation as well as the complete algorithm are discussed in the textbook.

One of the dual variables is arbitrary and we assign that one the value of zero. For the case shown, we have assigned the 0 value to v(3). Given the first assignment it is always possible to assign the others based on the requirement that the reduced costs for basic cells are 0. Once v(3) is assigned, then the values of u(3) and u(4) are determined by the expressions:

u(3) = v(3) + c(3,3) = 8

u(4) = v(3) + c(4,3) = 9.

The computer computes the dual values and shows them to the right and below the tableau.

The basic cells all have d(i,j)= 0, but the other cells take on positive or negative values. The condition for optimality for the transportation problem is that all cells must have nonnegative reduced costs. This is clearly not true for the tableau shown in the figure, because the solution is not optimum.

The next article describes how to select a cell to enter the basis.