Operations Research Lecture Notes PDF

OPERATIONS RESEARCH LECTURE NOTES JANE ADUDA November 6, 2013 Contents LIST OF FIGURES v LIST OF TABLES viii COURSE...

OPERATIONS RESEARCH LECTURE NOTES JANE ADUDA November 6, 2013 Contents LIST OF FIGURES v LIST OF TABLES viii COURSE OUTLINE viii 1 Introduction 1 1.1 History of operations Research......................... 3 1.2 The Nature of Operations Research...................... 4 1.3 Operations Research Models.......................... 6 1.4 Solving the OR Model............................. 8 2 Linear programming 11 2.1 Basic Assumptions............................... 12 2.2 Mathematical Formulation of a LP model................... 13 2.2.1 The General Linear Programming Model............... 14 2.3 Resource Allocation Models.......................... 15 i Operations Research Jane Akinyi Aduda 2.3.1 Maximization problems......................... 15 2.3.2 Minimization problems......................... 18 2.4 Solution Methods for L.P. Problems...................... 20 2.4.1 Terminology for Solutions of the Model................ 21 3 Solving LP Problems 22 3.1 Graphical Method................................ 22 3.2 The Simplex Computations.......................... 27 3.2.1 Algebraic determination of corner points............... 29 3.2.2 The Simplex Algorithm......................... 30 3.3 The Transportation Problem.......................... 39 3.3.1 Finding Basic Feasible Solution for Transportation Problem.... 43 3.3.2 Methods to find the bfs for a balanced TP.............. 43 3.3.3 Northwest Corner Method (NWC).................. 44 3.3.4 Least-Cost Method........................... 45 3.3.5 Vogel Approximation Method (VAM)................. 46 3.3.6 Iterative Computations of the Transportation Algorithm...... 47 3.3.7 Maximization using the Transportation algorithm.......... 55 3.4 The Assignment Model............................. 56 3.4.1 Unbalanced assignment model..................... 63 3.4.2 Maximization using the Assignment algorithm............ 66 ii Operations Research Jane Akinyi Aduda 4 Inventory Models 68 4.1 Types of Inventory............................... 70 4.2 ABC Classification of Inventories....................... 71 4.2.1 A -Class Items............................. 71 4.2.2 B -class items.............................. 71 4.2.3 C -class items.............................. 72 4.3 Lot/Order Size Model with no Shortages or Basic EOQ Model....... 77 4.4 Derivation of Basic EOQ Model........................ 77 5 Network Optimization Models 80 5.1 Terminologies used in Networks........................ 81 5.2 The Shortest Path Problem.......................... 85 5.3 The Minimum Spanning Tree Problem.................... 86 5.4 The Maximum Flow Problem......................... 87 5.5 The Minimum Cost Flow Problem....................... 89 5.6 PERT/CPM Models for Project Management................ 90 5.6.1 Basic difference between PERT and CPM.............. 91 5.6.2 PERT/CPM Network Components And Precedence Relationship. 92 5.6.3 Critical Path Calculations....................... 95 5.6.4 Determination of the Critical Path.................. 95 5.6.5 Project Management PERT...................... 98 iii Operations Research Jane Akinyi Aduda 6 Waiting Line Theory or Queuing Model 100 6.1 QUEUING SYSTEM OR PROCESS..................... 101 6.1.1 Input Process.............................. 102 6.1.2 Service Mechanism or Service Facility................. 103 6.2 QUEUING PROBLEMS............................ 105 6.3 SYMBOLS USED IN QUEUING MODELS................. 106 6.3.1 Notations................................ 107 iv List of Figures 3.1 Graph of Marangi paint problem....................... 23 3.2 Graph For the X and Y Products....................... 25 3.3 Chicken Diet Problem............................. 26 3.4 Ozark Diet Problem.............................. 28 3.5 Algebraic Determination of corner points................... 30 3.6 Graphical Solution............................... 38 4.1 ABC analysis.................................. 74 v List of Tables 2.1 Data for a resource allocation Model..................... 14 2.2 Data for Marangi Paint Problem....................... 15 2.3 Data for Vitamin deficiency Problem..................... 18 2.4 Data for the Diet Problem........................... 19 3.1 Results for Marangi paint Problem...................... 23 3.2 Data for products X and Y........................... 24 3.3 Results for the X and Y products....................... 25 3.4 Ozark Diet Problem.............................. 26 3.5 Results for Ozark Diet Problem........................ 27 3.6 Corner Points.................................. 30 3.7 First Simplex Tableau............................. 32 3.8 Feasibility condition 1............................. 33 3.9 Second Simplex Tableau............................ 34 3.10 Feasibility condition 2............................. 34 3.11 Third Simplex Tableau............................. 35 vi Operations Research Jane Akinyi Aduda 3.12 Solution..................................... 35 3.13 Results for minimization Problem....................... 38 3.14 First Simplex Tableau (Dual)......................... 38 3.15 Second Simplex Tableau (Dual)........................ 38 3.16 Third (optimal) Simplex Tableau (Dual)................... 39 3.17 Shipping costs, Supply, and Demand for Powerco Example......... 41 3.18 NWC Starting Solution............................. 45 3.19 Least-Cost Method Starting Solution..................... 46 3.20 VAM Starting Solution............................. 47 3.21 Z-row coefficients................................ 48 3.22 Z-row coefficients................................ 49 3.23 Z-row coefficients................................ 49 3.24 First iteration.................................. 49 3.25 First iteration result.............................. 51 3.26 Second Table.................................. 51 3.27 Third Table................................... 52 3.28 Fourth Table.................................. 53 3.29 Assignment Model............................... 57 3.30 Assignment Model............................... 61 3.31 Assignment Model............................... 61 vii Operations Research Jane Akinyi Aduda 3.32 Assignment Model............................... 62 3.33 Assignment Model continued.......................... 62 3.34 Assignments solution 1............................. 63 3.35 Assignments solution 2............................. 63 3.36 Assignment Problem 1............................. 63 3.37 Assignment Problem 2............................. 64 5.1 Table for park problem............................. 86 5.2 VIVA Company Example............................ 94 viii Operations Research Jane Akinyi Aduda HBC 2122: OPERATIONS RESEARCH I PURPOSE: This course is aimed at providing students with concepts of Operations Research and their applications in business and other related areas. OBJECTIVES: At the end of this course the students should be able to:- Understand operations research techniques. Solve linear programming and optimization problems. Use operations research techniques to solve practical problems in business and management. SYLLABUS: History and nature of operations research. Linear Programming; simplex method,solution and its interpretation. application areas. Transportation model; using north-west method, least cost method, Vogel approximation method (VAM). Assignment model; formulation solution. Inventory models: periodic model, quan- tity models, basic economic order quantity, discounts, stock-out, buffer stock, ac- tivity based costing analysis, Pareto analysis, just in time (JIT) systems. Net- work model; deterministic, critical path analysis/ critical path method, probabilistic model, programme evaluation review technique, crashing, resource levelling. queu- ing model, single server and multi-server systems, Simulation: Introduction and ap- plication in queuing and inventory models. Game theory; pure and mixed strategies, SADDLE, dominance, graphical solution, solution by algebraic and linear program- ming method. PRE-REQUISITE: HBC 2211 MANAGEMENT MATHEMATICS II COURSE OUTLINE: Week 1-4 History and nature of operations research Linear Programming (i) Simplex method,solution and its interpretation ix Operations Research Jane Akinyi Aduda (ii) Application areas (iii) Transportation model (iv) Using northwest method, (v) Least cost method (vi) Vogel approximation method (VAM) Week 5-10 CAT I Assignment model; formulation and solution. Inventory models (i) Periodic model, (ii) Quantity models (iii) Basic economic order quantity (iv) Discounts, Stock-out, Buffer stock (v) Activity based costing analysis (vi) Pareto analysis (vii) Just in time (JIT) systems Network models (i) Deterministic, critical path analysis/ critical path method (ii) Probabilistic model, programme evaluation review technique (iii) Crashing, resource leveling (iv) Queuing model, single server and multiserver systems Week 11-14 CAT II Simulation: Introduction and application in queuing and inventory models. Game theory x Operations Research Jane Akinyi Aduda (i) Pure and mixed strategies (ii) SADDLE (iii) Dominance (iv) Graphical solution (v) Solution by algebraic and linear programming method. TEACHING METHODOLOGIES: In order to achieve the learning objectives stated above, the following learning and teaching methods will be used. (i) Lectures (ii) Independent Study (iii) Group discussions (iv) Tutorials INSTRUCTIONAL MATERIALS: These will include tablet, white board, comput- ers and teaching notes. COURSE ASSESMENT: CATS & assignments 30%, Written examination 70% REFERENCES: 1. Hamdy A. Taha, A.M. Natarajan, P. Balsubramanie and A. Tamilarasi. Operations Research (An Introduction),(2008). 2. Terry Lucey. Quantitative Techniques, 6th edition, (2002). 3. N.K Tiwari, Shishir K. Shandilya Operations Research. xi Chapter 1 Introduction Operational Research is an interdisciplinary branch of applied mathematics and formal science that uses methods such as mathematical modelling, statistics, and algorithms to arrive at optimal or near optimal solutions to complex problems. It is typically concerned with optimizing the maxima (profit, assembly line performance, crop yield, bandwidth, etc) or minima (loss, risk, etc.) of some objective function. Operations research helps management achieve its goals using scientific methods. According to the Operations Society of Great Britain, Operations Research is the application of the methods of science to complex problems arising in the direction and management of large systems of men, materials and money in industry, business, Govern- ment 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 outcome of alternative decisions, strategies or controls. The purpose is to help management to determine its policy and actions scientifically. It provides a facility to a decision maker to evaluate the given problems, identify alternative solutions, recognize the constraints and then assist the decision maker to have the best possible solution available, which is known as the optimal solution. It tries to avoid the dangers from taking decisions merely by guessing or by using thumb 1 Operations Research Jane Akinyi Aduda rules. Management is a multidimensional and dynamic concept. It is multidimensional in the sense that management problems and their solutions have consequences in several dimensions, such as human, economic, social and political fields. Also, the manager operates his system in an environment, which will never remain static, hence the dynamic nature. Hence any manager, while making decisions, must consider all aspects in addition to economic aspect, so that his solution should be useful in all aspects. The general approach is to analyse the problem in economic terms and then implement the solution if it is not aggressive or does not impact negatively on other aspects like humanity, social and political factors. In summary we can say operations research has the following features:- Operations Research uses Scientific Methods for making decisions. It is interdisciplinary approach for solving problems and it uses the knowledge and experience of experts in various fields. While analysing the problems all aspects are considered and examined and analysed scientifically for finding the optimal solution for the problem on hand. As operations research has scientific approach, it improves the quality of answers to the problems. Operations research provides a scientific base for decision-making and provides sci- entific substitute for judgement and intuition. In other words, operations research can be said to have the following characteristics 1. Operations Research is an interdisciplinary team approach. 2. Operations Research increases the creative ability of the decision maker. 3. Operations Research is a systems approach. 2 Operations Research Jane Akinyi Aduda 1.1 History of operations Research Since the advent of the industrial revolution, the world has seen a remarkable growth in the size and complexity of organizations. The artisans small shops of an earlier era have evolved into the billion-dollar corporations of today. An integral part of this revolutionary change has been a tremendous increase in the division of labour and segmentation of management responsibilities in these organizations. The results have been spectacular. However, along with its blessings, this increasing specialization has created new prob- lems, problems that are still occurring in many organizations. One problem is a tendency for the many components of an organization to grow into relatively autonomous empires with their own goals and value systems, thereby losing sight of how their activities and objectives mesh with those of the overall organization. What is best for one component frequently is detrimental to another, so the components may end up working at cross purposes. A related problem is that as the complexity and specialization in an organization in- crease, it becomes more and more difficult to allocate the available resources to the various activities in a way that is most effective for the organization as a whole. These kinds of problems and the need to find a better way to solve them provided the environment for the emergence of operations research (commonly referred to as OR). The roots of OR can be traced back many decades, when early attempts were made to use a scientific approach in the management of organizations. However, the beginning of the activity called operations research has generally been attributed to the military services early in World War II. Because of the war effort, there was an urgent need to allocate scarce resources to the various military operations and to the activities within each operation in an effective manner. Therefore, the British and then the U.S. military management called upon a large number of scientists to apply a scientific approach to dealing with this and other strategic and tactical problems. In effect, they were asked to do research on (military) operations. These teams of scientists were the first OR 3 Operations Research Jane Akinyi Aduda teams. By developing effective methods of using the new tool of radar, these teams were instrumental in winning the Air Battle of Britain. Through their research on how to better manage convoy and antisubmarine operations, they also played a major role in winning the Battle of the North Atlantic. Similar efforts assisted the Island Campaign in the Pacific. When the war ended, the success of OR in the war effort spurred interest in applying OR outside the military as well. As the industrial boom following the war was running its course, the problems caused by the increasing complexity and specialization in organizations were again coming to the forefront. It was becoming apparent to a growing number of people, including business consultants who had served on or with the OR teams during the war, that these were basically the same problems that had been faced by the military but in a different context. By the early 1950s, these individuals had introduced the use of OR to a variety of organizations in business, industry, and government. The rapid spread of OR soon followed. 1.2 The Nature of Operations Research As its name implies, operations research involves research on operations. Thus, opera- tions research is applied to problems that concern how to conduct and coordinate the operations (i.e., the activities) within an organization. The nature of the organization is essentially immaterial, and, in fact, OR has been applied extensively in such diverse areas as manufacturing, transportation, construction, telecommunications, financial planning, health care, the military, and public services, to name just a few. Therefore, the breadth of application is unusually wide. The research part of the name means that operations research uses an approach that resembles the way research is conducted in established scientific fields. To a considerable extent, the scientific method is used to investigate the problem of concern. (In fact, the term management science sometimes is used as a synonym for operations research.) In particular, the process begins by carefully observing and 4 Operations Research Jane Akinyi Aduda formulating the problem, including gathering all relevant data. The next step is to construct a scientific (typically mathematical) model that attempts to abstract the essence of the real problem. It is then hypothesized that this model is a sufficiently precise representation of the essential features of the situation that the conclusions (solutions) obtained from the model are also valid for the real problem. Next, suitable experiments are conducted to test this hypothesis, modify it as needed, and eventually verify some form of the hypothesis. (This step is frequently referred to as model validation.) Thus, in a certain sense, operations research involves creative scientific research into the fundamental properties of operations. However, there is more to it than this. Specifically, OR is also concerned with the practical management of the organization. Therefore, to be successful, OR must also provide positive, understandable conclusions to the decision maker(s) when they are needed. One way of summarizing the usual (overlapping) phases of an OR study is the follow- ing: 1. Define the problem of interest and gather relevant data. 2. Formulate a mathematical model to represent the problem. 3. Develop a computer-based procedure for deriving solutions to the problem from the model. 4. Test the model and refine it as needed. 5. Prepare for the ongoing application of the model as prescribed by management. 6. Implement. 5 Operations Research Jane Akinyi Aduda 1.3 Operations Research Models “The objective of Operations Research is to provide a scientific basis to the decision maker for solving the problems involving the interaction of various components of an organization by employing a team of scientists from various disciplines, all working together towards finding a solution which is in the best interest of the organization as a whole. The best solution thus obtained is known as optimal decision”. Imagine that you have a 5-week business commitment between Nairobi (NBI) and Kisumu (KSM). You fly out of Nairobi on Mondays and return on Wednesdays. A regular round-trip ticket costs shs.8,000, but a 20% discount is granted if the dates on the ticket span a weekend. A one-way ticket in either direction costs 75% of the regular price. How should you buy the tickets for the 5-week period? Consider this situation as a decision-making problem. Solving this requires the answer to the following three questions: 1. What are the decision alternatives? 2. Under what restrictions is the decision made? 3. What is the appropriate objective criterion for evaluating the alternatives? These three alternatives can be considered: 1. Buy five regular NBI-KSM-NBI for departure on Monday and return on Wednesday of the same week. 2. Buy one NBI-KSM, four KSM-NBI-KSM that span weekends and one KSM-NBI. 3. Buy one NBI-KSM-NBI to cover Monday of the first week and Wednesday of the last week and four KSM-NBI-KSM to cover the remaining legs. All tickets in this alternative span at least one weekend. 6 Operations Research Jane Akinyi Aduda The restriction on these options is that you should be able to leave NBI on Monday and return on Wednesday of the same week. An obvious objective criterion for evaluating the proposed alternative is the price of the tickets. The alternative that yields the smallest cost would be the best. Specifically, we have Alternative 1 cost = 5 × 8, 000 = kes 40, 000 Alternative 2 cost = (0.75 × 2 × 8, 000) + (4 × 0.8 × 8, 000) = kes 37, 600 Alternative 3 cost = 5 × 0.8 × 8, 000 = kes 32, 000 Option 3 looks like the best choice in this case. Although this example illustrates the three main components of an OR model, situa- tions differ in the details of how each component is developed and constructed. Consider forming a maximum-area rectangle out of a piece of wire of length L inches. Contrary to the example above, the number of alternatives are infinite (the length and width of the rectangle can assume an infinite set of values). The alternatives of this problem can be expressed as continuous (algebraic) variables. Let l= length and w= width of the rectangle in inches. The restrictions in the situation can be expressed verbally as: 1. Length + width of rectangle= Half the length of the wire. 2. Length and width cannot be negative. Algebraically, these restrictions can be translated as; 2(l + w) = L l ≥ 0, w ≥ 0 7 Operations Research Jane Akinyi Aduda Finally, the objective of the problem is maximization of the area of the rectangle. If we let z to be the area of the rectangle, then, the complete model becomes maximize z = lw subject to 2(l + w) = L and l, w ≥ 0 Based on these two examples, the general OR model can be given as Maximize or minimize an Objective Function subject to Constraints A solution of the model is feasible if it satisfies all the constraints, and optimal if, in addition yo being feasible, it yields the best (maximum or minimum) value of the objective function. Problem: identify a fourth feasible alternative for the tickets problem. 1.4 Solving the OR Model Generally, the type and complexity of the mathematical model dictates the nature of the solution method. The following are some of the tools that can be used. (i) Linear Programming Model- This model is used for resource allocation when the resources are limited and there are number of competing candidates for the use of resources. The model may be used to maximize the returns or minimize the costs. Consider the following situations: 8 Operations Research Jane Akinyi Aduda A manufacturing company wants to use their resources optimally and produce different quantities of each type of product, which yield different returns, so as to maximize the returns. This is a maximization problem A company manufacturing different types of alloys requires to purchase the three basic materials while at the same time maintaining the crucial percentage of basic materials in each alloy. This is to be done at the minimum cost. This is a minimization problem Both of these first two are resource allocation models. Number of factories are manufacturing the same commodities in different ca- pacities and the commodity is sent to various markets to meet the demands of the consumers. When the cost of transportation is known, linear programming is used to formulate a programme to distribute the commodity from factories to markets at the least possible cost. The model used is transportation model. When a company has number of orders on its schedule, which are to be pro- cessed on the same machines and the processing time, is known, then we have to allocate the jobs or orders to the machines, so as to complete all the jobs in minimum time. This we can also solve using the Assignment model. All the above-discussed models are Linear Programming Models. (ii) Sequencing Model- When a manufacturing firm has some job orders, which can be processed on two or more machines and the processing times of each job on each machine is known, then the problem of processing in a sequence to minimize the cost or time is known as Sequencing model. (iii) Waiting Line Model or Queuing Model-A model used for solving a problem where certain service facilities have to provide service to its customers, so as to avoid lengthy waiting line or queue, so that customers will get satisfaction from effective service and idle time of service facilities are minimized is waiting line model or queuing model. 9 Operations Research Jane Akinyi Aduda (iv) Replacement Model-Any capital item, which is continuously used for providing service or for producing the product is subjected to wear and tear due to usage, and its efficiency goes on reducing. This reduction in efficiency can be predicted by the increasing number of breakdowns or reduced productivity. The worn out parts or components are to be replaced to bring the machine back to work through maintenance. A time is reached when even the maintenance cost becomes too high and the manager feels replacement of the old machine by new one is the best thing to do. These type of problems and can be solved using replacement models. (v) Inventory Models-Any manufacturing firm has to maintain stock of materials for its use. This stock of materials, which are maintained in stores, is known as in- ventory. Inventory is one form of capital or money. The company has to maintain inventory at optimal cost. There are different types of inventory problems, depend- ing the availability and demand pattern of the materials. These can be solved by the application of inventory models. 10 Chapter 2 Linear programming A model, which is used for optimum allocation of scarce or limited resources to competing products or activities under such assumptions as certainty, linearity, fixed technology, and constant profit per unit, is a linear programming model. Linear Programming is one of the most versatile, powerful and useful techniques for making managerial decisions Linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Informally, linear program- ming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations. It is a mathematical technique concerned with the allocation of scarce resources. It is a procedure that optimizes the value of some objective function (maximizing profits or minimizing costs) when the factors involved (e.g. labour or machine hours) are subject to some constraints (e.g. only 1,000 labour hours available in a week). Problems to be solved must conform to the following: 1. The problem must be capable of being stated in numeric terms. 11 Operations Research Jane Akinyi Aduda 2. All factors involved in the problem must have a linear relationship. 3. The problem must permit a choice or choices between alternative courses of action. 4. There must be one or more restrictions in the factors involved. The programming part of a LP refers to the solution method. 2.1 Basic Assumptions Below are some of the important assumptions made when formulating a linear program- ming model: 1. The decision maker here is completely certain (i.e., deterministic conditions) regard- ing all aspects of the situation, such as availability of resources, profit contributions, technology, courses of action and their consequences etc. 2. The relationship between variables in the problem and the resources available is lin- ear. Here the term linearity implies proportionality and additivity. This assumption is very useful as it simplifies modelling of the problem. 3. We assume here fixed technology i.e., production requirements are fixed during the planning period and don’t change in the period. 4. The profit contribution of a product remains constant, irrespective of level of pro- duction and sales. 5. The decision variables are continuous meaning companies can manufacture products in fractional units e.g. 2.5 vehicles, 3.2 barrels of oil etc. This is referred to as the assumption of perfect divisibility. 6. Only one decision is required for the planning period. This condition shows that the linear programming model is a static model, implying that the linear programming 12 Operations Research Jane Akinyi Aduda problem is a single stage decision problem. (Note: Dynamic Programming problem is a multi-stage decision problem). 7. All variables are restricted to non-negative values (i.e., their numerical value will be ≥ 0). 2.2 Mathematical Formulation of a LP model The following steps are followed: 1. Study the given situation, find the key decision to be made. Hence, identify the decision variables(issues or factors in the problem whose values are to be determined) in the problem, specifying their units of measurement. 2. Formulate the objective function to be optimized and express it as a linear function of the decision variables (z=decision variables multiplied by their cost or profit contributions). 3. Formulate the constraints of the problem (these are imposed by resource availability) and express them as linear equalities or inequalities in terms of the decision variables. These are restrictions on the decision variables which arise due to limited resources. 4. Add non-negativity restrictions. The objective function, the set of constraints and the non-negativity restrictions together form the LP model. 13 Operations Research Jane Akinyi Aduda 2.2.1 The General Linear Programming Model In particular, this model is seeks to select the values for x1 , x2 ,..., xn so as to Optimize z = c1 x1 + c2 x2 +... + cn xn Subject to a11 x1 + a12 x2 +... + a1n xn (≤, =, ≥) b1 a21 x1 + a22 x2 +... + a2n xn (≤, =, ≥) b2.. (2.1). am1 x1 + am2 x2 +... + amn xn (≤, =, ≥) bm and x1 , x2 ,... , xn ≥ 0 This can then be summarized as n X Optimize z = cj x j j=1 n Subject to X aij xj (≤, =, ≥) bi , i = 1, 2,... , m (2.2) j=1 and xj ≥ 0, j = 1, 2,... , n or as in the table below Table 2.1: Data for a resource allocation Model Resource usage per unit of Activity Resource 1 2... n Amount of resource available 1 a11 a12... a1n b1 2 a21 a22... a2n b2.................. m am1 am2... amn bm Contribution to z c1 c2... cn per unit of activity where xj s are the decision variables and aij s, bi s and cj s are constants. 14 Operations Research Jane Akinyi Aduda 2.3 Resource Allocation Models 2.3.1 Maximization problems Here we mainly seek to maximize profits, revenue or output from a production process. Example 2.1 (Marangi Paint Problem). The Marangi Paint company produces both interior and exterior paints from two raw materials, M 1 and M 2. The following table provides the basic data for the problem: Table 2.2: Data for Marangi Paint Problem Tons of raw material Exterior paint Interior paint Maximum daily available (tons) Raw material M 1 6 4 24 Raw material M 2 1 2 6 Profit per ton ($ 1000) 5 4 A market survey indicates that, the daily demand for interior paint cannot exceed that of exterior paint by more than 1 ton. Also the maximum daily demand for interior paint is 2 tons. Marangi paint company wants to determine the optimum (best) product mix for interior and exterior paints that maximizes the daily profits. Solution: Step 1. Identify the decision variables. These are the amounts of exterior and interior paints that need to be produced. Let x1 and x2 represent the tons of exterior and interior paints to be produced daily respectively. Step 2. Formulate the objective function. The company wants to maximize profits. Letting z represent the total daily profit (in thousands of dollars), the objective function can be given as, maximize z = 5x1 + 4x2 15 Operations Research Jane Akinyi Aduda Step 3. Formulate the constraints that restrict raw material usage and express the demand. For raw material usage we have:- (usage of raw materials by both paints) ≤ (maximum raw material availability) From the data we have, 6x1 + 4x2 ≤ 24 Raw material M1 x1 + 2x2 ≤ 6 Raw material M2 For the demand restrictions we have the first one saying that the difference between the daily production of interior and exterior paints, x2 − x1 , does not exceed 1 ton. This translate to x2 − x1 ≤ 1. The second restriction stipulates that the maximum daily demand for interior paint is limited to two tons, which translates to x2 ≤ 2. Step 4. Add the non-negativity constraints. Therefore the complete Marangi Model is: maximize z = 5x1 + 4x2 subject to 6x1 + 4x2 ≤ 24 x1 + 2x2 ≤ 6 −x1 + x2 ≤ 1 x2 ≤ 2 and x1 , x2 ≥ 0 Example 2.2 (KICOMI Garment Problem). The KICOMI retail store stocks two types of shirts A and B, These are packed in attractive cardboard boxes. In one week the store can sell a maximum of 400 shirts of type A and a maximum of 300 shirts of type B. The storage capacity, however, is limited to a maximum of 600 of both types combined. 16 Operations Research Jane Akinyi Aduda Type A shirt fetches a profit of Kshs. 20/- per unit and type B a profit of Kshs. 50/- per unit. The store wants to establish how many of each type of shirt they need to stock per week in order to maximize their total profit. Formulate a mathematical model for this problem. Solution: Step 1. We require the decision variables with regard to the quantities we need to stock weekly. Let x1 and x2 represent the numbers of shirts A and B to be stocked weekly respectively Step 2. The store is seeking to maximize weekly profits. The profit contributions for types A and B are 20/- and 50/- per unit respectively, so if z represents the weekly profits for KICOMI store, then the objective function becomes z = 20x1 + 50x2 Step 3. We are limited by the sales and storage capacities so we consider the maximum sales and the maximum storage. The sales and storage constraints are given as x1 ≤ 400 x2 ≤ 300 x1 + x2 ≤ 600 Step 4. Finally x1 , x2 ≥ 0 The complete model is therefore given as maximize z = 20x1 + 50x2 subject to x1 ≤ 400 x2 ≤ 300 x1 + x2 ≤ 600 and x1 , x2 ≥ 0 17 Operations Research Jane Akinyi Aduda 2.3.2 Minimization problems For minimization we are interested in minimizing costs be they production, storage etc as well as time spent on production or deliveries and so on. Example 2.3 (Vitamin Deficiency Problem). A patient consults a doctor to check on his ill health. The Doctor finds him to be having deficiency of two vitamins, A and D. The patient is advised to consume vitamins A and D regularly for some time so as to regain his health. The doctor prescribes tonics I and II, both of which contain vitamins A, and D in certain proportions. He is also advised to consume at least 40 units of vitamin A and 50 units of vitamin D Daily. The costs of tonics I and II and the proportions of vitamins A and D that they contain are given in the table below. Formulate the linear programming model that minimizes the cost of tonics. Table 2.3: Data for Vitamin deficiency Problem Tonics Vitamins I II Daily requirements in units A 2 4 40 D 3 2 50 Cost per unit in Kshs. 50 30 Solution: Step 1. Let x1 and x2 represent the quantities of Tonic I and II that can be purchased Step 2. Let the total cost of purchasing these tonics be z. The objective function considering the costs becomes minimize z = 50x1 + 30x2 Step 3. We are limited by the proportion of each vitamin in the tonics and their mini- 18 Operations Research Jane Akinyi Aduda mum daily requirements. The constraints will then be given by 2x1 + 4x2 ≥ 40 Vitamin A constraint 3x1 + 2x2 ≥ 50 Vitamin D constraint Step 4. Finally x1 , x2 ≥ 0 In standard form, we have minimize z =50x1 + 30x2 subject to 2x1 + 4x2 ≥ 40 3x1 + 2x2 ≥ 50 and x1 , x2 ≥ 0 Example 2.4 (Diet Problem). Polly wonders how much money she must spend on food in order to get all the energy (2,000 kcal), protein (55 g), and calcium (800 mg) that she needs every day. She chooses six foods that seem to be cheap sources of the nutrients and collects her data in the following table of nutritive value per serving. She also decides to impose servings-per-day limits on all foods. Present this problem in standard form. Table 2.4: Data for the Diet Problem Energy Protein Calcium Price per serving Servings at Food Serving size (kcal) (g) (mg) (shillings) most per day Oat meal 28g 110 4 2 3 4 Chicken 100g 205 32 12 24 3 Eggs 2 large 160 13 54 13 2 Whole milk 237 cc 160 8 285 9 8 Cherry pie 170 g 420 4 22 20 2 Pork with beans 260 g 260 14 80 19 2 Solution: To design the most economical menu, she speculates about some as yet unspecified menu, 19 Operations Research Jane Akinyi Aduda consisting of x1 servings of oatmeal, x2 servings of chicken, and so on. She wants to find numbers x1 , x2 ,... , x6 that satisfy her self-imposed servings-per-day limits, meet the requirements for energy, protein, calcium, and yet minimize the cost. This diet problem can be nicely formulated as follows. minimize z = 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6 subject to 0 ≤ x1 ≤ 4 0 ≤ x2 ≤ 3 0 ≤ x3 ≤ 2 0 ≤ x4 ≤ 8 0 ≤ x5 ≤ 2 0 ≤ x6 ≤ 2 and 110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000 4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55 2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800 and x1 , x2 ,... , x6 ≥ 0 2.4 Solution Methods for L.P. Problems Linear Programming, is a method of solving the types of problems in which two or more candidates or activities compete to utilize the available limited resources, with a view of optimizing the objective function of the problem. The objective may be to maximize the returns or to minimize the costs. The various methods available to solve the problem are: 1. The Graphical Method:This method limits us to problems that have two decision variables in the problem. (To deal with more decision variables by the graphical method will become complicated, because we would have to deal with planes instead of straight lines). 2. The Systematic Trial and Error method, where we go on giving various values 20 Operations Research Jane Akinyi Aduda to variables until we get optimal solution. This method takes too much of time and laborious. 3. The Algebraic method. In this method each decision variable is considered as a vector and principles of vector algebra are used to get the optimal solution. This method is also time consuming. 4. The Simplex method. When the problem is having more than two decision vari- ables, simplex method is the most powerful method to solve the problem. It has a systematic algorithm used to solve the problem. 2.4.1 Terminology for Solutions of the Model In linear programming (and its extensions) any specification of values for the decision variables (x1 , x2 ,... , xn ) is called a solution, regardless of whether it is a desirable or even an allowable choice. Different types of solutions are then identified by using an appropriate adjective. A feasible solution is a solution for which all the constraints are satisfied. An infeasible solution is a solution for which at least one constraint is violated. The feasible region is the collection of all feasible solutions. However we can note that it is possible for a problem to have no feasible solutions. An optimal solution is a feasible solution that has the most favourable value of the objective function. Most problems will have just one optimal solution. However, it is possible to have more than one. Another possibility is that of having no optimal solutions. A corner-point feasible (CPF) solution is a solution that lies at a corner of the feasible region. Note that if a problem has exactly one optimal solution, it must be a CPF solution. If the problem has multiple optimal solutions, at least two must be CPF solutions. 21 Chapter 3 Solving LP Problems 3.1 Graphical Method Linear programming problems with two variables can be represented and solved graphi- cally with ease. Though in real-life, the two variable problems are practised very little, the interpretation of this method will help to understand the simplex method. The non negativity constraint implies the decision variables must have positive values and always lie in first quadrant of the graph. In graphical method, the inequalities (structural con- straints) are considered to be equations. Consider the Marangi Paint Problem which was summarized as maximize z =5x1 + 4x2 subject to 6x1 + 4x2 ≤ 24 x1 + 2x2 ≤ 6 −x1 + x2 ≤ 1 x2 ≤ 2 and x1 , x2 ≥ 0 Graphically, this can be expressed as shown in figure 3.1. To do this, we follow the following procedure:- 22 Operations Research Jane Akinyi Aduda Figure 3.1: Graph of Marangi paint problem Plot the inequalities as equalities and shade off the unwanted region (use broken lines for strict inequalities and bold lines for those “greater than or equal to”, or “less than or equal to” situations.) Identify all the corner points, pick their coordinates and plug them into the objective function. Pick the pair of points that give the optimal value of the objective function. From this graph, we obtain the results as shown in table 3.1. From these results we see that Marangi will maximize profits ($ 21,000) if they produce 3 tons of exterior paint and 1.5 tons of interior paint. Table 3.1: Results for Marangi paint Problem Corner Point Coordinates Value of Objective function A (0,0) 0 B (0,1) 4 C (1,2) 13 D (2,2) 18 E (3,1.5) 21 F (4,0) 20 23 Operations Research Jane Akinyi Aduda Consider the example below Example 3.1. A company manufactures two products, X and Y by using three machines A, B, and C. Machine A has 4 hours of capacity available during the coming week. Similarly, the available capacity of machines B and C during the coming week is 24 hours and 35 hours respectively. One unit of product X requires one hour of Machine A, 3 hours of machine B and 10 hours of machine C. Similarly one unit of product Y requires 1 hour, 8 hour and 7 hours of machines A, B and C respectively. When one unit of X is sold in the market, it yields a profit of shs.50/- per product and that of Y is shs.70/- per unit. Solve the problem by using graphical method to find the optimal product mix. The details given in the problem is given in table 3.2: Table 3.2: Data for products X and Y Products Machines (time required in hours) Available capacity in hours X Y A 1 1 4 B 3 8 24 C 10 7 35 Profit per unit in shs. 50 70 Let x and y be the units of X and Y to be produced by the company. The L.P. model is then given by maximize z =50x + 70y subject to x + y ≤ 4 3x + 8y ≤ 24 10x + 7y ≤ 35 and x, y ≥ 0 The plot is as shown in figure 3.3. The results are as shown in table 3.3 indicating they should produce 1.6 units of X and 2.4 units of Y so as to maximize profits(shs.248). 24 Operations Research Jane Akinyi Aduda Figure 3.2: Graph For the X and Y Products Table 3.3: Results for the X and Y products Corner Point Coordinates Value of Objective function A (0,0) 0 B (0,3) 210 C (1.6,2.4) 248 D (2.33,1.67) 233.33 E (3.48,0.03) 176 For minimization, Consider the problem below (The Chicken Diet Problem). On a chicken farm, the poultry is given a healthy diet to gain weight. The chicken have to consume a minimum of 15 units of Substance A and another 15 units of Substance B. In the market there are only two classes of compounds: Type X, with a composition of one unit of A to five units of B, and another type, Y, with a composition of five units of A to one of B. The price of Type X is $10 and Type Y, $30. What are the quantities of each type of compound that have to be purchased to cover the needs of the diet with a minimal cost? We can express this problem mathematically as follows:- Let x1 and x2 represent the quantities of Compounds X and Y to be purchased 25 Operations Research Jane Akinyi Aduda respectively. minimize z =10x1 + 30x2 subject to x1 + 5x2 ≥ 15 5x1 + x2 ≥ 15 and x1 , x2 ≥ 0 This is a very straight forward problem with only two constraints and thus the solution is at the intersection. The farm should purchase 2.5 units of each compounds at a cost of $100 as shown in figure 3.3. Figure 3.3: Chicken Diet Problem Consider the following minimization problem Example 3.2. Ozark farm uses at least 800 lb of special feed every day. This special feed is a mixture of corn and soyabean meal with the following compositions: The dietary Table 3.4: Ozark Diet Problem Per lb of foodstuff Feed stuff protein fibre Cost(shs/lb) Corn 0.09 0.02 0.30 Soyabean meal 0.60 0.06 0.90 requirements of the special feed are at least 30% protein and at most 5% fibre. Ozark Farm wishes to to determine the daily minimum-cost feed mix. 26 Operations Research Jane Akinyi Aduda Let x1 and x2 represent the lb of corn and soyabean meal in the daily mix respectively. The objective function seeks to minimize the total daily costs i.e. minimize z = 0.3x1 + 0.9x2 Because Ozark Farm needs at least 800 lb of feed everyday, the associated constraint can be expressed as x1 + x2 ≥ 800 As for the protein and fibre dietary constraints we need at least 30% and 5% of the total feed mix (x1 + x2 )lb, that is 0.09x1 + 0.60x2 ≥ 0.30(x1 + x2 ) which is also 0.21x1 − 0.30x2 ≤ 0 and 0.02x1 + 0.06x2 ≤ 0.05(x1 + x2 ) which is also 0.03x1 − 0.01x2 ≥ 0 Our problem can then be expressed as below: minimize z =0.3x1 + 0.9x2 subject to x1 + x2 ≥ 800 0.21x1 − 0.30x2 ≤ 0 0.03x1 − 0.01x2 ≥ 0 and x1 , x2 ≥ 0 This is the graphical representation and the results are at point C which is the optimal (cost minimizing) mix as seen in figure 3.4 as well as table 3.5 Table 3.5: Results for Ozark Diet Problem Corner Point Coordinates Value of Objective function B (200,600) 600 C (470.59,529.41) 437.65 3.2 The Simplex Computations The development of the simplex method computations is facilitated by imposing two requirements on the constraints of the problem. The two requirements help to standardize 27 Operations Research Jane Akinyi Aduda Figure 3.4: Ozark Diet Problem and streamline the calculations. 1. All constraints (with the exception of the non negativity of the variables) are equa- tions with a non-negative right hand side. 2. All the variables are non-negative. Converting inequalities into equations with non-negative RHS In (≤) constraints, the RHS represents a limit on the resource availability while the LHS represents the usage of resources by the activities of the model. RHS-LHS= unused or slack resources. To convert (≤) to =, add a slack variable to the LHS e.g. in the Marangi problem, the inequality 6x1 + 4x2 ≤ 24 becomes 6x1 + 4x2 + s1 = 24, where s1 ≥ 0 and s1 represents the unused amount of M1. (≥) constraints set a lower limit on the activities of the LP model so that LHS- RHS=surplus. The conversion of (≥) to = is achieved by subtracting a surplus amount from the LHS of the inequality.e.g in the vitamin deficiency problem, the 28 Operations Research Jane Akinyi Aduda inequality 2x1 + 4x2 ≥ 40 becomes 2x1 + 4x2 − S1 = 40, where S1 ≥ 0 NOTE:The equations must always have a non-negative RHS 3.2.1 Algebraic determination of corner points In a set of m × n equations with m < n, we set n − m variables equal to zero and solve the remaining equations for the remaining m variables. The resulting solution, if unique, is a basic solution and must conform to one of the corner points of the solution space. This means the maximum number of corner points is n! Cmn = m!(n − m)! Consider the following LP with two variables maximize z =2x1 + 3x2 subject to 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 5 and x1 , x2 ≥ 0 After converting the inequalities to equations we have maximize z =2x1 + 3x2 subject to 2x1 + x2 + s1 = 4 x1 + 2x2 + s2 = 5 and x1 , x2 , s1 , s2 ≥ 0 This system therefore has m = 2 equations and n = 4 unknowns. We therefore set n − m = 4 − 2 variables equal to zero and solve for the remaining 2 variables. We get the graph in figure 3.5 The corner points can be summarized as in table 3.6 29 Operations Research Jane Akinyi Aduda Figure 3.5: Algebraic Determination of corner points Table 3.6: Corner Points non basic Basic Basic Solution Corner points Feasible value of Obj. Func (x1 , x2 ) (s1 , s2 ) (4,5) A Yes 0 (x1 , s1 ) (x2 , s2 ) (4,-3) C No - (x1 , s2 ) (x2 , s1 ) (2.5,1.5) B Yes 7.5 (x2 , s1 ) (x1 , s2 ) (2,3) E Yes 4 (x2 , s2 ) (x1 , s1 ) (5,-6) F No - (s1 , s2 ) (x1 , x2 ) (1,2) D Yes 8 3.2.2 The Simplex Algorithm Rather than enumerate all the corner points as above, the simplex method only investi- gates a select few. It focuses solely on CPF solutions. For any problem with at least one optimal solution, finding one requires only finding a best CPF solution. Normally, the simplex method starts from the origin and seeks to find the next variable that gives the largest improvement to the objective function. The design of the simplex method calls for increasing one variable at a time. It deals with iterative process, which consists of first designing a Basic Feasible Solution or a Programme and proceed towards the OPTIMAL SOLUTION and testing each feasible solution for Optimality to know whether the solution on hand is optimal or not. If not an optimal solution, redesign the programme, and test for optimality until the 30 Operations Research Jane Akinyi Aduda test confirms OPTIMALITY. Hence we can say that the Simplex Method depends on two concepts known as Feasibility and optimality. The iterative steps of the simplex method are repeated until a finite optimal solution, if exists, is found. If no optimal solution, the method indicates that no finite solution exists. The Simplex procedure is as follows Step 1: Determine the starting basic feasible solution. Step 2: Select the entering variable using the optimality condition. This condition states that the entering variable in a maximization (minimization) problem is the non basic variable having the most negative (positive) coefficient in the z-row. Ties are broken arbitrarily. The optimum is reached at the iteration where all the z- row coefficients of the non-basic variables are non-negative (negative). Step 3: Select the leaving variable using the feasibility condition. For both maxi- mization and minimization problems, this condition states that the leaving variable is the basic variable associated with the smallest non-negative ratio (intercept i.e. ratio of the solution column to the constraint coefficients under the entering variable (pivot column)). Ties are broken arbitrarily. Step 4: Determine the new basic solution by using the appropriate Gauss- Jordan Computations and go to step two. The Gauss- Jordan row operations are 1. Pivot row: (a) Replace the leaving variable in the Basic column with the entering variable. (b) New pivot row=Current pivot row ÷ pivot element (the element at the inter- section of the pivot row and pivot column) 2. All other rows, including z: New row = (Current row) - (pivot column coefficient) × (New pivot row) 31 Operations Research Jane Akinyi Aduda MAXIMIZATION CASE Let us refer to the Marangi paint problem once again. We express the problem in this form. maximize z =5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4 subject to 6x1 + 4x2 + s1 = 24 x1 + 2x2 + s2 =6 −x1 + x2 + s3 =1 x2 + s4 = 2 and x1 , x2 , s1 , s2 , s3 , s4 ≥ 0 Next, we write the objective function as z − 5x1 − 4x2 = 0 This way the initial simplex tableau can be given as:- The first iteration starts at the Table 3.7: First Simplex Tableau Basic z x1 x2 s1 s2 s3 s4 Solution z 1 -5 -4 0 0 0 0 0 z-row s1 0 6 4 1 0 0 0 24 s1 -row s2 0 1 2 0 1 0 0 6 s2 -row s3 0 -1 1 0 0 1 0 1 s3 -row s4 0 0 1 0 0 0 1 2 s4 -row origin (where x1 = x2 = 0), leaving us with only the slack variables as basic. This tableau is not optimal and can be improved by increasing either x1 or x2. Since in this tableau, we have expressed out objective function as z − 5x1 − 4x2 = 0 we pick the variable with the most negative coefficient as the next entering variable (optimality condition), which in this case is x1. The column corresponding to the entering variable is called the pivot column. 32 Operations Research Jane Akinyi Aduda To identify the leaving variable, we compute the intercepts (ratios) and pick the vari- able with the minimum non-negative ratio. This identifies s1 as the leaving variable as shown in table 3.8 Table 3.8: Feasibility condition 1 Basic Entering x1 Solution Ratio (or intercept) 24 s1 6 24 x1 = 6 = 4 minimum 6 s2 1 6 x1 = 1 =6 1 s3 -1 1 x1 = −1 = −1 ignore 2 s4 0 2 x1 = 0 = ∞ ignore So for the next tableau, we swap x1 with s1 using the Gauss- Jordan operations. 1. Replace s1 in the basic column with x1 and calculate the coefficients of the new x1 as follows: New x1 -row= Current s1 -row ÷6 1 2 1 = (0, 6, 4, 1, 0, 0, 0, 24) = (0, 1, , , 0, 0, 0, 4) 6 3 6 all other rows including z, New row=(current row)-[(it’s pivot column coefficient)×(New pivot row)] 2. New z-row=current z-row-(-5)× new x1 -row, i.e. 2 1 2 5 (1, −5, −4, 0, 0, 0, 0, 0) − (−5) × (0, 1, , , 0, 0, 0, 4) = (1, 0, − , , 0, 0, 0, 20) 3 6 3 6 3. New s2 -row=current s2 -row-(1)× new x1 -row, i.e. 2 1 4 1 (0, 1, 2, 0, 1, 0, 0, 6) − (1) × (0, 1, , , 0, 0, 0, 4) = (0, 0, , − , 1, 0, 0, 2) 3 6 3 6 4. New s3 -row=current s3 -row-(-1)× new x1 -row, i.e. 2 1 5 1 (0, −1, 1, 0, 0, 1, 0, 1) − (−1) × (0, 1, , , 0, 0, 0, 4) = (0, 0, , , 0, 1, 0, 5) 3 6 3 6 33 Operations Research Jane Akinyi Aduda Table 3.9: Second Simplex Tableau Basic z x1 x2 s1 s2 s3 s4 Solution z 1 0 − 23 5 6 0 0 0 20 z-row 2 1 x1 0 1 3 6 0 0 0 4 x1 -row 4 s2 0 0 3 − 61 1 0 0 2 s2 -row 5 1 s3 0 0 3 6 0 1 0 5 s3 -row s4 0 0 1 0 0 0 1 2 s4 -row 5. New s4 -row=current s4 -row-(-1)× new x1 -row, i.e. 2 1 (0, 0, 1, 0, 0, 0, 1, 2) − (0) × (0, 1, , , 0, 0, 0, 4) = (0, 0, 1, 0, 0, 0, 1, 2) 3 6 This yields the second simplex tableau as shown in table 3.9 We can see that this tableau is not optimal as the objective function can still be improved. The next entering variable is x2 and using the feasibility condition we can identify the leaving variable to be s2 as shown in table 3.10 So we repeat the Gauss- Jordan row operations and they produce the Table 3.10: Feasibility condition 2 Basic Entering x2 Solution Ratio (or intercept) 2 2 x1 3 4 x2 = 4 ÷ 3 =6 4 4 s2 3 2 x2 = 2 ÷ 3 = 1.5 minimum 5 5 s3 3 5 x2 = 5 ÷ 3 =3 s4 1 2 x2 = 2 ÷ 1 = 2 following simplex tableau in 3.11. 1. New pivot x2 -row=current s2 -row ÷ 43 2. New z-row=current z-row −(− 23 )× New x2 -row 3. New x1 -row=current x1 -row −( 23 )× New x2 -row 4. New s3 -row=current s3 -row −( 35 )× New x2 -row 34 Operations Research Jane Akinyi Aduda Table 3.11: Third Simplex Tableau Basic z x1 x2 s1 s2 s3 s4 Solution 3 1 z 1 0 0 4 2 0 0 21 z-row 1 x1 0 1 0 4 − 12 0 0 3 x1 -row x2 0 0 1 − 18 3 4 0 0 3 2 x2 -row 3 s3 0 0 0 8 − 54 1 0 5 2 s3 -row 1 s4 0 0 0 8 − 34 0 1 1 2 s4 -row 5. New s4 -row=current s4 -row −(1)× New x2 -row Based on the optimality condition, none of the z-row coefficients associated with the non basic variables s1 and s2 are negative, hence this last tableau is optimal and the solution is interpreted as in table 3.12 Table 3.12: Solution Decision variable Optimal value Recommendation x1 3 Produce 3 tons of exterior paint daily 3 x2 2 Produce 1.5 tons of interior paint daily z 21 Daily profit is $21,000 Therefore in summary, to solve a linear programming problem in standard form, use the following steps. 1. Convert each inequality in the set of constraints to an equation by introducing slack variables. 2. Create the initial simplex tableau. 3. Locate the most negative entry in the z row. The column for this entry is called the entering column. (If ties occur, any of the tied entries can be used to determine the entering column.) 4. Form the ratios of the entries in the solution-column with their corresponding posi- tive entries in the entering column. The departing row corresponds to the smallest 35 Operations Research Jane Akinyi Aduda non-negative ratio (If all entries in the entering column are 0 or negative, then there is no maximum solution. For ties, choose either entry.) The entry in the departing row and the entering column is called the pivot element. 5. Use elementary row operations so that the pivot element is 1, and all other entries in the entering column are 0. This process is called pivoting. 6. If all entries in the bottom row are zero or positive, this is the final tableau. If not, go back to Step 3. 7. If you obtain a final tableau, then the linear programming problem has a maximum solution, which is given by the entry in the lower-right corner of the tableau. MINIMIZATION CASE Consider the minimization problem below minimize C =0.12x1 + 0.15x2 subject to 60x1 + 60x2 ≥ 300 12x1 + 6x2 ≥ 36 10x1 + 30x2 ≥ 90 and x1 , x2 ≥ 0 The basic procedure used to solve such a problem is to convert it to a maximization problem in standard form, and then apply the simplex method. The first step in converting this problem to a maximization problem is to form the augmented matrix for this system of inequalities. To this augmented matrix we add a last row that represents the coefficients of the objective function, as follows...   60 60. 300..    12 6. 36   ..      10 30. 90      ..............   0.12 0.15. 0 36 Operations Research Jane Akinyi Aduda Next, we form the transpose of this matrix by interchanging its rows and columns...   60 12 10. 0.12..      60 6 30. 0.15     ............... ..   300 36 90. 0 Note that the rows of this matrix are the columns of the first matrix, and vice versa. Finally, we interpret the new matrix as a maximization problem as follows. (To do this, we introduce new variables, y1 , y2 , and y3.) We call this corresponding maximization problem the DUAL of the original minimization problem. maximize Z =300y1 + 36y2 + 90y3 subject to 60y1 + 12y2 + 10y3 ≤ 0.12 60y1 + 6y2 + 30y3 ≤ 0.15 and y1 , y2 , y3 ≥ 0 As it turns out, the solution of the original minimization problem can be found by applying the simplex method to the new dual problem, as follows. This problem in equation form is maximize Z =300y1 + 36y2 + 90y3 + 0s1 + 0s2 subject to 60y1 + 12y2 + 10y3 + s1 = 0.12 60y1 + 6y2 + 30y3 + 0s1 + s2 = 0.15 and y1 , y2 , y3 , s1 , s2 ≥ 0 Graphically, this problem is solved as shown in figure 3.6 and the solution can be summarized as shown in table 3.13 from which we see that point C is optimal with x1 = 3, x2 = 2 and Z = 0.66 Using the simplex algorithm, the initial solution is in table 3.14 The other iterations are as shown in table 3.15 and 3.16 Thus, the solution of the dual maximization problem is Z = 0.66. This is the same value obtained by the graphical solution. The x-values corresponding to this optimal 37 Operations Research Jane Akinyi Aduda Figure 3.6: Graphical Solution Table 3.13: Results for minimization Problem Corner Point Coordinates Value of Objective function A (0,6) 0.90 B (1,4) 0.72 C (3,2) 0.66 D (9,0) 1.08 Table 3.14: First Simplex Tableau (Dual) Basic z y1 y2 y3 s1 s2 Solution Ratio z 1 -300 -36 -90 0 0 0 z-row 1 s1 0 60 12 10 1 0 0.12 s1 -row 500 1 s2 0 60 6 30 0 1 0.15 s2 -row 400 Table 3.15: Second Simplex Tableau (Dual) Basic z y1 y2 y3 s1 s2 Solution Ratio z 1 0 24 -40 5 0 3/5 z-row 0 y1 0 1 1/5 1/6 1/60 0 1/500 y1 -row 0.012 s2 0 0 -6 20 -1 1 0.03 s2 -row 0.0015 solution are obtained from the entries in the z-row corresponding to slack variable columns. In other words, the optimal solution occurs when x1 = 3 and x2 = 2. 38 Operations Research Jane Akinyi Aduda Table 3.16: Third (optimal) Simplex Tableau (Dual) Basic z y1 y2 y3 s1 s2 Solution z 1 0 12 0 3 2 0.66 z-row y1 0 1 0.25 0 0.0025 -1/120 0.00175 y1 -row y3 0 0 -3/10 1 -1/20 1/20 0.0015 s2 -row The fact that a dual maximization problem has the same solution as its original minimization problem is stated formally in a result called the von Neumann Duality Principle, after the American mathematician John von Neumann (1903-1957). 3.3 The Transportation Problem The general transportation problem is concerned (literally or figuratively) with distribut- ing any commodity from any group of supply centres, called sources, to any group of receiving centres, called destinations, in such a way as to minimize the total distribu- tion cost. Each source has a certain supply of units to distribute to the destinations, and each destination has a certain demand. A transportation problem basically deals with the problem, which aims to find the best way to fulfil the demand of n demand points using the capacities of m supply points. While trying to find the best way, generally a variable cost of shipping the product from one supply point to a demand point or a similar constraint should be taken into consideration. These problems can be solved by the simplex method; however, specialized algorithms have been developed which offer greater efficiency. The transportation problem has the following characteristics:- 1. There is a set of m supply points from which goods are shipped. Supply point i can supply at most si units. This is the amount of supply at source i 2. There is a set of n demand points to which the good is shipped. Demand point j must receive at least dj units of the shipped good. This is the amount of demand 39 Operations Research Jane Akinyi Aduda at destination j 3. Each unit produced at supply point i and shipped to demand point j incurs a variable cost of cij. The sources and destinations are represented by nodes. The routes linking the sources and destinations are denoted by arcs. Arc (i, j) joining source i to destination j caries two pieces of information. 1. The transportation cost per unit cij 2. The amount to be shipped xij The objective of the model is to determine the unknowns xij that will minimize the total transportation cost while satisfying all the supply and demand restrictions. Example 3.3. Powerco has three electric power plants that supply the electric needs of four cities. The associated supply of each plant and demand of each city is given in the table 3.17. The cost of sending 1 million kwh of electricity from a plant to a city depends on the distance the electricity must travel. Solution: Transportation tableau A transportation problem is specified by the supply, the demand, and the shipping costs. So the relevant data can be summarized in a transportation tableau. The trans- portation tableau implicitly expresses the supply and demand constraints and the shipping cost between each demand and supply point. 1. Decision Variable: Since we have to determine how much electricity is sent from each plant to each 40 Operations Research Jane Akinyi Aduda Table 3.17: Shipping costs, Supply, and Demand for Powerco Example From Destination Supply City 1 City 2 City 3 City 4 (Million kwh) Plant 1 $8 $6 $10 $9 35 Plant 2 $9 $12 $13 $7 50 Plant 3 $14 $9 $16 $5 40 Demand 45 20 30 30 (Million kwh) city; xij = Amount of electricity produced at plant i and sent to city j x14 = Amount of electricity produced at plant 1 and sent to city 4 2. Objective function Since we want to minimize the total cost of shipping from plants to cities; Minimize Z = 8x11 + 6x12 + 10x13 + 9x14 + 9x21 + 12x22 + 13x23 + 7x24 + 14x31 + 9x32 + 16x33 + 5x34 3. Supply Constraints: Since each supply point has a limited production capacity; x11 + x12 + x13 + x14 ≤ 35 x21 + x22 + x23 + x24 ≤ 50 x31 + x32 + x33 + x34 ≤ 40 4. Demand Constraints: x11 + x21 + x31 ≥ 45 x12 + x22 + x32 ≥ 20 x13 + x23 + x33 ≥ 30 x14 + x24 + x34 ≥ 30 41 Operations Research Jane Akinyi Aduda 5. Sign Constraints: Since a negative amount of electricity can not be shipped all xij ’s must be non negative; xij ≥ 0, (i = 1, 2, 3; j = 1, 2, 3, 4) The mathematical formulation of the transportation model is to determine the non- negative values of xij satisfying both availability (supply) and requirements (demand) constraints and minimizing the total cost of transportation. So we have m X X n minimize Z = xij cij i=1 j=1 Xn subject to xij = si , i = 1, 2,... , m j=1 m X xij = dj , j = 1, 2,... , n i=1 and xij ≥ 0, i = 1, 2,... , m; j = 1, 2,... , n Balanced Transportation Problem If Total supply equals to total demand, the problem is said to be a balanced transportation problem: m X n X si = dj i=1 j=1 All constraints must be binding becomes relatively easy to find a basic feasible solution Simplex pivots do not involve multiplication, they reduce to additions and subtrac- tions Therefore, it is desirable to formulate a transportation problem as a balanced trans- portation problem 42 Operations Research Jane Akinyi Aduda Balancing a Transportation problem if total supply exceeds total demand If total supply exceeds total demand, we can balance the problem by adding a dummy demand point. Since shipments to the dummy demand point are not real, they are assigned a cost of zero. Balancing a Transportation problem if total supply is less than total demand If a transportation problem has a total supply that is strictly less than total demand the problem has no feasible solution. However, it is sometimes desirable to allow the possibility of leaving some demand unmet: A penalty (cost) is often associated with the unmet demand To balance the problem, add a “dummy (or shortage) supply point” 3.3.1 Finding Basic Feasible Solution for Transportation Prob- lem Unlike other Linear Programming problems, a balanced Transportation Problem with m supply points and n demand points is easier to solve, although it has m + n equality constraints. The reason for that is, if a set of decision variables (xij s) satisfy all but one constraint, the values for xij s will satisfy that remaining constraint automatically. 3.3.2 Methods to find the bfs for a balanced TP There are three basic methods: 1. Northwest Corner Method 43 Operations Research Jane Akinyi Aduda 2. Minimum Cost Method 3. Vogel’s Method 3.3.3 Northwest Corner Method (NWC) To find the bfs by the NWC method; Begin in the upper left (north-west) corner of the transportation tableau and set x11 as large as possible (here the limitations for setting x11 to a larger number, will be the demand of demand point 1 and the supply of supply point 1. Your x11 value can not be greater than minimum of this 2 values). 1. Allocate as much as possible to the selected cell, and adjust the associated amount of supply and demand by subtracting the allocated amount. 2. Cross out the row or column with zero supply or demand to indicate that no further assignments can be made in that row or column. If both row and column are net to zero simultaneously, cross out only one, and leave a zero supply (demand) in the uncrossed out row (column) 3. If exactly one row or column is left uncrossed out, stop. Otherwise move to the cell to the right if a column has just been crossed out, or below if a row has been crossed out. Go to step 1. This is shown in figure 3.18 This gives a starting basic solution of Z = 35 × 8 + 10 × 9 + 12 × 20 + 13 × 20 + 16 × 10 + 5 × 30 = 280 + 90 + 240 + 260 + 160 + 150 = 1, 180 Note: The total number of allocations must be equal to m + n − 1, where m is the number of rows and n is the number of columns, otherwise the solution will be degenerate. 44 Operations Research Jane Akinyi Aduda Table 3.18: NWC Starting Solution From Destination Supply City 1 City 2 City 3 City 4 (Million kwh) $8 $6 $10 $9 Plant 1 35 35 $9 $12 $13 $7 Plant 2 10 20 20 50 $14 $9 $16 $5 Plant 3 10 30 40 Demand 45 20 30 30 (Million kwh) 3.3.4 Least-Cost Method The Northwest Corner Method dos not utilize shipping costs. It can yield an initial bfs easily but the total shipping cost may be very high. The minimum cost method uses shipping costs in order come up with a bfs that has a lower cost. To begin the minimum cost method, first we find the decision variable with the smallest shipping cost (xij ). Then assign xij its largest possible value, which is the minimum of si and dj. After that, as in the Northwest Corner Method we should cross out row i and column j and reduce the supply or demand of the non-crossed-out row or column by the value of xij. Then we will choose the cell with the minimum cost of shipping from the cells that do not lie in a crossed-out row or column and we will repeat the procedure. This is shown in figure 3.19 This gives a starting basic solution of Z = 30 × 5 + 20 × 6 + 15 × 8 + 30 × 9 + 20 × 13 + 10 × 16 = 150 + 120 + 120 + 270 + 260 + 160 = 1, 080 45 Operations Research Jane Akinyi Aduda Table 3.19: Least-Cost Method Starting Solution From Destination Supply City 1 City 2 City 3 City 4 (Million kwh) $8 $6 $10 $9 Plant 1 15 20 35 $9 $12 $13 $7 Plant 2 30 20 50 $14 $9 $16 $5 Plant 3 10 30 40 Demand 45 20 30 30 (Million kwh) 3.3.5 Vogel Approximation Method (VAM) VAM is an improved version of the Least-Cost Method, that generally, but not always, produces better starting solutions. 1. Start by computing each row and column a penalty. The penalty will be equal to the difference between the two smallest shipping costs in the row or column. 2. Identify the row or column with the largest penalty. Find the first basic variable which has the smallest shipping cost in that row or column. 3. Then assign the highest possible value to that variable, and cross-out the row or column as in the previous methods. Compute new penalties and use the same procedure. If a row and a column are satisfied simultaneously, only one of the two is crossed out, and the remaining row or column is assigned zero supply or demand. If exactly one row or column with zero supply or demand remains uncrossed-out stop. If one row (column) with positive supply (demand) remains uncrossed out, determine the basic variables in the row (column) by the least cost method. Stop. This is shown in figure 3.20. This gives a starting solution of 46 Operations Research Jane Akinyi Aduda Table 3.20: VAM Starting Solution From Destination Row Row Row Row Row Supply City 1 City 2 City 3 City 4 plty 1 plty 2 plty 3 plty 4 plty 5 (M kwh) Plant 1 $8 $6 $10 $9 2 2 2 1 2 35 10 25 Plant 2 $9 $12 $13 $7 2 3 3 3 1 50 45 5 Plant 3 $14 $9 $16 $5 4 5 40 10 30 plty 1 1 3 3 2 plty 2 1 3 3 plty 3 1 6 3 plty 4 1 3 plty 5 3 Demand 45 20 30 30 (M kwh) Z = 30 × 5 + 10 × 9 + 10 × 6 + 45 × 9 + 25 × 10 + 5 × 13 = 150 + 90 + 60 + 405 + 250 + 65 = 1, 020 3.3.6 Iterative Computations of the Transportation Algorithm After determining the starting solution (using any of the three methods discussed above), we use the following algorithm to determine the optimal solution. 1. Use the simplex optimality condition to determine the entering variable as the cur- rent non-basic variable that can improve the solution. If the optimality condition is satisfied, stop, otherwise go to step 2. 47 Operations Research Jane Akinyi Aduda 2. Determine the leaving variable using the simplex feasibility condition. Change the basis and return to step 1. The determination of the entering variable from among the current non-basic variables (those that are not part of the starting basic solution) is done by computing the non-basic coefficients in the Z-row using the method of multipliers. In the method of multipliers, we associate the multipliers ui and vj with row i and column j of the transportation tableau. For each current basic variable xij , ui + vj = cij for each basic xij Using the NWC starting solution, the initial basic feasible solution has 6 basic variables, leading to 6 equations with 7 unknowns. To solve these equations, the method of multi- pliers calls for arbitrary setting any u1 = 0 and then solving the remaining variables as shown in table 3.21 Table 3.21: Z-row coefficients Basic variable (u, v) equation Solution x11 u1 + v1 = 8 set u1 = 0 ⇒ v1 = 8 x21 u2 + v1 = 9 if v1 = 8 ⇒ u2 = 1 x22 u2 + v2 = 12 if u2 = 1 ⇒ v2 = 11 x23 u2 + v3 = 13 if u2 = 1 ⇒ v3 = 12 x33 u3 + v3 =