LP - Augmented／Slack Form

Optimization (LP) problems can be converted into an Augmented/Slack Form in order to apply the common form of the simplex algorithm

Purpose

given a linear programming problem:

• objective function:
  Z = c₁x₁ + c₂x₂
• linear constraints:
  a₁₁x₁ + a₁₂x₂≤ b₁
  a₂₁x₁ + a₂₂x₂≥ b₂
• non-negative variables:
  x₁ ≥ 0
  x₂ ≥ 0

problem:

• the linear constraints are not of same equality symbol (i.e. all either: ≤, =, or ≥), thus not satisfying standard form

solution:

• use augmented form, by adding slack variables into the linear constraints

resulting form:

• objective function:
  Z = c₁x₁ + c₂x₂
• linear constraints:
  a₁₁x₁ + a₁₂x₂- s₁ = b₁
  a₂₁x₁ + a₂₂x₂+ s₂ = b₁
• non-negative variables:
  x₁ ≥ 0
  x₂ ≥ 0
• slack variables:
  s₁ ≥ 0
  s₂ ≥ 0

Equation Form

• objective function:
  Z = c₁x₁ + c₂x₂ + … + c_nx_n
• augmented linear constraints:
  a₁₁x₁ + a₁₂x₂ + … + a_1nx_n + s₁= b₁
  a₂₁x₁ + a₂₂x₂ + … + a_2nx_n + s₂= b₂
  …
  a_m1x₁ + a_m2x₂ + … + a_mnx_n + s_m= b_m
• non-negative variables:
  x₁ ≥ 0
  x₂ ≥ 0
  …
  x_n ≥ 0
• non-negative slack variables:
  s₁ ≥ 0
  s₂ ≥ 0
  …
  s_m ≥ 0

Block Matrix Form