When a linear program is formulated like this:
$\begin{align}
\text{minimise}\quad &c^Tx\\
\text{subject to}\quad &Ax \ge b
\end{align}$
With $c\in \mathbb{R}^{|x|}$, $A \in \mathbb{R}^{n \times |x|}$ (where $n$ is the number of constraints) and $b \in \mathbb{R}$, we can say that the feasible region is the intersection of the half spaces associated with all of the linear inequality constraints.
However, sometimes I see linear programs formulated like this:
$\begin{align}
\text{minimise}\quad &c^Tx\\
\text{subject to}\quad &Ax = b
\end{align}$
How can we use this formulation to define a feasible region? If $b \in \mathbb{R}$, then the constraints define a set of lines, instead of half spaces. Do we now take $b \subseteq \mathbb{R}$ instead of some single element? Or, is the implication that we can write $x = y \Leftrightarrow x \ge y \land x \le y$, so the lines $Ax = b$ each define the boundary of a half space? If so, then how do we determine on which side of the boundary the feasible region lies?
Best Answer
If you like the first form better, you can write condition $Ax=b$ as $$\begin{bmatrix}A\\ -A\end{bmatrix}x\ge \begin{bmatrix}b\\ -b\end{bmatrix}$$
and work just like you would in the first instance with $2n$ constraints instead of $n$.