I have a task to write a dual program for the following primal:

maximize $x_1 + 2x_2 + 3x_4$

subject to

$x_2 - 6x_3 + x_4 \leq 4 $

$x_1 + 3x_2 - 3x_3 = 0$

$6x_1 - 2x_2 + 2x_3 - 4x_4 \geq 5$

$x_2 \leq 0$, $x_4 \geq 0$

However, $x_1$ and $x_3$ variables are not under a constraint (there is no limiting constraint $x_i \geq 0$ or $x_i \leq 0$ or $x_i \in \mathbb{R}$).

How should I proceed? Should I assume that $x_1, x_3 \in \mathbb{R}$ and put "=" signs to first and third constraints?

  • $\begingroup$ Write each of the free variables as a difference of two nonnegative decision variables, i.e. $x_i = x_i^+ - x_i^-$, where $x_i^+ = \max(x_i,0), x_i^- = \max(0,-x_i)$ to transform it to the canonical form that you're familiar with, and write the dual. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 14 '18 at 15:27
  • $\begingroup$ @GNUSupporter thank you for your response $\endgroup$ – Ros Fateev May 14 '18 at 15:30
  • $\begingroup$ The answer of GNU Supporter is if you want to put the problem in standard form (e.g., as preparation for the simplex method). Your suggestion to use "=" constraints is the right answer. $\endgroup$ – LinAlg May 15 '18 at 14:43
  • $\begingroup$ @LinAlg thank you for your response. I have decided to express variable in a similar way, that GNU Supporter has suggested, except I took both those variables non-negative(instead of "=max($x_i$, 0)"). In such way the flexibility remains: $x_i$ can still be any real number and all variables are bounded. $\endgroup$ – Ros Fateev May 24 '18 at 14:37

Your Answer

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

Browse other questions tagged or ask your own question.