LOYOLA COLLEGE (AUTONOMOUS), CHENNAI –600 034

M.Sc., DEGREE EXAMINATION – STATISTICS

## FOURTH SEMESTER – APRIL 2004

**ST 4951/S 1052 – ADVANCED OPERATIONS RESEARCH**

12.04.2004 Max:100 marks

1.00 – 4.00

**SECTION – A**

** **

Answer **ALL** questions (10 ´ 2 = 20 marks)

- What is the need for an integer programming problem?
- Define a covex function.
- Is the following quadratic form negative definite?

j (x_{1}, x_{2}) = –

- Is the function f(x) = x
_{1} separable? x = (x_{1}, x_{2}).
- Define a quadratic programming problem.
- Explain the Markovian property of dynamic programming.
- When do you say the Khun-Tucker necessary conditions are also sufficient for a maximization problem?
- Explain the need for Goal programming.
- What is zero-one programming?
- When do we need Geometric programming problem?

**SECTION – B**

** **

Answer any **FIVE** questions (5 ´ 8 = 40 marks)

- Solve the following LPP by dynamic programming.

max z = 3x_{1} + 4x_{2}

Subject to

2x_{1}+x_{2} £ 40

2x_{1}+5x_{2} £ 180

x_{1}+x_{2} ≥ 0

- State and prove the necessary condition for a function of n variables to have a minimum. Also prove the sufficient condition.
- Derive the Gomery’s constraint for a mixed algorithm.
- Solve by Beale’s method

max Z = 2x_{1} +3x_{2} –

Subject to

x_{1} + 2x_{2} £ 4, x_{1}, x_{2} ≥ 0.

- Solve by using Khun – Tucker conditions

max Z = 10x_{1} + 4x_{2} – 2

Subject to: 2x_{1} + x_{2} £ 5, x_{1}, x_{2} ≥ 0

- Reduce the following separable programming problem to an approximate linear programming problem.

f(x_{1}, x_{2}) = 2x_{1} + 3

Subject to 4x_{1} + 2£ 16, x_{1}, x_{2} ≥ 0

- Consider the chance constrained problem

max Z = 5x_{1} + 6x_{2} + 3x_{3}

Subject to

P_{r} [a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} £ 8] ≥ .95

P_{r} [5x_{1} + x_{2} + 6x_{3} £ b_{2}] ≥ .1, x_{j }≥ 0 “j = 1,2,3

~ N

b_{2} ~ N (7,9). Reduce this problem to a deterministic model.

- Solve

minimize f(x_{1}, x_{2}) = 3 + 2

Subject to

x_{1} + x_{2} = 7

x_{1}, x_{2}≥ 0

** **

**SECTION – C**

** **

Answer any **TWO** questions (2 ´ 20 = 40 marks)

- a) Solve the following all Integer programming problem

max Z = x_{1} + 2x_{2}

Subject to

x_{1} + x_{2} £ 7

2x_{1} £ 11

2x_{2} £ 7 x_{1}, x_{2} ≥ 0, x_{1}, x_{2} integers.

- b) Explain branch and bound method with an example. (12+8)
- Solve by Wolfe’s method

max Z = 2x_{1} + 3

Subject to

x_{1} + 4 x_{2} £ 4

x_{1} + x_{2} £ 2

x_{1}, x_{2} ≥ 0

- a) A student has to take examination in 3 courses A,B,C. He has 3 days available for the study. He feels it would be best to devote a whole day to the study of the same course, so that he may study a course for one day, two days or three days or not at all. His estimates of the grades he may get by study are as follows:-

Course A B C

Days

0 0 1 0

1 1 1 1

2 1 3 3

3 3 4 3

How should he study so that he maximizes the sum of his grades? Solve by Dynamic

Progrmming.

- b) Solve the following using dynamic programming

min Z =

Subject to

u_{1}+u_{2}+u_{3} ≥ 10, u_{1}, u_{2}, u_{3} ≥ 0 (15+5)

- a) Solve the following Geometric programming problem

f(X) = .

- b) Explain how will you solve if there is a constraint. (15+5)

Go To Main page