There is a lemma in the book saying:
"If the primal basic solution is an optimal solution of a linear program (P), B is not necessarily an optimal basis."
I don't understand because, by the dual theory, if the primal has a feasible solution and so does the dual, then B has to be optimal? I tried to find an example that matches this but I can't think of any. Can someone give me an example so that I can think this through?
It depends on how you define "optimal basis". In the presence of degeneracy, you can have a basis where the basic solution of the dual is not feasible, but the basic solution of the primal turns out to be optimal (and after some pivots you get an optimal basis with the same basic solution of the primal.
For an extreme example, consider the problem
$$ \eqalign{\text{maximize }\ x_1 &\cr \text{subject to }\ x_1 + x_2 \le 0\cr x_1, x_2 \ge 0\cr} $$ There is only one basic feasible solution: $x_1 = 0$, $x_2 = 0$, slack variable $s_1 = 0$. But not every basis is optimal.
