LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – STATISTICS

AC 51

FOURTH SEMESTER – APRIL 2006

                                        ST 4951 – ADVANCED OPERATIONS RESEARCH

 

 

Date & Time : 27-04-2006/9.00-12.00         Dept. No.                                                       Max. : 100 Marks

 

 

SECTION A  

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

1. Define linearly independent vectors.
2. Define a Mixed Integer Programming  Problem.
3. What is the need for Integer Programming Problems?
4. State Bellman’s principle of optimality.
5. What is meant by Separable Programming Problem?
6. Define Goal Programming Problem.
7. Write down the mathematical formulation of a Geometric Programming Problem.
8. Explain the stage and state variables in a dynamic Programming Problem.
9. Name the methods used in solving a Quadratic Programming Problem.
10. What is the need for Dynamic Programming Problem?

 

SECTION B

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

 

1. Explain the construction of fractional cut in the Gomory’s constraint method.

 

1. State all the characteristics of a Dynamic Programming Problem.

 

1. In the network given below are different routes for reaching city B from city A passing through a number of other cities, the lengths of the individual routes are shown on the arrows. It is required to determine the shortest route from A to B. Formulate the problem as a Dynamic Programming Problem model, explicitly defining the stages, states and then find the optimal solution.

 

6

 

 

5                      3                  2                      4

 

 

 

7                   4                   2                    2

 

5

 

 

 

1. Solve the following Non-Linear Programming Problem:

Optimize Z = X ² +Y ² + W ²,

subject to X +Y + W = 1,

X, Y, W ≥ 0.

1. Derive the Kuhn-Tucker necessary conditions for solving a Generalized Non-Linear Programming Problem with one inequality constraint.

 

1. Derive the orthogonality and Normality conditions for solving the unconstrained Geometric Programming Problem.

 

1. Convert the following Stochastic Programming Problem into an equivalent deterministic model, max Z = X₁ + 2 X₂ + 5 X₃ ,subject to

P [a₁ X₁ + 3 X₂ + a₃ X₃  ≤ 10 ] ≥ 0.9,

P [ 7 X₁ + 5 X₂ + X₃  ≤ b₂ ] ≥ 0.1,

X₁, X₂, X₃  ≥ 0.

Assume that a₁, a₃ are independent normally distributed random variables with means E (a₁) = 2, E (a₃) = 5, V (a₁) = 9, V (a₃) = 16. Also assume that

b₂ ~ N (15, 25).

 

1. The manufacturing plant of an electronics firm produces two types of T.V. sets, both colour and black-and-white. According to past experiences, production of either a colour or a black-and-white set requires an average of one hour in the plant. The plant has a normal production capacity of 40 hours a week. The marketing department reports that, because of limited sales opportunity, the maximum number of colour and black-and-white sets that can be sold are 24 and 30 respectively for the week. The gross margin from the sale of a colour set is Rs. 80, whereas it is Rs. 40 from a black-and-white set.

The chairman of the company has set the following goals as arranged in the order of their importance to the organization.

1. 1. Avoid any underutilization of normal production capacity (on layoffs of production workers).
   2. Sell as many T.V. sets as possible. Since the gross margin from the sale of colour T.V. set is twice the amount from a black-and-white set, he has twice as much desire to achieve sales for colour sets as black-and-white sets.
   3. The chairman wants to minimize the overtime operation of the plant as much as possible.

Formulate this as a Goal Programming Problem.

 

SECTION C

Answer any TWO questions.                                                        (2 x 20 =40 marks)

1. Solve the following Integer Programming Problem:

Max Z = 3 X₁ +  X₂ + 3 X₃

subject to – X₁ + 2 X₂ + X₃  ≤ 4,

4 X₂ – 3 X₃  ≤ 2,

X₁ – 3 X₂ + 2 X₃  ≤ 3,

X₁, X₂, X₃  ≥ 0.

 

1. (i) Solve the following Dynamic Programming Problem (DPP):

Min Z =  subject to    = C , x _j ≥ 0 , j = 1,2, … n. C > 0.

 

(ii) Solve the following LPP by DPP technique:

Max Z = 3 X₁ + 4 X₂ ,

subject to 2 X₁ + X₂  ≤ 40,

2 X₁ + 5 X₂  ≤ 180,

X₁, X₂ ≥ 0.

 

1. Use Kuhn-Tucker necessary conditions to solve the following Generalized Non- Linear Programming Problem:

Max Z = 2 X₁ – X₁² +  X₂

subject to 2 X₁ + 3 X₂  ≤ 6,

2 X₁ + X₂  ≤ 4,

X₁, X₂ ≥ 0.

 

1. Solve the following Quadratic Programming Problem using Wolfe’s algorithm:

Max Z = 4 X₁ + 6 X₂ –  2 X₁² – 2 X₁ X₂  –  2 X₂² ,

subject to  X₁ + 2 X₂  ≤ 2,

X₁, X₂ ≥ 0.

 

 

Go To Main page