Graphical Solutions in Linear Programming

Linear Programming Components

  • Constraints: Linear inequalities representing physical, operational, or resource limits.
  • Objective Function: A linear equation representing the target quantity to be maximized or minimized.
  • Feasible Region: The overlapping region on a graph containing all coordinate points that satisfy all constraints simultaneously.

Fundamental Theorem of Linear Programming

  • Bounded Feasible Region: If a solution exists to a bounded linear programming problem, it must occur at one of the corner points (vertices) of the feasible region.
  • Unbounded Feasible Region (Maximum): If a feasible region is unbounded, a maximum value for the objective function does not exist.
  • Unbounded Feasible Region (Minimum): If a feasible region is unbounded and the objective function contains only positive coefficients, a minimum value exists.

Steps to Solve Graphically

  • Step 1: Define the decision variables to be optimized.
  • Step 2: Formulate the objective function equation in terms of the variables.
  • Step 3: Formulate the constraint inequalities in terms of the variables.
  • Step 4: Graph all constraint boundary lines and shade the intersecting feasible region.

Feasible region defined by linear constraints

  • Step 5: Identify all corner points of the feasible region by solving systems of linear equations for intersecting lines.
  • Step 6: Evaluate the objective function at each corner point. The corner point yielding the largest result (for maximization) or smallest result (for minimization) is the optimal solution.

Key Solution Summary

  • Basic vs. Premium Products (Maximization):

    • Objective: P=30b+40pP = 30b + 40p
    • Constraints: 20b+30p≤390020b + 30p \le 3900, 15b+30p≤330015b + 30p \le 3300, b≥0b \ge 0, p≥0p \ge 0
    • Optimal Corner Point: (195,0)(195, 0)
    • Maximum Profit: P=$5850P = \$5850

  • Fruit Bar Blend (Minimization):

    • Objective: C=3.33x+2.00yC = 3.33x + 2.00y
    • Constraints: 407x+271y≥4700407x + 271y \ge 4700, x≥1x \ge 1, y≥1y \ge 1
    • Optimal Corner Point: (1,15.8)(1, 15.8)
    • Minimum Cost: C=$34.96C = \$34.96

  • Chairs and Tables (Maximization):

    • Objective: P=20c+30tP = 20c + 30t
    • Constraints: c+2t≤40c + 2t \le 40, 2c+t≤422c + t \le 42, c+t≤25c + t \le 25, c≥0c \ge 0, t≥0t \ge 0
    • Evaluated Corner Points: (0,0)(0, 0), (0,20)(0, 20), (21,0)(21, 0), (10,15)(10, 15), (17,8)(17, 8)
    • Optimal Corner Point: (10,15)(10, 15)
    • Maximum Profit: P=$650P = \$650