O P E R A T I O N S R E S E A R C HDr.Vikrama D K Professor Department of MBA PESITM, ShivamoggaPREPARED BYM B A 2 0 4
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 1 OPERATIONS RESEARCH MODULE-I Introduction: Evolution of OR, Definitions of OR, Scope of OR, Applications of OR, Phases in OR, Characteristics and limitations of OR, models used in OR, Quantitative approach to decision making models (Theory Only) 1.1 … Introduction to OR Optimisation is the act of obtaining the best result under given circumstances. We come across many practical situations in which optimisation is observed. For example, suppose we are dealing with problems involving costs and want to minimise a cost. Then the least value of the cost is nothing but the optimised value. Similarly, maximisation of profit is the optimisation of profit. Further, suppose that different jobs are to be assigned to different persons and only one job is to be given to one person. We know that every person will complete each job in different times. Then the optimal solution is to assign each job to a person in such a way that the total time taken in completing all the jobs is the least. “Operation‟ implies some action applied in any area of interest. „Research‟ means some organised process of getting and analysing information about the problem environment. The term Operations Research came into existence and gained prominence during the Second World War when military planners were faced with logistical tasks requiring prompt and effective solutions. Hence, a group of scientists with diverse educational backgrounds including mathematics, statistics and physics became involved in applying a scientific approach to deal with strategic and tactical problems of various military operations. This initial research on military operations soon found applications in other decision making problems in business and industry. Hence, the word „military‟ was dropped and it was named as „Operations Research‟. In India, Operations Research came into existence in 1949 with the opening of an Operations Research unit at the Regional Research Laboratory in Hyderabad and also in the Defence Science Laboratory. 1.2 … Evolution of OR It is generally agreed that operations research came into existence as a discipline during World War II when there was a critical need to manage scarce resources. However, a particular model and technique of OR can be traced back as early as in World War I, when
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 2 Thomas Edison (1914–15) made an effort to use a tactical game board for finding a solution to minimize shipping losses from enemy submarines, instead of risking ships in actual war conditions. About the same time AK Erlang, a Danish engineer, carried out experiments to study the fluctuations in demand for telephone facilities using automatic dialling equipment. Such experiments were later on used as the basis for the development of the waiting-line theory. Since World War II involved strategic and tactical problems that were highly complicated, to expect adequate solutions from individuals or specialists in a single discipline was realistic. Thus, groups of individuals who were collectively considered specialists in mathematics, economics, statistics and probability theory, engineering, behavioural, and physical science, were formed as special units within the armed forces, in order to deal with strategic and tactical problems of various military operations. Such groups were first formed by the British Air Force and later the American armed forces formed similar groups. One of the groups in Britain came to be known as Blackett’s Circus. This group, under the leadership of Prof. P M S Blackett was attached to the Radar Operational Research unit and was assigned the problem of analyzing the coordination of radar equipment at gun sites. Following the success of this group similar mixed-team approach was also adopted in other allied nations. After World War II, scientists who had been active in the military OR groups made efforts to apply the operations research approach to civilian problems related to business, industry, research, etc. The following three factors are behind the appreciation for the use of operations research approach: (i) The economic and industrial boom resulted in mechanization, automation and decentralization of operations and division of management functions. This industrialization resulted in complex managerial problems, and therefore the application of operations research to managerial decision making became popular. (ii) Continued research after war resulted in advancements in various operations research techniques. In 1947, G B Dantzig, developed the concept of linear programming, the solution of which is found by a method known as simplex method. Besides linear programming, many other techniques of OR, such as statistical quality control, dynamic programming, queuing theory and inventory theory were well-developed before 1950’s.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 3 (iii) The use of high speed computers made it possible to apply OR techniques for solving real- life decision problems. During the 1950s, there was substantial progress in the application of OR techniques for civilian problems along with the professional development. Many colleges/schools of engineering, public administration, business management, applied mathematics, computer science, etc. Today, however, service organizations such as banks, hospitals, libraries, airlines, railways, etc., all recognize the usefulness of OR in improving efficiency. In 1948, an OR club was formed in England which later changed its name to the Operational Research Society of UK. Its journal, OR Quarterly first appeared in 1950. The Operations Research Society of America (ORSA) was founded in 1952 and its journal, Operations Research was first published in 1953. In the same year, The Institute of Management Sciences (TIMS) was founded as an international society to identify, extend and unify scientific knowledge pertaining to management. Its journal, Management Science, first appeared in 1954. In India, during same period, Prof R S Verma set up an OR team at Defence Science Laboratory for solving problems of store, purchase and planning. In 1953, Prof P C Mahalanobis established an OR team in the Indian Statistical Institute, Kolkata for solving problems related to national planning and survey. The OR Society of India (ORSI) was founded in 1957 and it started publishing its journal OPSEARCH 1964 onwards. In the same year, India along with Japan, became a member of the International Federation of Operational Research Societies (IFORS) with its headquarters in London. The other members of IFORS were UK, USA, France and West Germany. A year later, project scheduling techniques – Program Evaluation and Review Technique (PERT) and Critical Path Method (CPM) were developed for scheduling and monitoring lengthy, complex and expensive projects of that time. The American Institute for Decision Sciences came into existence in 1967. It was formed to promote, develop and apply quantitative approach to functional and behavioural problems of administration. It started publishing a journal, Decision Science, in 1970. Because of OR’S multi-disciplinary approach and its application in varied fields, it has a bright future, provided people devoted to the study of OR help to meet the needs of society. Some of the problems in the area of hospital management, energy conservation, environmental pollution, etc., have been solved by OR
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 4 specialists. This is an indication of the fact that OR can also contribute towards the improvement of the social life and of areas of global need. 1.3 … Definitions of Operations Research “Operations research is the application of the methods of science to complex problems in the direction and management of large systems of men, machines, materials and money in industry, business, government and defence. The distinctive approach is to develop a scientific model of the system incorporating measurements of factors such as chance and risk, with which to predict and compare the outcomes of alternative decisions, strategies or controls. The purpose is to help management in determining its policy and actions scientifically.” – Operational Research Society, UK “The application of the scientific method to the study of operations of large complex organizations or activities. It provides top level administrators with a quantitative basis for decisions that will increase the effectiveness of such organizations in carrying out their basic purposes.” – Committee on OR National Research Council, USA “Operations research is a scientific approach to problem-solving for executive management.” – H M Wagner “Operations research is the art of finding bad answers to problems which otherwise have worse answers.” - T.L.Saaty , Univof Pittsburg “Operations research is the art of winning wars without actually fighting them.” – Aurther Clarke. “O.R. 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”- Morse and Kimball 1.4 … Scope of OR O.R. has a wide scope in everyday life as it provides better solutions to various decision- making problems with great speed and competence. It finds applications in a wide range of areas including defence operations, planning, agriculture, industry (finance, marketing, personal management, production management), research and development. We now describe the applications briefly
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 5 In Defence Operations Since the Second World War, Operations Research techniques have been used for defence operations with the objective of getting maximum gains with minimum effort. It has been used for coordinating various activities of Air Force, Army and Navy. Decisions regarding formulation and selection of strategies of the various available courses of action are taken by a team of scientists. In Planning for Economic Development Careful planning is necessary for economic development of any country. Operations Research is used to frame future economic and social policies. In Agriculture Agricultural output needs to be increased due to increasing needs for adequate quantity and quality of food for our increasing population. But there are a number of restrictions under which agricultural production is studied. Problems of agricultural production under various restrictions such as optimum allocation of land to various crops in accordance with the climatic conditions, optimum distribution of water from various resources for irrigation purposes can easily be solved by application of Operations Research techniques. In Industry Now-a-days, due to complexities of operations and huge sizes of industries, important decisions regarding various sections of the organisation, e.g., planning, procurement, marketing, finance, etc. have to be taken division wise. For example, the production department needs to minimise the cost of production, but maximise output; the finance department needs to optimise capital investment; the personnel department needs to appoint competent work force at minimum cost. Each department has to plan its own objectives which may be in conflict with the objectives of other departments and may not conform to the overall objectives of the organisation. For example, the sales department of an organisation may want to keep sufficient stocks in the inventory, whereas the finance department may want to have minimum investment. In that case, both departments would be in conflict with each other. The applications of O.R. techniques to such situations help in overcoming this difficulty by evolving an optimal strategy and serving efficiently the interest
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 6 of the organisation as a whole. Some of the problems faced by various divisions of an industry, which can be solved by the application of Operations Research techniques are as follows: Finance department of an organisation needs to optimise capital investment, determine optimal replacement strategies, apply cash flow analysis for long range capital investments, formulate credit policies, credit risks, breakeven analysis. All these can be attained by applying Operations Research techniques. The marketing department of any organisation has to face various problems like product selection, formulation of competitive strategies, sales forecasting, distribution strategies, selection of advertising media with respect to cost and time, finding the optimal number of salesmen, finding optimum time to launch a product. All such problems can be overcome using Operations Research methods. Personnel Management of an organisation needs to find the best combination of workers in different categories with respect to costs, skills, age and nature of jobs. It also needs to forecast the work force requirement, frame recruitment policies, assign jobs to machines or workers, negotiate in a bargaining situation, etc. This can be achieved very easily by the application of Operations Research techniques. Problems related to production management of an organisation, i.e., determination of the optimal product mix, selection of the location and design of the sites for production plant, scheduling and sequencing the production run by proper allocation of machines, location and size of warehouse/new plant, etc. can very easily be solved by applying Operations Research techniques. In Research and Development Operations Research helps in planning and control of new research and development projects. It also helps in planning the launch of new products. Operations Research helps in solving many other problems faced by public as well as private sectors such as the ones in economic and social planning, management of natural resources, energy, housing, pollution control, waiting lines and administrative problems, insurance policies, and many more. 1.5 … Applications of OR Some of the industrial/government/business problems that can be analysed by the OR approach have been arranged by functional areas as follows:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 7 Finance and Accounting • Dividend policies, investment and portfolio management, auditing, balance sheet and cash flow analysis • Break-even analysis, capital budgeting, cost allocation and control, and financial planning • Claim and complaint procedure, and public accounting • Break-even analysis, capital budgeting, cost allocation and control, and financial planning • Establishing costs for by-products and developing standard costs Marketing • Selection of product-mix, marketing and export planning • Sales effort allocation and assignment • Launching a new product at the best possible time • Advertising, media planning, selection and effective packing alternatives • Predicting customer loyalty Purchasing, Procurement and Exploration • Optimal buying and reordering with or without price quantity discount • Transportation planning • Replacement policies • Bidding policies • Vendor analysis Personnel Management • Manpower planning, wage/salary administration • Negotiation in a bargaining situation • Skills and wages balancing • Scheduling of training programmes to maximize skill development and retention • Designing organization structures more effectively Government • Economic planning, natural resources, social planning and energy
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 8 • Urban and housing problems • Military, police, pollution control, etc 1.6 … Phases in OR The operations research approach to problem solving is based on three phases, namely (i) Judgement Phase; (ii) Research Phase, and (iii) Action Phase. Judgement phase This phase includes: (i) identification of the real-life problem, (ii) selection of an appropriate objective and the values of various variables related to this objective, (iii) application of the appropriate scale of measurement, i.e. deciding the measures of effectiveness (desirability), and (iv) formulation of an appropriate model of the problem and the abstraction of the essential information, so that a solution to the decision-maker’s goals can be obtained. Research phase This phase is the largest and longest amongst all the phases. However, even though the remaining two are not as long, they are also equally important as they provide the basis for a scientific method. This phase utilizes: (i) observations and data collection for a better understanding of the problem, (ii) formulation of hypothesis and model, (iii) observation and experimentation to test the hypothesis on the basis of additional data, (iv) analysis of the available information and verification of the hypothesis using pre-established measures of desirability, (v) prediction of various results from the hypothesis, and (iv) generalization of the result and consideration of alternative methods. Action phase This phase consists of making recommendations for implementing the decision. This decision is implemented by an individual who is in a position to implement results. This individual must be aware of the environment in which the problem occurred, be aware of the objective, of assumptions behind the problem and the required omissions of the model. 1.7 … Characteristics of OR Essential characteristics Three essential characteristics of operations research are a systems orientation, the use of interdisciplinary teams, and the application of scientific method to the conditions under which the research is conducted.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 9 Systems orientation The systems approach to problems recognizes that the behaviour of any part of a system has some effect on the behaviour of the system as a whole. Even if the individual components are performing well, however, the system as a whole is not necessarily performing equally well. For example, assembling the best of each type of automobile part, regardless of make, does not necessarily result in a good automobile or even one that will run, because the parts may not fit together. It is the interaction between parts, and not the actions of any single part, that determines how well a system performs. Thus, operations research attempts to evaluate the effect of changes in any part of a system on the performance of the system as a whole and to search for causes of a problem that arises in one part of a system in other parts or in the interrelationships between parts. In industry, a production problem may be approached by a change in marketing policy. For example, if a factory fabricates a few profitable products in large quantities and many less profitable items in small quantities, long efficient production runs of high-volume, high-profit items may have to be interrupted for short runs of low-volume, low-profit items. An operations researcher might propose reducing the sales of the less profitable items and increasing those of the profitable items by placing salesmen on an incentive system that especially compensates them for selling particular items The interdisciplinary team Scientific and technological disciplines have proliferated rapidly in the last 100 years. The proliferation, resulting from the enormous increase in scientific knowledge, has provided science with a filing system that permits a systematic classification of knowledge. This classification system is helpful in solving many problems by identifying the proper discipline to appeal to for a solution. Difficulties arise when more complex problems, such as those arising in large organized systems, are encountered. It is then necessary to find a means of bringing together diverse disciplinary points of view. Furthermore, since methods differ among disciplines, the use of interdisciplinary teams makes available a much larger arsenal of research techniques and tools than would otherwise be available. Hence,
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 10 operations research may be characterized by rather unusual combinations of disciplines on research teams and by the use of varied research procedures. Methodology Until the 20th century, laboratory experiments were the principal and almost the only method of conducting scientific research. But large systems such as are studied in operations research cannot be brought into laboratories. Furthermore, even if systems could be brought into the laboratory, what would be learned would not necessarily apply to their behaviour in their natural environment, as shown by early experience with radar. Experiments on systems and subsystems conducted in their natural environment (“operational experiments”) are possible as a result of the experimental methods developed by the British statistician R.A. Fisher in 1923–24. For practical or even ethical reasons, however, it is seldom possible to experiment on large organized systems as a whole in their natural environments. This results in an apparent dilemma: to gain understanding of complex systems experimentation seems to be necessary, but it cannot usually be carried out. This difficulty is solved by the use of models, representations of the system under study. Provided the model is good, experiments (called “simulations”) can be conducted on it, or other methods can be used to obtain useful results. 1.8 … Advantages of Operations Research Better Systems: Often, an O.R. approach is initiated to analyze a particular problem of decision making such as best location for factories, whether to open a new warehouse, etc. It also helps in selecting economical means of transportation, jobs sequencing, production scheduling, replacement of old machinery, etc. Better Control: The management of large organizations recognize that it is a difficult and costly affair to provide continuous executive supervision to every routine work. An O.R. approach may provide the executive with an analytical and quantitative basis to identify the problem area. The most frequently adopted applications in this category deal with production scheduling and inventory replenishment.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 11 Better Decisions: O.R. models help in improved decision making and reduce the risk of making erroneous decisions. O.R. approach gives the executive an improved insight into how he makes his decisions. Better Co-ordination: An operations-research-oriented planning model helps in co- ordinating different divisions of a company. 1.9 … Limitations of Operations Research Dependence on an Electronic Computer: O.R. techniques try to find out an optimal solution taking into account all the factors. In the modern society, these factors are enormous and expressing them in quantity and establishing relationships among these require voluminous calculations that can only be handled by computers. Non-Quantifiable Factors: O.R. techniques provide a solution only when all the 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 O.R. models. Distance between Manager and Operations Researcher: O.R. being specialist's job requires a mathematician or a statistician, who might not be aware of the business problems. Similarly, a manager fails to understand the complex working of O.R. Thus, there is a gap between the two. Money and Time Costs: When the basic data are subjected to frequent changes, incorporating them into the O.R. models is a costly affair. Moreover, a fairly good solution at present may be more desirable than a perfect O.R. solution available after sometime. Implementation: Implementation of decisions is a delicate task. It must take into account the complexities of human relations and behaviour. 1.10 …Models used in OR A MODEL is a representation of the reality. Most of our thinking of operations research in business take place in the context of models. The objective of model is not to identify all aspects of the situation but to identify significant factors and their intre- relationship. A major advantage of modelling is that it permits the decision maker to examine the behaviour of a system without interfering with as going operations. Classification Based on Structure • Physical models
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 12 o Iconic Models o Analogue Models • Symbolic models o Verbal Models o Mathematical Models Classification Based on Function (or Purpose) • Descriptive models • Predictive models • Normative (or Optimization) models Classification Based on Time Reference • Static models • Dynamic models Classification Based on Degree of Certainty • Deterministic models • Probabilistic (Stochastic) models Classification Based on Method of Solution or Quantification • Heuristic models • Analytical models • Simulation models Classification Based on Structure Physical models These models are used to represent the physical appearance of the real object under study, either reduced in size or scaled up. Physical models are useful only in design problems because they are easy to observe, build and describe. For example, in the aircraft industry, scale models of a proposed new aircraft are built and tested in wind tunnels to record the stresses experienced by the air frame. Physical models cannot be manipulated and are not very useful for prediction. Problems such as portfolio selection, media selection, production scheduling, etc., cannot be analysed with the help of these models. Physical models are classified into two categories. (i) Iconic Models An iconic model is a scaled (small or big in size) version of the system. Such models retain some of the physical characteristics of the system they represent.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 13 Examples of iconic model are, blueprints of a home, maps, globes, photographs, drawings, air planes, trains, etc. An iconic model is used to describe the characteristics of the system rather than explaining the system. This means that such models are used to represent system’s characteristics that are not used in determining or predicting effects that take place due to certain changes in the actual system. For example, (i) colour of an atom does not play any vital role in the scientific study of its structure, (ii) type of engine in a car has no role to play in the study of the problem of parking, etc. (ii) Analogue Models An analogue model does not resemble physically the system they represent, but retain a set of characteristics of the system. Such models are more general than iconic models and can also be manipulated. For example, (i) oil dipstick in a car represents the amount of oil in the oil tank; (ii) organizational chart represents the structure, authority, responsibilities and relationship, with boxes and arrows; (iii) maps in different colours represent water, desert and other geographical features, (iv) Graphs of time series, stockmarket changes, frequency curves, etc., represent quantitative relationships between any two variables and predict how a change in one variable effects the other, and so on. Symbolic models These models use algebraic symbols (letters, numbers) and functions to represent variables and their relationships for describing the properties of the system. Such relationships can also be represented in a physical form. Symbolic models are precise and abstract and can be analysed by using laws of mathematics. Symbolic models are classified into two categories. (i) Verbal Models These models describe properties of a system in written or spoken language. Written sentences, books, etc., are examples of a verbal model. (ii) Mathematical Models These models use mathematical symbols, letters, numbers and mathematical operators (+, –, ÷, ×) to represent relationships among variables of the system to describe its properties or behaviour. The solution to such models is obtained by applying suitable mathematical technique. Few examples of mathematical model are (i) The relationship among velocity, distance and acceleration, (ii) The relationship among cost-volume-profit, etc. Classification Based on Function (or Purpose)
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 14 Descriptive models These models are used to investigate the outcomes or consequences of various alternative courses of action (strategies, or actions). Since these models evaluate the consequence based on a given condition (or alternative) rather than on all other conditions, there is no guarantee that an alternative selected is optimal. These models are usually applied (i) in decision-making where optimization models are not applicable, and (ii) when objective is to define the problem or to assess its seriousness rather than to select the best alternative. These models are especially used for predicting the behaviour of a particular system under various conditions. Simulation is an example of a descriptive model for conducting experiments with the systems based on given alternatives. Predictive models These models represent a relationship between dependent and independent variables and hence measure ‘cause and effect’ due to changes in independent variables. These models do not have an objective function as a part of the model of evaluating decision alternatives based on outcomes or pay off values. Also, through such models decision-maker does not attempt to choose the best decision alternative, but can only have an idea about the possible alternatives available to him. For example, the equation S = a + bA + cI relates dependent variable (S) with other independent variables on the right hand side. This can be used to describe how the sale (S) of a product changes with a change in advertising expenditure (A) and disposable personal income (I ). Here, a, b and c are parameters whose values must be estimated. Thus, having estimated the values of a, b and c, the value of advertising expenditure (A) can be adjusted for a given value of I, to study the impact of advertising on sales. Also, through such models decision-maker does not attempt to choose the best decision alternative, but can only have an idea about the possible alternative available to him. Normative (or Optimization) models These models provide the ‘best’ or ‘optimal’ solution to problems using an appropriate course of action (strategy) subject to certain limitations on the use of resources. For example, in mathematical programming, models are formulated for optimizing the given objective function, subject to restrictions on resources in the context of the problem under consideration and non-negativity of variables. These models are also called prescriptive models because they prescribe what the decision maker ought to do. Classification Based on Time Reference
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 15 Static models Static models represent a system at a particular point of time and do not take into account changes over time. For example, an inventory model can be developed and solved to determine an economic order quantity assuming that the demand and lead time would remain same throughout the planning period. Dynamic models Dynamic models take into account changes over time, i.e., time is considered as one of the variables while deriving an optimal solution. Thus, a sequence of interrelated decisions over a period of time are made to select the optimal course of action in order to achieve the given objective. Dynamic programming is an example of a dynamic model. Classification Based on Degree of Certainty Deterministic models If all the parameters, constants and functional relationships are assumed to be known with certainty when the decision is made, the model is said to be deterministic. Thus, the outcome associated with a particular course of action is known, i.e. for a specific set of input values, there is only one output value which is also the solution of the model. Linear programming models are example of deterministic models. Probabilistic (Stochastic) models If at least one parameter or decision variable is random (probabilistic or stochastic) variable, then the model is said to be probabilistic. Since at least one decision variable is random, the independent variable, which is the function of dependent variable(s), will also be random. This means consequences (or payoff) due to certain changes in the independent variable(s) cannot be predicted with certainty. However, it is possible to predict a pattern of values of both the variables by their probability distribution. Insurance against risk of fire, accidents, sickness, etc., are examples where the pattern of events is studied in the form of a probability distribution. Classification Based on Method of Solution or Quantification Heuristic models If certain sets of rules (may not be optimal) are applied in a consistent manner to facilitate solution to a problem, then the model is said to be Heuristic. Analytical models These models have a specific mathematical structure and thus can be solved by the known analytical or mathematical techniques. Any optimization model (which requires maximization or minimization of an objective function) is an analytical model.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 16 Simulation models These models have a mathematical structure but cannot be solved by the known mathematical techniques. A simulation model is essentially a computer-assisted experimentation on a mathematical structure of a problem in order to describe and evaluate its behaviour under certain assumptions over a period of time. Simulation models are more flexible than mathematical models and can, therefore, be used to represent a complex system that cannot be represented mathematically. These models do not provide general solution like those of mathematical models 1.11 … Quantitative approach to decision making models 1. Mathematical Programming 2. Cost Analysis (Break-Even Analysis) 3. Cost-Benefit Analysis 4. Linear Programming 5. Capital Budgeting 6. Inventory Management 7. Expected Value 8. Decision Tree 9. Simulation 10. Queuing or Waiting Line Theory 11. Game Theory 12. Information Theory 13. Preference Theory/Utility Theory 14. Few Others Various quantitative techniques for decision making are:- 1. Mathematical Programming 2. Cost Analysis (Break-Even Analysis) 3. Cost-Benefit Analysis 4. Linear Programming
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 17 5. Capital Budgeting 6. Inventory Management 7. Expected Value 8. Decision Tree 9. Simulation 10. Queuing or Waiting Line Theory 11. Game Theory 12. Information Theory 13. Preference Theory/Utility Theory and Few Others. Technique # 1. Mathematical Programming: Besides the calculus, there are other management science techniques which can be employed to resolve a variety of decision problems. One such technique is Mathematical Programming which is useful whenever several factors constrain the choice of strategies. Consider the inventory problem. If the objective is simply to minimize total cost, there are no constraints which limit our choice of strategies. If there are constraints, they might limit either the space in which inventory can be placed, the funds which can be spent on inventory, or the maximum number of orders that can be placed by the purchasing department. This being the case, it would have become a problem in constrained minimization and mathematical programming techniques could be used to find a solution. The constraints create the environment within which decision makers strive to maximize or minimize the objectives to be achieved. This is the essence of mathematical programming: Constrained maximization or minimization. It becomes an intuitively appealing framework for the analysis of many types of business problems. The difficult task, however, is shouldered by the model builder, who must abstract from the environment those important elements that are to be incorporated in the mathematical model. Linear programming techniques such as Simplex method, graphical method etc., make the mathematical models to solve them. Technique # 2. Cost Analysis (Break-Even Analysis):
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 18 Managers want to make money. The objective of the break-even analysis is to decide the optimum break-even point, that is, where profits will be highest. In making decisions, managers must pay a great deal of attention to the profit opportunities of alternative courses of action. This obviously requires that the cost implications of those alternatives are assessed. An important aspect of such cost analysis is that made between fixed and variable costs. A cost can be classified as being fixed or variable in relation to changes in the level of activity within a given period. (In the long run, of course, all costs are variable). Fixed costs are those which remain fixed irrespective of the volume of production or sales. For example, a managing director’s salary will not vary (change) with the volume of goods produced during any year. Road tax payable for a car will not vary with its annual mileage covered. Insurance premiums, rent charges, R&D costs are a few other typical examples of fixed costs. Variable costs vary or change in response to changes in, say, volume of production or sales or any other similar activity. Sales commissions in relation to sales levels, petrol costs in relation to miles travelled and labour, costs in relation to hours worked are obvious examples. Mixed costs are of hybrid nature, being partly fixed and partly variable. An example is found in telephone charges – the rental element is a fixed cost, whereas charges for calls made are a variable cost. Separating fixed and variable costs. The total cost at any level of operations is the sum of a fixed cost component and a variable cost component. The importance of separating variable costs from fixed costs stems from the different behaviour patterns of each, which have a significant bearing on their control. Variable Costs must be controlled in relation to the level of activity, whilst fixed costs must be controlled in relation to time. From a decision-making point of view, it is also important to know whether or not a particular cost will vary as a result of a given decision. By adding graphically variable cost to the fixed cost for different levels of activity (e.g. number of goods produced), a total cost curve can be drawn. If a revenue curve is super-imposed on the same graph (Fig. 18.2) the result is the break-even chart which depicts the profits/loss picture for several possible cost-revenue situations at different levels of activity.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 19 In particular, break-even analysis is useful as a background information device for reviewing overall cost and profit levels, but it can also be used in connection with special decisions such as selecting a channel of distribution or make or buy decisions. Technique # 3. Cost-Benefit Analysis: Cost-benefit analysis is a mathematical technique for decision-making. It is a quantitative technique used to evaluate the economic costs and the social benefits associated with a particular course of action. In this technique, an effort is made to identify all costs and benefits, not only those that may be expressed in rupees, but also the less easily calculated effects of a given decision. In general, this technique (which is fairly complicated) is advocated for use in decisions on public projects, in which social costs and social benefits as well as actual out-of-pocket costs should be taken into account. What counts as a benefit or loss to one part of the economy— to one or more persons or groups- does not necessarily count as a benefit or loss to the economy as a whole. And in cost-benefit analysis we are concerned with the economy as a whole, with the welfare of a defined society and not any smaller part of it. But cost-benefit analysis may also be applicable to a single company, for in many cases, it is advisable to place a value on costs and benefits that are not ordinarily expressed in rupees. Somewhat similar to cost-benefit analysis is the cost-effectiveness analysis, which is analysis to determine the least expensive way of reaching an objective or of obtaining the greatest possible value from a given expenditure. Technique # 4. Linear Programming: Linear programming is a quantitative technique used to determine the optimal mix of limited resources for maximizing profits or minimizing costs. Linear programming is an extension of break-even analysis that is very useful in analyzing complex problems. Linear programming involves the solution of linear equations and is appropriate when the manager must allocate scarce resources to competing projects. Technique # 5. Capital Budgeting: A manager relies heavily on linear programming when he allocates resources to competing projects. Similarly Capital budgeting provides a set of techniques a manager can use to
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 20 evaluate the relative attractiveness of various projects in which a lump payment is made to generate a stream of earnings over a future period. Examples of capita! budgeting projects include an investment in a new machine that will increase future profits by reducing costs, an investment of a sum of money into an advertising campaign to increase future sales (and profits) etc. In essence, capital budgeting techniques provide management with a useful method for analyzing the profitability of potential investments that have dissimilar earnings characteristics. Without these techniques, it would be nearly impossible to weigh the advantages of dissimilar investments. Technique # 6. Inventory Management: In quest to make money, a manager should employ his resources as efficiently as possible. Inventory management involves determining and controlling the amount of raw material an organization should keep in stock to operate effectively and efficiently. Efficient management of inventory requires balancing several conflicting goals. The first goal is 10 Keep inventories as small as possible to minimize the amount of warehouse space and the amount of money tied up in inventories. This goal is in conflict with the need to fill all customer requirements, to optimize the number of orders placed, and to take advantage of the economies of long production runs and quantity discounts. To solve inventory problems, the manager can use the economic order quantity (EOQ) model. This model can be expressed as a mathematical formula. The solution of EOQ formula tells the manager how many items he should purchase, and how often. Technique # 7. Expected Value: To understand expected value model, it is important to comprehend the concept of probability which refers to the likelihood that an event will happen. Mathematically, probability is expressed as a fraction or percentage. For example, there is a 30% (or 0.3) probability that it will rain tomorrow. Probabilities may be established empirically, by observing some phenomenon over time. When several courses of action are available and the outcome of each is uncertain, the decision maker can use probabilities to select his final choice. Taking an example:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 21 The sales of an air-conditioner will depend on how hot the summer is. The expected value for any event is the income it would produce times its probability. Adding the expected values of all possible events, yields expected sales, the average level of sales that can be expected over the long run if the given probabilities hold, as shown in table below. For the air-conditioner, expected sales for the summer are Rs. 7,300,000. Technique # 8. Decision Tree: Another increasingly useful tool for management decision-makers is the so called decision tree. This is basically a conceptual map of possible decisions and outcomes in a particular situation. It is useful in cases where a manager is required to make a number of sequential decisions i.e., where earlier decisions will affect later ones. Technique # 9. Simulation: Simulation techniques are especially applicable to what if problems, in which a manager or technician wants to know, If we do this, what will happen. Simulation can, of course, be conducted by the manipulation of physical models. For example, one might have a physical model of a machine and actually keep on increasing its speed to determine at what point it would begin to jam, fly apart or walk across the floor. With no loss, one may, instead, use a mathematical model in which each of the terms represents one of the variables, and observe the effect on the others when different values are given to one or more of the terms. With the help of a computer, it is possible to examine what will happen in an enormous number of cases-without spending a prohibitive amount of time. Because large electronic computers have become easily accessible in recent years, management can simulate complex situations in order to determine the best course of action. Simulation is the process of building, testing and operating models of real-world phenomena through the use of mathematical relationships that exist among critical factors. This technique is useful for solving complex problems that cannot be readily solved by other techniques. A simulation model can be deterministic if the manager knows exactly the value of the factors he employs in the equations. However, simulation is essentially probabilistic, since the manager typically must estimate the future values of these factors. Simulation is very helpful in engineering and design problems, where the medium may be either the mathematical model or a diagram on a screen (VDU)
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 22 connected to the computer. In the latter case, the engineer-designer can modify the design by using a light pen. The technique is equally applicable to management decision-making. It is obviously much cheaper, safer and easier to experiment with a mathematical model or diagrammatic simulator than to experiment with real machines or even physical models of machines. In some cases, however the variables that one manipulates are not exact quantities but probabilities. Then what are known as Monte Carlo techniques must be used. These make it possible to stretch as far as possible such few actual data as are available to begin with. Technique # 10. Queuing or Waiting Line Theory: Queuing theory is an O.R. technique which aids the manager in making decisions involving the establishment of service facilities to meet irregular demands. Cost problems arise when there are more service facilities available than are needed, or when too few facilities are available and consequently, long waiting lines form. For example, in a battery of machines, breakdowns will occur randomly, and whenever the maintenance service falls below that demanded by the breakdowns, a waiting line of unrepaired machines forms. This idle capacity is a cost that has to be balanced against the costs of keeping maintenance services available. Queuing theory is applied to any situation producing a need to balance the cost of increasing available service against the cost of letting units wait. To arrive at the best number of service facilities, the manager and the O.R. team must first determine (in the example above) the breakdown rate and the time required to service each machine. These data can then be used to construct a mathematical model of the problem, which can become extremely complex. Simulation methods are widely used to solve waiting line problems. Simulation is a systematic, trial and error procedure for solving waiting line & problems that are too complex for easy mathematical analysis. Reasonably good solutions may often be obtained by simulating important elements of the problem. A widely used method of simulating business problems in which events occur with assigned or computed probabilities is known as the Monte Carlo Method. This method utilizes the mathematics of probability, and is often run on the computer. Technique # 11. Game Theory: Game theory is a technique of operations research. This provides a basis for determining, under specified conditions, the particular strategy that will result in maximum gain or
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 23 minimum loss, no matter what opponents do or do not do. (An opponent would be the enemy general in military application, or a competitor in a business situation etc.) The simplest application of the game theory is the two-person, zero-sum game, in which there are only two players and one player can gain only at the expense of the other. These two conditions are generally fulfilled when two armies are opposing each other. In business they are fulfilled only in special cases. Assume, a company has only one competitor and the size of the market is fixed; thus every gain in sales by one company means an equal loss in sales for the other. In an expanding market, both the companies could gain, in a declining market, one could gain at the expense of the other. Game theory has the greatest practical usefulness in planning sales promotion strategies. A Company who wishes to increase its sales may do so by using one or more of such techniques as: (1) A reduction in product price, (2) An increase in number of salesmen, and (3) A rise in its advertising budget, The company must consider what the rival can do to nullify the effect of any of these techniques. The company therefore asks itself questions like these. Assuming we decide to increase our share of market by cutting prices, what will actually happen if: (a) Our rival also cuts prices, (b) He increases the number of his salesmen, (c) He raises his advertising budget or (d) He uses a combination of all three of these tactics? By evaluating each one of these possibilities, the company can ascertain the greatest possible damage the rival can inflict. This will reveal either the minimum gain the company is assured of or the maximum loss it can suffer. In real life, however, there are more than two competitors and the demand for most products is not stable or fixed. If all competitors cut prices, the market for all may be increased and possibly all may gain. Or, if the market remains the same, all may lose. Therefore the losses of one do not necessarily equal the gains of another.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 24 Game Models: The next quantitative decision making model consists of game models or competitive strategies. These models are derived from game theory which provides many useful insights into situations involving elements of competition. Decision situations are of a game nature when a rational opponent (e.g., a competitor in the market) is involved, so that resulting effects are dependent on the specific strategies selected by the decision maker and his opponent. This assumes that the opponent will carefully consider what the decision maker may do before he selects his own strategy. Technique # 12. Information Theory: A central element in all decision making is the process of obtaining, using and disseminating information. Information theory is a rigorous mathematical effort to solve problems in communication engineering. Since information theory deals with the flow of information and communication net-works, it has important implications for organization design and for man- machine relationships. Information theory provides a means of measuring the information content of both symbolic and verbal languages and relating the characteristics of an efficient communication system to the information content of messages transmitted. This body of theory has been of great use in the design of communication systems and computers. Technique # 13. Preference Theory/Utility Theory: One of the interesting and practical supplements of modern decision theory is (the work that has been done and) the techniques developed to supplement statistical probabilities with analysis of individual preferences in the assumption or avoidance of risk. While referred to here as preference theory, it is more classically denoted Utility theory. It might seem reasonable that if we had a 60% chance of a decision being the right one, we would take it. But this is not necessarily true, since the risk of being wrong is 40% and a manager might not wish to take this risk, particularly if the penalty for being wrong is severe, whether in terms of monetary losses, reputation or job security. If we doubt this, we might ask ourselves whether we would risk, say Rs. 40,000 on the 60% chance that we might make Rs. 100,000. We might readily risk Rs. 4 on a chance of making Rs. 10, and gamblers have been known to risk much more on a lesser chance of success. Therefore, in order to give probabilities practical meaning in decision making, we need better understanding of the individual decision
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 25 maker’s aversion to, or acceptance of risk. This varies not only with people but also with the size of the risk, with the level of managers in an organization and according to whether the funds involved are personal or belong to a company. Higher level managers are accustomed to taking larger risks than lower-level managers. The same top manager who may take a decision involving risks of millions of rupees for a company would not like to do that with his own personal fortune. Moreover, the same manager willing to opt for a 75% risk in one case might not be willing to, in another. For example, he may go for a large advertising program where the chances of success are 70%, but might not decide in favour of an investment in plant and machinery unless the probabilities for success were higher. In other words, attitudes toward risk vary with events, as well as with people and positions. Most of us are gamblers when small stakes are involved, but soon take on the role of risk averters when the stakes rise. Many managers are risk averters and thereby miss opportunities. Technique # 14. Heuristic Programming: Heuristic programming, sometimes called heuristic problem solving, is an approach to decision making that has gained increasingly wide usage in recent years. It is in fact a branch of simulation model analysis. It is applied to problems in such areas as assembly line balancing, plant layout, job shop scheduling, warehouse location and resource allocation. A heuristic is any device or procedure used to reduce problem-solving effort. A rule-of-thumb is a commonly used heuristic. For example, the rule that “when there are only ten parts in the bin, reorder the part” or “do not drink liquor and drive a car”, are examples of heuristics. Much business behaviour and much in everyday life is guided by this kind of rule. When heuristics are combined to solve a problem, a heuristic program is formed. Complex programs require computers for their solution. Heuristic programs are used wherever the problem is too large or too complex to solve by mathematical or statistical techniques. It is also used to deal with ill-structured problems that cannot be stated in mathematical terms, so that quantitative techniques (such as O.R.) are not suitable for such problems. The chief inputs in heuristic programming are subjective, based on the managers past experience,
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 26 the pooling of knowledge and judgments of colleagues, the use of judgment, intuition, creativity, learning processes and other qualitative variables. The decision maker immerses himself in the total problem, and searches by means of trial and error for a satisfactory solution in a reasonable time and at a reasonable cost, rather than striving for an optimal solution at all costs. Technique # 15. Decision Theory: Decision Theory may be defined as a set of general concepts and techniques that assist a decision maker in choosing among alternatives. Decision theory problems are commonly cast in a standard framework, termed a decision matrix which consists of the following components: (a) Strategies or alternatives (S), available to the decision maker. For example make and buy would be two strategies in a make-or-buy decision problem. Strategies are within the control of the decision maker. (b) States of nature (N), which are characteristics of the environment and are beyond the control of the decision maker. The term derives from the Weather, where we might observe, say, three states of nature: sunshine, rain or snow. In business decisions, states of nature might be various levels of demand for a product, the number of competitors, governmental actions etc. (c) Predictions of likelihood (Pr) or the probability associated with the occurrence of each state of nature. If a particular state of nature is sure to occur (Pr = 1.0), the decision situation is termed one of certainty. If the decision maker can assign probability of occurrence to one or more states of nature, with no one state given a value of 1.0, it is termed a risk situation. Finally, if the decision maker has no idea of the probabilities of occurrence of any state of nature, the situation is defined as decision making under uncertainty. Thus in the decision matrix above, there would be an entry for probability if the situation is one of certainty or risk and no entry if it is one of uncertainty. (d) Pay offs or outcomes (O), which represent the value associated with each combination of strategy and state of nature. The value may be stated in terms of utility, cost, profit, satisfaction etc.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 27 Solving a decision theory problem obviously requires some choice to be made from among the alternatives, and thus some rule or decision criterion must be selected for this purpose. For example, in certainty situations, the decision criterion is to select the single strategy with the highest pay off. Since only one state of nature is relevant, this entails a simple scanning of the payoff column under the certain N and picking the best one. Technique # 16. Cost Effectiveness Analysis: Cost effectiveness analysis is a decision making methodology that ultimately leads to a comparison of alternatives in terms of their costs and effectiveness in attaining some specific objective. It differs from conventional economic analysis in that it attempts to devise a quantitative criterion that can simultaneously measure both the quantitative and qualitative elements of a decision problem. Because its methodology permits analysis of alternatives with widely ranging physical and operational characteristics, it has been applied in situations where a general objective can be achieved in many ways. Theory Questions 1 Define OR 3 2 Discuss application of OR 7 3 Briefefly discuss the OR models 10 4 Explain physical models of OR 3 5 Examine the techniques of OR 10 6 Enumerate on the scope of OR 7 7 Explain the methodology of OR 10 8 List out the various phases of OR 3 9 Describe the characteristics of OR 10 10 What is model? 3 11 Write three limitations of OR 3 12 Give any three characteristics of a good model 3
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 28 13 “Operations research is the art of winning wars without actually fighting them” Critically evaluate 7 14 Discuss in details history of OR 7 15 What is the definition of OR form Operational Research Society, UK perspective 3 16 “Operations research is the art of finding bad answers to problems which otherwise have worse answers.” Justify 7 17 What are the advantages and limitation of OR
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 29 OPERATIONS RESEARCH MODULE-2 Linear programming: Linear Programming Problem (LPP), Generalized LPP- Formulation of LPP, Guidelines for formulation of linear programming model, Assumption, Advantages, Limitations, Linear Programming problem (LPP), optimal and feasible Solutions by graphical method (minimization and maximization). Simplex Method(Theory and Problems) Definition Linear Programming is a mathematical technique useful for allocation of ‘scarce’ or ‘limited’ resources, to several competing activities on the basis of a given criterion of optimality. In 1947, during World War II, George B Dantzing while working with the US Air Force, developed LP model, primarily for solving military logistics problems. But now, it is extensively being used in all functional areas of management, airlines, agriculture, military operations, education, energy planning, pollution control, transportation planning and scheduling, research and development, health care systems, etc. Though these applications are diverse, all LP models have certain common properties and assumptions – that are essential for decision-makers to understand before their use. General Structure of an LP Model Decision variables (activities): The evaluation of various courses of action (alternatives) and select the best to arrive at the optimal value of objective function, is guided by the nature of objective function and availability of resources. For this, certain activities (also called decision variables) usually denoted by x1, x2, . . ., xn are conducted. The objective function: The objective function of each LP problem is expressed in terms of decision variables to optimize the criterion of optimality (also called measure-of- performance) such as profit, cost, revenue, distance etc. In its general form, it is represented as: Optimize (Maximize or Minimize) Z = c1x1 + c2 x2 + . . . + cn xn, The constraints: There are always certain limitations (or constraints) on the use of resources, such as: labour, machine, raw material, space, money, etc., that limit the degree to which an objective can be achieved. Such constraints must be expressed as linear equalities or
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 30 inequalities in terms of decision variables. The solution of an LP model must satisfy these constraints. Assumptions of an LP Model In all mathematical models, assumptions are made for reducing the complex real-world problems into a simplified form that can be more readily analyzed. The following are the major assumptions of an LP model: 1. Certainty: In LP models, it is assumed that all its parameters such as: availability of resources, profit (or cost) contribution per unit of decision variable and consumption of resources per unit of decision variable must be known and constant. 2. Additivity: The value of the objective function and the total amount of each resource used (or supplied), must be equal to the sum of the respective individual contribution (profit or cost) of the decision variables. For example, the total profit earned from the sale of two products A and B must be equal to the sum of the profits earned separately from A and B. Similarly, the amount of a resource consumed for producing A and B must be equal to the total sum of resources used for A and B individually. 3. Linearity (or proportionality): The amount of each resource used (or supplied) and its contribution to the profit (or cost) in objective function must be proportional to the value of each decision variable. For example, if production of one unit of a product uses 5 hours of a particular resource, then making 3 units of that product uses 3×5 = 15 hours of that resource. 4. Divisibility (or continuity): The solution values of decision variables are allowed to assume continuous values. For instance, it is possible to collect 6.254 thousand litres of milk by a milk dairy and such variables are divisible. But, it is not desirable to produce 2.5 machines and such variables are not divisible and therefore must be assigned integer values. Hence, if any of the variable can assume only integer values or are limited to discrete number of values, LP model is no longer applicable. ADVANTAGES OF USING LINEAR PROGRAMMING Following are certain advantages of using linear programming technique: 1. Linear programming technique helps decision-makers to use their productive resources effectively.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 31 2. Linear programming technique improves the quality of decisions. The decision-making approach of the user of this technique becomes more objective and less subjective. 3. Linear programming technique helps to arrive at optimal solution of a decision problem by taking into account constraints on the use of resources. For example, saying that so many units of any product may be produced does not mean that all units can be sold. 4. Linear programming approach for solving decision problem highlight bottlenecks in the production processes. For example, when a bottleneck occurs, machine cannot produce sufficient number of units of a product to meet demand. Also, machines may remain idle. LIMITATIONS OF LINEAR PROGRAMMING In spite of having many advantages and wide areas of applications, there are some limitations associated with this technique. These are as follows: 1. Linear programming assumes linear relationships among decision variables. However, in real-life problems, decision variables, neither in the objective function nor in the constraints are linearly related. 2. While solving an LP model there is no guarantee that decision variables will get integer value. For example, how many men/machines would be required to perform a particular job, a non-integer valued solution will be meaningless. Rounding off the solution to the nearest integer will not yield an optimal solution. 3. The linear programming model does not take into consideration the effect of time and uncertainty. 4. Parameters in the model are assumed to be constant but in real-life situations, they are frequently neither known nor constant. 5. Linear programming deals with only single objective, whereas in real-life situations a decision problem may have conflicting and multiple objectives.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 32 GENERAL MATHEMATICAL MODEL OF LINEAR PROGRAMMING PROBLEM GUIDELINES ON LINEAR PROGRAMMING MODEL FORMULATION Step 1: Identify the decision variables Step 2: Identify the problem data Step 3: Formulate the constraints Step 4: Formulate the objective function GRAPHICAL METHOD An optimal as well as a feasible solution to an LP problem is obtained by choosing one set of values from several possible values of decision variables x1, x2, . . ., xn, that satisfies the given constraints simultaneously and also provides an optimal (maximum or minimum) value of the given objective function. For LP problems that have only two variables, it is possible that the entire set of feasible solutions can be displayed graphically by plotting linear constraints on a graph paper in order to locate the best (optimal) solution. The technique used to identify the optimal solution is called the graphical solution method (approach or technique) for an LP problem with two variables. Since most real-world problems have more than two decision variables, such problems cannot be solved graphically. However, graphical approach provides understanding of solving an LP problem algebraically, involving more than two variables. the following two graphical solution methods (or approaches): (i) Extreme point solution method (ii) Iso-profit (cost) function line method
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 33 ISO-PROFIT (COST) FUNCTION LINE METHOD According to this method, the optimal solution is found by using the slope of the objective function line (or equation). An iso-profit (or cost) line is a collection of points that give solution with the same value of objective function. By assigning various values to Z, we get different profit (cost) lines. Graphically many such lines can be plotted parallel to each other. The steps of iso-profit (cost) function method are as follows: Step 1: Identify the feasible region and extreme points of the feasible region. Step 2: Draw an iso-profit (iso-cost) line for an arbitrary but small value of the objective function without violating any of the constraints of the given LP problem. However, it is simple to pick a value that gives an integer value to x1 when we set x2 = 0 and vice-versa. A good choice is to use a number that is divided by the coefficients of both variables. Step 3: Move iso-profit (iso-cost) lines parallel in the direction of increasing (decreasing) objective function values. The farthest iso-profit line may intersect only at one corner point of feasible region providing a single optimal solution. Also, this line may coincide with one of the boundary lines of the feasible area. Then at least two optimal solutions must lie on two adjoining corners and others will lie on the boundary connecting them. However, if the iso- profit line goes on without limit from the constraints, then an unbounded solution would exist. This usually indicates that an error has been made in formulating the LP model. Step 4: An extreme (corner) point touched by an iso-profit (or cost) line is considered as the optimal solution point. The coordinates of this extreme point give the value of the objective function.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 34 Comparison of Two Graphical Solution Methods After having plotted the constraints of the given LP problem to locate the feasible solution region (area) one of the two graphical solution methods may be used to get optimal value of the given LP problem. DIFFERENTIATE BETWEEN INFESIBILITY V/S UNBOUNEDNESS An infeasible problem is a problem that has no solution while an unbounded problem is one where the constraints do not restrict the objective function and the objective goes to infinity. Both situations often arise due to errors or shortcomings in the formulation or in the data defining the problem. Simplex Method The Simplex Method is a mathematical technique used to solve Linear Programming Problems (LPPs), which aim to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints (inequalities or equations). Key Points about the Simplex Method: 1. Purpose: To find the optimal solution for problems involving resource allocation, production scheduling, transportation, etc. 2. Form of the Problem: o Objective Function: Maximize or minimize Z=c1x1+c2x2+⋯+cnxnZ = c_1x_1 + c_2x_2 + \dots + c_nx_nZ=c1x1+c2x2+⋯+cnxn o Constraints: System of linear inequalities or equations o Non-negativity: xi≥0x_i \geq 0xi≥0 3. Steps Involved:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 35 o Convert inequalities to equations using slack, surplus, and artificial variables. o Construct the initial simplex tableau. o Perform iterative computations (pivoting) to improve the solution. o Stop when no further improvement is possible (optimality condition met). 4. Advantages: o Provides exact optimal solution. o Efficient for problems with a moderate number of variables and constraints. 5. Limitations: o Can be computationally expensive for very large problems. o Not suitable for non-linear problems. 1 What Basic feasible solution? Mention the type of basic feasible solution 3 2 Explain the various assumption, advantages and limitation of LPP 10 3 Discuss the special cases of LPP 7 4 Outline any two assumptions of LPP models 3 5 What are the applications of LPP in management? 3 6 Explain the various assumption, advantages and limitation of LPP models 3 7 what is LPP? 3 8 Write a note on Isocost and Isoprofit lines 3 9 What are objective function, decision variables and constraints with reference to LPP? 7 1 0 Write general structure of LPP 7
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 36 OPERATIONS RESEARCH MODULE-3 Decision Theory: Introduction, Decision under uncertainty- Maxmin &Minmax, Decision under Risk- Expected Value, Simple decision tree problems. (Only theory). Job Sequencing- ‘n’ jobs on 2 machines, ‘n’ jobs on 3 machines, ‘n’ jobs on ‘m’ machines. Sequencing of 2 jobs on ‘m’ machines. (Theory and Problems). Introduction In decision theory a set of techniques are used for making decisions in the decision- environment of uncertainty and risk. Decision theory is both descriptive and prescriptive business modeling approach to classify the degree of knowledge and compare expected outcomes due to several courses of action. The degree of knowledge is divided into four categories: complete knowledge (i.e. certainty), ignorance, risk and uncertainty as shown in below fig. Decision alternatives There is a finite number of decision alternatives available to the decision-maker at each point in time when a decision is made. The number and type of such alternatives may depend on the previous decisions made and their outcomes. Decision alternatives may be described numerically, such as stocking 100 units of a particular item, or non-numerically, such as conducting a market survey to know the likely demand of an item. Payoff It is a numerical value (outcome) obtained due to the application of each possible combination of decision alternatives and states of nature. The payoff values are always conditional values because of unknown states of nature. The payoff values are measured within a specified period (e.g. within one year, month, etc.) called the decision horizon. The payoffs in most decisions are monetary. Payoffs resulting from each possible combination of decision alternatives and states of natures are displayed
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 37 in a matrix (also called payoff matrix) form as shown in below table . STEPS OF DECISION-MAKING PROCESS The decision-making process involves the following steps: 1. Identify and define the problem. 2. List all possible future events (not under the control of decision-maker) that are likely to occur 3. Identify all the courses of action available to the decision-maker. 4. Express the payoffs ( pij ) resulting from each combination of course of action and state of nature. 5. Apply an appropriate decision theory model to select the best course of action from the given list on the basis of a criterion (measure of effectiveness) to get optimal (desired) payoff. TYPES OF DECISION-MAKING ENVIRONMENTS To arrive at an optimal decision it is essential to have an exhaustive list of decision- alternatives, knowledge of decision environment, and use of appropriate quantitative approach for decision-making. In this section three types of decision-making environments: certainty, uncertainty, and risk, have been discussed. The knowledge of these environments helps in choosing the quantitative approach for decision-making.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 38 Type 1 Decision-Making under Certainty In this decision-making environment, decision-maker has complete knowledge (perfect information) of outcome due to each decision-alternative (course of action). In such a case he would select a decision alternative that yields the maximum return (payoff) under known state of nature. For example, the decision to invest in National Saving Certificate, Indira Vikas Patra, Public Provident Fund, etc., is where complete information about the future return due and the principal at maturity is know. Type 2 Decision-Making under Risk In this decision-environment, decision-maker does not have perfect knowledge about possible outcome of every decision alternative. It may be due to more than one states of nature. In a such a case he makes an assumption of the probability for occurrence of particular state of nature. Type 3 Decision-Making under Uncertainty In this decision environment, decision-maker is unable to specify the probability for occurrence of particular state of nature. However, this is not the case of decision-making under ignorance, because the possible states of nature are known. Thus, decisions under uncertainty are taken even with less information than decisions under risk. For example, the probability that Mr X will be the prime minister of the country 15 years from now is not known. DECISION-MAKING UNDER UNCERTAINTY When probability of any outcome can not be quantified, the decision-maker must arrive at a decision only on the actual conditional payoff values, keeping in view the criterion of effectiveness (policy). The following criteria of decision-making under uncertainty have been discussed in this section. (i) Optimism (Maximax or Minimin) criterion (ii) Pessimism (Maximin or Minimax) criterion (iii) Equal probabilities (Laplace) criterion
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 39 (iv) Coefficient of optimism (Hurwiez) criterion (v) Regret (salvage) criterion Optimism (Maximax or Minimin) Criterion In this criterion the decision-maker ensures that he should not miss the opportunity to achieve the largest possible profit (maximax) or the lowest possible cost (minimin). Thus, he selects the decision alternative that represents the maximum of the maxima (or minimum of the minima) payoffs (consequences or outcomes). The working method is summarized as follows: (a) Locate the maximum (or minimum) payoff values corresponding to each decision alternative. (b) Select a decision alternative with best payoff value (maximum for profit and minimum for cost). Since in this criterion the decision-maker selects an decision-alternative with largest (or lowest) possible payoff value, it is also called an optimistic decision criterion. Pessimism (Maximin or Minimax) Criterion In this criterion the decision-maker ensures that he would earn no less (or pay no more) than some specified amount. Thus, he selects the decision alternative that represents the maximum of the minima (or minimum of the minima in case of loss) payoff in case of profits. The working method is summarized as follows: (a) Locate the minimum (or maximum in case of profit) payoff value in case of loss (or cost) data corresponding to each decision alternative. (b) Select a decision alternative with the best payoff value (maximum for profit and mimimum for loss or cost). Since in this criterion the decision-maker is conservative about the future and always anticipates the worst possible outcome (minimum for profit and maximum for cost or loss), it is called a pessimistic decision criterion. This criterion is also known as Wald’s criterion.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 40 Equal Probabilities (Laplace) Criterion Since the probabilities of states of nature are not known, it is assumed that all states of nature will occur with equal probability, i.e. each state of nature is assigned an equal probability. As states of nature are mutually exclusive and collectively exhaustive, so the probability of each of these must be: 1/(number of states of nature). The working method is summarized as follows: (a) Assign equal probability value to each state of nature by using the formula: 1 ÷ (number of states of nature). (b) Compute the expected (or average) payoff for each alternative (course of action) by adding all the payoffs and dividing by the number of possible states of nature, or by applying the formula: (Probability of state of nature j ) × (Payoff value for the combination of alternative i and state of nature j.) (c) Select the best expected payoff value (maximum for profit and minimum for cost). This criterion is also known as the criterion of insufficient reason. This is because except in a few cases, some information of the likelihood of occurrence of states of nature is available Coefficient of Optimism (Hurwicz) Criterion This criterion suggests that a decision-maker should be neither completely optimistic nor pessimistic and, therefore, must display a mixture of both. Hurwicz, who suggested this criterion, introduced the idea of a coefficient of optimism (denoted by α) to measure the decision-maker’s degree of optimism. This coefficient lies between 0 and 1, where 0 represents a complete pessimistic attitude about the future and 1 a complete optimistic attitude about the future. Thus, if α is the coefficient of optimism, then (1 – α) will represent the coefficient of pessimism. The Hurwicz approach suggests that the decision-maker must select an alternative that maximizes H (Criterion of realism) = α (Maximum in column) + (1 – α ) (Minimum in column) The working method is summarized as follows:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 41 (a) Decide the coefficient of optimism α (alpha) and then coefficient of pessimism (1 – α). (b) For each decision alternative select the largest and lowest payoff value and multiply these with α and (1 – α) values, respectively. Then calculate the weighted average, H by using above formula. (c) Select an alternative with best weighted average payoff value. Regret (Savage) Criterion This criterion is also known as opportunity loss decision criterion or minimax regret decision criterion because decision-maker regrets for choosing wrong decision alternative resulting in an opportunity loss of payoff. Thus, he always intends to minimize this regret. The working method is summarized as follows: (a) From the given payoff matrix, develop an opportunity-loss (or regret) matrix as follows: (i) Find the best payoff corresponding to each state of nature (ii) Subtract all other payoff values in that row from this value. (b) For each decision alternative identify the worst (or maximum regret) payoff value. Record this value in the new row. (c) Select a decision alternative resulting in a smallest anticipated opportunity-loss value. DECISION-MAKING UNDER RISK In this decision-making environment, decision-maker has sufficient information to assign probability to the likely occurrence of each outcome (state of nature). Knowing the probability distribution of outcomes (states of nature), the decision-maker needs to select a course of action resulting a largest expected (average) payoff value. The expected payoff is the sum of all possible weighted payoffs resulting from choosing a decision alternative. The widely used criterion for evaluating decision alternatives (courses of action) under risk is the Expected Monetary Value (EMV) or Expected Utility.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 42 Expected Monetary Value (EMV) The expected monetary value (EMV) for a given course of action is obtained by adding payoff values multiplied by the probabilities associated with each state of nature. Mathematically, EMV is stated as follows: The Procedure 1. Construct a payoff matrix listing all possible courses of action and states of nature. Enter the conditional payoff values associated with each possible combination of course of action and state of nature along with the probabilities of the occurrence of each state of nature. 2. Calculate the EMV for each course of action by multiplying the conditional payoffs by the associated probabilities and adding these weighted values for each course of action. 3. Select the course of action that yields the optimal EMV Expected Opportunity Loss (EOL) Expected opportunity loss (EOL), also called expected value of regret, is an alternative decision criterion for decision making under risk. The EOL is defined as the difference between the highest profit (or payoff ) and the actual profit due to choosing a particular course of action in a particular state of nature. Hence, EOL is the amount of payoff that is lost by not choosing a course of action resulting to the minimum payoff in a particular state of nature. A course of action resulting to the minimum EOL is preferred. Mathematically, EOL is stated as follows.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 43 The Procedure 1. Prepare a conditional payoff values matrix for each combination of course of action and state of nature along with the associated probabilities. 2. For each state of nature calculate the conditional opportunity loss (COL) values by subtracting each payoff from the maximum payoff. 3. Calculate the EOL for each course of action by multiplying the probability of each state of nature with the COL value and then adding the values. 4. Select a course of action for which the EOL is minimum. Expected Value of Perfect Information (EVPI) If decision-makers can get perfect (complete and accurate) information about the occurrence of various states of nature, then choosing a course of action that yields the desired payoff in the presence of any state of nature is easy. The EMV or EOL criterion helps the decision-maker to select a particular course of action that optimizes the expected payoff, without any additional information. Expected value of perfect information (EVPI) represents the maximum amount of money required to pay for getting additional information about the occurrence of various states of nature before arriving to a decision. Mathematically, it is stated as: DECISION TREE ANALYSIS Decision-making problems discussed earlier were limited to arrive at a decision over a fixed period of time. That is, payoffs, states of nature, courses of action and probabilities associated
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 44 with the occurrence of states of nature were not subject to change. However, situations may arise when a decision-maker needs to revise his previous decisions due to availability of additional information. Thus he intends to make a sequence of interrelated decisions over several future periods. Such a situation is called a sequential or multiperiod decision process. For example, in the process of marketing a new product, a company usually first go for ‘Test Marketing’ and other alternative courses of action might be either ‘Intensive Testing’ or ‘Gradual Testing’. Given the various possible consequences – good, fair, or poor, the company may be required to decide between redesigning the product, an aggressive advertising campaign or complete withdrawal of product, etc. Based on this decision there might be an outcome that leads to another decision and so on. A decision tree analysis involves the construction of a diagram that shows, at a glance, when decisions are expected to be made – in what sequence, their possible outcomes, and the corresponding payoffs. A decision tree consists of nodes, branches, probability estimates, and payoffs. There are two types of nodes: • Decision (or act) node: A decision node is represented by a square and represents a point of time where a decision-maker must select one alternative course of action among the available. The courses of action are shown as branches or arcs emerging out of decision node. • Chance (or event) node: Each course of action may result in a chance node. The chance node is represented by a circle and indicates a point of time where the decision-maker will discover the response to his decision Branches emerge from and connect various nodes and represent either decisions or states of nature. There are two types of branches: • Decision branch: It is the branch leading away from a decision node and represents a course of action that can be chosen at a decision point. • Chance branch: It is the branch leading away from a chance node and represents the state of nature of a set of chance events. The assumed probabilities of the states of nature are written alongside their respective chance branch. • Terminal branch: Any branch that makes the end of the decision tree (not followed by either a decision or chance node), is called a terminal branch. A terminal branch can represent either
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 45 a course of action. The terminal points of a decision tree are supposed to be mutually exclusive points so that exactly one course of action will be chosen The optimal sequence of decisions in a tree is found by starting at the right-hand side and rolling backwards. At each node, an expected return is calculated (called position value). If the node is a chance node, then the position value is calculated as the sum of the products of the probabilities or the branches emanating from the chance node and their respective position values. If the node is a decision node, then the expected return is calculated for each of its branches and the highest return is selected. This procedure continues until the initial node is
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 46 reached. The position values for this node corresponds to the maximum expected return obtainable from the decision sequence.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 47 SEQUENCING PROBLEMS INTRODUCTION The optimal order (sequence) shows the minimum time in which jobs, equipment, people, materials, facilities and all other resources are arranged to support the production schedules to give low costs and high utilizations. Other objectives of calculating optimal production schedule are minimizing customers waiting time for a product or service, meeting promised delivery dates, keeping stock levels low providing preferred working pattern, and so on. If n jobs are to be performed, one at a time, on each of m machines, where sequence (order) of the machines in which each job should be performed, and the actual (or expected) time required by the jobs on each of the machines are given, then the general sequencing problem is to find a sequence out of (n!)m possible sequences, which minimize the total elapsed time between the start of the job on first machine and the completion of the last job on the last machine. In particular, if there are n = 3 jobs to be performed and m = 3 machines are to be used, then the total number of possible sequences will be (3!)3 = 216. Theoretically, it may be possible to find the optimum sequence but this would require a lot of computational time. Thus, one should adopt the sequencing technique. To find the optimum sequence, we first need to calculate the total elapsed time for each of the possible sequences. As stated earlier, even if the values of m and n are very small, it is difficult to get the desired sequence with the total minimum elapsed time. However, due to certain rules designed by Johnson, the task of determining an optimum sequence has become quite easy. Sequencing problem is the problem of finding an optimal sequence of completing certain number of jobs so as to minimize the total elapsed time between completion of first and last job. NOTATIONS, TERMINOLOGY AND ASSUMPTIONS
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 48 Assumptions 1. The processing time on different machines are exactly known and are independent of the order of the jobs in which they are to be processed. 2. The time taken by the job in moving from one machine to another is negligible. 3. Once a job has begun on a machine, it must be completed before another job can begin on the same machine. 4. All jobs are known and are ready for processing before the period under consideration begins. 5. Only one job can be processed on a given machine at a time. 6. Machines to be used are of different types. 7. The order of completion of jobs are independent of the sequence of jobs. PROCESSING n JOBS THROUGH TWO MACHINES Let there be n jobs, each of which is to be processed through two machines, M1 and M2 in the order M1M2, i.e. each job has to pass through the same sequence of operations. In other words, a job is assigned on machine M1 first and once processing is over on machine M1, it is
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 49 assigned to machine M2. If the machine M2 is not free for processing the same job, then the job is placed in waiting line for its turn on machine M2, i.e. passing is not allowed. Since passing is not allowed, therefore, machine M1 will remain busy in processing all the n jobs one by- one, while machine M2 may remain idle waiting for the jobs to come from M1. The idle time for both M1 and M2 may be reduced by determining an optimal sequence of n jobs to be processed on two machines M1 and M2. The procedure suggested by Johnson for determining the optimal sequence is summarized as follows: Johnson’s Procedure Step 1: List the jobs along with their processing times on each machine in a table, as shown below:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 50 PROCESSING n JOBS THROUGH THREE MACHINES An extension of Johnson’s procedure for scheduling jobs on two machines M1 and M2 in the order M1 M2 has been discussed in this section. The list of jobs with their processing times on three machines M1, M2 and M3 is given below. An optimal solution to this problem can be obtained if either or both of the following conditions hold good: 1. The minimum processing time on machine M1 is at least as great as the maximum processing time on machine M2, that is, min t1j ≥ max t2j, for j = 1, 2, . . ., n 2. The minimum processing time on machine M3 is at least as great as the maximum processing time on machine M2, that is, min t3j ≥ max t2j, for j = 1, 2, . . ., n If either or both the above conditions hold good, then the steps of the algorithm can be summarized in the following steps:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 51 The Procedure
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 52 PROCESSING n JOBS THROUGH m MACHINES PROCESSING TWO JOBS THROUGH m MACHINES Let there be two jobs A and B, each of which is to be processed on m machines say M1, M2, . . ., Mm, in two different orders. The technological ordering of each of the two jobs through m machines is known in advance. Such ordering may not be same for both the jobs. The exact or expected processing times on the given machines are known. Each machine can perform only one job at a time. The objective is to determine an optimal sequence of processing the jobs so as to minimize total elapsed time.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 53
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 54 1 What are the steps of decision making process? 7 2 Explain decision making methods under uncertainty 10 3 Explain the assumptions of sequencing problems 7 4 What do you understand by work breakdown structure 3 5 why is job sequencing important? 3 6 Briefly explain the steps involved i n decision-making process 7 7 What are the different criteria for decision making under uncertainty? explain 7 8 What do you mean by "pay off" in decision theory? 3 9 What do you understand by Decision tree? 3 10 what is decision tree analysis? bring out the two approach s used to evaluate the decision tree 3 11 Briefly explain the types of decision-making environment 10 12 Explain briefly about decision making under risk and decision trees 3 13 What are nodes and branches in decision tree 3 14 Define opportunity loss table 3 15 Differentiate between Maximin and Minimax principle 7 16 Explain the procedure of processing 'n' jobs in two machines 7 17 Explain the procedure of processing 'n' jobs in 3machines 7 18 Write a sequencing procedure of processing 2 jobs in m machines 7
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 55 OPERATIONS RESEARCH MODULE-4 Transportation Problems: Formulation of transportation problem, types, initial basic feasible solution using North-West Corner Rule (NWCR), Least Cost Method (LCM) and Vogel’s Approximation method (VAM). Optimality in Transportation problem by Modified Distribution (MODI) method. Unbalanced T.P. Maximization T.P. Degeneracy in transportation problems, Application of transportation problem. (Theory and Problems) Introduction One important application of linear programming is in the area of physical distribution (transportation) of goods and services from several supply centres to several demand centres. A transportation problem when expressed in terms of an LP model can also be solved by the simplex method. However a transportation problem involves a large number of variables and constraints, solving it using simplex methods takes a long time. Two transportation algorithms, namely Stepping Stone Method and the MODI (modified distribution) Method have been developed for solving a transportation problem. The structure of transportation problem involves a large number of shipping routes from several supply centres to several demand centres. Thus, objective is to determine shipping routes between supply centres and demand centres in order to satisfy the required quantity of goods or services at each destination centre, with available quantity of goods or services at each supply centre at the minimum transportation cost and/or time. The transportation algorithms help to minimize the total cost of transporting a homogeneous commodity (product) from supply centres to demand centres. However, it can also be applied to the maximization of total value or utility. The study of transportation problem helps to identify optimal transportation routes along with units of commodity to be shipped in order to minimize total transportation cost. General Mathematical Model of Transportation Problem Let there be m sources of supply, S1, S2, . . ., Sm having ai (i = 1, 2, . . ., m) units of supply (or
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 56 capacity), respectively to be transported to n destinations, D1, D2, . . ., Dn with bj ( j = 1, 2, . . ., n) units of demand (or requirement), respectively. Let cij be the cost of shipping one unit of the commodity from source i to destination j. If xij represents number of units shipped from source i to destination j, the problem is to determine the transportation schedule so as to minimize the total transportation cost while satisfying the supply and demand conditions. Mathematically, the transportation problem, in general, may be stated as follows: THE TRANSPORTATION ALGORITHM The algorithm for solving a transportation problem may be summarized into the following steps: Step 1: Formulate the problem and arrange the data in the matrix form The formulation
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 57 of the transportation problem is similar to the LP problem formulation. In transportation problem, the objective function is the total transportation cost and the constraints are the amount of supply and demand available at each source and destination, respectively. Step 2: Obtain an initial basic feasible solution In this chapter, following three different methods are discussed to obtain an initial solution: • North-West Corner Method, • Least Cost Method, and • Vogel’s Approximation (or Penalty) Method. The initial solution obtained by any of the three methods must satisfy the following conditions: (i) The solution must be feasible, i.e. it must satisfy all the supply and demand constraints (also called rim conditions). (ii) The number of positive allocations must be equal to m + n – 1, where m is the number of rows and n is the number of columns. Any solution that satisfies the above conditions is called non-degenerate basic feasible solution, otherwise, degenerate solution. Step 3: Test the initial solution for optimality In this chapter, the Modified Distribution (MODI) method is discussed to test the optimality of the solution obtained in Step 2. If the current solution is optimal, then stop. Otherwise, determine a new improved solution. Step 4: Updating the solution Repeat Step 3 until an optimal solution is reached. METHODS OF FINDING INITIAL SOLUTION North-West Corner Method (NWCM) This method does not take into account the cost of transportation on any route of transportation. The method can be summarized as follows:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 58 Step 1: Start with the cell at the upper left (north-west) corner of the transportation table (or matrix) and allocate commodity equal to the minimum of the rim values for the first row and first column, i.e. min (a1, b1). When total demand equals total supply, the transportation problem is said to be balanced Step 2: (a) If allocation made in Step 1 is equal to the supply available at first source (a1, in first row), then move vertically down to the cell (2, 1), i.e., second row and first column. Apply Step 1 again, for next allocation. (b) If allocation made in Step 1 is equal to the demand of the first destination (b1 in first column), then move horizontally to the cell (1, 2), i.e., first row and second column. Apply Step 1 again for next allocation. (c) If a1 = b1, allocate x11 = a1 or b1 and move diagonally to the cell (2, 2). Step 3: Continue the procedure step by step till an allocation is made in the south-east corner cell of the transportation table. Remark If during the process of making allocation at a particular cell, the supply equals demand, then the next allocation of magnitude zero can be made in a cell either in the next row or column. This condition is known as degeneracy. Least Cost Method (LCM) Since the main objective is to minimize the total transportation cost, transport as much as possible through those routes (cells) where the unit transportation cost is lowest. This method takes into account the minimum unit cost of transportation for obtaining the initial solution and can be summarized as follows: Step 1: Select the cell with the lowest unit cost in the entire transportation table and allocate as much as possible to this cell. Then eliminate (line out) that row or column in which either the supply or demand is fulfilled. If a row and a column are both satisfied simultaneously,
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 59 then crossed off either a row or a column. In case the smallest unit cost cell is not unique, then select the cell where the maximum allocation can be made. Step 2: After adjusting the supply and demand for all uncrossed rows and columns repeat the procedure to select a cell with the next lowest unit cost among the remaining rows and columns of the transportation table and allocate as much as possible to this cell. Then crossed off that row and column in which either supply or demand is exhausted. Step 3: Repeat the procedure until the available supply at various sources and demand at various destinations is satisfied. The solution so obtained need not be non-degenerate. Vogel’s Approximation Method (VAM) Vogel’s approximation (penalty or regret) is preferred over NWCR and LCM methods. In this method, an allocation is made on the basis of the opportunity (or penalty or extra) cost that would have been incurred if the allocation in certain cells with minimum unit transportation cost were missed. Hence, allocations are made in such a way that the penalty cost is minimized. An initial solution obtained by using this method is nearer to an optimal solution or is the optimal solution itself. The steps of VAM are as follows: Step 1: Calculate the penalties for each row (column) by taking the difference between the smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty or extra cost that has to be paid if decision-maker fails to allocate to the cell with the minimum unit transportation cost. Step 2: Select the row or column with the largest penalty and allocate as much as possible in the cell that has the least cost in the selected row or column and satisfies the rim conditions. If there is a tie in the values of penalties, it can be broken by selecting the cell where the maximum allocation can be made. Step 3: Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 60 (column) is assigned a zero supply (demand). Any row or column with zero supply or demand should not be used in computing future penalties. Step 4: Repeat Steps 1 to 3 until the available supply at various sources and demand at various destinations is satisfied. TEST FOR OPTIMALITY Once an initial solution is obtained, the next step is to check its optimality in terms of feasibility of the solution and total minimum transportation cost. The test of optimality begins by calculating an opportunity cost associated with each unoccupied cell (represents unused route) in the transportation table. An unoccupied cell with the largest negative opportunity cost is selected to include in the new set of transportation routes (allocations). This value indicates the per unit cost reduction that can be achieved by making appropriate allocation in the unoccupied cell. This cell is also known as an incoming cell (or variable). The outgoing cell (or variable) from the current solution is the occupied cell (basic variable) where allocation will become zero as allocation is made in the unoccupied cell with the largest negative opportunity cost. Such an exchange reduces the total transportation cost. The process is continued until there is no negative opportunity cost. That is, the current solution is an optimal solution. The Modified-distribution (MODI) method (also called u-v method or method of multipliers) is used to calculate opportunity cost associated with each unoccupied cell and then improving the current solution leading to an optimal solution
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 61 Steps of MODI Method (Transportation Algorithm)
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 62 VARIATIONS IN TRANSPORTATION PROBLEM Some of the variations that often arise while solving a transportation problem are as follows. Unbalanced Supply and Demand For a feasible solution to exist, it is necessary that the total supply must equal the total demand. That is, But a situation may arise when the total available supply is not equal to the total demand [For proof see appendix]. The following two cases may arise: (a) If the total supply exceeds the total demand, then an additional column (called a dummy demand centre) can be added to the transportation table in order to absorb the excess supply. The unit transportation cost for the cells in this column is set equal to zero because these represent product items that are neither made nor sent. (b) If the total demand exceeds the total supply, a dummy row (called a dummy supply centre) can be added to the transportation table to account for the excess demand quality. The unit transportation cost in such a case also, for the cells in the dummy row is set equal to zero. Degeneracy and its Resolution A basic feasible solution for the general transportation problem must have exactly m + n – 1 (number of rows + number of columns – 1) positive allocations in the transportation table. If the number of occupied cells is less than the required number, m + n – 1, then such a solution is called degenerate solution. In such cases, the current solution cannot be improved further because it is not possible to draw a closed path for every occupied cell. Also, the values of dual variables ui and vj that are used to test the optimality cannot be computed. Thus, degeneracy needs to be removed in order to improve the given solution. The degeneracy in the transportation problems may occur at two stages: (a) At initial basic feasible solution the number of occupied cells may be less than m + n – 1 allocations.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 63 (b) At any stage while moving towards optimal solution two or more occupied cells may become simultaneously unoccupied. Alternative Optimal Solutions The existence of alternative optimal solutions can be determined by an inspection of the opportunity costs, Δij for the unoccupied cells. If Δij = 0, for an unoccupied cell in an optimal solution, then an alternative optimal solution exists and can be obtained by bringing such an unoccupied cell in the solution mix without increasing the total transportation cost. Prohibited Transportation Routes If situations like road hazards (snow, flood, etc.), traffic regulations, etc., arise, then it may not be possible to transport goods from certain sources to certain destinations. Such situations can be handled by assigning a very large cost, say M (or ∞ ) to such a route(s) (or cell). MAXIMIZATION TRANSPORTATION PROBLEM In general, the transportation model is used for cost minimization problems. However, it may also be used to solve problems in which the objective is to maximize total profit. That is, instead of unit cost cij, the unit profit or payoff pij associated with each route, (i, j) is given. The objective function in terms of total profit (or payoff) is then stated as follows: The procedure for solving such problems is same as that for the minimization problem. However, a few adjustments in Vogel’s approximation method (VAM) for finding initial solution and in the MODI optimality test are required. For finding the initial solution by VAM, the penalties are computed as difference between the largest and next largest payoff in each row or column. In this case, row and column differences represent payoffs. Allocations are made in those cells where the payoff is largest, corresponding to the highest row or column difference.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 64 Since it is a maximization problem, the criterion of optimality is the converse of the rule for minimization. The rule is: A solution is optimal if all opportunity costs dij for the unoccupied cells are zero or negative. The transportation problem is a linear programming problem that has many applications, including: • Moving goods: The most common application is moving goods from factories to warehouses or from warehouses to stores. • Moving troops: The transportation problem can be used to move troops from bases to battlefields. • Assigning workers: The transportation problem can be used to assign workers to different jobs or positions. • Inventory control: The transportation problem can be used for inventory control. • Production planning: The transportation problem can be used for production planning. • Scheduling: The transportation problem can be used for scheduling. • Resource assignment: The transportation problem can be used for resource assignment. • Collaboration: The transportation problem can be used for collaboration in specialty. • Manufacturing: The transportation problem can be used for redistribution in manufacturing. • Districting: The transportation problem can be used to partition an area into districts.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 65 1 Outline the concept of Modified distribution method 3 2 What is degeneracy in transportation problem? 3 3 What is a closed loop in transportation problem? how a closed loop is drawn? explain 7 4 What is meant by unbalanced transportation problem? how to solve unbalanced transportation problem? 3 5 Differentiate between transportation and assignment problems 7 6 Witha the help of suitable flow chart explain Transportation problem 10 7 Explain the procedure of NWCM, LCM and VAM method in transportation 7
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 66 OPERATIONS RESEARCH MODULE-5 Theory of Games: Definition, Pure Strategy problems, Saddle point, Max-Min and Min-Max criteria, Principle of Dominance, Solution of games with Saddle point. Mixed Strategy problems (Graphical and algebraic methods). Assignment Problem: Formulation, Solutions to assignment problems by Hungarian method, Special cases in assignment problems, unbalanced, Maximization assignment problems. Introduction Game theory applies to those competitive situations which are technically known as “competitive games” or in general known an games. As the game is a competition involving two or more decisions makers each of whom is keen to win. The basic aim of this chapter is to study about how the optimal strategies are formulated in the conflict. Thus we can say that game theory is not related with finding an optimum or winning strategy for a particular conflict situation. Afterwards we can say that the theory of game is simply the logic of rational decisions. After reading this unit, you should be able to know how to take decision under the cut-throat competition and know that outcome of our business enterprise depends on what the competitor will do. Payoff Matrix: Company A has strategies A1, A2,…, Am, and Company B has strategies B1,B2,….,Bn. The number of pay-offs or outcomes is m × n. The pay-off amn represents company A’s gains from Company B, if company A selects strategy m and company B selects strategy n. At the same time, it is a loss for company B (–amn). The pay-off matrix is given (Table below) with respect to company A.
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 67 Two-person zero-sum game In a game with two players, if the gain of one player is equal to the loss of another player, then the game is a two person zero-sum game. A game in a competitive situation possesses the following properties: i. The number of players is finite. ii. Each player has finite list of courses of action or strategy. iii. A game is played when each player chooses a course of action (strategy) out of the available strategies. No player is aware of his opponent’s choice until he decides his own. iv. The outcome of the play depends on every combination of courses of action. Each outcome determines the gain or loss of each player. Pure strategies: game with saddle point The aim of the game is to determine how the players must select their respective strategies such that the pay-off is optimized. This decision-making is referred to as the
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 68 minimax-maximin principle to obtain the best possible selection of a strategy for the players. In a pay-off matrix, the minimum value in each row represents the minimum gain for player A. Player A will select the strategy that gives him the maximum gain among the row minimum values. The selection of strategy by player A is based on maximin principle. Similarly, the same pay-off is a loss for player B. The maximum value in each column represents the maximum loss for Player B. Player B will select the strategy that gives him the minimum loss among the column maximum values. The selection of strategy by player B is based on minimax principle. If the maximin value is equal to minimax value, the game has a saddle point (i.e., equilibrium point). Thus the strategy selected by player A and player B are optimal Mixed strategies: games without saddle point For any given pay off matrix without saddle point the optimum mixed strategies are shown in Table below
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 69 Dominance property THE RULES (PRINCIPLES) OF DOMINANCE The rules of dominance are used to reduce the size of the payoff matrix. These rules help in deleting certain rows and/or columns of the payoff matrix that are inferior (less attractive) to at least one of the remaining rows and/or columns (strategies), in terms of payoffs to both the players. Rows and/or columns once deleted can never be used for determining the optimum strategy for both the players. The rules of dominance are especially used for the evaluation of two-person zero-sum games without a saddle (equilibrium) point. Certain dominance principles are stated as follows:
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 70 1. For player A, the row which has all the elements smaller than the elements of some other row, then the row with smaller elements can be deleted. 2. For player B, the column which has all the elements greater than the elements of some other column, then the column with the greater element can be deleted. 3. In the payoff matrix of the player A, if each of the average sum of the entries of any 2 rows is greater than or equal to the corresponding entry of 3rd row, then the 3rd row is dominated by previous 2 rows (avg sum). Then, 3rd row can be deleted. 4. In a payoff matrix of player B, if average sum of entries of any 2 columns is lesser than or equal to the corresponding entry of the 3rd column, then the 3rd column is dominated by the avg sum of 2 previous columns, then the 3rd column is deleted. LIMITATIONS OF GAME THEORY The assumption that players have the knowledge about their own pay-offs and pay-offs of others is not practical. The techniques of solving games involving mixed strategies particularly in case of large pay- off matrix is very complicated. All the competitive problems cannot be analyzed with the help of game theory Note: Rules (principles) of dominance discussed are used when the payoff matrix is a profit matrix for the player A and a loss matrix for player B. Otherwise the principle gets reversed. Game theory Terminologies Strategy : The strategy of a player is the list of all possible actions that he takes for every pay- off. The strategy is classified into pure strategy and mixed strategy. Pure Strategy : Pure strategy is always selecting a particular course of action with the probability of 1. For example, in case of two strategies, probability of selecting the strategies for players A is p1 = 0 and p2 = 1. Mixed Strategy : Mixed strategy is to choose at least two courses of action. The probability of selecting an individual strategy will be less than 1, but the sum of the strategies will be 1. For
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 71 example, if player A plays a mixed strategy, then the probability of selection of mixed strategy is p1 = 0.45 and p2 = 0.55. But the sum of the strategies is 0.45 + 0.55 = 1. Saddle Point : Saddle point is a situation where both the players are facing pure strategies. When there is no saddle point, it indicates the players will play both the strategies. Minimax Criterion : Minimax criterion is selecting the strategies that minimize the loss for each player. In other words, the player always anticipates worst possible outcome and chooses the strategy to get maximum for profit and minimum for loss. Value of the Game : The Value of the game is the expected gain of player A if both players use their best strategies. The best strategy is arrived at using minimax criterion.
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 72 ASSIGNMENT PROBLEM INTRODUCTION An assignment problem is a particular case of a transportation problem where the resources (say facilities) are assignees and the destinations are activities (say jobs). Given n resources (or facilities) and n activities (or jobs), with effectiveness (in terms of cost, profit, time, etc.) of each resource for each activity. Then problem becomes to assign (or allocate) each resource to only one activity (job) and vice-versa so that the given measure of effectiveness is optimized. The problem of assignment arises because the resources that are available such as men, machines, etc., have varying degree of efficiency for performing different activities. Therefore, the cost, profit or time of performing different activities is also different. Thus, the problem becomes: How should the assignments be made in order to optimize the given objective. Some of the problems where the assignment technique may be useful are assignment of (i) workers to machines, (ii) salesmen to different sales areas, (iii) clerks to various checkout counters, (iv) classes to rooms, (v) vehicles to routes, (vi) contracts to bidders, etc. MATHEMATICAL MODEL OF ASSIGNMENT PROBLEM The general data matrix for assignment problem is shown in Table 10.1. It may be noted that this data matrix is the same as the transportation cost matrix except that the supply (or availability) of each of the resources and the demand at each of the destinations is taken to be one. It is due to this fact that assignments are made on a one-to-one basis.
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 73 This mathematical model of assignment problem is a particular case of the transportation problem for two reasons: (i) the cost matrix is a square matrix, and (ii) the optimal solution table (matrix) for the problem would have only one assignment in a given row or a column. SOLUTION METHODS OF ASSIGNMENT PROBLEM An assignment problem can be solved by any of the following methods: • Enumeration method
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 74 • Simplex method • Transportation method • Hungarian method Hungarian Method The Hungarian method (developed by Hungarian mathematician D. Konig) is an efficient method of finding the optimal solution of an assignment problem without making a direct comparison of every solution. The method works on the principle of reducing the given cost matrix to a matrix of opportunity costs. Opportunity costs show the relative penalties associated with assigning a resource to an activity. Hungarian method reduces the cost matrix to the extent of having at least one zero in each row and column so as to make optimal assignments. HUNGARIAN METHOD FOR SOLVING ASSIGNMENT PROBLEM The Hungarian method (minimization case) can be summarized in the following steps: Step 1: Develop the cost matrix from the given problem If the number of rows are not equal to the number of columns, then add required number of dummy rows or columns. The cost element in dummy rows/columns are always zero. Step 2: Find the opportunity cost matrix (a) Identify the smallest element in each row of cost matrix and then subtract it from each element of that row, and (b) In the reduced matrix obtained from 2(a), identify the smallest element in each column and then subtract it from each element of that column. Each row and column now have at least one zero element. Step 3: Make assignments in the opportunity cost matrix The procedure of making assignments is as follows: (a) First round for making assignments
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 75 • Identify rows successively from top to bottom until a row with exactly one zero element is found. Make an assignment to this single zero by making a square around it. Then cross off (×) all other zeros in the corresponding column. • Identify columns successively from left to right hand with exactly one zero element that has not been assigned. Make assignment to this single zero by making a square around it and then cross off (×) all other zero elements in the corresponding row. (b) Second round for making assignments • If a row and/or column has two or more unmarked zeros and one cannot be chosen by inspection, then choose zero element arbitrarily for assignment. • Repeat steps (a) and (b) successively until one of the following situations arise. Step 4: Optimality criterion (a) If all zero elements in the cost matrix are either marked with square or are crossed off (×) and there is exactly one assignment in each row and column, then it is an optimal solution. The total cost associated with this solution is obtained by adding the original cost elements in the occupied cells. (b) If a zero element in a row or column was chosen arbitrarily for assignment in Step 4(a), there exists an alternative optimal solution. (c) If there is no assignment in a row (or column), then this implies that the total number of assignments are less than the number of rows/columns in the square matrix. In such a situation proceed to Step 5. Step 5: Revise the opportunity cost matrix Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost matrix obtained from Step 3, by using the following procedure: (a) For each row in which no assignment was made, mark a tick (b) Examine the marked rows. If any zero element is present in these rows, mark a tick to the respective columns containing zeros.
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 76 (c) Examine marked columns. If any assigned zero element is present in these columns, tick the respective rows containing assigned zeros. (d) Repeat this process until no more rows or columns can be marked. (e) Draw a straight line through each marked column and each unmarked row. If the number of lines drawn (or total assignments) is equal to the number of rows (or columns), the current solution is the optimal solution, otherwise go to Step 6. Step 6: Develop the new revised opportunity cost matrix (a) Among the elements in the matrix not covered by any line, choose the smallest element. Call this value k. (b) Subtract k from every element in the matrix that is not covered by a line. (c) Add k to every element in the matrix covered by the two lines, i.e. intersection of two lines. (d) Elements in the matrix covered by one line remain unchanged. Step 7: Repeat steps Repeat Steps 3 to 6 until an optimal solution is obtained. VARIATIONS OF THE ASSIGNMENT PROBLEM Multiple Optimal Solutions While making an assignment in the reduced assignment matrix, it is possible to have two or more ways to strike off a certain number of zeros. Such a situation indicates that there are multiple optimal solutions with the same optimal value of objective function. Maximization Case in Assignment Problem If instead of cost matrix, a profit (or revenue) matrix is given, then assignments are mode in such a way that total profit is maximized. The profit maximization assignment problems are solved by converting them into a cost minimization problem in either of the following two ways:
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 77 (i) Put a negative sign before each of the elements in the profit matrix in order to convert the profit values into cost values. (ii) Locate the largest element in the profit matrix and then subtract all the elements of the matrix from the largest element including itself. The transformed assignment problem can be solved by using usual Hungarian method. Unbalanced Assignment Problem The Hungarian method for solving an assignment problem requires that the number of columns and rows in the assignment matrix should be equal. However, when the given cost matrix is not a square matrix, the assignment problem is called an unbalanced problem. In such cases before applying Hungarian method, dummy row(s) or column(s) are added in the matrix (with zeros as the cost elements) in order to make it a square matrix. Restrictions on Assignments Sometimes it may so happen that a particular resource (say a man or machine) cannot be assigned to a particular activity (say territory or job). In such cases, the cost of performing that particular activity by a particular resource is considered to be very large (written as M or ∞) so as to prohibit the entry of this pair of resource-activity into the final solution. TRAVELLING SALESMAN PROBLEM The travelling salesman problem may be solved as an assignment problem, with two additional conditions on the choice of assignment. That is, how should a travelling salesman travel starting from his home city (the city from where he started), visiting each city only once and returning to his home city, so that the total distance (cost or time) covered is minimum. For example, given n cities and distances dij (cost cij or time t ij) from city i to city j, the salesman starts from city 1, then any permutation of 2, 3, . . ., n represents the number of possible ways of his tour. Thus, there are (n – 1)! possible ways of his tour. Now the problem is to select an optimal route that is able to achieve the objective of the salesman. To formulate and solve this problem, let us define:
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 78 DIFFERENCE BETWEEN ASSIGNMENT PROBLEM AND TRAVELLING SALESMAN PROBLEM
Operations Research (MBA204) DEPARTMENT OF NBA , PESITM, SHIVAMOGGA 79 1 What is pure and mixed stragety? 3 2 compare Minimax and Maximin principle 3 3 Distinguish zero sum game and non zero sum game 3 4 What is assignement problem? 3 5 What is saddle point? 3 6 What are the objectives of Game theory 3 7 What do you mean by optimal stragegy and value of game with reference to game theory? 3 8 Difference between assignment and Travelling salesman problem 7
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 80 OPERATIONS RESEARCH MODULE-6 Project Management: Introduction, Construction of networks, Structure of projects, phases of project management-planning, scheduling, controlling phase, work breakdown structure, project control charts, network planning (Theory only) Critical path method to find the expected completion time of a project, determination of floats in networks, PERT networks, determining the probability of completing a project, predicting the completion time of project, INTRODUCTION A project involves a large number of interrelated activities (or tasks) that must be completed on or before a specified time limit, in a specified sequence (or order) with specified quality and minimum cost of using resources such as personnel, money, materials, facilities and/or space. Examples of projects include, construction of a bridge, highway, power plant, repair and maintenance of an oil refinery or an air plane; design, development and marketing of a new product, research and development work, etc. Since a project involves large number of interrelated activities, therefore it is necessary to prepare a plan for scheduling and controlling these activities (or tasks). This approach will help in identifying bottlenecks and even discovering alternate work-plan for the project. Network Analysis, Network Planning or Network Planning and Scheduling Techniques are used for planning, scheduling and controlling large and complex projects. These techniques are based on the representation of the project as a network of activities. A network is a graphical presentation of arrows and nodes for showing the logical sequence of various activities to be performed to achieve project objectives. PERT (Programme Evaluation and Review Technique) was developed in 1956–58 by a research team to help in the planning and scheduling of the US Navy’s Polaris Nuclear Submarine Missile project involving thousands of activities. The objective of the team was to efficiently plan and develop the Polaris missile system. This technique has proved to be useful for
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 81 projects that have an element of uncertainty in the estimation of activity duration, as is the case with new types of projects which have never been taken up before. CPM (Critical Path Method) was developed by E.I. DuPont company along with Remington Rand Corporation almost at the same time, 1956-58. The objective of the company was to develop a technique to monitor the maintenance of its chemical plants. This technique has proved to be useful for developing time-cost trade-off for projects that involve activities of repetitive nature. DIFFERENCE BETWEEN PERT AND CPM PHASES OF PROJECT MANAGEMENT In general, project management consists of three phases: Planning, Scheduling and Control. 1. Project planning phase:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 82 In order to understand the sequencing or precedence relationship among activities in a project, it is essential to draw a network diagram. The steps involved during this phase are listed below: (i) Identify various activities (tasks or work packages/elements) to be performed in the project, that is, develop a breakdown structure (WBS). (ii) Determine the requirement of resources such as men, materials, machines, money, etc., for carrying out activities listed above. (iii) Assign responsibility for each work package. The work packages corresponds to the smallest work efforts defined in a project and forms the set of tasks that are the basis for planning, scheduling and controlling the project. (iv) Allocate resources to work packages. (v) Estimate cost and time at various levels of project completion. (vi) Develop work performance criteria. (vii) Establish control channels for project personnel. 2. Scheduling phase: Once all activities have been identified and given unique codes, the project scheduling (when each of the activities is required to be performed) is taken up. Prepare an estimate of the likelihood of the project to be completed on or before the specified time. The steps involved during this phase are listed below: (i) Identify all people who will be responsible for each task. (ii) Estimate the expected duration(s) of each activity, taking into consideration the resources required for their execution in the most economic manner. (iii) Specify the interrelationship (i.e. precedence relationship) among various activities. (iv) Develop a network diagram, showing the sequential interrelationship between various activities. For this, tips such as; what is required to be done; why it must be done, can it be
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 83 dispensed with; how to carry out the job; what must precede it; what has to follow; what can be done concurrently, may be followed. (v) Based on these time estimates, calculate the total project duration, identify critical path; calculate floats; carry out resources smoothing (or levelling) exercise for critical (or scare) resources, taking into account the resource constraints (if any). 3. Project control phase: Project control refers to the evaluation of the actual progress (status) against the plan. If significant differences are observed, then remedial (modifying planning) or reallocation of resources measures are adopted in order to update and revise the uncompleted part of the project. PROJECT CONTROL CHARTS A project management chart is a graphical representation of the data related to a project. There are different types of project management charts that you can use to eliminate bottlenecks and make better decisions while developing projects. These charts also come in handy to streamline project activities, manage resources efficiently, and improve time management. The most notable thing about project management charts is that they make it easier to understand the complex project data. Gantt chart A Gantt chart provides you the timeline view of your projects. It allows you to visualize how different tasks/activities of a project are connected with each other and how they fit in the overall timeline of the project. A Gantt chart is basically a variation of the bar chart and is quite easy to interpret.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 84 PERT chart PERT is the acronym for Program Evaluation and Review Technique and is one of the most popular project management methodologies used in a wide variety of industries. A PERT chart represents the activities and milestones of a project in the form of a network diagram. Work breakdown structure (WBS) The work breakdown structure is an organized way of dividing a project into smaller manageable sections. In general, the WBS chart has a level 1 which contains the main tasks. The tasks at Level 1 are then divided into sub-tasks and listed in the downward direction.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 85 While the WBS has no stats or figures to display, it certainly is useful in simplifying the way you manage projects. It allows you to execute a project in a systematic manner and ensure proper resource allocation. Flowchart Projects that have several processes and have a complex flow of activities are difficult to manage. A flowchart is the best solution to simplify such types of projects and make your life easier when you are dealing with complicated projects. Cause-effect chart
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 86 The cause-effect chart allows managers to highlight all the potential causes that give rise to a particular problem. In general, the chart contains information about various causes and their effects that can lead to problems in a project. While creating a cause-effect chart, it is important that you include all the potential causes of an issue otherwise, it will become difficult to resolve the problem during the actual project development. Pareto chart A Pareto chart is the combination of a bar graph and a line graph. By using this chart, you can highlight some specific factors of your project. Typically, Pareto charts are used for the identification of problems and complications in a project. It helps you to identify the most common reasons for the occurrence of a problem and thus you can take appropriate actions to eradicate the problem.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 87 Control Chart If you want to monitor a certain project process, control charts are the best way to do it. This type of project management chart is popular for observing any erratic change in the process behavior, which makes it possible to identify problems at the early stages. Control charts offer a reliable way of determining the stability of a process. By ensuring the stability of various project processes, you can make sure that the project executes as smoothly as possible while facing minimum hindrances. PERT/CPM NETWORK COMPONENTS AND PRECEDENCE RELATIONSHIPS PERT/CPM network consists of two major components. Events Events in the network diagram represent project milestones, such as the start or the completion of an activity (task) or activities, and occur at a particular instant of time at which some specific part of the project has been or is to be achieved. Events are commonly represented by circles (nodes) in the network diagram.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 88 The events can be further classified into the following two categories: (i) Merge Event: An event which represents the joint completion of more than one activity is known as a merge event. (ii) Burst Event: An event that represents the initiation (beginning) of more than one activity is known as burst event. Events in the network diagram are identified by numbers. Each event should be identified by a number higher than that the one allotted to its immediately preceding event to indicate progress of work. The numbering of events in the network diagram must start from left (start of the project) to the right (completion of the project) and top to the bottom. Care should be taken that there is no duplication in the numbering. Activities Activities in the network diagram represent project operations (or tasks) to be conducted. As such each activity except dummy activity requires resources and takes a certain amount of time for completion. An arrow is commonly used to represent an activity with its head indicating the direction of progress in the project. Activities are identified by the numbers of their starting (tail or initial) event and ending (head, or terminal) event, for example, an arrow (i, j) between two events; the tail event i represents the start of the activity and the head event j represents the completion of the activity as shown in Fig. (a). The activities can be further classified into the following three categories: (i) Predecessor Activity: An activity which must be completed before one or more other activities start is known as predecessor activity.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 89 (ii) Successor Activity: An activity which starts immediately after one or more of other activities are completed is known as successor activity. (iii) Dummy Activity: An activity which does not consume either any resource and/or time is known as dummy activity. A dummy activity in the network is added only to establish the given precedence relationship among activities of the project. It is needed when (a) two or more parallel activities in a project have same head and tail events, or (b) two or more activities have some (but not all) of their immediate predecessor activities in common. A dummy activity is shown by a dotted line in the network diagram as shown in Fig. Network models use the following two types of precedence network to show precedence requirements of the activities in the project. Activity-on-Node (AON) network In this type of precedence network each node (or circle) represents a specific task while the arcs represent the ordering between tasks. AON network diagrams place the activities within nodes, and the arrows are used to indicate sequencing requirements. Generally, these diagrams have no particular starting and ending nodes for the whole project. The lack of dummy activities in these diagrams always make them easier to draw and to interpret.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 90 Activity-on-Arrow (AOA) network In this type of precedence network at each end of the activity arrow is a node (or circle). These nodes represent points in time or instants, when an activity is starting or ending. The arrow itself represents the passage of time required for that activity to be performed. These diagrams have a single beginning node from which all activities with no predecessors may start. The diagram then works its way from left to right, ending with a single ending node, where all activities with no followers come together. Three important advantages of using AOA are as follows: (i) Many computer programs are based on AOA network. (ii) AOA diagrams can be superimposed on a time scale with the arrows drawn, the correct length to indicate the time requirement. (iii) AOA diagrams give a better sense of the flow of time throughout a project. Rules for AOA Network Construction Following are some of the rules that have to be followed while constructing a network: 1. In network diagram, arrows represent activities and circles the events. The length of an arrow is of no significance. 2. Each activity should be represented only by one arrow and must start and end in a circle called event. The tail of an activity represents the start, and head the completion of work. 3. The event numbered 1 denotes the start of the project and is called initial event. All activities emerging (or taking off) from event 1 should not be preceded by any other activity or activities. An event carrying the highest number denotes the completion event. A network should have only one initial event and only one terminal event. 4. The general rule for numbering the event is that the head event should always be numbered larger than the number at its tail. That is, events should be numbered such that for each activity (i, j), i < j.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 91 5. An activity must be uniquely identified by its starting and completion event, which implies that: (a) An event number should not get repeated or duplicated. (b) Two activities should not be identified by the same completion event. (c) Activities must be represented either by their symbols or by the corresponding ordered pair of starting-completion events. 6. The logical sequence (or interrelationship) between activities must follow following rules: (a) An event cannot occur until all its incoming activities have been completed. (b) An activity cannot start unless all the preceding activities, on which it depends, have been completed. (c) Though a dummy activity does not consume either any resource of time, even then it has to follow the rules 6(a) and (b). ERRORS AND DUMMIES IN NETWORK Looping and Dangling Looping (cycling) and dangling are considered as faults in a network. Therefore, these must be avoided. (i) A case of endless loop in a network diagram, which is also known as looping, is shown in Fig. (a), where activities A, B and C form a cycle. Due to precedence relationships, it appears from Fig. (a) that every activity in looping (or cycle) is a predecessor of itself. In this case it is difficult to number three events associated with activity A, B and C so as to satisfy rule 6 of constructing the network.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 92 (ii) A case of disconnect activity before the completion of all activities, which is also known as dangling, is shown in Fig. (b). In this case, activity C does not give any result as per the rules of the network. The dangling may be avoided by adopting rule 5 of constructing the network Dummy (or Redundant) Activity The following are the two cases in which the use of dummy activity may help in drawing the network correctly, as per the various rules. (i) When two or more parallel activities in a project have the same head and tail events, i.e. two events are connected with more than one arrow.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 93 In Fig. (a), activities B and C have a common predecessor – activity A. At the same time, they have activity D as a common successor. To arrive at the correct network, a dummy activity for the ending event B to show that D may not start before B and C, is completed. This is shown in Fig. (b). (ii) When two chains of activities have a common event, yet are completely or partly independent of each other, as shown in Fig. (a). A dummy which is used in such a case, to establish proper logical relationships, is also known as logic dummy activity. In Fig. (a), if head event of C and D do not depend on the completion of activities A and B, then the network can be redrawn, as shown in Fig. (b). Otherwise, the pattern of Fig. (a) must be followed:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 94 CRITICAL PATH ANALYSIS The objective of critical path analysis is to estimate the total project duration and to assign starting and finishing times to all activities involved in the project. This helps to check the actual progress against the scheduled duration of the project. The duration of individual activities may be uniquely determined (in case of CPM) or may involve the three time estimates (in case of PERT), out of which the expected duration of an activity is computed. Having done this, the following factors should be known in order to prepare the project scheduling. (i) Total completion time of the project. (ii) Earlier and latest start time of each activity. (iii) Critical activities and critical path. (iv) Float for each activity, i.e. the amount of time by which the completion of a non-critical activity can be delayed, without delaying the total project completion time. Consider the following notations for the purpose of calculating various times of events and activities. Ei = Earliest occurrence time of an event, i. This is the earliest time for an event to occur when all the preceding activities have been completed, without delaying the entire project. Li = Latest allowable time of an event, i. This is the latest time at which an event can occur without causing a delay in project’s completion time. ESij = Early starting time of an activity (i, j). This is the earliest time an activity should start without affecting the project completion. LSij = Late starting time of an activity (i, j). This is the latest time an activity should start without delaying the project completion. EFij = Early finishing time of an activity (i, j). This is the earliest time an activity should finish without affecting the project completion.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 95 LFij = Late finishing time of an activity (i, j). This is the latest time an activity should finish without delaying the project completion. t ij = Duration of an activity (i, j). As mentioned earlier, a network diagram should have only one initial event and one end event. The other events are numbered consecutively with integer 1, 2, . . ., n, such that i < j for any two events i and j connected by an activity, which starts at i and finishes at j. Critical path is the longest path through the project network; the activities on the path are the critical activities, therefore any delay in their completion must be avoided to prevent delay in project completion. For calculating the earliest occurrence and latest allowable times for events, following two methods: Forward Pass method and Backward Pass method are used: Forward Pass Method (For Earliest Event Time) In this method, calculations begin from the initial event 1, proceed through the events in an increasing order of event numbers and end at the final event, say N. At each event, its earliest occurrence time (E) and earliest start and finish time for each activity that begins at that event is calculated. When calculations end at the final event N, its earliest occurrence time gives the earliest possible completion time of the project. The method may be summarized as follows: 1. Set the earliest occurrence time of initial event 1 to zero. That is, E1 = 0, for i = 1. 2. Calculate the earliest start time for each activity that begins at event i (= 1). This is equal to the earliest occurrence time of event, i (tail event). That is: ESij = Ei , for all activities (i, j) starting at event i. 3. Calculate the earliest finish time of each activity that begins at event i. This is equal to the earliest start time of the activity plus the duration of the activity. That is: EFij = ESij + t ij = Ei + tij, for all activities (i, j) beginning at event i.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 96 4. Proceed to the next event, say j; j > i. 5. Calculate the earliest occurrence time for the event j. This is the maximum of the earliest finish times of all activities ending into that event, that is, Ej = Max {EFij} = Max {Ei + tij }, for all immediate predecessor activities. 6. If j = N (final event), then earliest finish time for the project, that is, the earliest occurrence time EN for the final event is given by EN = Max { EFij} = Max { EN – 1 + tij}, for all terminal activities Backward Pass Method (For Latest Allowable Event Time) In this method, calculations begin from the final event N. Proceed through the events in the decreasing order of event numbers and end at the initial event 1. At each event, latest occurrence time (L) and latest finish and start time for each activity that is terminating at that event is calculated. The procedure continues till the initial event. The method may be summarized as follows: 1. Set the latest occurrence time of last event, N equal to its earliest occurrence time (known from forward pass method). That is, LN = EN , j = N. 2. Calculate the latest finish time of each activity which ends at event j. This is equal to latest occurrence time of final event. That is: LFij = Li , for all activities (i, j) ending at event j. 3. Calculate the latest start times of all activities ending at j. This is obtained by subtracting the duration of the activity from the latest finish time of the activity. That is:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 97 LFij = Lj and LSij = LFij – tij = Lj – tij, for all activity (i, j) ending at event j. 4. Proceed backward to the event in the sequence, that decreases j by 1. 5. Calculate the latest occurrence time of event i (i < j). This is the minimum of the latest start times of all activities from the event. That is: Li = Min {LSij} = Min {Lj – tij}, for all immediate successor activities. 6. If j = 1 (initial event), then the latest finish time for project, i.e. latest occurrence time L1 for the initial event is given by: L1 = Min {LSij} = Min{Lj–1 – tij}, for all immediate successor activities. Float (Slack) of an Activity and Event The float (slack) or free time is the length of time in which a non-critical activity and/or an event can be delayed or extended without delaying the total project completion time. Slack of an Event The slack (or float) of an event is the difference between its latest occurrence time (Li ) and its earliest occurrence time (Ei ). That is: Event float = Li – Ei It is a measure of how long an event can be delayed without increasing the project completion time. (a) If L = E for certain events, then such events are called critical events. (b) If L ≠ E for certain events, then the float (slack) on these events can be negative (L < E) or positive (L > E). Slack of an Activity It is the amount of activity time that can increased or delayed without delaying project completion time. This float is calculated as the difference between the latest finish time and the earliest finish time for the activity. There are three types of floats for each non-critical activity in a project.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 98 a) Total float: This is the length of time by which an activity can be delayed until all preceding activities are completed at their earliest possible time and all successor activities can be delayed until their latest permissible time. For each non-critical activity (i, j) the total float is equal to the latest allowable time for the event at the end of the activity minus the earliest time for an event at the begining of the activity minus the activity duration. That is: Total float (TFij) = (Lj – Ei ) – t ij = LSij – ESij = LFij – EFij b) Free float: This is the length of time by which the completion time of any non-critical activity can be delayed without causing any delay in its immediate successor activities. The amount of free float time for a non-critical activity (i, j) is computed as follows: Free float (FFij) = (Ej – Ei ) – t ij = Min {ESij , for all immediate successors of activity (i, j)} – EFij c) Independent float: This is the length of time by which completion time of any non-critical activity (i, j) can be delayed without causing any delay in its predecessor or the successor activities. Independent float time for each non-critical activity is computed as follows: Independent float (IFij) = (Ej – Li ) – t ij = {ESij – LSij} – t ij The negative value of independent float is considered to be zero. Remarks 1. Latest occurrence time of an event is always greater than or equal to its earliest occurrence time (i.e. Li ≥ Ei ), TFij ≥ (Lj – Ei ) – t ij This implies that the value of free float may range from zero to total float but will not exceed total float value. That is, Independent float ≤ Free float ≤ Total float. 2. The calculation of various floats can help the decision-maker in identifying the underutilized resources, flexibility in the total schedule and possibilities of redeployment of resources.
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 99 3. Total float for a non-critical activity may be viewed as follows: (a) Negative (i.e. L – E < 0): Project completion is behind the schedules date, i.e., resources are not adequate and activities may not finish in time. This needs extra resources or certain activities need crashing in order to reduce negative float value. (b) Positive (i.e. L – E > 0): Project completion is ahead of the schedule date, i.e., resources are surplus. These resources can be deployed elsewhere or execution of the activities can be delayed. (c) Zero (i.e. L = E): Resources are just sufficient for the completion of activities in a project. Any delay in activities execution will necessarily increase the project cost and time. Critical Path Certain activities in any project are called critical activities because delay in their execution will cause further delay in the project completion time. All activities having zero total float value are identified as critical activities, i.e., L = E The critical path is the sequence of critical activities between the start event and end event of a project. This is critical in the sense that if execution of any activity of this sequence is delayed, then completion of the project will be delayed. A critical path is shown by a thick line or double lines in the network diagram. The length of the critical path is the sum of the individual completion times of all the critical activities and defines the longest time to complete the project. The critical path in a network diagram can be identified as: (i) If Ei -value and Lj -value for any tail and head events is equal, then activity (i, j) between such events is referred as critical, That is, Ej = Lj and Ei = Li . (ii) On critical path Ej – Ei = Lj – Li = t ij. PROJECT SCHEDULING WITH UNCERTAIN ACTIVITY TIMES PERT was developed to handle projects where the time duration for each activity is not known with certainty but is a random variable that is characterized by β (beta)-distribution. To
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 100 estimate the parameters: mean and variance, of the β-distribution three time estimates for each activity are required to calculate its expected completion time. The three-time estimates that are required are as under. (i) Optimistic time (t o or a) The shortest possible time (duration) in which an activity can be performed assuming that everything goes well. (ii) Pessimistic time (t p or b) The longest possible time required to perform an activity under extremely bad conditions. However, such conditions do not include natural calamities like earthquakes, flood, etc. (iii) Most likely time (t m or m) The time that would occur most often to complete an activity, if the activity was repeated under exactly the same conditions many times. Obviously, it is the completion time that would occur most frequently (i.e. model value). The β-distribution is not necessarily symmetric, the degree of skewness depends on the location of t m to t o and t p. The range of optimistic time (t o) and pessimistic time (t p) is assumed to enclose every possible duration of the activity. The most likely completion time (t m) for an activity may not be equal to the midpoint (t o + t p)/2 and may occur to its left or to its right as shown in Fig. In Beta-distribution the midpoint (t o + t p)/2 is given half weightage than that of most likely point (t m). Thus, the expected or mean (t e or μ) time of an activity, that is also the weighted average of three time estimates, is computed as the arithmetic mean of (t o + t p)/2 and 2 t m. That is: event can be approximated by the normal distribution using statement of central limit theorem. Thus, the probability of completing the project on the schedule (or desired) time, Ts is given by:
Operations Research (MBA204) DEPARTMENT OF MBA, PESITM, SHIVAMOGGA 101 1 What is network analysis? 3 2 explain event ande activity in a network diagram 3 3 What is crashing in project 3 4 Explain the phases of Project management 7 5 Enumerate on the difference between PERT & CPM 7 6 What do you mean by crasing of the project? 3 7 What is redundant constraint? Explain with neat sketch 3 8 Explain looping and dangling errors in network 3 9 Briefly explain the rules for constructing network diagram 7 10 Describe the procedure to drawing CPM network 3 11 What is dummy activity? 3 12 Define dummy activity. What is the purpose of introducing dummy activity? 7 13 Differentiate between merge and burst event 3 14 Explain in details cost analysis in network 5 15 Write a short note on ES, EF, LS, LF and varous floats in project 10