West Bengal Institute of Technology (WBIT) 2009-4th Sem B.Tech Computer Science and Engineering Computer Science - Operation Research and Optimization Techniques - Question Paper
C8/B.Tech(C8E)/8EM-4/mC8)-402/09 3
ENGINEERING & MANAGEMENT EXAMINATIONS, JUNE - 2009
OPERATIONS RESEARCH & OPTIMIZATION TECHNIQUES
I
Time : 3 Hours ) I Full Marks : 70
Graph sheets are provided at the end of this booklet
GROUP - A ( Multiple Choice Type Questions )
1. Choose the correct alternatives for any ten of the following : 10 x 1 = 10
1) in n assignment problem the basic feasible solution for the constraint equations will consist of
a) ( 2m + 1 ) variables b) (2m- 1 ) variable
c) 2m variables d) 2m2 variables. 1
ii) For an LPP the dual of the dual problem is called the
a) primal problem b) dual problem '
c) both (a) and (b) d) none of these 1
ill) What is the number of basic non-variables In the balanced TP with 4 rows and
5 columns ?
a) 4 b) 5
c) 12 d) 20. |
iv) The full form of CPM is
a) crash project management b) critical path management
c) critical path method d) none of these. ____
' . ' ' ' ' . ' * ' .... , ........... ' .....
v) A necessary and sufficient condition for a basic solution to a maximizing problem to be optimal is that (for all J)
a) Zj-Cjt 0 b) Zj -CjZQ
c) Zj-Cj = 0 d) Zj-Cj<OotZj-Cj> 0. 1
vl) The basic feasible solutions of the system of equations *i +x2 + x3 = 8 3jtx + 2x2 =18
are
a) (2, 6, 0 ), (6. 0, 2) b) ( 1.7.0). (7. 1.0)
c) ho basic solution d) none of these. __
vii) In an assignment problem, the minimum number of lines covering all zeroes In the reduced cost matrix of order n can be
a) at most n b) n + 1
c) n-1 d) at least n. 1
vttQ Given ai system of m simultaneous linear equations in n unknown variables .( m < n). the number of basic variables will be
' . ' ' ' a) m b) n.
c) n - m d) m - n.
Ix) If there are n workers and n jobs, there would be
a) n t solutions b) ( n 1) I solutions
c) (n!)n solutions d) n solutions. .
x) The point of intersection of a pure strategy game is called
a) value of the game b) two-person game
c) mixed strategy game d) none of these.
xi) In an ( M/M/1 ) : ( /FIFO ) model, the average number of customers E ( n) is given by
a) p" b)
1 -p
, P2
c) j _ p d) None of these.
xll) An assignment problem is a special type of
a) transportation problem b) LPP
c) Inventory problem d) none of these.
xiii) In a fair game the value of the game is
a) 1 b} 0
c) unbounded d) none of these.
|
xiv) The value of the game having the following pay-off matrix Is | ||||||||||||||||
|
|
a) 6 c) 8 xv) An assignment problem can be aj Hungarian Method ' c) Matrix Minima Method |
b) 10 d) 2. A by b) VAM d) Dominance Principle. |
GROUP-B ( Short Answer Type Questions)
3 x 5 = 15
Answer any three of the follctortng.
2. Show that the set given by
x={ (xyx2) : 4x? + 9xa<36}
is a convex set.
3. Solve the following game problem :
|
Player B |
I |
n |
m |
:& |
|
~ I |
3 |
2 |
4 |
0 |
|
II |
3 |
4 |
2 |
4 |
|
HI |
4 |
2 |
4 |
0 |
|
- IV |
0 |
4 |
.0 |
8 |
Player A
6
4. Write the LPP in its standard form Max ( Z) = x j - 3x2 + 5x3
subject to
*1 +x2 + x3<7
Xj -X2 + X3> 2
*3x j - x2 + ?x3 = - 5
' . - * '
x j, x2 2: 0 and x3 is unrestricted.
|
' ' . 1 4461(08/06) |
 |
5. Find any one of the basic feasible solutions of the following system of equations :
Xj + 2x2 + 3x3 = 6
2x i -x2 + 4x3 = 4
6. Use Big Mmethod to maximize
' ' . t
Z = 3*l-*2 subject to
2x1+x22 .
Xj + 3x2 <3 .... .
x2 4
xj,x20.
GROUP - C (Long Answer Type Questions)
, Answer any three of the following. 3 x 15 = 45
7. Use the dual simplex method to solve the following L.P.P. : 15
Maximize Z = -2xj -2x2-4x3
subject to the constraints
2xj + 3x2 + 5x3 > 2 3Xj + x2 + 7x 3 S 3 Xj + 4x2 + 6x3 5 x j-.'xj, x3 0.
8. a) Solve the transportation problem by VAM method and checking optimality find optimum cost. 9
10
13
12
|
Z>1 |
- d2 |
03 | |
|
Oi |
4 |
3 |
2 |
|
1 |
5 |
0 | |
|
3 |
3 |
8 |
5 |
|
8 |
5 |
4 |
|
b) Find the assignment of Machines to the Jobs, that will maximize the profit. AB | ||||||||||||||||||||||||
|
|
9. A small maintenance project consists of the following Jobs whose precedence relationship is given below : | ||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||
Draw the project network. 3
a)
b) c)
Find the expected duration and variance of each activity. 2
Calculate the early and late occurrence for each event and the expected project length.* 3
d) Calculate the variance and standard deviations of project length. 2
e) What Is the probability that the project will be completed
I) 4 weeks earlier than expected ? '
II) not more than 4 weeks later than expected ?
If the project due date is 19 weeks, what is the probability of meeting the due date ?
[ Given that p { 1-33 ) = 04082 and ( 0-666 ) = 0-2514 ] 2 + 2+1
|
10. a) A medium project has twelve distinct activities which are to be further analyzed by using PERT. The following relevant Information is also given in tabular form : | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
1) Present these activities on the PERT network, ii) Find the expected total float for each activity, ill) Determine the average critical path.
iv) Within how many days is It expected to complete the project with 99%
12
chance ?
b) Find graphically the non-negative values of the variables x and y which satisfy the constraints 3x + 5y 15. 5x+2y< 10 and which maximizes the linear form z = 6x + 3y. 3
11. a) Customers arrive at a one-window drive-ln bank according to a Poisson
distribution with mean 10 per hour. Service time per customer is exponential with mean 5 minutes. The space in front of the window, including that for the serviced car can accommodate a maximum of 3 cars. Other cars can wait outside this space. '
i) What is the probability that an arriving customer can drive directly to the space in front of the window ?
ii) What 1$ the probability that an arriving customer will have to wait outside the indicated space ? *
ill) How long is an arriving customer expected to wait before starting service ?
iv) How many spaces should be provided in front of the window so that all the
arriving customers can wait in front of the window at least 20% of the time? 4 x 2= 10
* *
b) Find the dual of the following LPP : .
Minimize Z= 3x x + x2
subject to x j + x2 > 1
2x j + 3x2 > 2
t
xj,x2i0. 5
12. a) Solve the travelling salesman problem with the following cost matrix
[ c y ) 4 x 4 where, c is the cost of travelling from city i to city J :
|
1 |
2 |
3 |
4 | |
|
1 |
QO |
15 |
30 |
4 |
|
2 |
6 |
oo |
4 |
1 |
|
3 |
10 |
15 |
oo |
16 |
|
4 |
7 |
18 |
13 |
OO |
CS/B.Tech (CSE)/8EM-4/M(C8)-403/09
b) . Solve the following Transportation Problem using the Vogel's Approximation Method : .
|
d2 |
*>3 | ||
|
Oi |
2 |
7 |
4 |
|
3 |
3 |
1 | |
|
3 |
5 |
4 |
7 |
|
04 |
1 |
6 |
2 |
Also test the optimality of the solution obtained using Modified Distribution Method. 10
END
4461 ( OS/OeT1
|
Attachment: |
| Earning: Approval pending. |
