316 linear programming

linear programming The branch of mathematics

concerned with finding the maximum or minimum val-

ues of linear functions, that is, functions involving vari-

ables raised only to the first power, subject to a number

of inequalities that must remain true, is called linear

programming. This field has profound applications to

economics and industry and is an area of active

research. While, in principle,

OPTIMIZATION

problems

of this type are straightforward to solve, practical

problems may involve well over 100 variables and be

difficult to analyze. The challenge is to find efficient

techniques for finding solutions.

The principle of linear programming is best illus-

trated with an example. Suppose, for instance, we wish

to find the maximum value of the function U= 4x– 3y

subject to the constraints x≥0, y≥0, x≤1, and y≤1.

In this example, the constraints define a unit square in

the plane, and we wish to find the point (x, y) in this

“feasible region” that provides the largest value for the

“objective function”U= 4x– 3y.

Reasoning backward, note that each possible value

cof the objective function defines a line 4x– 3y= cof

slope 4/3. As the value of cvaries, this line sweeps

across the plane. Starting with a large value of cand

decreasing its value, we thus seek the first value, of c

that produces a line that touches the feasibility region.

Clearly, this will occur at one of the vertices of the

square. Checking all four vertices, (0,0), (1,0), (0,1),

and (1,1), we see that x= 1, y= 0 gives the largest pos-

sible value 4 for U.

In general, the constraint conditions define a polyg-

onal region in space, and the maximal and minimal

values of Ucan only occur at vertices of the region.

Linear programming then seeks to find efficient meth-

ods for checking which vertices yield the largest and

smallest values for U.

See also

OPERATIONS RESEARCH

.

linear transformation A map T : V →Wbetween

two

VECTOR SPACE

s Vand Wis called a linear transfor-

mation if the following two conditions hold:

i. T(a+ b) = T(a) + T(b) for any two vectors aand b

ii. T(ka) = kT(a) for any number kand any vector a

If the vector spaces Vand Wrepresent the set of all

points in the plane or in three-dimensional space, then

a linear transformation is an example of a

GEOMETRIC

TRANSFORMATION

that takes straight lines to straight

lines. For instance, rotations and reflections are linear

transformations. However, not every geometric trans-

formation is a linear transformation. Although a trans-

lation, for example, preserves straight lines in the

plane, it does not satisfy the first condition described

above and so is not a linear transformation.

If e1e2,…,enis a basis for the vector space V, then

any vector ain Vcan be written as a linear combina-

tion of these basis vectors:

a= c1e1+ c2e2+…+ cnen

for some numbers c1, c2,…, cn. Thus the value of the

linear transformation Tis completely determined by its

values on the basis vectors:

T(a) = T(c1e1+ c2e2+…+ cnen)

= c1T(e1) + c2T(e2) +…+ cnT(en)

If f1,f2,…,fmis a basis for the second vector space W,

then each vector T(ej) is a linear combination of these

basis vectors:

T(ej) = a1jf1+ a2jf2+…+ amjfm

Thus the numbers aij completely specify how the lin-

ear transformation works. Let Abe the

MATRIX

with

(i,j)th entry equal to aij. This shows that every linear

transformation is represented by a matrix. Moreover,

if we represent the basis vectors e1,e2,…,enas the col-

umn vectors:

then the matrix A, whose jth column is the sequence of

values that result when Tis applied to the jth basis vec-

tor ej, satisfies Aej= T(ej), and, in general, for any vec-

tor awe have:

T(a) = Aa

That is, we have: