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)