2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.