0

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?

RobPratt
  • 45,619
moli
  • 69
  • 1
    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. – Charlie Vanaret Dec 05 '20 at 11:37

1 Answers1

1

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.

RobPratt
  • 45,619
  • can adding artificial variable make a bounded problem into unbounded (not for the original problem but the reformulated one) – moli Dec 28 '20 at 13:48
  • 1
    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
  • If we do not take into consideration the objective function for the original problem not the altered version obtained by adding artificial variables but just the feasible region. Can feasible region be enlarged by adding artificial variables such that it will become unbounded? – moli Dec 28 '20 at 16:27
  • 1
    Yes, the auxiliary problem has an unbounded feasible region. You can make the artificial variables as large as you want. – RobPratt Dec 28 '20 at 16:29