# Math Help - Linear Programming - Vertex Enumeration

1. ## Linear Programming - Vertex Enumeration

Hi, I have the following problem (I have scanned and attached a file of what I have got so far...but I really don't know what I am doing)... It says:

Write down the following LP problem in standard form by introducing slack variables $x_4$ and $x_5$. And also, use vertex enumeration to identify all vertices of the feasible region and, hence, determine an optimal solution to the problem.

maximise $f = -x_1 + 4x_2 + 5x_3$
subject to
$-x_1 + x_2 + 3x_3 <= 3$
$2x_2 + x_3 <= 8$
$x_1, x_2, x_3 >= 0$

So this is easy, I got:

maximise $f= -x_1 + 4x_2 + 5x_3$
subject to
$-x_1 + x_2 + 3x_3 + x_4 = 3$
$2x_2 + x_3 + x_5 = 8$
$x_1, x_2, x_3, x_4, x_5 >= 0$

So what I don't know is when a singular system is inconsistent (I've crossed through 2 rows, but I am not sure...), how you pick the values for the coordinates (there could be much more than 10 combinations and I don't know what I should look for)... and also, do I need to draw the LP problem to see which ones are feasible, or is there any other way I can work it out mathematically?

I would really appreciate it if you could give me a little explanation so that I can get this done before tomorrow