What is the optimal solution

Question

I am trying to maximize my objective function $$3x_1+5x_2$$ subject to \begin{align} x_1+2x_2&\leq5\\ x_1&\leq3\\ x_2&\leq2\end{align}

where $$x_1,x_2 \geq0 $$

so this is what I did \begin{align} x_3&=5-x_1-2x_1 \\ x_4&=3-x_1\\ x_5&=2-x_2\\ z&=3x_1+5x_2\end{align}

I chose $x_2$ since it has the bigger coefficient, then replaced $x_5$, resulting in

\begin{align}x_2&=2-x_5\\ x_3&=1-x_1+2x_5\\ x_4&=3-x_1\\ z&=10+3x_1-5x_5\end{align}

I then chose $x_1$ and replaced $x_3$ to get

\begin{align}x_1&=1-x_3+2x_5\\ x_2&=2-x_5\\ x_4&=2+x_3-2x_5\\ z&=13-3x_3+x_5\end{align}

I then chose $x_5$ and replaced $x_2$ to get \begin{align}x_5&=2-x_2\\ x_1&=5-2x_2-x_3\\ x_4&=-2+x_2+x_3\\ z&=15-x_2-3x_3\end{align}

However, the optimal solution is supposed to be $14$, where I should have replaced $x_4$ in my last iteration. I have no idea why was $x_4$ chosen over $x_2$, can someone help me?

Answer 1

My Solution : I prefer to solve these questions using coordinate geometry.

Let me change variables from $x_1$ and $x_2$ to $x$ and $y$ respectively, since it'll be easier then.

First inequality :

$x+2y \le 5$ This represents the following area in coordinate axes :

Another inequality :

$ 0 \le x \le 3$ , $0 \le y \le 2$

This bounds the reigon to the area enclosed by black line.

Now, notice another line $3x+5y=0$.The value $3x+5y$ represents the $ \sqrt{34} $ times the distance of a point $(x,y)$ from the line. (distance will be $\frac {3x+5y}{\sqrt{34}}$)

Therefore if distance is maximum, $3x+5y$ will be maximum.

Blue line is $3x+5y=0$

Now we have to find a point which lies in the reigon bounded by black lines, and is also farthest from the line(Perpendicular distance).

Obviously it's the point on the upper-right corner of the pentagon i.e. $(3,1)$

Now we are done.

You want $3x+5y$

$3\times3+5\times1$

$\max{(3x+5y)}=14$

Coming to your solution, I think we cannot solve using this approach because we cannot comment on the value of variables as they are dependent on each other too. (First inequality)

Therefore by your approach we can just get rough estimate of its maximum value, not exact.

Hope it helps!

Answer 2

Given the shape of the equations, the domain must be a rectangle from which the top-right corner has been cut out. As the coefficients of the objective function are both positive, the solution must be at one of the vertices of the cut.

We solve

$$x_1+2x_2=5, x_1=3\to\color{green}{(3,1)\to14},$$ and $$x_1+2x_2=5, x_2=2\to(1,2)\to13.$$