Linear Programming Problems - Graphical Method

  • Linear programming is a mathematical technique for finding the best possible solution given certain constraints and constraints.
  • The graphical method is one approach to solve linear programming problems.
  • In this method, we represent constraints and the objective function graphically and determine the optimal solution by finding the point of intersection of the constraints region.

Steps in Graphical Method

  1. Identify the decision variables.
  1. Define the objective function.
  1. Write the constraints.
  1. Graph the constraints.
  1. Determine the feasible region.
  1. Identify the corner points.
  1. Evaluate the objective function at each corner point.
  1. Determine the optimal solution.

Decision Variables

  • Decision variables are the unknown quantities that we need to determine.
  • These are usually represented by x1, x2, x3, and so on.
  • For example, if we want to maximize profit, we might have decision variables such as the number of units produced or sold.

Objective Function

  • The objective function is a mathematical expression that defines what we want to optimize (maximize or minimize).
  • It is usually represented as a linear equation or a linear combination of decision variables.
  • For example, if we want to maximize profit, our objective function may be in the form of Z = cx1 + dx2, where c and d are constants.

Constraints

  • Constraints are the conditions or limitations that must be satisfied.
  • They represent the restrictions on decision variables.
  • Constraints are represented as linear inequalities or equations.
  • For example, if we have a constraint that limits the number of units produced to less than or equal to 100, we can represent it as x1 ≤ 100.

Graphing the Constraints

  • Once we have identified the decision variables and written the constraints, we can graph them on a coordinate plane.
  • Each constraint will be represented by a line or inequality.
  • We will shade the region that satisfies all the constraints to find the feasible region.

Determining the Feasible Region

  • The feasible region is the region on the graph that satisfies all the constraints simultaneously.
  • It is the area where all the lines or inequalities intersect.
  • The feasible region is usually bounded by lines, and it may be unbounded in some cases.

Corner Points

  • The corner points are the vertices or points of intersection of the lines that define the feasible region.
  • These are the points where the constraints are equally satisfied.

Evaluating the Objective Function

  • After identifying the corner points, we need to evaluate the objective function at each of these points.
  • We substitute the corner point values into the objective function and calculate the corresponding objective function value.
  • This step helps us determine which corner point gives the optimal value for the objective function.

Optimal Solution

  • The optimal solution is the corner point that results in the maximum or minimum value of the objective function.
  • It represents the best possible outcome given the constraints and objective.
  • The optimal solution can be identified by comparing the objective function values obtained at the corner points.

Good morning class! Today, we will continue our discussion on Linear Programming Problems using the Graphical Method. Let’s dive into slides 11 to 20!

Graphical Method - Step 5: Determine the Feasible Region

  • Shade the region on the graph that satisfies all the constraints simultaneously.
  • The feasible region is the area where all the lines or inequalities intersect.

Graphical Method - Step 6: Identify the Corner Points

  • The corner points are the vertices or points of intersection of the lines that define the feasible region.
  • These are the points where the constraints are equally satisfied.

Graphical Method - Step 7: Evaluate the Objective Function at Corner Points

  • Substitute the corner point values into the objective function.
  • Calculate the corresponding objective function value for each corner point.

Graphical Method - Step 8: Determine the Optimal Solution

  • Compare the objective function values obtained at the corner points.
  • The corner point with the maximum or minimum objective function value is the optimal solution.

Example 1

Maximize Z = 3x1 + 4x2 Subject to the constraints:

  • x1 + x2 ≤ 5
  • x1 ≥ 0
  • x2 ≥ 0

Example 1 - Graphing the Constraints

  • Begin graphing the first constraint, x1 + x2 ≤ 5.
  • Represent it as a line and shade the region below the line.

Example 1 - Graphing the Constraints (contd.)

  • Graph the second constraint, x1 ≥ 0.
  • Represent it as a vertical line passing through the origin.
  • Shade the region to the right of the line.

Example 1 - Graphing the Constraints (contd.)

  • Graph the third constraint, x2 ≥ 0.
  • Represent it as a horizontal line passing through the origin.
  • Shade the region above the line.

Example 1 - Finding Corner Points

  • Identify the points where the shaded regions intersect.
  • These are the corner points.

Example 1 - Evaluating the Objective Function

  • Substitute the corner point values into the objective function Z = 3x1 + 4x2.
  • Calculate the corresponding Z value for each corner point.
    Great job, everyone! We have covered slides 11 to 20. Keep up the good work. Next, we will move on to slides 21 to 30.

Example 1 - Finding the Optimal Solution

  • The corner points are (0, 0), (0, 5), and (5, 0).
  • Substitute these values into the objective function:
    • Z = 3(0) + 4(0) = 0
    • Z = 3(0) + 4(5) = 20
    • Z = 3(5) + 4(0) = 15
  • The maximum value of Z is 20, which occurs when x1 = 0 and x2 = 5.
  • Therefore, the optimal solution is x1 = 0, x2 = 5, and the maximum value of Z is 20.

Example 2

Minimize Z = 2x1 + 3x2 Subject to the constraints:

  • x1 + x2 ≥ 4
  • 2x1 + x2 ≤ 6
  • x1, x2 ≥ 0

Example 2 - Graphing the Constraints

  • Begin graphing the first constraint, x1 + x2 ≥ 4.
  • Represent it as a line and shade the region above the line.

Example 2 - Graphing the Constraints (contd.)

  • Graph the second constraint, 2x1 + x2 ≤ 6.
  • Represent it as a line and shade the region below the line.

Example 2 - Graphing the Constraints (contd.)

  • Graph the third constraint, x1, x2 ≥ 0.
  • Represent it as lines passing through the origin.
  • Shade the region to the right and above the axes.

Example 2 - Finding Corner Points

  • Identify the points where the shaded regions intersect.
  • These are the corner points.

Example 2 - Evaluating the Objective Function

  • Substitute the corner point values into the objective function Z = 2x1 + 3x2.
  • Calculate the corresponding Z value for each corner point.

Example 2 - Evaluating the Objective Function (contd.)

  • Substitute the corner point values into the objective function Z = 2x1 + 3x2.
  • Calculate the corresponding Z value for each corner point.

Example 2 - Determining the Optimal Solution

  • Compare the objective function values obtained at the corner points.
  • The minimum value of Z is 10, which occurs when x1 = 2 and x2 = 2.
  • Therefore, the optimal solution is x1 = 2, x2 = 2, and the minimum value of Z is 10.

Summary

  • Linear programming problems can be solved using the graphical method.
  • The graphical method involves graphing the constraints and determining the feasible region.
  • The corner points of the feasible region are identified and evaluated using the objective function.
  • The optimal solution is found by comparing the objective function values at the corner points.

Great job, everyone! We have completed slides 21 to 30. Keep up the good work. Next, we will move on to slides 31 to 40.