VRS - Exam [February 16, 2022], Problem 9a (Simplex Algorithm)

Question

In the second step, when  y₂=-5 violates the bound  [-4, +∞], why do we make x₁ basic variable instead of choosing y₁. 

In the previous exam questions (e.g. August 25th, 2020, February 17, 2021) we used to replace with the first non-basic variable.

I think, I am failing to understand the step "find suitable x_j for pivoting with y_i" as given in Exercise 10 solutions page 5. How do we find suitable x_j?

Answer 1

In the second step, we have the equation y2 = -5/3 * y1 + 4/3 * x1 and y2 has to increase from -5 to -4 to fullfill the constraints. We cannot use y1 for pivoting because y1 will decrease when y2 will increase and because of this, y1 would become less than 3 and would violate its constraint. This is seen by the coefficient -5/3 which is negative.

Hence, we have to check whether x1 can be used for pivoting, and since x1 does not have bounds, we can obviously choose it for pivoting.

Comments

Exam [February 17, 2021] - Question 9a:

- If two constraints are invalid, like for y0 and y1, does it matter which constraint do we choose to solve first? (Normally I choose to solve the first constraint)

- In step 2 of the same question ([February 17, 2021] - Question 9a), where we are choosing y1 as a pivot against y0, can we also choose it against x1 instead of y0 because it does not violate x1 costraint since x1 does not have bounds?

- Considering the above two questions, is it possible to have multiple correct solutions?

---

If two constraints are invalid, you can choose anyone to proceed with first. Also, there may be several candidates for pivoting, and again, it does not matter which of these you choose. You should just avoid an infinite looping, which can be done by ordering the variables and choosing the minimal ones. For these reasons, there are in general many correct solutions, just like a propositional logic formula may have many satisfying variable assignments.