West Bengal Institute of Technology (WBIT) 2009-4th Sem B.Tech Computer Science and Engineering Computer Science - Mathematics - Question Paper

Name : .....................................................................

RoaNo.:.............................................

Invigilator's Signature:...............................................

C8/B.TBCB(CSB)/8BM-4/M(CS)-402/2010 2010

OPERATION RESEARCH & OPTIMIZATION TECHNIQUES

TimeAllotted: 3 Hours    Full Marks : 70

The figures in the margin indicate fiM marks.

Candidates are required to give their answers In theft own words

as far as practicable.

Graph sheet(s) to be supplied by the Institute.

GROUP -A (Multiple Choice Type Questions)

1. Choose the correct alternatives for any ten of the following :

10 x 1 = 10

1) An activity is said to be.............if a delay in the start

of the course makes a delay in the completion time of the entire project.

a) non-critical    b) critical

c) delay    d) all of these.    .

ifl The set S* { x² + y ² < 25 : ( x, y) eK} is a .a) Convex set    b) Concave set

c) Noii-convex set    d) Non-concave set.

HQ In a transportation problem ............... method gives

the closest initial basic feasible solution to the optimal basic feasible solution    ₍

a) NWC    b) MMM

c) VAM    dj MODI.

Iv) In an m x n transportation problem we get a degenerate basic feasible solution if the number of occupied cells are

m + n - 1    b) less than m * n - 1

c) more than m + n - 1 d) m-n.

v) Assignment problem is solved by

a)    Stepping stone method

b)    Two phase method

. ' ' .

c)    Hungarian method

d)    Karmakar's Algorithm.

vl) If the primal problem has ail unbounded solution then the solution to the dual problem will be

a) unbounded    b) unique

c)    multiple    d) infeasible.

vii) A queuing model is generally expressed using

a)    Fulkerson's Notation

b)    Newton's Notation

c)    Dantzing's Notation

d)    Kendall's Notation.

vtii) Which of the following set is not convex set ?

a)    . x-{(x,y):- | x | S3, j y | S2)

b)    x = {( xjy ) ; 5x - y = 4 }

c)    x * {(x ) : 2x - y S 3 }

d)    x * {(x_xy ) ; x² + y ² = 5 }.

ix)    A basic solution of the system of equations 2xj + Xj*2, 3xj + 2x2 - a:₃ = 3 is

a) ( 1, 1. 1 )    b) ( 1, 1, 0 )

c) (1,0,0)    d) none of these.

x)    The Canonical fqrm of L.P.P. can be written inmatrix form as

a)    MaxZs cx Sub to, Ax b

*0

b)    Max Z=cx Sub to, Ax S b

x 0

c)    Min Zs cx Sub to, Ax$b

xiO

d)    MlnZ=cx Sub to, Ax tb

x 0.    .

xi)    For a rn x n degenerate Transportation problem the number of occupied cells is

a)    less than ( m + n - 1 )

b)    greater than ( m + n - 1J

c)    less than equal to ( m + n - 1 )

d)    equal to ( m + n - 1 ).     '

xtt) A game is solved graphically when the pay off matrix is of the form

a) mx 1    b) mxn

c) mx2    d) nx m.

GROUP - B (Short Answer Type Questions)

Answer any three of the following. Solve the game whose pay-off matrix is given by

Player B

Bi	b2	b3
1	3	1
0	-4	-3
1	5	- *

Solve the following by graphical method; Maximize Z = 4 + 7xjj

subject to    ^/

2x_x t- 5xa 40,

*i +*2 = 11.

*2 * ⁴*

Xx , x% 2: 0.

4. Obtain the dual of the following L.P.P :

Minimize Z*x₁-x₂ + 2x3

subject to    .

x, + Xz + 4x_s 7, i    xjj 2xjj 2 10,    

3xi +X2 + Xi_}3.

Xj 1 Xj > Xg 0.

5.. Find the optimal assignment for the assignment problem with the given cost matrix

I	II	III	IV
10	9	7	8
5	8	7	7
5	4	6	5
2	3	4	3

6.    Determine EOQ in an inventory control problem having

# Constant rate of demand

y) Instantaneous replenishment and itt) Finite rate of production.

7.    Food X contains 6 unit of vitamin A & 7 unit of vitamin B per gram and costs 12p/gm. Food Y contains 8 unite and 12 units of A and B per gram respectively and costs 20 p/gm. The daily requirement of vitamin A & B are at least 100 units & 120 units respectively. Formulate the above as a L.P.P. to minimize the costs.

GROUP -C ( Long Answer Type Questions)

Answer any three of the following. 3 x 15 = 45

8. a) Use duality to solve the LLP,

Min Z = 3*! + Xj Subject to

2x_x + 32 2, ' x_x + X2 > 1,

- ' . ' ' * ' .

. , X2 > 0.

b) Solve graphically the game having the following pay of matrix

B1 B2 B3 B4

A1 '

7 + 8

9. a) A television repairman find that the time spent on his jobs has an exponential distribution with a mean of 30 minutes. If he repairs the sets in the order in which they came in and if the arrival of sets follows a Poisson distribution with an approximate average rate of 10 per 8-hours day, what is the repairman s expected idle time

each day ? How many jobs are ahead of the average set just brought ?

bj Solve the following LLP :

Max X = x_x + *2

Subject to    i

3x_x + 2x2 5,

*22,

GS/B.TECH(CSE) /SEM-4/M(CS)-402/2010

10. a) Solve the transportation problem by VAM :

	I	11	III
1	8	7	3	60
2	3	8	9	70
3	11	3	5	80
bJ	50	80	80

Also verify whether the solution obtained by VAM is optimal or not ? Find optimal solution, if the above solution is not optimal

b) Solve the following LPP,

Maximize Z = 6x_x + lOx*

Subject to 3xj + 5 < 10,

5xj + 3X2 15 and . x₁,x₂0.    8 + 7

11. a) Construct a network for the project whose activities and precedence relationship are as given below :

Activities	A	B	C	D	E	F	G	H
Immediate Predecessor		A	A	B	B, C	E	D, F	G

b) The time of each activity of the network Is given in ^fo *m ~ form, where t₀ is the optimistic time, t_p is

the pessimistic time and is most likely time.

i)    Determine the expected project length ( )

ii)    Calculate s.d. of the project length ( o)

iii)    What is the percentage of confidence that the project will complete

a)    at least 4 weeks earlier than expected time

b)    not more than 4 weeks than the expected time ?

tv) What should be the scheduled complication times for the probability of complication are 90% confidence and 100% confidence ?

P(Z<, 1.33 ) = 0.9082 Given data P ( 1.28 ) = 0.9

P(ZS 5) = 0.99999.    5+ 10

12. a) Find the shortest path from Node 1 to Node 9 of the distance network shown in the following figure using Dijkstra's algorithm.

routes between every two nodes from the network given below. The distances (in kms. ) are given on the arcs.

4051    8

Attachment: west-bengal-institute-of-technology--wbit--2009-b-tech-computer-science-and-engineering-51959-1.pdf

Earning:   Approval pending.