Simplex Method Questions and Answers

Q: At the current basic feasible solution (bfs) \(\mathbf{v}_{0}\) (\(\mathbf{v}_{0} \in \mathbb{R}^{5}\)), the simplex method yields the following form of a linear programming problem in standard form.minimize \(z = -x_{1} - 2x_{2}\)s.t. \(x_{3} = 2 + 2x_{1} - x_{2}\)\(x_{4} = 7 + x_{1} - 2x_{2}\)\(x_{5} = 3 - x_{1}\)\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \ge 0\)Here the objective function is written as a function of the non-basic variables. If the simplex method moves to the adjacent bfs \(\mathbf{v}_{1}\) (\(\mathbf{v}_{1} \in \mathbb{R}^{5}\)) that best improves the objective function, which of the following represents the objective function at \(\mathbf{v}_{1}\), assuming that the objective function is written in the same manner as above?

The objective at \(\mathbf{v}_{1}\) is \(z = -4 - 5x_{1} + 2x_{3}\).Both non-basic variables have negative coefficients in z, so increasing either one improves it. Find how far each can rise (ratio test) and the resulting z:Raising \(x_{2}\): \(x_{3} = 2 - x_{2} \ge 0\) gives \(x_{2} \le 2\), and \(x_{4} = 7 - 2x_{2}\) gives \(x_{2} \le 3.5\). So \(x_{2} = 2\), \(x_{3}\) leaves, and \(z = -4\).Raising \(x_{1}\): only \(x_{5} = 3 - x_{1}\) limits it, so \(x_{1} = 3\) and \(z = -3\).The best improvement is to bring in \(x_{2}\). From the \(x_{3}\) row, \(x_{2} = 2 + 2x_{1} - x_{3}\), and substituting:\[ \begin{aligned} z &= -x_{1} - 2(2 + 2x_{1} - x_{3}) \\ &= -4 - 5x_{1} + 2x_{3} \end{aligned} \]Option B is the objective after bringing in \(x_{1}\), the lesser improvement. Option C has the wrong leaving variable (\(x_{4}\) is not the binding constraint), and D has the wrong constant.

Q: The optimal solution of the linear programming problem is located :

The optimal solution lies at one of the corners of the feasible region.The feasible region of a linear programme is a convex polygon (polyhedron), and the objective function is linear. A linear function over such a region reaches its maximum or minimum at an extreme point, a vertex. That is the fundamental theorem of linear programming and the reason the simplex method moves from corner to corner.An interior point or the centre can never be strictly better than a vertex. When a whole edge is optimal, its two end corners are optimal too, so 'on the surface' adds nothing beyond the corner statement.

Q: Consider the LP problem :Max \(Z = 10x_{1} + 6x_{2}\)Subject to the constraints :\(5x_{1} + 3x_{2} \le 30;\)\(x_{1} + 2x_{2} \le 18\) and\(x_{1}, x_{2} \ge 0.\)Then the LP has :

The LP has multiple feasible solutions.The origin satisfies both constraints, so the feasible region is non-empty, and it is a polygon with vertices (0, 0), (6, 0), (6/7, 60/7) and (0, 9). Any non-empty polygon of positive area contains infinitely many feasible points.In fact the objective \(10x_{1} + 6x_{2} = 2(5x_{1} + 3x_{2})\) is parallel to the first constraint, so even the optimum (Z = 60) is reached along the whole edge from (6, 0) to (6/7, 60/7). The problem certainly has feasible solutions, more than one of them, and enough is known to say so.

Q: Which of the following statement/s is/are true for an LP problem ?(I) Every feasible solution is a basic feasible solution.(II) If there is a feasible solution, then there is a basic feasible solution.

The answer is only (II) is true.(II) is part of the fundamental theorem of linear programming: if a standard-form LP has a feasible solution, it has a basic feasible solution (and if it has an optimal solution, it has an optimal basic feasible solution).(I) is false: basic feasible solutions are the vertices of the feasible region, while points in the interior or along an edge are feasible but not basic. For example, with \(x_{1} + x_{2} \le 2\), the point (0.5, 0.5) is feasible but has no zero among the decision and slack variables that a basic solution in two dimensions would need.

Q: For an LP problem which of the following statements is false ?

The false statement is if an optimal solution exists, then the feasible region is bounded.An LP can have an optimal solution on an unbounded feasible region. For example, minimise \(x_{1} + x_{2}\) subject to \(x_{1}, x_{2} \ge 0\): the region is the whole first quadrant, which is unbounded, yet the minimum 0 is attained at the origin.The other statements are true. If the feasible polyhedron has an optimum, at least one vertex (basic feasible solution) is optimal. If the half-spaces of the constraints have empty intersection, there is no feasible point. And an intersection of half-spaces is convex, so the feasible set is convex.

Q: Which of the following is not true regarding the Karmarkar's algorithm ?

The statement that is not true is constraints are assumed to be non-homogeneous.Karmarkar's projective algorithm works with a problem in a special canonical form: minimise \(c'x\) subject to homogeneous constraints \(Ax = 0\), \(\sum x_{j} = 1\), \(x \ge 0\). The centre of the simplex, \(x = (1/n, \ldots, 1/n)\), is assumed to satisfy \(Ax = 0\), and the algorithm starts from this interior point, moving through the interior rather than along the edges.So (A) and (B) describe it, and, being a polynomial-time interior point method, it typically needs far fewer iterations on large problems (D). Non-homogeneous constraints are not part of its assumptions.

Q: Which of the following statements is true ?

The true statement is that the simplex method approaches the solution by moving from corner to corner along the edges.The simplex method starts at a vertex (basic feasible solution) of the feasible region and at each step moves along an edge to an adjacent vertex with a better objective value, stopping when no neighbouring vertex is better.It is not guaranteed to solve every problem: it can only report infeasibility or unboundedness, and without anti-cycling rules it can cycle. Searching through the interior of the region is what Karmarkar's interior-point algorithm (1984) does, so the second and third statements have the two methods the wrong way round.

In the context of operations research, the "Simplex Method" is primarily associated with solving which type of problems?

A.Linear Programming Problems
B.Dynamic Programming Problems
C.Network Flow Problems
D.Non-linear Optimization Problems

Exam Year(s)

DSSSB - 2023,

Answer: A

The simplex method is used for solving linear programming problems. It moves from one corner point of the feasible region to the next, improving the objective function, until the optimum is found. Dynamic programming, network flow problems and non-linear optimisation have other methods of solution, so they are not the problems of the simplex method.

Discuss in Forum

At the current basic feasible solution (bfs) \(\mathbf{v}_{0}\) (\(\mathbf{v}_{0} \in \mathbb{R}^{5}\)), the simplex method yields the following form of a linear programming problem in standard form.

minimize \(z = -x_{1} - 2x_{2}\)
s.t. \(x_{3} = 2 + 2x_{1} - x_{2}\)
\(x_{4} = 7 + x_{1} - 2x_{2}\)
\(x_{5} = 3 - x_{1}\)
\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \ge 0\)

Here the objective function is written as a function of the non-basic variables. If the simplex method moves to the adjacent bfs \(\mathbf{v}_{1}\) (\(\mathbf{v}_{1} \in \mathbb{R}^{5}\)) that best improves the objective function, which of the following represents the objective function at \(\mathbf{v}_{1}\), assuming that the objective function is written in the same manner as above?

A.\(z = -4 - 5x_{1} + 2x_{3}\)
B.\(z = -3 + x_{5} - 2x_{2}\)
C.\(z = -4 - 5x_{1} + 2x_{4}\)
D.\(z = -6 - 5x_{1} + 2x_{3}\)

Exam Year(s)

GATE ME - 2024,

Answer: A

The objective at \(\mathbf{v}_{1}\) is \(z = -4 - 5x_{1} + 2x_{3}\).

Both non-basic variables have negative coefficients in z, so increasing either one improves it. Find how far each can rise (ratio test) and the resulting z:

Raising \(x_{2}\): \(x_{3} = 2 - x_{2} \ge 0\) gives \(x_{2} \le 2\), and \(x_{4} = 7 - 2x_{2}\) gives \(x_{2} \le 3.5\). So \(x_{2} = 2\), \(x_{3}\) leaves, and \(z = -4\).
Raising \(x_{1}\): only \(x_{5} = 3 - x_{1}\) limits it, so \(x_{1} = 3\) and \(z = -3\).

The best improvement is to bring in \(x_{2}\). From the \(x_{3}\) row, \(x_{2} = 2 + 2x_{1} - x_{3}\), and substituting:

\[ \begin{aligned} z &= -x_{1} - 2(2 + 2x_{1} - x_{3}) \\ &= -4 - 5x_{1} + 2x_{3} \end{aligned} \]

Option B is the objective after bringing in \(x_{1}\), the lesser improvement. Option C has the wrong leaving variable (\(x_{4}\) is not the binding constraint), and D has the wrong constant.

Discuss in Forum

The optimal solution of the linear programming problem is located :

A.in the interior of the feasible region
B.at the center of the feasible region
C.at one of the corners of the feasible region
D.on the surface of the feasible region

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The optimal solution lies at one of the corners of the feasible region.

The feasible region of a linear programme is a convex polygon (polyhedron), and the objective function is linear. A linear function over such a region reaches its maximum or minimum at an extreme point, a vertex. That is the fundamental theorem of linear programming and the reason the simplex method moves from corner to corner.

An interior point or the centre can never be strictly better than a vertex. When a whole edge is optimal, its two end corners are optimal too, so 'on the surface' adds nothing beyond the corner statement.

Discuss in Forum

Consider the LP problem :

Max \(Z = 10x_{1} + 6x_{2}\)

Subject to the constraints :
\(5x_{1} + 3x_{2} \le 30;\)
\(x_{1} + 2x_{2} \le 18\) and
\(x_{1}, x_{2} \ge 0.\)

Then the LP has :

A.No feasible solution
B.Multi-feasible solutions
C.Unique feasible solution
D.Cannot say anything about solution

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The LP has multiple feasible solutions.

The origin satisfies both constraints, so the feasible region is non-empty, and it is a polygon with vertices (0, 0), (6, 0), (6/7, 60/7) and (0, 9). Any non-empty polygon of positive area contains infinitely many feasible points.

In fact the objective \(10x_{1} + 6x_{2} = 2(5x_{1} + 3x_{2})\) is parallel to the first constraint, so even the optimum (Z = 60) is reached along the whole edge from (6, 0) to (6/7, 60/7). The problem certainly has feasible solutions, more than one of them, and enough is known to say so.

Discuss in Forum

Which of the following statement/s is/are true for an LP problem ?

(I) Every feasible solution is a basic feasible solution.
(II) If there is a feasible solution, then there is a basic feasible solution.

A.only (I) is true
B.only (II) is true
C.both are true
D.neither (I) nor (II) is true

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The answer is only (II) is true.

(II) is part of the fundamental theorem of linear programming: if a standard-form LP has a feasible solution, it has a basic feasible solution (and if it has an optimal solution, it has an optimal basic feasible solution).

(I) is false: basic feasible solutions are the vertices of the feasible region, while points in the interior or along an edge are feasible but not basic. For example, with \(x_{1} + x_{2} \le 2\), the point (0.5, 0.5) is feasible but has no zero among the decision and slack variables that a basic solution in two dimensions would need.

Discuss in Forum

For an LP problem which of the following statements is false ?

A.If the feasible region is a polyhedron, then at least one basic feasible solution is optimal
B.If an optimal solution exists, then the feasible region is bounded
C.If the half spaces corresponding to the constraints do not intersect, the problem has no feasible solution
D.The set of all feasible solutions to the problem is a convex set

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The false statement is if an optimal solution exists, then the feasible region is bounded.

An LP can have an optimal solution on an unbounded feasible region. For example, minimise \(x_{1} + x_{2}\) subject to \(x_{1}, x_{2} \ge 0\): the region is the whole first quadrant, which is unbounded, yet the minimum 0 is attained at the origin.

The other statements are true. If the feasible polyhedron has an optimum, at least one vertex (basic feasible solution) is optimal. If the half-spaces of the constraints have empty intersection, there is no feasible point. And an intersection of half-spaces is convex, so the feasible set is convex.

Discuss in Forum

Which of the following is not true regarding the Karmarkar's algorithm ?

A.The algorithm starts with an interior point of the feasible region
B.One of the basic conditions is that \(x = \left(\frac{1}{n}, \frac{1}{n}, \ldots, \frac{1}{n}\right)\) satisfies the equation \(Ax = 0\).
C.Constraints are assumed to be non-homogeneous
D.The algorithm reduces the number of iterations

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The statement that is not true is constraints are assumed to be non-homogeneous.

Karmarkar's projective algorithm works with a problem in a special canonical form: minimise \(c'x\) subject to homogeneous constraints \(Ax = 0\), \(\sum x_{j} = 1\), \(x \ge 0\). The centre of the simplex, \(x = (1/n, \ldots, 1/n)\), is assumed to satisfy \(Ax = 0\), and the algorithm starts from this interior point, moving through the interior rather than along the edges.

So (A) and (B) describe it, and, being a polynomial-time interior point method, it typically needs far fewer iterations on large problems (D). Non-homogeneous constraints are not part of its assumptions.

Discuss in Forum

Which of the following statements is true ?

A.Simplex method is so robust that it is guaranteed to give the solution of any linear programming problem
B.Simplex method searches for the solution through interior of the feasible region
C.Karmarkar's algorithm searches for the solution through corner points of the feasible region
D.Simplex method approaches the solution by moving from corner to corner along the edges

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: D

The true statement is that the simplex method approaches the solution by moving from corner to corner along the edges.

The simplex method starts at a vertex (basic feasible solution) of the feasible region and at each step moves along an edge to an adjacent vertex with a better objective value, stopping when no neighbouring vertex is better.

It is not guaranteed to solve every problem: it can only report infeasibility or unboundedness, and without anti-cycling rules it can cycle. Searching through the interior of the region is what Karmarkar's interior-point algorithm (1984) does, so the second and third statements have the two methods the wrong way round.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Simplex Method Questions and Answers || Simplex Method MCQ Questions and Answers || Simplex Method GK Questions and Answers || Simplex Method GK MCQ Questions || Simplex Method Multiple Choice Questions and Answers || Simplex Method GK || GK on Simplex Method || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Simplex Method Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications