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/users/2150/brian-borchers), "How to start the Simplex method from a feasible internal point?"