My Dual Answer

Update: The question has been reopened.

I intended to answer 김종현’s problem on Math.SE. However, the programs in the question body aren’t typeset in MathJax. As a result, I downvoted and closed this question because found it unclear. From the proposed dual, it seems that I shouldn’t interpret the primal as a linear program. Anyways, without further clarifications from OP, I found no reason to look at this further. Here’s my intended answer:

First, you have to properly write the primal as

$$ \begin{alignedat}{8} \max \quad & z = & 3w_1 & + & 4 w_2 & + & 5w_3 & && \\ \text{s.t.} \quad & & w_1 & - & w_2 & & & - & \varepsilon_1 & & & & & \le 0 && \\ & & & & w_2 & - & w_3 & & & - & \varepsilon_2 & & & \le 0 && \\ & & & & & & w_3 & & & & & - & \varepsilon_3 & \le 0&& \\ & & & & & & & & 2\varepsilon_1 & + & 3\varepsilon_2 & + & 4\varepsilon_3 &\ge 1 && \\ & & w_1 & + & w_2 & + & w_3 & & & & & & & = 1, && \end{alignedat} $$

Your claimed dual

$$ \begin{array}{ll} \max & \varepsilon_1 r_1 + \varepsilon_2 r_2 + \varepsilon_3 r_3 + (2\varepsilon_1 +3\varepsilon_2 + 4\varepsilon_3) r_4 + r_5 \\ \text{s.t. } & x_1 + x_5 \le 3 \\ & x_2 \le 4 \\ & x_3 \le 5 \\ & r_4, r_5 \text{ free} \end{array} $$

is incorrect since it’s not a linear program.


1 comment

Your email address will not be published. Required fields are marked *.