Linear Programming

Terminology

• process of fomulating and solving linear programs
• mathematical program with some special properties
  1. objective function
  2. constraints (\(b_1, b_2, ..., b_m\))
  3. decision variables (\(x_1, x_2, ..., x_n, x_i ∈ ℝ\))
     → also expressed as a \(x\) that means vector of \(n\) variables

constraints

• Sign constraints: single variable

  • nonnegative: \(x_i ≥ 0\)
  • nonpositive: \(x_i ≤ 0\)
  • unrestricted in sign or free: no sign constraints

• Functional constraints: other cases

• equality constraints: \(a_1x_1 + a_2x_2 + ... + a_nx_n = b\)

• inequality constraints: \(a_1x_1 + a_2x_2 + ... + a_nx_n ≤ b\)

• binding constraints (or active constraints)
  no matter \(g(x)\) is equality or not, if \(g(a) = b, a\) is binding

• strict constraints: \(a_1x_1 + a_2x_2 + ... + a_nx_n < b\)

• weak constraints: \(a_1x_1 + a_2x_2 + ... + a_nx_n ≤ b\)

  → practical mathematical program’s inequalities are all weak

solution

• feasible solution: satisfies all constraints
  • feasible region: set of all feasible solutions
• optimal solution: maximizes or minimizes the objective function
  there may be multiple or no optimal solutions

Three types of LPs

1. Infeasible
2. Unbounded: unbounded feasible region does not imply an unbounded LP
3. Finitely optimal
   • Unique optimal solutions
   • Multiple optimal solutions

Parameter: we know. \(C_1, C_2, ...\)
Variables: do not know. \(x_1, x_2, ...\)