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