Linear Programming
Linear programming is a mathematical method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
Maximize: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
x₁, x₂, ..., xₙ ≥ 0
Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
x₁, x₂, ..., xₙ ≥ 0
Objective Function
Constraints
Solution
Linear Programming Examples
Production Planning Example
A company produces two products (A and B) with the following constraints:
Maximize: Z = 3x₁ + 5x₂
Subject to:
2x₁ + 3x₂ ≤ 12 (Machine hours constraint)
x₁ + x₂ ≤ 5 (Labor hours constraint)
x₁, x₂ ≥ 0
Diet Problem Example
Minimize the cost of a diet while meeting nutritional requirements:
Minimize: Z = 0.6x₁ + x₂
Subject to:
10x₁ + 4x₂ ≥ 20 (Protein requirement)
5x₁ + 5x₂ ≥ 20 (Carbohydrate requirement)
2x₁ + 6x₂ ≥ 12 (Fat requirement)
x₁, x₂ ≥ 0