Lecture on Linear Programming by Mr. T

Introduction to Linear Programming

• Purpose: To optimize a function (maximize or minimize).
• Constraints: A set of constraints in the form of inequalities limiting the values of x and y.
• History:
  • Invented during WWII for optimizing cargo loads.
  • Kept secret during the war, published post-war and adopted by corporations.

Graphing Inequalities

• Forms a feasible region or solution space which is usually closed.
• The feasible region is bounded by the constraints and contains possible values for optimization.

Optimizing the Objective Function

• Key Concept: Maximum and minimum values occur at the vertices (corners) of the feasible region.
• Example Objective Function: 5x - 3y
  • Evaluate the function at each vertex to find max and min values.
  • Example points:
    • (0,2): P = -6
    • (3,4): P = 3
    • (6,2): P = 24
    • (0,-2): P = 6
  • Max Value: 24 at (6,2)
  • Min Value: -6 at (0,2)

Linear Programming Example

Problem Description

• Scenario: Farmer with 240 acres of land to plant corn and oats.
  • Profit: $40/acre for corn, $30/acre for oats.
  • Labor: 320 hours available.
  • Corn requires 2 hours/acre, Oats require 1 hour/acre.
  • Objective: Maximize profit.

Developing the Objective Function

• Profit = 40x + 30y
  • x = acres of corn
  • y = acres of oats

Developing Constraints

• Non-negativity Constraint: x, y ≥ 0
• Land Constraint: x + y ≤ 240
• Labor Constraint: 2x + y ≤ 320

Graphing the Constraints

• Axes Setup: Only first quadrant shown (since x, y ≥ 0)
• Graph the Lines:
  • x-intercept for land constraint: (240,0)
  • y-intercept for land constraint: (0,240)
  • x-intercept for labor constraint: (160,0)
  • y-intercept for labor constraint: (0,320)

Finding Feasible Region

• Feasible Region: Area where all constraints are satisfied.
• Vertices:
  • (0,240)
  • (160,0)
  • Intersection of constraints: Solve x + y = 240 and 2x + y = 320
    • Intersection: (80,160)

Calculating Profit

• Evaluate profit at each vertex:
  • (0,240): Profit = $7,200
  • (160,0): Profit = $6,400
  • (80,160): Profit = $8,000
• Maximum Profit: $8,000 at (80,160)
  • Plant 80 acres of corn and 160 acres of oats for maximum profit.

Conclusion

• Linear programming allows for efficient decision making in resource management.
• Next steps: Apply the method to more complex real-world problems.