So very quickly, let's jump into our first topic. It's about evaluating a new variable. So let's study this motivating example. There's a company selling two kinds of products. I'm going to leave all the sentences here for you to read by yourself. But anyway, the idea is very simple. The two products are here. They may be sold at $2 or $3 if you make one unit of them. There are two resources. Each has four unit or six unit as the upper limit for each day, okay? And if you want to make one unit of product 1, you need one unit of resource 1 one and one unit of resource 2. If you want to make one unit of product 2, you need one unit of resource 1 and two units of resource 2, okay? So very quickly, we may formulate this very typical, very classic linear program about product mix, about resource allocation, okay? So if we want to solve this problem, at least we have two ways. We either draw a graph or we use the simplex method. So very quickly, let's review the simplex method. Your first copy all the numbers into your Tableau and then you flip the sign for your objective row. Then you take a look at your objective row. You see that there is a negative number. Let's say we use the smallest index rule. And then what we will do is that we will choose this column to be the entering column. We do this ratio test, 4 is less than 6, so we're going to choose x1 as our pivot. And then we do some row operations to eliminate this number, that number to eliminate all other numbers in the entering column. Then we reach our second Tableau and then we do everything again. So this is a negative reduced cost. We do the ratio test, 1 is the denominator. And then 2 is smaller than 4, so we find our pivot. We do it again. Then we're done, because in our last Tableau, there is no negative reduced cost. We can see this identity matrix here. This number is x1. This number is x2. In our optimal solution, each of the products should be made for two units, and then our objective value would be 10. So this is a very typical problem that we know how to solve. Its just a linear program. So now let's consider a situation. We now have a new activity, or in this particular case, a new product. So somehow, our company is not just satisfied with the two products. We are trying to see whether there are some new products that customers love it, so we may sell it at a higher price and it's easier to make. And then we invent our third product. One unit of product 3 requires just one unit of resource 2 and can be sold at a very high price, $8, okay? Then we have a new formulation. Pretty much, we have a new option here. It's resource consumption is just one unit of product 2 and it may be sold at $8. So now let's say we still want to find an optimal solution. If we want to do that, that's pretty much okay because it's nothing but another linear program. So we may solve this new program from scratch. Let's say we start from here. So now we can see we have a new column, right? We still use our smallest index rule. So this is our iteration 1, iteration 2, iteration 3. In the third iteration, we can see that x3 has the negative reduced cost. So we try to enter this one. And then we do one more iteration, now x4 also have a negative reduced cost. We do it again. So the last two variables who enters our bases are x3 and x4. But we can see the solutions here. X3 should be 6, x4 should be 4. We should produce six units of product 3. And then we don't need to produce any product 1 or any product 2 because they are non basic. We will have four units of resource 1 left there because there's no need to use them in our optimal plan. Our new profit is $48, okay? So all those discussions are good. We know how to solve the problems and our problems somehow makes sense. If you go back to look at the resource consumption, go back to look at the unit sales price, you would agree product 3 is much more profitable than the first two. And it turns out that in our optimal solution, there is no need to consider product 1 and 2. We just use all our resources to make product 3. But the thing is that sometimes you are facing not so trivial problems, okay? That example was amazing because your product 3 dominates the first two products. But in most cases, your product 3 is simply another option. You somehow need to mix product 3 with your products 1 and 2, okay? So you really need to solve this problem carefully. The thing is that we just solved a problem with n activities. Now we have a new problem or a new instance which has n+1 activities, okay? And we know the older original activities are still there. All the resource limitations are still there. So the two problems or two instance are just so similar to each other, right? If that's the case, we should somehow expect we are able to move from an optimal solution of the original one to our new solution. Somehow that means you already spent a lot of time finding your original optimal solution under the original setting. So now you're setting is just changed a little bit. Maybe it is possible for us to move from the original problem to the new problem, to move from the original optimal solution to the new optimal solution, okay? So that's our plan and that should help us save a lot of time, because the initial point is here, okay? And then we do a lot of search to get to our original optimal solution. Now the problem is changed a little bit, so the new initial solution is here and we have no idea about where is our optimal solution. But ideally, it should be able to be found by just go from our original optimal solution instead of going from our initial point. So that's the plan. So this is an idea, and this may be even more required if your problem is really complicated. For example, when you need to use the two-phase method, when you have millions of variable, millions of constraints. All right, so this is our motivation. Next, we will see how to do this.
