📂Optimization

Linear Programming: Dictionaries and Tableau

Notation

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

For the matrix $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$, it is said that the linear programming problem is represented in the form of equation form as above, and let’s denote its components as follows. $$ \begin{align*} A =& \left( a_{ij} \right) \\ \mathbf{b} =& \left( b_{1} , \cdots , b_{m} \right) \\ \mathbf{c} =& \left( c_{1} , \cdots , c_{n} \right) \\ \mathbf{x} =& \left( x_{1} , \cdots , x_{n} \right) \end{align*} $$

Dictionary ¹

For $i = 1 , \cdots , m$, the following form of a system of equations is called a Dictionary. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$

Variables on the left-hand side other than $\zeta$ are called Basic Variables, and those on the right-hand side are called Nonbasic Variables. First, let’s denote their indices as $$ \begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*} $$ However, this is just a transcription of the initial linear programming problem, and with the progress of the solution, a bar is placed on the changing coefficients to express it as follows. $$ \begin{align*} \zeta &=& \bar{\zeta} &+& \sum_{j \in \mathcal{N}} \bar{c}_{j} x_{j} \\ x_{n+i} &=& \bar{b}_{i} &-& \sum_{j \in \mathcal{N}} \bar{a}_{ij} x_{j} \end{align*} $$ Here, $i \in \mathcal{B}$ and as indicated by the notation, $\mathcal{N}$ and $\mathcal{B}$ are not fixed sets but also change as the solution progresses.

Tableau ²

The simplex Tableau $\mathcal{T}(B)$, determined by the feasible basis $B$, refers to the nth-order system of linear equations that has the same set of solutions as the given linear programming problem $A \mathbf{x} = \mathbf{b}, z = \mathbf{c}^{T} \mathbf{x}$. For $N := \left\{ 1 , \cdots , n + m \right\} \setminus B$, if $\mathbf{x}_{B}$ is the vector of basic variables and $\mathbf{x}_{N}$ is the vector of nonbasic variables, then for some vectors $\mathbf{p} \in \mathbb{R}^{m}$, $\mathbf{r} \in \mathbb{R}^{n-m}$ and matrix $Q \in \mathbb{R}^{m \times (n-m)}$, it is represented as follows. $$ \begin{align*} \mathbf{x}_{B} &=& \mathbf{p} &+& Q \mathbf{x}_{N} \\ z &=& z_{0} &+& \mathbf{r}^{T} \mathbf{x}_{N} \end{align*} $$

Explanation

Frankly speaking, the Dictionary and the Tableau are the same thing, and as can be seen from the quotations, it is merely a matter of preference for expressions among the authors. Of course, conceptually $B = \mathcal{B}$ is the same as $N = \mathcal{N}$, and the only difference is whether one is using the variables as they are or using matrix notation.

In preparation for posting, I looked through many textbooks on linear programming, and no author seemed to want to explain in detail about either the Dictionary or the Tableau. From ‘system of equations’ onwards, students accustomed to a high degree of abstraction feel extreme anxiety and aversion to vague expressions like ‘in the following form’ or ‘changing according to the algorithm’. While understanding these feelings, it also seemed that the authors themselves preferred to quickly move on to discussing linear programming itself rather than dwelling on notations. If one is truly interested in linear programming, it is recommended to somewhat gloss over and move on.