Linear Programming

Linear programming is a response to situations that require the maximization or minimization of certain functions which are subject to limitations. These limitations are called constraints.

Its use is common in industry applications such as economics, military strategy, etc.

Objective Function

Essentially, linear programming is to optimize (maximize or minimize) an objective function (a linear function of several variables):

f(x,y) = ax + by.


The objective function is subject to certain constraints, expressed by linear inequalities:

S a1x + b1y ≤ c1
a2x + b2y ≤c2
...  ... ...
anx + bny ≤cn

Each inequality constraint system determines a half-plane.

Linear Programming Graph

Feasible Solution

The intersection set of all half-planes is formed by the constraints which determine a site. This site is called the validity region or area of feasible solutions.

Feasible Solution Graph

Optimal Solution

The set of vertices of the enclosure is called a set of basic feasible solutions and the vertex which presents the optimal solution is called the maximum solution (or minimum).

Optimal Solution Graph