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