BACHELOR OF BUSINESS ADMINISTRATION SEMESTER-V OPERATION RESEARCH
First Published in 2021 All rights reserved. No Part of this book may be reproduced or transmitted, in any form or by any means, without permission in writing from Chandigarh University. Any person who does any unauthorized act in relation to this book may be liable to criminal prosecution and civil claims for damages. This book is meant for educational and learning purpose. The authors of the book has/have taken all reasonable care to ensure that the contents of the book do not violate any existing copyright or other intellectual property rights of any person in any manner whatsoever. In the event, Authors has/ have been unable to track any source and if any copyright has been inadvertently infringed, please notify the publisher in writing for corrective action. 2 CU IDOL SELF LEARNING MATERIAL (SLM)
CONTENT Unit 1 - Introduction To Operation Research ......................................................................... 4 Unit 2 - Linear Programming .............................................................................................. 28 Unit 3 - Formulation Of Linear Programming ..................................................................... 45 Unit 4 – Transportation Problems Part 1.............................................................................. 83 Unit 5 –Transportation Problems Part 2............................................................................... 99 Unit 6 – Assignments Problems......................................................................................... 123 Unit 7 – Game Theory....................................................................................................... 147 Unit 8 – Simulation ........................................................................................................... 172 Unit 9 – Inventory Management Techniques ..................................................................... 185 Unit 10 – Pert/Cpm ........................................................................................................... 200 Unit 11 – Decision Theory And Decision Trees................................................................. 215 Unit 12 – Decision Making ............................................................................................... 228 3 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 1 - INTRODUCTION TO OPERATION RESEARCH STRUCTURE 1.0 Learning Objectives 1.1 Introduction 1.2 Basic Concepts 1.3 Decision- Making 1.3.1 Complex 1.3.2 Problems 1.3.3 Operational Research 1.3.4 Optimization 1.4 Summary 1.5 Keywords 1.6 Learning Activity 1.7 Unit End Questions 1.8 References 1.0 LEARNING OBJECTIVES After studying this unit, you will be able to: Define the term operations research. Get insights on the basic concepts of operations research. Appreciate the potential of operations research in decision making needs for an organization in every aspect. 1.1 INTRODUCTION An operation research (OR) is an analytical method of problem-solving and decision-making that is useful in the management of organizations. In operations research, problems are broken down into basic components and then solved in defined steps by mathematical analysis. The process of operations research can be broadly broken down into the following steps: 1. Identifying a problem that needs to be solved. 4 CU IDOL SELF LEARNING MATERIAL (SLM)
2. Constructing a model around the problem that resembles the real world and variables. 3. Using the model to derive solutions to the problem. 4. Testing each solution on the model and analysing its success. 5. Implementing the solution to the actual problem. Disciplines that are similar to, or overlap with, operations research include statistical analysis, management science, game theory, optimization theory, artificial intelligence and network analysis. All of these techniques have the goal of solving complex problems and improving quantitative decisions. The concept of operations research arose during World War II by military planners. After the war, the techniques used in their operations research were applied to addressing problems in business, the government and society. Characteristics of Operations Research There are three primary characteristics of all operations research efforts: 1. Optimization- The purpose of operations research is to achieve the best performance under the given circumstances. Optimization also involves comparing and narrowing down potential options. 2. Simulation- This involves building models or replications in order to try out and test solutions before applying them. 3. Probability and statistics- This includes using mathematical algorithms and data to uncover helpful insights and risks, make reliable predictions and test possible solutions. Importance of Operations Research The field of operations research provides a more powerful approach to decision making than ordinary software and data analytics tools. Employing operations research professionals can help companies achieve more complete datasets, consider all available options, predict all possible outcomes and estimate risk. Additionally, operations research can be tailored to specific business processes or use cases to determine which techniques are most appropriate to solve the problem. Uses of Operations Research Operations research can be applied to a variety of use cases, including: Scheduling and time management. Urban and agricultural planning. Enterprise resource planning (ERP) and supply chain management (SCM). 5 CU IDOL SELF LEARNING MATERIAL (SLM)
Inventory management. Network optimization and engineering. Packet routing optimization. Risk management. Applications of Operations Research Today, almost all fields of business and government utilize the benefits of Operations Research. There are voluminous applications of Operations Research. Although it is not feasible to cover all applications of O.R. in brief. The following are the abbreviated set of typical operations research applications to show how widely these techniques are used today: Accounting Assigning audit teams effectively Credit policy analysis Cash flow planning Developing standard costs Establishing costs for by-products Planning of delinquent account strategy Construction Project scheduling, monitoring and control Determination of proper work force Deployment of workforce Allocation of resources to projects Facilities Planning Factory location and size decision Estimation of number of facilities required Hospital planning International logistic system design Transportation loading and unloading Warehouse location decision Finance Building cash management models 6 CU IDOL SELF LEARNING MATERIAL (SLM)
Allocating capital among various alternatives Building financial planning models Investment analysis Portfolio analysis Dividend policy making Manufacturing Inventory control Marketing balance projection Production scheduling Production smoothing Marketing Advertising budget allocation Product introduction timing Selection of Product mix Deciding most effective packaging alternative History of Operations Research Operation Research is a relatively new discipline. Whereas 70 years ago it would have been possible to study mathematics, physics or engineering (for example) at university it would not have been possible to study Operation Research, indeed the term O.R. did not exist then. It was really only in the late 1930's that operational research began in a systematic fashion, and it started in the UK. As such it would be interesting to give a short history of O.R. 17th, Probability based problem solving by Christian Huygens and Blaise Pascal ~1890, Scientific Management by Frederick Taylor ~1900, Control chart (Project Scheduling) by Henry Gantt Systems change over time by Andrew A. Markov Network model: assignment approach ~1910, Optimal Inventory Theory by F. W. Harris Average waiting time for telephone callers (Queuing Theory) by E. K. Erlang ~1920, Quality control charts William Shewart Quality Control (Sampling) by H. Dodge and H. Romig 7 CU IDOL SELF LEARNING MATERIAL (SLM)
~1930, Game Theory by Jon von Neuman and Oscar Morgenstern ~ 1940, Simplex method (Linear Programming) by George Dantzig ~ 1950, Non-linear Programming by H.Kuhn and A.W.Tucker Integer Programming by Ralph Gomory PERT and CPM (Project Scheduling) Dynamic Programming by Richard Bellman ~ 1960, Queuing Theory by John D.C. Little Simulation Management science as “the business use of OR” by Stafford Beer ~ 1980, Multiple-criteria decision-making (MCDM) by Stanley Zionts New Linear Programming by N. Karmarkar India was one the few first countries who started using operations research. In India, Regional Research Laboratory located at Hyderabad was the first Operations Research unit established during 1949. At the same time another unit was set up in the Defence Science Laboratory to solve the Stores, Purchase and Planning Problems. In 1953, Operations Research unit was established in Indian Statistical Institute, Calcutta, with the objective of using Operations Research methods in National Planning and Survey. In 1955, the Operations Research Society of India was formed, which is one of the first members of the International Federation of Operations Research societies. Today Operations Research is a popular subject in management institutes and schools of mathematics. Classification of Operations Research Model Deterministic Model Linear Optimization Linear programming (LP) Integer programming (IP) Transportation and assignment model Multi-criteria decision-making programming (MCDM) Network models Nonlinear optimization Classical model Search model 8 CU IDOL SELF LEARNING MATERIAL (SLM)
Nonlinear programming Hybrid Model PERT-CPM Dynamic programming Inventory model Simulation model Stochastic Model Decision analysis model Markov model Queuing Model 1.2 BASIC CONCEPTS Operations Research (OR) is also known as management science, decision science or industrial engineering. It helps in providing quantitative aid to the management in a decision- making process. The main objective of operations research is to find the best or optimal solution to the problem under consideration. It is also the scientific study of large systems with a view to identify problem areas and provide managers with a quantitative basis for decisions which will enhance their effectiveness in achieving the specified objectives. In order to get a clearer idea of what OR, let’s try to solve a specific problem below and then highlight some general lessons and concepts from this specific example. Two Mines Company The Two Mines Company own two different mines that produce an ore which, after being crushed, is graded into three classes: high, medium and low-grade. The company has contracted to provide a smelting plant with 12 tons of high-grade, 8 tons of medium-grade and 24 tons of low-grade ore per week. The two mines have different operating characteristics as detailed below. Mine Cost per day (£'000) Production (tons/day) High Medium Low X 180 63 4 Y 160 11 6 How many days per week should each mine be operated to fulfil the smelting plant contract? Note: this is clearly a very simple (even simplistic) example but, as with many things, we have to start at a simple level in order to progress to a more complicated level. 9 CU IDOL SELF LEARNING MATERIAL (SLM)
Guessing To explore the Two Mines problem further we might simply guess (i.e. use our judgement) how many days per week to work and see how they turn out. work one day a week on X, one day a week on Y This does not seem like a good guess as it results in only 7 tonnes a week of high-grade, insufficient to meet the contract requirement for 12 tonnes of high-grade a week. We say that such a solution is infeasible. work 4 days a week on X, 3 days a week on Y This seems like a better guess as it results in sufficient ore to meet the contract. We say that such a solution is feasible. However it is quite expensive (costly). Rather than continue guessing we can approach the problem in a structured logical fashion as below. Reflect for a moment though that really we would like a solution which supplies what is necessary under the contract at minimum cost. Logically such a minimum cost solution to this decision problem must exist. However even if we keep guessing we can never be sure whether we have found this minimum cost solution or not. Fortunately our structured approach will enable us to find the minimum cost solution. Two Mines Solution What we have is a verbal description of the Two Mines problem. What we need to do is to translate that verbal description into an equivalent mathematical description. In dealing with problems of this kind we often do best to consider them in the order: 1. variables 2. constraints 3. Objective. We do this below and note here that this process is often called formulating the problem (or more strictly formulating a mathematical representation of the problem). 1. Variables These represent the \"decisions that have to be made\" or the \"unknowns\". Let x = number of days per week mine X is operated y = number of days per week mine Y is operated Note here that x >= 0 and y >= 0. 2. Constraints 10 CU IDOL SELF LEARNING MATERIAL (SLM)
It is best to first put each constraint into words and then express it in a mathematical form. ore production constraints - balance the amount produced with the quantity required under the smelting plant contract Ore High 6x + 1y >= 12 Medium 3x + 1y >= 8 Low 4x + 6y >= 24 Note we have an inequality here rather than an equality. This implies that we may produce more of some grade of ore than we need. In fact, we have the general rule: given a choice between an equality and an inequality choose the inequality. For example - if we choose an equality for the ore production constraints we have the three equations 6x+y=12, 3x+y=8 and 4x+6y=24 and there are no values of x and y which satisfy all three equations (the problem is therefore said to be \"over-constrained\"). For example the (unique) values of x and y which satisfy 6x+y=12 and 3x+y=8 are x=4/3 and y=4, but these values do not satisfy 4x+6y=24. The reason for this general rule is that choosing an inequality rather than an equality gives us more flexibility in optimising (maximising or minimising) the objective (deciding values for the decision variables that optimise the objective). days per week constraint - we cannot work more than a certain maximum number of days a week e.g., for a 5-day week we have x <= 5 y <= 5 Constraints of this type are often called implicit constraints because they are implicit in the definition of the variables. 3. Objective Again in words our objective is (presumably) to minimise cost which is given by 180x + 160y Hence we have the complete mathematical representation of the problem as: Minimise 180x + 160y Subject to 6x + y >= 12 11 CU IDOL SELF LEARNING MATERIAL (SLM)
3x + y >= 8 4x + 6y >= 24 x <= 5 y <= 5 x, y>= 0 There are a number of points to note here. A key issue behind formulation is that IT MAKES YOU THINK. Even if you never do anything with mathematics this process of trying to think clearly and logically about a problem can be very valuable. A common problem with formulation is to overlook some constraints or variables and the entire formulation process should be regarded as an iterative one (iterating back and forth between variables/constraints/objective until we are satisfied). The mathematical problem given above has the form i. All variables continuous (i.e. can take fractional values) ii. A single objective (maximise or minimise) iii. The objective and constraints are linear i.e. any term is either a constant or a constant multiplied by an unknown (e.g. 24, 4x, 6y are linear terms but xy is a non-linear term). iv. Any formulation which satisfies these three conditions is called a linear program (LP). As we shall see laterLPs are important. We have (implicitly) assumed that it is permissible to work in fractions of days - problems where this is not permissible and variables must take integer values will be dealt with under integer programming (IP). Often (strictly) the decision variables should be integer but for reasons of simplicity we let them be fractional. This is especially relevant in problems where the values of the decision variables are large because any fractional part can then usually be ignored (note that often the data (numbers) that we use in formulating the LP will be inaccurate anyway). The way the complete mathematical representation of the problem is set out above is the standard way (with the objective first, then the constraints and finally the reminder that all variables are >=0). Discussion Considering the Two Mines example given above. 12 CU IDOL SELF LEARNING MATERIAL (SLM)
This problem was a decision problem. We have taken a real-world situation and constructed an equivalent mathematical representation - such a representation is often called a mathematical model of the real- world situation (and the process by which the model is obtained is called formulating the model).Just to confuse things the mathematical model of the problem is sometimes called the formulation of the problem. Having obtained our mathematical model we (hopefully) have some quantitative method which will enable us to numerically solve the model (i.e. obtain a numerical solution) - such a quantitative method is often called an algorithm for solving the model. Essentially an algorithm (for a particular model) is a set of instructions which, when followed in a step-by-step fashion, will produce a numerical solution to that model. You will see some examples of algorithms later in this course but note here that many algorithms for OR problems are available in packages. Our model has an objective that is something which we are trying to optimise. Having obtained the numerical solution of our model we have to translate that solution back into the real-world situation. We can also define a mathematical model as consisting of: Decision variables, which are the unknowns to be determined by the solution to the model. Constraints to represent the physical limitations of the system. An objective function. A solution (or optimal solution) to the model is the identification of a set of variable values which are feasible (i.e. satisfy all the constraints) and which lead to the optimal value of the objective function. Phases of an OR Project Drawing on our experience with the Two Mines problem we can identify the phases that a (real-world) OR project might go through. 1. Problem Identification Diagnosis of the problem from its symptoms if not obvious (i.e. what is the problem?) Delineation of the sub problem to be studied. Often we have to ignore parts of the entire problem. Establishment of objectives, limitations and requirements. 2. Formulation as a Mathematical Model 13 CU IDOL SELF LEARNING MATERIAL (SLM)
It may be that a problem can be modelled in differing ways, and the choice of the appropriate model may be crucial to the success of the OR project. In addition to algorithmic considerations for solving the model (i.e. can we solve our model numerically?). We must also consider the availability and accuracy of the real-world data that is required as input to the model. Note that the \"data barrier\" (\"we don't have the data!!!\") can appear here, particularly if people are trying to block the project. Often data can be collected/estimated, particularly if the potential benefits from the project are large enough. You will also find, if you do much OR in the real-world, that some environments are naturally data-poor, that is the data is of poor quality or non-existent and some environments are naturally data-rich. 3. Model Validation (or algorithm validation) Model validation involves running the algorithm for the model on the computer in order to ensure: The input data is free from errors The computer program is bug-free (or at least there are no outstanding bugs) The computer program correctly represents the model we are attempting to validate The results from the algorithm seem reasonable (or if they are surprising we can at least understand why they are surprising). Sometimes we feed the algorithm historical input data (if it is available and is relevant) and compare the output with the historical result. 4. Solution of the Model Standard computer packages, or specially developed algorithms, can be used to solve the model (as mentioned above). In practice, a \"solution\" often involves many solutions under varying assumptions to establish sensitivity. For example, what if we vary the input data (which will be inaccurate anyway), then how will this affect the values of the decision variables? Questions of this type are commonly known as \"what if'' questions nowadays. Note here that the factors which allow such questions to be asked and answered are: The speed of processing (turn-around time) available by using pc's; and The interactive/user-friendly nature of many pc software packages. 5. Implementation This phase may involve the implementation of the results of the study or the implementation of the algorithm for solving the model as an operational tool (usually in 14 CU IDOL SELF LEARNING MATERIAL (SLM)
a computer package). In the first instance detailed instructions on what has to be done (including time schedules) to implement the results must be issued. In the second instance operating manuals and training schemes will have to be produced for the effective use of the algorithm as an operational tool. It is believed that many of the OR projects which successfully pass through the first four phases given above fail at the implementation stage (i.e. the work that has been done does not have a lasting effect). As a result, one topic that has received attention in terms of bringing an OR project to a successful conclusion (in terms of implementation) is the issue of client involvement. By this is meant keeping the client (the sponsor/originator of the project) informed and consulted during the course of the project so that they come to identify with the project and want it to succeed. Achieving this is really a matter of experience. A graphical description of this process is given below. Figure 1.1: A graphical description of the phases of an OR project 1.3 DECISION- MAKING Undoubtedly, decisions hold immense significance in an organisation. For enhanced decision-making and problem-solving, operation research is pivotal. A decision can be made after analysing all the relevant information, facts and data. This is where operation research proves utilitarian. Operation Research is considered to be the most supportive means in management because it can help in resolving any uncertain or complex problem easily. 15 CU IDOL SELF LEARNING MATERIAL (SLM)
Different methods such as stimulation, queuing theory, game theory, mathematical & network analysis which are part of operation research are considered as major helpers in the decision-making process. There are various reasons for which operation research can be significant in decision making and in management. For an organisation’s growth, decisions, controlling, productivity as well as coordination rule over other components. In this sense, operation research is also imperative as it leads to well-informed decisions. This, in turn, garners different benefits for the organisation such as: Effective decisions Enhanced control Improves productivity 1.3.1 Complex Decisions have to be taken in this complex world. Making a decision solely on a single criterion appears insufficient in which the decision is making process deals with a complex organizational environment. It is impossible to squeeze the complexity of opinions, motivations and the goals found in organizations into a single objective. Therefore, decisions may involve several objectives that are conflicting in nature. Decision maker may be an individual or a group of individuals. The presence of several criteria which are wholly or partially contradictory in nature leads to the development of multi-criteria decision making problems or multi-criteria optimization problems. Therefore, decision making is a multi- criteria optimization. Sometimes decisions are analytical and it requires the data. Operational research is only the means of taking the decision and provides the data to the manager to take the appropriate and valid decision. The managers use this quantitative data for taking the decisions and find out the better decision. Hence, it is used to solve complex problems. In operations research, problems are broken down into basic components and then solved in defined steps by mathematical analysis. 1.3.2 Problems OR (Operations Search) defines analyses and solves the problem based on data, information, facts in a systematic, scientifically, and logically manner. It is useful when quantitative models are built upon and modified by creative insights and experiences of decision-makers, which is an increasing degree of decision management. It gives the developments to decision making as:- Define the problem. Comparative study. Correct solution at the correct time. 16 CU IDOL SELF LEARNING MATERIAL (SLM)
Creation of optimum strategy. Creation of reaction graph. Deployment of resources. Draw the sensitivity of fluctuation. Forecasting and determining long-range objectives. Production of myriad quantitative models. Project completion in time. Provides the tool for scientific analysis and Solutions for various problems. Selection of the best course for action. Systematically and scientifically analysis of a problem. To minimize the waiting and servicing cost. When to buy, and how much to buy for the stock? Areas Under the OR vigilance, decision-makers study the problems and find its best solutions associated with the various areas and their subsets concerned to. For example, in agriculture as such production & distribution of crops, seed, power, fertilizer, and operating policies etc. In banking & finance such as financial policies, banking facilities to vary areas, investment portfolios, cash flow, economic developments of the nation, long term requirements, market risk etc. In defence selection of armaments (guns, missiles, rocketry, etc.), their procurement includes technical characteristics of newly advanced emerging technologies. In educational policies (infrastructural, educational, examination, staffing, human resource management etc.). In industry such as land, labour, capital, entrepreneur, forecasting, cost effectiveness, distribution pattern, sale, purchasing, and manufacturing etc. In marketing as market research, advertising & integrated brand promotion, marketing management, study of competitors, stock availability as per the demand for present and future. In personnel management as selection of suitable personnel, attractive emoluments, human resource management and welfare policies. 17 CU IDOL SELF LEARNING MATERIAL (SLM)
In production management as planning of hierarchy structure, distribution, manufacturing, location, maintenance, skilled workers, basic amenities at site. In purchasing, procurement as purchasing of raw material & machines, rules ofbuying and supplying, quotations strategy among the new sources, etc. In R&D, as selection of area for R&D, research designing, survey, questionnaires, know the limitations, cost. In transportation, (road, rail, air) as the amalgamation of technology for development, coordination of engineering departments, crews availability, analysis of freight structure, modern management techniques, traffic rules, yard operation etc. 1.3.3 Operational Research Operations Research is the study of how to make decisions efficiently. Mathematical Programming is one of the most powerful techniques used in Operations Research to the extent that sometimes both terms are used interchangeably. The programming in Mathematical Programming has nothing to do with computer programming; it means Optimization in British usage. Discrete optimization (or programming if you will) tackles problems where variables can only assume discrete values (for example, integer values). Figure 1.2: Operations research, mathematical programming, and discrete optimization Operations Research in Practice Every day, Operations Research practitioners solve real life problems that save people money and time. These problems are very diverse and almost always seem unrelated. However, their essence is always the same, making decisions to achieve a goal in the most efficient manner. The journey from learning about a client’s business problem to finding a solution can be challenging. In general, this journey can be dissected into the following four layers. 18 CU IDOL SELF LEARNING MATERIAL (SLM)
Figure 1.3: Four layers of abstractions to solve Operations Research problems Business Problems It is not exactly what it sounds like. Rather a better name for this tier would be real-world applications. The term business is meant to point out that the problem at hand is not yet a mathematical problem, but rather a more concrete, less formally stated, real life challenge. Business problems are best expressed in Natural Language (like English). They stem out of problems in industry and therefore are communicated to OR practitioners in layman terms. It is the responsibility of the OR practitioner, therefore, to formalize these problems and take it down to a lower level of abstraction. In practice, this is an iterative process. Examples of business problems can be found in different industries. Most of OR business problems you will hear about come from the logistics industry. Here are some examples: I am a hospital manager; how do I assign shifts to hospital staff? I am a trucking company manager; in what order should I schedule deliveries? I am starting a manufacturing company, where should I locate my factory? Generic Problems 19 CU IDOL SELF LEARNING MATERIAL (SLM)
When Operations Research was first invented, mathematicians recognized that most business problems they encountered could be mapped to a number of lower level generic families of problems. Hence, they dedicated a lot of their time and bandwidth to study these problems, gave them specific names, and proposed solutions for them. Most of the OR practitioners I know (and myself included) spend most of their time on the process of converting a business problem to one of these well-known generic problems. Once you get to that stage, solving the problem becomes standard procedure more or less. Generic Operations Research problems are concise enough to be described in mathematical notation. However, Operations Research practitioners usually express these problems using higher-level modelling languages. Here are some examples. The Travelling Salesman Problem (TSP) The Shortest Path Problem (SPP) The Set Covering Problem The Graph Colouring Problem As an example of the higher-level modelling language, scheduling problems are often described using terms like activities, resources and precedence constraints. Modelling Paradigms A modelling paradigm is a set of rules and practices that allows you to represent higher level problems using lower-level data structures such as matrices. When using a modelling paradigm, the OR practitioner expresses the problem using mathematical notation or an Algebraic Modelling Language (AML) that converts these mathematical notations to matrices to pass to the last level of abstraction, algorithms. The most famous modelling paradigm in Operations Research is Linear, Integer, and Mixed- Integer Programming. These are modelling paradigms that can express problems using linear equality constraints. It is a very powerful and natural way to represent optimization problems. Constraint Programming is another paradigm that has gained a lot of popularity lately, especially for scheduling applications. Network models are also a very well-known modelling paradigm based on graph theory. This paradigm is particularly useful to build good intuition of the problem and can represent a wide variety of discrete optimization problems in an efficient manner. Algorithms An algorithm is a procedure or a sequence of steps that if followed can solve a problem. Some algorithms are ubiquitous in all fields of Computer Science like searching and sorting, while others are geared towards more specific problems. 20 CU IDOL SELF LEARNING MATERIAL (SLM)
Search algorithms are very important in solving Operations Research problems. As their name implies, they are searching for a solution. In Operations Research, a family of algorithms known as “Branch and X” are used to solve Integer, Mixed-Integer and Constraint Programming problems. The most basic example is the Branch & Bound algorithm that solves integer programs. Others include Branch & Cut, Branch & Prune, and Branch & Price (aka Column Generation). Dynamic Programming algorithms are equally important in Operations Research. This family of algorithms solve problems by exploiting their optimal substructures. In simpler terms, if a problem can be solved using a bunch of identical tasks, we solve one of these tasks and store the result in a table. When we encounter the next instant of the same subproblem, we simply look up the answer instead of recomputing it. This can be very helpful in solving graph problems. The most famous example is the Bellman-Ford algorithm, named after the father of Dynamic Programming Richard Bellman. Sometimes, problems are too tough to solve optimally and we just need to find a quick solution. Greedy algorithms are used to accomplish this task. They do not usually guarantee optimality (but sometimes they do) but they can be very fast. The most famous example is Dijkstra’s algorithm for finding the shortest path problem. Dijkstra is guaranteed to find the shortest path if some assumptions are met. Figure 1.4: Search algorithms for solving operations research problems Stages of Development of Operations Research The stages of development of O.R. are also known as phases and processes of O.R, which has six important steps. These six steps are arranged in the following order: Step I: Observe the problem environment Step II: Analyse and define the problem Step III: Develop a model Step IV: Select appropriate data input Step V: Provide a solution and test its reasonableness 21 CU IDOL SELF LEARNING MATERIAL (SLM)
Step VI: Implement the solution 1.3.4 Optimization Finding the best possible solution to a question, given potential practical constraints. Optimization can be about maximization or Minimization of a cost or benefit that is decided on before starting. It is possible to have multiple goals, in which case we can define a combined cost function by applying weights of our different costs (for example taking the sum of two costs to minimize could be an example of a combined cost function). Second often-occurring things to deal with in those optimizations are constraints. Sometimes, an algorithm looking for minimization of a cost can go look for solutions in a way that is practically impossible. For example, when looking for the best staff planning, we want to constrain the algorithm to plan people for 24-hour-shifts because that would be simply illegal. Designing and controlling complex systems, solving hard problems of efficiently allocating scarce resources using incomplete information, and developing sustainable strategies to master situations of conflict and co-operation have always been necessary and challenging for individuals, organizations, and economies. Optimization and Operations Research are the disciplines that deal with such problems on a scientific basis; that is, they apply scientific methods and information technology to problem solving and provide the problem owner with quantitative approaches to informed and rational decision-making. Central to any quantitative decision analysis and decision-making are the foundation on mathematical models and the application of mathematical theories and methods. Here the mathematical model should abstract the crux of the decision-making problem. It should give a suitable and well-structured view of the underlying real problem, so that the conclusions obtained from analysing and manipulating the model are valid for the real problem. Optimization is that discipline within applied mathematics that deals with optimization models, their mathematical properties (optimization theory), and the development and implementation of algorithms (numerical analysis and algorithmic design). Specifying and formulating the problem, constructing a suitable mathematical model and deriving a solution from it, testing and modifying the model, and finally implementing the model solution in the real problem situation are the phases of the Operations Research approach. Thus, it is optimization that supports this process with a powerful tool-box. In an optimization problem or mathematical program we seek to minimize or maximize a (real valued) function over a set of (decision) variables subject to constraints. Example: Find integer values for the variables x, y, z and k with k > 2 such that x k + y k – z k is minimal. This is the well-known Fermat problem, which remained unsolved for about 350 years and was ultimately proved by Andrew Wiles in 1997. Thus Optimization is problem oriented, yet these problems are purely ideal and formal constructs. Carl Friedrich Gauss, the great German mathematician, claimed problems like the 22 CU IDOL SELF LEARNING MATERIAL (SLM)
Fermat problem were of no interest for him since the solution would yield no generalizable insight or knowledge. But research on this kind of seemingly purely formal and theoretical problems has been the engine for progress in mathematics leading to the development of many “applicable” theories and methodologies. Some examples of problem types which come from the meat of optimization/mathematical programming, and which from a certain point of view are more “interesting” and “practical” follow. 1.4 SUMMARY Operations Research is an approach to problems of how to coordinate and control the operations or activities \"within an organization. Following is an example which elaborates the nature of operations research. In order to run an organization effectively as a whole the problem that arises frequently is of coordination among the conflicting goals of its various functional departments. For example, consider the problem of stocks of finished goods. The various departments of the organization may like to handle this problem differently. To the marketing department, stock of a large variety of products is a means of supplying the company's customers with what they want, and where they want it. Clearly, the fully stocked ware-house is of prime importance to the company. The production department argues for long production runs preferably on a smaller product range, particularly if there is a significant time loss when production is switched from one variety to another. On the other hand, the finance department sees stocks kept as capital tied up unproductively and argues strongly for their reduction. Finally the personnel department sees great advantage in labour relations if there is a steady level of production leading to steady employment. To optimize the whole system, the decision maker must decide the best policy keeping inview the relative importance of objectives and validity of conflicting claims of various departments from the perspective of the whole organization. Operations research thus helps to seek the optimal solution to a problem and not merely one which gives better solutions than the one currently in use. The decision taken by the decision maker may not be acceptable to every department but it should be optimal for the organization as a whole or at least for a large portion of the total organization. In order to obtain such types of solution, the decision maker must follow the effects and interactions of a particular decision. Operations Research increases the effectiveness of management decisions. Management is most of the time making decisions. It is thus a decision science which 23 CU IDOL SELF LEARNING MATERIAL (SLM)
helps management to make better decisions. So, the major premise of OR is the decision-making, irrespective of the situation involved. Therefore, decision making is a systematic process and consists of the following steps. a. Diagnose the problem, and establish the criterion. The criterion may be the maximization of profits, utility and minimization of cost etc. b. Select the alternative course of action for consideration. c. Determine the model to be used and values of the parameters. d. Evaluation of various alternatives. e. Selecting the best and the optimum alternative. 1.5 KEYWORDS Operations Research- Operations research (O.R.) is defined as the scientific process of transforming data into insights to making better decisions. For instance, each car has a distance from potential customers. Drivers can drive only for so many hours a day. Each road has a speed limit and each car has a maximum number of passengers it can take. This is the most common example of Operations Research. Optimisation- Optimization methods are used in many areas of study to find solutions that maximize or minimize some study parameters, such as minimize costs in the production of a good or service, maximize profits, minimize raw material in the development of a good, or maximize production. Linear Programming- Linear programming is a mathematical technique that determines the best way to use available resources. Managers use the process to help make decisions about the most efficient use of limited resources – like money, time, materials, and machinery. Integer Programming- Integer programming expresses the optimization of a linear function subject to a set of linear constraints over integer variables. Integer programming is the class of problems that can be expressed as the optimization of a linear function subject to a set of linear constraints over integer variables. Dynamic Programming-Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub problems. 1.6 LEARNING ACTIVITY 1. Operations research contains key design tools for students. And they often have a difficult time learning the basic concepts. Hence assign the students certain games that are very familiar. Tell the students to visualise problems, break problems down 24 CU IDOL SELF LEARNING MATERIAL (SLM)
into manageable sub-sections. Then inform them to develop solution strategies, and seek known and well established goals. ___________________________________________________________________________ ___________________________________________________________________________ 2. In this activity, assign the task of a transport operator like Ola or Uber. Suppose a person wants to travel from Kurla to Bandra. Then the students have to develop; i. A master routing plan ii. Which driver should be sent where and when? iii. What is the charge for transportation? The purpose of this learning activity is to make the possible decision by using the available resources optimally. ___________________________________________________________________________ ___________________________________________________________________________ 1.7 UNIT END QUESTIONS A. Descriptive Question Short Questions 1. Define operations research. 2. What is the purpose of optimization? 3. What is the significance of operations research for an organisation? 4. What are the operations research applications in accounting? 5. Give a brief in operations research in practice. Long Questions 1. What does the basic concept of operations research convey? 2. Explain how operations research is helpful in making decisions on the part of managers. 3. What complex problems get solved through the tools of operations research? 4. What are the areas in which operations research is in use in general? 5. How important is dynamic programming in operations research? B Multiple Choice Questions 1. Which is not a step of operations research? 25 CU IDOL SELF LEARNING MATERIAL (SLM)
a. Identifying a problem that needs to be solved b. Constructing a model around the problem that resembles the real world and variables c. Using the model to derive no solutions to the problem d. Testing each solution on the model and analysing its success 2. Which are primary characteristics of all operations research efforts? 26 a. Optimisation b. Simulation c. Probability d. All of these 3. When did India establish its first operations research unit? a. 1939 b. 1949 c. 1959 d. 1969 4. Which doesn’t belong to linear optimisation? a. Linear programming b. Integer programming c. Classic model d. Network models 5. Which among the following is not ensured through model validation? a. Input data is free from errors b. Compute program is bug free c. Computer program correctly represents the model d. Results from the algorithm seem unreasonable Answers 1-c 2-d 3-b 4-c 5-d 1.8 REFERENCES References CU IDOL SELF LEARNING MATERIAL (SLM)
What is OR – IFORS, Operations Research, Operational Research, Management Science Mohamed Leila The big picture of Operations Research Towards Data Science Operations Research: Concept, stages involved, scope of OR (thefactfactor.com) JMESTN42351698.pdf (PDF) Operations Research in Decision Making (researchgate.net) Textbooks Irfan Ali, Leopoldo Eduardo Cárdenas-Barron, Aquil Ahmed, Shaikh Optimal Decision Making in Operations Research and Statistics Methodologies and Applications Edited B., L. Rigby, S. Lasdon and A. D. Waren, \"The Evolution of Texaco's Blending Systems: From OMEGA to Star Blend” Ulrich Derigs OPTIMIZATION AND OPERATIONS RESEARCH – Vol. I - Optimization and Operations Research Websites What is Operations Research and Why is it Important? (techtarget.com) Basic OR concepts (brunel.ac.uk) Importance of Operation Research in Decision Making - (mitsde.com) 27 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 2 - LINEAR PROGRAMMING STRUCTURE 2.0 Learning Objectives 2.1 Introduction 2.2 Meaning 2.3 Scope 2.3.1 Maximization Models 2.3.2 Minimization Models 2.4 Assumptions 2.5 Summary 2.6 Keywords 2.7 Learning Activity 2.8 Unit End Questions 2.9 References 2.0 LEARNING OBJECTIVES After studying this unit, you will be able to: Get more insights on linear programming. Gain knowledge on maximisation and minimisation models. Assume the applications of linear programming in various fields. 2.1 INTRODUCTION We all come across many target based situations in day to day life. Can you think of any? Say a student has to complete a project in 15 days or a salesperson has to achieve a sales target within a month while another person has to buy an electronic gadget within a budget of ₹500 rupees, go through these situations and try to find out the main objective to achieve by each person individually. Let's say what is the objective of the student in this case, yes she wants to achieve the maximum score in this project, can you tell me the objective of the salesperson in this case? Yes, he would aim to achieve maximum possible sales in a month. What you think would be the objective of a person buying a gadget, she would try to minimize the cost as much as possible, she buys a gadget that Falls within a budget we can see that is each of 28 CU IDOL SELF LEARNING MATERIAL (SLM)
these cases above the objective of each of the situation was to maximize the benefits or minimize the cost such types of problem are college Optimisation problems. In mathematics does an Optimisation problem may involve finding maximum profit, minimum cost, or maybe minimum use of resources there can be many more examples in our day to day life that need to be solved using the Optimisation techniques, the problems can be as simple as stated above but could get complicated depending on the situation, we have already discussed the objective of the three given situation now we can look at the important factors we will identify the limiting factor in each case. What does that mean? well in each case there is a scarcity of some resources like is the first case, the time limit to complete the project is limited time to be allotted for completing the project is limited to 15 days only likewise in case two the time in the limiting factor the person has to sell the maximum possible product in a period of one month what can you say about the third situation what the limiting factor in this case the person has to buy the gadget within a predetermined budget that means amount to spend your money is the limiting factor in this case this limiting factor that is the scarcity of resources acts as constraints in finding the best solutions of the given problems, But how are these Optimisation problems solving in mathematics. They’re all different problem solving techniques to solve such problems. The main technique we will discuss is linear programming. Linear programming is not a programming language like C++, Java, or Visual Basic. Linear programming can be defined as: “A mathematical method to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed using a linear objective function and linear inequality constraints.” A linear program consists of a set of variables, a linear objective function indicating the contribution of each variable to the desired outcome, and a set of linear constraints describing the limits on the values of the variables. The “answer” to a linear program is a set of values for the problem variables that results in the best — largest or smallest — value of the objective function and yet is consistent with all the constraints. Formulation is the process of translating a real-world problem into a linear program. Once a problem has been formulated as a linear program, a computer program can be used to solve the problem. In this regard, solving a linear program is relatively easy. The hardest part about applying linear programming is formulating the problem and interpreting the solution. 2.2 MEANING Linear programming (LP) or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimisation problems involve the calculation of profit and loss. Linear programming problems are an important class of 29 CU IDOL SELF LEARNING MATERIAL (SLM)
optimisation problems that helps to find the feasible region and optimise the solution in order to have the highest or lowest value of the function. Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions. Some of the assumptions taken while working with linear programming are: The number of constraints should be expressed in the quantitative terms The relationship between the constraints and the objective function should be linear The linear function (i.e., objective function) is to be optimised Components of Linear Programming The basic components of the LP are as follows: Decision Variables Constraints Data Objective Functions Characteristics of Linear Programming The following are the characteristics of the linear programming problem: 1. Constraints – The limitations should be expressed in the mathematical form, regarding the resource. 2. Objective Function – In a problem, the objective function should be specified in a quantitative way. 3. Linearity – The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one. 4. Finiteness – There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible. 5. Non-negativity – The variable value should be positive or zero. It should not be a negative value. 6. Decision Variables – The decision variable will decide the output. It gives the ultimate solution to the problem. For any problem, the first step is to identify the decision variables. Linear Programming Problems The Linear Programming Problems (LPP) is a problem that is concerned with finding the optimal value of the given linear function. The optimal value can be either maximum value or 30 CU IDOL SELF LEARNING MATERIAL (SLM)
minimum value. Here, the given linear function is considered an objective function. The objective function can contain several variables, which are subjected to the conditions and it has to satisfy the set of linear inequalities called linear constraints. In Linear programming, the term “linear” represents the mathematical relationship that is used in the given problem (Generally, linear relationship) and the term “programming” represents the method of determining the particular plan of action. The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on. Methods to Solve Linear Programming Problems The linear programming problem can be solved using different methods, such as the graphical method, simplex method, or by using tools such as R, open solver etc. Here, we will discuss the two most important techniques called the simplex method and graphical method in detail. Linear Programming Simplex Method The simplex method is one of the most popular methods to solve linear programming problems. It is an iterative process to get the feasible optimal solution. In this method, the value of the basic variable keeps transforming to obtain the maximum value for the objective function. The algorithm for linear programming simplex method is provided below: Step 1: Establish a given problem. (i.e.,) write the inequality constraints and objective function. Step 2: Convert the given inequalities to equations by adding the slack variable to each inequality expression. Step 3: Create the initial simplex tableau. Write the objective function at the bottom row. Here, each inequality constraint appears in its own row. Now, we can represent the problem in the form of an augmented matrix, which is called the initial simplex tableau. Step 4: Identify the greatest negative entry in the bottom row, which helps to identify the pivot column. The greatest negative entry in the bottom row defines the largest coefficient in the objective function, which will help us to increase the value of the objective function as fastest as possible. Step 5: Compute the quotients. To calculate the quotient, we need to divide the entries in the far right column by the entries in the first column, excluding the bottom row. The smallest quotient identifies the row. The row identified in this step and the element identified in the step will be taken as the pivot element. Step 6: Carry out pivoting to make all other entries in the column zero. 31 CU IDOL SELF LEARNING MATERIAL (SLM)
Step 7: If there are no negative entries in the bottom row, end the process. Otherwise, start from step 4. Step 8: Finally, determine the solution associated with the final simplex tableau. Graphical Method The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane. Once all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explain what all values our model can take. Let us see an example here and understand the concept of linear programming in a better way. Example 1 Calculate the maximal and minimal value of z = 5x + 3y for the following constraints. x + 2y ≤ 14 3x – y ≥ 0 x–y≤2 Solution The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region. The optimisation equation (z) = 5x + 3y. You have to find the (x, y) corner points that give the largest and smallest values of z. To begin with, first solve each inequality. x + 2y ≤ 14 ⇒ y ≤ -(1/2) x + 7 3x – y ≥ 0 ⇒ y ≤ 3x x–y≤2⇒y≥x–2 32 CU IDOL SELF LEARNING MATERIAL (SLM)
Figure 2.1: Graph for the Example 1 equations. Now pair the lines to form a system of linear equations to find the corner points. y = -(½) x + 7 y = 3x Solving the above equations, we get the corner points as (2, 6) y = -1/2 x + 7 y=x–2 Solving the above equations, we get the corner points as (6, 4) y = 3x y=x–2 Solving the above equations, we get the corner points as (-1, -3) For linear systems, the maximum and minimum values of the optimisation equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y (2, 6): z = 5(2) + 3(6) = 10 + 18 = 28 (6, 4): z = 5(6) + 3(4) = 30 + 12 = 42 33 CU IDOL SELF LEARNING MATERIAL (SLM)
(–1, –3): z = 5(-1) + 3(-3) = -5 -9 = -14 Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3) 2.3 SCOPE Linear Programming Applications A real-time example would be considering the limitations of labours and materials and finding the best production levels for maximum profit in particular circumstances. It is part of a vital area of mathematics known as optimisation techniques. The applications of LP in some other fields are Engineering – It solves design and manufacturing problems as it is helpful for doing shape optimisation Efficient Manufacturing – To maximise profit, companies use linear expressions Energy Industry – It provides methods to optimise the electric power system. Transportation Optimisation – For cost and time efficiency. Importance of Linear Programming Linear programming is broadly applied in the field of optimisation for many reasons. Many functional problems in operations analysis can be represented as linear programming problems. Some special problems of linear programming are such as network flow queries and multi-commodity flow queries are deemed to be important to have produced much research on functional algorithms for their solution. Managerial Uses and Applications LP technique is applied to a wide variety of problems listed below: Optimizing the product mix when the production line works under certain specification; Securing least cost combination of inputs; Selecting the location of Plant; Deciding the transportation route; Utilizing the storage and distribution centres; Proper production scheduling and inventory control; Solving the blending problems; Minimizing the raw materials waste; 34 CU IDOL SELF LEARNING MATERIAL (SLM)
Assigning jobs to specialized personnel. The fundamental characteristic in all such cases is to find the optimum combination of factors after evaluating known constraints. LP provides solutions to business managers by understanding the complex problems in a clear and sound way. The basic problem before any manager is to decide the manner in which limited resources can be used for profit maximization and cost minimization. This needs the best allocation of limited resources—for this purpose linear programming can be used advantageously. 2.3.1 Maximization Models Application problems in business, economics, and social and life sciences often ask us to make decisions on the basis of certain conditions. The conditions or constraints often take the form of inequalities. In this section, we will begin to formulate, analyse, and solve such problems, at a simple level, to understand the many components of such a problem. A typical linear programming problem consists of finding an extreme value of a linear function subject to certain constraints. We are either trying to maximize or minimize the value of this linear function, such as to maximize profit or revenue, or to minimize cost. That is why these linear programming problems are classified as maximization or minimization problems, or just optimization problems. The function we are trying to optimize is called an objective function, and the conditions that must be satisfied are called constraints. A typical example is to maximize profit from producing several products, subject to limitations on materials or resources needed for producing these items; the problem requires us to determine the amount of each item produced. Another type of problem involves scheduling; we need to determine how much time to devote to each of several activities in order to maximize income from (or minimize cost of) these activities, subject to limitations on time and other resources available for each activity. Let’s solve the maximization problem through an example. Example: Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours preparing. If Nikki makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income? Solution We start by choosing our variables. Let x = The number of hours per week Niki will work at Job I. Let y = The number of hours per week Niki will work at Job II. 35 CU IDOL SELF LEARNING MATERIAL (SLM)
Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation. I=40x+30y Our next task is to find the constraints. The second sentence in the problem states, \"She never wants to work more than a total of 12 hours a week.\" This translates into the following constraint: x+y≤12 The third sentence states, \"For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation.\" The translation follows. 2x+y≤16 The fact that x and y can never be negative is represented by the following two constraints: x≥0, and y≥0. Well, good news! We have formulated the problem. We restate it as: Maximize I=40x+30y Subject to: x+y≤12 2x+y≤16 X≥0; y≥0 In order to solve the problem, we graph the constraints and shade the region that satisfies all the inequality constraints. Any appropriate method can be used to graph the lines for the constraints. However often the easiest method is to graph the line by plotting the x-intercept and y-intercept. The line for a constraint will divide the plane into two regions, one of which satisfies the inequality part of the constraint. A test point is used to determine which portion of the plane to shade to satisfy the inequality. Any point on the plane that is not on the line can be used as a test point. If the test point satisfies the inequality, then the region of the plane that satisfies the inequality is the region that contains the test point. If the test point does not satisfy the inequality, then the region that satisfies the inequality lies on the opposite side of the line from the test point. In the graph below, after the lines representing the constraints were graphed using an appropriate method, the point (0,0) was used as a test point to determine that (0,0) satisfies the constraint x+y≤12 because 0+0<12 (0, 0) satisfies the constraint 2x+y≤16 because 2(0)+0<16 36 CU IDOL SELF LEARNING MATERIAL (SLM)
Therefore, in this example, we shade the region that is below and to the left of both constraint lines, but also above the x axis and to the right of the y axis, in order to further satisfy the constraints x≥0 and y≥0. Figure 2.2: Feasibility region The shaded region where all conditions are satisfied is called the feasibility region or the feasibility polygon. The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasibility region. Therefore, we will identify all the vertices (corner points) of the feasibility region. We call these points’ critical points. They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute these points in the objective function to see which point gives us the highest income per week. We list the results below. Critical Points Income (0, 0) 40(0) + 30(0) = $0 (0, 12) 40(0) + 30(12) = $360 (4, 8) 40(4) + 30(8) = $400 37 CU IDOL SELF LEARNING MATERIAL (SLM)
(8, 0) 40(8) + 30(0) = $320 Table 2.1: Substitution of the points in the objective function Clearly the point (4, 8) gives the most profit: $400. Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II. 2.3.2 Minimization Models Minimization linear programming problems are solved in much the same way as the maximization problems. For the standard minimization linear program, the constraints are of the form ax+by≥c, as opposed to the form ax+by≤c for the standard maximization problem. As a result, the feasible solution extends indefinitely to the upper right of the first quadrant, and is unbounded. But that is not a concern, since in order to minimize the objective function, the line associated with the objective function is moved towards the origin, and the critical point that minimizes the function is closest to the origin. However, one should be aware that in the case of an unbounded feasibility region, the possibility of no optimal solution exists. Let’s understand it through an example. Example: At a university, Professor Symons wishes to employ two people, John and Mary, to grade papers for his classes. John is a graduate student and can grade 20 papers per hour; John earns $15 per hour for grading papers. Mary is a post-doctoral associate and can grade 30 papers per hour; Mary earns $25 per hour for grading papers. Each must be employed at least one hour a week to justify their employment. If Prof. Symons has at least 110 papers to be graded each week, how many hours per week should he employ each person to minimize the cost? Solution We choose the variables as follows: Let x = the number of hours per week John is employed. And y = the number of hours per week Mary is employed. The objective function is C=15x+25y The fact that each must work at least one hour each week results in the following two constraints: x≥1 y≥1 38 CU IDOL SELF LEARNING MATERIAL (SLM)
Since John can grade 20 papers per hour and Mary 30 papers per hour, and there are at least 110 papers to be graded per week, we get 20x+30y≥110 The fact that x and y are non-negative, we get x≥0, and y≥0. The problem has been formulated as follows. Minimize C=15x+25y Subject to: x≥1 Y≥1 20x+30y≥110 x≥0; y≥0 To solve the problem, we graph the constraints as follows: Figure 2.3: Graphing the constraints Again, we have shaded the feasibility region, where all constraints are satisfied. If we use a test point (0,0) that does not lie on any of the constraints, we observe that (0, 0) does not satisfy any of the constraints x≥1, y≥1, 20x+30y≥110. Thus, all the shading for the feasibility region lies on the opposite side of the constraint lines from the point (0,0). Alternatively, we could use test point (4,6), which also does not lie on any of the constraint lines. We’d find that (4,6) does satisfy all of the inequality constraints. Consequently, all the shading for the feasibility region lies on the same side of the constraint lines as the point (4,6). 39 CU IDOL SELF LEARNING MATERIAL (SLM)
Since the extreme value of the objective function always takes place at the vertices of the feasibility region, we identify the two critical points, (1, 3) and (4, 1). To minimize cost, we will substitute these points in the objective function to see which point gives us the minimum cost each week. The results are listed below. Critical points Income (1, 3) 15(1) + 25(3) = $90 (4, 1) 15(4) + 25(1) = $85 The point (4, 1) gives the least cost, and that cost is $85. Therefore, we conclude that in order to minimize grading costs, Professor Symons should employ John 4 hours a week, and Mary 1 hour a week at a cost of $85 per week. 2.4 ASSUMPTIONS Linear programs are constrained optimisation models that satisfy three requirements. 1. The decision variables must be continuous; they can take on any value within some restricted range. 2. The objective function must be a linear function. 3. The left-hand sides of the constraints must be linear functions. Most linear programs require that all decision variables be nonnegative. Several assumptions are implicit in linear programming problems. These assumptions are: Proportionality- The contribution of any variable to the objective function or constraints is proportional to that variable. This implies no dis5 counts or economies to scale. For example, the value of 8x1 is twice the value of 4x1, no more or less. Additivity- The contribution of any variable to the objective function or constraints is independent of the values of the other variables. Divisibility- Decision variables can be fractions. However, by using a special technique called integer programming, we can bypass this condition. Unfortunately, integer programming is beyond the scope of this paper. Certainty- This assumption is also called the deterministic assumption. This means that all parameters (all coefficients in the objective function and the constraints) are known with certainty. Realistically, however, coefficients and parameters are often the result of guess-work and approximation. The effect of changing these numbers can be determined with sensitivity analysis. 40 CU IDOL SELF LEARNING MATERIAL (SLM)
2.5 SUMMARY Linear Programming Problems (LPP) is a system process of finding a maximum or minimum value of any variable in a function, it is also known by the name of optimization problem. LPP is helpful in developing and solving a decision making problem by mathematical techniques. The problem is generally given in a linear function which needs to be optimized subject to a set of different constraints. Major usage of LPP is in advising the management to make the most efficient & effective use of the scarce resources. It has different parts like: i. Decision Variable: Variables which are changeable & going to impact the decision function. Like the profit function is affected by both sales and price, now which one of these two is changeable, will be our decision variable. ii. Objective Function: Linear function of the objective, either to Maximize or minimize, like Maximize Profit, sales, production etc. and Minimize Cost, Loss, energy, consumption, wastage etc. iii. Constraints: Any kind of limitation or scarcity explained through a function like Limitations of raw materials, time, funds, equipment's etc. Non-Negative Constraints will also be there which will remain non-negative all the time. Characteristics of Linear Problem i. The objective is function is mimization type ii. All constraints are equality type iii. All the decision variables are non-negative Standard form of Linear Program (LP) Minimize f (x1, x2, x3…….xn) = c1x1+c2x2+c3x3+.....+cnxn Overall, Linear Programming is used to successfully model numerous real world situations, ranging from scheduling airline routes to shipping oil from refineries to cities to finding inexpensive diets capable of meeting the minimum daily requirements. 2.6 KEYWORDS Linear Optimisation- Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. 41 CU IDOL SELF LEARNING MATERIAL (SLM)
Decision Variable- A decision variable is unknown in an optimization problem. It has a domain, which is a compact representation of the set of all possible values for the variable. Decision variable types are references to objects whose exact nature depends on the underlying optimizer of a model. Constraints- The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions. Proportionality- A change in a variable results in a proportionate change in that variable's contribution to the value of the function. Objective Function- The objective function in linear programming problems is the real-valued function whose value is to be either minimized or maximized subject to the constraints defined on the given LPP over the set of feasible solutions. The objective function of a LPP is a linear function of the form z = ax + by. 2.7 LEARNING ACTIVITY 1. Let us look at this diet problem. A housewife wishes to mix two types of food F1 and F2 in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food F1 costs E60/Kg and Food F2 costs E80/kg. Food F1 contains 3 units/kg of vitamin A and 5 units/kg of vitamin B while Food F2 contains 4 units/kg of vitamin A and 2 units/kg of vitamin B. Formulate this problem as a linear programming problem to minimize the cost of the mixtures. ___________________________________________________________________________ ___________________________________________________________________________ 2. A furniture company produces inexpensive tables and chairs. The production process for each is similar in that both require a certain number of hours of carpentry work and a certain number of labour hours in the painting department. Each table takes 4 hours of carpentry and 2 hours in the painting department. Each chair requires 3 hours of carpentry and 1 hour in the painting department. During the current production period, 240 hours of carpentry time are available and 100 hours in painting is available. Each table sold yields a profit of E7; each chair produced is sold for a E5 profit. Find the best combination of tables and chairs to manufacture in order to reach the maximum profit. ___________________________________________________________________________ ___________________________________________________________________________ 2.8 UNIT END QUESTIONS 42 CU IDOL SELF LEARNING MATERIAL (SLM)
A. Descriptive Questions Short Questions 1. What are the components of linear programming? 2. What are few assumptions of linear programming? 3. Explain linear programming problems. 4. When is the graphical method used? 5. What are the fields that use linear programming applications? Long Questions 1. How does a maximisation model help in maximising profit? 2. What is a standard minimisation linear program? 3. How can managers use linear programming to the advantage of their organisations? 4. What are the steps involved in linear programming simplex method? 5. What are the characteristics of linear programming? B. Multiple Choice Questions 1. Which is not a characteristic of linear programming? a. Constraints b. Subjective function c. Linearity d. Finiteness 2. Which is not a component of linear programming? a. Restraints b. Decision variables c. Data d. Objective functions 3. Which assumptions are taken into consideration in linear programming? a. The number of constraints should be expressed in the quantitative terms b. The relationship between the constraints and the objective function should be linear c. The linear function (i.e., objective function) is to be optimised d. All of these 43 CU IDOL SELF LEARNING MATERIAL (SLM)
4. Which is not a step involving linear programming simplex method? a. Establish a given problem b. Convert the given inequalities to equations c. Create the initial simplex tableau d. Identify the smallest negative entry in the bottom row 5. When is the right condition to use a graphical method? a. If the problem has two decision variables b. If the problem has one decision variable c. If the problem has three decision variables d. None of these Answers 1-b 2-a 3-d 4-d 5-a 2.9 REFERENCES References Maximization Applications - Mathematics Libre Texts LP.pdf (uky.edu) SUPPLEMENT B: Introduction to Optimization - Operations Management: An Integrated Approach, 5th Edition [Book] (oreilly.com) Textbooks Maximization Applications - Mathematics Libre Texts John J. Jarvis Mokhtar S. Bazaraa and Hanif D. Sherali. Linear Programming and Network Flows. John Wiley & Sons, second edition, 1990. Wayne L. Winston. Operations Research: Applications and Algorithms. Duxbury Press, fourth edition, 2003. Websites Linear Programming (Definition, Components, Methods) | Linear Programming Problems. (byjus.com) D:\\Classes\\For466W\\TextBook\\Master.PDF (washington.edu) Linear Programming –GeeksforGeeks LPP-Business-Mathematics-1.pdf (arsdcollege.ac.in) 44 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 3 - FORMULATION OF LINEAR PROGRAMMING STRUCTURE 3.0 Learning Objectives 3.1 Introduction 3.2 Formulation of Linear Programming Problem 3.2.1 Types of Constraints 3.3 Graphical Method 3.3.1 Graphical Analysis of Linear Programming 3.3.2 Graphical Linear Programming Solution 3.4 Simplex Methods 3.4.1 Two Phase Method 3.4.2 M Method 3.4.3 Solutions 3.5 Summary 3.6 Keywords 3.7 Learning Activity 3.8 Unit End Questions 3.9 References 3.0 LEARNING OBJECTIVES After studying this unit, you will be able to: Explain the ways to formulate linear programming problem. Describe how to use graphical method in linear programming. Elucidate simplex methods and their applications. 3.1 INTRODUCTION Linear Programming is a problem solving approach that has been developed to help managers to make decisions. Linear Programming is a mathematical technique for determining the 45 CU IDOL SELF LEARNING MATERIAL (SLM)
optimum allocation of resources and obtaining a particular objective when there are alternative uses of the resources, money, manpower, material, machine and other facilities. Linear programming is viewed as a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity. In the real world, planning tends to be ad hoc because of the many special-interest groups with their multiple objectives. The LPP technique was first introduced in 1930 by Russian mathematician Leonid Kantorovich in the field of manufacturing schedules and by American economist Wassily Leontief in the field of economics. After a decade during World War II, these techniques were heavily adopted to solve problems related to transportation, scheduling, allocation of resources, etc. In 1950, the first simplex method algorithm for LPP was created by American mathematician George Dantzig. Elements of a basic LPP Decision Variables: These are the unknown quantities that are expected to be estimated as an output of the LPP solution. Objective Function: All linear programming problems aim to either maximize or minimize some numerical value representing profit, cost, production quantity, etc. It evaluates the amount by which each decision variable would contribute to the net present value of a project or an activity. Objective Function coefficient: The amount by which the objective function value would change when one unit of a decision variable is altered, is given by the corresponding objective function coefficient. Constraints: The restrictions or limitations on the total amount of a particular resource required to carry out the activities that would decide the level of achievement in the decision variables. In the standard form of a linear programming problem, all constraints are in the form of equations. Non-negative constraints: Each decision variable in any Linear Programming model must be positive irrespective of whether the objective function is to maximize or minimize the net present value of an activity. This is a critical restriction. Besides, there are two other elements such as resource availability and technological coefficients. The Nature of Linear Programming Problem Two of the most common are: 1. The product-mix problem 2. The blending Problem 46 CU IDOL SELF LEARNING MATERIAL (SLM)
In the product- mix problem there are two or more products also called candidates or activities competing for limited resources. The problem is to find out which products to include in the production plan and in what quantities these should be produced or sold in order to maximize profit, market share or sales revenue. The blending problem involves the determination of the best blend of available ingredients to form a certain quantity of a product under strict specifications. The best blend means the least cost blend of the required inputs. 3.2 FORMULATION OF LINEAR PROGRAMMING PROBLEM Three components are: 1. The decision variable 2. The environment (uncontrollable) parameters 3. The result (dependent) variable Figure 3.1 Linear Programming Model is composed of the same components The Mathematical Expression of the LP Model The general LP Model can be expressed in mathematical terms as shown below: Let Oij = Input-Output Coefficient Cj = Cost (Profit) Coefficient bi = Capacities (Right Hand Side) Xj = Decision Variables Find a vector (x1, x2, x3 ..........xn) that minimise or maximise a linear objective function F(x) where F(x) = c1x1 + c2x2 + ................+ cnxn subject to linear constraints a1x1 + a2x2 + ................+ anxn = b2 a1x1 + a2x2 + ................+ anxn ≤ b2 am1x1 + am2x2 + ................+ amnxn ≤ b2 47 CU IDOL SELF LEARNING MATERIAL (SLM)
and non-negativity constraints x1 ≥ 0, x2 ≥ 0, .................., xn ≥ 0 Formulation of LPP Steps 1. Identify decision variables 2. Write objective function 3. Formulate constraints A firm produces three products. These products are processed on three different machines. The time required to manufacture one unit of each of the three products and the daily capacity of the three machines are given in the table below: Table 3.1Time per unit and machine capacity It is required to determine the daily number of units to be manufactured for each product. The profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6 respectively. It is assumed that all the amounts produced are consumed in the market. Formulate the mathematical (L.P.) model that will maximise the daily profit. Formulation of Linear Programming Model Step 1 From the study of the situation find the key-decision to be made. In the given situation the key decision is to decide the extent of products 1, 2 and 3, as the extents are permitted to vary. Step 2 Assume symbols for variable quantities noticed in step 1. Let the extents (amounts) of products 1, 2 and 3 manufactured daily be x1, x2 and x3 units respectively. Step 3 Express the feasible alternatives mathematically in terms of variables. Feasible alternatives are those which are physically, economically and financially possible. In the given situation feasible alternatives are sets of values of x1, x2 and x3 units respectively. Where x1, x2 and x3 ≥ 0. Since negative production has no meaning and is not feasible. Step 4 Mention the objective function quantitatively and express it as a linear function of variables. In the present situation, the objective is to maximize the profit. i.e., Z = 4x1+ 3x2 + 6x3 Step 5 Put into words the influencing factors or constraints. These occur generally because of constraints on availability (resources) or requirements (demands). Express these constraints 48 CU IDOL SELF LEARNING MATERIAL (SLM)
also as linear equations/inequalities in terms of variables. Here, constraints are on the machine capacities and can be mathematically expressed as: 2x1+ 3x2 + 2x3 ≤ 440 4x1+ 0x2 + 3x3 ≤ 470 2x1+ 5x2 + 0x3 ≤ 430 Example 2: Product Mix Problem A factory manufactures two products A and B. To manufacture one unit of A, 1.5 machine hours and 2.5 labour hours are required. To manufacture product B, 2.5 machine hours and 1.5 labour hours are required. In a month, 300 machine hours and 240 labour hours are available. Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulated as LPP. Solution: Table 3.2 Products and resource/unit There will be two constraints. One for machine hour’s availability and for labour hours availability. Decision Variables X1 = Number of units of A manufactured per month. X2 = Number of units of B manufactured per month. The objective function: Max Z = 50x1+ 40x2 Subjective Constraints For machine hours 1.5x1+ 2.5x2 ≤ 300 For labour hours 2.5x1+ 1.5x2 ≤ 240 Non negativity x1, x2 ≥0 Example: 3 A company produces three products A, B, C. For manufacturing three raw materials P, Q and R are used. Profit per unit A - Rs. 5, B - Rs. 3, C - Rs. 4 49 CU IDOL SELF LEARNING MATERIAL (SLM)
Table 3.3: Resource requirements/unit Maximum raw material availability: P - 80 units; Q - 100 units; R - 150 units. Formulate LPP. Solution Decision variables: x1 = Number of units of A x2 = Number of units of B x3 = Number of units of C Objective Function Since Profit per unit is given, objective function is maximisation Max Z = 5x1+ 3x2 + 4x3 Constraints For P: 0x1+ 20x2 + 30x3 ≤ 80 For Q: 20x1+ 30x2 + 20x3 ≤ 100 For R: 50x1+ 0x2 + 40x3 ≤ 150 (For B, R is not required) X1, X2, X3 ≥ 0 Example 4: Portfolio Selection (Investment Decisions) An investor is considering investing in two securities 'A' and 'B'. The risk and return associated with these securities is different. Security 'A' gives a return of 9% and has a risk factor of 5 on a scale of zero to 10. Security 'B' gives a return of 15% but has a risk factor of 8. Total amount to be invested is Rs. 5, 00, 000/- Total minimum returns on the investment should be 12%. Maximum combined risk should not be more than 6. Formulated as LPP. Solution Decision Variables X1 = Amount invested in Security A 50 CU IDOL SELF LEARNING MATERIAL (SLM)
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
