Working with constraints

Working with Constraints

Understanding Constraints

  • Constraints in linear programming are restrictions or limitations on the decision variables. They form the boundary for feasible solutions.

  • They must be expressed as linear inequalities or equations, where decision variables are combined additively with constants or coefficients.

  • Constraints can represent limited resources such as time, materials or money, or conditions that must be satisfied for a solution to be considered feasible.

Building Constraint Equations

  • Start by identifying all decision variables involved in the constraint. Remember that these are often quantities of items or resources you’re trying to optimise.

  • Then, translate the constraint information into mathematical terms. This could involve setting up a linear inequality that reflects the limitation or requirement at hand.

  • Be sure to consider what the inequality operator should be (less than, greater than, or equal to) based on the wording of the constraint.

  • Ensure that each constraint equation accurately represents the real-world restriction it’s based on.

Graphing Constraints

  • When working with two variables, each constraint can be graphed as a line on a two-dimensional plane.

  • Each constraint line effectively divides the graph into two halves: one half satisfies the constraint (the feasible half), and the other half doesn’t.

  • To determine which half-plane is feasible, choose a test point not on the line (typically the origin, if it’s not on the line) and substitute its coordinates into the inequality. If the inequality is satisfied, the half-plane containing the test point is the feasible one. If it’s not, the feasible half-plane is the one opposite to the test point.

  • Graph each constraint in this way, and the area/region where all the feasible half-planes overlap is the feasible region.

Handling Multiple Constraints

  • When dealing with multiple constraints, the feasible region is where all constraints are simultaneously satisfied.

  • In graphical terms, this is the area where all feasible half-planes overlap. It could be a polygon, a single half-plane, or even a single line or point, depending on the constraints.

  • The vertices or corner points of the feasible region (where two or more constraint lines intersect) often contain the optimal solution.

Working with constraints properly is vital not only for defining the feasible region correctly, but also for ensuring that the linear programming problem reflects its real-world counterpart with accuracy.