So let's take a look at this example. Again, our example is still this one. And let's take a look at our new primal problems. So it's here, right? And we already had 22 as our proposed solution. But unfortunately, this violates the third constraint. That's why you see in the last row you get a negative 1 here. This implies your current solution is infeasible. So if we want to fix primal infeasibility, what we need to do is to look at the negative right hand side values. Okay, so it's here. We know S3. Okay, S3 should not be an inside our basis. It should be kicked out from the basis. So it's going to be a leaving variable. And then we need to find a pivot, right? Somehow, let's assume when we find a pivot, we're going to do some row operations. Then with that, we should get an idea about which one should be the pivot. So don't forget that when you are doing all these processes, your pivot is always a number that is under your non basic columns, right? Typically, we are trying to look at non basic, non basic columns. We look at the negative reduced cost and obviously relationship in non basic. So again here is the same. There's no reason for you to think about these basic values. Okay, those values under the basic columns, you are not going to choose them as your pivot. You will only focus on non basic values on naturally. And you also know that non basic values they do have their reduced costs where basic ones they reduced costs are 0. And there's nothing we may do with ratio test. So we will focus on non basic ones. Among those non basic variables, we choose one to be the entering one here because we want to fix primal infeasibility. So very naturally, what we will choose is this one negative 2. The pivot must be a negative number so that when we do a row operation, we're going to flip the sign for the third constraint in this example. And that that's going to make negative 1 become positive, all right? So this somehow tells us that among or between negative 2 and 1 we will choose negative 2. So once we choose negative 2 as our pivot, what we will do is that first, let's do a row operation on row 3. We multiply every number by negative one half, okay? So this becomes 1, and this number becomes one half. And then we do natural row operations on row 0, row 1, and row 2. So once we do that again, we are trying to cancel out all these numbers in our pivot column, okay? But once we do that, a few iterations data, we will get to your new tableau. So your new tableau, this one looks very good, right? All the right hand side values are positive. All the reduced costs are non negative. And then we're done. This is our new optimal solution. We may also take a look at least new optimal solution. This is your X1. It is distorted downwards to 1 instead of 2. Because you cannot produce more than 1. This is your X2, and this is your S1. So somehow there is a resource constraint that it has some slicks there. And your new optimal solution gives you a objective value which is 19 over 2. So all of this has been explained. Here S3 leaves the basis and S1 enters the basis, okay? According to our calculation, the new basic solution becomes this one. This is a feasible one. Now it corresponds to the practical new solution 1 in the 5 over 2. So we fix our production quantity. And then gets a new optimal solution. This Z value 19 over 2 is less than 10, okay? And it makes sense because a new constraint restrict us somehow. So we cannot do as good as the previous one. So now we need to answer another question. There may be a possibility that you face multiple negative right hand side values. For example, in this case, okay? Suppose you have multiple right hand side numbers. Then we need to find a way to choose one, okay? In this case, actually, you may pick any one you like. So this situation is very similar to your primal simplex method, where you have multiple values that are negative as negative reduced cost. We may, for example, follow the smallest index rule to pick one. So here we also follow the smallest index rule. Let's pick X1, okay? So this is a way to deal with multiple right hand side negative values. And then maybe we may have multiple negative numbers. For example, here we have negative 2 and a negative 1. Choosing either one to be your pivot is going to fix this right hand side value. So we somehow need to consider which one to choose. All right, so the idea is here. Somehow we need to maintain dual feasibility, dual feasibility and translate that back to primal. That means your reduced costs should remain non negative. That's going to help us to pick one, okay? Let's take a look. Suppose you pick negative 2, okay? And then you flip the sign by multiplying every number by negative one half, okay? So you get this one. And then you do some ratio test. Let's focus on row 0. And then once you fix everything on row 0, you will see that this number becomes one half, okay? But if you pivot at a negative 1, okay? Then calculation seems to be easy. But once you try to fix row 0, you're going to give you a negative 1 here. So that's negative 1. That's negative reduced cost, of course, is very bad. Why is that? Because that tells you well, this seems to be an entering candidate while it should be in a leaving candidate. Okay, so that's weird. And why is that? Because by choosing to pivot at a wrong number, we're going to get to a place where we are primal infeasible and the dual infeasible. So that's something we don't know how to deal with. So don't do that. Here obviously, you should pivot at a number that is helping you to maintain dual feasibility. Helping you to maintain all the numbers as your reduced cost should be non negative. So quickly we may do a conclusion and remarks. Read the dual simplex method, basically help us deal with additional constraints. So that's the idea. The pivoting rule may be summarized here. First, there must be a basic variable that is negative. So that you need to initiate your dual simplex. So that must be a row with the negative right hand side. We may choose that. And then we need to do a ratio test. The principle of ratio test is to maintain non negative reduced costs, okay? So basically, we can say for those non basic columns with negative elements in the leaving row, all right? We would choose the reduced cost as the numerator and the absolute values of the negative elements as your denominators. So don't forget when you have a negative number here, the first screening reason is you need to think about how to fix your right hand side. So if you have multiple candidates, we focus on only those with negative numbers there. So that means you need to choose a negative pivot, okay? So and then when you are doing the ratio test, we take the absolute value of that negative element, all right as your denominator. And once you do that, the last thing to do is to choose a non basic variable with the smallest ratio. So pretty much everything is the same as your primal simplex method. It's just that sometimes you look at the negative number. In primal, you look at a negative reduced cost. In dual, you look at your negative right hand side. And then for the dual, you choose you focus on negative denominator. But when you do that when you do the ratio test, don't forget to make it absolute value. Then you are done. You may try this for a few examples by yourself. And then you will see how it works. So the last thing I want to say is that well, dual simplex seems to be just used to deal with a new constraints. Seems to be used unjust sensitivity analysis. But actually it is used in many other situations. For example, we all know that when we try to solve an integer program, one very fundamental method is the branch and bound algorithm. When we do that branch and bound, we know when we have a node, we're going to create two nodes by what? By adding constraints, right? We're going to add constraints, add constraints continuously to create new nodes. Whenever we create a new node, we need to solve it, right? So if you have a lot of linear programs to solve you can do that. You can always invoke in simplex method from the scratch. But now you don't need to do that. To solve a new node while we know the original optimal solution. If we know the optimal solution for your parent node, then for your new child node with one additional constraint, just use the dual simplex method that's going to help you a lot. Because in a natural branch and bound tree, you may have thousands millions of nodes to solve. This one and the next one, they are so similar. Why not use the previous one? All right, so that's the idea of dual simplex method. And that's something connected to branch and bound. Now we know branch and bound can be implemented in a faster way, much faster way if you take your simplex into consideration, all right? So that maybe also an instance an example showing you how theories, how knowing more theories help you invent better algorithms. Okay, that's the end for today. Thank you.
