M.Sc. (Computer Science) (Semester III) (CGPA)
Examination, 2017
OPERATION REASEARCH
Day Date: Tuesday, 25-04-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
Instruction Q.NO.1 and Q.NO.2 are compulsory.
Attempt any 3 questions from Q.No3 to Q.No.7.
Figure to the right indicates full marks.
Q.1 Choose the correct alternative (one mark each) 10
A st-cut is partition of the verties with
SEA SEA &tEB tEB None of these
Which finding dual of any primal form, all constraints must be in

Any of these
Which of the following is the assumption of an LP model
Divisibility Proportionality
Additivity All of the above
If an opportunity cost value is used for an unused cell to test
optimatity, it should be
equal to zero most negative number
most positive number any value
The degeneracy in the transportation problem indicates that
dummy allocation(s) need to be added
The problem has no feasible solution
The multiple optimal solution exist
but not
If there were n workers n jobs there would be
solutions Solutions
solutions n solutions
For maximization LP model, the simplex method terminated when
all values
Cj zj 0 Cj zj 0 Cj zj 0 zj 0
Page 2 of 3
If for a given solution, a slack variables is equal to zero then
the solution is optimal
the solution is infeasible
The entire amount of resource with the constraint in which the
slack variable appears has been consumed
All of the above
For any primal problem its dual.
optimal value of objective function is same
primal will have an optimal solution if f dual does too
both primal dual cannot be infeasible
All of the above
10) The another term commonly used for activity slack time is.
Total float Free float
Independent float All of the above
State whether True or False 04
If dual has an unbounded solution, primal has feasible solution.
In time cost-trade-off function analysis cost decreases linearly as
time increases.
When the given cost matrix is not square matrix, the assignment
problem is called an unbalanced problem.
MODI algorithm is used to solve assignment problem.
Q.2 What is assignment problem? Give two applications. 04
Define Critical Path Analysis. 03
What are linear programming what are its major assumption
limitation.
04
Define optimistic time. 03
Q.3 Give the difference between PERT CPM. 06
Solve the following LP problem by graphically 08
Min z 20 1 10 2
Subject to 1+2 2 40
3 1 2
4 3 2
2
Q.4 Determine an initial basic feasible solution to the following
transportation problem by using vogel's Approximation method
07
Destination
D1 D2 D3 D4 Supply
S1 21 16 15 3 11
Source S2 17 18 14 23 13
S3 32 27 18 41 19
Demand 6 10 12 15
Explain the Hungarian method to solve assignment problem. 07
Page 3 of 3
Q.5 Give outlines of the simplex method in linear programming. 07
Solve Min z 6 1 2
Subject to constraints
2 1 2 2 2 0
by dual simplex method.
07
Q.6 Explain Matroid with an example. 06
Five men are available to do five different jobs. From past records, the
time (in hours) that each man takes to do each job is known given in
the following table
08
Men
Jobs
I II III IV V
A 2 9 2 7 1
B 6 8 7 6 1
C 4 6 5 3 1
D 4 2 7 3 1
E 5 3 9 5 1
Find the assignment of men to jobs that will minimize the total time
taken
Q.7 The following table gives the activities in a construction project other
relevant information
12
Activity Immediate Time(months) Direct cost
Predecessor Normal Crash Normal Crash
A 4 3 60 90
B 6 4 150 250
C 2 1 38 60
D A 5 3 150 250
E C 2 2 100 100
F A 7 5 115 175
G E 4 2 100 240
Indirect costs vary as follows:
Months: 15 14 13 12 11 10 9
Cost 600 500 400 250 175 100 75
8 7 6
50 35 25
Draw an arrow diagram for the project
Determine the project duration which will result in minimum total
project cost.
Define Critical Path. 02