I have the following optimal tableau:

enter image description here

Thus $x = (0, 1, 0, 4)$ is the optimal solution. However, since non-basic variable $x_{1}$ has reduced cost of 0, then we have multiple optimal solutions.

Since the column $\hat{a}_{1} = [-1 -1]^{T}$, I cannot pivot $x_{1}$ into the basis for an alternative solution.

Given this, how do I express all optimal solutions?

  • $\begingroup$ It seems, that there is only one optimal solution. This is not an extraordinary case. $\endgroup$ – callculus Sep 27 '15 at 17:21
  • $\begingroup$ Wrong @calculus, see below. $\endgroup$ – GarryB Sep 29 '15 at 10:02
  • $\begingroup$ @GarryB How did you recreate the original problem ? $\endgroup$ – callculus Sep 29 '15 at 10:07
  • $\begingroup$ As there are only two constraints and one of the (presumed) slacks is still basic, I assumed that only one iteration had taken place to bring x2 in in place of x3 and just reversed it. The "-z" suggested that a minimisation problem had been converted to a maximisation one. On further thought, I've extended my answer below. $\endgroup$ – GarryB Sep 30 '15 at 8:40

As it's a problem with two constraints, I assume that x3 and x4 are slack variables. Going back a step, I recreate the original problem as

-x1 + x2 <= 1

x1 - 2x2 <= 2

x1 - x2 is to be minimised with x1, x2 non-negative

As the objective function is parallel to the first constraint boundary, multiple solutions exist, being anywhere along that boundary "northeast" of (0,1), so in general the solution is x1 >= 0, x2 = x1 + 1, o.f. = -1

The original problem has an unbounded feasible region, which is why there is only one optimal BFS, i.e vertex. If another constraint is added to truncate this, e.g. x1 + x2 <= 3, another optimal BFS will be found after the first iteration has exchanged x2 and x3. In the case suggested, this will exchange x1 and x5 (the new slack variable) to give a second optimal BFS at (1,2). The complete solution will then be any point between this and the original one at (0,1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.