This is a classical problem in Linear Programming - to start a simplex method, one must find a vertex.
This is so-called "Phase I" of the simplex method, and without doubt the best ways to do this have been researched a lot. See e.g. what Brian Borchers wrote in scicomp, "How to start the Simplex method from a feasible internal point?"