Roll No. …………………..

BCA–C-304
B. C. A. (Third Semester)
EXAMINATION, 2022-23
COMPUTER BASED OPTIMIZATION TECHNIQUES
1
Time : 22 Hours

Maximum Marks : 60
Note : All questions have to attempted.
Section—A

1. Choice the correct options : 1 each

(a) Identify the non-relevance characteristic of linear
programming : (CO1, BL-4)
(i) resources must be limited
(ii) only one objective function
(iii) parameters value remains constant during
the planning period
(iv) the problem must be of minimization type

P. T. O.
 [2] BCA–C-304

(b) Non-negativity condition is an important

component of LP model because : (CO3, BL-3)
(i) variables value should remain under the
control of the decision-maker
(ii) value of variables make sense and
correspond to real-world problems
(iii) variables are interrelated in terms of limited
resources
(iv) None of the above
(c) While plotting constraints on a graph paper,
terminal points on both the axes are connected by
a straight line because : (CO3, BL-3)
(i) The resources are limited in supply
(ii) The objective function is a linear function
(iii) The constraints are linear equations or
inequalities
(iv) All of the above
(d) For maximization LP model, the simplex method
is terminated when all values : (CO3, BL-2)
(i) cj − zj  0

(ii) cj − zj  0

(iii) cj − zj = 0

(iv) zj  0
 [3] BCA–C-304

(e) A variable which does not appear in the basic

variable (B) column of simplex table is :
(CO1, BL-3)
(i) Never equal to zero
(ii) Always equal to zero
(iii) Called a basic variable
(iv) None of the above
(f) If an artificial variable is present in the ‘basic
variable’ column of optimal simplex table, then
the solution is : (CO2, BL-3)
(i) Infeasible
(ii) Unbounded
(iii) Degenerate
(iv) None of the above
(g) The dual of the primal maximization LP problem
having m constraints and n non-negative variables
should : (CO3, BL-3)
(i) Have n constraints and m non-negative
variables
(ii) Be a minimization LP problem
(iii) Both (i) and (ii)
(iv) None of the above

P. T. O.
 [4] BCA–C-304

(h) Select the method used for solving an assignment

problem is called : (CO4, BL-4)
(i) Reduced matrix method
(ii) MODI method
(iii) Hungarian method
(iv) None of the above
(i) Identify the aim of a dummy row or column in an
assignment problem : (CO4, BL-4)
(i) To obtain balance between total activities
and total resources
(ii) To prevent a solution from becoming
degenerate
(iii) To provide a means or representing a
dummy problem
(iv) None of the above
(j) When the total supply is not equal to total
demand in a transportation problem then it is
called : (CO2, BL-3)
(i) Balanced
(ii) Unbalanced
(iii) Degenerate
(iv) None of the above
(k) Two person zero-sum game means that the :
(CO5, BL-3)
(i) Sum of losses to one player is equal to the
sum of gains to other
 [5] BCA–C-304

(ii) Sum of losses to one player is not equal to

the sum of gains to other
(iii) Both (i) and (ii)
(iv) None of the above
(l) When maximin and minimax values of the game
are same, then : (CO2, BL-3)
(i) no solution exists
(ii) solution is mixed
(iii) saddle point exists
(iv) None of the above

2. Attempt any four of the following : 3 each

(a) Illustrate the dual of a linear programming
problem. Elaborate the functional properties of
duality. (CO3, BL-3)
(b) Elaborate the difference between Assignment
Problem and Transportation Problem.
(CO4, BL-3)
(c) Discuss slack, surplus and artificial variables in a
linear programming problem. (CO1, BL-3)
(d) Briefly elaborate the assignment problems in OR
and applications of assignment in OR.
(CO4, BL-3)
(e) Discuss payoff matrix and types of strategy in
game theory. (CO5, BL-3)
P. T. O.
 [6] BCA–C-304

Section—B

3. Attempt any two of the following : 6 each

(a) A company sells two different products A and B,
making a profit of ` 40 and ` 30 per unit,
respectively. They are both produced with the
help of a common production process and are
sold in two different markets. The production
process has a total capacity of 30,000 man-hours.
It takes three hours to produce a unit of A and one
hour to produce a unit of B. The market has been
surveyed and company officials feel that the
maximum number of units of A that can be sold is
8,000 units and that of B is 12,000 units. Subject
to these limitations, products can be sold in any
combination. Formulate this problem as an LP
model to maximize profit. (CO3, BL-6)
(b) Apply the graphical method to solve the
following LP problem : (CO3, BL-4)
Minimize :
z = 3x1 + 2 x2
subject to the constraints
5x1 + x2  10 ,
x1 + x2  6 ,
x1 + 4x2  12
and x1, x2  0 .
 [7] BCA–C-304

(c) Consider the following traveling salesman

problem. Design a tour to five cities to the
salesman such that minimize the total distance.
Distance between cities is shown in the following
matrix : (CO5, BL-5)
1 2 3 4 5
1 – 10 3 6 9
2 5 – 5 4 2
3 4 9 – 7 8
4 7 1 3 – 4
5 3 2 6 5 –
4. Attempt any two of the following : 6 each
(a) Apply the simplex method to solve : (CO3, BL-4)
Max. :
z = 3x1 + 5x2 + 4x3
Subject to :
2x1 + 3x2  8
2x2 + 5x3  10
3x1 + 2x2 + 4x3  15
x1, x2 , x3  0 .
(b) Three sugar factories X, Y and Z located at
different places of the country produce 6, 4 and 5
lakh tones of sugar respectively. Under the
directive of the central government, they are to be
distributed to 3 States A, B and C as 5, 3 and 7

P. T. O.
 [8] BCA–C-304

lakh tones respectively. The transportation cost

per tones in rupees is given below :
A B C
X 11 17 16
Y 15 12 14
Z 20 12 15

Evaluate the suitable transportation pattern at

minimum cost by North West Corner method and
Vogel’s Approximation method. (CO2, BL-4)
(c) There are nine jobs, each of which must go
through two machines P and Q in the order PQ,
the processing times (in hours) are given below :

Job(s)
Machine A B C D E F G H I
P 2 5 4 9 6 8 7 5 4
Q 6 8 7 4 3 9 3 8 11
Find the sequence that minimizes the total
elapsed time T. Also calculate the total idle time
for the machines in this period. (CO5, BL-4)
5. Attempt any two of the following : 6 each
(a) Evaluate by Big M simplex method :
(CO3, BL-4)
Minimize :
Z = x1 + x2
 [9] BCA–C-304

Subject to :
2x1 + x2  4 ,
x1 + 7 x2  7 ,
x1, x2  0 .
(b) Determine the value of the game : (CO3, BL-4)
Player B
I II III IV
1 4 2 3 6
Player A 2 3 4 7 5
3 6 3 5 4
(c) A department of a company has five employees
with five jobs to be performed. The time (in hour)
that each employee takes to perform each job is
given in the effectiveness matrix :
Employees
I II III IV V
A 10 5 13 15 16
B 3 9 18 13 6
Jobs C 10 7 2 2 2
D 7 11 9 7 12
E 7 9 10 4 12
How should the jobs be allocated, one per
employee, so as to minimize the total man-hours ?
(CO4, BL-5)
BCA–C-304

P. T. O.