Definitions Of Linear Programming:

Definitions of Linear Programming:

 A mathematical procedure for minimizing or maximizing a linear function of several variables, subject to a finite number of linear restrictions on these variables.

 A branch of mathematics that uses linear inequalities to solve decision-making problems involving maximums and minimums.

 A mathematical technique that solves resource allocation problems.

 A method of solution for problems in which a linear function of a number of variables is subject to a number of constraints in the form of linear inequalities.

 A mathematical technique used in economics; finds the maximum or minimum of linear functions in many variables subject to constraints

 In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

Linear programming

In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

Linear programming is an important field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations.

Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

 A linear function to be maximized

e.g. maximize c1x1 + c2x2

 Problem constraints of the following form

e.g.

 Non-negative variables

e.g.

The problem is usually expressed in matrix form, and then becomes:

maximize

subject to

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.

[edit]

Example

Suppose that a farmer has a piece of farm land, say A square kilometres large, to be planted with either wheat or barley or some combination of the two. The farmer has a limited permissible amount F of fertilizer and P of insecticide which can be used, each of which is required in different amounts per unit area for wheat (F1, P1) and barley (F2, P2). Let S1 be the selling price of wheat, and S2 the price of barley. If we denote the area planted with wheat and barley with x1 and x2 respectively, then the optimal number of square kilometres to plant with wheat vs barley can be expressed as a linear programming problem:

maximize S1x1 + S2x2 (maximize the revenue - this is the "objective function")

subject to (limit on total area)

(limit on fertilizer)

(limit on insecticide)

(cannot plant a negative area)

Which in matrix form becomes:

maximize

subject to

[edit]

Augmented form (slack form)

Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace non-equalities with equalities in the constraints. The problem can then be written on the following form:

Maximize Z in:

where xs are the newly introduced slack variables, and Z is the variable to be maximized.

[edit]

Example

The example above becomes as follows when converted into augmented form:

maximize S1x1 + S2x2 (objective function)

subject to x1 + x2 + x3 = A (augmented constraint)

F1x1 + F2x2 + x4 = F (augmented constraint)

P1x1 + P2x2 + x5 = P (augmented constraint)

where x3,x4,x5 are (non-negative) slack variables.

Which in matrix form becomes:

Maximize Z in:

[edit]

Duality

Every linear programming problem, referred to as a primal problem, can be converted into an equivalent dual problem. In matrix form, we can express the primal problem as:

maximize

subject to

The equivalent dual problem is:

minimize

subject to

where y is used instead of x as variable vector.

[edit]

Theory

Geometrically, the linear constraints define a convex polyhedron, which is called the feasible region. Since the objective function is also linear, all local optima are automatically global optima. The linear objective function also implies