Page 390 - A Course in Linear Algebra with Applications

374 Chapter Ten: Linear Programming

Standard and canonical form
Since the general linear programming problem has a com-
plex form, it is important to develop simpler types of prob-
lem which are equivalent to it. Here two linear programming
problems are said to be equivalent if they have the same sets
of feasible solutions and the same optimal solutions.
A linear programming problem is said to be in standard
form if it is a maximization problem with all constraints in-
equalities and all variables constrained. It therefore has the
general form
maximize: z — c\X\ + • • • + c nx n
subject to:

' anXi + a\ 2x 2 + h ai nx n < bi
a 2\Xi + a 22x 2 + h a 2nx n < b 2
I a mixi + a m2x 2 j H = h a mnx n < b m

l,2,...,n
Xj>0,
This problem can be written in matrix form: let A = (a,ij) mn,
T
B = (bi b 2 ... b m) , C = (ci c 2 ... c n) T and X =
T
(x\ x 2 ... x n) . Then the problem takes the form:

maximize : z = C X

, . . , (AX<B
subject to- S x > Q

Here a matrix inequality U < V means that U and V are
of the same size and Uy < v^j for all i,j: there is a similar
definition of U > V.