Given the following feasible solution determine if the problem is degenerate and then find the optimal solution and its cost. Assume that capacity for source A is 10 and 30 for source B. Destination A demands 10 units while destination B demands 30 units. Cost of shipping per unit is given as AA ($4), AB ($1), BA ($3), and BB ($2).
$30\begin{array} { | l | c | c | } \hline & \text { Destination A } & \text { Destination B } \\\hline \text { Source A } & 10 & \\\hline \text { Source B } & & 30 \\\hline\end{array}$

Question

Given the following feasible solution determine if the problem is degenerate and then find the optimal solution and its cost. Assume that capacity for source A is 10 and 30 for source B. Destination A demands 10 units while destination B demands 30 units. Cost of shipping per unit is given as AA ($4), AB ($1), BA ($3), and BB ($2).

30\begin{array} { | l | c | c | } \hline & \text { Destination A } & \text { Destination B } \\\hline \text { Source A } & 10 & \\\hline \text { Source B } & & 30 \\\hline\end{array}

Ahmed H Mohammed · Accepted Answer

Final Answer :

The number of cells used should be 4 - 1 = 3, however only 2 cells are used. Thus the problem is degenerate. Students may then place a zero in either empty cell and proceed with the stepping-stone method to find an optimal solution of

1020\begin{array} { | l | c | c | } \hline & \text { Destination A } & \text { Destination B } \\\hline \text { Source A } & & 10 \\\hline \text { Source B } & 10 & 20 \\\hline\end{array}

This solution has a total cost of 10 * 3 + 10 * 1 + 20 * 2 = $80 (compared to $100 from the initial solution).

Definitions

Learning Objectives

Learning Objectives

Related questions