Can someone explain this Linear Programming example's explanation?

Question

Can anyone explain part c) to me from this explanation? I don't understand how the author gets:

$x=\frac1b$ when $a>b$

and

$x=\frac1a$ when $b>a$

Intuitively I don't see how x can be used in both of those equations. I tried drawing it but I don't see the connection.

In my opinion there are infinite solutions on the line since there is only one constraint and there are no other constraints that intersect this constraint. Even when $a>b$ or $b>a$ since you still have the same number of constraints from the linear program.

Update

I just realized now why this didn't click with me as I wasn't properly understanding the linear program. My assumption was $x$ AND $y$ need to be maximized meaning whatever point on the line is a solution.

I was not thinking:

$result = x + y$

Maximize the $result$

Where an isosceles region has many solutions because all points on the line have the same $result$. And a scalene region has only one unique solution since it is the max $result$.

Answer 1

In the problem you have the constraints $x,y\geq0$ and $ax+by\leq1$. That means you have to search the solution in the triangle determined by the ordinate, the abscissa and the $ax+by=1$ line. Since you maximize $x+y$, this means you are looking for the point farthest from the origin point. This will be one of the other two vertices of this triangle, namely $(\frac{1}{a},0)$ and $(0,\frac{1}{b})$. If $a>b$, $\frac{1}{a}<\frac{1}{b}$, so you get $\frac{1}{b}$ as the maximum.

You are correct that infinite solutions exist on the line. All the points of the $(0,0)$,$(\frac{1}{a},0)$,$(0,\frac{1}{b})$ triangle are feasible solutions. However, since the triangle is a bounded polytope, it must take the optimal solutions in one of it's vertices, $(0,0),(0,\frac{1}{a})$ or $(\frac{1}{b},0)$.

Answer 2

I give you a numerical example where $a<b$. I present a graphical explanation as you tried.

$\texttt{max}\ z=x+y$

$2x+3y\leq 5$

$x,y\geq 0$

Now it can be solved graphically.

We solve the constraint for y: $y=\frac53-\frac23x$. You can draw that line.

We can solve the objective function as well.

$y=z-x$ Now you set z equal to 0.

$y=-x$

The line go through the origin with the slope $-1$. You need one more point to draw the line, for instance $P_2(-1,1)$. Now you have the objective function as a line with the initial level 0. This is the red line.

Then you push the left most blue line right upwards parallel until the line touches the feasible region (green) the $ \texttt{last time}$. The blue lines illustrates the process of moving the line upward. You see that it touches a corner. The optimal solution is $(x^*,y^*)=(2.5,0)$ lies on the x-axis.

Another case is if $a=b=2$. Then the solved equations are $y=\frac52-x$ and $y=-x$. Both have the same slope of $-1$. The graphical method can be seen in the next picture. At the end the objective function lies on the constraint. The optimal solutions are $(x^*,y^*)=\left(x,\frac{5}2-x\right) \ \forall \ 0\leq x\leq 2.5$.

Answer 3

Maximize $x+y$ subject to $ax+by\le 1, x\ge 0,y\ge 0$.

The LP has a finite optimal when a and b are positive. Suppose now $a > b$. Then, the optimal is clearly uniquely achieved at $x = 1/b$. Similarly, if $b > a$. the unique optimum is $x = 1/a$ . However, if $a = b$, then any positive pair $(x, y)$ such that $x + y = 1/a$ achieves the optimum. Hence, the optimum exists and is unique if and only if $a, b$ are positive and $a \ne b$.

Refer to the three cases:

$\hspace{1cm}$

The red areas are feasible regions. The black and blue lines are contour lines, in particular, the black lines are feasible and the blue lines are infeasible. The optimal points are when the contour line touches the feasible region from above.