'Optimal Solution' term explanation in maximization problem

Question

I have a problem in linear programming which says

$2 * x_1 + 2 * x_2 -> max$

Then gives these conditions

$x_1 + x_2 - x_3 \le 2$

$2x_1 + x_2 - 2x_3 \le 3$

$x \ge 0$

Now I need to prove that $x=(1,1,0)$ is an optimal solution.

I've constructed coresponding minimalization problem by->min this way $Ay \ge c$ and $y \ge 0$ where $c= (2,1,0), b = (2,3), A$ is a matrix$$A = \begin{bmatrix}1&2\\1&1\\-1&-2\end{bmatrix}$$and solved this graphically. Now I can't understand what does 'optimal solution' mean. What I have to do in order to prove that $x=(1,1,0)$ is an optimal solution or is not.

Thanks for your time!

Answer 1

Well if you're trying to maximise $2x_1+2x_2$ then an optimal solution is a value of x for which $2x_1+2x_2$ is maximal. "Optimal" means best, so it should be the x that gives you the best possible value.

So to prove it, you need to prove that any other value of x gives you a value less than 2*1+2*1=4.

As currently written this isn't true, since x = (50, 50, 100) fits the constraints and would give a higher value of 2*50 + 2*50 = 200, and in fact there is no optimal value under those constraints. But I suspect this may be because there's an error in your copying of the question. If for instance there was plus instead of the minus signs in the constraints then your current solution would be an optimal solution.

Answer 2

Guide:

• Optimal means it is the best value with respect to the objective value that you are considering. In this case, the objective value is the maximum.

• You can use duality theorem of linear programming.

• Exhibit a solution for the dual solution that attains the same value as the primal solution, then it proves that both primal and dual are optimal.