Simplex Method Giving Right Solution, Wrong Value (REPOST)

[dane502]

Two days ago I posted a similar post in the "Calculus & Beyond Forum", but I guess that this forum is more appropriate - any admin should correct me if I am wrong..

Homework Statement

I am trying to solve the follwing linear program


$$\max \qquad 4x_1+x_2+3x_3$$
$$\text{s.t }\qquad x_1+4x_2\qquad\,\leq1$$
$$\text{ }\qquad \quad3x_1-x_2+x_3\leq3$$

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)
$$\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}$$

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?

 

[KataKoniK]

Thank you for posting this problem in our forum. The problem you have presented is indeed a linear program, and the simplex method is an appropriate method to solve it. Your approach and calculations are correct, and you have correctly identified the optimal solution as (0,1/4,13/4) with an optimal objective value of 41/4.

However, when you insert this solution into the objective function, you are not taking into account the constraints of the problem. The objective function is only optimized when all constraints are satisfied. In this case, when you insert the solution into the objective function, you are not taking into account the constraint x1+4x2≤1.

To find the actual optimal objective value, you need to check if the solution satisfies all constraints. In this case, the solution (0,1/4,13/4) does not satisfy the first constraint x1+4x2≤1, which means that it is not a feasible solution. Therefore, the actual optimal objective value is 10, as stated in the textbook.

I hope this explanation helps clarify the discrepancy between your calculated optimal objective value and the textbook's stated optimal objective value. Keep up the good work and keep practicing solving linear programs!