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!
Best Answer
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.