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
add comment

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.