2
$\begingroup$

I have the linear programming problem as follows

maximise $f(x,y)=5x+2y$

subject to $x+3y \le 14$, $2x+y \le 8$, $x,y \ge 0$

If you solve this graphically then you can see a feasibility region with four extreme points, of which one of them is the optimal solution.

I am wondering if it is possible to show that there is EXACTLY one solution. I have been reading lots and found lots of proofs that if an optimal solution exists (which it does here), then there exists an optimal solution at an extreme point (vertex).

I have also found a theorem that says if the feasibility region is a compact convex set (which it is here), then the optimal solution is at a vertex.

I understand why none of these theorems state that the only optimal solution is at a vertex, as there are clearly cases where there are infinite optimal solutions on an edge between two extreme points. But that is not the case here as only one of the extreme points is an optimal solution.

It may not even be possible (I haven't been asked to do this so might be flogging a dead horse as they say), but is there any way to show that the point (4,0) (which is the optimal solution here) is the ONLY point where the objective function is maximised?

To explain what I mean further: I can prove that this is an optimal solution as I can prove that if an optimal solution exists, then there exists an optimal solution at an extreme point. And none of the other extreme points give the maximum value for the objective function. But how can I know for sure that the same maximum is not reached at some other point in the feasibility region (e.g. somewhere in the middle, or on a boundary line)? I can explain intuitively about contour lines etc. but I want to actually prove it.

Any ideas?

Thank you in advance!

$\endgroup$
  • $\begingroup$ A more visual solution is that if there is another optimal solution, all points on the line connecting two optimal solutions that are feasible are optimal. That line goes through $(4,0)$ and through another point at the boundary. If that point on the boundary is not a vertex, it is on a facet and its value is in between the two values at the corresponding vertices. The two corresponding vertices would then also have to be optimal. $\endgroup$ – LinAlg Nov 5 '18 at 16:46
0
$\begingroup$

Suppose $(x_2, y_2)$ is optimal as well and $x_2 = 4+\Delta_x, y_2 = 0+\Delta _y.$

Hence we have $$5(4+\Delta_x)+2(0+\Delta_y) = 5(4)+2(0) \iff5\Delta_x+2\Delta_y=0 \tag{1}$$

$$2(4+\Delta_x)+\Delta_y \le 8 \iff 2\Delta_x+\Delta_y \le 0 \tag{2}$$

$$(0+\Delta_y) \ge 0 \iff\Delta_y \ge 0 \tag{3}$$

From $(1)$, we have $\Delta_x=-\frac25 \Delta_y$, substitute this into $(2)$, we have

$$\frac{\Delta_y}5 \le 0$$

Together with $(3)$, we can conclude that $\Delta_y=0$ and hence $\Delta_x=0$.

Hence the solution is unique.

$\endgroup$
  • $\begingroup$ Thank you so much Siong, I love it! Sorry for the stupid question, but the triangle with the subscript x (for example), is that said as delta? And does it mean a translation of that amount in the x direction? Again, sorry, I have never learnt this $\endgroup$ – Josie Jones Nov 5 '18 at 12:59
  • $\begingroup$ Yup, it is the uppercase greek letter that is known as delta, which is commonly use to denote changes. I define $\Delta_x = x_2-x_1$ where $x_1$ is the $x$ coordinate of $(4,0)$ and $x_2$ is the $x$ coordinate of a possible alternative solution. $\endgroup$ – Siong Thye Goh Nov 5 '18 at 13:03
0
$\begingroup$

You need to show that none of the edges/faces with dimension $\ge1$ is perpendicular to the gradient of your function.

The gradient $\nabla f = (5, 2)$. Since we have only 2 variables, the region is 2-dimensional, a polygon. It has only 1-dimensional edges. Those edges have tangent vectors: $(3, -1)$, $(1, -2)$, $(0, 1)$, $(1,0)$. None of those dot-multiplied by $\nabla f$ give zero — none of them are perpendicular to gradient, so the optimum is located at vertex, and thus the problem has one solution.

$\endgroup$
  • $\begingroup$ Thank you Vasily, that is really very helpful. I have done very little with vectors so I have not seen the gradient of a function as a vector, or a tangent vector (although I have seen the dot product), but I will enjoy researching this further. However, this seems to only show that the optimal solution does not also lie on any of the edges. Is there also a way to show that it doesn't also lie somewhere within the feasibility region - for example in the middle? Obviously it doesn't, but how can I show this mathematically? Thanks again for your help! $\endgroup$ – Josie Jones Nov 5 '18 at 12:35

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.