Overview
This lecture introduces linear programming formulation, outlining its assumptions, components, and step-by-step modeling using real-world examples, including maximization and minimization problems.
Introduction to Linear Programming
- Linear programming (LP) is a mathematical technique for optimal allocation of scarce resources.
- LP aims to maximize satisfaction (e.g., profit) or minimize costs using limited resources.
- Applications include production mix, diet problems, media selection, and transportation.
Assumptions of Linear Programming
- Linearity: Relationships among variables, constraints, and objective function are linear.
- Divisibility: Solutions can be fractional, not just integers.
- Certainty: All parameters and coefficients are known and constant.
- Non-negativity: Decision variables cannot take negative values.
Components/Structure of LP Models
- Constraints: Resource limitations expressed mathematically.
- Decision Variables: Quantities to determine for optimal solution.
- Objective Function: Mathematical expression (Z) to maximize or minimize (e.g., profit or cost).
- Non-negativity Restrictions: All decision variables ≥ 0.
Steps in LP Formulation
- List and define decision variables (e.g., x1, x2,…).
- State the objective function involving decision variables and their contributions.
- List constraints based on resource limitations.
- Explicitly state non-negativity restrictions.
Example 1: Burger Production Maximization
- Decision variables: x1 = units of burger A, x2 = units of burger B.
- Objective function: Maximize Z = 8x1 + 7x2.
- Constraints: 2x1 + x2 ≤ 5 (flour), 3x1 + 2x2 ≤ 12 (meat).
- Non-negativity: x1, x2 ≥ 0.
Example 2: Workshop Product Mix Maximization
- Decision variables: x1 = units of A1, x2 = units of A2, x3 = units of S3.
- Objective: Maximize Z = 25x1 + 35x2 + 40x3.
- Constraints: 10x1 + 15x2 + 10x3 ≤ 80 (cutting), 8x1 + 10x2 + 12x3 ≤ 70 (drilling), 9x1 + 12x2 + 15x3 ≤ 60 (polishing).
- Non-negativity: x1, x2, x3 ≥ 0.
Example 3: Diet Minimization Problem
- Decision variables: x1 = Vega Vita tablets, x2 = Half Health tablets per day.
- Objective: Minimize Z = 0.2x1 + 0.3x2 (cost).
- Constraints:
- 20x1 + 30x2 ≥ 60 (Vitamin C),
- 500x1 + 250x2 ≥ 1000 (Calcium),
- 9x1 + 2x2 ≥ 18 (Iron),
- 60x1 + 90x2 ≥ 360 (Magnesium).
- Non-negativity: x1, x2 ≥ 0.
Key Terms & Definitions
- Linear Programming (LP) — Mathematical optimization technique for allocating limited resources.
- Objective Function — Formula to maximize/minimize (e.g., profit or cost).
- Decision Variables — Variables representing quantities to decide (e.g., units produced).
- Constraints — Mathematical expressions of limitations (e.g., resource availability).
- Non-negativity Restrictions — Requirement that decision variables must be ≥ 0.
Action Items / Next Steps
- Review the process of formulating LP models from real problems.
- Practice transforming word problems into LP standard form.