ALCCS

 

Code: CS42†††††††††††††††††† Subject: OPERATIONS RESEARCH AND SYSTEM SIMULATION

Flowchart: Alternate Process: MARCH 2010Time: 3 Hours††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††† Max. Marks: 100

 

NOTE:

      Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.Marks are indicated against each question.

      Parts of a question should be answered at the same place.

      All calculations should be up to three places of decimals.

 

Q.1 ††† a.†† Discuss how revised simplex method can be used to improve computational efficiency of solving a linear programming problem.

 

††††††† †††† b. Discuss the economic interpretation of the dual problem.

 

††††††† †††† c. Differentiate between unbounded solution and infeasible solution in the context of solution to linear programming problem.

 

††††††† †††† d.Explain what is an unbalanced transportation problem.

 

††††††† †††† e.Discuss four applications of integer programming.

††††††† †††† f.†† Discuss degeneracy in linear programming problem?

 

†† †††† †††† g.Discuss the role of Operations Research in decision making.†††††††††††††††††††††††††††††††††† (7 4)

††††††††††††

Q.2†††† a.What is the standard form of linear programming problem and how do you obtain it? Also discuss special cases that arise in application of simplex method.†††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (9) †††††††††††

 

††††††††††† b.Use penalty method to solve the following linear programming problem:††††††††††††††††††††††††††††††††††††††††† Maximize z= 2x1+x2+x3

†††††††† †††††††††††††† Subject to

††††††††††††††††††††††† 4x1+6x2+3x3<=8,†††† 3x1-6x2-4x3<=1, 2x1+3x2-5x3>=4

and x1, x2, x3<=0.†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† ††† (9)

††††††† †††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

Q.3†††† a.What are various algorithms for finding initial basic solution for a transportation problem? Discuss them.††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††††††††††††††††††††††††††††††(9)

 

††††††††††† b.†† Determine the basic feasible solution, if exists, to the following transportation††††         problem using Vogelís Approximation method.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† Distribution Centres

†††††† Sources†††††††††††††††† D1†††††††††††††††††† D2†††††††††††††††††† D3†††††††††††††††††† D4†††††† Supply

††††††††† S1††††††††††††††††††† 2††††††††††††††††††††† 3††††††††††††††††††††† 11††††††††††††††††††† 7††††††††† 6

††††††††††† S2††††††††††††††††††† 1††††††††††††††††††††† 0††††††††††††††††††††† 6††††††††††††††††††††† 1††††††††† 1

††††††††††† S3††††††††††††††††††† 5††††††††††††††††††††† 8††††††††††††††††††††† 15††††††††††††††††††† 9††††††††† 10

††† Requirement 7††††††††††††††††††††† 5††††††††††††††††††††† 3††††††††††††††††††††† 2

†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (9)

†††††††††††† ††††

Q.4†††† a.What are various algorithms for solving an Integer Linear programming problem? Discuss branch and bound method in detail.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (9)

 

b.Using the cutting plane method, solve the following Integer Linear Programming

††††† Problem

††††††††††††††††††††††† Maximize †††††††† z = 7x1+10x2

†††††††††††††††††      Subject to†† -x1+3x2<=6, 7x1+x2<=35, x1, x2 are non-negative integers.†††††††††† †††††††† (9)

††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

Q.5†† †† a.Discuss in detail the various parameters for designing and evaluating a simulation††††††

†††††††††††††††††† based experiments.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††††† †††††††(9)

 

††† b. A student has to take examination in three courses x, y, z. He has three days††   available for study. He feels that it would be best to devote a whole day to   study 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 grades he may get by studying are as   follows.

†††† Study days/courses††††††††††††† x††††††††††††††††††††† y††††††††††††††††††††† z

††††††††††† 0††††††††††††††††††††††††††††††††† 1††††††††††††††††††††† 2††††††††††††††††††††† 1

††††††††††† 1††††††††††††††††††††††††††††††††† 2††††††††††††††††††††† 2††††††††††††††††††††† 2

††††††††††† 2††††††††††††††††††††††††††††††††† 2††††††††††††††††††††† 4††††††††††††††††††††† 4

††††††††††† 3††††††††††††††††††††††††††††††††† 4††††††††††††††††††††† 5††††††††††††††††††††† 4

How should the student plan to study so that the grades obtained are maximized?††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† ††††† (9)

†††††††

Q.6†††† a.Discuss Hungarian Assignment algorithm in detail.†††††††††††††††††††††††††††††††††††† †††††††††††††(9)†††††††

 

b.†† A department has five employees with five jobs to be performed. The time (in hrs) each man will take to perform each job is given by the following cost matrix:†††††††††††††††††††††

Employees

††††††††††††††††††††††††††††††††††† I†††††††††† II††††††††† III††††††† IV††††††† V

††††††††† Jobs†††††† A†††††††† 10††††††† 5††††††††† 13††††††† 15††††††† 16

††††††††††††††††††††††† B††††††††† 3††††††††† 9††††††††† 18††††††† 13††††††† 6

††††††††††††††††††††††† C†††††††† 10††††††† 7††††††††† 2††††††††† 2††††††††† 2

††††††††††††††††††††††† D†††††††† 7††††††††† 11††††††† 9††††††††† 7††††††††† 12

††††††††††††††††††††††† E††††††††† 7††††††††† 9††††††††† 10††††††† 4††††††††† 12

How should jobs be allocated one per employee so that total the man-hours can be maximized?††††††††††††††† †††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††† (9)

†††††††

Q.7†††† †††† Write a short note on any THREE of the following:

†††††††††††††††††

(i)     GPSS.

(ii)    Degeneracy in Transportation Problem.

(iii) Sensitivity and Parametric Analysis.

(iv) Monte Carlo Method.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††† (6+6+6)

††††††††††††