# VTU Previous Exam Papers BE CS Sixth Semester

# Operations Research July 2011

**PART-A**

**Note: Answer FIVEfutt questions, selecting at least TWO questions from each part.**

1 a. What are the different phases of OR? Explain th’cm briefly.

b. Define the following with reference to LPP i) Unbounded solution, ii) Feasible solution. iii) Slack Variable.

c.ABC firm manufactures three products Pi, P2 and P3. The profits are Rs. 30, Rs. 20 and Rs. 40 respectively. The firm has two machines Ml and M2 and requires processing time in minutes for each machine on each product and total machine available minutes on each

Machine | Machine minutes required | Total machine minutes available | ||

PI | P2 | P3 | ||

Ml | ‘ 4 | 3 | 5 | 2000 |

M2 | 2 | 2 | 4 | 2500 |

The firm must manufacture at least 100 Pi’s and 200 P2*s and 50 Pj’s but not more than 150 Pi’s. Setup LP model to solve by simplex method.

2 a. Briefly explain assumptions required in Linear programming models,

b. Use graphical method to solve the following:

X Maximize z = x, + —

x, +x_{2} <S18 subject to 3x, + 2x_{2} < 12 5Xj<nO,

-x,+x_{2}>4, x, andx_{2} S 0

c. Why is simplex method a better technique than graphical for most real case? Explain.

3 a. Explain the concept of degeneracy in simplex method.

b. Use penalty method to solve the following LPP Minimize z = 5x_{t} + 3x_{2}

Subject to 2xj + 4x_{2} <12 2xj +2x_{2} =10, 5x_{t} +2x_{2} >10

x_{t} and x_{2} >0

4 a. Construct the dual problem for the following LPP Maximize Z = 16x, + 14x_{2} + 36x_{3} + 6x_{4} Subject to 14x,+4x_{2}+14x_{3}+8x_{4} =21 ; 13xj + 17x_{2} + 80x_{3} +2x_{4} <48 x„ x_{2} >0 ; X3; X4 unrestricted.

b. Use revised simplex method to solve the following LPP Maximize z = x_{t} + 2x_{2} subject to x, +x_{2} <3,

x, + 2x_{2} < 5

3x, + x_{2} < 6, Xj, x_{2} >0

**PART-B**

5 a. Briefly discuss about sensitivity analysis,

b. Find the maximum of z = 6x, + 8x_{2}

subject to 5x_{r}+ 2x_{2} < 20 x_{l}+2x_{2}<10 x, & x_{2} > 0

6 a Define feasible solution* basic feasible solution, non-degenerate solution and optimal solution in a Transportation problem.

b. A product is pioduced^{;} by 4 faotories *Fi, F2, F3 and F4. Their unit production costs are Rs. 2,3,1 and 5 respectively . Production capacity of the factories are 50,70, 30 and 50 units respectively. The product is supplied to 4 stores Si, S2, S3 and S4, the requirements of which

actories”‘”^ | s, | S* | S_{3} |
S_{4} |

F, | 2 | 4 | 6 | 11 |

f_{2} |
10 | S | 7 | 5 |

Fj | 13 | 3 | 9 | 12 |

F* | 4 | 6 | 8 . | 3 |

Find the transportation plan such that the total production and transportation cost is minimum.

7 a. Solve the following assignment problem. If it is treated as a salesman problem and the cell entries represent cost in rupees, find the least cost route such that salesman does not visit any city twice.

A | B | C | D | E | |

A | – | 2 | 5 | 7 | 1 |

B | 6 | – | 3 | 8 | 2 |

C | 8 | 7 | — | 4 | 7 |

*12“ | ‘-5“* | ||||

E | 1 | 3 | 2 | 8 | — |

b. Explain the following

i) Minimax and Maximin principles.

ii) Pure and: Mixedstrategies.

iii) Two persons zero sum game.

8 a. Write a brief note on Tabu search algorithm.

B | ||||||

I | n | HI | rv | V | ||

A | I | 2 | -1 | 5 | •. -2 | 6 |

II | -2 | 4 | -3 | 1 | 0 |

No. of copies, sold | , 10- | -12–: | 13 | 14 | |

Probability | 0.10 | 0.15 | 0.20 | 0.25 | 0.30 |

Cost of a copy is 30 paise and sale price is 5( many copies should he order?