# VTU Previous Exam Papers BE CS Sixth Semester

# Operations Research January 2010

**Part-A**

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

**2. Any missing data may be assumed suitably.**

1 a. What is operations research? Mention six phases of an operations research study.

b. Formulate a linear programming model for the problem given below. The Apex television company has to decide on the number of 27-inch and 20-inch sets to be produced at one of its factories. Market research indicates that at most 40 of the 27-inch sets and 10 of 20-inch sets can be sold per month. The maximum number of work hours available is 5 00 per month. A 27-inch set requires 20 work hours and 20-inch set requires 10 work hours. Each 27-inch set sold produces a profit of $120 and each 20-inch produces a profit of $80. A wholesaler agreed to purchase all the television sets produced if the numbers do not exceed the maxima indicated by market research.

c. Use graphical method to solve the following LPP: Maximize z = 3x_{{} + 5x_{2} Subject to x,<4 2x_{2} <12 3x, +2x_{2} <18 Xj >0, X_{2} >0

d. Write the meaning of following terms with respect to a LPP, Give example for each:

i) Feasible solution. ii) Infeasible solution. iii) Feasible region,

iv) Optimal solution. v) CPF solution.

2 a. Write four assumptions of linear programming.

b. Write six key solution concepts of simplex method. ,

c. Solve the following LPP using simplex method in tabular form:

Maximize z = 5x_{}} + 4x_{2} Subject to 6Xj +4x_{2} <24

Xj + 2x_{2} < 6 -x,+ x_{2} <1

x_{2} < 2 and x, > 0, x_{2} > 0

3 a. Using Big M method solve the following:

Minimize z = 3Xj +2x_{2} + x_{3} Subject to Xj+X_{2}=7

3x, +x_{2} + x_{3} >10 and X, >0, x_{2} >0, x_{3} >0 (12Marks)

b. Explain the typical steps in post optimality analysis for linear programming studies.

4 a. Apply revised simplex method to solve the following problem:

Maximize z = 4xj + 3x_{2} + 6x_{3} Subject to 3x, +x_{2} +3x_{3} <30 2x_{{} +2x_{2} + 3x_{3} <40

and x, >0, x_{2} >0, x_{3} >0

b. Explain key relationships between primal and dual problems.

**Part – B**

5 a. Write a procedure for sensitivity analysis.

b. Use dual simplex method to solve the following:

Maximize z = -4y_{:} -12y_{2} — 18y_{3}

Subject to j_{t} + 3y^>3 2y_{2} + 2y, > 5 and > 0, y_{2} > 0, y_{3} > 0

6 a. Suppose that England, France and Spain produce all the wheat, barley and oats in world. Th world demand for wheat requires 125 million acres of land devoted to wheat production similarly, 60 million acres of land are required for barley and 75 million acres of land fo oats. The total amounts of land available for these purposes in England, France and Spai] are 70 million acres, 110 million acres, 80 million acres respectively. The number of hour of labor needed in England, . France and Spain to produce an acre of wheat is 18, 13 and 1< respectively. The number of hours of labor needed in England, France and Spain to produci an acre of barley is 15, 12 and 12 respectively. The number of hours of labor needed ii England, France and Spain to produce an acre of oats is 12, 10 and 16 respectively. Th< labor cost per hour in producing wheat is $9.00, $7.20 and $9.90 in England, France an( Spain respectively. The labor cost per hour in producing barley is $8.10, $9.00 and $8.40 ii England, France and Spain respectively. The labor cost per hour in producing oats is $6.90 $7.50 and $6.30 in England, France and Spain respectively. The problem is to allocate lane use in each country so as to meet the world food requirement and minimize the total labo: cost.

i) Formulate this problem as a transportation problem by constructing the appropriat* parameter table.

ii) Starting with the north west comer rule, interactively apply the transportation simple> method to obtain an optimal solution.

b. Write different steps in Hungarian algorithm to solve an assignment problem.

7 a. Explain basic characteristics of two person, zero sum game. For the game having following pay off table, determine the optimal strategy for each player by successively eliminating dominated strategies. Indicate the order in which you eliminate strategies.

Player – 2 12 3

Player -1 1

1 | 2 | 0 |

2 | -3 | -2 |

0 | 3 | -1 |

b. Explain how to construct a decision tree and how it is used for decision analysis.

8 Explain briefly:

a. Metaheuristics, its nature, advantage and disadvantage.

b. Tabu search algorithm.

c. Simulated annealing algorithm.

d. Genetic algorithm.