Solving a Maximization LP Problem using Simplex Tableau

Introduction

• Objective: Solve a maximization linear programming (LP) problem using simplex tableau setup.
• Method: Convert to standard form, utilize slack variables, change inequalities to equalities.

Standard Form and Initial Setup

• Slack Variables: Added because constraints are "less than or equal to", converting inequalities to equalities.
• Variable Coefficients: Coefficients for slack variables are zeros in the objective function.
• Non-Negativity: All variables must be non-negative.
• Decision Variables: Original problem contains two decision variables.
• Initial Basic Solution:
  • Set non-basic variables (e.g., x1 and x2) to zero.
  • Basic variables (e.g., s1 and s2) are solved.
  • Feasibility: Must satisfy non-negativity.

Simplex Tableau Setup

• Objective Coefficient Row: Called the c-row or cj row.
• Coefficients in Constraints: Known as the A matrix.
• Right-Side Values: Referred to as the b column or quantity column.
• Basis Column: Shows basic variables (initial basic feasible solution).
• cB Column: Lists basic variables' objective function coefficients.

Calculating Initial Simplex Tableau

• Zj Row: Values from multiplying cB with corresponding column values.
• Objective Function Value: Initial value is zero.
• cj – zj Row: Represents the net change in objective function value (net evaluation row).
• Initial Simplex Tableau:
  • Basic feasible solution: x1 = 0, x2 = 0, s1 = 16, s2 = 12.

Iterations for Optimization

1. Select Non-Basic Variable
   • Choose with largest positive net evaluation row value.
   • Variable provides largest net improvement to the objective function.
2. Identify Pivot Row
   • Calculate ratios of b column values to pivot column values.
   • Choose row with minimum non-negative ratio.
3. Elementary Row Operations
   • Convert pivot column to unit column (make pivot element 1, others 0).

Next Iterations

• Repeat Steps: Continue until all cj – zj are negative or zero (optimal solution reached).
• Example Steps:
  • New pivot column with largest positive net evaluation.
  • Calculate pivot row and adjust tableau.

Optimal Solution

• Final Tableau Solution:
  • x1 = 2, x2 = 3, s1 = 0, s2 = 0.
  • Optimal objective function value = 32.

Graphical Correspondence

• Basic Solutions: Extreme points labeled 1 to 6.
• Basic Feasible Solutions: Extreme/corner points of feasible region.
• Initial and Iterative Solutions:
  • Initial solution at corner point 1.
  • First iteration at point 2 with objective value 28.
  • Final solution at corner point 3.

Summary Steps

1. Convert LP problem to standard form (add slack variables).
2. Develop initial simplex tableau.
3. Select non-basic variable with largest net evaluation to become basic.
4. Calculate b-column to pivot column ratios.
5. Perform row operations for unit column.
6. Iterate until net evaluation row has no positive entry (optimal solution reached).

Thank you for watching!