2

I have a linear program that I want to solve using the Simplex Method. I would like help figuring out how to initialize the tableau from a given feasible solution.

I have found many instructions how to initialize the tableau generally. But they all involve introducing slack/artificial variables in order to derive an initial feasible solution where all the original variables are set to $0$. However, for my program I already know an initial solution from which I would like to start.

Concretely my program is $$\text{max } -\theta \text{ subject to}$$ $$(\sum_{i = 1}^{n} c_i^{(1)}\lambda_i) - c_k^{(1)}\theta + s^{(1)} = 0$$ $$(\sum_{i = 1}^{n} c_i^{(2)}\lambda_i) - c_k^{(2)}\theta + s^{(2)} = 0$$ $$(\sum_{i = 1}^{n} c_i^{(3)}\lambda_i) - c_k^{(3)}\theta + s^{(3)} = 0$$ $$(\sum_{i = 1}^{n} c_i^{(4)}\lambda_i) - s^{(4)} = c_k^{(4)}$$ $$\sum_{i = 1}^{n} \lambda_i = 1$$ where $k$ is some number in $\{1, \ldots, n\}$ and the $c_i^{(j)}$'s are nonnegative constants. In this case setting $\theta = \lambda_k = 1$ and all other variables to $0$ would be a solution. How would I construct the initial tableau given this initial solution?

Guut Boy
  • 153

1 Answers1

1

In any case you MUST introduce artificial variables. There is no way to avoid them. I mean you started from some Corner Point, okay. But then? To walk through other points you need to introduce slack variables, actually using M method — google it. As all your constraints are not in general form, then you should add slack variables with $M$ coefficient, which if very big number, in all of them.

And if we assume that you have 5 constraints in your problem, then you will have 5 slack variables. Then, as I understand, if you know your initial feasible solution without introducing slack variables, then your slack variables will be of value $0$. And others are those you have as initial values. It means you make your slack variables be non-basic, and others are basic. Hope this helps.

P.S.: look at this answer too. https://stackoverflow.com/questions/17289032/solving-a-linear-program-in-case-of-an-equality-constraint

As mentioned there you can also change equalities to 2 inequalities, but by doing so you also increase the number of constraints. So you can choose either M-method or replacing equalities with inequalities.

Community
  • 1
Turkhan Badalov
  • 1,083
  • I looked up the M method, and it seems to apply only to the case of finding an initial feasible solution where the origin is not one. How would you apply it to creating the initial tableau for a non-origin feasible solution that is known? (I don't want to find a new solution, I already have one.) – weux082690 Apr 20 '18 at 14:01