0

I am (trying) to understand the following theorem:

If the simplex method does not terminate, it must cycle

Now I know that two dictionaries with the same $\mathcal{B}$ have to be encountered because the possibilities we have for that is not endless. ( we have $\binom{n+m}{m}$ possibilities). So that is not the problem I'm having. The problem comes when trying to prove that two dictionaries who share the same basis, are the same dictionaries/define the same feasible region.

Any help? I know the normal intuition on this, but the proof is being a hard nut to crack.

The proof the book gives:

recall that both dictionaries describe the complete feasible region under the restriction that $x_i \geq 0$ for all $i\in\mathcal{B} \cup \mathcal{N}$

in particular, for an arbitrary $k\in\mathcal{N}$ this holds for all feasible points with $x_k = t$ and $x_j=0$ for $j\in\mathcal{N}\backslash\{ k \}$. substituting this into the dictionaries yields $$ \begin{align} x_i &= \bar{b}_i - \bar{a}_{ik}t &=& \bar{b}^*_i - \bar{a}^*_{ik}t, \tag{$i\in\mathcal{B}$}\\ z &= \bar{w}+\bar{c}_kt&=&\bar{w}^* +\bar{c}^*_kt \end{align} $$ because this holds for all feasible $t\geq 0$ we have for all $k\in\mathcal{N}$ $$ \begin{align} \bar{b}_i=\bar{b}^*_i, \bar{a}_{ik}=\bar{a}^*_{ik},\tag{$i\in\mathcal{B}$}\\ \bar{w} = \bar{w}^*, \bar{c}_k=\bar{c}^*_k \end{align} $$ so we encounter the same dictionary twice, which means that the simplex method cycles.

now my problem with this proof is, what exactly is the $t$ doing?

WiseStrawberry
  • 817
  • Not sure what you are asking. If you have the same basis, wouldn't you always come up with the same resulting tableaux? The idea is that if it does not terminate, it must repeat some tableaux at least once, and then cycling is guaranteed... – gt6989b Jun 11 '13 at 13:52
  • yes I know it holds up, but the proof for same basis = same dictionary seems weird. – WiseStrawberry Jun 11 '13 at 13:56
  • anybody, any pointers?\ – WiseStrawberry Jun 13 '13 at 08:47
  • Do you have anywhere online the text of the proof? Intuitively it should make sense that once you fix what will enter the basis, you have exactly defined the correct constraints. Even mechanically, if you choose to insert the same things into the basis, it will result in the same numbers. But if you want formally, show me the proof and what step exactly you have trouble understanding. – gt6989b Jun 13 '13 at 14:16
  • i have added it @gt6989b – WiseStrawberry Jun 13 '13 at 14:58

0 Answers0