Reduced Cost in Linear Programming (operations & analytics tutoring)

Why Tutoring - California Graduate Tutor
Reduced Cost in Linear Programming (operations & analytics tutoring)
Submit Homework

Reduced cost is a key concept in linear programming and operations analytics. It measures how much the objective function would improve if a non‑basic variable were to enter the basis. In simplex, reduced cost determines which variable should enter next — and whether the current solution is already optimal.

Students often struggle to interpret reduced cost values and understand their role in optimality conditions. For help with simplex, optimization modeling, or LP diagnostics, visit the tutoring services page.

Reduced Cost: The amount the objective must improve before a non‑basic variable becomes attractive to enter the basis.

For maximization problems, a negative reduced cost means the variable can improve the objective. For minimization problems, a positive reduced cost indicates potential improvement.

Why Reduced Cost Matters

Reduced cost is essential because it:

  • determines which variable enters the basis in simplex
  • signals optimality when all reduced costs satisfy the optimality condition
  • reveals shadow prices and dual relationships
  • helps diagnose modeling errors and constraint issues

How Reduced Cost Works Step by Step

  1. Start with a simplex tableau.
    Basic variables have value > 0; non‑basic variables are set to 0.
  2. Compute reduced cost for each non‑basic variable:
    c̄ⱼ = cⱼ − yB Aⱼ where yB is the vector of dual prices.
  3. Interpretation:
    c̄ⱼ measures how much the objective would change if variable j entered the basis.
  4. Optimality condition:
    Maximization: all c̄ⱼ ≥ 0 Minimization: all c̄ⱼ ≤ 0 If satisfied → optimal solution found.
  5. Pivot rule:
    Choose the variable with the most negative (max) or most positive (min) reduced cost to enter the basis.

Numerical Example

Consider the LP: Maximize z = 4x₁ + 3x₂ subject to: x₁ + x₂ ≤ 6 x₁ ≤ 4 x₂ ≤ 5 x₁, x₂ ≥ 0

Suppose the current BFS has x₁ = 4, x₂ = 2. Reduced costs computed from the tableau:

  • c̄₁ = 0 (basic variable)
  • c̄₂ = 0 (basic variable)
  • c̄₃ = −1 (non‑basic slack variable)

Because c̄₃ is negative, entering that variable would improve the objective. If all reduced costs were ≥ 0, the solution would be optimal.

Common Mistakes

  • Thinking reduced cost is the same as marginal cost (it isn’t)
  • Ignoring sign conventions for max vs. min problems
  • Misinterpreting reduced cost for basic variables (always zero)
  • Failing to connect reduced cost to dual prices

Why This Matters in Optimization

Reduced cost is central to:

  • simplex pivot decisions
  • dual interpretation of LPs
  • shadow pricing and sensitivity analysis
  • operations research and supply chain modeling

Related Topics

Speak Directly to a Tutor — Send Your Message Below

No call centers. No delays. Your message goes straight to the tutor.

Get help with reduced cost, simplex pivots, duality, and optimization modeling.