2000

1) Solve the following assignment problem for the given assignment costs: \begin{table} \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline &\(P_1\)&\(P_2\)&\(P_3\)&\(P_4\)&\(P_5\)
\hline \(J_1\)&11&17&8&16&20
\hline \(J_2\)&9&7&12&6&15
\hline \(J_3\)&13&16&15&12&16
\hline \(J_4\)&21&24&17&28&26
\hline \(J_5\)&14&10&12&11&13
\hline \end{tabular} \end{center} \end{table} Here, \(P_i,J_i\) reperesent person and jobs respectively and valie of \(i=1,2..,5\).

[15M]

1999

1) A police department has the following minimal daily requirement for police officers during its sixth shift periods:

| Time of Day | Period |  Minimal Number Required|
|-------------|--------|-------------------------|
|02a.m.-06a.m |   1    |           22            |
|06a.m.-10a.m |   2    |           55            |
|10a.m.-02p.m |   3    |           88            |
|02p.m.-06p.m |   4    |          110            |
|06p.m.-10p.m |   5    |           44            |
|10p.m.-02a.m |   6    |           33            |

An officer must start at the beginning of a 4-hour shift and stay on duty for two consecutive shifts(an 8-hour tour).Any one starting during period 6 days on duty during period 1 of the next day.The objective of the police department is always have to on duty the minimal number required in a period but to do so with least number of officers.Develop the corresponding linear programming model.

[20M]

2) Show that a problem in the theory of games can be expressed as a linear programming problem.

[20M]

3) Respond True or False to the following, justify your answer in case of False:

(i) If the number of primal variables is much smaller than the number of constraints, it is more efficient to obtain the solution of primal by solving its dual.

(ii) When the primal problem is non-optimal,the dual problem is automatically infeasible.

(iii) An unrestricted primal variable will have the effect of yielding an equality dual constraint.

(iv) If the solution space is unbounded, the objective value always will be unbounded.

(v) The selection of the entering variable from among the currnt non-basic variable as the one with the most negative objective coefficient guarantees the most increase in the objective value in the next iteration.

(vi) In the simplex method,the feasibility condition for the maximization and minimization problems are different.

(vii) A simplex iteration(basic solution) may not necessarily coincides with a feasible extreme point of the solution space.

(viii) If the leaving variable does not corresponding to the minimum ration,atleast one basic variable will definitely become negative in the next iteration.

[20M]

4) Develop mathematical model of a balanced transportation problem.Prove that it always has a feasible solution.

[20M]

5) Find the optimal assignment for the given assignment costs:

           Machine

|       |$$M_1$$|$$M_2$$|$$M_3$$|
|-------|-------|-------|-------|
|$$J_1$$|   5	|    7	|   9 	|  	
|$$J_2$$|  14	|  	10  |  	12  |  	
|$$J_3$$|  15 	|   13	|  	16  |  	   

[20M]

TBC

6) Give the economic interpretation of duality in linear programming

[20M]

1998

1) A certain stimulus administered to each of 12 patients resulted in the following increases of blood pressures: 5,2,8,-1,3,0,6,-2,1,5,0,4. Can it be calculated that the stimulus will be, in general accompanied by an increases of blood pressure, given that for 11 degree of freedom value \(t_{.05}\) is 2.201.

[20M]

2) Prove that a basic feasible solution to a linear programming problem must correspond to an extreme point of the set of all feasible solutions.

[20M]

3) Solve the unbalanced assignment problem in minimization where \([C_{ij}]= \begin{bmatrix} 12& 10& 15&22&18&8\\ 10& 18& 25&15&16&12\\ 11& 10& 3&8&5&9\\ 6& 14& 10&13&13&12\\ 8& 12& 11&7&13&10 \end{bmatrix}.\)

[20M]

4) Solve the \(m \times 2\) game: \(\begin{bmatrix} 2& 3\\ 6& 7\\ -6& 10\\ -3& -2\\ 3& 2 \end{bmatrix}.\)

[20M]

5) A bookbinder processes the manuscripts of five books through the three stages of operation viz., printing ,binding and finishing. the time required to perform the printing, binding and finishing operations are given below:

[20M]

Processing Time (in hours)

Book Printing Binding Finishing 1 50 60 90 2 100 70 110 3 90 30 70 4 70 40 80 5 60 50 110 —— ———- ——— ———–

[20M]

6) Determine the order in which books should pr processes in order to minimize the total time required to process the books. Find the minimum total processing time. Use dynamic programming to find the maximum value of \(Z=y_1y_2y_3\) subject to the constraints
\(y_1+y_2+y_3=5\), \(y_1,y_2,y_3\geq 0\)

[20M]

7) A bank has two tellers working on saving accounts.The first tellers handles withdrawals only. The second teller handles depositors only. It has been found that the service time distribution of both deposits and withdrawals are exponential with a mean service time of 3 minutes per customer. Depositors and withdrawers are found to arrive in a Poisson fashion throughout the day with mean arrival rate of 16 and 14 per hour. What would be the effect on the average waiting time for depositors and withdrawers if each teller could handle both withdawals and deposits? What would be the effect if this could only be accomplished by increasing the service time to 3.5 minutes?

[20M]

1997

1) Describe a quadratic programming problem and outline a method of solving it.

[10M]

2) Minimize Subject to \(\mathrm{u}_{1}^{2}+\mathrm{u}_{2}^{2}+\mathrm{u}_{3}^{2}\) \(\quad \mathrm{u}_{1}+\mathrm{u}_{2}+\mathrm{u}_{3} \geq 10 ; \quad \mathrm{u}_{1}, \mathrm{u}_{2}, \mathrm{u}_{3}, 20\)

[10M]

3) Consider a modified form of matching biased coins game problem. The matching player is paid eight rupees if the two coins tum both heads and one rupees if the coins turn both tails. The non-matching player as paid three rupees when the two coins do not match. Given the choice of being the matching or non- matching players, which one would you choose and what would be your strategy?

[10M]

4) State the Transportation problem in general terms and explain the problem of degeneracy.

[10M]

5) Use simplex method to solve the following Linear Programming Problem Maximize \(\quad z=4 x_{1}+10 x_{2}\) subject to the constraints \(\quad 2 \mathrm{x}_{1}+\mathrm{x}_{2} \leq 50\) \(\begin{array}{l} 2 \mathrm{x}_{1}+5 \mathrm{x}_{2} \leq 100 \\ 2 \mathrm{x}_{1}+3 \mathrm{x}_{2} \leq 90 \\ \mathrm{x}_{1}, \mathrm{x}_{2} \geq 0 \end{array}\)

[10M]

6) In a factory, there are six jobs to perform and each should go through two machines \(A\) and \(B\) in the order \(A\), \(B\). The processing timings (in hours) for the jobs are given below. Determine the sequence for performing the jobs that would minimize the total elapsed time \(T\). What is the value of \(T\)? \begin{tabular}{|l|c|c|c|c|c|c|} \hline Job : & & \(\mathrm{J}_{1}\) & \(\mathrm{~J}_{2}\) & \(\mathrm{~J}_{3}\) & \(\mathrm{~J}_{4}\) & \(\mathrm{~J}_{5}\) & \(\mathrm{~J}_{6}\)
Machine A : & 1 & 3 & 8 & 5 & 6 & 3
Machine B : & 5 & 6 & 3 & 2 & 2 & 10
\hline \end{tabular}

[10M]

1996

1) Solve that linear programming problem: \(Maximize\;subject\;to\; \quad z=3 x_{1}+5 x_{2}\) \begin{aligned} x_{1} & \leq 4
x_{2} & \leq 6
3 x_{1}+2 x_{2} & \leq 18
x_{1,} & x_{2} \leq 0 \end{aligned} If the cost coefficient of \(\mathrm{x}_{1}\) is kept fixed, find the range for the cost coefficient of \(\mathrm{x}_{2}\) without affecting the optimal solution.

[15M]

2) A tax consulting firm has four service stations (counters) in its office to receive people who have problems and complaints about their income, wealth etc. The number of arrivals averages 80 persons in an eight hour service day, Each tax adviser spends an irregular amount of time serving the arrivals which have been found to have an exponential distribution. The average service time is 20 minutes. Calculate the average number of people waiting to be serviced, average time a person spends in the system and the average waiting time for a person. What is the expected number of idle tax advisers af any specified time.

[15M]