Linear Programming Study Guide

Mastering ECE 580 Exam 2 Concepts (Chapters 15-17)

0% Complete 0 Points
0 Badges

Formulating Linear Programming Problems

What is Linear Programming?

Linear programming (LP) is a mathematical method for determining the best outcome in a mathematical model whose requirements are represented by linear relationships.

Key components:

  • Objective Function: What we want to maximize or minimize
  • Decision Variables: Variables that represent choices
  • Constraints: Limitations on the decision variables

Example: Taco & Burger Stand

A food stand sells tacos ($2 profit each) and burgers ($3 profit each). They have limited ingredients:

  • Meat: 20 lbs (taco: 0.25 lb, burger: 0.5 lb)
  • Cheese: 15 lbs (taco: 0.1 lb, burger: 0.3 lb)
  • Time: 8 hours (taco: 2 min, burger: 5 min)

Practice: Pizza & Wings

A restaurant sells pizza ($8 profit) and wings ($5 profit). They have:

  • Dough: 50 lbs (pizza: 1 lb, wings: 0.2 lb)
  • Sauce: 20 lbs (pizza: 0.5 lb, wings: 0.1 lb)
  • Oven time: 12 hours (pizza: 15 min, wings: 10 min)

Quick Review

  • LP problems have an objective to maximize or minimize
  • Decision variables represent quantities to be determined
  • Constraints limit the possible values of variables
  • All relationships must be linear (no exponents, no products of variables)
  • Non-negativity constraints are usually required

Graphical Solutions

Graphical Method Basics

For problems with two variables, we can solve LP problems graphically:

  1. Plot each constraint as an equation
  2. Identify the feasible region (area satisfying all constraints)
  3. Plot the objective function for different values
  4. Find the optimal solution at a corner point of the feasible region

Special Cases

  • Multiple Solutions: Objective function parallel to a constraint
  • Unbounded: Feasible region extends infinitely
  • Infeasible: No points satisfy all constraints

Interactive Graph

Quick Review

  • Graphical method works for 2-variable problems
  • Feasible region is the intersection of all constraints
  • Optimal solution is at a corner point (vertex)
  • Objective function is moved parallel until it touches the feasible region

Standard Form

Standard Form Requirements

All LP problems must be converted to standard form for the simplex method:

  • Maximization problem (convert minimization by multiplying objective by -1)
  • All constraints are equations (not inequalities)
  • All variables are non-negative
  • Right-hand side constants are non-negative

Conversion Rules

  • ≤ constraints: Add slack variable (s ≥ 0)
  • ≥ constraints: Subtract surplus variable (s ≥ 0) and add artificial variable (a ≥ 0)
  • = constraints: Add artificial variable (a ≥ 0)
  • Unrestricted variables: Replace x with x⁺ - x⁻ where x⁺, x⁻ ≥ 0

Example Conversion

Original Problem:

Minimize: -x₁ + 2x₂

Subject to:

x₁ + x₂ ≤ 6

x₁ - x₂ ≥ 2

x₁ + 2x₂ = 10

x₁ ≥ 0, x₂ unrestricted

Standard Form:

Maximize: x₁ - 2x₂⁺ + 2x₂⁻

Subject to:

x₁ + x₂⁺ - x₂⁻ + s₁ = 6

x₁ - x₂⁺ + x₂⁻ - s₂ + a₁ = 2

x₁ + 2x₂⁺ - 2x₂⁻ + a₂ = 10

All variables ≥ 0

Practice Conversion

Quick Review

  • Standard form requires maximization, equality constraints, and non-negative variables
  • Slack variables are added for ≤ constraints
  • Surplus and artificial variables are added for ≥ constraints
  • Artificial variables are needed for = constraints
  • Unrestricted variables are split into positive and negative parts

Simplex Method

Simplex Algorithm Steps

  1. Convert problem to standard form
  2. Set up initial simplex tableau
  3. Identify entering variable (most negative coefficient in objective row)
  4. Identify departing variable (minimum ratio test)
  5. Pivot to create new tableau
  6. Repeat until all coefficients in objective row are non-negative

Special Cases

  • Degeneracy: Minimum ratio test has a tie
  • Unbounded: No positive denominators in ratio test
  • Multiple Solutions: Zero coefficient in objective row for non-basic variable
  • Infeasible: Artificial variable remains in basis

Simplex Practice

Basic x₁ x₂ s₁ s₂ RHS
s₁
s₂
z

Quick Review

  • Simplex method moves from one basic feasible solution to another
  • Entering variable has most negative coefficient in objective row
  • Departing variable is chosen by minimum ratio test
  • Pivot operation updates the tableau
  • Process continues until optimality is reached

Duality

Duality Concepts

Every LP problem (primal) has a corresponding dual problem:

  • Primal maximization becomes dual minimization (and vice versa)
  • Primal constraints become dual variables
  • Primal variables become dual constraints
  • Constraint coefficients become constraint coefficients in transposed form

Duality Theorems

  • Weak Duality: Value of any feasible dual solution ≥ value of any feasible primal solution
  • Strong Duality: If one problem has optimal solution, so does the other, with equal objective values
  • Complementary Slackness: At optimality, either primal slack or dual variable is zero for each constraint

Example: Primal to Dual

Primal Problem:

Maximize: 3x₁ + 2x₂

Subject to:

x₁ + x₂ ≤ 4

2x₁ + x₂ ≤ 6

x₁ ≥ 0, x₂ ≥ 0

Dual Problem:

Minimize: 4y₁ + 6y₂

Subject to:

y₁ + 2y₂ ≥ 3

y₁ + y₂ ≥ 2

y₁ ≥ 0, y₂ ≥ 0

Practice Duality

Quick Review

  • Dual of a maximization problem is a minimization problem
  • Number of dual variables = number of primal constraints
  • Number of dual constraints = number of primal variables
  • Constraint coefficients are transposed
  • Weak duality provides bounds, strong duality provides exact equality at optimality