Course Code: MTE-12
Assignment Code: MTE-12/TMA/2023
Maximum Marks: 100

1. Which of the following statements are true and which are false? Give a short proof or a counter-example in support of your answer.

a) In a two-dimensional LPP solution, the objective function can assume the same value at two distinct extreme points.

b) Both the primal and dual of an LPP can be infeasible.

c) An unrestricted primal variable converts into an equality dual constraint.

d) In a two-person zero-sum game, if the optimal solution requires one player to use a pure strategy, the other player must do the same.

e) If 10 is added to each entry of a row in the cost matrix of an assignment problem, then the total cost of an optimal assignment for the changed cost matrix will also increase by 10 .

2. a) Solve the following linear programming problem using simple method:

Maximize \(\mathrm{z}=3 \mathrm{x}_{1}+5 \mathrm{x}_{2}+4 \mathrm{x}_{3}\)

Subject to \(2 \mathrm{x}_{1}+3 \mathrm{x}_{2} \leq 8\)

\(2 \mathrm{x}_{2}+5 \mathrm{x}_{3} \leq 10\)

\(3 \mathrm{x}_{1}+2 \mathrm{x}_{2}+4 \mathrm{x}_{3} \leq 15\)

\(\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3} \geq 0\)

b) Using the principle of dominance, reduce the size of the following game:

\[
\left[\begin{array}{ccc}
-1 & -2 & 8 \\
7 & 5 & -1 \\
6 & 0 & 12
\end{array}\right]
\]

Hence solve the game.

3. a) Find all basic feasible solutions for the following set of equations:

\[
\begin{aligned}
& 2 x_{1}+6 x_{2}+2 x_{3}+x_{4}=3 \\
& 6 x_{1}+4 x_{2}+4 x_{3}+6 x_{4}=2 \\
& x_{1}, x_{2}, x_{3}, x 4 \geq 0
\end{aligned}
\]

b) Examine convexity of the following sets:

i) \(\mathrm{S}_{1}=\left\{\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right) \in \mathbb{R}^{2} \mid 4 \mathrm{x}_{1}+3 \mathrm{x}_{2} \leq 6, \mathrm{x}_{1}+\mathrm{x}_{2} \geq 1\right\}\)

ii) \(\mathrm{S}_{2}=\left\{(\mathrm{x}, \mathrm{y}) \in \mathbb{R}^{2} \mid \mathrm{x}^{2}+\mathrm{y}^{2} \geq 1\right\}\).

4. a) Solve the following linear programming problem by graphical method:

\[
\text { Maximize } \mathrm{z}=5 \mathrm{x}_{1}+7 \mathrm{x}_{2}
\]

Subject to \(\quad \mathrm{x}_{1}+\mathrm{x}_{2} \leq 4\)

\[
\begin{aligned}
& 3 \mathrm{x}_{1}+8 \mathrm{x}_{2} \leq 24 \\
& 10 \mathrm{x}_{1}+7 \mathrm{x}_{2} \leq 35 \\
& \mathrm{x}_{1}, \mathrm{x}_{2} \geq 0
\end{aligned}
\]

b) Find the dual of the following LPP:

\[
\begin{array}{ll}
\text { Maximize } & z=x_{1}+x_{2}+x_{3} \\
\text { Subject to } & x_{1}-3 x_{2}+4 x_{3}=5 \\
& x_{1}-2 x_{2} \leq 3 \\
& 2 x_{2}-x_{3} \geq 4
\end{array}
\]

\(\mathrm{x}_{1}, \mathrm{x}_{2} \geq 0\) and \(\mathrm{x}_{3}\) is unrestricted in sign.

5. a) Find the initial basic feasible solution of the following transportation problem using matrix-minima method:

Also, find the optimal solution.

b) Solve the following game graphically:

6. a) A firm manufactures two types of products, A and B, and sells them at a profit of ₹ 2 on type \(A\) and \(₹ 3\) on type B. Each product is processed on two machines \(M_{1}\) and \(M_{2}\). Type a requires one minute of processing time on \(M_{1}\) and two minutes on \(M_{2}\); type \(B\) requires one minute on \(M_{1}\) and one minute on \(M_{2}\). The machine \(M_{1}\) is available for not more than 6 hours 40 minutes while machine \(M_{2}\) is available for 10 hours during any working day.

Formulate the problem at LPP.

b) Solve the following assignment problem:

7. a) The following table is obtained in the intermediate state while solving an LPP by simplex method:

Check whether an optimal solution of the LPP will exist or not.

b) Write the LPP model of the following transportation problem:

c) Find the range of values of \(\mathrm{p}\) and \(\mathrm{q}\) which will render the entry \((2,2)\), a saddle point for the following game:

8. a) Test the convexity of the following sets:

\[
\begin{aligned}
& S_{1}=\left\{(x, y) \mid x^{2}+y^{2} \geq 1, y \geq x, y \geq-x\right\} \\
& S_{2}=\left\{(x, y) \mid x^{2}+y^{2} \leq 16, x \leq 2, y \geq 2\right\}
\end{aligned}
\]

b) Determine all the basic feasible solutions to the equations

\[
\begin{aligned}
& x_{1}+x_{2}+2 x_{3}=4 \\
& 2 x_{1}-x_{2}+x_{3}=2 .
\end{aligned}
\]

Identify the degenerate basic feasible solutions.

9. a) Let \(A=\left[\begin{array}{lll}2 & 5 & 1 \\ 3 & 2 & 1\end{array}\right], \mathrm{B}=\left[\begin{array}{ll}1 & 2 \\ 3 & 5\end{array}\right]\) and \(\mathrm{C}=\left[\begin{array}{ll}1 & 3 \\ 2 & 2 \\ 5 & 1\end{array}\right]\). Compute \(\mathrm{AB}, \mathrm{BC}, \mathrm{AC}\), if they exists, otherwise, give reason for their non-existence.

b) Solve the following LPP:

\[
\begin{array}{ll}
\text { Minimize } & \mathrm{z}=\mathrm{x}_{1}-2 \mathrm{x}_{2}-3 \mathrm{x}_{3} \\
\text { Subject to } & -2 \mathrm{x}_{1}+3 x_{2}+3 \mathrm{x}_{3}=2 \\
& 2 \mathrm{x}_{1}+3 \mathrm{x}_{2}+4 \mathrm{x}_{3}=1 \\
& \mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3} \geq 0
\end{array}
\]

c) Find the saddle point (if exists) in the following pay-off matrix:

Also, find the value of the game.

10. a) Determine an initial basic feasible solution to the following transportation problem and hence find an optimal solution to the problem:

b) Find all values of \(\mathrm{k}\) for which the vectors \(\left[\begin{array}{l}1 \\ 0 \\ 1\end{array}\right],\left[\begin{array}{c}1 \\ -1 \\ 0\end{array}\right]\) and \(\left[\begin{array}{c}\mathrm{k} \\ -\mathrm{k} \\ 2\end{array}\right]\) are linearly independent.