Question

For the standard transportation linear program with m sources and n destinations and total supply equaling total demand, an optimal solution (lowest cost) with the smallest number of non-zero $x_{ij}$ values (amounts from source i to destination j) is desired. The best upper bound for this number is

• A. 2(m + n)
• B. m + n - 1
• C. mn
• D. m + n

Answer 1

The correct option is B m + n - 1

$\text{Degeneracy arises if number of allocation are less than m + n - 1}$