Learn & Review: Linear Programming: Simplex Method : Performance Management /Math/ Operation Research / Statistics

Summary of Simplex Method for Linear Programming

This presentation introduces the Simplex method as a technique for solving linear programming problems, particularly when dealing with multiple constraints.

1. Introduction to Linear Programming

• Definition: Linear programming is a mathematical modeling approach used to allocate limited resources among competing products under multiple constraints.
• Key Requirement: The existence of multiple constraints is crucial for the application of linear programming.

2. Methods for Solving Linear Programming

The speaker has previously covered:

• Formulation of linear programming problems.
• Solving using simultaneous equations.
• Solving using the graphical method.

This video focuses on the Simplex Method.

3. The Simplex Method

• Definition: The Simplex method is a step-by-step approach that moves from one feasible solution to a better one until the optimal solution is reached.
• Optimal Solution Condition: The optimal solution is achieved when all variables in the objective function row are zero or negative.

4. Key Terms in Simplex Method

• Slack Variable: Represents unused capacity or unutilized resources within a constraint.
• Pivot Column: The column with the largest value in the objective function row.

5. Steps for Solving Linear Programming using Simplex Method

1. Formulate: Define the linear programming objective function and constraints.
2. Convert Inequalities to Equalities: Add slack variables to each constraint to turn inequalities into equalities.
3. Matrix Form: Arrange the equations in a matrix format.
4. Identify Pivot Element:
   • Determine the pivot column by finding the largest value in the objective function row.
   • Calculate the "solution quantity" by dividing the values in the solution column by the corresponding values in the pivot column.
   • The pivot element is the value in the pivot column that corresponds to the least positive ratio from the division.
5. Normalize Pivot Row: Divide all elements in the pivot row by the value of the pivot element to make the pivot element equal to 1.
6. Create New Rows: For each other row, subtract a multiple of the pivot row to make the element in the pivot column zero. The multiple is determined by the value in the pivot column for that specific row.
7. Repeat: Continue steps 4-6 until the optimal solution is reached (all values in the objective function row are zero or negative).

Note: The Simplex method is suitable for problems with more than two variables, unlike the graphical method which is limited to two variables.

6. Worked Example: Maximizing Contribution

A company produces three products (A, B, C) with contributions of £8, £5, and £10 respectively. The production is subject to constraints on machine capacity, special components, special alloy, and a trade agreement. The goal is to maximize total contribution.

Step 1: Formulation

• Objective Function: Maximize Z = 8A + 5B + 10C
• Constraints:
  • Machine Capacity: 2A + 3B + C ≤ 400
  • Special Component: A + C ≤ 150
  • Special Alloy: 2A + 4C ≤ 200
  • Trade Agreement (Product B): B ≤ 50
  • Non-negativity: A ≥ 0, B ≥ 0, C ≥ 0

Step 2: Introduce Slack Variables

• 2A + 3B + C + S1 = 400
• A + C + S2 = 150
• 2A + 4C + S3 = 200
• B + S4 = 50

Step 3: Matrix Form (Initial Simplex Tableau)

The initial tableau is constructed with coefficients for variables (A, B, C, S1, S2, S3, S4) and the solution quantity. The objective function is represented in the last row.

Steps 4-7: Iterative Process (Tableau Calculations)

The presentation details the iterative process of identifying pivot elements, normalizing pivot rows, and creating new rows to transform the tableau. This involves multiple simplex tableaus (Second, Third, Fourth, Fifth).

• Pivot Identification: Based on the largest positive value in the objective function row.
• Ratio Test: Used to determine the pivot element by dividing solution quantities by pivot column values.
• Row Operations: Used to introduce zeros into the pivot column, moving towards the optimal solution.

Optimal Solution Identification

After several iterations, the final tableau is reached when all values in the objective function row are zero or negative.

• Optimal Production Plan:
  • Product A: 100 units
  • Product B: 50 units
  • Product C: 0 units
• Maximum Contribution: £1050
• Unused Resources (Slack Variables):
  • S1 (Machine Capacity): 50 hours
  • S2 (Special Component): 50 units
  • S3 (Special Alloy): 0 kg
  • S4 (Product B Trade Agreement): 0 units
• Shadow Prices:
  • S3 (Special Alloy): £4 per kg
  • S4 (Product B Trade Agreement): £5 per unit

The presentation concludes by mentioning that the next topic will cover dual constraints and minimization problems.