Problem 9.16 of The Nature of Computation states
Jumpstart for LP. How do we find an initial feasible solution for the simplex algorithm? By solving another linear program for which we know a feasible solution! As we outlined in Section 9.4.1, we can transform the set of inequalities $\mathbf{Ax\leq b}$ into a set of equalities $\mathbf{A'x'= b'}$ by adding "slack" variables $\mathbf{s\geq 0}$. Hence we can assume that our linear program is of the form $$ \max_\mathbf{x}(\mathbf{c}^T\mathbf{x})\qquad\text{subject to}\qquad \mathbf{Ax=b}\qquad\text{and}\qquad \mathbf{x\geq0}\,. $$ By adding more variables, construct yet another linear program that has a trivial feasible solution, and whose optimal solution is a feasible solution of this problem. Hint: if $\mathbf{b}\in\mathbb{R}^m$, you need $m$ additional variables. Without loss of generality you may assume that $\mathbf{b\geq 0}$.
I'm stuck understanding why one can assume that $\mathbf{b\geq 0}$. It seems that this assumption would lead straight to having $\mathbf{x=0}$ available as a trivial solution which is a little too easy.
There have been suggestions to just multiply every row in which $\mathbf{b}$ is negative by -1. I don't think it's that easy. Take the following example:
$$ \max_\mathbf{x}([1]\cdot\mathbf{x})\qquad\text{subject to}\qquad \begin{bmatrix} 1\\ -1 \end{bmatrix} \mathbf{x}\leq \begin{bmatrix} 2\\-1 \end{bmatrix} \qquad\text{and}\qquad \mathbf{x\geq 0} $$ It can easily be seen that this is maximized for $\mathbf{x}=[2]$. The corresponding problem with slack variables $\mathbf{s}$ has the same optimum and we must have $\mathbf{s}=[0\;1]^T$ to achieve equality. Now suppose we multiplied the second row by -1 to ensure $\mathbf{b\geq 0}$. Then $\mathbf{s}$ would have to become $[0\;-1]^T$ to still achieve equality, violating the constraint $\mathbf{s\geq 0}$.