0
$\begingroup$

Say you're given a linear program graphed with multiple constraints, and you're asked to identify which are binding, non binding or redundant just by looking at the graph.

A redundant constraint is easiest to see as it is one that does not contribute to the feasible region, but i'm struggling to determine what makes a constraint binding or non binding just from visual inspection.

I'm just after some clarification or a definition or something else to help me identify which is which.

$\endgroup$
3
$\begingroup$

Presumably this linear programming problem has two variables, so the graph is two-dimensional. Also I'm assuming these are inequality constraints. Thus the feasible region for the constraint consists of a line (where the two sides of the constraint are equal) and the half-space on one side of the line.

A redundant constraint is one whose removal would not change the feasible region. Thus if the line for the constraint doesn't touch the feasible region, it's certainly redundant. If the feasible region has an edge along the line for this constraint (and for no other constraints), it is not redundant. There are some other cases that are a bit trickier.

A binding constraint is one where some optimal solution is on the line for the constraint. Thus if this constraint were to be changed slightly (in a certain direction), this optimal solution would no longer be feasible. A non-binding constraint is one where no optimal solution is on the line for the constraint.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.