Finding an optimal solution to a linear program among solutions of another

Question

I had the following question on my last Algorithms test which I didn't know how to solve, and the the professor didn't agree to publish the solution. I would like to know the solution though, since it's been bothering me not knowing.

I am given two linear programs with the same variables- $P_1, P_2$, both in standard form and it is known that $P_1$ has an optimal solution. Write a single linear program for the following problem: Find among all optimal solutions to $P_1$ which satisfy the restrictions of both $P_1,P_2$, a solution that maximizes the objective function of $P_2$.

Answer 1

Suppose $P_i$ is as follows:

$$\min c_i^Tx$$

subject to $$A_ix=b_i$$

$$x \ge 0$$

Let's write down the dual:

$$\max p^Tb_i$$

subject to $$p^TA_i=c_i^T$$

I would construct the following linear programming problem

$$\min c_2^Tx $$

subject to

$$c_1^Tx=p^Tb_1$$

$$A_1x=b_1$$

$$p^TA_1=c_1^T$$

$$x \ge 0$$

$$A_2x=b_2$$

Note that I have used duality theorem to ensure that the solution for the new system is an optimal solution to the first system.