# Show that two Linear Programming problems are equal

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?

• @copper.hat My bad, I made a typo. I edited the post. Commented May 8, 2013 at 18:59

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
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$$