Answer to Question #203212 in Abstract Algebra for Dag Stern

Question

Which of the following statements are true? Give a short proof or a counter example in 

support of your answer.

 (i) For any two square matrices A and B, AB = BA.

 (ii) If the following table is obtained in the intermediate stage while solving an LPP by  the Simplex method, then the LPP has an unbounded solution: 

____________________________

-1 -2 0 0 0

____________________________

1 x₁ 1 2 -1 0 1

0 x₄ 0 3 -1 1 2

____________________________

0 4 -1 0 1

____________________________

 

(iii) The number of basic variables in a feasible solution of a transportation problem with  m sources and n destinations is mn.

iv) An optimal assignment of the assignment problem with cost matrix C is also an optimal assignment of the assignment problem with cost matrix C^t

 (v) (1,2) is an optimal solution to the following LPP: 

 Max Z = 2x₁ + 4x₂ subject to 

 x₁ + 2x₂ ≤ 5

 x₁ + x₂ ≤ 4

 x₁, x₂ ≥ 0

Answer 1

i) false

For example:

$\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}=\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}$

v) false

$Max\ Z=2x_1+4x_2$

subject to

$x_1 + 2x_2 ≤ 5$

$4 x_1 + x_2 ≤2$

$x_1, x_2 ≥ 0$

Solve by Simplex method (online calculator www.atozmath.com); optimal solution:

$Max\ Z=8,x_1=0,x_2=2$

iii) false

Correct answer: $m+n-1$

ii) false

Under the Simplex Method, an unbounded solution is indicated when there are no positive values of Replacement Ratio i.e. Replacement ratio values are either infinite or negative. In this case there is no outgoing variable.

In our case there are positive values of Replacement Ratio.

iv) true

For example, if we solve the assignment problem by Hungarian Method, on each step we subtract minimal cost from other costs $C_{ij}$ . So, if we have $tC{ij}$ instead of $C_{ij}$ , we get the same result.