First of all, I am confused as to the wording of the problem, they say the new constrain is $a^T x \geq \beta$, but they didnt say what $a$ is. Can we assume is a row of $A$?
IF so, then here is what I can do:
Since $x^*$ is feasible to the new constraint, then we know so far that $a^T x^* \geq \beta $. To prove optimality, i Need to problem that $c^T x^* \leq c^T x $ for all $x$ that satisfies all the constrains including the new one. We know however that
$$ c^T x^* \leq c^T y $$
where $ y $ satisfies the old constrains: $Ay \geq b $ and $y \geq 0 $. Here Is where I get stuck. Am I on the right track to prove this proposition?
If we argue by contradiction. Suppose $x^*$ is not optimal to new added constrain so there is some $x'$ so that $c^T x' > c^T x^*$.
Here, if $x'$ also satisfies $Ax' \geq b $ and $x' \geq 0$ then that would be a contradiction since that means we would have found another point in the feasible region that is bigger than the smallest value.
But, I am still haveing trouble understanding why is this $x'$ also belongs to the old constraint. What am I missing here?