IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.
BBA/BCOM 2 All right are reserved with CU-IDOL Business Mathematics & Statistics Course Code: BBA102/BCM 102 Semester: First SLM Unit: 7 e-Lesson: 4 www.cuidol.in Unit 7 (BBA 102 /BCM 102)
Business Mathematics & Statistics 33 OBJECTIVES INTRODUCTION To make students aware of the concept of Linear In this unit we are going to learn about linear Programming programming To develop an understanding of graphical methods Under this you will learn how to solve linear of solution equations using graphical methods To make students understand how to solve linear In this unit you will learn the various business equations in various business problems problems and how to solve these problems . using linear programming www.cuidol.in Unit 7 (BBABA1/0B2C/OBMCM10120)2) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNerLvINedE LwEiAthRNCIUN-GIDOL
Topics To Be Covered 4 Introduction of Basic concept of Linear Programming Graphical Method of Solution Programming related to two variables mixed constraints; cases having no solution, multiple solutions, unbounded solution and redundant constraints www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Introduction of Linear 5 Programming The word linear means the relationship which can be represented by a straight line .i.e. the relation is of the Form ax +by=c. In other words it is used to describe the relationship between two or more variables which are proportional to each other. The word “programming” is concerned with the optimal allocation of limited resources. Linear programming is a way to handle certain types of optimization problems Linear programming is a mathematical method for determining a way to achieve the best outcome. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Definition of Linear Programming 6 A mathematical technique used to obtain an optimum solution in resource allocation problems, such as production planning. It is a mathematical model or technique for efficient and effective utilization of limited recourses to achieve organization objectives (Maximize profits or Minimize cost). When solving a problem using linear programming ,the program is put into a number of linear inequalities and then an attempt is made to maximize (or minimize) the inputs LP is a mathematical modeling technique useful for the allocation of “scarce or limited’’ resources such as labor, material, machine ,time ,warehouse space • ,etc…,to several competing activities such as • product ,service ,job, new equipments, projects, etc...on the basis of a given criteria of optimality www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Areas of Application of 7 Linear Programming Industrial Application Product Mix Problem Blending Problems Production Scheduling Problem Assembly Line Balancing Make-Or-Buy Problems Management Applications Media Selection Problems Portfolio Selection Problems Profit Planning Problems Transportation Problems Miscellaneous Applications Diet Problems Agriculture Problems Flight Scheduling Problems www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Advantages of Linear 8 Programming It helps in attaining optimum use of productive factors. It improves the quality of the decisions. It provides better tools for meeting the changing conditions. It highlights the bottleneck in the production process. Simplicity and easy way of understanding. Linear programming makes use of available resources To solve many diverse combination problems Helps in Re-evaluation process- linear programming helps in changing condition of the process or system. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Steps involved in Mathematical 9 programming It helps in attaining optimum use of productive factors. It improves the quality of the decisions. It provides better tools for meeting the changing conditions. It highlights the bottleneck in the production process. Simplicity and easy way of understanding. Linear programming makes use of available resources To solve many diverse combination problems Helps in Re-evaluation process- linear programming helps in changing condition of the process or system. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Linear Programming Model X1, X2, X3, ………, Xn = decision variables 10 Z = Objective function or linear function Requirement: Maximization of the linear function Z. …..Eq (1) Z = c1X1 + c2X2 + c3X3 + ………+ cnXn subject to the following constraints: where aij, bi, and cj are given co Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL www.cuidol.in
Characteristics of Linear 11 Programming 1. Decision or Activity Variables & Their Inter-Relationship. 2. Finite Objective Functions – clearly defined, unambiguous objective 3. Limited Factors/Constraints – availability of machines, hours, labors 4. Presence of Different Alternatives – should be present 5. Non-Negative Restrictions – negative – no value – must assume non negativity 6. Linearity Criterion – decision variable – must be direct proportional 7. Additivity –profit exactly equal to sum of all individual 8. Mutually Exclusive Criterion – occurrence of one variable rules out the simultaneous occur. Of such variable 9. Divisibility- factional values – need not be whole no. 10. Certainty- relevant parameters – fully and completely known 11. Finiteness – assume finite no. of activities or constraints – must – w/o this – not possible for optimal solution www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Assumptions in Linear 12 Programming Proportionality - The rate of change (slope) of the objective function and constraint equations is constant. Additivity - Terms in the objective function and constraint equations must be additive. Divisibility -Decision variables can take on any fractional value and are therefore continuous as opposed to integer in nature. Certainty - Values of all the model parameters are assumed to be known with certainty (non- probabilistic). www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Types of Linear 13 Programming Graphing and LP model helps provide insight into LP models and their solutions. While this can only be done in two dimensions, the same properties apply to all LP models and solutions. There are mainly two types of Linear Programming Graphical Method Simplex Method www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
LP Model Formulation 14 Product mix problem - Beaver Creek Pottery Company How many bowls and mugs should be produced to maximize profits given labor and materials constraints? Product resource requirements and unit profit: Resource Requirements Product Labor Clay Profit (Hr./Unit) (Lb./Unit) ($/Unit) Bowl Mug 1 4 40 2 3 50 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
15 Resource 40 hrs of labor per day 120 lbs of Availability: clay Decision x1 = number of bowls to produce per day Variables: x2 = number of mugs to produce per day Maximize Z Objective = $40x1 + $50x2 Function: Where Z = profit per day Resource Constraints: 1x1 + 2x2 40 hours of labor 120 4x1 + 3x2 pounds of clay Non-Negativity Constraints: X1 0; x2 0 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Complete Linear Programming Model: 16 Maximize Z = $40x1 + $50x2 subject to: 1x1 + 2x2 40 4x2 + 3x2 120 x1, x2 0 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Feasible Solution 17 A feasible solution does not violate any of the constraints: Example: x1 = 5 bowls x2 = 10 mugs Z = $40x1 + $50x2 = $700 Labor constraint check: Clay 1(5) + 2(10) = 25 < 40 hours constraint check: 4(5) + 3(10) = 70 < 120 pounds www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Infeasible Solution 18 An infeasible solution violates at least one of the constraints: Example: x1 = 10 bowls x2 = 20 mugs Z = $40x1 + $50x2 = $1400 Labor constraint check: 1(10) + 2(20) = 50 > 40 hours www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Graphical Solution of LP Models 19 Graphical solution is limited to linear programming models containing only two decision variables (can be used with three variables but only with great difficulty). Graphical methods provide visualization of how a solution for a linear programming problem is obtained. Graphical methods can be classified under two categories: 1. Iso-Profit(Cost) Line Method 2. Extreme-point evaluation Method. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right ar2e-r1e9served with CU-IDOL
20 X2 is mugs Maximize Z = $40x1 + $50x2 subject to: 1x1 + 2x2 40 4x2 + 3x2 120 x1, x2 0 X1 is bowls Figure 2.2 Coordinates for Graphical Analysis www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
21 Maximize Z = $40x1 + $50x2 subject to: 1x1 + 2x2 40 120 4x2 + 3x2 x1, x2 0 Figure 2.3 Graph of Labor Constraint www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
22 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4xx12, + 3x02 x2 Figure 2.4 Labor Constraint Area www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
23 Maximize Z = $40x1 + $50x2 subject to: 1x1 + 2x2 40 120 4x2 + 3x2 x1, x2 0 www.cuidol.in Figure 2.5 Clay Constraint Area All right are reserved with CU-IDOL Unit 7 (BBA 102 /BCM 102)
24 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.6 Graph of Both Model Constraints www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
25 Maximize Z = $40x1 + $50x2 subject to: 1x1 + 2x2 40 120 4x2 + 3x2 x1, x2 0 Figure 2.7 Feasible Solution Area www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
26 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.8 Objection Function Line for Z = $800 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
27 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.9 Alternative Objective Function Lines www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
28 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.10 Identification of Optimal Solution Point www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL2-25
29 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.11 Optimal Solution Coordinates www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are res2e- rved with CU-IDOL
30 Maximize Z = $40x1 + $50x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.12 Solutions at All Corner Points www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
31 Maximize Z = $70x1 + $20x2 40 subject to: 1x1 + 2x2 120 4x2 + 3x2 x1, x2 0 Figure 2.13 Optimal Solution with Z = 70x1 + 20x2 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Slack Variables 32 Standard form requires that all constraints be in the form of equations (equalities). A slack variable is added to a constraint (weak inequality) to convert it to an equation (=). A slack variable typically represents an unused resource. A slack variable contributes nothing to the objective function value. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Max Z = 40x1 + 50x2 + s1 + s2 33 subject to:1x1 + 2x2 + s1 = 40 All right are reserved with CU-IDOL 4x2 + 3x2 + s2 = 120 x1, x2, s1, s2 0 Where: x1 = number of bowls x2 = number of mugs s1, s2 are slack variables Figure 2.14 Solution Points A, B, and C with Slack www.cuidol.in Unit 7 (BBA 102 /BCM 102)
34 Two brands of fertilizer available - Super-gro, Crop-quick. Field requires at least 16 pounds of nitrogen and 24 pounds of phosphate. Super-gro costs $6 per bag, Crop-quick $3 per bag. Problem: How much of each brand to purchase to minimize total cost of fertilizer given following data. Chemical Contribution Brand Nitrogen Phosphate (lb/bag) (lb/bag) Super-gro Crop-quick 24 43 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
35 Decision Variables: x1 = bags of Super-gro x2 = bags of Crop-quick The Objective Function: Minimize Z = $6x1 + 3x2 Where: $6x1 = cost of bags of Super-Gro $3x2 = cost of bags of Crop-Quick Model Constraints: 16 lb (nitrogen constraint) 24 lb 2x1 + 4x2 (phosphate constraint) 4x1 + 3x2 0 (non-negativity constraint) x1, x2 www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
36 Minimize Z = $6x1 + $3x2 16 subject to: 2x1 + 4x2 24 4x2 + 3x2 x1, x2 0 Figure 2.16 Graph of Both Model Constraints www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
37 Minimize Z = $6x1 + $3x2 subject to: 2x1 + 4x2 16 24 4x2 + 3x2 x1, x2 0 www.cuidol.in Figure 2.17 Feasible Solution Area All right are reserved with CU-IDOL Unit 7 (BBA 102 /BCM 102)
38 Minimize Z = $6x1 + $3x2 subject to: 2x1 + 4x2 16 24 4x2 + 3x2 x1, x2 0 Figure 2.18 Optimum Solution Point www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Surplus Variables 39 A surplus variable is subtracted from a constraint to convert it to an equation (=). A surplus variable represents an excess above a constraint requirement level. A surplus variable contributes nothing to the calculated value of the objective function. Subtracting surplus variables in the farmer problem constraints: 2x1 + 4x2 - s1 = 16 (nitrogen) 4x1 + 3x2 - s2 = 24 (phosphate) www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Irregular types of LP Variables 40 For some linear programming models, the general rules do not apply. Special types of problems include those with: Multiple optimal solutions Infeasible solutions Unbounded solutions www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
41 The objective function is parallel to a constraint line. Maximize Z=$40x1 + 30x2 subject to: 1x1 + 2x2 40 120 4x2 + 3x2 x1, x2 0 Where: x1 = number of bowls x2 = number of mugs Figure 2.20 Example with Multiple Optimal Solutions www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Every possible solution 42 violates at least one constraint: All right are reserved with CU-IDOL Maximize Z = 5x1 + 3x2 subject to: 4x1 + 2x2 8 x1 4 x2 6 x1, x2 0 www.cuidol.in Figure 2.21 Graph of an Infeasible Problem Unit 7 (BBA 102 /BCM 102)
An Unbounded Problem 43 Value of the objective function increases indefinitely: Maximize Z = 4x1 + 2x2 subject to: x1 4 x2 2 x1, x2 0 Figure 2.22 Graph of an Unbounded Problem www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
44 ■ Hot dog mixture in 1000-pound batches. ■ Two ingredients, chicken ($3/lb) and beef ($5/lb). ■ Recipe requirements: at least 500 pounds of “chicken” at least 200 pounds of “beef ” ■ Ratio of chicken to beef must be at least 2 to 1. ■ Determine optimal mixture of ingredients that will minimize costs. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Step 1: 45 Identify decision variables. x1 = lb of chicken in mixture x2 = lb of beef in mixture Step 2: Formulate the objective function. www.cuidol.in Minimize Z = $3x1 + $5x2 All right are reserved with CU-IDOL where Z = cost per 1,000-lb batch $3x1 = cost of chicken $5x2 = cost of beef Unit 7 (BBA 102 /BCM 102)
Step 3: 46 All right are reserved with CU-IDOL Establish Model Constraints x1 + x2 = 1,000 lb x1 500 lb of chicken x2 200 lb of beef x1/x2 2/1 or x1 - 2x2 0 x1, x2 0 The Model: Minimize Z = $3x1 + 5x2 subject to: x1 + x2 = 1,000 lb x1 50 x2 200 x1 - 2x2 0 x1,x2 0 www.cuidol.in Unit 7 (BBA 102 /BCM 102)
47 Solve the following model graphically: Maximize Z = 4x1 + 5x2 subject to: x1 + 2x2 10 6x1 + 6x2 36 x1 4 x1, x2 0 Step 1: Plot the constraints as equations www.cuidol.in Figure 2.23 Constraint Equations All right are reserved with CU-IDOL Unit 7 (BBA 102 /BCM 102)
48 Maximize Z = 4x1 + 5x2 10 subject to: x1 + 2x2 36 6x1 + 6x2 x1 4 x1, x2 0 Step 2: Determine the feasible solution space Figure 2.24 Feasible Solution Space and Extreme Points www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right ar2e-r4e8served with CU-IDOL
49 Maximize Z = 4x1 + 5x2 subject to: x1 + 2x2 10 6x1 + 6x2 36 x1 4 x1, x2 0 Step 3 and 4: Determine the solution points and optimal solution Figure 2.25 Optimal Solution Point www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
SUMMARY 50 Linear Programming – Linear programming is an optimization technique for a system of linear constraints and a linear objective function. An objective function defines the quantity to be optimized, and the goal of linear programming is to find the values of the variables that maximize or minimize the objective function. Simplex Method- Simplex method, Standard technique in linear programming for solving an optimization problem, typically one involving a function and several constraints expressed as inequalities. The inequalities define a polygonal region (see polygon), and the solution is typically at one of the vertices. Graphical Method- Graphical method, or Geometric method, allows solving simple linear programming problems intuitively and visually. This method is limited to two or three problems decision variables since it is not possible to graphically illustrate more than 3D. www.cuidol.in Unit 7 (BBA 102 /BCM 102) All right are reserved with CU-IDOL
Search
