LPP
Question 1 
In the Hungarian method for solving assignment problem, an optimal assignment requires that the maximum number of lines that can be drawn through squares with zero opportunity cost is equal to the number of:
rows or columns  
rows + columns  
rows + columns  1  
rows + columns + 1 
Question 1 Explanation:
In the Hungarian method for solving assignment problem, an optimal assignment requires that the maximum number of lines that can be drawn through squares with zero opportunity cost is equal to the number of rows or columns.
Question 2 
Consider the following transportation problem:
is degenerate solution  
is optimum solution  
needs to improve  
is infeasible solution 
Question 2 Explanation:
Step1: In vogel’s approximation method first find out the row difference(by calculating the difference between the two smallest values of that row) and column difference(by calculating the difference between the two smallest values of that row)
Then select the row having highest row difference and after selecting row choose the column/cell of that row having minimum value.
After that fulfill the demand by using supply from the selected row and column.
After that if demand becomes zero then delete that column and if the row become zero then delete that row and then repeat step 1.
Then select the row having highest row difference and after selecting row choose the column/cell of that row having minimum value.
After that fulfill the demand by using supply from the selected row and column.
After that if demand becomes zero then delete that column and if the row become zero then delete that row and then repeat step 1.
Question 3 
Given the following statements with respect to linear programming problem:
S 1 : The dual of the dual linear programming problem is again the primal problem
S 2 : If either the primal or the dual problem has an unbounded objective function value, the other problem has no feasible solution.
S 3 : If either the primal or dual problem has a finite optimal solution, the other one also possesses the same, and the optimal value of the objective functions of the two problems are equal.
Which of the following is true?
S 1 : The dual of the dual linear programming problem is again the primal problem
S 2 : If either the primal or the dual problem has an unbounded objective function value, the other problem has no feasible solution.
S 3 : If either the primal or dual problem has a finite optimal solution, the other one also possesses the same, and the optimal value of the objective functions of the two problems are equal.
Which of the following is true?
S 1 and S 2  
S 1 and S 3  
S 2 and S 3  
S 1 , S 2 and S 3 
Question 3 Explanation:
S 1 : TRUE: The dual of the dual linear programming problem is again the primal problem
S 2 : TRUE: If either the primal or the dual problem has an unbounded objective function value, the other problem has no feasible solution.
S 3 : TRUE: If either the primal or dual problem has a finite optimal solution, the other one also possesses the same, and the optimal value of the objective functions of the two problems are equal.
S 2 : TRUE: If either the primal or the dual problem has an unbounded objective function value, the other problem has no feasible solution.
S 3 : TRUE: If either the primal or dual problem has a finite optimal solution, the other one also possesses the same, and the optimal value of the objective functions of the two problems are equal.
Question 4 
Consider the following statements with respect to duality in LPP:
(a) The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.
(b) If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.
(c) If either problem has an unbounded optimal solution, then the other problem has no feasible solution at all. Which of the statements is (are) correct?
only (a) and (b)  
only (a) and (c)  
only (b) and (c)  
(a), (b) and (c) 
Question 4 Explanation:
Duality in LPP:
TRUE: The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.
TRUE: If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.
TRUE: If either problem has an unbounded optimal solution, then the other problem has no feasible solution at all.
TRUE: The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.
TRUE: If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.
TRUE: If either problem has an unbounded optimal solution, then the other problem has no feasible solution at all.
Question 5 
A basic feasible solution of an mXn TransportationProblem is said to be nondegenerate, if basic feasible solution contains exactly____number of individual allocation in ___positions
m+n+1, independent  
m+n1, independent  
m+n1, appropriate  
mn+1, independent 
Question 5 Explanation:
The initial solution of a transportation problem is said to be nondegenerate basic feasible solution if it satisfies:
→The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
→The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
→All the positive allocations must be in independent positions
A few terms used in connection with transportation models are defined below.
1. Feasible solution: A feasible solution to a transportation problem is a set of nonnegative allocations, xij that satisfies the rim (row and column) restrictions.
2. Basic feasible solution: A feasible solution to a transportation problem is said to be a basic feasible solution if it contains no more than m + n – 1 non – negative allocations, where m is the number of rows and n is the number of columns of the transportation problem.
3. Optimal solution: A feasible solution (not necessarily basic) that minimizes (maximizes) the transportation cost (profit) is called an optimal solution.
4. Nondegenerate basic feasible solution: A basic feasible solution to a (m x n) transportation problem is said to be non – degenerate if, the total number of nonnegative allocations is exactly m + n – 1 (i.e., number of independent constraint equations), and these m + n – 1 allocations are in independent positions.
5. Degenerate basic feasible solution: A basic feasible solution in which the total number of nonnegative allocations is less than m + n – 1 is called degenerate basic feasible solution.
Note: It is very standard and regular question and asked in UGCNET Dec2015 paper3
Refhttps://solutionsadda.in/ugcnetcs2015decpaper3/
→The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
→The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
→All the positive allocations must be in independent positions
A few terms used in connection with transportation models are defined below.
1. Feasible solution: A feasible solution to a transportation problem is a set of nonnegative allocations, xij that satisfies the rim (row and column) restrictions.
2. Basic feasible solution: A feasible solution to a transportation problem is said to be a basic feasible solution if it contains no more than m + n – 1 non – negative allocations, where m is the number of rows and n is the number of columns of the transportation problem.
3. Optimal solution: A feasible solution (not necessarily basic) that minimizes (maximizes) the transportation cost (profit) is called an optimal solution.
4. Nondegenerate basic feasible solution: A basic feasible solution to a (m x n) transportation problem is said to be non – degenerate if, the total number of nonnegative allocations is exactly m + n – 1 (i.e., number of independent constraint equations), and these m + n – 1 allocations are in independent positions.
5. Degenerate basic feasible solution: A basic feasible solution in which the total number of nonnegative allocations is less than m + n – 1 is called degenerate basic feasible solution.
Note: It is very standard and regular question and asked in UGCNET Dec2015 paper3
Refhttps://solutionsadda.in/ugcnetcs2015decpaper3/
Question 6 
Consider the following linear programming (LP):
The optimum value of the LP is
The optimum value of the LP is
23  
9.5  
13  
8 
Question 7 
If an artificial variable is present in the ‘basic variable’ column of optimal simplex table, then the solution is
Optimum  
Infeasible  
Unbounded  
Degenerate 
Question 8 
The occurrence of degeneracy while solving a transportation problem means that
total supply equals total demand  
total supply does not equal total demand  
the solution so obtained is not feasible  
none of these 
Question 8 Explanation:
The occurrence of degeneracy while solving a transportation problem means that the solution so obtained is not feasible.
Question 9 
Five men are available to do five different jobs. From past records, the time (in hours) that each man takes to do each job is known and is given in the following table :
Find out the minimum time required to complete all the jobs.
Find out the minimum time required to complete all the jobs.
5  
11  
13  
15 
Question 10 
In constraint satisfaction problem, constraints can be stated as __________.
Arithmetic equations and inequalities that bind the values of variables  
Arithmetic equations and inequalities that doesn’t bind any restriction over variables  
Arithmetic equations that impose restrictions over variables
 
Arithmetic equations that discard constraints over the given variables 
Question 11 
A basic feasible solution of a linear programming problem is said to be __________ if at least one of the basic variables is zero.
degenerate  
nondegenerate  
infeasible  
unbounded 
Question 11 Explanation:
Feasible Solution: The set of values of decision variables X_{j} (j = 1, 2, ... n) which satisfy all the constraints and nonnegativity conditions of a linear programming problem simultaneously is said to constitute the feasible solution to that problem.
Basic Solution: For a set of m simultaneous equations in n variables (n > m), a solution obtained by setting (n – m) variables equal to zero and solving for remaining m variables is called a “basic feasible solution”.
Basic Feasible Solution: A feasible solution to LP problem which is also the basic solution is called the “basic feasible solution”. Basic feasible solutions are of two types;
(a) Degenerate: A basic feasible solution is called degenerate if value of at least one basic variable is zero.
(b) Nondegenerate: A basic feasible solution is called ‘nondegenerate’ if all values of m basic variables are nonzero and positive.
Hence the correct option is option(A)
Basic Solution: For a set of m simultaneous equations in n variables (n > m), a solution obtained by setting (n – m) variables equal to zero and solving for remaining m variables is called a “basic feasible solution”.
Basic Feasible Solution: A feasible solution to LP problem which is also the basic solution is called the “basic feasible solution”. Basic feasible solutions are of two types;
(a) Degenerate: A basic feasible solution is called degenerate if value of at least one basic variable is zero.
(b) Nondegenerate: A basic feasible solution is called ‘nondegenerate’ if all values of m basic variables are nonzero and positive.
Hence the correct option is option(A)
Question 12 
Consider the following conditions:
(a)The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
(b)The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
(c)All the positive allocations must be in independent positions.
The initial solution of a transportation problem is said to be nondegenerate basic feasible solution if it satisfies:
(a)The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
(b)The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
(c)All the positive allocations must be in independent positions.
The initial solution of a transportation problem is said to be nondegenerate basic feasible solution if it satisfies:
(a) and (b) only  
(a) and (c) only  
(b) and (c) only  
(a), (b) and (c)

Question 12 Explanation:
The initial solution of a transportation problem is said to be nondegenerate basic feasible solution if it satisfies:
→The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
→The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
→All the positive allocations must be in independent positions.
→The solution must be feasible, i.e. it must satisfy all the supply and demand constraints.
→The number of positive allocations must be equal to m+n1, where m is the number of rows and n is the number of columns.
→All the positive allocations must be in independent positions.
Question 13 
Consider the following transportation problem:
The transportation cost in the initial basic feasible solution of the above transportation problem using Vogel’s Approximation method is:
The transportation cost in the initial basic feasible solution of the above transportation problem using Vogel’s Approximation method is:
1450  
1465  
1480  
1520 
Question 14 
The region of feasible solution of a linear programming problem has a _____ property in geometry, provided the feasible solution of the problem exists.
concavity  
convexity  
quadratic  
polyhedron 
Question 14 Explanation:
→ The region of feasible solution of an LP problem has a convexity property in geometry, provided the feasible solution of the problem exists.
→ The basic feasible solutions for a standard form LP are vertices for the convex set of feasible solution for the LP.
→ If an LP has a ﬁnite optimal objective function value, then the optimal value occurs at at least one basic feasible solution.
→ The basic feasible solutions for a standard form LP are vertices for the convex set of feasible solution for the LP.
→ If an LP has a ﬁnite optimal objective function value, then the optimal value occurs at at least one basic feasible solution.
Question 15 
Consider the following statements:
(a) Revised simplex method requires lesser computations than the simplex method.
(b) Revised simplex method automatically generates the inverse of the current basis matrix.
(c) Less number of entries are needed in each table of revised simplex method than usual simplex method.
Which of these statements are correct?
(a) Revised simplex method requires lesser computations than the simplex method.
(b) Revised simplex method automatically generates the inverse of the current basis matrix.
(c) Less number of entries are needed in each table of revised simplex method than usual simplex method.
Which of these statements are correct?
(a) and (b) only  
(a) and (c) only  
(b) and (c) only  
(a), (b) and (c) 
Question 16 
The following transportation problem: is
infeasible solution  
optimum solution  
nonoptimum solution  
unbounded solution 
Question 17 
Consider the following linear programming problem :
Max. z = 0.50 x_{2} – 0.10x_{1}
Subject to the constraints
2x_{1} + 5x_{2} < 80
x_{1} + x_{2} < 20
and x_{1}, x_{2} > 0
The total maximum profit (z) for the above problem is :
Max. z = 0.50 x_{2} – 0.10x_{1}
Subject to the constraints
2x_{1} + 5x_{2} < 80
x_{1} + x_{2} < 20
and x_{1}, x_{2} > 0
The total maximum profit (z) for the above problem is :
6  
8  
101  
12 
Question 18 
Consider the following statements :
(a) If primal (dual) problem has a finite optimal solution, then its dual (primal) problem has a finite optimal solution.
(b) If primal (dual) problem has an unbounded optimal solution, then its dual (primal) has no feasible solution at all.
(c) Both primal and dual problems may be infeasible.
Which of the following is correct ?
(a) If primal (dual) problem has a finite optimal solution, then its dual (primal) problem has a finite optimal solution.
(b) If primal (dual) problem has an unbounded optimal solution, then its dual (primal) has no feasible solution at all.
(c) Both primal and dual problems may be infeasible.
Which of the following is correct ?
(a) and (b) only  
(a) and (c) only  
(b) and (c) only  
(a), (b) and (c)

Question 19 
Consider the following statements :
(a) Assignment problem can be used to minimize the cost.
(b) Assignment problem is a special case of transportation problem.
(c) Assignment problem requires that only one activity be assigned to each resource.
Which of the following options is correct ?
(a) Assignment problem can be used to minimize the cost.
(b) Assignment problem is a special case of transportation problem.
(c) Assignment problem requires that only one activity be assigned to each resource.
Which of the following options is correct ?
(a) and (b) only  
(a) and (c) only  
(b) and (c) only  
(a), (b) and (c) 
Question 20 
Which of the following statements is true?
The sentence S is a logical consequence of S_{1},.., S_{n} if and only if S_{1} ∧ S_{2} ∧.... ∧ S_{n} → S is satisfiable.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧S_{n} → S is valid.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧ S_{n} ∧ S is consistent.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧ S_{n} ∧ S is inconsistent. 
Question 21 
A terror correcting qnary linear code must satisfy:
Where M is the number of code words and X is
Where M is the number of code words and X is
q^{n}  
q^{t}  
q^{n}  
q^{t} 
Question 22 
With respect to a loop in the transportation table, which one of the following is not correct?
Every loop has an odd no. of cells and at least 5.  
Closed loops may or may not be square in shape.  
All the cells in the loop that have a plus or minus sign, except the starting cell, must be occupied cells.  
Every loop has an even no. of cells and at least four. 
Question 23 
At which of the following stage(s), the degeneracy do not occur in transportation problem ? (m, n represents number of sources and destinations respectively)
(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n – 1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n – 1.
(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n – 1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n – 1.
(a), (b) and (c)  
(a), (c) and (d)  
(a) and (d)  
(a), (b), (c) and (d) 
Question 24 
Consider the following LPP :
Min. Z = X_{1} + X_{2} + X_{3}
Subject to 3X_{1} + 4X_{3} ≤ 5
5X_{1} + X_{2} + 6X_{3} = 7
8X_{1} + 9X_{3} ≥ 2,
X_{1}, X_{2}, X_{3} ≥ 0
The standard form of this LPP shall be :
Min. Z = X_{1} + X_{2} + X_{3}
Subject to 3X_{1} + 4X_{3} ≤ 5
5X_{1} + X_{2} + 6X_{3} = 7
8X_{1} + 9X_{3} ≥ 2,
X_{1}, X_{2}, X_{3} ≥ 0
The standard form of this LPP shall be :
Question 24 Explanation:
Question 25 
Which of the following is a valid reason for causing degeneracy in a transportation problem ?
Here m is no. of rows and n is no. of columns in transportation table
Here m is no. of rows and n is no. of columns in transportation table
When the number of allocations is m+n−1.  
When two or more occupied cells become unoccupied simultaneously.  
When the number of allocations is less than m+n−1.  
When a loop cannot be drawn without using unoccupied cells, except the starting cell of the loop. 
Question 26 
Consider the following LPP :
Max Z = 15x_{1} + 10x_{2}
Subject to the constraints
4x_{1 }+ 6x_{2 }≤ 360
3x_{1 }+ 0x_{2} ≤ 180
0x_{1 }+ 5x_{2} ≤ 200
x_{1}, x_{2} / 0
The solution of the LPP using Graphical solution technique is :
Max Z = 15x_{1} + 10x_{2}
Subject to the constraints
4x_{1 }+ 6x_{2 }≤ 360
3x_{1 }+ 0x_{2} ≤ 180
0x_{1 }+ 5x_{2} ≤ 200
x_{1}, x_{2} / 0
The solution of the LPP using Graphical solution technique is :
x_{1}=60, x_{2}=0 and Z=900  
x_{1}=60, x_{2}=20 and Z=1100  
x_{1}=60, x_{2}=30 and Z=1200  
x_{1}=50, x_{2}=40 and Z=1150 
Question 27 
Consider the following LPP :
Min Z = 2x1 + x2 + 3x3
Subject to :
x_{1} − 2x_{2} + x_{3 }≥ 4
2x_{1} + x_{2} + x_{3} ≤ 8
x_{1} − x_{3} ≥ 0
x_{1}, x_{2}, x_{3} ≥ 0
The solution of this LPP using Dual Simplex Method is :
Min Z = 2x1 + x2 + 3x3
Subject to :
x_{1} − 2x_{2} + x_{3 }≥ 4
2x_{1} + x_{2} + x_{3} ≤ 8
x_{1} − x_{3} ≥ 0
x_{1}, x_{2}, x_{3} ≥ 0
The solution of this LPP using Dual Simplex Method is :
x_{1}=0, x_{2=0, x3=3 and Z=9}  
x_{1}=0, x_{2}=6, x_{2}=0 and Z=6  
x_{1}=4, x_{2}=0, x_{2}=0 and Z=8  
x_{1}=2, x_{2}=0, x_{2}=2 and Z=10 
Question 28 
Which of the following statements is false about convex minimization problem ?
If a local minimum exists, then it is a global minimum  
The set of all global minima is convex set  
The set of all global minima is concave set  
For each strictly convex function, if the function has a minimum, then the minimum is unique 
Question 28 Explanation:
Properties of convex optimization problems:
1. Every local minimum is a global minimum
2. The optimal set is convex
3. If the objective function is strictly convex, then the problem has at most one optimal point.
These results are used by the theory of convex minimization along with geometric notions from functional analysis (in Hilbert spaces) such as the Hilbert projection theorem, the separating hyperplane theorem, and Farkas' lemma.
1. Every local minimum is a global minimum
2. The optimal set is convex
3. If the objective function is strictly convex, then the problem has at most one optimal point.
These results are used by the theory of convex minimization along with geometric notions from functional analysis (in Hilbert spaces) such as the Hilbert projection theorem, the separating hyperplane theorem, and Farkas' lemma.
There are 28 questions to complete.