0
$\begingroup$

For the following linear programming, state its dual $(D_i)$ for $i=1,2$:

$$(P) \text{ } \text{ max}\left\{5x_1+6x_2 \mid \begin{matrix} -2x_1+x_2 \leq 2\\ -x_1+x_2 \leq 4\\ 2x_1+x_2 \geq 6\\ 2x_1-3x_2 \leq 6\\ x_1 \geq 0, x_2 \geq 0 \end{matrix}\right\}$$

I'm very confused because it's saying "for $i=1,2$". That means they are looking for $2$ dual linear programmings, I think.

Before I can form the LP, I need to make sure that the inequalities are fine, they must be all "$\leq$". So I change the third inequation to: $-2x_1-x_2 \leq -6$.

Now I write them as a matrix: $\begin{bmatrix} -2 & 1 & 2\\ -1 & 1 & 4\\ -2 & -1 & -6\\ 2 & -3 & 6\\ 5 & 6 & 0 \end{bmatrix}$. Now I need to transpose this matrix, I get: $\begin{bmatrix} -2 & -1 & -2 & 2 & 5\\ 1 & 1 & -1 & -3 & 6\\ 2 & 4 & -6 & 6 & 0 \end{bmatrix}$

Now I write this as a linear programming:

$$(D_1) \text{ } \text{ min}\left\{2y_1+4y_2-6y_3+6y_4 \mid \begin{matrix} -2y_1-y_2-2y_3+2y_4 \geq 5\\ y_1+y_2-y_3-3y_4 \geq 6 \end{matrix}\right\}$$


My question is if my work is correct at all and how $(D_2)$ is supposed to be different?

Edit: Here is a screenshot, maybe there is a misunderstanding with "for $i=1,2$"

enter image description here

$\endgroup$
1
$\begingroup$

You wrote the dual correctly - there is only one dual problem for each primal problem.

$\endgroup$
  • $\begingroup$ Oh thanks for your answer, I was afraid no one would react because this topic doesn't seem to be common / liked here. Glad I did it correctly till here :D Maybe you can tell me what $D_2$ means and how it could be solved? $\endgroup$ – tenepolis May 18 '17 at 18:26
  • $\begingroup$ This may depend on what your text/source says. I think this refers to the constraints in the dual problem, but I'm not sure. $\endgroup$ – Sean Roberson May 18 '17 at 18:30
  • $\begingroup$ I have added a screenshot of the task in my question. They probably take reference to the second part of the task, right? It's in German but maybe it's obvious by seeing? If not I will try to translate it precisely. $\endgroup$ – tenepolis May 18 '17 at 18:38
  • 2
    $\begingroup$ These are two separate problems. $D_1$ is the dual of $P_1$ and $D_2$ is the dual of $P_2$. $\endgroup$ – Sean Roberson May 18 '17 at 18:40
  • $\begingroup$ Great, thank you :) And @JeanMarie thanks for the nice edit! $\endgroup$ – tenepolis May 18 '17 at 18:49

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.