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