CHAPTER 3: Matrix formulation of the simplex method for LPPs Flashcards
matrix expression for…
matrix formulae for the various quantities in a tableau in a simplex calculation.
We will be considering the LPP max z = c^Tx, subject to ¯ Ax := [A,I]x = b with x ≥ 0. ¯ A is an m×n (n > m)matrix, x ∈ R^n is an n-vector,
the resource vector b∈ R^m is an m-vector.
in this section it is not required that b ≥ 0. As we have seen from the last section, the sign of b matters only at the initial step, when we choose the starting basic feasible solution to initiate the simplex iterations. The matrix formulae do not concern this step
Notation 1
¯ A as a collection of its columns [a1,…,an] where a_j is the jth column vector. We will use a_ij to denote the (i,j) element of ¯ A. a_ij is the ith component of column vector aj.
We also use ei to denote the ith column of the identity matrix,
i.e., ei = (0,…,0,1,0,…,0)^T where 1 is the ith component. We will call ei the ith unit vector.
(we often come across identity matrix)
Notation 2:
initial tableau
initial tableau:
basis variables x^T ,
solution column vector b
- cost coefficients recorded in the tableau
coefficient matrix ¯ A
list of basic variables vector x_b
solution for z is vector z_b corresponding to this basis
how to represent at later iteration?
Matrix multiplication
Matrix multiplication can be performed column-wise. Considering matrices E, F, where F = [f1, f2] with f1 and f2 being the column vectors, then EF = E[f1, f2] = [Ef1,Ef2].
Row operations applied to a matrix
Row operations applied to a matrix can be represented by left-multiplying the matrix by another matrix.
we can derive this ourselves
Similar representations can be found for other row operations
Left-multiplying a matrix by a row vector
Left-multiplying a matrix by a row vector gives a linear combination of the rows of the matrix. Say d = [d1,d2,...,dm]T. Then d^TA = [d1,d2,...,dm]* [ R1] [ R2] [ . . .] [ Rm]
= d_1R_1 +d_2R_2 +…+d_mR_m,
where Ri is the ith row of the matrix A.
Conversely, we can also say a linear combination of the rows of a matrix can be obtained by left-multiplying the matrix by a row vector.
Basic matrix
used in simplex calculations
The rows corresponding to the constraints include columns from the extended coefficient matrix ¯ A = [A,I]
Basis x1 x2 x3 x4 x5 x6 Sol z -3 -2 0 0 0 0 0 x3 1 2 1 0 0 0 6 x4 2 1 0 1 0 0 8 x5 -1 1 0 0 1 0 1 x6 0 1 0 0 0 1 2 Table 3.1: The initial (first) tableau.
and the solution column, which can be combined into one matrix [A,I,b]. The actual calculations applied to the tableaux amount to the following two transformations, which are accomplished by successive row operations:
[A,I,b] =
[1 2 | 1 0 0 0 | 6 ] [2 1 | 0 1 0 0 | 8 ] [2 1 | 0 0 1 0 | 1 ] [2 1 | 0 0 0 1 | 2 ] to [0 3/2 | 1 -1/2 0 0 | 2 ] [1 1/2 | 0 1/2 0 0 | 4 ] [0 3/2 | 0 1/2 1 0 | 5 ] [0 1 | 0 0 0 1 | 2 ] to [0 1 | 2/3 -1/3 0 0 | 4/3 ] [1 0 | -1/3 2/3 0 0 | 20/3 ] [0 0 | -1 1 1 0| 3 ] [0 0 | -2/3 1/3 0 1 | 2/3 ]
row operations can be represented by matrix multiplications. The cumulative effects of all the row operations to update a tableau can be represented by a matrix, say, D. Thus, starting from matrix [A,I,b], we should be able to find matrix D such that the second matrix is given by
D[A,I,b] ≡ [DA,D,Db].
The 2nd tableau : the x3 to x6 columns form the matrix B−1 2 The columns in the first tableau corresponding to the basic variables x3, x1, x5 and x6 form B2. The 3rd tableau : the x3 to x6 columns form the matrix B−1 3 . The columns in the first tableau corresponding to the basic variables x2, x1, x5 and x6 form B3
How do we find D?
When the tableaux are available, we can read D off the tableaux. The updated tableau is [DA,D,Db], therefore D is the sub-matrix in the middle section, which corresponds to the identity matrix in the initial tableau. Thus, to obtain the second tableau, the row operations are equivalent to left-multiplying [A,I,b] by matrix
D_2= [1 −1/2 0 0 ] [0 1/2 0 0 ] [0 1/2 1 0 ] [0 0 0 1 ]
To obtain the third tableau, the row operations are equivalent to left-multiplying [A,I,b] by matrix
D_3 = [2/3 −1/3 0 0 ] [−1/3 2/3 0 0 ] [−1 1 1 0 ] [−2/3 1/3 0 1 ]
D 2 and D3 are, respectively, the last four columns of coefficients in the 2nd and 3rd tableau. As you will see later, it is also useful to know the inverse of D (e.g., D−1 2 and D−1 3 ). Traditionally, we use B−1 to denote the above D so that D−1 is represented by B. Hence B−1 2 denotes D2 and B−1 3 denotes D3.
B2
B_2 is formed by those columns in the first tableau that correspond to the basic variable in the 2nd tableau
in the 2nd tabeau the basic var columns form B_2 ^-1
The calculation to obtain the 2nd tableau is the same as
[A,I,b] → B^−1_2 [A,I,b] = [B^−1_2 A ,B^−1_2 ,B^−1_2 b]
B_3
B−1 3 (associated with the 3rd tableau) is formed from the last four columns in the 3rd tableau. B3 is found in a way similar to finding B2:
B3 is formed by those columns in the first tableau that correspond to the basic variables in the 3rd tableau.
The calculation from the 1st table auto the 3rd is the same as
[A,I,b] → B^−1_3
[A,I,b] = [B^−1_3 A,B^−1_3 ,B^−1_3 b]. Note the two-step calculation leading to the 3rd tableau has been combined into matrix B^−1_3 .
reduced cost
usually given by: -c^T
DEF 3.1
MATRIX B
(Basis/basicmatrix).
Definition3.1(Basis/basicmatrix). The constraints
¯ Ax = b associate each component of x to a column of ¯ A by the relation
¯ Ax = ∑ from j=1 to n of [a_jx_j].
The m columns corresponding to the m basic variables of a tableau form a m×m matrix. The matrix is called the basis matrix or basic matrix corresponding to this tableau, denoted by B. If the solution for the basic variables is feasible, then the matrix is a basic feasible matrix. We will use x_B to denote the vector of the basic variables where subscript B indicates that the corresponding basic matrix is B.
Remark. In the majority cases, B is non-singular. It means the columns of B are linearly independent, and they form a basis in the m-dimensional space Rm.
basis matrix notes
If B is the basic matrix corresponding to a tableau, the argument so far has shown the following:
- The coefficients for the constraints in this tableau is given by B^−1 ¯A
- The ‘solution’ in this tableau is given by B^−1 b. We will use
ˆx_B to denote this solution,
i.e., ˆx_B ≡ B^−1 b.
Therefore, the constraints corresponding to this tableau can be written as B^−1 ¯Ax = B^−1b.
We will also use c_B to denote the cost coefficients for the basic variable x_B; z_B to denote the solution for z corresponding to ˆxB,
i.e., z_B ≡c^T_B ˆx_B.
deriving:
The matrix formula for the reduced costs
*reduced costs are the coefficients for x in the z-row of a tableau. Let r be the column vector for the reduced costs. Initially r=-c where c is the cost coefficients in the cost function z=c^Tx.
to derive matrix formula for r in the tableau for later iteration:
assume basic matrix for this tableau is B.
coefficient matrix in this tableau is thus B^−1 ¯A
r_p = reduced cost at the previous iteration
simplex algorithm: ass multiple of current pivot row B^−1 ¯A to r to find r
operation is r^T = r^T_p + d^TB^-1 ¯A for some vector d. Let h^T= d^T B^-1
Equation becomes:
r^T = r^T_p + h^T ¯A
(h^T ¯A represents linear combo of rows of ¯A so this shows:
the current coefficient matrix B^−1 ¯A can be written as a (most likely different) linear combination of the rows of the original coefficient matrix ¯A, and
r^T is obtained from r^T_p by adding the a linear combination of the rows of ¯A
By the same argument, r_p is obtained in the same way from the reduced costs in yet another iteration before. Repeating the argument all the way back to the initial step, we can write
r^T = −c^T + f^T ¯A.
where−cT is the initial reduced cost, fT is a row vector which represents the cumulative effects of the linear combinations. According to the simplex algorithm, the reduced costs for the basic variables have to be zero. Therefore, considering only the components of the above matrix equation for the basic variables, we have
0 = −c^T_B + f^T_B ⇒ f^T = c^T_B B^−1.
Thus
r^T = c^T_B B^−1 ¯A − c^T, or in terms of components r_j = c^T_B B^−1 a_j −c_j (j = 1,2,…,n).
This is the matrix formulae for the reduced costs. It is clear that if xj is a basic variable, then rj = 0, since this is the condition used to derive the expression for f. In some references zj is used to denote the first part in the formula for rj, i.e., zj = cT BB−1aj, so that rj = zj−cj.z j also has an economical interpretation, but we do not discuss it here.
The matrix formula for the reduced costs
r^T = c^T_B B^−1 ¯A − c^T, or in terms of components r_j = c^T_B B^−1 a_j −c_j (j = 1,2,…,n).
