Linear Programming Terminology: Core Concepts Defined

Key Terms in Linear Programming & Optimization

Constraint

An equation or inequality that rules out certain combinations of decision variables as feasible solutions.

Problem Formulation

The process of translating a verbal statement of a problem into a mathematical statement called the mathematical model.

Mathematical Model

A representation of a problem where the objective and all constraint conditions are described by mathematical expressions.

Decision Variable

A controllable input for a linear programming model.

Objective Function

The expression that defines the quantity to be maximized or minimized in a linear programming model.

Nonnegativity Constraints

A set of constraints that requires all variables to be nonnegative.

Linear Program

A mathematical model with a linear objective function, a set of linear constraints, and nonnegative variables.

Linear Functions

Mathematical expressions in which the variables appear in separate terms and are raised to the first power.

Feasible Solution

A solution that satisfies all the constraints simultaneously.

Feasible Region

The set of all feasible solutions.

Slack Variable

A variable added to the left-hand side of a less-than-or-equal-to constraint to convert the constraint into an equality. The value of this variable can usually be interpreted as the amount of unused resource.

Standard Form

A linear program in which all the constraints are written as equalities. The optimal solution of the standard form of a linear program is the same as the optimal solution of the original formulation of the linear program.

Redundant Constraint

A constraint that does not affect the feasible region. If a constraint is redundant, it can be removed from the problem without affecting the feasible region.

Extreme Point

Graphically speaking, extreme points are the feasible solution points occurring at the vertices, or “corners,” of the feasible region. With two-variable problems, extreme points are determined by the intersection of the constraint lines.

Surplus Variable

A variable subtracted from the left-hand side of a greater-than-or-equal-to constraint to convert the constraint into an equality. The value of this variable can usually be interpreted as the amount over and above some required minimum level.

Alternative Optimal Solutions

The case in which more than one solution provides the optimal value for the objective function.

Infeasibility

The situation in which no solution to the linear programming problem satisfies all the constraints.

Unbounded Solution

The situation in which the value of the solution may be made infinitely large in a maximization linear programming problem or infinitely small in a minimization problem without violating any of the constraints.