The last example that we want to show you is personnel scheduling. Also this is a problem that is somewhat different from the previous ones. So that's the hostis. Suppose you are running a department store and you want to hire some employees to work there. Your store is good. So it opens seven days a week. So you need several workers for each day. The thing is that each employee is going to work for five consecutive days and then take rest for two consecutive days. Somehow that means if they start to work on Monday, they work for five days and Let's keep working until Friday. And then they have to holidays and then they go back to work on that's the idea of five consecutive days. You also realize that the number of employees you need for different days are different. For Monday you only need 110. For Tuesday you need 80. For Wednesday, somehow you need 150 and so on and so on. So according to the description above, we may say there are seven different ways to schedule your employees or they are seven shifts. The first shift is from Monday to Friday. The second shift is from Tuesday to Saturday. So if someone start to work on Tuesday is off days are Sunday and the Monday and so on. So because on days in a week they repeat and repeat. So in total, you just have seven different ways to let your workers go to work. So the thing is that we want to minimize the total number of employees that we need to hire. Okay? So finding feasible solution is not very difficult. For example, you may start to think about shift one. If you want to hire some persons to work in shift one and shift one is going to cover the first five days, right? So you may think, okay, I'm going to have 150 employees to work from Monday to Friday. Then you think about shift 6, for shift 6 now you need 160 to fulfill the demand for Saturday and Sunday. So altogether you hire 310 persons. But you can see that this is not a very good idea, because for some days you have much, many, many more A much higher number of persons then the amount you need, okay? For pretty much this is suggesting us that there should be some better solution. If you have some free time, maybe you may try to use your pencil and paper to try to find a better solution. I won't say it's easy, because that assignment to the seven shifts, needs some careful consideration that may be too hard for persons. So that's the whether linear programming may help us. So we have Monday, Tuesday, Wednesday. That say xi is the number of employees who start to work from day i for five consecutive days. I need to remind you again that definitions must be precise. If you say day i, you need to specify, you need to define what do you mean by day i, okay? Day 1 means Monday, day 2 means Tuesday, you need to specify that. So that also says x1, is the number of employees assigned to shift 1, x2 is the number of employees assigned to shift 2 As long as you have precise definition, how to describe it is up to you. So now our objective function is clear. We want to minimize the total number of workers we hire and assign to the seven shifts. And then we need to fulfil demands. We need 110 employees that work on Monday. So we need to ask ourselves how may we determine the number of employees that will work on Monday? So there are seven different shifts. So for shift one, those persons indeed work on Monday, but for shifted 2 and 3. They start to work on Tuesday and Wednesday. Monday is their holidays. So we don't have x 2 and x 3. In the left hand side of this constraint, we don't. Instead we have x 4,5,6 and 7. Because if you start to work on Sunday, you also work on Monday. If you start to work on Thursday, Friday, Saturday, you also work on Monday. If you start to work on Wednesday, you don't. So pretty much we may collect all those shifts. At left hand side, as those persons who will work on Monday, the sum of the persons in these five shifts must be at least 110. And then of course for Tuesday that's pretty much Much the same thing. If you start work on Monday or Tuesday, you work on Tuesday. If you start work on Wednesday or Thursday you don't. And for the other three you do, so the sum of these five must be at least 80. And so on and so on and so on. You also have non negativity constraints. So if you collect everything, this is your complete formulation. You need to minimize the total number of employees you hire, and for these seven days for each day, you count the number of workers who really works on that day and the non negativity then you are done with the formulation. Once you have the formulation, you input that into a solver, some people will tell you how to do the best decision, how to make the least cost hiring and assignment. Okay? Okay, so one thing I need to say at the end of this older examples is that, whenever we are writing linear programs, we always just set the variables to be, fractional to be real numbers. We don't really require them to be integer. So. This is important. So I need to talk about this for many, times. Don't do that. Don't do integer values when you are writing linear programs, if you say they need to be integers. Then you are doing integer programming. And very quickly you will see integer programming takes more time to be solved. So it would be better to work with linear programs. So I know it may take time to understand this. So just a quick summary. If someone asks you to write down a linear program, don't set variables to be integers. All right. So that's one comment. Another comment is that from time to time you need to modify the definition of your decision variables. For example, for many of the beginners when they see this problem, they would set decision variables as xi as the number of employees who work in AI. Okay they will write down things like this, but then very quickly you would see, even though for the objective function, it seems to be the same. But if you write it in that way is actually wrong. And then you also have no way to determine, to connect this decision variable set with your seven shifts. So then you may realize it and then modify your definitions. Somehow your definition would be good. If all the quantities you care about in the objective function in the constraints can be described can be expressed by using your definition of decision variables. If that's the case, eventually you will be able to write down any linear program you want.
