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 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\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, 2017 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$ May 18, 2017 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, 2017 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$ May 18, 2017 at 18:40
  • $\begingroup$ Great, thank you :) And @JeanMarie thanks for the nice edit! $\endgroup$
    – tenepolis
    May 18, 2017 at 18:49

You must log in to answer this question.

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