MA9219 OPERATIONS RESEARCH Question Paper

M.E/M.Tech DEGREE EXAMINATION, JANUARY 2010

First Semester

Computer Science and Engineering

MA9219- OPERATION RESEARCH

(Common to M.E-Network Engineering, M.E-Software Engineering and M.Tech- IT)

(Regulation 2009)

Time: Three hours Maximum: 100 Marks

Answer all the questions

Part A – (10*2=20 Marks)

1. Explain the main characteristics of the queuing system
2. State the steady state measures of performance in a queuing system.
3. State Pollaczek-Khinctchine formula for non-Markovian queuing system.
4. Mention the different types of queuing models in series.
5. What is Monte Carlo simulation? Mention its advantages.
6. Give one application area in which stochastic simulation can be used in practice.
7. Define slack and surplus variable in a linear programming problem.
8. Mention the different methods to obtain an initial basic feasible solution of a transportation problem.
9. State the Kuhn-Tucker conditions for an optimal solution to a Quadratic programming problem.
10. Define Non-linear programming problem. Mention its uses.

Part B – (5*16=80 Marks)

11. (a) (i) Explain M/M/1 (N/FCFS) system and solve it under steady state condition. (8)
(ii) In a railway marshalling yard, goods trains arrive at a rate of 30 trains per day. Assuming that the inter-arrival time follows an exponential distribution and the service time (the time taken to bump a train) distribution is also exponential with an average 36 minutes. Calculate the following The average no of trains in the queue The probability that the queue size exceeds 10. If the input of trains increases to an average 33 per day, what will be changed in (1) and (2)? (8)

(Or)

(b) (i) Explain the model M/M/S in case of first come first serve basis. Give a suitable illustration. (8)
(ii) An automobile inspection in which there are three inspections stalls. Assume that cars wait in such a way that when stall becomes vacant, the car at the head of the line pulls up to it. The station can accommodate almost four cars waiting (Seven in station) at one time. The arrival pattern is Poisson with a mean of one car every minute during the peak hours. The service time is exponential with mean of 6 minutes. Find the average no of customers in the system during peak hours, the average waiting time and the average number per hour that cannot enter the station because of full capacity. (8)
12. (a)(i) Discuss the queuing model which applied to queuing system having a single service channel, Poisson input, exponential service, assuming that there is no limit on the system capacity while the customers are served on a first in first out basis. (7)
(ii)At a one-man barber shop, customers arrive according to Poisson distribution with a mean arrival rate of 5 per hour and his hair cutting time was exponentially distributed with an average hair cut taking 10 minutes. It is assumed that because of his excellence, reputation customers were always willing to wait. Calculate the following Average number of customers in the shop and the average no of customers waiting for a haircut. The percentage of customers who have to wait prior getting into the Barber’s chair. The percent of time an arrival can walk without having to wait. (9)

(Or)

(b)(i) Explain briefly open and closed networks models in a queue system. (8)
(ii)Truck drivers who arrive to unload plastic materials for recycling currently wait an average of 15 minutes before unloading. The cost of driver & truck time wasted while in queue is valued Rs. 100 per hour. A new device is installed to process truck loads at a constant rate of 10 trucks per hours at a cost of Rs. 3 per truck unloaded. Trucks arrive according to a Poisson distribution at an average rate of 8 per hour. Suggest whether the device should be put to use or not. (8)
13. (a)(i) Distinguish between solutions derived from simulation models & solutions derived from analytical models. (6)
(ii)Describe the kind of problems for which Monte Carlo will be an appropriate method of solution. (5)
(iii)Explain what factors must be considered when designing a simulation experiment.

(Or)

(b)(i)Discuss stochastic simulation method of solving a problem. What are the advantages & limitations of stochastic simulation? (9)
(ii)What are random numbers? Why are random numbers useful in simulation models and solutions derived from analytical models? (7)
14. (a)(i)Explain various steps of the simplex method involved in the computation of an optimum solution to a linear programming problem? (4)
(ii)Explain the meaning of basic feasible solution and degenerate solution in a linear programming problem. (4)
(iii)Solve the following LPP using the simplex method. (8)
Max z=5x1+3x2
subject to x1+x2<=2
5x1+2x2<=10
3x1+8x2<=12
X1, X2>=0

(Or)

(b)(i)What is degeneracy in transportation problem? How is transportation problem solved when demand and supply are not equal? (8)
(ii)A company has factories at F1, F2 and F3 which supply to warehouses at W1, W2 and W3. Weekly factory capacities are 200,180,120 and 150 units respectively. Unit shipping costs (in rupees) are as follows.
Warehouse
W1 W2 W3 Supply
F1 16 20 12 200
Factor F2 14 8 18 160
F3 26 24 16 90
Demand 180 120 150 450
Determine the optimal distribution for this company to minimize total shipping cost. (8)
15. (a)(i)What is meant by quadratic programming? How does a quadratic programming differ from a linear programming problem? (8)
(ii)Explain briefly the various methods of solving a quadratic programming pbm. (8)

(Or)

(b)(i)Explain the role of Lagrange multipliers in a non-linear programming problem. (6)
(ii)Solve the following quadratic programming problem: (10)
Maximize=2x1+x2-x1^2
Subject to the constraints 2x1+3x2<=6
2x1+x2<=4
And
X1,x2>=0

M.E/M.Tech DEGREE EXAMINATION, JUNE 2010

First Semester Computer Science and Engineering 

MA9219- OPERATION RESEARCH 

(Common to M.E-Network Engineering, M.E-Software Engineering and M.Tech- IT) 

(Regulation 2009) 

Time: Three hours Maximum: 100 Marks Answer all the questions 

Part A – (10*2=20 Marks)

1. Define queue discipline.
2. What do you mean by (a) steady state and (b) transient state in a queuing system?
3. Write down Pollaczek Khintchine formulae.
4. What is meant by closed queuing network?
5. Mention the types of simulation.
6. Specify any two advantages of simulation.
7. Define Basic feasible solution of a LPP.
8. Write down the mathematical formulation of a transportation problem.
9. What are the Kuhn-Tucker conditions for solving a non-linear programming problem?
10. What is Quadratic programming?

Part B – (5*16=80 Marks)

11. (a)Arrivals at a telephone booth are considered to be Poisson, with an average time of 10 minutes between one arrival and the next. The length of the phone call is assumed to be distributed exponentially. (i) What is the probability that a person arriving at the booth will have to wait? (ii)What is the average length of the queues that form from time to time? (iii)The telephone department will install a second booth when convinced that an arrival would expect to have a wait atleast three minutes for the phone. By how much must the flow of arrivals be increased in order to justify a second booth? (16)

(Or)

(b)A super market has two salesmen ringing up sales at the counters. If the service time for each customer is exponential with mean 4 minutes, and if people arrive in a Poisson fashion at the counter at the rate of 10 per hour. (i) Calculate the probability that an arrival will have to wait for service (ii) Find the expected percentage of idle time for each salesman (iii)If a customer has to wait, find the expected length of his waiting time. (16)
12. (a)An automatic car wash facility operates with only one bay. Cars arriving according to Poisson distribution with a mean of 4 cars per hour may wait in the facility’s parking lot if the bay is busy. The time of washing and cleaning a car is exponential, with a mean of 10 minutes. Cars that cannot park in the lot can wait in the street bordering the wash facility. The manager of the facility wants to determine the size of the parking lot. Suppose that a new system is installed so that the service time for all cars is constant and equal to 10 minutes, how does the new system affect the operation facility.(16)

(Or) 

(b)Consider two servers. An average of 8 customers per hour arrive from outside at server1, and an average of 17 customers per hour arrive from outside at server2. Inter-arrival times are exponential. Server1 can serve at an exponential rate of 20 customers per hour and server 2 can serve at an exponential rate of 30 customers per hour. After completing service at serve 1, half the customers leave the system and half go to server2. After completing server2, ¾ of the customers complete service and ¼ returns to server 1. 

(i)What fraction of the time is server1 idle? 

(ii) Find the expected no of customers at each server (iii)Find the average time a customer spends in the system 

(iv)How would the answers to parts (1)-(3) change if server 2 could serve only an average of 20 customers per hour. (16)

13. (a)The occurrence of rain in a city on a day depends upon whether or not it rained on the previous day. If it has rained on the previous day, the rain distribution is
Event : No rain 1cmrain 2cmrain 3cmrain 4cmrain 5cmrain Probability: 0.5 0.25 0.15 0.05 0.03 0.02 If it did not rain on the previous day, the distribution is, Event : No rain 1cmrain 2cmrain 3cmrain Probability: 0.75 0.15 0.06 0.04 Simulate the city’s weather for 10 days and determine by simulation, the total rainfall during the period. Use the random numbers 67 63 39 55 29 78 70 06 78 76 for simulation. Assume that for the 1st day of the simulation it had not rained the day before.

(Or) 

(b)Records of 100 truckloads of finished jobs arriving in a department’s check out area show the following: Checking out takes 5 minutes and checker takes care of only one truck at a time. The data is summarized in the following table: Truck Inter Arrival time: 1 2 3 4 5 6 7 8 9 10 Frequency : 1 4 7 17 31 23 7 5 3 2 (total=100) As soon as the trucks are checked out, the truck drivers take them to the next departments. Using Monte-Carlo simulations determine: What is the average waiting time before service? What is likely to be the largest?

14. (a)Use two phase simplex method to solve the problem.
Minimize Z= ((15/2) x1) – (3x2) Subject to the constraints 3x1 - x2 - x3>=3 X1 – x2 + x3>=2 And x1, x2, x3>=0

(Or) 

(b)A company has 5 jobs to be done. The following matrix shows the return in rupees on assigning ith (i=1, 2, 3, 4, 5) machine to the jth job (j=A, B, C, D, E). Assign the five jobs to the five machines so as to maximize the total expected profit. A B C D E 1 5 11 10 12 4 2 2 4 6 3 5 Machine 3 3 12 5 14 6 4 6 14 4 11 7 5 7 9 8 12 5

15. (a)Find the dimensions of a rectangular parallelepiped with largest volume whose sides are parallel to the coordinate planes, to be inserted in the ellipsoid, G(x, y, z) = ((x^2/a^2) +(y^2/b^2) + (z^2/c^2)-1) =0 (Or) (b)Apply Wolfe’s Method for solving the quadratic programming problem Maximize Z=4x1+6x2 – (2(x1^2)) - 2x1x2 – (2(x2^2)) Subject to X1+2x2<=2 And x1,x2>=0