Week 13. Revised Simplex Algorithm

[@Batuta-ys7ri]

Great explanation, however, I am not quite sure what to do when the coefficient of x's were equal to each other. In this case -60 was the most negative and we choose x1 as entering, what if x2 and/or x3 had 60 coefficient as well. In that case all of them would be -60 the most negative, then which variable do we choose as entering variable?

[@coverCell]

Hello! Thanks for the question. In this case, suppose we have more than one variable having the most negative coefficients, then you may choose any one of those as the entering variable. In the end, you will obtain the same optimal solution(s), if it (they) exists.

[@edofransisco2484]

I have a question about the z value in the last part of the video. The equation written there is B two inverse * b which is the same with the top one. So what does it use the 48 20 8 not the answer from the top 24 8 2

[@coverCell]

Hi Edo. In 16:00 when we calculate z-value, we use (c_BV * B inverse 2) * b. Remember that "b" is always the original rhs, that's why b = [48 20 8]. If you want to use [24 8 2], which is (B inverse 2 * b), you can also do it. Since the BVs are s1, x3, x1; then c_BV = [0 20 60]. Then, do the multiplication: c_BV * (B inverse 2 * b). The multiplication of [0 20 60] and the column vector [24 8 2] gives the same result, i.e., 0*24 + 20*8 + 60*2 = 280.

[@dominicblanco8383]

On both B_0 and B_1 where you do Gaussian elimination, why is the result multiplied by what R_3 and R_2 were multiplied by? For B_0, you did 1/2R_3, but you applied the 1/2 to every element in the final result. For B_1, you did 2R_2, but you applied 2 to every element as well. At this point, the third column also changed. It became -8 -4 1.5. How did this happen? My understanding is that multiplying a row by a constant just changes that row, not the entire matrix. That's how I learned Gaussian elimination. What am I missing?

[@coverCell]

In 13:45, it is explained that in the next iteration, the column of x3 should change from [-1 0.5 0.25] to become [0 1 0]. To achieve that, we multiply second row by 2: 0.5*2 = 1. For the first row: (Old Row 1 + R2) = -1 + 1 = 0. For the third row: (Old Row 3 - 0.25R2) = 0.25 - 0.25*1 = 0. Now, in 14:05, we need to update the Binverse_1 to Binverse_2. Do the update by applying the same three rules for the first, second, and third rows to Binverse_1, and you will get the result of Binverse_2. I hope this explanation clarifies the matter.

[@That_One_Guy...]

I found that without ratio test and determining the most negative coefficient to determine pivot (instead of doing those two i choose the pivot diagonally, from upper left x_1 until bottom right x_3) seems to also worked out nicely, why? Additional Detail : what i mean by diagonally choosing pivot is i choose pivot like how you choose it when you're doing gauss elimination to find intersection point of 3 planes or 2 lines. Like this : x_1 x_2 x_3 c_1 0 0 0 c_2 0 0 0 c_3 Pivot(iteration 1) = c_1 Pivot(iteration 2) = c_2 Pivot(iteration 3) = c_3

[@coverCell]

Hello! That is an interesting idea. However, how do you choose the correct columns (basic variables), i.e., x_1, x_2, x_3? Because we usually have many more variables (columns) than constraints (rows). For example, we have 6 variables, but only 3 constraints. So, out of x_1, x_2, ..., x_6; how you would pick 3 out of them, I wonder.

[@johncassidy2230]

@14:06 for the first row of B^-1*a3 shouldn't the calculation be (1*1)+(0*1)+(-4*1)= -3 , not -1? This in turn effects the transformation needed to get to the canonical form, which would be (Old Row 1)+6(R2) I don't know how that difference in transformation would affect the answer.

[@coverCell]

Hello! The calculation is (1*1)+(0*1)+(-4*0.5) = -1. Notice that the last term is -4*0.5. Thank you for commenting and watching my videos!