Operations Research Answers

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. (10)

(a) The optimal solution for the following LPP is 30 :

*

Z =

Max 1 2 3 3 Z = x − x + x

Subject to x1 + x2 + x3 ≤10

x1

, x2

, x3 ≥ .0

(b) The optimal solution of an ILLP can be obtained by rounding off the optimal solution

of its LP relaxation.

(c) If the availabilities and requirements of a balanced transportation problem are

integers, the optimal solution to the problem will have integer values.

(d) The following max /3/4 F / F problem can be reduced to a machine problem.

Job

Processing time on

M1 M2 M3

1 8 6 10

2 5 2 13

3 4 11 11

4 6 7 10

(e) For the mixed generator rn+1 = 5( rn + )7 (mod ),8 if r0 = ,4 then 3

r is zero.

10. Find the initial basic feasible solution of the following transportation problem using North-

West corner method: (10)

P1 P2 P3 P4

Requirement

M1

19 11 23 11 11

M2

15 16 12 21 13 

M3

30 25 16 39 19 

Availability 6 10 12 15 113 

 Also, find the optimal solution.

8(b) Using graphical method, solve the game whose pay-off matrix is given as: (4) 

 Player B

 I II III IV 

 I 1 3 − 3 7 

Player A 

 II 2 5 4 − 6

6. (a) A company has 5 jobs to be processed by 5 mechanics. The following table gives the 

return in rupees when the th i job is assigned to the th j mechanic. i,( j = ,2,1 K ).5,

How should the jobs be assigned to the mechanics so as to maximize the overall 

return?

Jobs 

1 2 3 4 5 

1 22 28 30 18 30 

Mechanics 2 30 34 18 11 26 

3 31 17 23 20 27 

 4 12 28 31 26 26 

 5 19 23 30 25 29

5. A businessman needs five cabinets, 12 desks and 18 shelves cleaned out. He has two part 

time employees, Rashid and Ruby. Ruby can clean one cabinet, three desks and three 

shelves in a day while Rashid can clean one cabinet, two desks and 6 shelves in one 

day. Rashid is paid Rs. 22 per day and Ruby is paid Rs. 25 per day. In the order to 

minimize the cleaning costs, for how many days should Rashid and Ruby be 

employed? Formulate the problem as a linear programming problem and find its 

solution by the graphical method.

4. (a) For the transportation problem given below, check whether the given basic feasible 

solution is optimal. If not, modify the given solution and find an optimal solution and 

the optimal value for the problem. (5) 

6 1

25

9 3

45 70

11 5

5

2

50

8

55

10

85

12

5

4 7

90

85 35 50 45

3. Solve the following LPP by the two-phase simplex method. (10) 

 Max 1 2 3 Z = x + x − x

 Subject to 4x1 + x2 + x3 = 4

3 2 6 x1 + x2 − x4 =

 x1

, x2

, x3 ≥ 0

2. Solve the 4( × )3 game with pay off matrix. (10) 

6 5 6

7 4 5

8 6 5

8 5 8

A

 At each stage, clearly explain the steps involved.

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

support of your answer. (10) 

 (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

1

x 1 2 −1 0 1

4

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 .

t C

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

 Max 2 1 4 2 Z = x + x subject to 

 x1 + 2x2 ≤ 5

 4 x1 + x2 ≤

 x1

, x2 ≥ 0

In a public telephone booth the arrivals are on the average 15 per hour. A call on the average takes 3minutes.If there is just one phone,find

a)expected number of callers in the booth at anytime

b)The portion of the time the booth is expected to be idle