> my question is generally the same one, which was asked on this group
> some time ago:
> ------------------
> I have a little problem understanding the
> MODI method for solving the transportation
> problem and I hope somebody can help me with it.
> The MODI method regards the dual problem
> to the transportation problem with variables
> u_i (i=1,...,m) and v_j (j=1,...,n) corresponding
> to the offer and demand constraints in the primal
> (transportation) problem. In the dual problem,
> the constraints are u_i + v_j <= c_ij, where
> c_ij are the unit transportation costs from
> place i to place j. Regarding a feasible basis
> solution to the transportation problem, the MODI
> method computes the possible cost decrease of
> any non-basis variable by first solving
> u_i + v_j = c_ij for any basis variable x_ij,
> and then computing c_ij - u_i - v_j as the
> possible cost reduction for any non-basis
> variable x_ij. But assuming u_i + v_j = c_ij
> means that the complementary slackness conditions
> hold for the pair of solutions for the primal
> and the dual problem. But since the primal
> solution generally is not optimal at first, i.e.
> after applying some heuristic to gain a starting
> solution, I wonder why that assumption makes sense.
> -------------

> With the following answer:
> ------------
> Suppose that you were to solve the primal problem using the simplex
> method.  The reduced cost of every basic variable is zero, even though
> the current basic feasible solution is suboptimal (until the last
> iteration).  If we denote the constraint matrix and objective
> coefficient vector by A and c respectively, and let B be the basic
> submatrix of A (with inverse Binv) and c_B be the basic subvector of
> c,
> then the reduced cost vector is c'-y'A, where y'=c_B'Binv is a
> superoptimal solution to the dual (feasible, and hence optimal, in the
> final iteration).

> In the case of the Hitchcock (transportation) problem, it's relatively
> easy to show that the reduced cost of any variable X_ij is c_ij - u_i
> -
> v_j, so the MODI method uses the fact that the reduced cost of basic
> variables must be zero to solve for u and v.

> Note that complementary slackness *plus feasibility* implies mutual
> optimality.  In intermediate stages of the MODI method, the dual
> solution is infeasible (u_i + v_j > c_ij for some x_ij, one of which
> will enter the basis at the next iteration), so there is no
> contradiction to the current primal solution being suboptimal.
> ----------

> After reading that answer, my questions are:
> Why do we need complementary slackness at all?
>       -> We can compute the u_i, v_j through the equation for reduced
> costs of basic variables?
>                c_ij - u_i - v_j = 0 for x_ij in basis
>       -> Solution is optimal iff no x_ij has reduced costs < 0
>     And that would be all we want to know.

> /Paul

> I know that for an optimal Basis B, the dual solution is just c_B^T
> B^-1
> but why does the interpretation of y = c_B^T B^-1 make sense for a non
> optimal basis?
> Or in other words, which is the meaning of  y = c_B B^-1 for a non
> optimal basis?

> > /Paul

> Then, hopefully, my final question is:
> Why does the reduced costs compute to c_ij - u_i - v_j

> I guess the answer is somewhere close to the following considerations:

> The vector of reduced costs is
>      c^T - c_B^T B^-1 A
> for every solution x to the primal problem (optimal or not)
> and we somehow can interprete c_B^T B^-1 as the values for the dual
> variables y
> so we can compute y , e.g. the u_i, v_j values, by solving
>      c_ij - u_i - v_j = 0 for basisvariables x_ij (as they have
> reduced costs = 0)

> I know that for an optimal Basis B, the dual solution is just c_B^T
> B^-1
> but why does the interpretation of y = c_B^T B^-1 make sense for a non
> optimal basis?
> Or in other words, which is the meaning of  y = c_B B^-1 for a non
> optimal basis?

> Thanks for helping