Finding extreme points of linear programming problem in 3D

Question

I have the following linear programming problem:

max $z = 2x+4y$

subject to:

$5x + 3y + 5z \leq 15$

$10x + 8y + 15z \leq 40$

$x,y,z \geq 0$

I plotted the two lines in 3 dimensions but I am having trouble seeing where the extreme points would lie. Is there an algebraic way to find them?

Answer 1

First of all the $z$ variable has to be removed from the constraints. It can be substituted by $2x+4y$. Thus the problem becomes

max $z = 2x+4y$

subject to:

$15x + 23y \leq 15$

$40x + 68y \leq 40$

$x,y \geq 0$

$\small{\text{This problem is related to the original problem}}$

This problem can be solved $\textrm{graphically}$ ($2D$) or by applying the $\textrm{simplex algorithm}$.

Answer 2

Guide:

• Vertices and basic feasible solution are equivalent.

• You have $5$ inequalities , pick $3$ of them, set them to equality and solve them as a linear system. If the solution is unique and it doesn't violate the other $2$ equalities (that is it is a feasible point), then it is an extreme point.

Remark:

In general, we do not enumerate all extreme point to solve a linear program, simplex algorithm is a famous algorithm to solve a linear programming problem. In general, number of vertices is exponential and though in theory, the worst case complexity of simplex method can be to visit every vertices, this is rarely the case in practice. Interior point method exists to solve linear programming problem too.

Answer 3

If you don't know the simplex algorithm, add slack variables $s,t \ge 0$ to the original problem \begin{align} 5x_1 + 3x_2 + 5x_3 &\leq 15 \tag{$P_1$} \\ 10x_1 + 8x_2 + 15x_3 &\leq 40 \tag{$P_2$} \end{align} so that the two constraints (which represent the image under two planes in $\Bbb{R}^3$ in the first octant) becomes equalities. \begin{align} 5x_1 + 3x_2 + 5x_3 + s &= 15 \tag{$E_1$} \\ 10x_1 + 8x_2 + 15x_3 + t &= 40 \tag{$E_2$} \end{align} Since the objective function $z = 2x_1+4x_2$ has positive coefficients for $x_1$ and $x_2$, it's normal to set $x_3 = s = t = 0$, so that \begin{cases} 5x_1 + 3x_2 &= 15\\ 10x_1 + 8x_2 &= 40. \end{cases} Solving this so that $2x_2 = 10 \iff x_2 = 5$ and $x_1 = (15-3(5))/5 = 0$. So the maximum value is $z = 2(0) + 4(5) = 20$ when $x_1 = 0$ and $x_2 = 5$.