Linear Programming Graphical Method Study Notes

Linear Programming: Graphical Solution Technique

Overview of Linear Programming

• Definition: Linear programming is a mathematical method for modeling a given problem by using linear constraints and inequalities to find potential solutions.

• Objective: The main goal is to discover the optimal solution, which could be defined as a maximum or minimum value based on a given context or problem.

Key Concepts

• Objective Function: In many cases, this function represents profit or cost that needs to be maximized or minimized. For example:

  • $ext{Profit} = 4x + 6y$

  • Here, the coefficients (4 and 6) represent the profit contribution of products x and y, respectively.

• Maximization or Minimization: In the provided example, the goal is to maximize profit.

Constraints in Linear Programming

• Constraints limit the values that x and y can take, expressed in the following inequalities:

  • 1) $2x + y = 180$

  • 2) $x + 2y ext{ (less than or equal to) } 160$

  • 3) $x + y ext{ (less than or equal to) } 100$

• Non-negativity constraints: Both variables must be greater than or equal to 0:

  • $x ext{ (greater than or equal to) } 0$

  • $y ext{ (greater than or equal to) } 0$

Graphical Representation

• The objective function and constraints must be plotted on a graph with:

  • x-axis and y-axis representing product quantities of x and y.

  • The intersection of the constraints creates a feasibility region where potential solutions lie.

• 3D Graph: Theoretically, if a problem included a third variable z, a 3D graph would be required; however, such graphs are typically not practical for graphical solutions in linear programming.

Key Parameters in Graphing

• Slope Calculation: Calculating slopes of constraints aids in determining the optimal solution. The slopes obtained from the constraints are:

  • 1) First constraint: $ext{slope} = -2$

  • 2) Second constraint: $ext{slope} = -0.5$

  • 3) Third constraint: $ext{slope} = -1$

• Intercept Calculation:

  • Y-intercept: Value of y when x is set to 0.

  • X-intercept: Value of x when y is set to 0.

• Example of intercept calculations:

  • For the first constraint when $x = 0$: $y ext{ max is } 180$

  • For the second constraint when $y = 0$: $x ext{ max is } 160$

Intersections and Feasibility Region

• The corner points of the feasibility region are critical in identifying potential optimal solutions.

• Corner Points Identification: The intersection of constraint lines and axes defines potential corner points:

  • These are labeled A, B, C, D, and E (e.g., A at (40, 60), B at (80, 20), etc.).

• Feasibility Shape: The shape of feasible area (often triangular or polygonal) helps in visualizing all combinations of x and y that satisfy all constraints.

Optimization Process

• Evaluate each corner point by substituting their coordinates back into the objective function to find the highest profit value:

  • Example of calculations for corner points:
    1) Point A: Profit = $4(40) + 6(60) = 520$
    2) Point B: Profit = $4(80) + 6(20) = 520$
    3) Point C: Profit calculations may yield different outcomes.

• After calculating profits for all points, identify the maximum profit.

Multiple Optimal Solutions

• Conditions for Multiple Solutions: If the slope of the objective function equals the slope of one of the constraints, multiple optimal solutions exist along the segment of the line.

  • E.g., if the slope is among the constraints slopes (-1.5 being between two slopes), then all values between those intersections could yield optimal values.

Summary

• Linear programming is a sophisticated tool for solving problems where a maximum or minimum objective is defined under constraints.

• The graphical method is an effective visualization tool, but only applicable to two-variable scenarios for practical purposes.

• Every feasible solution must satisfy all constraints, with the optimal solution found at one of the corner points of the feasibility region.