A linear program (LP) is a mathematical formulation of a problem. We define a set of decision variables which fully describe the decisions we wish to make. We then use these variables to define an objective function which we wish to minimize or maximize, and a set of constraints which restrict the decision options open to us. In a linear program, the variables must be continuous and the objective function and constraints must be linear expressions. An expression is linear if it can be expressed in the form c₁x₁ + c₂x₂ + ... + c_nx_n for some constants c₁, c₂, ... ,c_n. For example, 2x₁ + 7x₂ is a linear expression; x² and sin x are not.

We can think of an LP as having three sections, the objective function, the constraints and the sign restrictions on the decision variables.