[Music] [Music] [Applause] [Music] [Applause] [Music] good morning viewers I am dr. Kusum deep professor at the Department of Mathematics Indian Institute of Technology Roorkee I am here to present a course on operation research which is one of the leading areas of study as well as research now let us see some points about this course first of all who should attend this course so this course can be attended by ug and PG students gate aspirants UGC CSIR net aspirants research scholars and industry personnel the areas of specialization that would be interested in this course are science engineering management finance and business some of the topics that we are going to cover in this course are the linear programming problem and its variants multi objective and goal programming problems transportation and assignment problems sequencing and scheduling problems and game theory this course runs over 40 lectures and as you will see a number of examples and case studies will be dealt with also from time to time I will be giving you some exercises based on what we have learnt in the previous lectures so this is lecture number 1 on the title as introduction to our models the outline of this lecture is as follows first we will talk about the introduction to the subject of operation research and some definitions then we will come to the modeling of real-life as linear programming problems we will look at different types of our models and finally some question and answers and some exercises so what is operation research operation research is that branch of mathematics which is used to model and solve real-life problems in such a way that optimum decision is to be made so wherever there is a decision-making process the optimization techniques and the operation research techniques come into handy whether it is a day to day activity or some advanced engineering or science or business or financial applications now the operation research has the following sub areas of study the first one is called the linear programming problems they are also called the linear optimization problems next is the non linear programming problems or the non linear optimization problems queueing theory is that branch of operation research which studies the queues for example when you go to a bank to withdraw your money you have to follow a queue similarly when you are putting up some jobs on a computer then a queue is lined up so this queueing theory studies the behavior of queues reliability theory is also one of the major areas of operation research which studies the reliability of a system whether it is a mechanical system whether it is the building the civil engineering structure of a building and so on game theory is another very interesting area of operation research which talks about the decision making process when game is played between two or more than two components the network analysis is that study which talks about the study of the networks for example when we have to design a network which is let us say the Internet Service Providers or some other kind of network it is a study of the network analysis then comes the inventory inventory control is an important aspect when business has to be dealt with that is when a commodity has to be stored in some warehouse and the decision has to be made as to how much quantity of the commodity should be there in the inventory so that the customers are not lost and at the same time the cost of storing that commodity is minimized so first let us define what do we mean by a optimization problem because as I said that optimization is the key area of operation research whether it is network analysis or whether it is queueing analysis everywhere we encounter the optimization problem now the mathematical definition can be stated as follows minimize or maximize a function f of X which is a real valued function defined on the RN space that is the n-dimensional euclidean space and it is a real valued function so it is mapped onto the real numbers X the capital X is X 1 X 2 xn is the decision parameters these are the parameters which have to be determined and these x values should belong to a set s where s is a subset of RN defined by the following conditions GK X is greater than or equal to 0 where K go from 1 to up to M similarly HJ X is equal to 0 where J goes to 1 2 up to L and AI is less than X I is less than B i 4i goes to 1 2 up to n now this F is called as the objective function that is this is the function which has to be either maximized or minimized depending upon the problem at hand now the G case that is G 1 X G 2 X they are called the inequality constraints if they are less than equal to type then they can be converted to the greater than equal to type the HDX are called the equality constraints and these conditions are called the lower and upper bounds and of course these X 1 X 2 each of these X 1 X 2 s they are called the decision parameters decision values or decision parameters these are the ones that have to be determined now in general all these functions they are the real valued functions and they are in general non linear so in general f GI h i are non linear as a special case when they are linear then the problem is called as a linear optimization problem or a linear programming problem so first of all let us look at the various components of an optimization model the first one is the decision variables these are the variable that have to be determined for a given problem as I said in the previous slide X 1 X 2 X n these are the decision parameters they have to be determined they are called the decision variables or decision parameters second component is the objective function what is to be minimized or maximized and the third component are the constraints that is those conditions which the decision parameters should satisfy now let us look at the various kinds of classification that could exist in the various kinds of optimization problems the first one is the linear programming problem which I mentioned earlier that is those problems in which all the functions involved that is f G IHI they are all linear this is the specialized case of a linear programming problem the second category is called the non linear programming problems that is moment any one of F G I or H I they are lead a non linear then the problem becomes a non linear optimization problem now it may be possible that the problem does not have any constraints so in such a situation the problem is called as a unconstrained optimization problem however the moment even a single constraint is imposed on the decision parameters then it is called as a constraint optimization problem then there could be a classification which is based on the type of the decision parameters what does this mean the first one is called the dynamic programming problem this means that the decision variables are dependent upon each other with the help of a particular parameter usually time so that means there they are multistage programming problems and that's the reason why they are called as dynamic because the decision parameters are dependent on the time factor or some other stage so they are called the dynamic programming problems then there could be geometric programming problems in such type of problems the decision variables could be taking negative powers as well that is for example X 1 to the power minus 2 X 2 to the power minus 10 like this so they are called the geometric programming problems then comes the integer programming problems in these kind of problems the decision parameters are restricted to take only integer values they are not allowed to take the real parametric values then comes the quadratic programming problems these are those problems in which the objective function is a quadratic function whereas the constraints are linear then comes the separable programming problems in such type of problems the objective function is of the type which is of function of one variable only that means let us say F 1 of U 1 plus F 2 of u2 like this so the objective function can be broken into a number of terms such that each objective function is of one restricted variable only also we have the stochastic programming problems in which the decision parameters are stochastic in nature another classification that exists is based on the objective function if there are more than one objectives to be minimized or maximized it is called as a multi-objective optimization problem in general a multi objective optimization problem could be nonlinear and in the specialized case you could also have what is called as a multi objective linear programming problem so both the possibilities exist that is linear multi objective and non linear multi objective problem programming problems then there are problems in which a particular goal is to be achieved by the objective function and these are called as the goal programming problems also there could be a situation where a number of levels are to be achieved by the various objectives involved in the objective function they are called as multi level programming problems so other kind of problems could exist that is the fuzzy programming problems in which the decision parameters are fuzzy in nature stochastic programming problems in which the decision parameters and the constraints and the objective function are stochastic in nature recently another category of problems and methods has come into existence which are called as evolutionary computations these are these derive their inspiration from living organisms and in this category we have the genetic algorithms mimetic algorithms differential evolution evolutionary strategies another category that is come into existence in the last 20 years is the swarm intelligence techniques these techniques are based on the swamp behavior of a group of living organisms whether it is a group of birds flying in the sky or some of the fish that are swimming in a pond some of these techniques in this category are called the particle swarm optimization ant colony optimization bacterial foraging artificial bee colony and many more so now we will come to the simplex case of the linear programming problem so first of all let us look at the mathematical definition of a linear programming problem the objective function is a linear function which has to be minimized or maximized it is of the type c1 x1 plus c2 x2 plus CN xn so as you can see that I have used the x1 and x2 and xn as small so the decision parameters are x1 x2 xn and this could be subject to the following conditions a 1 1 X 1 plus a 1 2 X 2 plus a 1 n xn is less than or equal to B 1 similarly a 2 1 X 1 plus a 2 2 X 2 plus a 2 n xn is less than or equal to B 2 a M 1 X 1 plus a M 2 X 2 plus a M n xn less than or equal to BM all the decision parameters X AI there should be greater than or equal to 0 where I goes to 1 to up to n note that in general M need not be equal to n and M and n are both positive integers also these parameters AI J's CIS and VJs they are all real numbers so our decision vector x1 x2 xn this is our decision vector this has to be determined subject to the conditions that are given in these inequalities n is called as the size of the problem size of the problem now the same definition can be written in terms of metrics notation that is minimize or maximize subject to minimize or maximize C transpose X subject to ax is less than or equal to B and X is greater than or equal to 0 now let us look at some of the definitions which are related to the linear programming problems any vector X satisfying all the constraints of the problem is called as a feasible solution all those feasible solutions they combine to become the feasible region so the feasible region is defined as the set of all feasible solutions out of these feasible solutions there is one which is called as the optimum solution and this means that the objective function is the best so the best feasible solution is called as the optimum solution now by best we mean either minimum or maximum depending upon the problem at hand and finally the value of the objective function at that optimum solution is called the optimum value so modeling of real-life problems as linear programming problems please note that operation research is one such subject which is used to solve real-life optimization problems and that is what we are trying to understand how real-life problems can be modeled as optimization problems either linear item ization problems or non-linear optimization problems so first of all the case of modeling real-life problems as linear programming problems so here is an example it is the maximization of the profit so it's called the profit maximization problem the problem states that a company wishes to produce a product for which it has three models to choose from the labor and the material data for each model is given also the supply of raw material is given to be 200 kgs and the available manpower is given to be 150 hours we are required to formulate the model so as to determine the daily production such that the profit is maximized now the data that is given in the problem is as follows there are three models a B and C and the labor in terms of hours labor is in terms of hours it is given per unit so per unit of model a requires seven hours of labor similarly per unit of model B requires three units of labor and similarly the C model it requires six units of six hours of labor the second thing is the materials so material is in terms of kg so model a requires four kg of material model B requires again four kg of material and model C requires five kg of model C then comes the profit the model a per unit has profit of rupees 4 and 4 B it is 2 and for C it is 3 so this is the data that is given in the problem now we will try to model the problem in three steps the first step is identification of the decision variables so these are the variables which we have to determine so let us assume that we have the following decision variables x1 is equal to the number of units to be produced of model a similarly x2 is the number of units to be produced of model B and X 3 is the number of units to be produced of model C these are X 1 X 2 X 3 are the decision variables and this is what we have to determine second step is the identification of the constraints so these are the constraints 7 x 1 + 3 x2 + 6 X 3 is less than or equal to 150 how did this constraint come from look at the data that is given to you in the problem let me go back to the table so here you see in the first row of the table 7 3 & 6 these are the coefficients of each unit of model a model B and model C so since we have assumed x1 to be a variable that is the number of units to be produced of model a so 7 has to be multiplied by x1 and similarly 3 has to be multiplied by X 2 and 6 has to be multiplied by X 3 and all of them together when you add them up this should satisfy the condition that is they should be less than or equal to 150 by 150 because in the problem it is given that there are 150 hours of labour which is available so therefore the sum of all these three terms should be less than or equal to 150 in the similar manner we have the second constraint that is 4 X 1 plus 4 X 2 plus 5 X 3 should be less than or equal to 200 and of course all the decision variables X 1 X 2 X 3 should be greater than or equal to 0 and they should be integers of course the value of I goes from 1 to up to 3 why they have to be integers because you can produce either 6 units of model a or you can produce 7 units of model a you cannot produce 6. 5 units of model a that is the reason why this integer requirement is important the third step is the identification of the objective function that means what is it that we have to minimize or maximize so here we find in our case the profit has to be maximized and what is the expression for the profit it is given by 4 X 1 plus 2 X 2 Plus 3 X 3 why did this come from because in the last row of the table you can see in the table that is given this is the last row profit in terms of rupees that is one unit of model a requires 4 rupees similarly one unit of B requires 2 units and similarly one unit of model C requires 3 units so 4 X 1 plus 2 X 2 Plus 3 X 3 this is the expression for the profit and obviously it is come sense that the profit has to be maximized so you have to take a decision what do you have to do with the objective function whether it has to be maximized or minimized depending upon the problem at hand so therefore these are the decision parameters in step number one and step number two we have identified the constraints and in step number three we have identified the objective function which has to be maximized in this case so this is the way that using these three steps you can model a given problem into a linear programming problem which is also called as the linear optimization problem second problem is regarding the work schedule Inc problem these kind of problems have lots of applications whether it is the shadowing of the workers shadowing of the nurses or scheduling of any kind of stuff so in this problem there is a post office which requires different number of full-time employees on different days of the week the daily requirement is given in the table below and the union rules state that each full-time employee must work for five consecutive days and then take two days off that is the Union rule says that there should be five days working we are required to formulate the problem as an LP P so that the post office can minimize the number of full-time employees who should be hired so let us look at the data that is given the data says that the seven days of the week has the following requirement of number of full-time employees so first of all if you call Monday as number one day then it requires 17 number of full-time employees for Monday similarly for the day - that is Tuesday there are 13 full-time employees that are required and like this for the remaining days of the week this is the data this is given in the problem so first step is identification of the decision variables so it's very simple just define X I to be the number of employees beginning their work on day number I so X 1 X 2 X 3 X 7 till X 7 these are the number of full-time employees that should be employed on each of the seven days of course all the excise should be greater than or equal to zero because you cannot talk about minus ten number of employees so they have to be greater than equal to zero and also there should be integers because you can either employ five employees or you can employ six employees so therefore integer restriction has to be imposed then comes the objective function now the objective function is the sum of all the employees that have to be employed on all the seven days that is X 1 X 2 X 3 up to X 7 and this has to be minimized because the more you employ the more cost is incurred so therefore one was interested in only minimizing the total number of employees then comes the constraints now for each of the seven days of the week we have these constraints X 1 plus X 4 plus X 5 plus X 6 plus X 7 is greater than or equal to 17 you will ask why I have not written X 2 and X 3 in the first equation in the first equation at X 2 and X 3 are missing because the these are x2 and x3 employees they have to take two days off okay so therefore during the taking care of the union rules these number of employees have to be removed from the first equation and like this for the second equation we have to remove x3 and x4 and like this of course the permutation could be interchanged depending upon the way one tries to model and define X 1 X 2 etcetera so like this these are the constraints and as you know that they look there are 7 days so there are 7 constraints the third problem is about the industrial problem it says that a company has three operational departments these departments are called the weaving processing and packaging with the capacity to produce three different types of clothes which are called as suiting shirting and woolen yielding a profit of rupees two rupees for and rupees 3 per meter respectively one meter suiting requires three minutes in weaving two minutes in processing and one minute in packing similarly one minute of shooting requires two minutes in weaving one minute in processing and three minutes in packing while one meter of woollen requires three minute in each department in a week total runtime of each department is given to be 60 40 and 80 hours of weaving processing and packing Department respectively we are required to formulate the problem as a LPP to find the product in such a way that the profit is maximized so the first thing is let us tabulate the given information in the form of this table so there are three types of cloths that are available suiting shirting and woolen and three types of processing that is the weaving the processing and the packaging also the profit in terms of each unit and also on the right hand side is the available time that is in terms of hours so since we have to take care of the unit's some data is given in terms of minutes and the available time is given in terms of hours so hours should be converted into minutes in order to take care of the dimension of the data so we have three for three in the first row and this is less than or equal to 3600 so I think you are now fairly comfortable in guessing how we will define the decision parameters we will define the decision parameters as follows let x1 be the number of units in terms of meters for the suiting cloth X to be the number of units of shutting and x3 be the number of units of woollen and we have to maximize the profit that is 2 X 1 plus 4 X 2 Plus 3 X 3 so this is the data that is given so profit 2 X 1 plus 4 X 2 Plus 3 X 3 and also the constraints that are given are as follows 3 X 1 plus 4 X 2 Plus 3 X 3 less than or equal to 3600 and similarly the other constraints 2 X 1 plus X 2 plus 3 X 3 less than or equal to 2400 x1 plus 3x2 plus 3 X 3 is less than or equal to 4800 and of course X 1 X so x3 they should all be greater than or equal to zero please note that in this particular problem we need not impose the integer requirement because x1 x2 is the number of units and that number of units of a cloth it could be fractional also that is you could have either two meters or you could have three meters or you could even have two point three four meters or you could have two point five meters as well so therefore the integer requirement is not necessary in this particular example another interesting applications is about the advertising now the owner of a win/win sports company wishes to determine how many advertisements to place in the monthly magazines a B and C his objective is to advertise in such a way that the total exposure to the principle buyers of the expensive sports good is maximized the percentage of readers of each magazines is known and also the exposure in any particular magazine is the number of advertisements placed in that magazine multiplied by the number of principle buyers and this information can be recorded in this table that is magazine a magazine B and magazine C the readers how many readers are there magazine a has one lakh readers magazine B has 0.
6 lakh readers and magazine C has 0. 4 lakh readers and the principle buyers are 20% 15% and 8% for the three magazines a B and C also the cost per advertisement in terms of rupees is given to be eight thousand six thousand and five thousand for each of the three magazines a B and C now the budget amount is at most rupees one lakh for the advertisement and the owner has already decided that magazine a should have no more than fifteen advertisements and that the B and C magazines have at least 80 advertisements so we are required to formulate the given problem as a linear programming problem so let us first of all define the decision parameters let x1 x2 and x3 be the number of insertions in the magazines a B and C respectively and the objective function can be written as follows which is nothing but the the total exposure that is how many people are going to read it so we have to maximize the total exposure and mathematically it can be written as 20% of one lakh times x1 plus 15% of 60,000 times x2 plus 8% of 40,000 times x3 and when you simplify this you get the following expression and the constraints for each of the conditions that is the budgeting constraint because the budget is given to be 1 lakh so therefore the budgeting constraint can be written as 8 thousand x1 plus 6,000 x2 plus 5,000 x3 which should be less than or equal to 1 lakh and similarly the advertising constraint says that the first magazine should have not more than 15 advertisements so therefore X 1 should be less than or equal to 15 as far as the B and C magazines are concerned they must have at least 80 advertisements so therefore Stu should be greater than or equal to 80 + x3 should be greater than or equal to 80 of course the decision variables X 1 X 2 X 3 should be greater than or equal to 0 and they should be integers because you cannot insert 2. 5 insertions in advertisements in a magazine either you insert 2 or you insert 3 so therefore integer restriction is important the fifth problem is called the portfolio optimization problem assume you have inherited rupees 1 lakh from your father that can be invested in two kinds of stock portfolios with the maximum investment allowed in either portfolio set as rupees 75 thousand the first portfolio has an average rate of return of 10% whereas the second has 20% in terms of risk factors the first and the second portfolio have a risk rating of 4 and 9 respectively on a scale of 0 to 10 since you wish to maximize your returns you will not accept any average rate of rate of return below 2 at 12% or a risk factor above 6 hence you face the important question how much you should invest in each portfolio for this we will model the problem as a LPP so given data can be used to model the problem as follows maximize zero point X 1 plus zero point X 2 of course X 1 and X 2 are the amount that you have to invest in both the schemes subject to the condition X 1 plus X 2 is less than equal to 1 lakh X 1 is less than or equal to 35 thousand x2 is less than or equal to 75,000 0.
1 X 1 plus 0. 2 X 2 should be greater than or equal to 0.
