Compute $\A_{B^k}^{-1}$ and $\bar{\c}_{N^k} = \c_{N^k} - \c_{B^k} \A_{B^k}^{-1} \A_{N^k}$.

    -   end (if)

    -   $k \Leftarrow k+1$.

-   end (while)

\[mainAlg\]

We can modify the algorithm by selecting two entering variables using the indices corresponding to the [**two**]{} most negative elements in $\bar{\c}_{N^k}$. In the numerical test section, we will show that this is a not a good strategy. \[mostNeg\]

Analysis of the algorithm
=========================

In this section, we provide two upper bounds of the iteration numbers for the proposed algorithm using the strategy developed in [@km11; @km13; @ye11].

Let $r$ be a real number and $\lceil r \rceil$ be the smallest integer bigger than $r$. Let $\gamma_P^*$ be the maximum value of all elements of $\x^*$ and $$\gamma_D = \max_{k} \{ \gamma_D^k \} =
\max_{k} \Big\{ \max_{j^k \in N^k} 
\{ -\bar{c}_{j^k} ~|~ \bar{c}_{j^k} < 0 \} \Big\}.
\label{gammaD}$$ Let $(B^k,N^k)$ and $(B^*,N^*)$ be the partitions of base and non-base variables at iteration $k$ and at the end of the program when the optimization is achieved. Let $\x^*$ be partitioned using $(B^k,N^k)$ but not $(B^*,N^*)$, i.e., $$\x^*= \left[ \begin{array}{c}
\x_{B^k}^* \\ \x_{N^k}^* \end{array} \right].$$ The first lemma is derived using exactly the same argument but stating a slightly improved result 