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)

 

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

j (x₁, x₂) = –

4. Is the function f(x) = x₁ separable? x = (x₁, x₂).
5. Define a quadratic programming problem.
6. Explain the Markovian property of dynamic programming.
7. When do you say the Khun-Tucker necessary conditions are also sufficient for a maximization problem?
8. Explain the need for Goal programming.
9. What is zero-one programming?
10. When do we need Geometric programming problem?

 

SECTION – B

 

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

 

11. Solve the following LPP by dynamic programming.

max z = 3x₁ + 4x₂

Subject to

2x₁+x₂ £ 40

2x₁+5x₂ £ 180

x₁+x₂ ≥ 0

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

max Z = 2x₁ +3x₂ –

Subject to

x₁ + 2x₂ £ 4, x₁, x₂ ≥ 0.

15. Solve by using Khun – Tucker conditions

max Z = 10x₁ + 4x₂ – 2

Subject to: 2x₁ + x₂ £ 5, x₁, x₂ ≥ 0

 

 

 

 

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

f(x₁, x₂) = 2x₁ + 3

Subject to 4x₁ + 2£ 16, x₁, x₂ ≥ 0

17. Consider the chance constrained problem

max Z = 5x₁ + 6x₂ + 3x₃

Subject to

P_r [a₁₁ x₁ + a₁₂ x₂ + a₁₃ x₃ £ 8] ≥ .95

P_r [5x₁ + x₂ + 6x₃ £ b₂] ≥ .1, x_j ≥ 0 “j = 1,2,3

~ N

b₂ ~ N (7,9).  Reduce this problem to a deterministic model.

18. Solve

minimize f(x₁, x₂) = 3 + 2

Subject to

x₁ + x₂ = 7

x₁, x₂≥ 0

 

SECTION – C

 

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

 

19. a) Solve the following all Integer programming problem

max  Z = x₁ + 2x₂

Subject to

x₁ + x₂ £ 7

2x₁ £ 11

2x₂ £ 7     x₁, x₂ ≥ 0, x₁, x₂ integers.

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

max Z =  2x₁ + 3

Subject to

x₁ + 4 x₂  £  4

x₁ + x₂ £ 2

x­₁, x₂ ≥ 0

21. 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.

1. b) Solve the following using dynamic programming

min Z =

Subject to

u₁+u₂+u₃ ≥ 10,  u₁, u₂, u₃ ≥ 0                                                       (15+5)

22. a) Solve the following Geometric programming problem

f(X) = .

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

 

Go To Main page