Clarification about Simplex Algorithm concepts

Question

We have the following generic program:

$max \;\; c^Tx$
$\quad \quad Ax \le b$
$\quad \quad x \ge 0$

where $x$ is the vector of variables $(x_1, x_2,..., x_n)$. Suppose the origin is feasible. The it is certainly a vertex since it is the unique point at which the n inequalities are tight.

Now suppose we have the following LP:

$max \; 2x_1 + 5x_2$
$1)\quad 2x_1 - x_2 \;\;\;\le 4$
$2)\quad x_1 + 2x_2 \;\;\;\le 9$
$3)\quad -x_1 + x_2 \;\le 3$
$4)\quad x_1 \ge 0$
$5)\quad x_2 \ge 0$

Simplex can be started at the origin specified by constraints (4) and (5).
To move we release the tight constraint $x_2 \ge 0$. As $x_2$ is gradually increased, the first constraint it runs into is $-x_1+x_2\le3$ and thus it has to stop at $x_2=3$ at which point the new inequality is tight.
The new vertex is given by (3) and (4)

I have 2 questions:

1) What is meant by "inequality is tight"
2) Why does $x_2$ have to stop at 3?

Answer 1

1. The ineqaulity $a\ge b$ is tight iff $a=b$. In optimization context it is often called an active constraint.
2. $x_2$ has to stop at $x_2=3$ because looking at the third constraint we get for $x_1=0$ (at the origin, unchanged) and $x_2=3$ (as increased from zero) $$ -x_1+x_2=0+3=3\le3. $$ Hence, equality again (=tight), and the interesting things can happen.

Look at the picture below. We start at the origin $A$, increase $x_2$ and arrive at the point $B$ where (3) and (4) are tight. Now to make the objective function larger we increase $x_1$ this time, keeping (3) tight, and arrive at the point $C$ where (3) and (1) are tight. It is the optimal point. Observe that we are moving along the edges of the feasible set from smaller to larger objective values. It is how Simplex method works.