I have this Primal problem:

$ Max \sum\limits_{i=1}^{50} X_iC_i \\ S.T.\\ \sum\limits_{i=1}^{50} X_iw_i\le W \\ \sum\limits_{i=1}^{50} X_iV_i\le V \\ X_i \le 1 \\ X_i \ge 0 \\ $

Now according the basic law of dual problems, the dual problem should be:

$ Min \; s \times W + r \times V+ \sum\limits_{i=1}^{50} t_i \\ S.T. \\ s \times w_i + r \times v_i + t_i \ge C_i \\ r,s,t_i\ge0 $

However according the the set of rules our TA gave us - the dual problem constraint inequality signs are set according to inequality sign limitation $X_1 \ge 0 \; or \; X_1 \le $ (the non-negativity constraints) in the primal problem. They told us that a $\ge$ sign in the primal constraints translate to $\le$ sign in the dual constraints and vice versa.

For example: If in the primal problem $ X_1 \ge 0$ then in the dual problem this translates to $ 2y_1 + 4y_2 \le 0 $

In my original problem my constraints variables in the primal problem have the $\ge$ sign, so I was thinking the constraint variables in the dual problem would have the $\le$ sign. In my problem, I thought that since $X_i \ge 0 $ then the dual problem constraint would be $s \times w_i + r \times v_i + t_i \le C_i $

But this is not the case, can you please explain to me how come?

In addition, they said the inequality constraints in the dual problem are set according the the inequality sign of of the primal problem. In that case, the inequality sign stays the same.

For example: if $ 2x_1 -x_2 \ge 2 $ in the primal problem then $ y_1 \ge 0 $ in the dual problem

In my original problem I have:

$ \sum\limits_{i=1}^{50} X_iw_i\le W \\ \sum\limits_{i=1}^{50} X_iV_i\le V \\ X_i \le 1 \\ $

According to what I was taught I expected the inequality constraints in the dual problem would be:

$ r,s,t_i \le0 $

Why is that not the case here?

We haven't learnt this subject in depth, so if you can, please keep your explanation as simple as possible for me . Thanks :)

  • $\begingroup$ In this answer I go step-by-step through an explanation of where the dual problem comes from, together, with a summary of the primal-dual relationships at the end. Perhaps that would be helpful. $\endgroup$ Feb 2, 2013 at 20:48


You must log in to answer this question.

Browse other questions tagged .