Linear Programming Formulation Questions and Answers

Q: In graphical solution method of LPP, the redundant constraint is the one :

A redundant constraint is one which does not form the boundary of the feasible region.In the graphical method, the feasible region is the intersection of all the constraint half-planes. A constraint is redundant when the other constraints already imply it: its line lies wholly outside the feasible region, so removing it leaves the region unchanged and it contributes no edge.Constraints whose lines do form the boundary are binding somewhere and are not redundant. Optimising the objective is a property of points (vertices), not of constraints, so the last two options do not describe redundancy.

21.

In graphical solution method of LPP, the redundant constraint is the one :

A.Which forms the boundary of the feasible region
B.Which does not form the boundary of the feasible region
C.Which does not optimize the objective function
D.Which optimizes the objective function

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: B

A redundant constraint is one which does not form the boundary of the feasible region.

In the graphical method, the feasible region is the intersection of all the constraint half-planes. A constraint is redundant when the other constraints already imply it: its line lies wholly outside the feasible region, so removing it leaves the region unchanged and it contributes no edge.

Constraints whose lines do form the boundary are binding somewhere and are not redundant. Optimising the objective is a property of points (vertices), not of constraints, so the last two options do not describe redundancy.

Discuss in Forum

22.

In a Linear Programming Problem, suppose there are 3 basic variables and 2 non-basic variables, then the possible number of basic solutions are

A.6
B.8
C.10
D.12

Exam Year(s)

UGC NET - 2012,

Answer: C

A linear programming problem with 3 basic variables and 2 non-basic variables has 5 variables in all, so the number of constraints is 3, one for each basic variable. A basic solution is found by choosing 3 of the 5 variables as basic and setting the other two to zero, and the possible number of such choices is

\[ \binom{5}{3} = \frac{5!}{3!\,2!} = 10 \]

The options 6, 8 and 12 do not equal this count. The keyed answer is 10.

Discuss in Forum

23.

If dual has an unbounded solution, then its corresponding primal has

A.no feasible solution
B.unbounded solution
C.feasible solution
D.none of these

Exam Year(s)

UGC NET - 2012,

Answer: A

If the dual problem has an unbounded solution, then the primal problem has no feasible solution. By the duality theorem, a feasible primal with a bounded objective gives a dual with the same optimum, and if one problem is unbounded, the other cannot have any feasible point at all. A primal with an unbounded solution would need the dual to be infeasible, which is the converse, and a feasible primal would force a bounded dual. The keyed answer is no feasible solution.

Discuss in Forum

24.

The feasible region represented by the constraints \(x_{1} - x_{2} \le 1\), \(x_{1} + x_{2} \ge 3\), \(x_{1} \ge 0\), \(x_{2} \ge 0\) of the objective function Max \(Z = 3x_{1} + 2x_{2}\) is

A.A polygon
B.Unbounded feasible region
C.A point
D.None of these

Exam Year(s)

UGC NET - 2012,

Answer: B

The constraints are \(x_{1} - x_{2} \le 1\), \(x_{1} + x_{2} \ge 3\) and both variables non-negative. Along the line \(x_{1} - x_{2} = 1\), the point \((x_{2} + 1, x_{2})\) satisfies the second constraint once \(x_{2} \ge 1\) and can be taken as large as one pleases, so the feasible region extends without limit and no constraint closes it. It is therefore an unbounded feasible region, option (B), not a polygon or a single point, which are bounded.

Discuss in Forum

25.

Given the problem to maximize \(f(x)\), X = \((x_{1}, x_{2}, \ldots, x_{n})\) subject to m number of inequality constraints

\(g_{i}(x) \le b_{i},\ i = 1, 2, \ldots, m\)

including the non-negativity constraints \(x \ge 0\). Which of the following conditions is a Kuhn-Tucker necessary condition for a local maxima at \(\bar{x}\) ?

A.\(\dfrac{\partial L(\bar{X}, \bar{\lambda}, \bar{S})}{\partial x_{j}}\) = 0, j = 1, 2 \(\ldots\) m
B.\(\bar{\lambda}_{i}\,[g_{i}(\bar{X}) - b_{i}] = 0\), i = 1, 2 \(\ldots\) m
C.\(g_{i}(\bar{X}) \le b_{i}\), i = 1, 2 \(\ldots\) m
D.All of these

Exam Year(s)

UGC NET - 2013,

Answer: D

All of the listed conditions are Kuhn-Tucker necessary conditions for a local maximum, so the answer is All of these. For a problem of maximizing \(f(x)\) subject to \(g_{i}(x) \le b_{i}\), the conditions are: the stationarity condition, in which the partial derivatives of the Lagrangian with respect to each \(x_{j}\) vanish (option A); complementary slackness, \(\bar{\lambda}_{i}[g_{i}(\bar{X}) - b_{i}] = 0\) (option B); and feasibility of the point, \(g_{i}(\bar{X}) \le b_{i}\) (option C).

Because each of A, B and C is one of these necessary conditions, no single one of them is the only correct choice.

Discuss in Forum

26.

The following Linear Programming problem has :

\(\text{Max}\quad Z = x_{1} + x_{2}\)

Subject to \(x_{1} - x_{2} \ge 0\)
\(3x_{1} - x_{2} \le -3\)
and \(x_{1}, x_{2} \ge 0\)

A.Feasible solution
B.No feasible solution
C.Unbounded solution
D.Single point as solution

Exam Year(s)

UGC NET - 2013,

Answer: B

The problem has no feasible solution. The first constraint gives \(x_{1} \ge x_{2}\). The second gives \(x_{2} \ge 3x_{1} + 3\). Combining them, \(x_{2} \ge 3x_{1} + 3 \ge 3x_{2} + 3\), so \(-2x_{2} \ge 3\), that is \(x_{2} \le -1.5\). This contradicts \(x_{2} \ge 0\).

With the feasible region empty, there is no feasible point, no unbounded direction and no single optimal point. So options A, C and D are all ruled out.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Linear Programming Formulation Questions and Answers || Linear Programming Formulation MCQ Questions and Answers || Linear Programming Formulation GK Questions and Answers || Linear Programming Formulation GK MCQ Questions || Linear Programming Formulation Multiple Choice Questions and Answers || Linear Programming Formulation GK || GK on Linear Programming Formulation || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Linear Programming Formulation Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications