linear programming with logarithm

Question

max log $x_1$ + a log $x_2$

subject to

$2$$x_1$+ $x_2$ $\le 8$

$x_1$+$x_2$ $\le 5$

$x_1 \ge 0$ , $x_2 \ge 0$

i need to solve and show optimal solution when a =1

but how can i find it?

is it possible to use simplex method?

max log $x_1$ + 1 log $x_2$ + 0S1 +0S2

$2$$x_1$+ $x_2$ + S1= 8

$x_1$+$x_2$ +S2= 5

$x_1 \ge 0$ , $x_2 \ge 0$

i can count all possibility $4C2 = 6$ for $Ax=b$ so that $x=A^{-1}b$

i got that

(3,2,0,0), w=log 3+log2

(5,0,-2,0) , w=log 5-2

(4,0,0,1), w=log 4 + log 1

(0,5,3,0), w=log 5+3

(0,8,0,-3), w= log 8 - 3

(0,0,8,5), w= 8+5 =13

is this right? can i use simplex method ? but what is the coefficient?

Answer 1

The extreme points are $(0,0),(0,5),(3,2),(4,0)$. But unlike for linear programming, you cannot restrict your search for an optimal solution to these points. The level curves $x_1 x_2=k$ for the objective are rectangular hyperbolas, and the maximization means you want large $k$ (up and to the right). An optimal solution will appear on the boundary segments from $(0,5)$ to $(3,2)$ or from $(3,2)$ to $(4,0)$. On each of these two segments, you can eliminate one of the variables, reducing to a one-variable maximization:

• The segment from $(0,5)$ to $(3,2)$ is $x_1+x_2=5$, where $0 \le x_1 \le 3$. So $x_1 x_2 = x_1(5-x_1)$, which is maximized when $x_1=5/2$, yielding $(x_1,x_2)=(5/2,5/2)$, with objective value $(5/2)^2=25/4$.
• The segment from $(3,2)$ to $(4,0)$ is $2x_1+x_2=8$, where $3 \le x_1 \le 4$. So $x_1 x_2 = x_1(8-2x_1)$, which is maximized when $x_1=3$, yielding $(x_1,x_2)=(3,2)$, with objective value $3\cdot 2=6$.

Because $25/4>6$, we have found that $(x_1,x_2)=(5/2,5/2)$ is optimal.

Here's an animation to show the level curves $x_1 x_2=k$ for various values of $k$:

---

Here's a short alternative solution. By the AM-GM inequality: $$x_1 x_2 \le \left(\frac{x_1+x_2}{2}\right)^2 \le \left(\frac{5}{2}\right)^2 = \frac{25}{4},$$ and this upper bound is attained when $x_1=x_2=5/2$.