Show that two Linear Programming problems are equal

Question

Consider the general linear programming problem

$min \sum_{j=1}^n c_jx_j$

s.t. $\sum_{j=1}^n a_{ij}x_j \leq b_i$, for $i=1,\dots , m$

$x_j \geq 0$ for $j=1,\dots , n$

And the corresponding extended formulation

$min \sum_{j=1}^n c_jx_j$

s.t. $\sum_{j=1}^n a_{ij}x_j + x_{n+i} = b_i$ for $i=1,\dots m$

$x_j\geq 0$ for $j=1,\dots,m+n$.

Show that both problems are equivalent. Hint: two problems $[A]$ and $[B]$ are equivelent if for each feasible solution of $[A]$ there is a corresponding feasible solution of $[B]$ with the same objective value and vice versa.

---

Being a feasible solution of $A$ means that all constraints of $A$ should be satisfied. However, I cannot seem to find a way to show that then all constraints of $B$ should also be satisfied. Can anyone please help me out?

Answer 1

In extended form the inequality constraints in first case can be written as $$a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n\le b_1$$ $$a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n\le b_2$$ $$...$$ $$a_{m,1}x_1+a_{m,2}x_2+...+a_{m,n}x_n\le b_m$$ Let's introduce some slack variables $x_{n+i}\ge 0$ into the inequality constraints such that $$a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n+x_{n+1}= b_1$$ $$a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n+x_{n+2}= b_2$$ $$...$$ $$a_{m,1}x_1+a_{m,2}x_2+...+a_{m,n}x_n+x_{n+m}= b_m$$ In short form $$\sum_{j=1}^{n} a_{i,j}x_j+x_{n+i}=b_i\quad for\,i=1,...,m$$ And the first case is transformed into the second one

------EDIT-------

We can rewrite the equality conditions in B such as $$\sum_{j=1}^{n} a_{i,j}x_j=b_i-x_{n+i}\quad for\,i=1,...,m$$ Since the question states that $x_j\ge 0$ for $j=1,...,m+n$ we can eliminate $x_j$ for $j> n$ by using inequality constraints without loss of generality such that $$\sum_{j=1}^{n} a_{i,j}x_j\le b_i\quad for\,i=1,...,m$$