Question about alternative optimal extreme points

linear programmingoperations researchoptimizationproof-verification

Could someone please check if what I've done is correct? And how could I answer b. ?

Thank you.

Consider the following

$$\max 2x+3y\\ s.t.\ \ x+y\le2\\ 4x+6y\le9\\ x,y\ge0$$

a. Sketch the feasible region

b.Find 2 alternative optimal extreme (corner) points.

c. Find an infinite class of optimal solutions.

Solution

a.enter image description here

b. What does it mean with '2 alternative optimal extreme (corner) points' ? From the region one can see only one corner point which is the origin.

c.There are 4 extreme points. Evaluating them in the objective function gives $z=\frac{9}{2}$ at $(0,3/2)$ and $(3/2,1/2), 0$ at $(0,0)$ and $4$ at $(2,0)$.

Hence the line containing $(0,3/2)$ and $(3/2,1/2)$ gives an infinite optimal solution.

Best Answer

On linear programming problems the optimal points are in the corners of the feasible region. If two optimal points are connected by a line, then that line gives infinite optimal points.

For point a), the sketch you make is right. Remember that corners do not need to be on a straight angle, so this region has four corners. We see that the four corners of the feasible region are:

  1. $(0,0)$ with $J(0,0)= 0$
  2. $(0,3/2)$ with $J(0,3/2)=9/2$
  3. $(3/2,1/2)$ with $J(3/2,1/2)= 9/2$
  4. $(2,0)$ with $J(2,0)=4$

Question b) asks you to find two vertices of the feasible region such that both are optimal. We see that the maximum happens on both $(0,3/2)$ and $(3/2,1/2)$. So those two are alternative extreme optimal points.

As for c), as you noted, the line connecting the points $(0,3/2)$ and $(3/2,1/2)$ contains infinitely many optimal points.