Assuming finite optimal cost of a specific LP, find an optimal solution directly
Hint: Since there are $n+1$ constraints on $n$ variables, there is a solution in which all but one constraint are tight. You can calculate all these solutions explicitly ("on paper"), and choose the best one.