Graphical Method in Linear Programming
Linear programming is a powerful technique used in optimization, where the goal is to maximize or minimize a linear objective function, subject to a set of linear constraints. One of the simplest methods of solving linear programming problems is the Graphical Method. This method is particularly effective when dealing with two variable problems, as it allows us to visualize the solution and better understand the relationship between constraints.
1.0What is Linear Programming?
Linear programming (LP) is a mathematical technique for optimization. It involves finding the best possible outcome (such as maximum profit or minimum cost) in a mathematical model whose requirements are represented by linear relationships. These relationships are typically expressed through an objective function (which we aim to optimize) and constraints (which define the limits or restrictions).
For example, a company may want to maximize its profit by deciding how much of two products to produce, subject to constraints such as limited resources, time, or production capacity.
2.0The Graphical Method: An Overview
The Graphical Method is used to solve linear programming problems with two variables. It involves plotting the constraints on a graph, identifying the feasible region, and then determining the optimal point that maximizes or minimizes the objective function.
Key Elements of a Graphical Method:
- Decision Variables: These are the variables we need to solve for, often denoted as x1 and x2 in two-variable problems.
- Objective Function: A linear equation that needs to be maximized or minimized, typically in the form Z=c1x1+c2x2.
- Constraints: These are linear inequalities that limit the values of the decision variables (e.g., x1+2x2≤6).
3.0Steps in the Graphical Method
Step 1: Formulate the Linear Programming Problem
Start by defining the objective function and the constraints for the problem.
For example, consider the following problem:
- Objective: Maximize Z=3x1+4x2
Constraints:
- x1+x2≤4
- 2x1+x2≤5
- x1≥0,x2≥0 (non-negativity constraints)
Step 2: Graph the Constraints
Each constraint is a linear equation that can be plotted on a graph. To graph the constraint, first convert the inequality into an equation by replacing the inequality sign with an equal sign.
For example, for the constraint x1+x2≤4, graph the line x1+x2=4. This line divides the plane into two regions. The feasible region will be one side of the line, depending on whether the inequality is ≤ or ≥.
Repeat this process for each constraint, plotting them on the same graph.
Step 3: Identify the Feasible Region
The feasible region is the area that satisfies all the constraints. It is typically a polygon (or sometimes unbounded) where all the constraint lines intersect. This region represents all possible solutions that meet the problem's requirements.
Step 4: Locate the Corner Points
The optimal solution to a linear programming problem in the graphical method will always occur at one of the corner points (also called vertices) of the feasible region. These points can be found by identifying where the constraint lines intersect.
Step 5: Evaluate the Objective Function
Now that we have the corner points, evaluate the objective function at each of these points. Substitute the values of x1 and x2 into the objective function Z=3x1+4x2and calculate the corresponding values of Z.
Step 6: Choose the Optimal Solution
The solution that gives the highest (for maximization problems) or lowest (for minimization problems) value of the objective function is the optimal solution. If there are multiple corner points with the same value, there may be multiple optimal solutions.
4.0Solved Example: A Simple Linear Programming Problem
Problem: Maximize Z=3x1+2x2
Subject to:
- x1+x2≤6
- 2x1+x2≤8
- x1≥0,x2≥0
- Plot the constraints:
- x1+x2=6(Line1)
- 2x1+x2=8(Line2)
- Find the feasible region: The feasible region will be bounded by these lines and the non-negative axes.
- Locate the corner points: Identify the intersections of the lines, which are the possible solutions.
- Evaluate the objective function at each corner point:
- At (0, 6), Z = 3(0) + 2(6) = 12
- At (4, 0), Z = 3(4) + 2(0) = 12
- At (2, 4), Z = 3(2) + 2(4) = 14
- Optimal solution: The maximum value of Z occurs at (2, 4), where Z = 14.
Example 2: An aeroplane of an airline can carry a maximum of 200 passengers. A profit of Rs 400 is made on each first-class ticket and a profit of Rs 300 is made on each economy-class ticket. The airline reserves at least 20 seats for first class. However, at least 4 times as many passengers prefer to travel by economy class than by first class. Determine how many of each type of tickets must be sold in order to maximize the profit for the airline. What is the maximum profit?
Solution:
Let x tickets of first class and y tickets of economy class be sold to maximize the profit. Then,
x≥20,
y≥4x,
x≥80 and
x+y≤200.
The profit function is given by Z = 400x + 300y.
So, for a maximum profit first class ticket should be 40 and economy class should be 160.
Example 3: A firm manufactures two types of products, A and B, and sells them at a profit of Rs 5 per unit of type A and Rs 3 per unit of type B. Each product is processed on two machines, M1 and M2. One unit of type A requires one minute of processing time on M1 and two minutes of processing time on M2; whereas one unit of type B requires one minute of processing time on M1 and one minute on M2. Machines M1 and M2 are respectively available for at most 5 hours and 6 hours in a day. Find out how many units of each type of product should the firm produce a day in order to maximize the profit. Solve the problem graphically.
Solution:
Let x units of A and y units of B be produced in order to have a maximum profit.
Then, clearly x ≥ 0 and y ≥ 0.
x units of A and y units of B will take (x + y) minutes on M1.
∴ x + y ≤ 300.
x units of A and y units of B will take (2x + y) minutes on M2.
∴ 2x + y ≤ 360.
Let Z be the profit function. Then, Z = 5x + 3y.
We have to maximize Z= 5x + 3y ,
Subject to the constraints
x + y ≤ 300
2x + y ≤ 360
x ≥ 0
y ≥ 0.
So, for maximum profit x = 60 and y = 240.
5.0Advantages of the Graphical Method
- Visual Insight: It gives a clear visual representation of the feasible region, helping you understand the relationship between constraints and objective.
- Simple for Two Variables: The method is straightforward and easy to apply for problems with only two variables.
- Intuitive: It is an excellent tool for teaching and understanding the basics of linear programming.
6.0Limitations of the Graphical Method
- Limited to Two Variables: The graphical method is only feasible for problems with two decision variables. For larger problems (three or more variables), other methods such as the Simplex Method are needed.
- Less Practical for Large Problems: As the number of constraints or decision variables increases, the graphical method becomes cumbersome and impractical.
