Linear Programming

Linear Programming Formulation and Graphical Solutions

  • Developed by George Dantzig in the 1940s, linear programming (LP) is a widely used management science technique.

  • The term "programming" refers to planning problems described with linear functions, distinct from computer programming.

A Brief Definition

  • Linear programming (LP): Uses linear algebraic relationships to describe decisions under business objectives and resource constraints.

Model Formulation

  • Components:

    • Decision variables: Activity levels the firm chooses.

    • Objective function: A mathematical expression (maximized or minimized) representing the firm's goal.

    • Constraints: Restrictions from the operating environment.

    • Parameters: Fixed numerical coefficients.

Understanding Solutions

  • Feasible solution: Satisfies all constraints (e.g., $(x1, x2) = (0,0)$).

  • Infeasible solution: Violates at least one constraint (e.g., $(-1,0)$).

  • Optimal solution: A feasible solution yielding the best objective value (e.g., $(x1, x2) = (8,0)$ for Maximize $Z = 3x1 + 4x2$).

Model Formulation Steps

  1. Identify and define decision variables.

  2. Define the objective function.

  3. Define constraints.

Beaver Creek Pottery – Model Formulation Example

  • Scenario: Maximize profit from bowls (x1) and mugs (x2) given labor and clay constraints.

  • Objective Function: Maximize Z = 40x1 + 50x2

  • Constraints:

    • Labor: 1x1 + 2x2 \le 40

    • Clay: 4x1 + 3x2 \le 120

    • Non-Negativity: x1, x2 \ge 0

Graphical Analysis

  • Useful for 2D problems, provides intuition for higher dimensions.

  • Steps to Graph a Line: Connect two points satisfying the equation (e.g., for 1x1 + 2x2 = 40, plot (40,0) and (0,20)).

  • Graphing an Inequality: Graph the line, then test a point to determine which half-plane to shade as the feasible region.

  • Feasible region: The area where all constraints are satisfied. Optimal solutions lie within this region.

Objective Value Calculations

  • Plotting objective function lines helps understand the direction of increasing (or decreasing) objective values.

Optimal Solution

  • The optimal solution is the last point the objective function touches as it exits the feasible region, often at the intersection of two constraints.

  • Extreme (Corner) Point Solutions: If an optimal solution exists, it will be at a corner of the feasible region.

Slack and Surplus Variables

  • Slack Variables: Added to "less than or equal to" (\le) constraints to convert them into equalities, indicating unused resources.

  • Surplus Variables: Subtracted from "greater than or equal to" (\ge) constraints to convert them into equalities, indicating excess above a requirement.

Cost Minimization Problem: Fertilizer Example

  • Scenario: Minimize cost of Super-gro (x1) and Crop-quick (x2) bags while meeting minimum nitrogen and phosphate requirements.

  • Objective Function: Minimize Z = 6x1 + 3x2

  • Constraints:

    • Nitrogen: 2x1 + 4x2 \ge 16

    • Phosphate: 4x1 + 3x2 \ge 24

    • Non-Negativity: x1, x2 \ge 0

Irregular Types of Linear Programming Problems

  • Multiple optimal solutions: More than one optimal solution exists.

  • Infeasible problems: No solution satisfies all constraints.

  • Unbounded solutions: Objective function value can increase (or decrease) infinitely.