M.Sc. (Semester III) (CBCS) Examination Oct/Nov-2017
Computer Science
OPERATIONS RESEARCH
Day Date: Tuesday, 21-11-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
Instructions: Question no. 1 and 2 are compulsory.
Attempt any 3 questions from Q. no. 3 to Q. no. 7
Figures to the right indicate full marks.
Q.1 Fill in the blanks (one mark each) 07
The convex hull of a set XCRn is of convex sets
containing X.
A basic feasible solution is a basic solution which also satisfies the

A simplex in one dimension is
The shortest possible time in which the activity can be finished is
called as
If ?th constraint in the primal LPP is an equality then the corresponding
?th dual variable is
When more than one activity comes and joins as event, such event is
called event.
Unnecessarily inserting dummy activity in a network logic is known as
error of
State True or False mark 07
The sequence of critical activities in a network is called critical path.
The line 2x1 3x2 CR2 is a convex set.
The boundary point of a convex set is an extreme point.
The cost assigned to artificial variable in Two phase method is -M.
In Dual simplex method we find an initial solution which is infeasible
but optimal.
Activities that must be completed immediately prior to the start of
another activity is called a successor activity.
Closed half spaces are always convex set.
Q.2 Prove that the hyperplane in Rn is a convex set. 03
Compare CPM PERT explaining similarities and mentioning differences. 04
Write short note
Basic solution Basic feasible solution
04
Obtain the dual of following problem:-
Min z -2x1 3x2 x3
Subject to, x1 x3 51 x1 2x2 10x3 10
x1 x3 3 x1, x2 x3 0
03
Page 2 of 2
SLR-MG-303
Q.3 Prove that The collection of all feasible solutions to LP problem
constitute a convex set whose extreme points corresponds to basic
feasible solution.
07
Solve
Max. z 3x1 2x2 5x3
Subject to the constraints,
x1 2x2 x3 430, 3x1 2x3 460, x1 4x2 420 x1, x2↑x3 0
07
Q.4 A project has following time schedule.
Activity Time in Months Activity Time in Months
2 3
2 1
1 5
4 4
8 3
5
Construct a PERT network and compute
Total Float of each activity.
ii) Critical path its duration.
09
Construct Kuhn-Tucker conditions for solving quadratic Programming
Problem.
05
Q.5 Explain Ford Fulkerson algorithm of network flow problem. 09
Define Matroid with example 05
Q.6 Give algorithm of dual simplex method. 07
Solve by Big M method
Max. z -2x1 x2
Subject to the constraints,
3x1 x2 3 4x1 3x2 x1 2x2 4 x1, x2 0
07
Q.7 Write a note
Critical Activity ii) Critical path 06
Give algorithm for Hungarian Assignment method. 08