So now we are okay to several concepts of linear programs. Now we are ready to do some formulations. So for formulation we mean we are going to give you some practical application or seems to be some reasonable daily decision making problems. And then let's see how we may do linear programming formulation? To first precisely describe them. And the second, once we are able to find to form a linear program, we will be able to write computer programs to solve them and to get real solutions. So that's what we will do in today's lecture. Okay, so that's start by doing all the things. We now want to model practical situations. Once we do so, we will solve the problem because at least computers at least, solvers are able to help us to solve them even if we have no idea about how they do that. So the process is typically called LP formulation, linear programming formulation, or LP modelling, linear programming modelling. So, when you heard about formulation modelling, pretty much they are the same thing, okay? That's give you some example and don't forget practice makes perfect so maybe you need more examples, more exercises. But anyway that's try to see how to do that. And after we get some taste about simple formulation later we do some compact formulations for large scale problems. So consider a product mix problem. We want to produce several products and we want to sell them. Producing each product requires some resources and resources are limited. So there is no way for you to produce whatever amount you want because you have limited resources. We want to maximize the total sales revenue with our available resources. So let's see how to do that. Suppose in this example, we are producing just two items, desks and tables, okay. And producing a desk requires three units of wood, one hour of labor and the 15 minutes of machine time. So pretty much you need three resources, wood labor machine. And for machine you have one machine but you have limited machine time. You may choose to produce tables. Each table takes five units of wood, two hours of labor, but maybe is not so complicated. So for machine time, you only need 20 minutes. So you may see that Making these products takes resources. Then why do you want to do that? Because you may sell them. In this example, let's assume we may sell everything we produce. For each day we know the following thing. We have 200 workers that each works for eight hours. Okay, so you have a bunch of workers, each of them works for eight hours. You have 50 machines. Each of them runs for 16 hours, okay? So that's also something that you may use. Then finally, you have a supply of 3,600 units of woods. Once you make desk and tables, each of them may be sold at 700 or $900 per each per unit, okay? So that's the basic information we have. So what do we need to decide. In this particular example is simple, we need to decide two things. In each day how many desks we want to produce, and how many tables we want to produce. We need to somehow tell us what are some feasible plans and what are some optimal plans. What's the optimal way of making desks and tables? What's the optimal way to allocate our resources to this two different production activities, okay? So with these variables, we define. Now let's try to express our resource consumptions. So before that maybe it's even more easier to do the total sales revenue maximization because if you have x1 unit of table at desk and x2 units of table. Here, this is your total sales among or sales revenue, because for each desk, you may earn several $100 as your sales revenue, right? So in this particular case, we don't care about cost, we care about the revenues. So our objective function is simple, we try to maximize 700 times x1 + 900 times x2. So you may see that we want as many desks and tables as possible. But unfortunately there are some restrictions or there are some limitations where technically we call them constraints. We know for wood, I have at most 3600 units. But each desk and each table takes 3 or 5 units, okay? For labor hour, I have a limited amount of labor hours. I have 200 workers, each of them works 8 hours per day. So I have 1600 hours to be allocated to desks and tables. Finally I have machine time. Each machine I have 16 hours, so I have 800 hours in total. I also mentioned that these are 50 minutes, 20 minutes. So when I want to compare the minute consumption with the total supply, of coarse I need to, for example, multipliers 800 hours by 60 to know that I have 48000 machine minutes. So obviously, all these supplies are limited. So I may write down three inequalities to represent these resource constraints. The supply of wood is limited, right? So according to the amount of desks I want to produce, I know 3x1 is the total amount of wood I need to allocate to desk. 5x2 is the total amount of wood I need to allocate to table. The total amount I use cannot be greater than the total amount I have. For labor hour, the same thing, for machine time, the same thing. Just don't forget to use the same unit of measurement and then writing down these, it just takes some patience and some works. Collectively, we have a maximization problem, we want to maximize our sales revenue, subject to three resource constraints. And of course, don't forget that you cannot produce a negative number of desks or tables. So these two quantities should be non negative, okay? So this is pretty much the formulation we have, and indeed we may see this is a linear program. So for beginners we have some suggestions, or some typical things that all operations researchers follows. First, we always clearly define decision variables. And we do that before we write down our formulation. Here, even though we don't write them down in the same page, but you already mentioned that we do the definition. We do the variable definition before we try to write down everything, right? If you don't do that, then no one knows what do we mean by 3x1 + 5x2., okay? There's no way to judge whether this formulation is right or wrong if there is no clear definition of decision variables, okay? So this is always the most important and you need to put them in front of everything, okay? And also, we typically write objective function before constraints. We also write functional constraints in front of sign constraints, and that's the typical format. If you follow the typical format, it's easier for other people to understand your formulation. Finally, we suggest you to write comments after your formulation, or beside your formulation. These are the comments. This is saying that okay, the first one is talking about wood supply, the second one labor, the last one machine and so on. So all these are good thing to do if we are writing formulations. You already see that this is a two-dimensional problem, we only have two variables, right? So we may write something like this to solve a linear program. And I'm going to skip this part but maybe you want to try it by yourself. Eventually, we may really solve this problem and get an optimal solution, which is this one. In each day we're going to produce, okay? 884.21 that's and 189.47 tables. If this is the first time for you to learn linear programming, you may feel a little bit weird because a desk is a desk, 2 desks are 2 desks, what do we mean by 1.21 desks? Seems to be weird, right? So at the beginning this seems to be weird but that mean tell you how come it is acceptable. So first you are running a factory, in many cases, you don't run it for just one day, right? This suggestion, somehow just means today you do something and at the end you stop by having some unfinished furnitures, unfinished products and you go back to have sleep, tomorrow you go on to continue completing this one. Somehow that just means well in 100 days, please complete 888,420 desks and the sound values for tables, okay? So if you consider your production process as a continuous process then, this makes sense, right? This makes sense. Sometimes this is impossible. You just cannot stop, something that cannot be finished by one time, must be thrown away. That's also possible. So if that's the case then what do you do? This program still gives you a solution. This solution still can be converted by yourself into a feasible plan by just removing those fractional values, okay? So we work very hard, there are still some tiny resources that has not been used, just forget it. So the solution the model still give us suggestions. For example, this one, maybe we cannot run up, maybe we can run down because rounding up is going to violate some constraints but rounding down, it's safe in this case, okay? So even though this solution seems to be a little bit weird, it still supports decision making. As long as the model supports decision making, then it's good, okay? All models are wrong, but some are useful. All we want is decision support. All we want to get from a model from a linear program is that some suggestions may be provided. And then we decision makers, we make our own judgements, that's the typical process. So don't feel too uncomfortable about these fractional values. Also, don't try to require your x1, x2 to be integer values. If you do that, that's not a linear program, that's an integer program, something we will discuss in the future. But for today we only talk about linear programs and all the values should be real values instead of integer values, okay? So that's something I need to emphasize and you need to keep in mind
