The basic problem in linear programming is:

max $ c^Tx $

$ Ax \leq b $

$ x \geq 0 $

But why does the condition have to $ \leq $ instead of $ \geq $ ? In fact, when considering the dual problem, it is $ \geq $ when it is a maximizing problem. I don't get it. For me it makes sense the other way around?

  • 1
    $\begingroup$ It is just the definition of the standard linear program. The definition itself has nothing to do with the dual program. $\endgroup$ – callculus Aug 10 '19 at 14:28
  • $\begingroup$ Mh, ok. Then disregarding the dual program: When maximizing something, shouldn't the target be greater than anything, thus, Ax>b ? $\endgroup$ – Ben Aug 10 '19 at 14:34
  • 1
    $\begingroup$ The basic idea is that you maximize an objective function. But if there are no constraints the program is unbounded. The bounds describe the area where the objective function cannot exceed. Intuitively the constraints should be $\leq$- constraints.But it is possible that one or more constraints are $\geq$ constraints. In this case you multiply the constraint by (-1) to obtain a $\leq$-constraint and obtain the standard linear program. $\endgroup$ – callculus Aug 10 '19 at 14:41
  • $\begingroup$ Yeah, sure, that makes sense. When all constraints would be > then the solution would be somewhere in the infinity(?). $\endgroup$ – Ben Aug 10 '19 at 14:48
  • 1
    $\begingroup$ That´s true, especially if all coefficients $a_{ij}$ and all $b_i$ are non-negative. $\endgroup$ – callculus Aug 10 '19 at 15:20

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.