Simplex Algorithm

Question

Please someone clarify in exam 2020.02.19 problem 9 as below:

1. why strengthen constraint to x0 <= 1 ?

2. why pivoting x0 with y1?

Thanks in advance.

Comments

x0 is the first variable that is non-integer. In order to make it integer, we force it down from 11/9 to 9/9 = 1. We then just run Simplex in the hope that the result is integer. See slide 78 https://es.cs.uni-kl.de/teaching/vrs/slides/VRS-08-PredLogic-1.pdf

Answer 1

1. (Also see the comment) The task was an integer solution. We tighten the bounds to integer bounds in the hope of finding integer solutions. See slide 78 https://es.cs.uni-kl.de/teaching/vrs/slides/VRS-08-PredLogic-1.pdf
2. We want to lower x0 from 11/9 to 9/9 = 1. You can see that in the line of x0, there is a negative coefficent for y0, and a positive one for y1. Following the regular order, we would first try to pivot y0. As y0 has a negative coefficent and x0 shall be lower, our pivoting would increase y0, which its bounds already forbid. Hence, our next try is y1. Positive coefficient means we lower it in order to lower x0. That is allowed. We called that suitable variables on slide 64 https://es.cs.uni-kl.de/teaching/vrs/slides/VRS-08-PredLogic-1.pdf