# 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. – dreamer May 8 '13 at 18:59

## 1 Answer

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

• Thank you for your help! I understand the concept of using slack variables, however, how does this show that every solution of the first problem is also a solution of the second problem with the same objective value? – dreamer May 8 '13 at 19:24
• Because that makes both cases perfectly identical. If you want a more solid proof you can google "Karush-Kuhn-Tucker conditions". – AnilB May 8 '13 at 19:27
• Ok :). By the way, isn't the proof in reverse order (so from B to A) exaclty identical (but then in the opposite direction) to this one? – dreamer May 8 '13 at 19:30
• Check my edit for inverse transformation – AnilB May 8 '13 at 19:52
• @cruise any time... – AnilB May 9 '13 at 13:35