Linear Programming
Exam Duration: 45 Mins Total Questions : 20
In order the linear programming techniques provide valid results, then the
- (a)
relation between factors must be linear (positive)
- (b)
relation between factors must be linear (negative)
- (c)
results do not depend upon relation between factors
- (d)
Both (a) and (b)
In the graphical method of linear programming problem, every corner of the feasible polygon indicates
- (a)
optimum solution
- (b)
a basic feasible solution
- (c)
Both (a) and (b)
- (d)
None of the above
In simplex method of linear programming, the objective row of the matrix consists of
- (a)
slack variables
- (b)
coefficient of the objective function, which is the profit contribution per unit of each of the products
- (c)
names of the variables of the problem
- (d)
None of the above
Which of the following is not correct about LPP?
- (a)
All constraints must be linear relationships
- (b)
Objective functions must be linear
- (c)
All the constraints and decision variables must be of either \(\le\) or \(\ge\) type
- (d)
All decision variables must be non-negative
In the simplex method, infeasibility of a linear programming problem is indicated, when
- (a)
values of the index row, (cj - zj) under one or more of the non-base decision variables is/are zero
- (b)
value of index row, (cj - zj) indicate optimality with artificial variable in the base
- (c)
some of the values in constant column (bi) are zero
- (d)
all the replacement ratios, \({b_i\over a_{is}}\) (s is key column) are a negative
In the simplex method, the unbounded solution is indicated when
- (a)
value of index row (cj - zj), under one or more of the non-base decision variables is/are zero
- (b)
all the replacement ratios, \(({b_i\over a_{is}})\) (s indicates key column) are negative
- (c)
value of index row (Cj - Zj) indicate optimality with artificial variable in the base
- (d)
some of all values in the constant column (bi) are zero
In the simplex method, the existence of more than one optimum solution is indicated, when
- (a)
the index row (cj - Zj) under one or more of the non-base decision vanables is/are zero
- (b)
all the replacement ratios, \(({b_i\over a_{is}})\) (s indicates key column) are negative
- (c)
some of the values in constant column (bi) are zero
- (d)
All of the above
Dual of dual is
- (a)
primal
- (b)
dual
- (c)
either dual or primal
- (d)
None of these
The dual of the primal maximization LPP having m constraints and n non-negative variables should
- (a)
be a minimization LPP
- (b)
have n constraints and m non-negative variables
- (c)
Both (a) and (b)
- (d)
None of the above
If dual has an unbounded solution, primal has
- (a)
an unbounded solution
- (b)
an infeasible solution
- (c)
a feasible solution
- (d)
None of these
In a linear programming model, there are n variables and m constraints. The condition of degeneracy is that during an iteration, the total number of allocated base calls should
be
- (a)
equal to (m + n - 1)
- (b)
more than (m+ n-1)
- (c)
less than (m + n - 1)
- (d)
None of the above
In assignment model
- (a)
degeneracy always present in all the problems
- (b)
number of resources is equal to number of jobs
- (c)
only one unit from the ith source can be assigned to anyone of its destination
- (d)
All of the above
In a n x n matrix of an assignment problem, the optimality is reached when the minimum number of straight line scoring all the zeros is
- (a)
n
- (b)
\(1\over n\)
- (c)
n2
- (d)
None of these
Z = - x1 + 2x2 is subjected to the following constraints.
- x1 + 3x2 \(\le\) 10
x1 - x2 \(\le\) 2
x1 + x2 \(\le\) 6
x1, x2 \(\le\) 0
Minimum value of Z is
- (a)
\({20\over 3}\)
- (b)
6
- (c)
-2
- (d)
Zero
First of all, convert all inequalities into equation
-x1+3x2 = 10
x1 -x2 = 2
x1 +x2 = 6
Draw the lines
Now, find the values of A and B.
ForA,
-x1 + 3x2 = 10 ....(i)
-x1 +x2 = 6 ....(ii)
Adding Eq. (i) and Eq. (iii),
4x2 = 16
x2 = 4
x1 = 2
So, coordinates of point A are (2,4).
For B, x1 + x2 = 6
x1 -x2 = 2
2x1 = 8
x1= 4
and
x2 = 2
So, coordinates of point B is (4, 2).
Corner points are (0, 10/3), (4, 2), (2, 4) and (2, 0).
For minimize,
Z=-x1+2x2
At (0, 10/3),
Z= 0+2x\({10\over 3}={20\over 3}\)
At(4,2), Z=-4+4=0
At(2,4), Z=-2+8=6
At(2,0), Z=-2+2 x 0=-2.
Z = 2 x1 + 3x2 is subjected to constraints
x1 + x2 \(\le\)30
x1 - x2 \(\le\) 0
x2 \(\ge\) 0
x2 \(\ge\) 3
0 \(\le\) x1 \(\le\) 20
0\(\le\) x2 \(\le\) 12
The points at which maximum value of Z occurs, are
- (a)
(3,3)
- (b)
(20,10)
- (c)
(12, 12)
- (d)
(18, 12)
Corner points are (12, 12), (18, 12), (20, 10) and (20,0).
Maximize Z = 2x1+ 3x2
At (12, 12), Z = 24 + 36 = 60
At (20, 10), Z = 40 + 30 = 70
At (18, 12), Z = 36 + 36 = 72
At (20, 0), Z = 40 + 0 = 40
Hence, 72 the is maximum value corresponding to (18, 12).
If Z = x1 + x2 is subjected to constraints x1 + x2 \(\le\) 1, -3x1 + x2 \(\le\) 3 and x1 \(\le\) 0, X2\(\ge\) 0 then, the maximum value of Z occurs at
- (a)
\(({1\over2},{1\over2})\)
- (b)
(0,5)
- (c)
Infeasible solution
- (d)
None of these
x1 + x2 = 1
-3x1 +x2 = 3
There is no common region between given constraints. So, solution is infeasible.
Consider the linear programming:
Minimize Z = 4x1 + 6x2 + 18x3, subjected to constraints
x1 + 3x2 \(\ge\)3
x2 + 2x3 \(\ge\) 5
and x1, x2, x3\(\ge\) 0
Dual of this LPP is
- (a)
maximize Z = 3w1 + 5w2
w1 \(\le\) 4, w2 \(\le\) 9
3w1 + w2 \(\le\) 6
w1 w2 \(\ge\) 0 - (b)
maximize Z = 5w1 + 3w2
w1 \(\ge\)4, w2 \(\ge\) 9
3w1 + w2 \(\le\) 6
W1W2\(\ge\)0 - (c)
maximize Z = 3w1 + 5w2
w1 \(\le\)9, w2\(\le\) 4
w1+ 3w2\(\le\)6
w1, w2\(\ge\) 0 - (d)
None of the above
Constraints
x1 + 3x2 \(\ge\)3
x2 + 2x3 \(\ge\) 5
x1, x2, x3\(\ge\) 0
Minimize Z = 4x1 + 6x2 + 18x3
Dual is given by
Maximize Z = 3w1 + 5w2
Constraints
w1 \(\le\) 4, w2 \(\le\) 9
3w1 + w2 \(\le\) 6
w1 w2 \(\ge\) 0
There are 4 machines and 4 operators. Operator charges on different machines as
If one operator use one machine then, minimum cost to operate all machines is
- (a)
Rs. 21
- (b)
Rs.25
- (c)
Rs.26
- (d)
Rs.28
Step 1 Select least number in each row and subtract that number from all other elements.
I | II | III | IV | |
1 | 0 | 1 | 1 | 2 |
2 | 0 | 1 | 2 | 0 |
3 | 2 | 0 | 1 | 0 |
4 | 2 | 1 | 0 | 3 |
Step 2 Least element in each column subtract from other elements.
Operator | Charge on machine | |
1 | I | 6 |
2 | IV | 7 |
3 | II | 6 |
4 | III | 6 |
Minimum cost to operating all machine = (6 + 7 + 6 + 6) = Rs. 25
A company has one surplus truck in each of the cities A, 8, C and one deficit truck in each of cities P, Q, Rand S.The distance between cities in kilo metre is shown in matrix below. By assigning the trucks from cities is surplus to cities in deficits, If minimum distance is covered by vehicles.
P | Q | R | S | |
A | 7 | 5 | 10 | 17 |
B | 5 | 13 | 20 | 10 |
C | 6 | 5 | 3 | 8 |
Correct assigning orders is as
- (a)
A-P
B-Q
C-R - (b)
A-Q
B-P
C-S - (c)
A-Q
B-P
C-R - (d)
A-S
B-Q
C-P
P | Q | R | S | |
A | 7 | 5 | 10 | 17 |
B | 5 | 13 | 20 | 10 |
C | 6 | 5 | 3 | 8 |
P | Q | R | S | |
A | 7 | 5 | 10 | 17 |
B | 5 | 13 | 20 | 10 |
C | 6 | 5 | 3 | 8 |
D1 | 0 | 0 | 0 | 0 |
Step 1 It is not a square matrix because one row is less than the column so, add a dummy row.
Step 2 Select least element in each row and subtract it from other elements in that row. The number of lines is four, hence it is optimal condition.
Order is
A\(\rightarrow\)Q
B\(\rightarrow\)P
C\(\rightarrow\)R
D1\(\rightarrow\)S
A company has one surplus truck in each of the cities A, 8, C and one deficit truck in each of cities P, Q, Rand S.The distance between cities in kilo metre is shown in matrix below. By assigning the trucks from cities is surplus to cities in deficits, If minimum distance is covered by vehicles.
P | Q | R | S | |
A | 7 | 5 | 10 | 17 |
B | 5 | 13 | 20 | 10 |
C | 6 | 5 | 3 | 8 |
Minimum distance covered is
- (a)
15 km
- (b)
10 km
- (c)
12 km
- (d)
13 km
Minimum distance = 5 + 5 + 3
= 13 km