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?

  • $\begingroup$ First of all you mixed up x,y and $x_1,x_2$. $\endgroup$ – callculus Mar 15 '17 at 13:40
  • $\begingroup$ great job picking up an obvious typo $\endgroup$ – Goodbye World Mar 15 '17 at 13:44
  • $\begingroup$ Can you just use the Corner Principle? There are only five to check. $\endgroup$ – Matthew Leingang Mar 15 '17 at 13:50
  • $\begingroup$ I was trying to use the Dantzig's pivot rule to solve this question $\endgroup$ – Goodbye World Mar 15 '17 at 13:52
  • 1
    $\begingroup$ It´s better to recognize an obvious error than do not recognize it. You are welcome. $\endgroup$ – callculus Mar 15 '17 at 14:04

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 :

$x+2y \le 5$

Another inequality :

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

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

enter image description here

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$

enter image description here

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

enter image description here

Now we are done.

You want $3x+5y$



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!


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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.