Cochin University of Science and Techology (CUST) 2008-2nd Sem M.C.A , - Question Paper
MCA.2/08.6
MCA DEGREE Q SEMESTER EXAMINATION, APRIL 2008
CAS 2205 COMPUTER BASED OPTIMIZATIONS
Maximum marks : 50
Time: 3 Hours
PART A
(Answer ALL questions)
(All questions carry EQUAL marks)
(15 x 2 = 30)
I. a. What do you mean by an LPP. Express it mathematically.
b. Define artificial variables.
c. Distinguish between dual and primal problem in LPP.
II. a. Write the mathematical formulation of a transportation problem.
b. Explain briefly a method of solving an assignment problem.
c. What do you mean by degeneracy in transportation problems?
III. a. Define the binary LPP.
b. Write the mathematical formulation of a travelling salesman problem.
c. Write a note on integer programming problem.
IV. a. State Bellmans principle of optimality.
b. Write a note on probabilistic dynamic programming.
c. Explain the characteristics of a dynamic programming problem.
V. a. Explain the characteristics of a queuing system.
b. Distinguish between discrete and continuous Markov chains.
c. What do you mean by Birth-Death process?
PART B
(All questions carry EQUAL marks)
(5x4 = 20)
VI. A. Solve by Simplex method
Maximise Z = 4xj +10x2 Subject to
2x, + x2 50 2xj +5x2 < 100 2xx + 3x2 < 90
Xj} x2 2.0
OR
B. Solve by dual Simplex method
Minimise Z ~3xt + x2 Subject to
xl+x2>\
2xx + 3x2 2
Xj, x2 ;> 0
(Turn over)
(2)
VII, A. Solve the following transportation problem:
|
r A |
B |
C |
D |
Available | |
|
E |
11 |
13 |
17 |
14 |
250 |
|
F * |
16 |
18 |
14 |
10 |
300 |
|
G |
I 21 |
24 |
13 |
10 |
400 |
|
Demand 200 |
225 |
275 |
250 | ||
OR
B. Solve the assignment problem:
|
A |
B |
C |
D |
|
10 |
25 |
15 |
20 |
|
15 |
30 |
5 |
15 |
|
35 |
20 |
12 |
24 |
|
17 |
25 |
24 |
20 |
1
3
VIII. A, Solve by branch and bound technique:
|
Maximise |
z = |
2*j |
+ 3*2 |
Subject |
|
5xj |
+ 7*2 |
<35 | ||
|
4xl |
+ 9x2 |
<36 | ||
|
*!> |
tsJ IV o |
and are | ||
|
Solve the TSP | ||||
|
4 |
2 |
3 |
4 |
4 |
|
Ax qo |
2 |
5 |
7 |
1 |
|
A2 6 |
00 |
3 |
8 |
2 |
|
A3 8 |
7 |
00 |
4 |
7 |
|
A4 12 |
4 |
6 |
00 |
5 |
|
A5 1 |
3 |
2 |
8 |
CO |
OR
B.
Use DPP to show that Z = P\ !<>g P\ + Pi log Pi +
IX. A.
the
subject
constraints
+ Pn l0g Pn
to
n is a minimum when px - p2 =
Pi +P2+.......+ Pn = 1 md Pj * , j~ 1,2.
OR
Use DPP to solve the LPP Maximise Z =3x{ + 5x2 Subject to
x, < 4
x2 6
3xj + 2x2 18
Xj, x2 >0
B.
(Contd....3)
X. A. The rate of arrivals at a public telephone booth follows Poisson distribution with an average time of 10
minutes between one customer and the next. The duration of a phone call is assumed to follow exponential distribution with mean time of 3 minutes,
(a) What is the probability that a person arriving at the both will have to wait?
(b) What is the average length of the non-empty queues that form from time to time?
OR
B. Show that for a single service station, Poisson arrivals and exponential service time, probability that , exactly n calling units are in then queuing system is (1 - p) pn when p is the traffic intensity.
***
|
Attachment: |
| Earning: Approval pending. |
