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$.


  • $\begingroup$ Are you expecting someone to do your homework or take-home exam problem for you? $\endgroup$ Jul 3 '19 at 11:42
  • $\begingroup$ 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. $\endgroup$ Jul 3 '19 at 11:51
  • 5
    $\begingroup$ You should add the "self-study" tag (if you can, show us what what you have done, and indicate where you need help. $\endgroup$ Jul 3 '19 at 11:54
  • 1
    $\begingroup$ Who is Bazaraa who you mention in your question? $\endgroup$
    – JakobS
    Jul 3 '19 at 12:18
  • 2
    $\begingroup$ Exercise 6.38 of Bazaraa et al., Linear Programming and Network Flows. $\endgroup$ Jul 6 '19 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.