Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I don't understand why it is true that "$\mathbf{u}'$ and $K'$ satisfy points a, b and c listed in step 1", as stated in step 5 of the algorithm. Any help will be appreciated.

Input

  1. $m, n \in \mathbb{N}_1 (=\{1, 2, 3, \dots\})$ ... The number of constraints ($m$) and the number of variables ($n$) in the primal LP (= linear program)
  2. $\mathbf{A} \in \mathbb{R}_{m \times n}$ ... The constraints matrix
  3. $\mathbf{b} \in \mathbb{R}_{m \times 1}$ ... The rhs (= right hand side) of the constraints list
  4. $\mathbf{c} \in \mathbb{R}_{n \times 1}$ ... The cost coefficients
  5. $\Phi := (m, n, \mathbf{A}, \mathbf{b}, \mathbf{c})$ ... The primal LP, considered as the problem of deciding whether the feasible set $F := \{\mathbf{x}\in \mathbb{R}_{n \times 1} \mid: \mathbf{A}\mathbf{x} = \mathbf{b}\wedge\mathbf{x}\geq\mathbf{0}_{m \times 1}\}$ is empty and, if not, whether the set of costs $Z := \{\mathbf{c}^T\mathbf{x} :\mid \mathbf{x} \in F\}$ is bounded from below, and, if so, calculating some $\mathbf{x}^* \in \arg\min Z$.

Output

The algorithm assumes that the set $F' := \{\mathbf{u} \in \mathbb{R}_{m \times 1} \mid: \mathbf{A}^T\mathbf{u} \leq \mathbf{c}\}$ is non-empty. If it terminates, and it does so without error, it provides answers to the following questions:

  1. Is the set $Z':=\{\mathbf{b}^T\mathbf{u} :\mid \mathbf{u} \in F'\}$ bounded from above?
  2. If $Z'$ is bounded from above, what is some $\mathbf{u}^* \in \arg\max Z'$?

Notation

If $\mathbf{B} \in \mathbb{R}_{a \times b}$ is a real matrix (possibly a row/column vector) for some $a, b \in \mathbb{N}_1$, and if $\alpha$ is a non-empty, finite sequence of numbers from the set $\{1, 2, \dots, a\}$ and if $\beta$ is a non-empty, finite sequence of numbers from the set $\{1, 2, \dots, b\}$, then $\mathbf{B}_{\alpha, \beta}$ is the matrix $$ \left[\begin{array}{ccc} \mathbf{B}_{\alpha_1, \beta_1} & \mathbf{B}_{\alpha_1, \beta_2} & \dots \\ \mathbf{B}_{\alpha_2, \beta_1} & \mathbf{B}_{\alpha_2, \beta_2} & \dots \\ \vdots & \vdots & \ddots \end{array}\right] $$

A non-empty, finite subset $s \subseteq \{1, 2, \dots\}$ can be used where a sequence is expected (in particular, as a matrix subscript), in which case it denotes the sequence constructed by listing the elements of $s$ in ascending order.

If a single number, $t \in \{1, 2, \dots\}$. is used where a sequence is expected, it should be considered to denote the sequence $(t)$.

We set $M := \{1, 2, \dots, m\}$, $N := \{1, 2, \dots, n\}$, $L := N \setminus M$, where $m$, $n$ are the numbers that are input to the algorithm.

Vectors shall be considered to be matrices, and hence subscripted with two subscripts.

$\mathbf{N}_1 := \{1, 2, 3, \dots\}$. $I_a$ and $\mathbf{0}_{a \times b}$ (where $a, b \in \mathbb{N}_1$) are respectively the $a \times a$ identity matrix and the $a\times b$ matrix consisting entirely of $0$'s.

Comparisons between matrices of the same dimensions shall be carried out component-wise, for instance $[1\ 2] \geq \mathbf{0}_{1\times 2}$ is true, but $[-1\ 2] \geq \mathbf{0}_{1 \times 2}$ is false and $[1\ 2] \geq \mathbf{0}_{2 \times 1}$ is undefined.

If $\mathbf{v} \in \mathbb{R}_{a \times 1}$ ($a \in \mathbb{N}_1$) is a column vector of real numbers and $\varphi(x)$ is a predicate that applies to real numbers (e.g. "$x<0$"), then $\arg_{\varphi}(\mathbf{v}_{i, 1}) := \{i \in \{1, 2, \dots, a\} \mid: \varphi(i)\}$. If $\mathbf{w} \in \mathbb{R}_{1 \times a}$ is a row vector of real numbers and $\varphi(x)$ is as above, then $\arg_{\varphi}\mathbf{w} := \{j \in \{1, 2, \dots, a\} \mid: \varphi(\mathbf{w}_{1, j})\}$.

The matrix operations "transpose" and "inverse" are applied after subscripting, so, for example, if $\mathbf{B} \in \mathbb{R}_{a\times a}$ for some $a \in \mathbb{N}_1$, and if $\emptyset \neq \alpha \subseteq \{1, 2, \dots, a\}$ and $\emptyset \neq \beta \subseteq \{1, 2, \dots, a\}$, then $\mathbf{B}^T_{\alpha, \beta} = (\mathbf{B}_{\alpha, \beta})^T$.

Finally, we use the notation $F'$ and $Z'$ introduced in the "Output" section.

The dual simplex algorithm

  1. "Initialization". Find a dual basic feasible solution (dbfs), i.e. a vector $\mathbf{u} \in \mathbf{R}_{m \times 1}$ and a subset $K \subseteq N$ of power $m$, for which

    a) $A_{M, K}^T$ is invertible,

    b) $\mathbf{u} = \left(A_{M, K}^T\right)^{-1}\mathbf{c}_{K, 1}$,

    c) $\mathbf{u} \in F'$.

    If no such $(\mathbf{u}, K)$ pair can be found, terminate with an error.

  2. "Test for optimality". If $\mathbf{A}_{M, K}^{-1}\mathbf{b} \geq \mathbf{0}_{m \times 1}$, terminate: $Z'$ is bounded from above and $\mathbf{u} \in \arg\max Z'$. Otherwise, let $k \in \arg_{<0}\mathbf{A}_{M, K}^{-1}\mathbf{b}$, and set $k^*$ to be the $k$th element of the sequence $K$.

  3. "Computing the direction of movement". Set $\mathbf{d} := -\left(A_{M, K}^{-1}\right)^T_{k, M}$ [This direction is chosen because it leads to an increase in the dual cost, since $\mathbf{b}^T\mathbf{d} > 0$.]

  4. "Computing the amount of movement". If $\mathbf{A}_{M, L}^T\mathbf{d} \leq \mathbf{0}_{(n - m) \times 1}$, terminate: $Z'$ is not bounded from above. Otherwise, set $$ \begin{aligned} T & := \{(\mathbf{c}_{L, 1} - \mathbf{A}_{M, L}^T\mathbf{u})_{j, 1}/(\mathbf{A}_{M, L}^T\mathbf{d})_{j, 1}:\mid j \in \arg_{>0}\mathbf{A}_{M, L}^T\mathbf{d}\} \\ t & := \min T \\ j & :\in \arg\min T \end{aligned} $$

    ($j$ is an arbitrary member of $\arg\min T$) and set $j^*$ to be the $j$th element of the sequence $L$.

  5. "Moving to the new dbfs and pivoting". Set $\mathbf{u}' := \mathbf{u} + t\mathbf{d}$ and $K' := (K \setminus \{k^*\})\cup \{j^*\}$. $\mathbf{u}'$ and $K'$ satisfy points a, b and c listed in step 1 (if we identify $\mathbf{u}$ with $\mathbf{u}'$ and $K$ with $K'$). Go to step 2.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.