1995

1) Solve the following linear programming problem: Maximize: $z=x_1+2x_2+3x_3-x_4$ subject to $x_1+2x_2+3x_3=15$ $\begin{array}{l}2x_1+x_2+5x_3=20\\ x_1+2x_2+x_3+x_4=10\\ x_1\ge 0,x_2\ge 0,x_3\ge 0,x_4\ge 0\end{array}$

[15M]

---

2) Solve the transportation problem below for minimizing the cost \begin{tabular}{|cc|cccccc|c|} \hline \multirow{2}{} { costs } & & \multicolumn{6}{|c|} { Store } & \multirow{2}{} { Availability }
& & 1 & 2 & 3 & 4 & 5 & 6 &
\hline \multirow{6}{*} { Warehouse } & 1 & 9 & 12 & 9 & 6 & 9 & 10 & 5
& 2 & 7 & 3 & 7 & 7 & 5 & 5 & 6
& 3 & 6 & 5 & 9 & 11 & 3 & 11 & 2
& 4 & 6 & 8 & 11 & 2 & 2 & 10 & 9
\hline Requirement & 4 & 4 & 6 & 2 & 4 & 2 & 22
\hline \end{tabular}

[15M]

---

3) There are five jobs each of which must go through two machines $A$ and $B$ in the order $A,B$. Processing times are given below: $\begin{array}{lccllll}\text{ Job }& :& 1& 2& 3& 4& 5\\ \text{ Time for A (in hours) : }& 7& 3& 11& 5& 12\\ \text{ Time for A (in hours) : }& 4& 8& 9& 10& 6\end{array}$ Determine a sequence for the jobs that will minimise the elapsed time. Compute the total idle times for the machines in this period.

[15M]

---

4) Using dynamic programming technique solve the problem below: Minimize $z=x_1^2+x_2^2+x_3^2$ subject to $x_1+x_2+x_3\ge 30$ $x_1\ge 0,x_2\ge 0,x_3\ge 0$

[8M]

---

5) If $P_n$ represents the probability of finding $n$ in the long run in a queuing system with Poisson arrivals having parameter $\lambda$ and exponential service times with parameter $\mu ,$ show that $\lambda P_{n-1}-(\lambda +\mu )P_n+\mu P{n}_{+1}=0\text{ for }n>0$ and $-\lambda P_0+\mu P_1=0$ Solve these difference equations and $\mathrm{obtain}{P}_n$ in terms of $\rho ={\displaystyle \frac{\lambda }{\mu }}$

[15M]

---

6) For a machine the following data are available.

Determine the optimum policy for replacement of the above machine.

[15M]

1994

1) Maximise $z=3x_1+2x_2+5x_3$ (by Simplex method) $\begin{array}{ll}\text{ Subject to }& x_1+2x_2+x_3\le 430\\ & 3x_1+2x_3\le 460\\ & x_1+4x_2\le 420\\ & x_1,x_2,x_3\ge 0\end{array}$

[10M]

---

2) Consider the following data:

Here, $D_i$ and $S_i$ represents Destination and Source repectively and $i,j=1,2,3$ The cost of shipment from third source to the third destination is not known. How many units should be transported from the sources to the destinations so that the total cost of transporting all the units to their destinations is a minimum?

[10M]

---

3) Divide a quantity $b$ into $n$ parts so as to maximize their product. Let $f_n(b)$ denote the value. Show that $f_1(b)=b,f_n(b)=max\{z{f}_{n-1}(b-z)\}.0\le z\le b$. Hence find $f_n(b)$ and the division that maximises it.

[10M]

---

4) Apply Wolfe’s method for solving the quadratic programming problem Maximise $Z_x=4x_1+6x_2-2{\left(x_1\right)}^2-2x_1{x}_2-2{\left(x_2\right)}^2$ subject to $\begin{array}{l}{x}_1+2x_2\le 2\\ x_1,x_2\ge 0\end{array}$

[10M]

---

5) A car hire company has one car at each of five depots $a$, $b$, $c$, $d$, $e$. A customer requires a car in each town namely $A$, $B$, $C$, $D$, $E$. Distance (in kilometers between depots (origins) and towns (destinations) are given in the following distance matrix:

How should cars be assigned to customers so as to minimize the distance travelled?

[10M]

---

6) A person is considering to purchase a machine for his own factory. Relevant data about alternative machines are as follows:

As an adviser to the buyer, you have been asked to select the best machine, considering 12 per cent annual rate of return. You are given that (i) single payment present worth factor $@12\mathrm{\%}$ for 10 years $=0.322$. (ii) Annual series present worth factor $@12\mathrm{\%}$ for 10 years $=5.650$.

[10M]

1993

1) Use Simplex method to solve: Minimize Subject to $x_0=x_1-3x_2+2x_3$ $\begin{array}{l}3x_1-x_2+2x_3\le 7\\ -2x_1+4x_2\le 12\\ -4x_1+3x_2+8x_3\le 10\\ x_1,x_2,x_3\le 0\end{array}$

[10M]

---

2) A Departmental Head has four subordinates and four tasks are to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the times each man would take to perform each task is given in the effectiveness matrix below. How should the tasks be allocated one to one man, so as to minimize the total man hours?

Here,$M_i$ and $T_i$ represent Man and Task repectively.

[10M]

---

3) Minimize Subject to $z={\left(y_1\right)}^2+{\left(y_2\right)}^2+{\left(y_3\right)}^2$ $\begin{array}{l}{y}_1+y_2+y_3\ge 7\\ y_1,y_2,y_3\ge 0\end{array}$ by dynamic programming.

[10M]

---

4) Use Kuhn-Tucker conditions to Minimize subject to $f(x)={\left(x_1\right)}^2+{\left(x_2\right)}^2+{\left(x_3\right)}^2$ $\begin{array}{ll}& 2x_1+x_2-5\le 0\\ & x_1+x_3-2\le 0\\ & 1-x_1\le 0\\ & 2-x_2\le 0\\ & -x_3\le 0\end{array}$

[10M]

---

5) On an average 96 patients per 24 -hour day require the service of an emergency clinic. Also on average, a patient requires 10 minutes of active attention. Assume that the facility can handle only one emergency at a time. Suppose that it costs the clinic Rs, 100 per patient treated to obtain an average servicing time of 10 minutes and that each minute of decrease in this average time would cost Rs. 10 per patient treated. How much would have to budgeted by the clinic to decrease the average size of the queue from $1{\displaystyle \frac{1}{3}}$ patients to ${\displaystyle \frac{1}{2}}$ patient?

[10M]

---

6) A transport manager finds from his past records that the costs per year of running a two-wheeler whose purchase cost is Rs. $6000/-$ are given below:

At what age the two wheeler should be replaced? (Note that the money value is constant in time.)

1992

1) Maximize $z=3x_1+2x_2$ subject to $\begin{array}{l}{x}_1+x_2\le 4\\ x_1-x_2\le 2\\ x_1,x_2\ge 0\end{array}$

[10M]

---

2) The following table gives the cost for transporting material from supply points $A,B,C,D$ to demand points $E,F,G,H,J$

The present allocation is as follows: $\begin{array}{llll}\mathbf{\text{ A to E 90: }}& \mathbf{\text{ A to F 10; }}& \mathbf{\text{ B to F 150; }}& \mathbf{\text{ C to F10 }}\end{array}$ $\begin{array}{llll}\mathbf{\text{ C to G }}50;& \mathbf{\text{ C to }}J120;& \mathbf{\text{ D to }}H210;& \mathbf{\text{ D to }}J70\end{array}$ (i) Check if this allocation is optimum. If not, find an optimum schedule. (ii) If in the above problem the transportation cost from $A$ to $G$ is reduce to $10,$ what will be the new optimum schedule?

[10M]

---

3) Minimize $z=y_1+y_2+\dots +y_n$ subject to $y_1,y_2,..,y_n=d$ and $y_j\ge 0$ for all $j$.

[10M]

---

4) Determine $x_1,x_2,x_3$ so as to maximize $z=-x_1^2-x_2^2-x_3^2+4x_1+6x_2$ subject to the constraints $\begin{array}{l}{x}_1+x_2\le 2\\ 2x_1+3x_2\le 12\\ x_1,x_2\ge 2\end{array}$

[10M]

---

5) At what average rate must a clerk at a super-market work in order to insure a probability of 0.90 that the customer will not have to wait longer than 12 minutes? It is assumed that there is only one counter to which customers arrive in a Poisson fashion at an average rate of 15 per hour The length of service by the clerk has an exponential distribution.

[10M]

---

6) There are 5 jobs, each of which must go through machines $A,B$ and $C$ in the order $ABC$. Processing times are given in the following table: $\begin{array}{cccc}\mathbf{\text{ Job }}& \mathbf{\text{ Processing }}& \mathbf{\text{ times }}& \mathbf{\text{ (hours) }}\\ & \mathbf{\text{ A }}& \mathbf{\text{ B }}& \mathbf{\text{ C }}\\ 1& 8& 5& 4\\ 2& 10& 6& 9\\ 3& 6& 2& 8\\ 4& 7& 3& 6\\ 5& 11& 4& 5\end{array}$ Determine a sequence for five jobs that will time minimise the elapsed time.

[10M]