LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
B.Sc. DEGREE EXAMINATION – COMPUTER SCIENCE
FIFTH SEMESTER – APRIL 2012
CS 5402/5503 – OPERATIONS RESEARCH
Date : 27-04-2012 Dept. No. Max. : 100 Marks
Time : 1:00 – 4:00
PART-A
Answer ALL questions: 10 X 2=20
- Write a General form of LPP.
- What is optimal solution?
- Why we should prefer dual problem to solve LPP?
- Define traveling salesman problem.
- List out the methods of solving Transportation problem.
- Define Activity & Node
- What is a sequencing problem?
- What is setup cost?
- What is reordering level?
- When replacement is made?
PART-B
Answer All questions: 5 X 8=40
11 a) ) A Company produces refrigerators in unit I and heaters in unit II. The two
products are produced and sold in a weekly basis. Weekly production cannot
exceed 25 in unit I and 36 in unit II. Formulate this problem as an LP model
(OR)
11 b Solve the following l.p.p graphically.
Max Z = 10 x_{1} +15x_{2}
Subject to 2 x_{1} +x_{2 }≤ 26
2 x_{1} +4x_{2 }≤ 56
– x_{1} +x_{2 }≤ 5
_{ }x_{1} ,x_{2} ≥0
12 a) Construct the dual to the primal problem
Minimum Z = x_{1} +x_{2} +x_{3}
Subject to x_{1} –3x_{2 }+4 x_{3} _{ }= 5
x_{1} -2x_{2 }≤ 3
2 x_{2} – x_{3 }≥ 4
_{ }x_{1} ,x_{2} ≥0 x_{3} unrestricted in sign.
(OR)
12 b) Obtain the initial solution of the following transportation problem by the north-west corner rule and matrix minima given that (i) the requirements are 40, 90 and 100 units and (ii) the supply are 90, 70 and 70.
Source | |||
Destination | S1 | S2 | S3 |
D1 | 15 | 28 | 27 |
D2 | 24 | 24 | 25 |
D3 | 22 | 25 | 20 |
13 a) A department has five employees with five jobs to be performed . From past records, the time (in hours) that each man take to do each job is known and given in the table
Employee | ||||||
Jobs |
I | II | III | IV | V | |
A | 10 | 5 | 13 | 15 | 16 | |
B | 3 | 9 | 18 | 13 | 6 | |
C | 10 | 7 | 2 | 2 | 2 | |
D | 7 | 11 | 9 | 7 | 12 | |
E | 7 | 9 | 10 | 4 | 12 |
How should the jobs be allotted on per employee, so as to minimize the total number of hours
(OR)
13 b) Find the sequence that minimizes the total elapsed time required to complete the following tasks on two machines
Task : A B C D E F G H I
Machine I : 2 5 4 9 6 8 7 5 4
Machine II : 6 8 7 4 3 9 3 8 11
14 a) A project consists of a series of activities called A,B,..,I with the following relationship<X,Y means X and Y cannot start until W is completed with this notation construct a network diagram having the following constraints.
A<D,E; B,D<F; C<G; B<H; F,G<I;
Time: A B C D E F G H I
Activity:23 8 20 16 24 18 19 4 10
.
(OR)
14 b ) (i) Write down the difference between PERT & CPM. (4)
(ii) Define the following terms:
a)dummy activity b) total float .
15a) Manufacture has to supply 600 units of his product/year. Shortages are not allowed and storage cost amounts to Rs.0.60/unit/year.The set up cost/run is Rs.80.Determine(i) optimum run size (ii) the minimum average yearly cost.
(OR)
15 b) The annual demand for an item is 3200 units. The unit cost is Rs. 6/- and
inventory carrying charges 25% per annum. If the cost of one procurement is
Rs. 150/- determine (i) Economic order quality (ii) time between two
consecutive orders (iii) number of order per year (iv) the optimal total cost
PART-C
Answer any TWO 2 X 20=40
16 a) Use simplex method to solve the following L.P.P
Maximize Z = x_{1} +2x_{2}+x_{3}
Subject to 2 x_{1} +x_{2 }– x_{3 }≤ 2
-2 x_{1} +x_{2} -5x_{3 }≥-6
4 x_{1} +x_{2 }+x_{3 }≤ 6
_{ }x_{1} ,x_{2} ,x_{3}≥0
- b) Determine an initial basic feasible solution to the following transportation problem
by using (a) North west corner rule (b) Least cost method(c)Vogel’s
approximation.
Destination | ||||||
Source |
D1 | D2 | D3 | D4 | Supply | |
S1 | 21 | 16 | 15 | 3 | 11 | |
S2 | 17 | 18 | 14 | 23 | 13 | |
S3 | 32 | 27 | 18 | 41 | 19 | |
Demand |
6 |
10 |
12 |
15 |
17 a) Find the sequence that minimizes the total time required in performing the following job on three machines in order ABC .A processing time (in hours) are given in the following table.
Jobs :1 2 3 4 5
Machine A :8 10 6 7 11
Machine B :5 6 2 3 4
Machine C :4 9 8 6 5
- b) The project has the following time schedules.
Activity | 1-2 | 1-6 | 2-3 | 2-4 | 3-5 | 4-5 | 6-7 | 5-8 | 7-8 |
t_{0} | 3 | 2 | 6 | 2 | 5 | 3 | 3 | 1 | 4 |
t_{m} | 6 | 5 | 12 | 5 | 11 | 6 | 9 | 4 | 19 |
t_{p} | 15 | 14 | 30 | 8 | 17 | 15 | 27 | 7 | 28 |
- Draw the Project Network
- Find the critical path.
.
18 a) A stockiest has to supply 12,000 units of a product per year to his customer. The
demand is fixed and known and the shortage cost is assumed is to be infinite. The
inventory holding cost is Re.0.20 per unit per month and the ordering cost per order
is Rs.350. Determine the following
(i) The optimum lot size q_{0}
(ii) Optimum scheduling period t_{0}
(iii) Minimum total variable yearly cost.
- b) ) Given the following data:
Job | 1 | 2 | 3 | 4 | 5 | 6 |
Machine A | 12 | 10 | 9 | 14 | 7 | 9 |
Machine B | 7 | 6 | 6 | 5 | 4 | 4 |
Machine C | 6 | 5 | 6 | 4 | 2 | 4 |
Order of Processing : ACB
Determine the optimal sequence & the total elapsed time associated with it.
Latest Govt Job & Exam Updates: