Linear Programming Problem PDF

Linear programming Problem Linear programming is a mathematical method used for optimizing a linear objective function, subject to a set of linear equality and inequality constraints. This optimization process aims to achieve the best outcome, such as maximizing profit or minimizing costs, under sp...

Linear programming Problem Linear programming is a mathematical method used for optimizing a linear objective function, subject to a set of linear equality and inequality constraints. This optimization process aims to achieve the best outcome, such as maximizing profit or minimizing costs, under specific limitations such as resource availability, time, or budget constraints. Definition of Linear Programming Linear programming (LP) is defined as a technique that focuses on maximizing or minimizing a linear objective function while satisfying a set of linear constraints. The objective function usually represents a quantity to be optimized, such as profit or cost, which is expressed as a function of decision variables. Components of Linear Programming The fundamental components of a linear programming problem include: a. Objective Function: This is a linear function that one seeks to maximize or minimize. For example, if the goal is to maximize profit from different products, the objective function will be a linear combination of variables representing the quantities of each product to be produced. b. Decision Variables: These variables represent the quantities of different inputs or items to be determined by the solution to the problem. In a farming scenario, these could represent the number of acres allocated to different crops. c. Constraints: These are linear equations or inequalities that limit the values that the decision variables can take. Constraints can represent resource availabilities, such as land, labor, or budget. d. Feasible Region: The feasible region is the set of all possible points that satisfy the constraints of the linear programming problem. It is typically represented as a convex polytope in a multidimensional space. Mathematical Formulation A linear programming problem can be mathematically formulated in standard form as follows Eg: A Farmer with 5 acres of land wanted to diversify his farming with paddy type -I, paddy type –II , and Ground Nut. Availability of labour for farming is 180 days, requirement of Labour for paddy type –I 90 days, Labour for paddy type –II 80 days, for Ground Nut 70 days required per acre. Budget available/allocated for crop production 50 (‘00 rs), cost of capital for paddy type –I production is 20(‘00rs), for paddy type –II production 18 (‘00 rs), for Ground Nut production 25 (‘00 rs), Profit by selling paddy-I, Paddy – II and Groundnut is (cost price – selling price) =30 (‘000 Indian RS), 28, 26 respectively. Format: Maximize X = 30 X1 + 28 X2 + 26 X3 Subject to: X1 + X2 + X3 ≤ 5 ( land) 90 X1 + 80X2 + 70X3 ≤ 180 (time in days) 20X1 + 18X2 + 25 X3 ≤ 50 And X1 , X2 , X3 ≥ 0  Graphical Method 1. Maximization 10 X1 + 9 X2 Subject to 3 X1 + 3 X2 ≤ 21 4 X1 + 3 X2 ≤ 24 X1 , X2 ≥ 0 Sol: Graphical Method (Maximization) (0,8) 4x1 + 3x2 = 24 ( 0, 7) Z = 63 ( 3, 4 ) Z= 66 (Feasible Region) 3x1 + 3 x2 = 21 ( 0, 0 ) Z= 0 ( 6, 0) Z= 60 (7,0) Objective Function Lines touch last at ( 3, 4) Note: For every Z value represents a straight Line ( 3, 4) is the Optimum Solution Evaluate corner points Four corner points For (0,0) the objective function value Z = 0 For (6,0) the objective function value Z = 60 For (0,7) the objective function value Z = 63 For (3,4) the objective function value Z = 66 Optimum solution 2. Minimize 7 X1 + 5 X2 Subject to X1 + X2 ≥ 4 5 X1 + 2X2 ≥ 10 X1 , X2 ≥ 0 Sol: Graphical Method (Minimize) X2 ( 0 , 5) (0,4) ( 2/3 , 10/3) (Feasible Region) ( 0, 0) (2,0 ) (4, 0) X1 Feasible region has 3 corner points, the first corner point is given here which is (4, 0), the other corner point is (0, 5). For (4, 0) we evaluate the objective function and the objective function value is given as Z = 28. The next corner point is (0, 5) which is here and when we evaluate the objective function 7X1+5X2 we get Z = 25, (7 x 0)+(5 x 5) = 25. We now look at the third corner point which is (2/3, 10/3), now this (2/3, 10/3) can be found in the graph, if we draw this graph to scale and we draw the graph correctly as we have attempted to do, now you realize that this point has an X coordinate of 2/3 and has a Y coordinate of 10/3. This point is (2/3, 10/3), for objective function value we substitute: 7 (2/3) + 10(5/3) which is (50/3), (14/3)+(50/)3 is (64/3) Now we have (64/3) which is Z= 21.33 for the other corner point which is (2/3, 10/3). Therefore, the optimum solution to this minimization problem is that corner point which has the smallest value of the objective function and out of these 3 we realize that the point (2/3,10/3) with (64/3) has the smallest value and therefore, is the optimum solution. This point is the optimum solution with value (64/3), like we did for the maximization problem we can also draw what are called is objective function lines, where we fix 7X1+5X2 to a constant. The last feasible point is given by (2/3, 10/3), which is the optimum solution to the minimization problem. This is how we solve we solve minimization problems using the graphical method.