I am stuck on the following linear programming problem:
If P and Q are two n-dimensional polyhedra
Devise a linear programme such that:
If P ∩ Q is nonempty, return a point in P ∩ Q Else: LP is infeasible.
I might be trivializing the problem but wouldn't the LP:
min (or) max x such that x is contained in P and Q (the feasible region will be defined by the polyhedron P and Q) work?
"min (or) max x such that x is contained in P and Q (the feasible region will be defined by the polyhedron P and Q) work?" : yes, this is what you want. Can you write this in mathematical terms ?
Let $P = \{x\in \mathbb{R}^n\;|\;Ax=b\}$ and $Q = \{x\in \mathbb{R}^n\;|\;Cx=d\}$. $P \cap Q$ is non empty if the system of equations $$ \left\{ \begin{array}{ll} Ax=b\\ Cx=d\\ x\in \mathbb{R}^n \end{array} \right. $$ has a solution. As you suggested, you can maximize or minimize any dummy function over this domain to find a feasible solution.