Page 416 - A Course in Linear Algebra with Applications

400 Chapter Ten: Linear Programming

Recall from 10.3 that the extreme points of the set of
feasible solutions are exactly the basic feasible solutions. Also
keep in mind that in a basic solution the non-basic variables
all have the value 0.

The initial tableau
For the linear programming problem in canonical form
above we have the solution

X\ — X2 — ' — X n U, £ n _|_i — 0\, . • . , X n-^- m — 0 m .

Since B > 0, this is a basic feasible solution in which the basic
variables are the slack variables x n+i,..., x n+m. The value of
z at this point is 0 since z = c\Xi + 1- c nx n.
The data are displayed in an array called the initial
tableau.

Xi 2-n x n+l •En+m z
X 2
x n+x an a\2 O'ln 1 0 0 h
Xn+2 «21 «22 a-2n 0 0 0 b 2

%n-\-m 1 m l O'ml Q"mn 0 1 0 b n
- C l - c 2 C n 0 0 1 0

Here the rows in the array correspond to the basic vari-
ables, which appear on the left, while the columns correspond
to all the variables, including z. The bottom row, which lies
outside the main array and is called the objective row, displays
the coefficients in the equation — cixi — • • • — c nx n + z — 0.
The z-column is often omitted since it never changes during
the algorithmic process. The right most column displays the
current values of the basic variables, with the value of z in the
lower right corner.