Simplex method barely giving the correct answer when using tableaus

  • Thread starter dane502
  • Start date
  • Tags
    Method
In summary, The conversation discusses solving a linear program using the simplex method and a tableau. The optimal objective value is found to be 41/4, however, when the optimal solution is inserted into the objective function, it does not yield the same value. It is determined that the correct answer is 10 and Bland's rule was used to choose the pivots.
  • #1
dane502
21
0

Homework Statement



I am trying to solve the follwing linear program

[tex]
\max \qquad 4x_1+x_2+3x_3
[/tex]
[tex]
\text{s.t }\qquad x_1+4x_2\qquad\,\leq1
[/tex]
[tex]
\quad\quad\quad\quad\quad\quad3x_1-x_2+x_3\leq3
[/tex]

The Attempt at a Solution


Using the simplex method and a tableau (negated objective function in the last row, right-hand side of constraints in the last column):

[tex]
\begin{matrix}
\textcircled{1}&4&0&1&0&1\\
3&-1&1&0&1&3\\\hline
-4&-2&-3&0&0&0
\end{matrix}
\rightarrow
\begin{matrix}
1&4&0&1&0&1\\
0&-13&\textcircled{1}&-3&1&0\\\hline
0&14&-3&4&0&4
\end{matrix}
\rightarrow
\begin{matrix}
1&\textcircled{4}&0&1&0&1\\
0&-13&1&-3&1&0\\\hline
0&-25&0&-5&3&4
\end{matrix}
\rightarrow
\begin{matrix}
1/4&1&0&1/4&0&1/4\\
13/4&0&1&1/4&1&13/4\\\hline
25/4&0&0&5/4&3&41/4
\end{matrix}
[/tex]

From which I conclude that the optimal objective value is 41/4
and the optimal solution is (0,1/4,13/4).

Inserting the optimal solution in the objective function does NOT yield 41/4.
It yields 10. I know from the textbook that the correct answer is 10, so my solution is correct. Can anyone explain then why my objective value in the tableau is not?
 
Last edited:
Physics news on Phys.org
  • #2
Please note that I have chosen my pivots by Bland's rule
 

FAQ: Simplex method barely giving the correct answer when using tableaus

Why is the simplex method not giving the correct answer when using tableaus?

The simplex method is an iterative algorithm used to solve linear programming problems. It works by moving from one feasible solution to another until the optimal solution is reached. However, in some cases, the algorithm may get stuck at a local optimum instead of the global optimum, resulting in an incorrect solution.

How can I ensure that the simplex method gives the correct answer when using tableaus?

To ensure the simplex method gives the correct answer, it is important to check for degeneracy, which occurs when the algorithm gets stuck at a corner point with multiple optimal solutions. In such cases, modifications to the algorithm, such as using a different pivot rule, can help find the global optimum.

What is a tableau in the simplex method?

A tableau is a tabular representation of a linear programming problem, with the objective function, decision variables, constraints, and slack variables listed in columns and rows. It is used in the simplex method to track changes in the objective function and decision variables as the algorithm progresses.

Can the simplex method give an incorrect answer even when using tableaus?

Yes, in rare cases, the simplex method can give an incorrect answer even when using tableaus. This can happen when the problem is degenerate or when there are errors in the formulation of the problem, such as incorrect coefficients or constraints. It is important to double-check the problem formulation and consider using a different algorithm if the results seem incorrect.

Are there any limitations to using the simplex method with tableaus?

While the simplex method is a powerful and widely used algorithm for solving linear programming problems, it does have some limitations. It may not be suitable for problems with a large number of decision variables or constraints, and it may struggle with non-linear or non-convex problems. In such cases, other optimization techniques may be more effective.

Back
Top