Linear Programming: Application and Model Formulation PDF

CHAPTER TWO: LINEAR PROGRAMMING: APPLICATION AND MODEL FORMULATION INTRODUCTION In 1947, George Danzig developed the use of algebra for determining solutions to problems that involved the optimal allocation of scarce resources. In spite of numerous potential applicatio...

CHAPTER TWO: LINEAR PROGRAMMING: APPLICATION AND MODEL FORMULATION INTRODUCTION In 1947, George Danzig developed the use of algebra for determining solutions to problems that involved the optimal allocation of scarce resources. In spite of numerous potential applications in business, response to this new technique was low due to substantial computational burden, which is now removed with subsequent advances in computer technology and related software during the last three decades. The term linear implies that all the mathematical relations used in the problem are linear or straight-line relations, while the term programming refers to the method of determining a particular program or plan of action, i.e., the use of algorithms that is a well-defined sequence of steps that will lead to an optimal solution. Taken as a whole, the term linear programming refers to a family of mathematical techniques for determining the optimum allocation of resources and obtaining a particular objective when there are alternative uses of the limited or constrained resources. The technique of linear programming is applicable to problems in which the total effectiveness can be expressed as linear function of individual allocations and the limitations on resources give rise to linear equation or inequalities of the individual allocations. The usefulness of this technique is enhanced by the availability of several user-friendly soft wares such as STORM, TORA, QSB+, LINDO, etc. However, there is no general package for building an LP model. Model building is an art of practice. 2.1. LINEAR PROGRAMMING MODELS Linear programming models are mathematical representations of LP problems. Linear programming models have certain characteristics in common. Knowledge of these characteristics enables us to recognize problems that are amenable to a solution using LP models, and to be able to correctly formulate an LP model. These characteristics can be grouped as components and assumptions. The components relate to the structure of a model, whereas the assumptions reveal the conditions under which the model is valid. 2.1.1. COMPONENTS OF LP MODELS There are four major components of LP models including: Objective function, decision variables, constraints and parameters. 1 A) Objective and Objective Function The objective in problem solving is the criterion by which all decisions are evaluated. It provides the focus for problem solving. In linear programming models, a single, quantifiable objective must be specified by the decision maker. Because we are dealing with optimization, the objective will be either maximization or minimization. Hence, every LP problem will be either maximization or a minimization problem. Once the objective is specified, it becomes the measure of effectiveness against which alternate solutions are judged. An LP model consists of a mathematical statement of the objective called the objective function. B) Decision variables They represent unknown quantities to be solved for. The decision maker can control the value of the objective, which is achieved through choices in the levels of decision variables. For example, how much of each product should be produced in order to obtain the greatest profit? C) Constraints However, the ability of a decision maker to select values of the decision variables in an LP problem is subject to certain restrictions or limits coming from a variety of sources. The restrictions may reflect availabilities of resources (e.g., raw materials, labor time, etc.), legal or contractual requirements (e.g., product standards, work standards, etc.), technological requirements (e.g., necessary compressive strength or tensile strength) or they may reflect other limits based on forecasts, customer orders, company policies, and so on. In LP model, the restrictions are referred to as constraints. Only solutions that satisfy all constraints in a model are acceptable and are referred to as feasible solutions. The optimal solution will be the one that provides the best value for the objective function. Generally speaking, a constraint has four elements. Such as A right hand side (RHS) quantity that specifies the limit for that constraint. It must be a constant, not a variable. An algebraic sign that indicates whether the limit is an upper bound that cannot be exceeded, a lower bound that is the lowest acceptable amount, or an equality that must be met exactly. The decision variables to which the constraint applies. The impact that one unit of each decision variable will have on the right-hand side quantity of the constraint. Constraints can be arranged into three groups: System constraints – involve more than one decision variable, Individual constraints – involve only one variable, and 2 Non-negativity constraints – specify that no variable will be allowed to take on a negative value. The non-negativity constraints typically apply in an LP model, whether they are explicitly stated or not. D) Parameters The objective function and the constraints consist of symbols that represent the decision variables (e.g., X1, X2, etc.) and numerical values called parameters. The parameters are fixed values that specify the impact that one unit of each decision variable will have on the objective and on any constraint it pertains to as well as the numerical value of each constraint. The following simple example illustrates the components of LP models: 2.1.1. ASSUMPTIONS OF LP MODELS A) Linearity (proportionality) The linearity requirement is that each decision variable has a linear impact on the objective function and in each constraint in which it appears. In terms of a mathematical model, a function or equation is linear when the variables included are all to the power 1 (not squared, cubed, square root, etc.) and no products (e.g., x1x2) appear. On the other hand, the amount of each resource used (supplied) and its contribution to the profit (or cost) in the objective function must be proportional to the value of each decision variable. For example, if production of one unit requires 5 hours of a particular resource, then making 3 units of that product requires 15 hours ( 3x5) of that resource. 3 B) Divisibility (Continuity) The divisibility requirement pertains to potential values of decision variables. It is assumed that non-integer values are acceptable. However, if the problem concerns, for example, the optimal number of houses to construct, 3.5 do not appear to be acceptable. Instead, that type of problem would seem to require strictly integer solutions. In such cases, integer- programming methods should be used. It should be noted, however, that some obvious integer type situations could be handled under the assumption of divisibility. For instance, suppose 3.5 to be the optimal number of television sets to produce per hour, which is unacceptable, but it would result in 7 sets per two hours, which would then be acceptable. C) Certainty This requirement involves two aspects of LP models. One aspect relates to the model parameters, i.e., the numerical values. It is assumed that these values are known and constant. In practice, production times and other parameters may not be truly constant. Therefore, the model builder must make an assessment as to the degree to which the certainty requirement is met. Large departures almost surely will have a significant effect on the model. The other aspect is the assumption that all relevant constraints have been identified and represented in the model. D) 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 contributions (profit or cost) by 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 sum of resources used for A and B respectively. E) Non-negativity It assumes that negative values of variables are unrealistic and, therefore, will not be considered in any potential solutions. Only positive values and zero will be allowed and the non-negativity assumption is inherent in LP models. 4 2.1.2. Advantages of Linear Programming Following are certain advantages of linear programming.  Linear programming helps in attaining the optimum use of scarce productive resources. It also indicates how a decision maker can employ productive resources effectively by selecting and allocating these resources.  LP techniques improve quality of decisions. The decision making approach of the user of this technique becomes more objective and less subjective.  Highlighting of bottlenecks in the production process is one of the most advantages of this technique. For example, when a bottleneck occurs, some machines cannot meet demand while others remain idle for some of the time.  LP also helps in re-evaluation of a basic plan for changing conditions. If conditions change when the plan is carried out, they can be determined so as to adjust the remainder of the plan for best results. 2.1.3. Limitations of Linear Programming In spite of having many advantages and wide area of applications, there are some limitations associated with this technique. These are:  LP treats all relationships among decision variables as linear. However, generally neither the objective functions nor the constraints in real-life situations concerning business and industrial problems are linearly related to variables.  While solving an LP model, there is no guarantee that we will get integer valued solutions. For example, in finding out how many men and 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.  An LP model does not take in to consideration the effect of time and uncertainty. Thus, the LP model should be defined in such a way that any change due to internal as well as external factors can be incorporated.  It deals with only with a single objective, whereas in real-life situations we may come across conflicting multi-objective problems.  Parameters appearing in the model are assumed to be constant but, in real life situation they are frequently neither known nor constant. 5 2.1.1. FORMULATING LP MODELS Just as it is to define a problem, careful formulation of the model that will be used to solve the problem is important. Linear programming algorithms (solution techniques) are widely used and understood and computer packages are readily available for solving LP problems. Consequently, obtaining solutions is not the real issue, what is very important to note is failure to check that all constraints have been accounted for and have been correctly formulated results in ill-structuring of the model that can easily lead to poor decisions. Steps in formulating LP models:  Identify the decision variables.  Determine the objective function.  Identify the constraints.  Determine appropriate values for parameters and determine whether an upper limit, lower limit or equality is called for.  Use this information to build a model.  Validate the model. In many cases, the decision variables are obvious; in others it might require brief discussion with the appropriate manager. However, identifying the constraints and determining appropriate values for the parameters can require considerable time and effort. Potential sources of information include historical records, interviews with managers and staff, and data collection. Validating the model will involve a critical review of the output, perhaps under a variety of inputs, in order to decide if the results are reasonable. 2.2. LINEAR PROGRAMMING APPLICATIONS There is a wide range of problems that lend themselves to solution by linear programming techniques. This discussion is only meant to give an indication of the LP techniques for managerial decision making and the apparent diversity of situations to which linear programming can be applied. Some of these include production management (product mix, blending problems, production planning, Assembly line balancing…), Marketing management (media selection, traveling sales man problem, physical distribution), Financial management (portfolio selection, profit planning), agricultural application, military applications, personnel management (staffing problem, Determination of equitable salary and 6 etc. Product Mix Organizations often produce similar services that use the same resources. For example, labor, material cost, etc. because of limited resources available during any time period a decision must be made concerning how much of each product to produce or make available. Linear programming answers what mix of output (or service) will maximize profit given the availability of scarce resources Diet problem It usually involves the mixing of raw materials or other ingredients to obtain an end product that has certain characteristics. For example, what mix of inputs will achieve the desired results in the output for the least cost? Other applications that fall into this category include mixing feed for livestock, mixing pet foods, mixing building materials (concrete, mortar, paint), and so on. Portfolio selection These problems generally involve allocating a fixed dollar amount among a variety of investments, such as bonds, sockets, real states, etc. The goal usually is to maximize income or total return. The problems take on an added dimension when certain other requirements are specified (for example, no more than 40 percent of the portfolio can be invested in bonds). Practical Example for Product Mix 1. ABC private limited company is engaged in the production of power and traction transformers. Both of these categories of transformers pass through three basic processes: core preparation, core to coil assembly, and vapor phase drying. A power transformer yields a contribution of Birr 50,000 and traction transformer contributes Birr 10,000. The time required in the production of these two products in terms of hours for each of the processes is as follows. Power transformer Traction Transformer Core preparation 75 15 Core to Coil Assembly 160 30 Vapor Phase Drying 45 10 7 If the capacities available are 1000, 1500, and 750 machine hours in each processes Respectively, formulate the problem as LP? Solution Step1. Identify decision variables Since the products to be produced are power and traction transformers using the available resource to attain the objective set, we consider them as decision variables. This is because the organization‘s problem here is how many of each product to produce in order to attain the objective, which requires the management decision. Let X1 = the no of power transformers to be produced. X2= the no of traction transformer to be produced Step2. Determine Objective Function From the problem above, we understand that the problem is maximization problem. Hence, Zmax = 50,000X1+ 10,000X2 This is because, each unit of X1 contributes Birr 50,000 and X2 contributes Birr 10,000 to objective function. Step 3. Identify constraints Here we have two constraints: system (structural) and non-negativity constraints. The structural constraint is the amount of machine hours available in each process. Step 4. Determining Parameters Parameters are already identified in the table of the problem. Note: Step 3 and 4 can be performed simultaneously as: 75X1 + 15X2 < 1000 hrs- Core preparation process 160X1 + 30X2 < 1500 hrs- Core to Coil Assembly 45X1 + 10X2 < 750 hrs- Vapor Phase Drying X1, X2 > 0 Step 5. Building and validating the model Zmax = 50,000X1+ 10,000X2 Subject to: 75X1 + 15X2 < 1000 hrs 160X1 + 30X2 < 1500 hrs 45X1 + 10X2 < 750 hrs X1, X2 > 0 8  2.2. Solving LP Models Following the formulation of a mathematical model, the next stage in the application of LP to decision making problem is to find the solution of the model. An optimal, as well as feasible solution to an LP problem is obtained by choosing from several values of decision variables x1,x2…xn , the one set of values that satisfy the given set of constraints simultaneously and also provide the optimal ( maximum or minimum) values of the given objective function. The most common solution approaches are to solve graphically and algebraically the set of mathematical relationships that form the model, thus determining the values of decision variables. 2.2.1. Graphical linear programming methods Graphical linear programming is a relatively straightforward for determining the optimal solution to certain linear programming problems involving only two decision variables. Although graphic method is limited as a solution approach, it is very useful in the presentation of LP, in that it gives a ―picture‖ of how a solution is derived thus a better understanding of the solution. Moreover, graphical methods provide a visual portrayal of many important concepts. In this method, the two decision variables are considered as ordered pairs (X1, X2), which represent a point in a plane, i.e, X1 is represented on X-axis and X2 on Y-axis. Graphical method has the following advantages:  It is simple  It is easy to understand, and  It saves time. Steps to solve the given LP problem through Graphic method Step 1: Formulate the LP (Linear programming) problem Step 2: Construct a graph and plot the constraint lines Step 3: Determine the valid side of each constraint line Step 4: Identify the feasible solution region Step 5: Plot the objective function on the graph 9  Step 6: Find the optimum point Example In order to demonstrate the method, let us take a microcomputer problem in which a firm is about to start production of two new microcomputers, X1 and X2. Each requires limited resources of assembly time, inspection time, and storage space. The manager wants to determine how much of each computer to produce in order to maximize the profit generated by selling them. Other relevant information is given below: Type 1 Type 2 Profit per unit $60 $50 Assembly time per unit 4 hrs 10 hrs Inspection time per unit 2 hrs 1 hrs Storage space per unit 3 cubic feet 3 cubic feet Availability of company resources: Resources Assembly Amount available time Inspection time 100 hrs Storage space 22 hrs 39 cubic feet The model is then: Maximize 60X1 + 50X2 Subject to Assembly 4 X 1 +10 X 2 < 100 hrs Inspection 2 X 1 + 1 X 2 < 22 hrs Storage 3 X 1 + 3 X 2 < 39 cubic feet X1, X2 > 0 10  Graphical solution method involves the following steps. Step 1. Plot each of the constraints The step begins by plotting the non-negativity constraint, which restricts our graph only to the first quadrant. We then can deal with the task of graphing the rest of the constraints in two parts. For example, let us take the first constraint 4X1 + 10X2 < 100 hrs. First we treat the constraint as equality: 4X1 + 10X2 = 100. Then identify the easiest two points where the line intersects each axis by alternatively equating each decision variable to zero and solving for the other: when X1=0, X2 becomes 10 and when X2=0, X1 will be 25. We can now plot the straight line that is boundary of the feasible region as we have got two points (0, 10) and (25,0). Step 2. Identify the feasible region The feasible region is the solution space that satisfies all the constraints simultaneously. It is the intersection of the entire region represented by all constraints of the problem. We shade in the feasible region depending on the inequality sign. In our example above, for all the constraints except the non-negativity constraint, the inequality sign is ‗less than or equal to‘ and it represents region of the plane below the plotted lines. 11 Step 3. Locate the optimal solution. The feasible region contains an infinite number of points that would satisfy all the constraints of the problem. Point that will make the objective function optimum will be our optimal solution. This point is always found among the corner points of the solution space. Once the constraints are plotted and feasible region is determined, we use extreme point enumeration method 2.2.1.1. The Extreme Point Approach Corner or extreme point graphic method states that for problems that have optimal solutions, a solution will occur at the corner point in the case of unique solution, while in the case of multiple solutions, at least one will occur at a corner point as these multiple solutions will be combinations of those points between two corner points. The necessary steps for this approach is after graphing the problem, we determine the values of the decision variables at each corner point of the feasible region either by inspection or using simultaneous equations. We then substitute the values at each corner point into the objective function to obtain its value at each corner point and select the one with the highest value of the objective function (for a maximum problem) or lowest value (for a minimum problem) as the optimal solution. The constraints are connected with < sign. The solution space lies below the slant line and is bounded by the line segments. The origin and other points below the slant lines are in the solution space (i.e., feasible region) 12 Using this method for our example, simultaneously solving for corner points a, b, c, and d, we find corresponding profit values of 500, 700, 740, and 660, respectively giving us the same solution as the above one at C. Therefore, the optimal solution is X1= 9 units and X2 = 4 units while the optimal value of objective function is 740. Interpretation: For a firm to maximize its profit (740), it should produce 9 units of the Model I microcomputer and 4 units of model II. For a Minimization case Solving minimization problems involve where the objective functions (like cost function) will be minimum. The constraints are connected to RHS values with > sign. But, in real world problems, mixes of constraint is also possible. The value of RHS involves the lowest value of the constraint. The solution space lies above the slant lines and it is not enclosed. It extends indefinitely above the lines in the first quadrant. This means simply that cost increases without limit as more and more units are produced. The minimum cost will occur at a point along the inner boundary of the solution space. The origin and other points below the lines are not in the solution space. SLACK VERSUS SURPLUS Slack is the amount of a scarce resource that is unused by a given solution. Slack can potentially exist in a < constraint. Slack variables are considered in the objective function by using a coefficient of zero for each of them. When all the constraints are written as equalities after adding a slack variable to each of them, the linear program is said to be in standard form. For example, in the Assembly constraint 4X1 +10X2 < 100 hrs, the slack value is 100 – [4(9) +10(4)] = 24. 13 Surplus on the other hand is the amount by which the optimal solution causes a > constraint to exceed the required minimum amount. It can be determined in the same way that slack can, i.e., substitute the optimal values of the decision variables into the left side of the constraint and solve. The difference between the resulting value and the original right hand side amount is the amount of surplus. Surplus should also be accounted for in the objective function by using coefficients of zero like wise. 2.2.1.2. Graphical Solutions for the Special Cases of LP i) Unboundedness Unboundedness occurs when the decision variable increased indefinitely without violating any of the constraints. The reason for it may be concluded to be wrong formulation of the problem such as incorrectly maximizing instead of minimizing and/or errors in the given problem. Checking equalities or rethinking the problem statement will resolve the problem. Example: Max Z = 10X1 + 20X2 Subject to 2X1 + 4X2 > 16 X1 + 5X2 > 15 X 1, X 2 > 0 Following the above listed steps of graphical solution method, we find the following graph for the above model: The shaded area represents the set of all feasible solutions and as can be seen from the graph, the solution is unbounded. i) Redundant Constraints 14 In some cases, a constraint does not form a unique boundary of the feasible solution space. Such a constraint is called a redundant constraint. A constraint is redundant if its removal would not alter the feasible solution space. Redundancy of any constraint does not cause any difficulty in solving the LP problems graphically. Constraints appear redundant when it may be more binding (restrictive) than others.]# ii) Infeasibility In some cases after plotting all the constraints on the graph, feasible area (common region) that represents all the constraint of the problem cannot be obtained. In other words, infeasibility is a condition that arises when no value of the variables satisfy all the constraints simultaneously. Such a problem arises due to wrong model formulation with conflicting constraints. For example, Max Z = 3X1+2X2 Subject to:2X1 + X2 < 2 3X1 + 4X2 > 12 X1, X2 > 0 15  iii) Multiple optimal solutions Recall the optimum solution is that extreme point for which the objective function has the largest value. It is of course possible that in a given problem there may be more than one optimal solution. There are two conditions that should be satisfied for an alternative optimal solution to exist:  The given objective function is parallel to a constraint that forms the boundary of the feasible region. In other words, the slope of an objective function is the same as that of the constraint forming the boundary of the feasible region; and  The constraint should form a boundary on the feasible region in the direction of optimal movement of the objective function. In other words, the constraint should be an active constraint.  Note: The constraint is said to be an active or binding or tight, if at optimality the left hand side equals the right hand side. In other words, an equality constraint is always active. An inequality sign may or may not be active. For example Max Z = 8X1+16X2 Subject to: X1 + X2 < 200 ……. C1 3X1 + 6X2 < 900 ……. C2 X2 < 125 16  In the problem above, using extreme point method and solving for values of corner points simultaneously, the objective function assumes its maximum value of 2,400 at two corner points B (50,125) and C (100,100). Therefore, the optimal solution is found on the line segment connecting the two corner points. One benefit of having multiple optimal solutions is that for other (perhaps qualitative) reasons, a manager may prefer one of them to the others, even though each would achieve the same value of the objective function. In practical terms, one of the two corner points is usually chosen because of ease in identifying its values. Other corner points are computed by identifying the two corner points and keeping the value of the objective function constant, where 50  X1  100 and 100  X1  125. By selecting one value for one of the decision variables from the domain, we determine the value for another decision variable keeping the objective function‘s value. Let X1 = 80. Then, Z = 8X1+16X2  2400 = 8(80) +16X2 2 = 1760 X2 = 110 2.1.1. THE SIMPLEX METHOD The graphical method of solving linear programming problems is a simple way to find a solution since the optimum solution is searched among the corner points of the solution space. However, the graphical method is restricted to problems with two decision variables. When the number of variables and the number of constraints increase, it becomes difficult to visualize the solution space. As a result, the graphical method cannot be employed successfully in such cases. In order to avoid this limitation, the simplex method, or iterative or step by step method is efficient method for solving linear programming problems, which was developed by George B. Datzing in 1947. The simplex method is an algebraic procedure that starts with a feasible solution that is not optimal and systematically moves from one feasible solution to another until an optimal solution is found. Incase of the graphical approach, optimal solution occurs at the extreme points where the constraints intersect. Solutions where constraints intersect are called basic solutions, and those satisfying all of the constraints together with non-negativity constraints are called basic feasible solutions. Constraints are generally expressed using inequalities either in ‗less than‘ or ‗greater than‘ or in mixed form. Thus, constraints are not in standard form, meaning they should be converted 17  into equalities. To convert the inequality constraint into equality, we introduce slack or surplus variables. In economic terminology, slack variables represent unused capacity and surplus variables represent excess amount. The contribution (cost or profit) associated with the slack and surplus variables is zero. An inequality of the ‗less than or equal to‘ type is transformed into equality by introducing a non-negative slack variable, as follows: - Example Non Standard form Standard form X1+2X2