linear programming

linear programming is a mathematical technique for mathematical optimization of a linear objective function that is subject to linear equality and linear inequality constraints. It is a special case of constrained, convex optimization, which implies that

• The objective function is convex
• The feasible region, defined by linear constraints, is a convex polyhedron (a convex set). This means that any local optimum is also a global extremum, which is a characteristic of convex optimization problems.

Why convex?

Why Linear Objective Functions are Convex

A linear function is convex because it satisfies the definition of convexity:

For any two points and and any such that ,

Since this holds for any and any , the function is convex. In fact, a linear function is also concave, so it is both convex and concave (affine).

Why Feasible Sets in Linear Programs are Convex

The feasible set of a linear program is defined by a set of linear constraints:

Each inequality constraint defines a half-space in . A half-space is a convex set because for any two points and that satisfy the constraint , any convex combination for will also satisfy the constraint:

Since the intersection of convex sets is also convex, the feasible set defined by the intersection of multiple linear constraints is convex.

Standard form of linear program

Standard form of linear programming has a maximization objective function and requires all decision variables to be non-negative.

• is the vector of decision variables
• is the vector of coefficients for the objective function.
• is the matrix representing the coefficients of the constraints.
• is the vector representing the right-hand side of the constraints.

Example: A company produces two products, and . Each product requires a certain amount of resources, and the company aims to maximize its profit given resource constraints. Convert to standard LP form

Objective Function: Maximize profit, where:

Here, and represent the number of units of and produced, respectively.

Constraints:

1. Production constraint for Resource A:
2. Production constraint for Resource B:
3. Non-negativity constraint:

Convert to Standard LP Form:

To put this in the standard form, we need to express it as a minimization problem. We can convert maximization to minimization by negating the objective function.

Standard Form: Maximize:

Subject to:

Convert a linear program to standard form

(Camarena, n.d.)

Change minimizing the objective function , to maximizing

Change lower-bound constraint to upper-bound constraint by flipping signs on two sides

An equality  is equivalent to the system of inequalities  and 

A variable is not constrained to be non negative (i.e. there is no ). A good strategy is introducing new variables since the difference between two non-negative variables and could have any sign. Substitute these new variables into the objective function and constraints.

Augmented form (with slack variables)

Use slack variables to turn inequality constraints into equality constraints

Solution characteristics

Solution exists

• If exists, the global optimum is generally located at one of the vertices of the feasible region (convex polyhedron)

No solution exists

• When the feasible region is empty i.e. some constraints are contradictory
• When the feasible region is unbounded in the direction where the objective function is maximized