WIXLIB

.AcknowledgementsAcknowledgementsLet me begin by acknowledging the help and support that I have received from IIT Madras, whereI have the privilege and honour of serving as a faculty. The opportunity to teach some of the beststudents in the country is something that I am proud of as a teacher. I also acknowledge thesupport given by the Centre of Continuing Education, IIT Madras in terms of the financial supportand permission for writing this book.I respectfully remember all the professors who taught me this subject Professors Amarnathand K.N. Balasubramanian during my undergraduate days, and Professors T.T. Narendran andS. Kalpakam at IIT Madras. Professor Narendran has been a great teacher, a good friend and avaluable colleague. His contribution in shaping my career as a teacher is acknowledged. I thankmy colleagues in the Department of Management Studies at IIT Madras and other colleagues fromthe Department of Humanities and Social Sciences, where I served earlier. The interactions withProfessor Panneerselvam of Pondicherry University were useful.The first thought of writing a book on OR came during my stay at Lehigh University. I shouldthank Professor E.W. Zimmers (Jr) for the opportunity and the experience. Here I had theopportunity to interact with Professor M.P. Groover, whose useful tips on book writing came inhandy when I actually started writing. I also remember the meetings with Professor A. Ravindranboth at Penn State and at IIT Madras, from whom I drew motivation to write a book.It is impossible to acknowledge the names of all the students to whom I have taught thissubject. All of them have had a role in my process of learning to be a good teacher. Many otherstudents with whom I have spent hours discussing many things including Operations Researchhave contributed in their own way to what I am today. Natarajan Gautham and Hari Natarajan, twoof my students with whom I discussed interesting OR problems in person and over e-mails havefinetuned my thinking and teaching. My doctoral student Viswanath Kumar helped me inconverting some of the material into power point slides that have been useful. I take a lot ofpleasure in acknowledging the help that I received from my student Srikanth Srinivasan, withwhom I have had several coffee sessions that turned out to be OR sessions. We continue ourdiscussions on OR topics over phone, e-mail and over a cup of coffee frequently. The only wayI can acknowledge the enormous support that I have received from my students is by includingxv

xviAcknowledgementssome of their names in the problem situations that are presented in this book. Here again, it isimpossible to acknowledge all of them but I do remember all those students who contributed tothe discussions I had with them.My father is one person who certainly deserves a special mention. He believed that his sonshould write a book and constantly reminded me and encouraged me in this effort. I hope I havemade my parents proud through this effort. My wife Lata and kids Sathya and Hari have helpedme in their own way and words cannot describe the happiness that they have given me.Finally, I thank my publisher, PHI Learning for the spontaneous acceptance of my manuscriptand all for all the help and support extended to me during the production process of the book. Ialso wish an enjoyable reading of this book.

.AcknowledgementsAbout Operations ResearchOperations Research (OR) is a discipline that provides a set of analytical models for problemsolving and decision making. The results from solving OR problems are used extensively inengineering, management and public systems.OR models use theories, results and theorems of mathematics, statistics and probability in theproblem-solving process. It also has its own theories and algorithms that are being used byacademicians and practitioners.Operations Research is called Operational Research in Europe/Britain but the abbreviationOR is used for both throughout the world. This field is also called Management Science (MS) byAmericans. Sometimes both OR and MS are combined and called ORMS.OR as a field is over fifty years old. It started in the late 1930s and the history of OR has beentraced to several eminent contributors. In 1936, the early work in the field of attempting tointegrate radar data with the ground-based observer data for fighter interception, was the start ofOR. In 1938, a team to carry out research into the Operational (as opposed to technical) aspectswas created and the term Operational Research (Research into Military Operations) was coinedby Beasley. In the year 1942, the US Navy and Air Force used Operations Research in their warplanning activities.Today, the OR models include Mathematical Programming, Network Models, DecisionTheory, Queueing Theory and Nonlinear Optimization. Some books have included SimulationModels in their chapters while some have included Forecasting, Scheduling and ReplacementModels in their chapters. The topics under Mathematical Programming include LinearProgramming, Transportation and Assignment Problems, Integer Programming, DynamicProgramming and Nonlinear Programming.The field of optimization techniques also deals with OR models such as linear, dynamic andnonlinear programming models. Linear and nonlinear optimization is common to both the fieldsof operations research and optimization techniques.Another category of OR models is to classify them as deterministic and probabilistic models.Mathematical Programming deals with deterministic models while Stochasting Programming andQueueing theorgy use Probabilistic models. The field of inventory control, also part of OR, hasProbabilistic models.xvii

xviiiAbout Operations ResearchWhile most of the basic theories have been derived from Mathematics, the applications arefrom engineering, management and public systems. Most OR models attempt to provide optimalsolutions to problems and a lot of efforts have gone into providing or creating polynomiallybounded algorithms to several problems. Therefore, there are also inputs from computer sciencein topics of OR related to algorithms and analysis. Some OR problems have come out of graphtheoretic problems and, therefore, there is a strong relationship among mathematics, computerscience and graph theory.The solution to a problem using OR techniques involves three stages or phases. These are:· Formulation· Solution· ImplementationAmong these, solution methods have attracted the most attention among theoreticians whilethe practitioners of OR are interested in the implementation of the results. The formulation partinvolves both these groups. Most textbooks, research monographs and research publicationsprovide more treatment to solution methods than the other two aspects.It is difficult to trace the history of OR from the point of view of development of modelsbecause several results from mathematics are used in the OR models. Tracing the history of OR,one may be tempted to say that the book Mathematical Methods of Organization and PlanningProduction, by L.V. Kantorovich in the year 1939 could be termed the starting point of OR. Thetransportation problem was introduced in 1941 by Hitchcock. Several results and algorithms thatare used in OR today such as Königsberg Bridge Problem (by Euler), Bayes Rule (Bayes),Lagrangian multipliers (Lagrange), Solution of inequality systems (Farkas), Pareto Optimality(Pareto), Markov Chains (Markov), Probability theory (Erland) came much earlier in the 18th tothe 20th centuries.One of the significant contributors to the field of OR is G.B. Dantzig who is credited with theSimplex Algorithm (in 1947) and the Linear Programming theory. The Game theory was proposedby John von Neumann in his work Theory of Games and Economic Behavior, in 1944 anddevelopments in Game theory and Linear Programming were happening around the same time.The first OR journal, Operational Research Quarterly was started in 1950 and the Simplexmethod was formally established by Dantzig in 1952. Operations Research, first US OR journalwas started in 1952 and the Operations Research Society of America (ORSA) was also foundedin 1952. The first books on OR started appearing in the 1950s and 1960s while the first course inOR in MIT has been introduced earlier in 1948.In about six decades since its begining, OR became a well established field in its own rightwith several universities in the world offering graduate and doctoral programmes. It is learnt as acore subject in various engineering and management programmes all over the world. It is alsotaught and learnt as an elective in various undergraduate programmes of engineering, science andmanagement.A first course in OR usually deals with topics such as Linear Programming, Transportationand Assignment problems, Dynamic Programming and Inventory. Sometimes Queueing, GameTheory and CPM are included in the first course. An advanced course would address topics suchas Integer Programming, Advanced Topics in Linear Programming, Network Models andNonlinear Programming.

Linear Programming Formulations1.1Linear ProgrammingFormulationsLet us begin our discussion of Linear Programming (LP) with an example.ILLUSTRATION 1.1Product Mix ProblemConsider a small manufacturer making two products A and B. Two resources R1 and R2 arerequired to make these products. Each unit of Product A requires 1 unit of R1 and 3 units of R2.Each unit of Product B requires 1 unit of R1 and 2 units of R2. The manufacturer has 5 units of R1and 12 units of R2 available. The manufacturer also makes a profit of Rs. 6 per unit of Product Asold and Rs. 5 per unit of Product B sold.Let us address the above problem. The manufacturer has to decide on the number of units ofproducts A and B to produce. It is acceptable that the manufacturer would like to make as muchprofit as possible and would decide on the production quantities accordingly. The manufacturerhas to ensure that the resources needed to make the products are available.Before we attempt to find out the decision of the manufacturer, let us redefine the problem inan algebraic form. The manufacturer has to decide on the production quantities. Let us call themX and Y which are defined as follows:X Number of units of Product A madeY Number of units of Product B madeThe profit associated with X units of Product A and Y units of Product B is 6X 5Y. Themanufacturer would determine X and Y such that this function has a maximum value.The requirements of the two resources are X Y for R1 and 3X 2Y and the manufacturer hasto ensure that these are available.The problem is to find X and Y such that 6X 5Y is maximized and X Y 5 and3X 2Y 12 are satisfied. Also it is necessary that X, Y ³ 0 so that only non-negative quantitiesare produced.If we redefine the production quantities as X1 and X2 (for reasons of uniformity andconsistency) then the problem becomesMaximizeZ 6X1 5X21

2Operations Research: Principles and ApplicationsSubject toX1 X2 53X1 2X2 12X1, X2 ³ 01.1TERMINOLOGYThe problem variables X1 and X2 are called decision variables and they represent the solution orthe output decision from the problem. The profit function that the manufacturer wishes toincrease, represents the objective of making the decisions on the production quantities and iscalled the objective function. The conditions matching the resource availability and resourcerequirement are called constraints. These usually limit (or restrict) the values the decisionvariables can take.We have also explicitly stated that the decision variable should take non-negative values. Thisis true for all linear programming problems. This is called non-negativity restriction.The problem that we have written down in the algebraic form represents the mathematicalmodel of the given system and is called the problem formulation. The problem formulation hasthe following steps:1.2.3.4.Identifying the decision variablesWriting the objective functionWriting the constraintsWriting the non-negativity restrictions.In the above formulation, the objective function and the constraints are linear. Therefore, themodel that we formulated is a linear programming problem.A linear programming problem has a linear objective function, linear constraints and thenon-negativity constraints on all the decision variables.Let us consider some more examples to understand the linear programming formulationsbetter.ILLUSTRATION 1.2Production Planning ProblemLet us consider a company making a single product. The estimated demand for the product for thenext four months are 1000, 800, 1200, 900, respectively. The company has a regular time capacityof 800 per month and an overtime capacity of 200 per month. The cost of regular time productionis Rs. 20 per unit and the cost of overtime production is Rs. 25 per unit. The company can carryinventory to the next month and the holding cost is Rs. 3 per unit per month. The demand has tobe met every month. Formulate a linear programming problem for the above situation.Decision variables:Xj Quantity produced using regular time production in month jY j Quantity produced using overtime production in month jIj Quantity carried at the end of month j to the next month

3Linear Programming FormulationsÇ4Objective function:Minimize 20j 1Constraints:Ç4Xi 25ÇI4Yj 3j 1jj 1X1 Y1 1000 I1(Month 1 requirement)I1 X2 Y2 800 I2I2 X3 Y3 1200 I3I3 X4 Y4 900Xj 800 j 1,.,4Yj 200 j 1,.,4Xj, Y j, Ij ³ 0The above formulation has 12 decision variables and 12 constraints. Out of these, 4 are equations.We can eliminate the variables Ij by rewriting the constraints as:X1 Y1 ³ 1000(Month 1 requirement)X1 Y1 X2 Y2 ³ 1800X1 X2 X3 Y1 Y 2 Y3 ³ 3000X1 X2 X3 X4 Y1 Y2 Y 3 Y4 ³ 3900Xj 800 j 1,.,4Yj 200 j 1,.,4Xj , Y j ³ 0The objective function becomesÇ X 25Ç Y 3 (X Y 1000 X Y X Y 1800 X X X 4Minimize 204jj 1i111122123j 1Y1 Y2 Y3 3000 X1 X2 X3 X4 Y1 Y2 Y3 Y4 3900)If the total production exceeds 1000, the excess production is carried as inventory to thesecond month and so on. This explains the four-demand constraints. It may not be necessary toconsider ending inventory at the end of the fourth month. This constraint can be an equation. Forreasons of uniformity we have an inequality there. The cost of inventory is included in theobjective function. In any case, since the excess inventory is going to add to the cost in theobjective function, the minimization function will not allow excess inventory at the end of thefourth period in the solution.The second formulation has 8 variables and 12 constraints all of which are inequalities. In LPformulations, it is desirable to have inequalities. This is a better formulation than the first for thisproblem.Let us consider a third formulation by a new definition of decision variables. Let Xijk representproduction in month i to meet the demand of month j using production type k. (k 1 meansregular time production and k 2 means over time production). The constraints are

4Operations Research: Principles and ApplicationsX131 X132X141 X142 X241 X242X121 X231 X341X111 X122X232X342X121X221 X111X221X331X441X131X231X331X112 X122 X132X222 X232X332 X112 1000X222 800X332 1200X442 900X141 800X241 800X341 800X441 800 X142 200 X242 200 X342 200X442 200X111, X121, X131, X141, X221, X231, X241, X331, X341, X441, X112, X122, X132, X142, X222, X232, X242, X332,X342, X442 ³ 0The objective function is:Minimize 20(X111 X121 X131 X141 X221 X231 X241 X331 X341 X441) 25(X112 X122 X132 X142 X222 X232 X242 X332 X342 X442) 3(X121 X122 X231 X232 X341 X342) 6(X131 X132 X241 X242) 9(X141 X142)This formulation has 20 variables and 12 constraints out of which 4 are equations. This is notefficient as compared to the second formulation. (This formulation introduces us to minimizationof the objective function, and also helps us understand that the inequalities are desirable and theformulation with fewer constraints and variables is a better formulation).ILLUSTRATION 1.3Cutting Stock Problem (Gilmore and Gomory 1961)Consider a big steel roll from which steel sheets of the same length but different width have to becut. Let us assume that the roll is 20-cm wide and the following sizes have to be cut:9 inch 511 numbers8 inch 301 numbers7 inch 263 numbers6 inch 383 numbersIt is assumed that all the cut sheets have the same length (say, 25 inches). One dimensionalcutting is only allowed. The problem is to cut the sheets in such a way as to minimize wastage ofmaterial.From a 20-inch wide sheet, we can cut two 9 inches with a wastage of 2 inch. This is calleda cutting pattern and we can represent it is as [2 0 0 0] with a wastage of 2 inches. We write allthe possible patterns such that the wastage is less than 6 inches (minimum thickness desired),under the assumption that if the wastage exceeds 6, we can cut a 6-inch sheet out of the wastage.The possible cutting patterns are:

Linear Programming astagewastage 52422345501Let Xj be the number of sheets cut using pattern j. We have2X1 X5 X6 X7 ³ 5112X2 X5 X8 X9 ³ 3012X3 X6 X8 X10 ³ 263X3 3X4 X7 2X9 2X10 ³ 383Xj ³ ts)The objective function is to minimize wastage. This is given byMinimize2X1 4X2 2X4 3X5 4X6 5X7 5X8 X10However, if we make an assumption that excess sheets produced in every width are includedas waste (they are all inequalities because it may not be possible to get the exact number required),the objective function becomesMinimize 2X1 4X2 2X4 3X5 4X6 5X7 5X8 X1

Professor Department of Management Studies Indian Institute of Technology Madras Operations Research