logging in or signing up Definition of LPP anil.pari Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3120 Category: Education License: All Rights Reserved Like it (4) Dislike it (0) Added: November 05, 2008 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: satishgoenka (26 month(s) ago) thanks a lot.... it helped me a lot... tomorrow i have exam and dude this is going to help me for the thory part.... i owe u dude.. take care.. Saving..... Post Reply Close Saving..... Edit Comment Close By: ravidsr85 (38 month(s) ago) Nice Presentation Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript OPERATION RESEARCH : Wednesday, November 05, 2008 1 OPERATION RESEARCH Definition of LPP Content : Wednesday, November 05, 2008 2 Content Linear Programming (2) History of Linear Programming (3) Definition of LPP (4) Uses (5) Introduction with Example (6) Application Areas of Linear Programming (7) Basic Concept of Linear Programming Problem (8) Mathematical Formulation of Linear Programming Problems (9) Limitations of Linear Programming linear programming : Wednesday, November 05, 2008 3 linear programming A mathematical technique used to obtain an optimum solution in resource allocation problems, such as production planning. In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and inequality constraint. Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model given some list of requirements represented as linear equations History of linear programming : Wednesday, November 05, 2008 4 History of linear programming The problem of solving a system of linear inequalities dates back at least as far as Fourier, after whom the method of Fourier-Motzkinelimination is named. Linear programming arose as a mathematical model developed during thesecond world war to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. It was kept secret until 1947. Postwar, many industries found its use in their daily planning. Slide 5: Wednesday, November 05, 2008 5 The founders of the subject are George B. Dantzig, who published the simplex method in 1947, john vonNeumann, who developed the theory of the duality in the same year, and Leonid Kantorovich, a Russian mathematician who used similar techniques in economics before Dantzig and won the Nobel prize in 1975 in economics. The linear programming problem was first shown to be solvable in polynomial time by LeonidKhachiyan in 1979, but a larger major theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior point method for solving linear programming problems. Slide 6: Wednesday, November 05, 2008 6 Dantzig's original example of finding the best assignment of 70 people to 70 jobs exemplifies the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible optimal solutions that must be checked. Definition of LPP : Wednesday, November 05, 2008 7 Definition of LPP Linear programming deals with the optimization (Maximization or minimization) of a function of variables known as objective function, subject to a set of linear equations and/or inequalities known as constraint. The objective function may be profit, cost, production capacity or any other measure of effectiveness, which is to be obtained in the best possible or optimal manner. The constraint may be imposed by different resources such as market demand, production process and equipment, storage capacity, raw material availability, etc. Uses : Wednesday, November 05, 2008 8 Uses Linear programming is an important field of optimization for several reasons. Many practical problems in operation research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Slide 9: Wednesday, November 05, 2008 9 Likewise, linear programming is heavily used in microeconomics and business management, either to maximize the income or minimize the costs of a production scheme. Some examples are food blending, inventory management, portfolio and finance management, resource allocation for human and machine resources, planning advertisement campaigns, etc. Introduction : Wednesday, November 05, 2008 10 Introduction We are already familiar with graphical reorientation of linear equations and inequations. This chapter describes the application of linear equations and inequations in solving different kinds of practical problems. Let us consider few examples to understand what we mean by linear programming problem. Slide 11: Wednesday, November 05, 2008 11 Example1: Find two positive numbers whose sum is at least 15 and whose difference is at the most 7 such that their product is maximum. Before solving this problem, we have to state the problem Step 1: We have to choose two positive numbers. Let the two positive numbers be x and y. This x and y are decision variables. Slide 12: Wednesday, November 05, 2008 12 Step 2: Our object is to minimise the product xy. Let Z = xy. We have to maximise Z. Step 3: We have the following conditions on the variables x and y. a) Sum of the numbers is atleast 15 i.e., x + y >= 15 b) Difference of the numbers is at most 7 i.e., x - y <= 7 Slide 13: Wednesday, November 05, 2008 13 c) Since the x and y should be positive, we have two more conditions x > 0, y > 0 We call Z as objective function and the liner inequations x + y >=15 x - y <=7 x > 0, y > 0 as Linear constraints. The mathematical model for this problem is maximize the objective function Z = xy. Slide 14: Wednesday, November 05, 2008 14 Subject to the constraints x + y <= 15 x > 0, y > 0Linear Programming Problems (LPP) The standard form of the linear programming problem is used to develop the procedure for solving a general programming problem. Application Areas of Linear Programming : Wednesday, November 05, 2008 15 Application Areas of Linear Programming Transportation Problem Goods have to be transported from sources (like factories) to destinations (like warehouses) on a regular basis. The transportation problem deals with minimising the costs in doing so. Linear programming effectively deals with this problem. Military Applications To provide the required protection at the minimum cost, linear programming is used. This technique is useful to cause maximum damage to the enemy with minimum fuel/cost. Slide 16: Wednesday, November 05, 2008 16 Operation of System Of Dams Linear programming is used to find the variations in water storage of dams which generate power, thus maximising the energy got from the entire system. Personnel Assignment Problem If we are given the number of persons, number of jobs and the expected productivity of a particular person on a particular job, linear programming is used to maximise the average productivity of a person. Basic Concept of Linear Programming Problem : Wednesday, November 05, 2008 17 Basic Concept of Linear Programming Problem Objective Function Constraints Optimization Solution of a LPP Feasible Solution Optimal Solution Convex Region Non-convex Sets Objective Function : Wednesday, November 05, 2008 18 Objective Function The Objective Function is a linear function of variables which is to be optimised i.e., maximised or minimised. e.g., profit function, cost function etc. The objective function may be expressed as a linear expression. Constraints : Wednesday, November 05, 2008 19 Constraints A linear equation represents a straight line. Limited time, labour etc. may be expressed as linear inequations or equations and are called constraints. e.g., If 2 tables and 3 chairs are to be made in not more than 10 hours and 1 table is made in x hours while 1 chair is made in y hours, then this constraint may be written as A linear equation is also called a linear constraint as it restricts the freedom of choice of the values of x and y. Optimization : Wednesday, November 05, 2008 20 Optimization A decision which is considered the best one, taking into consideration all the circumstances is called an optimal decision. The process of getting the best possible outcome is called optimisation. The best profit is the maximum profit. Hence optizmizing the profit would mean maximising the profit. Optimising the cost would mean minimising the cost as this would be most favourable. Solution of a LPP : Wednesday, November 05, 2008 21 A set of values of the variables x1, x2,….xn which satisfy all the constraints is called the solution of the LPP. Solution of a LPP Feasible Solution : Wednesday, November 05, 2008 22 Feasible Solution A set of values of the variables x1, x2, x3,….,xn which satisfy all the constraints and also the non-negativity conditions is called the feasible solution of the LPP. Optimal Solution : Wednesday, November 05, 2008 23 Optimal Solution The feasible solution, which optimises (i.e., maximizes or minimizes as the case may be) the objective function is called the optimal solution. Convex Region : Wednesday, November 05, 2008 24 Convex Region A region is said to be a convex region, if for any two points of the region say (x1, y1) and (x2, y2) the line segment joining these points, is also in the region. Non-convex Sets : Wednesday, November 05, 2008 25 Non-convex Sets We know that the feasible solution of an LPP is a set. This set (If it is finite non-empty) is convex for any L.P.P. There are four types of feasible region normally we get : Wednesday, November 05, 2008 26 There are four types of feasible region normally we get Type 1: The region is totally empty, then there is no solution to the problem. Type 2: The region contains exactly one point, the point is optimal solution. Type 3: The region may be bounded convex set consisting of more than and point. Type 4: The region may be unbounded. Mathematical Formulation of Linear Programming Problems : Wednesday, November 05, 2008 27 Mathematical Formulation of Linear Programming Problems There are mainly four steps in the mathematical formulation of linear programming problem as a mathematical model. We will discuss formulation of those problems which involve only two variables. Identify the decision variables and assign symbols x and y to them. These decision variables are those quantities whose values we wish to determine. Identify the set of constraints and express them as linear equations/inequations in terms of the decision variables. These constraints are the given conditions. Identify the objective function and express it as a linear function of decision variables. It might take the form of maximizing profit or production or minimizing cost. Add the non-negativity restrictions on the decision variables, as in the physical problems, negative values of decision variables have no valid interpretation. Limitations of Linear Programming : Wednesday, November 05, 2008 28 Limitations of Linear Programming Linear programming is applicable only to problems where the constraints and objective function are linear i.e., where they can be expressed as equations which represent straight lines. In real life situations, when constraints or objective functions are not linear, this technique cannot be used. Factors such as uncertainty, weather conditions etc. are not taken into consideration. There may not be an integer as the solution, e.g., the number of men required may be a fraction and the nearest integer may not be the optimal solution. i.e., Linear programming techqnique may give practical valued answer which is not desirable. Only one single objective is dealt with while in real life situations, problems come with multi-objectives. Parameters are assumed to be constants but in reality they may not be so. Slide 29: Wednesday, November 05, 2008 29 Thank You You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Definition of LPP anil.pari Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3120 Category: Education License: All Rights Reserved Like it (4) Dislike it (0) Added: November 05, 2008 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: satishgoenka (26 month(s) ago) thanks a lot.... it helped me a lot... tomorrow i have exam and dude this is going to help me for the thory part.... i owe u dude.. take care.. Saving..... Post Reply Close Saving..... Edit Comment Close By: ravidsr85 (38 month(s) ago) Nice Presentation Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript OPERATION RESEARCH : Wednesday, November 05, 2008 1 OPERATION RESEARCH Definition of LPP Content : Wednesday, November 05, 2008 2 Content Linear Programming (2) History of Linear Programming (3) Definition of LPP (4) Uses (5) Introduction with Example (6) Application Areas of Linear Programming (7) Basic Concept of Linear Programming Problem (8) Mathematical Formulation of Linear Programming Problems (9) Limitations of Linear Programming linear programming : Wednesday, November 05, 2008 3 linear programming A mathematical technique used to obtain an optimum solution in resource allocation problems, such as production planning. In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and inequality constraint. Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model given some list of requirements represented as linear equations History of linear programming : Wednesday, November 05, 2008 4 History of linear programming The problem of solving a system of linear inequalities dates back at least as far as Fourier, after whom the method of Fourier-Motzkinelimination is named. Linear programming arose as a mathematical model developed during thesecond world war to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. It was kept secret until 1947. Postwar, many industries found its use in their daily planning. Slide 5: Wednesday, November 05, 2008 5 The founders of the subject are George B. Dantzig, who published the simplex method in 1947, john vonNeumann, who developed the theory of the duality in the same year, and Leonid Kantorovich, a Russian mathematician who used similar techniques in economics before Dantzig and won the Nobel prize in 1975 in economics. The linear programming problem was first shown to be solvable in polynomial time by LeonidKhachiyan in 1979, but a larger major theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior point method for solving linear programming problems. Slide 6: Wednesday, November 05, 2008 6 Dantzig's original example of finding the best assignment of 70 people to 70 jobs exemplifies the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible optimal solutions that must be checked. Definition of LPP : Wednesday, November 05, 2008 7 Definition of LPP Linear programming deals with the optimization (Maximization or minimization) of a function of variables known as objective function, subject to a set of linear equations and/or inequalities known as constraint. The objective function may be profit, cost, production capacity or any other measure of effectiveness, which is to be obtained in the best possible or optimal manner. The constraint may be imposed by different resources such as market demand, production process and equipment, storage capacity, raw material availability, etc. Uses : Wednesday, November 05, 2008 8 Uses Linear programming is an important field of optimization for several reasons. Many practical problems in operation research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Slide 9: Wednesday, November 05, 2008 9 Likewise, linear programming is heavily used in microeconomics and business management, either to maximize the income or minimize the costs of a production scheme. Some examples are food blending, inventory management, portfolio and finance management, resource allocation for human and machine resources, planning advertisement campaigns, etc. Introduction : Wednesday, November 05, 2008 10 Introduction We are already familiar with graphical reorientation of linear equations and inequations. This chapter describes the application of linear equations and inequations in solving different kinds of practical problems. Let us consider few examples to understand what we mean by linear programming problem. Slide 11: Wednesday, November 05, 2008 11 Example1: Find two positive numbers whose sum is at least 15 and whose difference is at the most 7 such that their product is maximum. Before solving this problem, we have to state the problem Step 1: We have to choose two positive numbers. Let the two positive numbers be x and y. This x and y are decision variables. Slide 12: Wednesday, November 05, 2008 12 Step 2: Our object is to minimise the product xy. Let Z = xy. We have to maximise Z. Step 3: We have the following conditions on the variables x and y. a) Sum of the numbers is atleast 15 i.e., x + y >= 15 b) Difference of the numbers is at most 7 i.e., x - y <= 7 Slide 13: Wednesday, November 05, 2008 13 c) Since the x and y should be positive, we have two more conditions x > 0, y > 0 We call Z as objective function and the liner inequations x + y >=15 x - y <=7 x > 0, y > 0 as Linear constraints. The mathematical model for this problem is maximize the objective function Z = xy. Slide 14: Wednesday, November 05, 2008 14 Subject to the constraints x + y <= 15 x > 0, y > 0Linear Programming Problems (LPP) The standard form of the linear programming problem is used to develop the procedure for solving a general programming problem. Application Areas of Linear Programming : Wednesday, November 05, 2008 15 Application Areas of Linear Programming Transportation Problem Goods have to be transported from sources (like factories) to destinations (like warehouses) on a regular basis. The transportation problem deals with minimising the costs in doing so. Linear programming effectively deals with this problem. Military Applications To provide the required protection at the minimum cost, linear programming is used. This technique is useful to cause maximum damage to the enemy with minimum fuel/cost. Slide 16: Wednesday, November 05, 2008 16 Operation of System Of Dams Linear programming is used to find the variations in water storage of dams which generate power, thus maximising the energy got from the entire system. Personnel Assignment Problem If we are given the number of persons, number of jobs and the expected productivity of a particular person on a particular job, linear programming is used to maximise the average productivity of a person. Basic Concept of Linear Programming Problem : Wednesday, November 05, 2008 17 Basic Concept of Linear Programming Problem Objective Function Constraints Optimization Solution of a LPP Feasible Solution Optimal Solution Convex Region Non-convex Sets Objective Function : Wednesday, November 05, 2008 18 Objective Function The Objective Function is a linear function of variables which is to be optimised i.e., maximised or minimised. e.g., profit function, cost function etc. The objective function may be expressed as a linear expression. Constraints : Wednesday, November 05, 2008 19 Constraints A linear equation represents a straight line. Limited time, labour etc. may be expressed as linear inequations or equations and are called constraints. e.g., If 2 tables and 3 chairs are to be made in not more than 10 hours and 1 table is made in x hours while 1 chair is made in y hours, then this constraint may be written as A linear equation is also called a linear constraint as it restricts the freedom of choice of the values of x and y. Optimization : Wednesday, November 05, 2008 20 Optimization A decision which is considered the best one, taking into consideration all the circumstances is called an optimal decision. The process of getting the best possible outcome is called optimisation. The best profit is the maximum profit. Hence optizmizing the profit would mean maximising the profit. Optimising the cost would mean minimising the cost as this would be most favourable. Solution of a LPP : Wednesday, November 05, 2008 21 A set of values of the variables x1, x2,….xn which satisfy all the constraints is called the solution of the LPP. Solution of a LPP Feasible Solution : Wednesday, November 05, 2008 22 Feasible Solution A set of values of the variables x1, x2, x3,….,xn which satisfy all the constraints and also the non-negativity conditions is called the feasible solution of the LPP. Optimal Solution : Wednesday, November 05, 2008 23 Optimal Solution The feasible solution, which optimises (i.e., maximizes or minimizes as the case may be) the objective function is called the optimal solution. Convex Region : Wednesday, November 05, 2008 24 Convex Region A region is said to be a convex region, if for any two points of the region say (x1, y1) and (x2, y2) the line segment joining these points, is also in the region. Non-convex Sets : Wednesday, November 05, 2008 25 Non-convex Sets We know that the feasible solution of an LPP is a set. This set (If it is finite non-empty) is convex for any L.P.P. There are four types of feasible region normally we get : Wednesday, November 05, 2008 26 There are four types of feasible region normally we get Type 1: The region is totally empty, then there is no solution to the problem. Type 2: The region contains exactly one point, the point is optimal solution. Type 3: The region may be bounded convex set consisting of more than and point. Type 4: The region may be unbounded. Mathematical Formulation of Linear Programming Problems : Wednesday, November 05, 2008 27 Mathematical Formulation of Linear Programming Problems There are mainly four steps in the mathematical formulation of linear programming problem as a mathematical model. We will discuss formulation of those problems which involve only two variables. Identify the decision variables and assign symbols x and y to them. These decision variables are those quantities whose values we wish to determine. Identify the set of constraints and express them as linear equations/inequations in terms of the decision variables. These constraints are the given conditions. Identify the objective function and express it as a linear function of decision variables. It might take the form of maximizing profit or production or minimizing cost. Add the non-negativity restrictions on the decision variables, as in the physical problems, negative values of decision variables have no valid interpretation. Limitations of Linear Programming : Wednesday, November 05, 2008 28 Limitations of Linear Programming Linear programming is applicable only to problems where the constraints and objective function are linear i.e., where they can be expressed as equations which represent straight lines. In real life situations, when constraints or objective functions are not linear, this technique cannot be used. Factors such as uncertainty, weather conditions etc. are not taken into consideration. There may not be an integer as the solution, e.g., the number of men required may be a fraction and the nearest integer may not be the optimal solution. i.e., Linear programming techqnique may give practical valued answer which is not desirable. Only one single objective is dealt with while in real life situations, problems come with multi-objectives. Parameters are assumed to be constants but in reality they may not be so. Slide 29: Wednesday, November 05, 2008 29 Thank You