Gujarat University
MCA Semester IV
CBOM
Date: 22nd January, 1992 Marks: 50
Instructions:
1. Question no. 1 and 5 are compulsory.
2. From the rest of the questions in each section attempt any two.
3. Answer each section in separate answer books.
Section I
Q-1 (a) A machine tool company conducts a job-training program for machinists. Trained machinists are used as
teachers in the program at a ratio of one for every ten trainees. The training program lasts for one month.
From past experience it has been found that out of ten trainees hired, only seven complete the program
successfully (the unsuccessful trainees are released). [7]
Trained machinists are also needed for machining and the company’s requirements for the next three months are as follows:
January 100
February 150
March 200
In addition the company requires 250 trained machinists by April. There are 130 trained machinists available at the beginning of the year. Payroll costs peer month are:
Each trainee $400
Each trained machinist 700
(machining or teaching)
Each trained machinist idle 500
(Union contract forbids firing trained machinists)
Set up the linear programming problem that will produce the minimum cost hiring and training schedule and meet the company requirements.
(b) Consider the following problem: [2]
Max 3x1 + 4x2 + 6x3
S.t., x1 + x2 + x3 <=1 0
2x1 + 3x3 <=50
x3 >= 0 and x1and x2 are unconstrained in sign.
You know that simplex assume that all the variables are restricted in sign. How will you tackle this in the
above problem. Do not solve. Just formulate the new problem.
Q-2 (a) For a minimization problem of LP. Consider the following simplex problem: [6]
Cj 0 1 -3 0 2 0 ans
X1 x2 x3 x4 x5 x6
- x1 - 5/2 - ¼ 2 - 10
- x2 - -1/2 - ¼ 0 - 8
- x4 - -5/2 - -1/4 8 - 1
Zj - - - - - - -
Cj-Zj - - - - - - -
Complete the above simplex tableau by filling up the missing entries. Check whether the solution is
optimal or not. If not perform one more iteration and comment.
(b) “Assignment Model is a special case of Transportation model” comment. [2]
Q-3 (a) State the algorithm of Revised simplex. [3]
(b) Consider the following transportation problem: [5]
Destinations
Origins 1 2 3 4 ai
1 2 3 4 5 6
2 5 4 3 4 8
3 1 3 3 2 10
bj 4 6 8 6 24
Apply Vogel’s method to get the initial solution and the apply MODI method to find optimal solution.
Q-4 (a) Consider the following LP problem: [5]
Max Z = 3x1 + 5x2 + 6x3 + 8x4
S.t. x1 + 2x2 + 2x3 + 3x3 =8
2x1 + 5x3 + x4 >=4
3x1 + 2x2 + 2x3 + x4 <=13
x1, x2, x3 >= 0 and x4 is unconstrained in sign.
Set up the dual problem for the above and explain the interpretation of dual variables.
(b) Anand Metal Shop does custom metal working for a number of local customers. AMS has currently five
jobs to be done and have five machines to do them. The cost matrix gives the cost of processing each job on any machine. Because of specific job requirement and machine specifications, certain jobs cannot be done on certain machines. These have been shown by X in the cost matrix. The assignment of jobs to machines must be done on a one-to-one basis. The objective is to assign the jobs to the machines so as to minimize the total cost within the restrictions mentioned above. [3]
Cost matrix
Jobs
Machines 1 2 3 4 5
1 80 40 X 70 40
2 X 80 60 40 40
3 70 X 60 80 70
4 70 80 30 50 X
5 40 40 50 X 80
Section II
Q-5 Explain the following: [9]
1. Characteristics of queuing models
2. Slacks
3. Methodology of solving OR problems
Q-6 (a) Derive expressions for Po, Pn, Ls, Lq, Ws and Wq for (M/M/1) : (N/FCFS) (Notations are as usual).
[5]
(b) Customer arrive at a box office window, being manned by a single individual according to a Poisson
input process with a mean rate of 30 per hour. The time required to serve a customer has an exponential
distribution with a mean of 90 seconds. Find the average waiting time of a customer.
Also determine the average number of customers in the system queue length. [3]
Q-7 (a) Patients arrive at a clinic according to a Poisson distribution at the rate of 30 patients per hour. The
waiting room does not accommodate more than 14 patients. Examination time per patient is exponential
with mean rate 20 per hour. [4]
(i) Find the effective arrival rate at the clinic.
(ii) What is the probability that an arriving patient will not wait? Will he find a vacant seat in the room?
(iii) What is the expected waiting time until a patient is discharged from the clinic?
(b) What is crashing? State the algorithm used in algorithm. [4]
Q-8 (a) In the following table optimistic, most-likely and pessimistic times are respectively shown against each
connected activity from 10 to 100 in a project. Find the critical path by constructing a network. [4]
The scheduled completion time for the project is 4 days. Calculate the probability of finishing the project
within this time (given that 89.5% probability corresponds to a normal deviation of +1.25).
Activity Times Activity Times
10-20 4,8,12 20-30 1,4,7
20-40 8,12,16 30-50 3,5,7
40-50 0,0,0 40-60 3,6,9
50-70 3,6,9 50-80 4, 8,6
60-100 4,6,8 70-90 4,8,12
80-90 2,5,8 90-100 4,10, 16
(b) Construct the network diagram with the following relationship. Find the critical path: [4]
1. A and B are the first activities of the project
2. A and B precede C
3. C precedes D
4. B precedes E and F
5. F and C precedes G
6. E precedes H
7. H precedes I and J
8. D and J precedes K
9. K precedes L
10. G, I and L are terminal activities of the project
Activity A B C D E F G H I J K L
Duration 5 3 2 1 3 2 8 1 2 3 4 7
(weeks)
