Page 391 - A Course in Linear Algebra with Applications

10.1: Introduction to Linear Programming 375

A second important type of linear programming problem
is a maximization problem with all constraints equalities and
allvariables constrained. The general form is:

maximize : z = C X

\ AX = B
subject to:
\ X > 0.
Such a linear programming problem is said to be in canonical
form.

Changes to a linear programming problem
Our aim is to show that any linear programming problem
is equivalent to one in standard form and to one in canoni-
cal form. To do this we need to consider what changes to a
program will produce an equivalent program. There are four
types of change that can be made.

Replace a minimization by a maximization
T
If the objective function in a linear program is z = C X,
the minimum value of z occurs for the same X as the maxi-
T
mum value of (—C) X. Thus we can replace "minimize" by
T
T
"maximize" and C X by the new objective function (—C) X.
Reverse an inequality
The inequality anX\ + - • -+ai nx n > bi is clearly equivalent
to (-Oji)a;i -I h {-a in)x n < -bi.

Replace an equality by two inequalities
The constraint anXi + - • -+ai nx n = b n is equivalent tothe
two inequalities

a-nxi H h a inx n < bi
(-a a)xi H h (-a in)x n < -bi