# Construct a direction of recession of the dual that is from growth to dual function

Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $$A \in \mathbb {R}^{ m × n}$$ has rank $$m$$. Suppose that, in a certain iteration of the dual-simplex method, relative to a dual-feasible base $$A_B \in \mathbb {R}^{m × n}$$, for some $$r \in\{1,. . . , m\}$$ happens $$b_{r} <0$$ and $$a_{rs} \geq 0$$ for every $$j = 1,..,n.$$ Determine a direction of recession of the dual that is from growth to dual function.

Bazaraa has a hint; he said to consider $$w=c_B\cdot A^{-1}_B + B^r$$, where $$B^r$$ is the $$r$$th row of $$A^{-1}_B$$. But I can't see how this can be true. Anyway, I would like to prove that $$w$$ is in fact a recession ray; in other words, $$Aw \leq 0$$, $$w\geq 0$$ and $$w \neq 0$$.

Thanks.

• Are you expecting someone to do your homework or take-home exam problem for you? Jul 3 '19 at 11:42
• By no means. Let be clear, i just asked for some kind of help and not for anyone to do it for me, it's a big difference. Jul 3 '19 at 11:51
• You should add the "self-study" tag (if you can, show us what what you have done, and indicate where you need help. Jul 3 '19 at 11:54
• Who is Bazaraa who you mention in your question? Jul 3 '19 at 12:18
• Exercise 6.38 of Bazaraa et al., Linear Programming and Network Flows. Jul 6 '19 at 13:04