# Operations Research July 2009

PART-A

Note: Answer any FIVE full questions, selecting at least TWO questions from each part.

1 a. Define : i) Feasible solution ii) Feasible region iii) Optimal solution

b.  A manufacturer produces three models I, II, III of certain product using raw materials A and B

 Raw material Requirements per unit Availability I II III A 2 3 5 4000 B 4 2 7 6000 Minimum demand 200 200 150 – Profit per unit (Rs) 30 20 50 –

Formulate the problem as a linear program model.

c. Using graphical method solve the LPP.

Maximize Z = 5xj + 4×2 Subject to 6xi + 4×2 < 24 xi + 2×2 < 6 -X] + x2 < 1

X2 < 2, Xi> X2 > 0

2 a. Define slack variable and surplus variable.

b.  Find all the basic solutions of the following system of equations identifying in each case the basic and non basic variables, 2Xj +x2 +4x3 = 11 , 3Xj +x2 +5x3 =14

c.   Using simplex method of tabular form solve the LPP.

Maximize- Z = 4xj + 3×2+ 6×3 Subject to 2xi + 3×2 + 2×3 < 440 4xi + 3×3 < 470 2xi+5×2<430

Xi, X2, X3 > 0

3 a. Using two-phase method solve the LPP. Minimize Z = 7.5xi – 3×2

Subject to 3xj – X2 – X3 > 3 Xj – X2 + X3 > 2 X], X2, X3 > 0

b. Using Big-M method solve the CPP.Maximize Z = 2xi + X2 Subject to 3xi + X2 = 3 4xi + 3×2 > 6 xi + 2×2 < 3 Xi, X2> 0

4. a. Use Revised Simplex Method to solve the LPP.

Maximize Z = 3xi + 5×2 Subject to 2xi <4 2x2 <12 3xi + 2×2 — 18 xi,x2>0

b. Explain : i) Weak duality property

ii) Strong duality property

iii) Complementary solutions property

c.   Write the dual of the following : i) Maximize Z = 6xj + 10×2

Subject to xi < 14 x2 < 16 3xi + 2×2< 18 xi, x2 > 0

ii) Maximize Z = (5 8)

Subject to

 1 2^ (xA f5‘ 1 3 I 10 3 5 j U; ^20^i (xA fo’ i > A; 1°,

PART-B

5  a. In Parametric Linear Programming explain about:

i)     Systematic changes in the Cj parameters.

ii)    Systematic changes in the bj parameters.

b. Using dual simplex method solve the LPP. Maximize Z = -3xj – 2×2

Subject to xi + X2 > 1 xi + x2 > 7 xj+2×2>10 x2>3 Xi, x2> 0

6  a. The transpiration costs per truck load of cement (in hundreds of rupees) from each plant t each project site are as follows : Project sites Factories  Supply

 1 2 3 4 1 2 3 11 7 6 2 1 0 6 1 1 3 5 8 15 9 10 7 5 3 2 17

b. Demand Determine the optimal distribution for the company so as to minimize the tota transportation cost. Four jobs are to be done on four different machines. The cost (in rupees) of producing i* jol on the j* machine is given below :

Mi Machines M2  M3  M4

 15 11 13 15 17 12 12 13 14 15 10 14 16 13 11 17

Assign the jobs to different machines so as to minimize the total cost.

7 a. Solve the game whose payoff matrix to the player A is given below

 1 7 2 6 2 7 5 2 6

b. Solve the following (2 x 3) game graphically.

 1 3 11 00 5 2

8  a. Use Tabu Search algorithm to find the optimal solution of

b.   Give note on outline of a Basic Simulated Annealing Algorithm.

c.   Give note on outline of a Basic Genetic Algorithm.