(3) Linear Programming - Graphical Solution | Don't Memorise

Introduction to Linear Programming

• Focus on solving linear programming problems, particularly through graphical methods.

• Definition of an optimal solution: maximum or minimum value of the objective function for a given problem.

Methods of Solving Linear Programming Problems

• Different methods exist:

  • Graphical method for two-variable problems.

  • Simplex method for problems with more than two variables.

• For the current discussion, the focus is on graphical solutions (two variables).

Setting Up the Graph

• Decision variables (x and y) must satisfy the non-negativity constraint: x, y ≥ 0.

• The solution will lie in the first quadrant of the coordinate plane.

Example Problem

• Objective function: Maximize Profit, represented as Z = 50X + 18Y.

• Need to find values of x and y to satisfy given linear inequalities.

Graphing Inequalities

• Convert inequalities into corresponding equations for graphing.

• Finding intercepts:

  • X-intercept: Set y = 0, solve for x (Example: x intercept of first equation is (50, 0)).

  • Y-intercept: Set x = 0, solve for y (Example: y intercept of first equation is (0, 100)).

• Plot intercept points on a coordinate plane and draw lines for each equation.

Feasible Region

• Definition: The common region determined by all constraints of the linear programming problem.

• Every point within this region satisfies the inequalities of the problem.

• Example Feasible Region: Based on constraints, the feasible region is restricted to specific points in the first quadrant.

  • Corner points may be numbered (e.g., O, A, B, and C), intersecting at significant coordinates (like (20, 60)).

Evaluating Corner Points

• The corner point method is used to find the optimal solution, where solutions lie at the corners of the feasible region.

• Steps to evaluate:

  1. List coordinates of corner points.

  2. Substitute coordinates into the objective function Z.

• Example evaluations:

  • Z at O (0, 0) = 0

  • Z at A (20, 60) = 1440

  • Z at B (30, 40) = 2080

  • Z at C (50, 0) = 2500

• Maximum Profit: Optimal solution is found at point C (x=50, y=0) yielding maximum Z.

Conclusion: Bounded vs Unbounded Regions

• Classify whether the feasible region is bounded or unbounded.

• This classification will be discussed further in the next lesson.

[Graphic Representation: Add visual aids to illustrate all concepts for better understanding]