Page 393 - A Course in Linear Algebra with Applications

10.1: Introduction to Linear Programming Oil

maximize: z = —3xi — 2x2 + x 3

—xi — x 2 — 2xz < —6
xi + x 2 + x 3 < 4
subject to: —x\ — x 2 - x 3 < —4
x\ - x 2 + 3x 3 < 2
> 0
x\,x 3
Next write x 2, which is an unconstrained variable, in the form
J/O Xn This yields a problem in standard form:

maximize: z = —3xi — 2xt + 2x 2 + x 3

subject to:

-Xi + Xn - 2x 3 < - 6
-x 2
+ xt-
x x Xn + x 3 < 4
x x 3 < - 4
+ xt + 2
Xi — xt + x 2 + 3^3 < 2
> 0
Xi,X~2,X 2 ,X 3
Slack variables

If we wish to transform a linear programming problem
to canonical form, a method for converting inequalities into
equalities is needed. This can be achieved by the introduction
of what are called slack variables.
Consider a linear programming problem in standard form:

T
maximize: z C X

AX < B
subject to:
X > 0
where A is m x n and the variables are x±,x 2,... ,x n. We
introduce m new variables, x n+i,..., x n+m, the so-called slack