3

In two phase simplex method we use artificial variables when our constraint is greater than or equal to some constant. I just want to know what is the purpose of these artificial variables?

Shariq
  • 61
  • It's so that you can transform the problem with inequalities into a problem with equalities. This allows you to use whatever machinery you've already developed to handle maximising a function on a simplex. – Patrick Stevens May 31 '18 at 20:07
  • Readers will find it easier to respond in a helpful way if you provide more context. For example, give an example of a linear program and how you approached it using the two phase simplex method. An answer can then show how one might (or might not) need artificial variables to solve it by the simplex method. – hardmath May 31 '18 at 20:15
  • Sorry! I didn't get it. Can you please elaborate? – Shariq May 31 '18 at 20:15
  • hardmath I don't have any problem in solving simplex method problems, I just want to know the reason of using artificial variables. – Shariq May 31 '18 at 20:26
  • The two-phase simplex method uses two kinds of "artificial variables"--one set are slack variables, which convert constraints of the form $\geq$ to the form $=$. The other, usually called "artificial variables", are used to find an initial solution which is feasible. It sounds like you are actually asking about slack variables? – David M. May 31 '18 at 23:23
  • See here for example. – David M. May 31 '18 at 23:24
  • Thanks David, the document you attached helps a bit. Actually, I was concern about "artificial variables", that are used to find an initial solution which is feasible. – Shariq Jun 01 '18 at 15:40

2 Answers2

3

I got my answer from other source. It clears all my confusion.

The general idea behind two-phase methods is create an auxiliary problem, with an obvious starting solution (which may be infeasible for the original problem), and with the objective of eliminating the infeasibilities. If the optimal auxiliary solution eliminates the infeasibilities, then the auxiliary solution values of the variables from the original problem can be used to start phase 2 with a basic feasible solution.

The artificial variables in phase 1 are introduced so that we can make the original problem variables nonbasic and set them to zero even though that may not be feasible to the original problem. The artificial variables take on the resulting infeasibilities and are basic at the start of phase 1. The phase 1 objective is to drive those variables to zero, at which point the original problem variables are feasible and the current basis consists of original problem variables. (Some minor cleanup may be necessary in the case of degeneracy.) Then one can use that basis as the start of phase 2.

If one can’t drive all the artificials to zero, that means the original problem has no feasible solution

Shariq
  • 61
-1

To use the simplex algorithm we need our LP in standard form $\textbf{maximise } f=\bar c^{T}\bar x$ subject to $A\bar x=\bar b$ and $\bar x\geq 0$. The reason for introducing slack variables is solely to convert the constraints $A\bar x\leq\bar b$ to the standard form $A\bar x=\bar b$ so that we can apply the simplex algorithm.

DaveyM94
  • 31