Maths Chapter 3: Introduction to Linear Programming PDF

UNIT 3: INTRODUCTION TO LINEAR PROGRAMMING 3.1 INTRODUCTION Linear programming- is an optimization method which shows how to allocate scarce resources in the best possible way subject to more than one limiting condition expressed in the form of inequalities and /or equations. It enables users to fi...

UNIT 3: INTRODUCTION TO LINEAR PROGRAMMING 3.1 INTRODUCTION Linear programming- is an optimization method which shows how to allocate scarce resources in the best possible way subject to more than one limiting condition expressed in the form of inequalities and /or equations. It enables users to find optional solution to certain problems in which the solution must satisfy a given set of requirements or constraints. Optimization in linear programming implies maximization (max) Profit, revenue, sales, market share or minimization (min) Cost, time, distance, or a certain objective function. Involves linearly related multi-variety functions i.e. functions with more than one independent variable. The goal in linear programming is to find the best solution given the constraints imposed by the problem, hence the term constrained optimization. 3.2 LINEAR PROGRAMMING MODELS LP models are mathematical representation of LP problems. Some models have a specialized format where as others have a more generalized format. Despite this, LPMs 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 correctly formulate an LP model. The characteristics can be grouped into two categories: Components and assumptions. assumptions. The components relate to the structure of a model, where as the assumptions describe the conditions under which the model is valid. Components Assumptions 1. Objective function 1. Linearity 2. Decision variables Model 2. Divisibility Model 3. Constraints Structure 3. Certainty Validity 4. Parameters and Right. 4. Non-negativity Hand Side Values 3.2.1 Components of LP Model a) The Objective function: is the mathematical/ quantitative expression of the objective of the company/ model. The objective in problem solving is the criterion by which all decisions are evaluated. In LPMs a single quantifiable objective must 58  be specified by the decision maker. For example, the objective might relate to profits, or costs or market share, best to only one of these. Moreover, because we are dealing with optimization, the objective will be either maximization or minimization, but not both at a time b) The Decision Variables: represent unknown quantities to be resolved for. These decision variables may represent such things as the: - number of units of different products to be sold - the # of dollars to invest in various projects - the # of ads to place with different media Since the decision maker has freedom of choice among actions, these decision variables are controllable variables. c) The constraints: are restrictions which define or limit the attainability (achievability) feasibility of a proposed course of action. They limit the degree to which the objective can be pursued. A typical restriction embodies scarce resources (such as labor supply, RMs, production capacity, machine time, storage space), legal or contractual requirements (leg. Product standards, work standards), or they may reflect other limits based on forecasts, customer orders, company policies etc. d) 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 to the numerical value of each constraint. The components are the building blocks of an LP model. We can better understand their meaning by examining a simple LP model as follows. Example: Maximize: Maximize: 4X1 + 7X2 + 5X3 (profit)… objective function subject to 2X1 + 3X2 + 6X3 300 labor hrs 5X1 + 4X3 200 raw mata. System 3X1 + 5X2 + 2X3 360 Constraints X1 = 30 Individual X1 – qty of product 1 X2 40 Constraints Variables Decision 59 X2 qty of product 2 X1, X2, X3 0 Non negativity constructs X3 qty of product 3 System constraints- constraints- involve more than one decision variables Individual constraint- constraint- involve only one decision variable. None-negativity constrains- constrains- 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. 3.2.2 Assumption of LP models a) Linearity The linearity requirement is that each decision variable has a linear impact on the objective function and in each constraint in which it appears. Taking the above example, producing one more unit of products add br. 4 to the total profit. This is true over the entire range of possible values of x1. The same applies (true) to each of the constraints. b) Divisibility: The divisibility requirement pertains to potential values of decision variables. If is assumed that non-integer values are acceptable. For example: 3.5 TV sets/ hr would be acceptable 7TV sets/ 2hr. c) Certainty: The parameters are known and constant. The certainty requirement involves two aspects of LP models. The constraint equations do not change. (1) With respect to model parameters (i.e. the numerical values) –If is assumed that these values are known and constant. Eg. In the above example each unit of product 1 requires 2 labor hours is known and remain constant, and also the 300 labor available is deemed to be known and constant. (2) All the relevant constraints identified and represented in the model are as they are. Non-negativity- The non-negativity constraint is that negative values of variables are d) Non-negativity- unrealistic and, therefore, will not be considered in any potential solutions, only positive values and zero will be allowed. 3.3 FORMULATING LP MODELS Once a problem has been defined, the attention of the analyst shifts to formulating a model. Just as it is important to carefully formulate the model that will be used to solve 60 the problem. If the LP model is ill formulated, ill-structured, it can easily lend to poor decisions. Formulating linear programming models involves the following steps: 1) Define the problem/ problems definition: definition: to determine the no. of type 1 and type 2 products to be produced per month so as to maximize the monetary profit given the restriction. 2) Identity the decision variables or represent unknown quantities. quantities. * Let X1 and X2 be the monthly quantities of type 1 and type 2 products. 3) Determine the objective function: Once the variables have been identified, the objective function can be specified. It is necessary to decide if the problem is maximization or a minimization problem and the coefficients of each decision variable. 4) Identify the constraints - system constraints- more than one variable - individual constraints- one variable - non-negativity constraints. Q(1) Check Your Progress Question 1. A firm that assembles computers computer equipment is about to start production of two new micro computers. Each type of microcomputer will require assembly time, inspection time, and storage space. The amount of each of there resources that can be devoted to the production of micro computers is limited. The manager of the firm would like to determine the quantity of each micro computer to produce in order to maximize the profit generated by sales of these microcomputers. Additional information In order to develop a suitable model of the problem, the manager has met with the design and manufacturing personnel. As a result of these meetings, the manager has obtained the following information: Type 1 Type 2 Profit per unit $ 60 $ 50 Assembly time per unit 4hrs 10hrs 61 Inspection time per unit 2hrs 1hr Storage space per unit 3 cubic ft 3 cubic ft The manager also has acquired information on the available company resources. These (weekly) amounts are: Resource Resource available Assembly time 100hrs Inspection time 22hrs Storage space 39cubic feet The manager has also met with the firms marketing manager and learned that demand for the micro computers was such that what ever combination of these two types of micro computers is produced, all of the output can be sold. Answer for the above check your progress question Step 1: 1: Problem definition - To determine the no. of two types of microcomputers to be produced (and sold) per week so as to maximize the weekly profit given the restrictions. Step 2: Variable representation - Let X1 and X2 be the weekly quantities of type 1 and type 2 microcomputers respectively. Step 3: Develop the objective function Maximize or Z max = 60X1 + 50X2 Step 4: Constraint identification  System constraints: 4X1 + 10X2 100hrs Assembly 2X1 + X2 22hrs Inspective 3X1 + 3X2 39 cub Feet Storage  Individual constraints ….No  Non-negativity constraint ….X1, X2 0 In summary, the mathematical model for the microcomputer problem is: Z max = 60X1 + 50X2 Subject to 4X1 + 10X2 100 62  2X1 + X2 22 3X1 + 3X2 39 X1, X2 0 Q(2) Check your progress 2. An electronics firm produces three types of switching devices. Each type involves a two-step assembly operation. The assembly times are shown in the following table: Assembly time per unit (minutes) Station 1 Station 2 Model A 2.5 3.0 Model B 1.8 1.6 Model C 2.0 2.2 7.5hr 7.5hr Each workstation has a daily working time of 7.5 hrs. The manager wants to obtain the greatest possible profit during the next five working days. Model A yields a profit of br. 8.25 per unit, Model B a profit of br 7.5 per unit and model C a profit of Br 7.8 per unit. Assume that the firm can sell all it produces. During this time, but it must fill outstanding orders for 20 units of each model type. Required. Required. Formulate the linear programming model of this problem. Solution for check your progress question number 2. Step 1: Problem definition: to determine the number of three types of searching devices to be produced to be produced and sold for the next 5 days (working) so as to maximize the 5 days profit. 2. Variable representation Let X1, X2, and X3 be the number of model A, B and C sketching devices to be produced and sold. 3. Develop objective function Z max = 8.25X1 + 7.50X2 + 7.80X3 4. Constraint identification System Constraints 63  2.5X1 + 1.8X2 + 2.0X3 450 minutes…Assembly time station 1 3.0X1 + 1.6X2 + 2.2X3 450 minutes…. Assembly time station2 X1 20 …. Model A Individual X2 20 ….Model B Constraints X3 20….Model C X1, X2, X3 0 ….no negativity Summary Z max = 8.25X1 + 7.50X2 + 7.8X3 Subject to: 2.5X1 + 1.8X2 + 2X3 450 3X1 + 1.6X2 + 2.2X3 450 X1 20 X2 20 X3 20 X1 X2 X3 0 3.4 SOLUTION APPROACHES TO LINEAR PROGRAMMING PROBLEMS There are two approaches to solve linear programming problems. 1. The graphic solution method 2. The algebraic solution/ simplex algorithm 3.4.1 The Graphic solution Method It’s a relatively straight forward method for determining the optional solution to certain linear programming problems. It gives us a clear picture. This method can be used only to solve problems that involve two decision variables. However, most linear programming applications involve situations that have more than two decision variables, so the graphic approach is not used to solve these. Example 1: Solving the micro-computer problem with graphic approach Z max: 60X1 + 50X2 S.t: 4X1 + 10X2 100 2X1 + X2 22 3X1 + 3X2 39 X1 X2 0 64 Steps 1. Plot each of the constraints and identify its region. 2. Identify the common region, which is all area that contains all of the points that satisfy the entire set of constraints. 3. Determine the optional solution-identify the point which leads to maximum benefit or minimum cost. 4X1 + 10X2 = 100 2X1 + X2 = 22 3X1 + 3X2 = 39 X1 0 25 X1 0 11 X1 0 13 X2 10 0 X2 22 0 X2 13 0 24 Region ABCDE is called feasible region (0 22) point C =? 2x1 + x2 = 22 x-3 20 3x1 + 3x2 = 39 -6x1 + 3x2 = -66 16 3x1 + 3x2 = 39 -3x1 = -27 12 x1 = -27/-3 = 9 E D 2(9) + x2 = 22 8 x2 = 22 – 18 = 4 Point D = 3x1 + 3x2 = 39 x - 4 4 C 4x1 + 10x2 = 100x3 = -12x1 + 12x2 = -156 12x1 + 30x2 = 300 0 18x2 = 144 A 4 8 B 12 16 20 24 x2 = 8 3x1 + 3(8) = 39 3x1 = 39 – 24 x1 = 15/3 = 5 To identity the maximum (minimum) value we use the corner point approach or the extreme point approach. The corner point/ extreme point approach has one theorem. It states that: For problems that have optional solutions, a solution will occur at an extreme, or corner point. Thus if a problem has a single optional solution, it will occur at a corner point. If it has multiple optional solutions, at least one will occur at a corner point consequently, in searching for an optional solution to a problem, we need any consider the extreme points because one of those must be optional. Further, determining the value of the objective 65 function at each corner point, we could identify the optional solution by selecting the corner point that has the best value (i.e. maximum or minimum, depending on the optimization case) of the objective function. Extreme points represent interactions of constraints. Determine the values of the decision variables at each corner point. Some times, this can be done by impaction (observation) and sometimes by simultaneous equation. Substitute the value of the decision variables at each corner point into the objective function to obtain its value at each corner point. After all corner points have been so evaluated, select the one with the highest or lowest value depending on the optimization case. Value of the obi Corner Coordinates How function Z = 60X1 + 50X2 Points X1 X2 determined? A 0 0 observation 0 br B 11 0 observation 660 br C 9 4 Simultaneous 740 br equation D 5 8 Simultaneous 700 br equation E 0 10 Observation 500 br Basic Solution X1 = 9 X2 = 4 Z = 740 Br. After we have got the optimal solution, solution, we have to substitute the value of the decision variables into the constraints and check whether all the resources available are used or not. If there are any unused resources we can use it for any other purpose. The amount of unused resource is known as slack- slack- the amount of a scarce resource that is unused by a given solution. The slack can range from zero, for a case in which all of a particular resource is used; to the original amount of the resource that was available (i.e. none of it is used.) Computing the amount of slack Originally unused Amount of slack 66  Amount used available (Available-used) Constraint X1 = 9 X2 = 4 Assembly 4(9) + 10(4) = 76 100 100 – 76 = 24 hrs Impective 2(9) 9+ 1(4) = 22 22 22 – 22 = 0 hr Storage 3(9) + 3(4) = 39 39 39 – 39 = 0 hr Constraints that have no slack are sometimes referred to as binding constraints since they limit or bind the solution. In the above cases, inspection time and storage space are binding constraints, while assembly time has slack. Knowledge of unused capacity can be useful for planning. A manager may be able to use the remaining assembly time for other products, or, perhaps to schedule equipment maintenance, safety seminars, training sermons or other activities Interpretation: The Company is advised to produce 9 units of type 1 micro computer and 4 units of type 2 micro computers per week to maximize its early profit to Br. 740 and in doing so the company would be left with unused resource of 24 assembly hrs which can be used for other purposes. Example 2: Solving the diet problem with graphic approach. C min = 5X1 + 8X2 10X1 + 30X2 140 10X1 + 30X2 = 140 20X1 + 15X2 145 X1 0 14 X1 , X2 0 X2 14/3 0 20X1 + 15X2 = 145 X1 0 +-25 X2 9.67 0 X2 12 8 A 4 B 0 X1 4 8 12 16 67  C 20X1 +15X2 = 145 Value of obj coordinates How determined Function cmin = 5X + 8X2 Points X1 X2 A 0 9.67 Observation 77.3 br. B 5 3 Simul. equn. 49 br. C 14 0 Observation 70 br. Basic solution X1 = 5 pounds X2 = 3 pounds C = 49 br. Interpretation to make the diet the minimum cost of br 49 we have to purchase 5 pounds of type 1 food and 3 pounds type 2 food. If there is a difference between the minimum required amount and the optimal solution, we call the difference surplus; that is: surplus 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: substitute the optimum 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 can potentially occur in a constraint. 68