Operations Research PDF

INTRODUCTION TO OPERATIONS RESEARCH 1.0 Introduction The British/Europeans refer to it as "operational research," the Americans to "operations research" - but both are often shortened to just "OR" - which is the term we will use. Another term that is used for this field is "management science"...

INTRODUCTION TO OPERATIONS RESEARCH 1.0 Introduction The British/Europeans refer to it as "operational research," the Americans to "operations research" - but both are often shortened to just "OR" - which is the term we will use. Another term that is used for this field is "management science" ("MS"). The Americans sometimes combine the terms OR and MS together and say "OR/MS" or "ORMS." Yet other terms sometimes used are "industrial engineering" ("IE") and "decision science" ("DS"). In recent years there has been a move towards a standardization upon a single term for the field, namely the term "OR." Operation Research is a relatively new discipline. The contents and the boundaries of the OR are not yet fixed. Therefore, giving a formal definition of the term Operations Research is a difficult task. The OR starts when mathematical and quantitative techniques are used to substantiate the decision being taken. In our daily life, we make decisions even without noticing them. The decisions are taken simply by common sense, judgment, and expertise without using any mathematical or any other model in simple situations. But the decisions we are concerned with here are complex and heavily responsible. Examples are public transportation network planning in a city with its own layout of factories, residential blocks, or finding the appropriate product mix when there are many products with different profit contributions and production requirements, etc. Operations Research tools are not from any one discipline. Operations Research takes tools from different disciplines such as mathematics, statistics, economics, psychology, engineering, etc., and combines them to make a new set of knowledge for decision-making. Today, OR became a professional discipline that deals with applying scientific methods for making the decision, especially to the allocation of scarce resources. The main purpose of OR is to provide a rational basis for decisions making in the absence of complete information because the systems composed of humans, machines, and procedures may not have complete information. Operations Research can also be treated as science in a sense it describing, understanding, and predicting the behaviour of the system, especially the man-machine system. Thus OR specialists are involved in three classical aspects of science as follows: i) Determining the system's behaviour ii) Analyzing the behaviour of the system by developing appropriate models 1  iii) Predict the future behaviour using these models The emphasis on analysis of operations as a whole distinguishes the OR from other research and engineering. OR is an interdisciplinary area that provided solutions to military operations problems during World War II and successful in other operations. Today business applications are primarily concerned with OR analysis for the possible alternative actions. The business and industry benefited from OR in the areas of inventory, reorder policies, optimum location and size of warehouses, advertising policies, etc. 1.2 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 OR did not exist then. It was really only in the late 1930s that OR began in a systematic fashion, and it started in the UK. As such, it would be interesting to give a short history of OR. 1936 Early in 1936, the British Air Ministry established Bawdsey Research Station, on the east coast, near Felixstowe, Suffolk, as the center where all pre-war radar experiments for both the Air Force and the Army would be carried out. Experimental radar equipment was brought up to a high state of reliability, and ranges of over 100 miles on aircraft were obtained. It was also in 1936 that Royal Air Force (RAF) Fighter Command, charged specifically with the air defense of Britain, was first created. It lacked, however, any effective fighter aircraft - no Hurricanes or Spitfires had come into service - and no radar data was yet fed into its very elementary warning and control system. It had become clear that radar would create a whole new series of problems in fighter direction and control, so in late 1936, some experiments started at Biggin Hill in Kent into the effective use of such data. This early work, attempting to integrate radar data with ground-based observer data for fighter interception, was the start of OR. 1937 The first of three major pre-war air-defense exercises were carried out in the summer of 1937. The experimental radar station at Bawdsey Research Station was brought into operation, and the information derived from it was fed into the general air-defense warning and control system. From the early warning point of view, this exercise was encouraging, but the tracking information obtained 2 from radar, after filtering and transmission through the control and display network, was not very satisfactory. 1938 In July 1938, a second major air-defense exercise was carried out. Four additional radar stations had been installed along the coast, and it was hoped that Britain now had an aircraft location and control system greatly improved both in coverage and effectiveness. The exercise revealed, rather, that a new and serious problem had arisen. There was the need to coordinate and correlate the additional and often conflicting information received from the additional radar stations. With the outbreak of war apparently imminent, it was obvious that something new - drastic if necessary - had to be attempted. A new approach was needed. Accordingly, on the termination of the exercise, the Superintendent of Bawdsey Research Station, A.P. Rowe, announced that although the exercise had again demonstrated the radar system's technical feasibility for detecting aircraft, its operational achievements still fell far short of requirements. He, therefore, proposed that a crash program of research into the operational - as opposed to the technical - aspects of the system should begin immediately. The term "operational Research" (RESEARCH into (military) OPERATIONS) was coined as a suitable description of this new branch of applied science. The first team was selected from amongst the scientists of the radar research group the same day. 1939 In the summer of 1939, Britain held what was to be its last pre-war air defense exercise. It involved some 33,000 men, 1,300 aircraft, 110 antiaircraft guns, 700 searchlights, and 100 barrage balloons. This exercise showed a great improvement in the operation of the air defense warning and control system. The contribution made by the OR team was so apparent that the Air Officer Commander- in-Chief RAF Fighter Command (Air Chief Marshal Sir Hugh Dowding) requested that, on the outbreak of war, they should be attached to his headquarters at Stanmore in North London. Initially, they were designated the "Stanmore Research Section." In 1941 they were redesignated the "Operational Research Section" when the term was formalized and officially accepted, and similar sections were set up at other RAF commands. 3 1940 On May 15th, 1940, with German forces advancing rapidly in France, Stanmore Research Section was asked to analyses a French request for ten additional fighter squadrons (12 aircraft a squadron - so 120 aircraft in all) when losses were running at some three squadrons every two days (i.e., 36 aircraft every 2 days). They prepared graphs for Winston Churchill (the British Prime Minister of the time), based upon a study of current daily losses and replacement rates, indicating how rapidly such a move would deplete fighter strength. No aircraft were sent, and most of those currently in France were recalled. Some hold this to be the most strategic contribution to the course of the war made by OR (as the aircraft and pilots saved were consequently available for Britain's successful air defense, the Battle of Britain). 1941 onward In 1941, an Operational Research Section (ORS) was established in Coastal Command which was to carry out some of the most well-known OR work in World War II. The responsibility of Coastal Command was, to a large extent, the flying of long-range sorties by single aircraft with the object of sighting and attacking surfaced U-boats (German submarines). The technology of the time meant that (unlike modern-day submarines) surfacing was necessary to recharge batteries, vent the boat of fumes and recharge air tanks. Moreover, U-boats were much faster on the surface than underwater as well as being less easily detected by sonar. Thus, Operations Research started just before World War II in Britain with the establishment of teams of scientists to study military operations' strategic and tactical problems. The objective was to find the most effective utilization of limited military resources by the use of quantitative techniques. Following the end of the war, OR spread, although it spread in different ways in the UK and USA. In 1951 a committee on Operations Research formed by the National Research Council of USA, and the first book on "Methods of Operations Research" by Morse and Kimball, was published. In 1952 the Operations Research Society of America came into being. Success of Operations Research in the Army attracted the attention of the industrial managers who were seeking solutions to their complex business problems. Nowadays, almost every organization in all countries has staff applying operations research. The use of operations research in government has spread from the military to a wide variety of departments at all levels. The growth of operations research has not limited to the USA and UK, it has reached many countries of the world, and today, Operations Research is a popular subject in management institutes and schools of mathematics. 4 1.1 MEANING OF OPERATIONS RESEARCH Defining OR is a difficult task as its boundaries and content are not yet fixed. It can be regarded as the use of mathematical and quantitative techniques to substantiate the decision being taken. Further, it is multidisciplinary which takes tools from subjects like mathematics, statistics, engineering, economics, psychology etc. and uses them to score the consequences of possible alternative actions. Today it has become a professional discipline that deals with the application of scientific methods to decision- making. The definitions stressed by various experts and Societies on the subject enable us to know what OR is and what it does. They are as follows: 1. According to the Operational Research Society of Great Britain, Operational Research is the attack of modern science on complex problems arising in the direction and management of large systems of men, machines, materials, and money in the industry, business, government, and defense. Its distinctive approach is to develop a scientific model of the system, incorporating measurements of factors such as change and risk, with which to predict and compare the outcomes of alternative decisions, strategies, or controls. The purpose is to help management determine its policy and actions scientifically. 2. Randy Robinson stresses that Operations Research is applying scientific methods to improve the effectiveness of operations, decisions, and management. By means such as analyzing data, creating mathematical models, and proposing innovative approaches. Operations Research professionals develop scientifically-based information that gives insight and guides decision-making. They also develop related software, systems, services, and products. 3. Morse and Kimball have stressed OR is a quantitative approach and described it as "a scientific method of providing executive departments with a quantitative basis for decisions regarding the operations under their control." 4. Saaty considers OR as a tool for improving the quality of answers. He says, "OR is the art of giving bad answers to problems which otherwise have worse answers." 5. Miller and Starr see OR as applied decision theory. They state, "OR is applied decision theory which uses any scientific, mathematical or logical means to attempt to cope with the problems that confront the executive when he tries to achieve a thoroughgoing rationality in 5  dealing with his decision problem." 6. Pocock stresses that OR is an applied Science. He states, "OR is a scientific methodology (analytical, mathematical, and quantitative) that assesses the overall implication of various alternative courses of action in a management system provides an improved basis for management decisions." 7. According to the Operations Research Society, America, "OR is concerned with scientifically deciding how to best design and operate man-machine system usually requiring the allocation of scarce resources." 8. Daellenbach and George state that "OR is essentially a collection of mathematical techniques and tools which, in conjunction with system approach, are applied to solve practical decision problems of an economic or engineering nature." 9. Thieraub and Klekamp stressed that "OR utilizes the planned approach (updated scientific method) and an interdisciplinary team in order to represent complex functional relationships as mathematical models for the purpose of providing a quantitative analysis." 10. H.A. Taha stresses that "OR is a scientific knowledge through interdisciplinary team effort for the purpose of determining the best utilization of limited resources." 11. According to H.M. Wagner, "OR is a scientific approach to problem-solving for executive management." 1. 2 FEATURES OF OR The significant features of operations research include the followings: i. Decision-making: Every industrial organization faces multifaceted problems to identify t he best possible solution to their problems. OR aims to help the executives to obtain optimal solution with the use of OR techniques. It also helps the decision-maker to improve his creative and judicious capabilities, analyze and understand the problem situation leading to better control, better co-ordination, better systems, and finally better decisions. ii. Scientific Approach: OR applies scientific methods, techniques, and tools for analysis and solution of complex problems. In this approach, there is no place for guesswork and the personal bias of the decision-maker. 6  iii. Inter-disciplinary Team Approach: Basically, the industrial problems are of complex nature and therefore require a team effort to handle it. This team comprises scientists/mathematicians, and technocrats who jointly use the OR tools to obtain an optimal solution to the problem. They try to analyze the cause and effect relationship between various parameters of the problem and evaluate multiple alternative strategies. iv. System Approach: The system approach's main aim is to trace for each proposal all significant and indirect effects on all sub-system on a system and evaluate each action in terms of effects for the system as a whole. The interrelationships and interactions of each sub- system can be handled with the help of mathematical/analytical models of OR to obtain an acceptable solution. v. Use of Computers: The models of OR need a lot of computation, and therefore, the use of computers becomes necessary. With the use of computers, it is possible to handle complex problems requiring a large number of calculations. The operations research models' objective is to attempt and locate the best or optimal solution under the specified conditions. For the above purpose, it is necessary that a measure of effectiveness has to be defined, which must be based on the goals of the organization. These measures can be used to compare the alternative courses of action taken during the analysis. 1.3 Overview of the O. R. Modeling Approach/ Stages of Development of Operations Research OR is a logical and systematic approach to provide a rational basis for decision-making. The stages of development of OR are also known as phases and processes. The phases of OR must be logical and systematic. The various steps required for the analysis of a problem under OR are as follows: Step I: Observe the problem environment Step II: Analyze and define the problem Step III: Develop a model Step IV: Select appropriate data input Step V: Provide a solution and test its reasonableness Step VI: Implement the solution Step I. Observe the Problem Environment The first step of the OR study is the observation of the environment in which the problem exists. The activities that constitute this step are visits, conferences, observations, research, etc. with the help of such activities, the OR analyst gets sufficient information and support to proceed and is better 7  prepared to formulate the problem. Step II. Analyze and Define the Problem In this step, not only the problem is defined but also objectives, uses, and limitations of the study that are stressed in the light of the problem. This step's end results are a clear grasp of the need for a solution and an understanding of its nature. Step III. Develop a Model The next step is to develop a model, which is a representation of the same real or abstract situation. OR models are basically mathematical models representing systems, processes, or environments in the form of equations, relationships, or formulae. The activities in this step are to define interrelationships among variables, formulating equations, using known OR models, or searching suitable alternate models. The proposed model may be field-tested and modified in order to work under stated environmental constraints. A model may also be modified if the management is not satisfied with the results. Step IV. Selection of Appropriate Data Input It is a fact that without authentic and appropriate data, the results of the OR models cannot be trusted. Hence, taping the right kind of data is a vital step in the OR process. Essential activities in this step are analyzing internal/external data and facts, collecting opinions, and using computer data banks. The purpose of this step is to have sufficient input to operate and test the model developed in Step III. Step V. Solution and Testing In this step, the solution to the problems is obtained with the help of the model and data input. Such a solution is not implemented immediately, and this solution is used to test the model and find its limitations, if any. If the solution is not reasonable or if the model is not behaving properly, updating and modification of the model are considered at this stage. The end result of this step is a solution that is desirable and supports current organizational objectives. Step VI. Implementation of the Solution This is the last phase of the OR study. In OR, the decision-making is scientific, but the implementation of decisions involves many behavioural issues. Therefore, the implementation authority has to resolve the behavioural issues involving the workers and supervisors to avoid further conflicts. The gap between management and OR scientist may offer some resistance but must be eliminated before the solution is accepted in totality. Both parties should play a positive role since the 8 implementation will help the organization as a whole. A properly implemented solution obtained through OR techniques results in improved working conditions and wins management support. 9 The process, process activities, and process output are summarized in the following Table 1 Process Activities Process Process Output Site visits, Conferences, Sufficient information and Observations, Research Step 1: support to proceed Observe the problem environment Define: Use, Objectives, A clear grasp of the need for limitations Step 2: and nature of the solution Analyze and define requested the problem Define interrelationships, Models that work under stated Formulate equations, environmental constraints Step 3: Develop a Model Use known OR model, Analyze: internal-external data, Sufficient inputs to operate and Search alternate Model facts Step 4: test model Collect options, Select appropriate data input Test the model Solution(s) that support current find limitations Step 5: organizational goals Use computer data banks Provide a solution and update the model test its reasonableness Resolve behavioural issues Improved working and Sell the idea Step 6: Management support for Give explanations Implement the solution longer run operation of model Management involvement Step 5: Provide a solution and test its reasonableness 10  1.4 Relationship between the Manager and OR Specialist The key responsibility of a manager is decision-making. The role of the OR specialist is to help the manager make better decisions. Figure 1-1 explains the relationship between the OR specialist and the manager/decision-maker. STEPS IN PROBLEM RECOGNITION, INVOLVEMENT: OR SPECIALIST or FORMULATION AND SOLUTION MANAGER Recognize from organizational symptoms that a problem exists. MANAGER Decide what variables are involved; state the problem in quantitative relationships M MANAGER and OR Specialist among the variables. Investigate methods for solving the OR Specialist problems as stated above; determine appropriate quantitative tools to be used. Attempt solutions to the problems; find various solutions; state assumptions underlying these solutions; test alternative O. OR Specialist solutions. Determine which solution is most effective because of practical constraints within the MANAGER and OR Specialist organization; decide what the solution means for the organization. MANAGER Choose the solution to be used. ‘Sell’ the decision to operating managers; get their understanding and cooperation. MANAGER and OR Specialist 11 1.5 Outlines of OR Models/OR Tools and Techniques In OR, the problem is expressed in the form of a model. A model is a theoretical abstraction (approximation) of a real-life problem. It can be defined as a simplified representation of an operation or a process in which only the basic aspects of the most important features of a typical problem under investigation are considered. OR analysts have given special impetus to the development and use of techniques like linear programming, game theory, decision theory, queuing/Waiting line theory, inventory models/Controls, and simulation. In addition to the above techniques, some other common tools are non-linear programming, integer programming, dynamic programming, sequencing theory, Markov process, network scheduling (PERT/CPM), symbolic model, information theory, and Utility/value theory. The list, of course, is not exhaustive. The brief explanations of some of the above techniques/tools are as follows: i. Linear Programming (LP.) Linear programming is basically a constrained optimization technique that tries to optimize some criterion within some constraints. It consists of an objective function which is some measure of effectiveness like profit, loss, or return on investment and several boundary conditions putting a restriction on the use of resources. The objective function and boundary conditions are linear in nature. There are methods available to solve a linear programming problem. ii. Game Theory It is used for decision-making under conflicting situations where there are one or more opponents. The opponents, in the game theory, are called players. The motives of the players are dichotomized. One player's success tends to be at the cost of others, and hence they are in conflict. In the game theory models, a conflict situation arises and helps to improve the decision process by formulating an appropriate strategy. iii. Decision Theory: Decision theory is concerned with making decisions under conditions of complete certainty about the future outcomes and under conditions such that we can make some probability about what will happen in the future. iv. Waiting Line or Queuing Theory This is used in situations where the queue is formed (for example, customers waiting for service, aircrafts waiting for landing, jobs waiting for processing in the computer system, etc.). If we assume that there are costs associated with waiting in line, and if there are costs of adding 12  more service facilities, we want to minimize the sum of costs of waiting and the costs of providing service facilities. The objective here is to minimize the cost of waiting without increasing the cost of services. Waiting line theory helps to make calculations like the number of expected members of people in the queue, expected waiting time in the queue, expected idle time for the server, etc. These calculations can be used to determine the desired number of service facilities or the number of servers. v. Inventory Control Models Inventory models make decisions that minimize total inventory cost. These models deal with the quantities which are either purchased or stocked since each factor involves cost. The purchase and material managers are normally encountering such situations. Therefore, inventory models provide a rational answer to these questions in different supply and demand situations for different kinds of materials. Inventory control models help managers to decide ordering time, reordering level, and optimal ordering quantity. The approach is to prepare a mathematical model of the situation that expressed total inventory costs in terms of demand, size of the order, possible over or understocking, and other relevant factors and then to determine optimal order size, optimum order-level, etc., using calculus or some other technique. This model successfully reduces the total cost of purchasing, carrying, and out-of-stock inventory. vi. Simulation Simulation is a procedure that studies a problem by creating a model of the process involved in the problem and then, through a series of organized trials and error solutions, attempts to determine the best solution. It is basically data generating technique, where sometimes it is risky, cumbersome, or time-consuming to conduct a real study or experiment to know more about the situation or problem or when actual experimentation is not feasible, or the solution of the model is not possible. The available analytical methods cannot be used in all situations due to a large number of variables or a large number of interrelationships among the variables and the complexity of the relationship; it is not possible to develop an analytical model representing the real situation. Sometimes, even building a model is possible, but its solution may not be possible. Under such situations, simulation is used. It should be noted that simulation does not solve the problem by itself, but it only generates the required information or data needed for decision problem or decision-making. 13 vii. Non-Linear Programming These models may be used when either the objective function or some of the constraints are not linear in nature. Non-linearity may be introduced by such factors as a discount on the price of purchase of large quantities and graduated income tax etc. Linear programming may be applied to approximate non-linear constraints but limited to some range because approximation becomes poorer as the range is extended. Non-linear methods may be used to determine the approximate area in which a solution lies, and linear methods may be used to obtain a more exact solution. viii. Integer Programming This method can be used when one or more of the variables can only take integer values. Examples are the number of trucks in a fleet, number of passengers in an aircraft, number of generators in a power generating plant, etc. Approximate solutions can be obtained without using integer programming methods, but the approximation generally becomes poorer as the number becomes smaller. There are techniques to obtain the solution to integer programming problems. ix. Dynamic Programming This is a method of analyzing multistage decision processes, in which each elementary decision is dependent upon those preceding it as well as upon external factors. It drastically reduces the computational efforts otherwise necessary to analyze the results of all possible combinations of elementary decisions. x. Sequencing Theory This is related to the waiting line theory and is applicable when the facilities are fixed, but the order of service may be controlled. The scheduling of service or the sequencing of jobs is done to minimize the relevant costs and time. xi. Markov Process It is used for decision-making in situations where various states are defined. The probability of going from one state to another is known and depends on the present state and is independent of how we have arrived at that state. The theory of Markov process helps us to calculate the long run probability of being in a particular state (steady-state probability), which is used for decision- making. xii. Network Scheduling—PERT and CPM These techniques are used to plan, schedule, and monitor large projects such as building construction, maintenance of computer system installation, Research and development design, etc. 14  The technique aims at minimizing trouble spots, such as delays, interruptions, and production bottlenecks, by identifying factors and coordinating various parts of the overall job/project. The different activities and their relationships of the entire project are represented diagrammatically with the help of networks made of arrows representing different activities and interrelationships among them. Such a representation is used for identifying critical activities and critical paths. There are two main types of technique in network scheduling, they are: Program Evaluation and Review Technique (PERT) – is used when activities time is not known accurately/ only probabilistic estimate of time is available. Critical Path Method (CPM) – is used when activity time is known accurately. xiii. Symbolic Logic/Model It deals with substituting symbols for words, classes of things, or functional systems. Symbolic logic involves rules, algebra of logic, and propositions. There have been only limited attempts to apply this technique to business problems; however, it has had extensive application in the design of computing machinery. xiv. Information Theory Information theory is an analytical process transferred from the electrical communications field to operations research. It seeks to evaluate the effectiveness of information flow within a given system. Despite its application mainly to communication networks, it has an indirect influence in simulating the examination of business organizational structures with a view to improving information or communication flow. xv. Utility/Value Theory It deals with assigning numerical significance to the worth of alternative choices. To date, this has been only a concept and is in the stage of elementary model formulation and experimentation and can be useful in the decision-making process 1.6 Applications of Operations Research The scope of OR is not only confined to any specific agency like defense services, but today it is widely used in all industrial organizations. It can be used to find the best solution to any problem, be it simple or complex. It is useful in every field of human activities, where optimization of resources is required in the best way. Thus, it attempts to resolve the conflicts of interest among the components of an organization in a way that is best for the organization as a whole. The main fields where OR is extensively used are given below; however, this list is not exhaustive but only illustrative. 15 i. National Planning and Budgeting: OR is used for the preparation of Five Year Plans, annual budgets, forecasting of income and expenditure, scheduling of major projects of national importance, estimation of GNP, GDP, population, employment and generation of agriculture yields, etc. ii. Defense Services: Basically, formulation of OR started from the Army, so it has wide application in the areas such as the development of new technology, optimization of cost and time, tender evaluation, setting and layouts of defense projects, assessment of "Threat analysis," strategy of battle, effective maintenance and replacement of equipment, inventory control, transportation and supply depots, etc. iii. Industrial Establishment and Private Sector Units: OR can be effectively used in plant location and setting finance planning, product and process planning, facility planning and construction, production planning and control, purchasing, maintenance management, and personnel management, etc., to name a few. iv. Research & Development and Engineering: Research and development being the heart of technological growth, OR has wide scope for and can be applied in technology forecasting and evaluation, technology, and project management, preparation of tender and negotiation, value engineering, work/method study and so on. v. Business Management and Competition: OR can help in taking business decisions under risk and uncertainty, capital investment and returns, business strategy formation, optimum advertisement outlay, optimum sales force and their distribution, market survey and analysis and market research techniques, etc. vi. Agriculture and Irrigation: In the area of agriculture and irrigation also OR can be useful for project management, construction of major dams at minimum cost, optimum allocation of supply and collection points for fertilizer/seeds and agriculture outputs, and optimum mix of fertilizers for better yield. vii. Education and Training: OR can be used for obtaining the optimum number of schools with their locations, optimum mix of students/teacher-student ratio, optimum financial outlay, and other relevant information in the training of graduates to meet the national requirements. 16  viii. Transportation: Transportation models of OR can be applied to real life problems to forecast public transport requirements, optimum routing, forecasting of income and expenses, project management for railways, railway network distribution, etc. In the same way, it can be useful in the field of communication. ix. Home Management and Budgeting: OR can be effectively used for control of expenses to maximize savings, time management, work-study methods for all related works. Investment of surplus budget, appropriate insurance of life and properties, and the estimate of depreciation and optimum premium of insurance, etc. 1.7 Limitations of Operations Research Operations Research has a number of applications; similarly, it also has certain limitations. These limitations are mostly related to the model building and money and time factors problems involved in its application rather than its practical utility. Some of them are as given below: i. Distance between User and Analyst: OR being a specialist's job requires a mathematician or statistician, who might not be aware of the business problems. Similarly, a manager is unable to understand the complex nature of Operations Research. Thus there is a gap between the two. Management itself may offer a lot of resistance due to conventional thinking. ii. The magnitude of Computation: Operations Research models try to find out optimal solutions taking into account all the factors. In this modern world, these factors are enormous, and expressing them in the quantitative model and establishing relationships among these require voluminous calculations, which can be handled only by machines/ computers. iii. Time and Money Costs: When basic data are subjected to frequent changes, incorporating them into the OR models is a costly proposition. Moreover, a fairly good solution at present may be more desirable than a perfect OR solution available after some time. The computational time increases depending upon the size of the problem and the accuracy of results desired. iv. Non-Quantifiable Factors: OR provides a solution only when all elements related to a problem can be quantified. All relevant variables do not lend themselves to quantification. Factors that cannot be quantified find no place in OR study. Models in OR do not take into account qualitative factors or emotional factors, which may be quite important. 17 v. Implementation: Implementation of any decision is a delicate task. It must take into account the complexities of human relations and behaviour. Sometimes, resistance is offered due to psychological factors which may not have any bearing on the problem as well as its solution. 18  LINEAR PROGRAMMING 2.0 Introduction to Linear Programming The development of linear programming has been ranked among the most important scientific advances of the mid-20th century, and we must agree with this assessment. Its impact since just 1950 has been extraordinary. Today it is a standard tool that has saved many thousands or millions of dollars for most companies or businesses of even moderate size in the various industrialized countries of the world. The adjective linear means that all the mathematical functions in this model are required to be linear functions. The word programming does not refer here to computer programming; rather, it is essentially a synonym for planning. Thus, linear programming involves the planning of activities to obtain an optimal result, i.e., a result that reaches the specified goal best (according to the mathematical model) among all feasible alternatives. Linear Programming is a special and versatile technique that can be applied to various management problems such as Advertising, Distribution, Investment, Production, Refinery Operations, and Transportation analysis. Linear programming is useful not only in industry and business but also in non-profit sectors such as Education, Government, hospitals, and Libraries. The most common type of application involves the general problem of allocating limited resources among competing activities in the best possible (i.e., optimal) way. More precisely, this problem involves selecting the level of certain activities that compete for scarce resources that are necessary to perform those activities. The choice of activity levels then dictates how much of each resource will be consumed by each activity. The linear programming method is applicable in problems characterized by the presence of decision variables. The objective function and the constraints can be expressed as linear functions of the decision variables. The decision variables represent quantities that are, in some sense, controllable inputs to the system being modeled. An objective function represents some principal objective criterion or goal that measures the effectiveness of the system, such as maximizing profits or productivity or minimizing cost or consumption. There is always some practical limitation on the availability of resources, such as man, material, machine, or time for the system. These constraints are expressed as linear equations involving the decision variables. 19 Solving a linear programming problem means determining actual values of the decision variables that optimize the objective function subject to the limitation imposed by the constraints. The main important feature of the linear programming model is the presence of linearity in the problem. The use of t h e linear programming model arises in a wide variety of applications. Some models may not be strictly linear but can be made linear by applying appropriate mathematical transformations. Still, some applications are not at all linear but can be effectively approximated by linear models. The ease with which linear programming models can usually be solved makes an attractive means of dealing with otherwise intractable non-linear models. 2.1 Linear Programming Problem Formulation The linear programming problem formulation involves 1. Choosing decision variables 2. Choosing an objective and an objective function – linear function in variables 3. Choosing constraints – linear inequalities 4. Choosing sign restrictions The linear programming problem formulation is illustrated below through a product mix problem. The product mix problem occurs in an industry where it is possible to manufacture a variety of products. A product has a certain margin of profit per unit and uses a common pool of limited resources. In this case, the linear programming technique identifies the product combination, which will maximize the profit subject to the availability of limited resource constraints. Example 2.1: Suppose an industry is manufacturing two types of products P1 and P2. The profits per Kg of the two products are Le30 and Le40 respectively. These two products require processing in three types of machines. The following table shows the available machine hours per day and the time required on each machine to produce 1 Kg of P1 and P2. Formulate the problem in the form of a linear programming model. Profit/Kg P1 P2 Total available machine Le30 Le40 hours/day Machine 1 3 2 600 Machine 2 3 5 800 Machine 3 5 6 1100 20 Solution: The procedure for linear programming problem formulation is as follows: Introduce the decision variable as follows: Let x1 = amount of P1 x2 = amount of P2 To maximize profits, we establish the objective function as 30 x1 + 40 x2 Since 1Kg of P1 requires 3 hours of processing time in machine 1 while the corresponding requirement for P2 is 2 hours and the Total available Machine hours/day is 600hrs, then the first constraint can be expressed as 3x1 + 2 x2  600 Similarly, corresponding to machine 2 and 3, the constraints are 3x1 + 5 x2  800 5 x1 + 6 x2  1100 In addition to the above, there is no negative production, which may be represented algebraically as x1  0; x2  0 Thus, the product mix problem in the linear programming model is as follows: Maximize 30 x1 + 40 x2 Subject to: 3x1 + 2 x2  600 3x1 + 5 x2  800 5 x1 + 6 x2  1100 x1  0; x2  0 2. 2 Formulation with Different Types of Constraints The constraints in example 2.1 are of "less than or equal to" type. In this section, we are going to discuss the linear programming problem with different constraints, which is illustrated in Example 2.2. 21 Example 2.2: A company owns two flour mills A and B, which have different production capacities for high, medium, and low-quality flour. The company has entered a contract to supply flour to a firm every month with at least 8, 12, and 24 kg of the high, medium, and low quality, respectively. It costs the company Le 2,000 and Le1,500 per day to run mill A and B, respectively. On a day, Mill A produces 6, 2, and 4 kg of the high, medium, and low-quality flour, Mill B produces 2, 4, and 12 kg of the high, medium, and low- quality flour, respectively. How many days per month should each mill be operated in order to meet the contract order most economically. Quality of Product (Flour)/day Cost of Production Mill High Medium Low (Le) A 6 2 4 2000 B 2 4 12 1500 Solutio n: Let x1 and x2 define the quantity produced by mills A and B. Here the objective is to minimize the cost of the machine runs and to satisfy the contract order. The linear programming problem is given by Minimize 2000 x1 + 1500 x2 Subject to: 6 x1 + 2 x2  8 (for high quality) 2 x1 + 4 x2  12 (for medium quality) 4 x1 + 12 x2  24 (for low-quality) x1  0; x2  0 (production level) 2.3 Product mix - Activity-based formulation Example 2.3: 22 Furniture Company manufactures four models of chairs. Each chair requires a certain amount of raw materials (wood/steel) to make. The company wants to decide on a product that maximizes profit (assuming all produced chairs are sold). The required and available amounts of materials are as follows. Chair 1 Chair 2 Chair 3 Chair 4 Total Available material (Kg) Steel 1 1 3 9 4,400 Wood 4 9 7 2 6,000 Profit $12 $20 $18 $40 Maximize Decision variables: xi = the number of chairs of the type i produced Each xi is non-negative Objective function: Maximize profit z = 12 x1 + 20 x2 + 18 x3 + 40 x4 Constraints: At most 4, 400 kg of Steel available: x1 + x2 + 3x3 + 9 x4  4, 400 At most 6, 000 kg of wood available: 4 x1 + 9 x2 + 7 x3 + 2 x4  6000 Resulting program: Max 12 x1 + 20 x2 + 18 x3 + 40 x4 = z [Profit] x1 + x2 + 3x3 + 9 x4  4, 400 [Steel] 4 x1 + 9 x2 + 7 x3 + 2 x4  6000 [wood] x1 , x2 , x3 , x4  0 Activity-based formulation Instead of constructing the formulation as before (row-by-row), we can proceed by columns. We can view columns of the program as activities. An activity has inputs: materials consumed per unit of activity (1 kg of Steel and 4 kg of wood) outputs: products produced per unit of activity ($12 of profit) activity level: a level at which we operate the activity (indicated by a variable x1 ) 1 kg of Steel Chair 1 23 x1  $12 of profit 4 kg of wood Input Activity Output Operating the activity "Chair 1" at level x1 means that we produce x1 chairs of type 1, each consuming 1 Kg of Steel, 4 kg of wood, and producing $12 of profit. Activity levels are always assumed to be non- negative. The materials/labor/profit consumed or produced by an activity is called items (correspond to rows). The effects of an activity on items (i.e., the amounts of items that are consumed/produced by an activity) are input-output coefficients. The total amount of items available/supplied/required is called the external flow of items. We choose the objective to be one of the items which we choose to maximize or minimize. The last step is to write material balance equations that express the flow of items in/out of activities and with respect to the external flow. Items: External flow of items: Steel Steel: 4,400 kg of available (flowing in) Wood Wood: 6,000 kg of available (flowing in) Profit maximize (flowing out) Objective: Profit: maximize (flowing out) Activities: Producing a chair of type i where i = 1, 2, 3, 4, each is assigned an activity level x1 Chair 1: Producing 1 chair of type 1 Consumes 1 kg of Steel 1 kg of Steel Chair 1 $12 of Profit x1 4 kg of Wood 4 kg of wood produces $12 of profit Chair 2: Producing 1 chair of type 2 consumes 1 kg of Steel 1 kg of Steel Chair 2 $20 of profit 9 kg of Wood 9 kg of wood x2 produces $20 of profit Chair 3: Producing 1 chair of type 3 24 Chair 3 x3 consumes 3 kg of Steel 3 kg of Steel $18 of profit 7 kg of Wood 7 kg of wood produces $18 of profit Chair 4: Producing 1 chair of type 4 Consumes 9 kg of Steel 9 kg of Steel Chair 4 $40 of Profit 2 kg of Wood 2 kg of wood x4 Produces $40 of profit The material balance equations: To see how to do this, consider activity Chair 1: consumes 1 kg of Steel, 4 kg of wood, and produces $12 of profit. Thus at level x1 , we consume 1x1 kg of Steel, 4x1 of wood, and produce 12x1 dollars of profit. 1 kg of Steel $12 of Profit... + 12 x1 +... [Profit] Chair 1 x1 4 kg of Wood... + 1x1 +... [Steel]... + 4 x1 +... Wood] On the right, you see the effect of operating the activity at level x1. (Note in general, we will adopt a different sign convention; we shall discuss it in a later example.) Thus considering all activities we obtain: 12 x1 + 20 x2 + 18 x3 + 40 x4 Profit] x1 + x2 + 3x3 + 9 x4 [Steel] 4 x1 + 9 x2 + 7 x3 + 2 x4 [Wood] Finally, we incorporate the external flow and objective: 4,400 kg of Steel available, 6,000 kg of wood available maximize profit: Max 12 x1 + 20 x2 + 18 x3 + 40 x4 = z [Profit] x1 + x2 + 3x3 + 9 x4  4, 400 [Steel] 4 x1 + 9 x2 + 7 x3 + 2 x4  6, 000 [Wood] x1 , x2 , x3 , x4  0 2.4 Blending 25 Example 2.5: A company wants to produce a certain alloy containing 30% lead, 30% zinc, and 40% tin. This is to be done by mixing certain amounts of existing alloys that can be purchased at certain prices. The company wishes to minimize the cost. There are 9 available alloys with the following composition and prices. Alloy 1 2 3 4 5 6 7 8 9 Blend Lead (%) 20 50 30 30 30 60 40 10 10 30 Zinc (%) 30 40 20 40 30 30 50 30 10 30 Tin (%) 50 10 50 30 40 10 10 60 80 40 Cost ($/kg) 7.3 6.9 7.3 7.5 7.6 6.0 5.8 4.3 4.1 Minimize Let the decision variables be x1 , x2 , x3 , x4...x9 where xi is the amount of Alloy i in a unit of blend In particular, the decision variables must satisfy x1 + x2 + x3 + x4 +...x9 = 1. (It is a common mistake to choose xi the absolute amount of Alloy i in the blend. (That may lead to a non-linear program.) With that, we can set up constraints and the objective function. Min 7.3x1 + 6.9 x2 + 7.3x3 + 7.5 x4 + 7.6 x5 + 6.0 x6 + 5.8 x7 + 4.3x8 + 4.1x9 = z [Cost] x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 = 1 0.2 x1 + 0.5 x2 + 0.3x3 + 0.3x4 + 0.3x5 + 0.6 x6 + 0.4 x7 + 0.1x8 + 0.1x9 = 0.3 [Lead] 0.3x1 + 0.4 x2 + 0.2 x3 + 0.4 x4 + 0.3x5 + 0.3x6 + 0.5 x7 + 0.3x8 + 0.1x9 = 0.3 [Zinc] 0.5 x1 + 0.1x2 + 0.5 x3 + 0.3x4 + 0.4 x5 + 0.1x6 + 0.1x7 + 0.6 x8 + 0.8 x9 = 0.4 [Tin] 2.5 Solving Linear Programs 2.5.1 Graphical Analysis of Linear Programming/ Graphical Method This section shows how a two-variable linear programming problem is solved graphically. The main steps involved are: Find the feasible region. Plot an iso-value (iso-profit, iso-cost) line for some value. Slide the line in the direction of increasing value until it only touches the region. Read-off an optimal solution. 26 2.5.2 Terminology for the Solutions of the Model You may be used to having the term solution mean the final answer to a problem, but the convention in linear programming (and its extensions) is quite different. Here, any specification of values for the decision variables ( x1 , x2...xn ) is called a solution, regardless of whether it is a desirable or even an allowable choice. Different types of solutions are then identified by using an appropriate adjective. A feasible solution is a solution for which all the constraints are satisfied simultaneously. An infeasible solution is a solution for which at least one constraint is violated. In example 2.6, the points (2, 3) and (4, 1) in Figure 2 are feasible solutions, while the points (-1, 3) and (4, 4) are infeasible solutions. Half Plane - A linear inequality in two variables is called a half-plane. Boundary - The corresponding equality (line) is called the boundary of the half-plane. Close Half Plane – Half plane with its boundary is called a closed half-plane. Feasible Region: The collection of all the feasible solutions is called the feasible region. An optimal solution is a feasible solution that has the most favorable value of the objective function. The most favorable value is the largest value if the objective function is to be maximized, whereas it is the smallest value if the objective function is to be minimized. A corner-point feasible (CPF) solution is a solution that lies at a corner of the feasible region. a) The Corner Point Feasible solutions of example 2.6 (Glass Company) are indicated in the figure below. The five dots are the five CPF solutions for the Glass Company problem. The graphical method is illustrated as follows: 27 Example 2.6 A Glass Company produces high-quality glass products, including windows and glass doors. It has three plants. Aluminum frames and hardware are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces the glass and assembles the products. Because of declining earnings, top management has decided to revamp the company's product line. Unprofitable products are being discontinued, releasing production capacity to launch two new products having large sales potential: Product A: An 8-foot glass door with aluminum framing Product B: A 4  6 foot double-hung wood-framed window Product A requires some of the production capacity in Plants 1 and 3, but none in Plant 2. Product B needs only Plants 2 and 3. The marketing division has concluded that the company could sell as much of either product as could be produced by these plants. However, because both products would be competing for the same production capacity in Plant 3, it is not clear which mix of the two products would be most profitable. The table below gives the number of hours of production time available per week in each plant, the number of hours of production time used in each plant for each batch produced, and the profit per batch produced Production Time Per Batch (Hours) Product Production Time Available Plant A B per Week (Hours) 1 1 0 4 2 0 2 12 3 3 2 18 Profit Per Batch $3000 $5000 As an OR Specialist, what advice would you give to management on production rates for the two products in order to maximize their total profit, subject to the restrictions imposed by the limited production capacities available in the three plants? (Each product will be produced in batches of 20, so the production rate is defined as the number of batches produced per week.) To formulate the mathematical (linear programming) model for this problem, let x1 = Number of batches of product A produced per week x2 = Number of batches of product B produced per week Z = Total profit per week (in thousands of dollars) from producing these two products 28 Thus, x1 and x2 are the decision variables for the model. Using the bottom row of the table, we obtain Z = 3x1 + 5 x2 The objective is to choose the values of x1 and x2 so as to maximize Z = 3x1 + 5 x2 , subject to the restrictions imposed on their values by the limited production capacities available in the three plants. The table above indicates that each batch of product 1 produced per week uses 1 hour of production time per week in Plant 1, whereas only 4 hours per week are available. This restriction is expressed mathematically by the inequality x1  4. Similarly, Plant 2 imposes the restriction that 2 x2  12. The number of hours of production time used per week in Plant 3 by choosing x1 and x2 as the new products' production rates would be 3x1 + 2 x2. Therefore, the mathematical statement of the Plant 3 restriction is 3x1 + 2 x2  18. Finally, since production rates cannot be negative, it is necessary to restrict the decision variables to be non-negative: x1  0 and x2  0. To summarize, in the mathematical language of linear programming, the problem is to choose values of x1 and x2 so as to Maximize Z = 3x1 + 5 x2 Subject to the restrictions x1  4 2 x2  12 3x1 + 2 x2  18 and x1  0 , x1  0 This very small problem has only two decision variables and, therefore, only two dimensions, so a graphical procedure can be used to solve it. This procedure involves constructing a two-dimensional graph with x1 and x2 as the axes. The first step is to identify the values of ( x1 , x2 ) that are permitted by the restrictions. This is done by drawing each line that borders the range of permissible values for one restriction. To begin, note that the non-negativity restrictions x1  0 and x2  0 require ( x1 , x2 ) to lie on the positive side of the axes (including actually on either axis), i.e., in the first quadrant. Next, observe that the restriction x1  4 means that ( x1 , x2 ) cannot lie to the right of the line x1  4. 29 These results are shown in the figure below, where the shaded area contains the only values of ( x1 , x2 ) that are still allowed. Figure 1 In a similar fashion, the restriction 2 x2  12 (or equivalently x2  6 ) implies that the line 2 x2 = 12 should be added to the boundary of the permissible region. The final restriction 3x1 + 2 x2  18 , requires plotting the points ( x1 , x2 ) such that 3x1 + 2 x2 = 18 (another line) to complete the boundary. (Note that the points such that 3x1 + 2 x2  18 are those that lie either underneath or on the line 3x1 + 2 x2 = 18 , so this is the limiting line above which points do not satisfy the inequality.) The resulting region of permissible values of ( x1 , x2 ) , called the feasible region, is shown in Figure 2 below. 30  Figure 2 The final step is to pick out the point in this feasible region that maximizes the value of Z = 3x1 + 5 x2. To discover how to perform this step efficiently, begin by trial and error. Try, for example, Z = 10 = 3x1 + 5 x2 to see if there are in the permissible region any values of ( x1 , x2 ) that yield a value of Z as large as 10. By drawing the line 3x1 + 5 x2 = 10 (see figure below), you can see that there are many points on this line that lie within the region. Having gained perspective by trying this arbitrarily chosen value of Z = 10 , you should next try a larger arbitrary value of Z, say, Z = 20 = 3x1 + 5 x2 31  Figure 3 Again, the figure above reveals that a segment of the line 3 x1 + 5 x2 = 20 lies within the region so that the maximum permissible value of Z must be at least 20. Now notice that the two lines just constructed are parallel. This is no coincidence since any line constructed in this way has the form Z = 3x1 + 5 x2 for the chosen value of Z, which implies that −3 1 5 x2 = −3x1 + Z or, equivalently, x2 = x1 + Z 5 5 This last equation, called the slope-intercept form of the objective function, demonstrates that the slope −3 −3 of the line is (since each unit increase in x1 changes x2 by ), whereas the intercept of the line with 5 5 1 1 −3 the x2 axis is Z (since x2 = Z when x1 = 0 ). The fact that the slope is fixed at means that all lines 5 5 5 constructed in this way are parallel. Again, comparing the Z = 10 = 3x1 + 5 x2 and Z = 20 = 3x1 + 5 x2 lines in the figure above., we note that the line giving a larger value of Z ( Z = 20 ) is farther up and away from the origin than the other line ( Z = 10 ). 32 This fact also is implied by the slope-intercept form of the objective function, which indicates that the 1  intercept with the x1 axis  Z  increases when the value chosen for Z is increased. 5  These observations imply that our trial-and-error procedure for constructing lines involves nothing more than drawing a family of parallel lines containing at least one point in the feasible region and selecting the line that corresponds to the largest value of Z. The above graph shows that this line passes through the point (2, 6), indicating that the optimal solution is x1 = 2 and x2 = 6. The equation of this line is 2 x1 + 5 x2 = 3 ( 2 ) + 5 ( 6 ) = 36 = Z , indicating that the optimal value of Z is Z = 36. The point (2, 6) lies at the intersection of the two lines 2 x2 = 12 and 3x1 + 2 x2 = 18 , shown in the graph above so that this point can be calculated algebraically as the simultaneous solution of these two equations. Using this approach, the optimal solution is x1 = 2 , x2 = 6 , with Z = 36. This solution indicates that the Glass Company should produce products 1 and 2 at the rate of 2 batches per week and 6 batches per week, respectively, with a resulting total profit of $36,000 per week. No other mix of the two products would be so profitable— according to the model Example 2.7 Maximize 3x1 + 2 x2 Subject to x1 + x2  80 2 x1 + x2  100 x1  40 x1 , x2  0 33  (a) Figure 4 (b) Having seen the trial-and-error procedure for finding the optimal point (2, 6) in example 2.6, you now can streamline this approach for other problems. Rather than draw several parallel lines, it is sufficient to form a single line with a ruler to establish the slope. Then move the ruler with a fixed slope through the feasible region in the direction of improving Z. (When the objective is to minimize Z, move the ruler in the direction that decreases Z.).Stop moving the ruler at the last instant that it still passes through a point in this region, as illustrated above. This point is the desired optimal solution. This procedure often is referred to as the graphical method for linear programming. It can be used to solve any linear programming problem with two decision variables. With considerable difficulty, it is possible to extend the method to three decision variables but not more than three. Example 2.8: Consider the product mix problem discussed in Example 2.1 Maximize 30 x1 + 40 x2 Subject to: 3x1 + 2 x2  600 3x1 + 5 x2  800 5 x1 + 6 x2  1100 34  x1  0; x2  0 The first step is to identify the values of ( x1 , x2 ) that are permitted by the restrictions. This is done by drawing each line that borders the range of permissible values for one restriction. To begin, note that the non-negativity restrictions x1  0; and x2  0 require ( x1 , x2 ) to lie on the positive side of the axes (including actually on either axis), i.e., in the first quadrant. From the constraints 3x1 + 2 x2  600 draw the line 3x1 + 2 x2 = 600 which passes through the point (200, 0) and (0, 300). This is shown in the following graph as line 1. Similarly, we have to determine the closed half-planes for the inequalities 3x1 + 5 x2  800 and 5 x1 + 6 x2  1100 (line 2 and line 3 in the graph). Since all the three constraints must be satisfied simultaneously, we have to consider the intersection of these three closed half-planes. The complete intersection of these three closed half-planes is shown in the graph below as ABCD. The region ABCD is called the feasible region, which is shaded in the graph. 35  Three closed half-planes and Feasible Region Example 2.9 In the previous example, we discussed the less than or equal to type of linear programming problem, i.e., maximization problem. Now consider a minimization (i.e., greater than or equal to type) linear programming problem formulated in Example 2.2. Minimize 2000 x1 + 1500 x2 Subject to: 6 x1 + 2 x2  8 2 x1 + 4 x2  12 4 x1 + 12 x2  24 x1  0; x2  0 The non-negativity restrictions x1  0; and x2  0 require ( x1 , x2 ) to lie on the positive side of the axes (including actually on either axis), i.e., in the first quadrant. The three lines 6 x1 + 2 x2 = 8 , 2 x1 + 4 x2 = 12 , and 4 x1 + 12 x2 = 24 passes through the point [(1.3,0), (0,4)], [(6,0), (0,3)] and [ (6,0) (0,2)]. The feasible region for this problem is shown in the Graph below. X2 36 In this problem, the constraints are greater than or equal to type of feasible region, which is bounded on one side only. a) Consider Example 2.7 Maximize 3x1 + 2 x2 Subject to x1 + x2  80 2 x1 + x2  100 x1  40 x1 , x2  0 37 The corner-point feasible (CPF) solutions are shown in figure 5 below. The optimal solution for the (CPF) is ( x1 , x2 ) = ( 20,60 ) Observe that this point is the intersection of two lines forming the boundary of the feasible region. Recall that lines we use to construct the feasible region come from inequalities (the points on the line satisfy the particular inequality with equality). Binding constraint: A constraint satisfied with equality. For solution (20, 60), the binding constraints are x1 + x2  80 and 2 x1 + x2  100 because 20 + 60 = 80 and 2 ( 20 ) + 60 = 100. The constraint x1  40 is not binding because x1 = 20 40. The constraint is binding because changing it (a little) necessarily changes the optimality of the solution. Any change to the binding constraints either makes the solution not optimal or not feasible. A constraint that is not binding can be changed (a little) without disturbing the optimality of the solution we found. Clearly, we can change x1  40 to x1  30 and the solution (20, 60) is still optimal. We shall discuss this more in-depth when we learn about Sensitivity Analysis. 2.6 Graphical Linear Programming Solution A two-variable linear programming problem can be easily solved graphically. The method is simple but the principle of the solution depends on certain analytical concepts, they are: i. Convex Region - A region R is convex if and only if for any two points on the region R, the line connecting those points lies entirely in the region R. 38  ii. Extreme Point - The extreme point E of a convex region R is a point such that it is not possible to locate two distinct points in R, so that the line joining them will include E. The extreme points are also called as corner points or vertices. Thus, the following result provides the solution to the linear programming model: "If the minimum or maximum value of a linear function defined over a convex region exists, then it must be on one of the extreme points". Every linear program has either i) a unique optimal solution, or ii) multiple (infinity) optimal solutions, or iii) is infeasible (has no feasible solution), or iv) is unbounded (no feasible solution is maximal). 2.6.1 relationship between optimal solutions and CPF solutions Consider any linear programming problem with feasible solutions and a bounded feasible region. The problem must possess CPF solutions and at least one optimal solution. Furthermore, the best CPF solution must be an optimal solution. Thus, if a problem has exactly one optimal solution, it must be a CPF solution. If the problem has multiple optimal solutions, at least two must be CPF solutions. In this section, we are going to describe linear programming graphical solutions for both the maximization and minimization problems discussed in Examples 2.8 and 2.9. Example 2. 10: Consider the maximization problem described in Example 2.8. Maximize 30 x1 + 40 x2 Subject to: 3x1 + 2 x2  600 3x1 + 5 x2  800 5 x1 + 6 x2  1100 x1  0; x2  0 The feasible region identified in Example 2.6 is a convex polygon, which is illustrated in the graph below. The extreme point of this convex region are A, B, C, D and E. 39 X2 X1 0 50 100 150 200 250 In this problem, the objective function is 30 x1 + 40 x2. Let M be a parameter; the graph 30 x1 + 40 x2 = M is a group of parallel lines with a slope – 30/40 (making x2 the subject). Some of these lines intersect the feasible region and contain many feasible solutions, whereas the other lines miss and contain no feasible solution. In order to maximize the objective function, we find the line of this family that intersects the feasible region and is farthest out from the origin. Note that the farthest the line is from the origin, the greater will be the value of M. Observe that the line 30 x1 + 40 x2 = M passes through the point D, which is the intersection of the Lines 3x1 + 5 x2 = 800 and 5 x1 + 6 x2 = 1100 has the coordinates x1 = 170 and x2 = 40. Since D is the only feasible solution on this line, the solution is unique. The value of M is 6700, which is the objective function maximum value. The optimum value variables are x1 = 170 and x2 = 40. 40 The following Table 1 shows the calculation of the maximum value of the objective function. Coordinates Objective Function Extreme Point x1 x2 30 x1 + 40 x2 A 0 0 0 B 0 160 6400 C 110 70 6100 D 170 40 6700 E 200 0 6000 Example 2.11: Consider the minimization problem described in Example 2.9. Minimize 2000 x1 + 1500 x2 Subject to: 6 x1 + 2 x2  8 2 x1 + 4 x2  12 4 x1 + 12 x2  24 x1  0; x2  0 The feasible region for this problem is illustrated in the following graph below. 41 X2 Here each of the half-planes lies above its boundary. In this case, the feasible region is infinite. In this case, we are concerned with the minimization; also, it is not possible to determine the maximum value. As in the previous example, let us introduce a parameter M in the objective function, i.e., 2000 x1 + 1500 x2 = M and draw the lines for different values of M, which is shown in the following Table 2. Coordinates Objective Function Extreme Point x1 x2 2000 x1 + 1500 x2 A 0 4 6000 B 0.5 2.75 5125 C 6 0 12000 The minimum value is 5125 at extreme point B, which is the value of M (objective function). The optimum values variables are x1 = 0.5 and x2 = 2.75. 2.6.2 Multiple Optimal Solutions When the objective function passed through only the extreme point located at the intersection of two half-planes, then the linear programming problem possesses unique solutions. All the previous linear programming examples are of this type (which possessed unique solutions). 42  When the objective function coincides with one of the half-planes generated by the constraints in the problem, it will possess multiple optimal solutions. In this section, we are going to discuss the multiple optimal solutions of linear programming problems with the help of the following Examples. Example 2.12: a) The Glass Company problem would have multiple optimal solutions if the objective function were changed to Z = 3x1 + 2 x2. b) A company purchasing scrap material has two types of scarp materials available. The first type has 30% of material X, 20% of material Y, and 50% of material Z by weight. The second type has 40% of material X, 10% of material Y and 30% of material Z. The costs of the two scraps are Le120 and Le160 per kg, respectively. The company requires at least 240 kg of material X, 100 kg of material Y, and 290 kg of material Z. Find the optimum quantities of the two scraps to be purchased so that the company requirements of the three materials are satisfied at a minimum cost. Solution First, we have to formulate the linear programming model. Let us introduce the decision variables x1 and x2 denoting the amount of scrap material to be purchased. Here the objective is to minimize the purchasing cost. So, the objective function here is 43  Minimize 120 x1 + 160 x2 Subject to: 0.3x1 + 0.4 x2  240 0.2 x1 + 0.1x2  100 0.5 x1 + 0.3x2  290 x1  0 , x2  0 Multiplying the constraints by 10 gives the following inequalities, then the problem becomes Minimize 120 x1 + 160 x2 Subject to: 3x1 + 4 x2  2400 2 x1 + x2  1000 5 x1 + 3x2  2900 x1  0 , x2  0 The graph for this problem is illustrated below. X2 X1 44 Let us introduce a parameter M in the objective function i.e. 120 x1 + 160 x2 = M. Then we have to determine the different values for M, which is shown in the following table below. Coordinates Objective Function Extreme Point X1 X2 120 x1 + 160 x2 A 0 1,000 160,000 B 150 740 136,400 C 400 300 96,000 D 800 0 96,000 Note that there are two minimum values for the objective function ( M = 96,000 ). The extreme points are A, B, C, and D. One of the objective functions 120 x1 + 160 x2 = M family coincides with the line CD at point C with value M = 96, 000 , and the optimum value variables are x1 = 400 and x2 = 300. And at point D with value M = 96, 000 , and the optimum value variables x1 = 800 and x1 = 0. Thus, every point on the line CD minimizes objective function value, and the problem contains multiple optimal solutions. 2.7.3 Unbounded Solution When the feasible region is unbounded, a maximization problem may not have an optimal solution since the values of the decision variables may be increased arbitrarily. This is illustrated with the help of the following problems. Example 2.13 a) The Glass Company problem (Example 2.6) would have no optimal solutions if the only functional constraint were x1  4 because x2 then could be increased indefinitely in the feasible region without ever reaching the maximum value of Z = 3x1 + 5 x2 45  b) Consider the linear programming problem Maximize 3x1 + x2 Subject to: x1 + x2  6 − x1 + x2  6 − x1 + 2 x2  −6 x1 , x2  0 Graph 6 shows the unbounded feasible region and demonstrates that the objective function Z = 3 x1 + x2 can be made arbitrarily large by increasing the values of x1 and x2 within the unbounded feasible region. In this case, there is no point ( x1 , x2 ) that is optimal because there are always other feasible points for which the objective function is larger. Note that it is not the unbounded feasible region alone that precludes an optimal solution. The minimization of the function subject to the constraints shown in the Graph 6 would be solved at one of the extreme point (A or B). 46 The unbounded solutions typically arise because some real constraints, which represent a practical resource limitation, have been missed from the linear programming formulation. In such situation the problem needs to be reformulated and re-solved. 2.6.4 Infeasible Solution A linear programming problem is said to be infeasible if no feasible solution to the problem exists. This section describes an infeasible solution to the linear programming problem with the help of the following examples. Example 2.14 a) The Glass Company problem (Example 2.6) would have no feasible solutions if the constraint 3 x1 + 5 x2  50 were added to the problem. b) Consider the linear programming problem Minimize 200 x1 + 300 x2 Subject to: 0.4 x1 + 0.6 x2  240 0.2 x1 + 0.2 x2  80 0.4 x1 + 0.3x2  180 x1 , x2  0 47 On multiplying both sides of the inequalities by 10, we get 4 x1 + 6 x2  2400 2 x1 + 2 x2  800 4 x1 + 3x2  1800 x1 , x2  0 The region right of the boundary AFE includes all the solutions which satisfy the first ( 4 x1 + 6 x2  2400 ) and third ( 4 x1 + 3x2  1800 ) constraints. The region left of the BC contains all solutions which satisfy the second constraint ( 2 x1 + 2 x2  800 ). Hence, there is no solution satisfying all three constraints (first, second, and third) simultaneously. Thus, the linear problem is infeasible. 48