Page 392 - A Course in Linear Algebra with Applications
P. 392
376 Chapter Ten: Linear Programming
Elimination of an unconstrained variable
Suppose that the variable Xj is unconstrained, i.e., it can
take negative values. The trick here is to replace Xj by two
new variables xt,xj which are constrained. Write Xj in the
form x-j = xf — x~ where xf.xj > 0. This is possible since
any real number can be written as the difference between two
positive numbers.
If we replace Xj by x~j~ — xj in each constraint and in
the objective function, and we add new constraints x^ > 0,
xj > 0, then the resulting equivalent program will have fewer
unconstrained variables.
By a sequence of operations of types I-IV a general linear
programming problem may be transformed to an equivalence
problem in standard form. Thus we have proved:
Theorem 10.1.1 Every linear programming problem is
equivalent to a program in standard form.
Example 10.1.3
Put the following programming problem in standard form.
minimize: z = 3x% + 2x 2 — ^3
{ Xi + X2 + 2x 3 > 6
%l +
+
^2
2
<
3^3
£1,2:3 > 0
First of all change the minimization to a maximization
and replace the constraints involving = and > by constraints
involving < :
