Meaning of linear programming

Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization).

• Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:
The three inequalities in the curly braces are the constraints. The area of the plane that they mark off will be the feasibility region. The formula "z = 3x + 4y" is the optimization equation. I need to find the (x, y) corner points of the feasibility region that return the largest and smallest values of z.
My first step is to solve each inequality for the more-easily graphed equivalent forms:

It's easy to graph the system:   Copyright © Elizabeth Stapel 2006-2011 All Rights Reserved

To find the corner points -- which aren't always clear from the graph -- I'll pair the lines (thus forming a system of linear equations) and solve:


y = –( 1/2 )x + 7y = 3x	y = –( 1/2 )x + 7y = x – 2	y = 3x y = x – 2
–( 1/2 )x + 7 = 3x–x + 14 = 6x14 = 7x 2 = x y = 3(2) = 6	–( 1/2 )x + 7 = x – 2 –x + 14 = 2x – 4 18 = 3x 6 = x y = (6) – 2 = 4	3x = x – 2 2x = –2x = –1 y = 3(–1) = –3
corner point at (2, 6)	corner point at (6, 4)	corner pt. at (–1, –3)

So the corner points are (2, 6), (6, 4), and (–1, –3).
Somebody really smart proved that, for linear systems like this, the maximum and minimum values of the optimization equation will always be on the corners of the feasibility region. So, to find the solution to this exercise, I only need to plug these three points into "z = 3x + 4y".

(2, 6):      z = 3(2)   + 4(6)   =   6 + 24 =   30
(6, 4):      z = 3(6)   + 4(4)   = 18 + 16 =   34
(–1, –3):  z = 3(–1) + 4(–3) = –3 – 12 = –15
Then the maximum of z = 34 occurs at (6, 4),
and the minimum of z = –15 occurs at (–1, –3).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.
Linear programs are problems that can be expressed in canonical form as

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and is the matrix transpose. The expression to be maximized or minimized is called the objective function (c^Tx in this case). The inequalities Ax ≤ b and x ≥ 0 are the constraints which specify a convex polytope over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second then we can say the first vector is less-than or equal-to the second vector.
Linear programming can be applied to various fields of study. It is widely used in business and economics, and is also utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.