M.Sc. (Semester III) (CBCS) Examination Nov/Dec-2018
Computer Science
OPERATIONS RESEARCH
Time 2½ Hours Max. Marks: 70
Instructions: All questions are compulsory.
Figures to the right indicate full marks.
Q.1 Choose the most correct alternative. 14
Artificial variable techniques not used in the
Big-M method Phase II method
Simplex method None of these
Transportation problem is a special case of
Assignment problem LPP
CPM Both and
Optimal solution in LPP is which
Maximize or minimize the objective function
Maximize the objective function
Minimize the objective function
Satisfies the non negative restrictions
A simplex in three dimension is
Line Triangle
Point None of these
In standard form of LPP
The decision variables are unrestricted in sign
The constraints are strict equations
The constraints are inequality
None of these
Give a system of m simultaneous linear equations in n unknown the
number of basic variable will ne
n n-m
n+m m
Network problems have advantages in terms of project
scheduling planning
controlling all of these
Quadratic programming problem is the particular case of
Linear programming problem
Non linear programming problem
Both and
None of these
Optimum basic feasible solution to the LPP corresponding to the
Middle point of feasible region
Corner point of feasible region
Both and
All of these
Page 2 of 3
SLR-VG-221
10) In critical path analysis, CPM is
Event oriented Probabilistic 8
Deterministic in nature Dynamic in nature
11) If the primal problem has unbounded solution, then the dual problem will have
Finite solution Feasible solution
Optimal solution No feasible solution
12) Which of the following is not assumption of LPP
Additive Uncertainty
Proportionality Divisibility
13) In phase II simplex method phase I
Gives a starting basic feasible solution
Optimize the objective function
Provide optimal solution
None of these
14) In assignment problem involving 4 workers and 3 jobs, total number of
assignment possible are
4 3
7 12
Q.2 Answer the following. (Any four) 08
Define a basic feasible solution and basic solution.
Compare CPM and PERT.
Define Cographic Matroid.
What is the meaning of Dual of a LPP?
Define Convex function and convex region.
Write notes on. (Any two) 06
Linear programming problem and its solution and optimum solution.
Balanced Transportation problem
unbalanced Transportation problem
Graphical method to solve LPP.
Q.3 Answer the following. (Any two) 08
Explain North-West corner method.
Define Matroid with an example.
Solve the following LPP by graphical method
Max Z 3X1 5X2
Subject to the constraints
2X1 X2 7
X1 X2 6
X1 3X2 9
X1, X2 0
Answer the following. (Any one) 06
Write procedure of Simplex method of solving a LPP.
Define CPM and PERT and Also explain critical activity and critical path.
Page 3 of 3
SLR-VG-221
Q.4 Answer the following. (Any two) 10
Solve the following assignment problem and find optimum assignment
schedule.
Person
Job
1 2 3 4 5
8 4 2 6 1
0 9 5 5 4
3 8 9 2 6
4 3 1 0 3
9 5 8 9 5
Prove that: The collection of all feasible solutions to LPP constitute a
convex set whose points corresponding to basic feasible solution.
Define Dual of Linear programming problem and obtain dual of following
LPP
Min Z -2X1 3X2 X3
Subject to the constraints
X1 X3 5
X1 2X2 10 X3 10
X1 X3 5
X1, X2, X3 0
Answer the following. (Any one) 04
Give algorithms for dual simplex method of solving linear programming
problem.
Define float activities and write a note on total float, free float and
independent float.
Q.5 Answer the following. (Any two) 14
Find the IBFS of following T.P. by North-West corner method and then optimize
the solution using MODI method.
Source
Destination
1 2 3 4 Supply
1 3 1 7 4 250
2 2 6 5 9 350
3 8 3 3 2 400
Demand 200 300 350 150
Explain Ford and Fulkerson algorithm of network flow problem and short
comment on exponential behavior of Ford and Fulkerson algorithm.
Solve the following LPP by simplex method
Max Z 3X1 4X2
Subject to the constraints
X1 X2 4
4X1 2X2 3
X1, X2 0