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

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$$.

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.

• Thank you very much. :) – Tamir Shalev Sep 28 '19 at 8:13