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](https://scicomp.stackexchange.com/questions/7616/how-to-start-the-simplex-method-from-a-feasible-internal-point/16268#16268), "How to start the Simplex method from a feasible internal point?"