Given the following constraints for an LP problem:
\begin{align}
x_1 + 2x_2 &\ge 4 \\
-3x_1 + 4x_2 &\ge 5 \\
2x_1 + x_2 &\le 6 \\
x_1 , x_2 &\ge 0
\end{align}
When I draw the feasible region I see the origin is not included.
Since we can't get an identity matrix by just adding slack variables, artificial variables are introduced as well.
\begin{align}
x_1 + 2x_2 -x_3 + x_6 &= 4 \\
-3x_1 + 4x_2 – x_4 + x_7 &= 5 \\
2x_1 + x_2 + x_5 &= 6 \\
x_1 , x_2, x_3,x_4,x_5,x_6,x_7 &\ge 0
\end{align}
Here $x_6$ and $x_7$ are artificial variables. The textbook states an initial basic feasible solution is $(0,0,0,0,6,4,5)$. However I don't understand when the origin is not included in the original problem how did adding artificial variables include the origin?
Best Answer
Introducing the artificial variables relaxes the problem, making the feasible region larger. The initial feasible solution for the relaxed problem is not feasible to the original problem, but that’s OK. The purpose is just to get the algorithm started. After a few steps, the artificial variables become $0$, and you obtain a feasible solution to the original problem.