0
$\begingroup$

\begin{align} \text{maximize} &\quad x_1 +3x_2 & & \\ \text{subject to} &\quad x_1 - x_2 = 2 \\ & -2x_1 +3x_2 \ge 5 \\ & \quad\quad\quad x_2 \ge 0 \end{align}

I was able to find the dual LP, but I am not seeing any connections to the original LP. Can I get some pointers?

Find the dual LP.

I first converted the LP to standard form then introduced a new variable.

Let $x_1=r_1-r_2$ \begin{align} \text{minimize} &\quad 2r_1-2r_2 -5x_2 & & \\ \text{subject to} &\quad r1-r_2+2x_2\geq 1 \\ & -r1+r_2-2x_2\geq -1 \\ & -r1+r_2-3x_2\geq 3 \end{align}

What happens to an equality constraint in the primal when you translate to the dual?

What happens to a free variable in the primal when you translate to the dual?

$\endgroup$
1
  • $\begingroup$ Have your read the table I´ve posted here? I wonder why you cannot answer the questions by yourself. $\endgroup$ Commented Feb 19, 2021 at 8:19

1 Answer 1

2
$\begingroup$
  • An equality constraint in the primal corresponds to a free variable in the dual formulation.

  • A free variable in the primal corresponds to an equality constraint in the dual formulation.

$$\max x_1+3x_2$$

subject to $$x_1-x_2=2$$ $$-2x_1+3x_5 \ge 5$$ $$x_2 \ge 0$$

We can associate a dual variable $p$ to the first equation and $q$ to the second constraint. $p$ is a free variable.

Since $x_1$ is a free variable in the primal formulation, the corresponding constraint in the dual variable in an equality which is $p-2q=1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .