Linear programming solve minimization as maximization

752 Views Asked by At

Given the following problem: $$max \ x_1 + x_2\\ s.t. \ x_1 \ge 0\\ x_2 \ge 0 \\ x_2 - x_1 \le 1 \\ x_1 + 6x_2 \le 15 \\ 4x_1 - x_2 \le 10$$ The result is 5 as shown here: https://i.stack.imgur.com/sLqpd.jpg
Why does the following hold? $$max \ x_1 + x_2 = min -(x_1 + x_2)$$ This means that the minimization problem result is $-5$, but it $0$. Having problems understanding this.

1

There are 1 best solutions below

0
On

The maximization problem: $$\text{Max} \ \ z=x_1+x_2 \ \ \text{subject to} \ \ \begin{cases} -x_1+x_2\le 1 \\ x_1+6x_2\le 1 \\ 4x_1-x_2\le 10 \\ x_1,x_2\ge 0\end{cases}$$ is equivalent to the minimization problem: $$\text{Min} \ \ z=-x_1-x_2 \ \ \text{subject to} \ \ \begin{cases} -x_1+x_2\le 1 \\ x_1+6x_2\le 1 \\ 4x_1-x_2\le 10 \\ x_1,x_2\ge 0\end{cases}$$ Indeed, while the feasible region (the pentagon) is the same for both problems, the largest value of $z=x_1+x_2$ occurs for $x_1+x_1=5$ and the smallest value of $z=-x_1-x_2$ occurs for $-x_1-x_2=-5$. Both problems produce the same solution $(x_1,x_2)=(3,2)$.