Revised simplex linear programming and certificates — Examples

With $B=(2)$, $A_B=1$, $x_2=1$, and $y=c_2=2$. Thus ${\bar{c}}_1=1-2=-1$, so $x_1$ is a valid entering variable.

For the changed right-hand side $b=-1$ and basis $B=(1)$, $x_1=-1$ while $y=1$ and ${\bar{c}}_2=1\ge 0$, so the basis is dual feasible and primal infeasible. Its only nonbasic coefficient is $d_{12}=A_B^{-1}{a}_2=1\ge 0$.

The direction coefficient is $d=A_B^{-1}{a}_1=1$ and the ratio is $x_2\mathrm{/}d=1$. The pivot yields $x_1=1,x_2=0$ and changes cost by $1\cdot (-1)=-1$, from $2$ to $1$.

At the new basis $B=(1)$, $y=c_1=1$ and ${\bar{c}}_2=2-1=1\ge 0$. The vector is feasible, so [F2] proves it is optimal; the primal and dual objective values are both $1$.

There is no eligible negative coefficient. The certificate from [F3] is $q=1$, for which $A^{\mathsf{T}}q=(1,1)\ge 0$ and $b^{\mathsf{T}}q=-1<0$. Thus the modified system has no nonnegative feasible vector.

Initially $B=(5,6,7)$, $x_B=(0,0,1)$, and the only negative reduced cost is ${\bar{c}}_1=-10$. For entering $x_1$, $d=(1\mathrm{/}2,1\mathrm{/}2,1)$ gives ratios $(0,0,1)$ for $(x_5,x_6,x_7)$, so the least-index leaving tie is $x_5$ and $\theta =0$. The next basis is $(1,6,7)$.

At $B=(1,6,7)$ the negative reduced costs are ${\bar{c}}_2=-53$ and ${\bar{c}}_3=-41$. Both rules choose $x_2$. Its direction is $d=(-11,4,11)$; the eligible ratios for $(x_6,x_7)$ are $(0,1\mathrm{/}11)$, so $x_6$ leaves at $\theta =0$ and the basis becomes $(1,2,7)$.

At $B=(1,2,7)$ the negative reduced cost is ${\bar{c}}_3=-29\mathrm{/}2$. Its direction is $d=(1\mathrm{/}2,1\mathrm{/}2,-1\mathrm{/}2)$, so the eligible ratios for $(x_1,x_2)$ are $(0,0)$; the least-index leaving variable is $x_1$, giving $\theta =0$ and basis $(3,2,7)$.

At $B=(3,2,7)$ the negative reduced costs are ${\bar{c}}_4=-18$ and ${\bar{c}}_5=-15$, so both rules choose $x_4$. Its direction is $d=(-8,2,0)$; the only eligible ratio is $0$ for $x_2$, which leaves and gives basis $(3,4,7)$.

At $B=(3,4,7)$ the only negative reduced cost is ${\bar{c}}_5=-21\mathrm{/}2$. Its direction is $d=(1\mathrm{/}2,1\mathrm{/}4,0)$; the eligible ratios for $(x_3,x_4)$ are $(0,0)$, so $x_3$ leaves at $\theta =0$ and the basis becomes $(5,4,7)$. Thus the first five pivots agree under both rules.

At $B=(5,4,7)$, ${\bar{c}}_1=-22$ and ${\bar{c}}_6=-24$. The most-negative rule chooses $x_6$, whose direction $d=(-9,1,0)$ has only the eligible ratio $0$ for $x_4$. The pivot leaves $x_4$ and returns to $(5,6,7)$ with the same basic vector and objective $0$; repeating the deterministic choices cycles.

At the same basis $(5,4,7)$, Bland chooses $x_1$ because $1<6$. Its direction is $d=(-4,1\mathrm{/}2,1)$; the eligible ratios for $(x_4,x_7)$ are $(0,1)$, so $x_4$ leaves and the next basis is $(5,1,7)$, still with $\theta =0$.

At $B=(5,1,7)$ the only negative reduced cost is ${\bar{c}}_3=-1$. Its direction is $d=(-2,-1,1)$, so only $x_7$ is eligible and its ratio is $1$. The pivot gives basis $(5,1,3)$ and basic values $(2,1,1)$, hence the full vector is $x=(1,0,1,0,2,0,0)$.

At this final basis the objective is $-10+9=-1$ and the remaining reduced costs for $(x_2,x_4,x_6,x_7)$ are $(30,42,18,1)$, all nonnegative. The basic vector is feasible, so [F2] proves it optimal; [F3] also confirms finite termination. The six-pivot most-negative cycle and Bland's terminating branch are thereby checked with exact rational pivots.

The basis matrix is $A_B=-1$, so $x_2=(-1{)}^{-1}0=0$. The multiplier is $y=(-1{)}^{-1}{c}_2=0$, and the nonbasic reduced cost is ${\bar{c}}_1=-1-1\cdot 0=-1$.

The entering direction coefficient is $d=A_B^{-1}{a}_1=-1$. There is no row with $d_i>0$, so the ray has $r_1=1$ and $r_2=-d=1$. Then $Ar=1-1=0$, $r\ge 0$, and $c^{\mathsf{T}}r=-1<0$; [F1] gives unboundedness below.

The third right-hand side is negative, so $D=\mathrm{diag}(1,1,-1)$ gives $\tilde{A}=DA=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 1& -1\end{array}\right]$ and $\tilde{b}=Db=(1,1,3{)}^{\mathsf{T}}$. The Phase I point $x=(1,1,0)$, $u=(0,0,1)$ satisfies $\tilde{A}x+u=\tilde{b}$ and has objective $1$.

The Phase I dual vector $y=(-1,-1,1)$ satisfies ${\tilde{A}}^{\mathsf{T}}y=(0,0,-1{)}^{\mathsf{T}}\le 0$ and ${\tilde{b}}^{\mathsf{T}}y=1$. For any Phase I feasible $(x,u)$, its objective ${\mathbf{1}}^{\mathsf{T}}u$ is at least ${\tilde{b}}^{\mathsf{T}}y=1$ by multiplying the constraints by $y$ and using ${\tilde{A}}^{\mathsf{T}}y\le 0$, $u\ge 0$, and $y\le \mathbf{1}$. Thus the displayed feasible point attains the Phase I optimum $1>0$.

The original Farkas vector is $q=-D^{\mathsf{T}}y=(1,1,1)$. Direct calculation gives $A^{\mathsf{T}}q=(0,0,1{)}^{\mathsf{T}}\ge 0$ and $b^{\mathsf{T}}q=1+1-3=-1<0$. Hence no $x\ge 0$ can satisfy $Ax=b$, as also follows from [F2].

The basis matrix has $\mathrm{\parallel }A{\mathrm{\parallel }}_2=1$ and $\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2={\delta }^{-1}=2^{27}$, so its 2-norm condition number is $2^{27}$. The exact solution is $(1,1)$, while the candidate has forward error $\widehat{x}-x^{\ast }=(0,\delta )$.

Exact multiplication gives $r_p=(0,{\delta }^2)=(0,2^{-54})$, $r_d=(0,0)$, and $g=\delta =2^{-27}$. Thus the residual norm is $2^{-54}$ although the absolute forward error is $2^{-27}$, larger by the condition factor.

Here $\mathrm{\parallel }\widehat{x}{\mathrm{\parallel }}_1=2+\delta$, $\mathrm{\parallel }y{\mathrm{\parallel }}_1=1+{\delta }^{-1}$, so [F2] gives $\mathrm{\mid }g\mathrm{\mid }\le (1+{\delta }^{-1}){\delta }^2=\delta +{\delta }^2$. The candidate is not exactly primal feasible and has a positive gap; the small residual alone therefore does not certify exact optimality or infeasibility.