Optimizations and Programming. Abdelkhalak El Hami

1.5.2. Simplex tableau

      Suppose that we wish to solve

      Let c = (4, 3, 0, 0)T , b = (12, 14)T , (A, I₂) =

It is easy to see that x = (x₁, x₂, x₃, x₄)T = (0, 0, 12, 14)T satisfies the constraints. Thus, x is a basic feasible solution with basis J = {3, 4} (the third and fourth components of x), whose basic variables are x₃ = 12 and x₄ = 14.

      Note that x is not optimal: z(x) = cT x = 0. The optimization procedure constructs a sequence of tables, called simplex tableaus. The first tableau summarizes the data c, b, A′ and the basic variables. The last row is equal to –cT.

Table 1.1. First simplex tableau

       General case

      Consider the problem

      where

and A is an m × n matrix. We may assume without loss of generality that rank A = m < n.

      DEFINITION 1.9.– Let A = (a1, a2, . . . , an) (where aj is the jth column of A), and, for J ⊂ {1, 2, . . . , n}, let AJ = {aj, j ∈ J}.

       – J ⊂ {1, 2, . . . , n} is a basis of (P) if |J| = m and if rank AJ = rank (aj, j ∈ J) = m;

       – let x = (x1, . . . , xn)T ∈ Then xj is a basic variable (respectively, non-basic variable) if j ∈ J (respectively, j ∉ J). We write xJ = (xj, j ∈ J);

       – basic feasible solution: x = (x1, . . . , xn)T ∈ such that xj = 0 for j ∉ J and such that Ax = AJ xJ = b.

      REMARK.– The advantage of passing from the canonical form to the standard form is that we immediately obtain a basic feasible solution that can be used as a starting point for the simplex algorithm. The basic variables are the slack variables.

      1.5.3. Change of feasible basis

      Let x be a basic feasible solution of (P). Then

      Our goal is to find another feasible basis and a basic feasible solution such that z() > z(x) (meaning that is better than x). The simplex method proceeds by replacing one of the basic variables xr with a non-basic variable xk. We say that

       – the variable xr enters the basis J : xr → r = 0;

       – the variable xk leaves the basis : xk = 0 → k > 0.

      Thus, = (J − {r}) ∪ {k}. We need rules to choose r and k. These rules are as follows:

       – Choose r such that[1.3]

       – Choose k such that[1.4]

      EXAMPLE 1.4.– Returning to the previous example: J = {3, 4}, c₃ = c₄ = 0, and so zj = 0 for j = 1, 2, 3, 4. Thus, zj − cj = −cj, j = 1, 2, 3, 4. Hence, k = 1.

      To choose r,

Thus, r = 2, x₄ leaves the basis, and x₁ enters the basis. The new basis is = {3, 1}. We have

      Hence, = (2, 0, 6, 0)T and Passing from J = {3, 4} to = {3, 1} increases the value of z to 8, but this value is not yet maximal.

       Calculating the new tableau

      We now apply the transformation x → that increased the value of z. Since the value z() (> z(x)) is not necessarily maximal in general, we may need to repeat the steps for choosing r and k several times until we find a basic feasible solution that is also a maximum of z.

      To do this, we need a second tableau where xJ is replaced by interpreted in the same way as the first. The same linear transformation that allowed us to pass from x to is applied to the columns of A.

      The matrix A = (aij, i = 1, . . . , m, j = 1, . . . , n) is replaced by Ā = (āij, i = 1, . . . , m, j = 1, . . . , n) as follows:

      [1.5]

      This gives

      [1.6]

      where i, i = 1, . . . , m, are the new basic variables

      The last row of the new tableau is computed in the same way:

      [1.7]

EXAMPLE 1.5.– If we apply the above procedure to our example, we obtain Table 1.2.

Table 1.2. Second simplex tableau