# If origin is not included in an LP problem how do we get a basic feasible solution?

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?

• The idea of phase I is to construct an auxiliary LP in which the artificial variables represent the infeasibility (constraint violation). When you solve this LP, you minimize the constraint violation (the sum of artificial variables). This means that you get a feasible solution for the original problem by solving the auxiliary problem, if at its solution all artificial variables are zero. Otherwise, the original problem is infeasible. – cvanaret Dec 5 '20 at 11:37

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.
• No, it cannot. If the original minimization objective is bounded below, then the auxiliary objective has that same lower bound because the artificial variables are nonnegative and penalized with $M>0$ in the objective. – RobPratt Dec 28 '20 at 15:07