Midpoint solutions to linear programs
First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want. 

Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...

==============

More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.

So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.

So, to summerize: 
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.