One redundant equation in linear program?

Question

Consider the general linear programming formulation of the transportation problem (see Table 8.6). Verify that the set of $(m+n)$ functional constraint equations $(m$ supply constraints and $n$ demand constraints) has one redundant equation, i.e. any one equation can be reproduced from a linear combination of the other $(m+n-1)$ equations.

The table 8.6 is

and the solution is

though I don't understand it.

Why each constraint column will have exactly two nonzero entries?

If we multiply by $-1$ the demand constraints then I can see where the $-1$ comes from but not the $+1.$

I don't see the conclusion since the total supply equals the total demand. Hence, there is a redundant constraint neither .

Could someone please help me to understand?

thank you.

Answer 1

Why each constraint column will have exactly two nonzero entries?

In the following picture I have multiplied all demand constraints with $-1$, and highlighted one column. Indeed there is one +1 and one -1.

I don't see the conclusion since the total supply equals the total demand. Hence, there is a redundant constraint neither .

This is another way to say it: if you add all constraint rows except for the very last one (in the picture in this post), almost all +1/-1 cancel out and you end up with the last demand constraint (times negative 1).