What are the Constraints?

Constraints define the possible values the variables of a linear programming problem may take. They typically represent resource constraints, or the minimum or maximum level of some activity. They take the following general form:

where

Xi = the ith decision variable,
aj, i = the coefficient on Xi in constraint j, and
bj = the right-hand-side coefficient on constraint j.

Note that j is an index that runs from 1 to m, and each value of j corresponds to a constraint. Thus, the above expression represents m constraints (equations, or, more precisely, inequalities) with this form. Resource constraints are a common type of constraint. In a resource constraint, the coefficient aj, i indicates the amount of resource j used for each unit of activity i, as represented by the value of the variable Xi . The right-hand side of the constraint (bj ) indicates the total amount of resource j available for the project.

Note also that while the constraint above is written as a less-than-or-equal constraint, greater-than-or-equal constraints can also be used. A greater-than-or-equal constraint can always be converted to a less-than-or-equal constraint by multiplying it by -1. Similarly, equality constraints can be written as two inequalities -- a less-than-or-equal constraint and a greater-than-or-equal constraint.

Back to Section 1