Mathematical Foundations of Linear Optimization and Graphical Solution Methods

Mathematical Foundations of Linear Optimization

  • Core Definitions and Terminology:

    • Objective Function: A mathematical function or measure that needs to be optimized through either maximization (e.g., profit) or minimization (e.g., cost).
    • Constraint Functions: Functional restrictions placed on decision variables, expressed as mathematical equalities or inequalities.
    • Decision Variables: Variables within an optimization model that represent practical decisions to be made. Their values are varied to achieve the optimal objective function output.
  • Mathematical Model Structure Example:

    • Objective: Maximize or minimize an objective function such as 3x+5y3x + 5y
    • Subject to Constraints:
      • 2x+1≤52x + 1 \le 5
      • −2y+4x≤10-2y + 4x \le 10
      • x≥0x \ge 0
      • y≥0y \ge 0
    • Constant vs. Variable Parameters:
      • Fixed values that cannot change in this model: min\text{min}, max\text{max}, 55, 1010, 44, 22, 11, and 00.
      • Variables that can change: xx and yy.
    • Value Dependency:
      • As decision variables xx and yy change, the value of the objective function changes accordingly.
      • Numerical Example: If x=0x = 0 and y=2y = 2, the objective function evaluates to 3(0)+5(2)=103(0) + 5(2) = 10
    • Practical Meaning of Decision Variables:
      • The term "decision" indicates operational decision-making in practice.
      • Practical Example: Setting x=0x = 0 represents an optimized operational decision, such as calculating optimized production demand to equal 00 units.
  • Mathematical Functions and Domain Mapping:

    • An optimization model uses mathematical functions where all components (objective function and constraints) follow standard function definitions.
    • General Function Notation: f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R}
      • Domain (Rn\mathbb{R}^n): The function accepts a vector of nn real numbers (x1,x2,…,xn)(x_1, x_2, \dots, x_n).
      • Range (R\mathbb{R}): The function processes the domain inputs and yields a single real value output f(x1,x2,…,xn)f(x_1, x_2, \dots, x_n).
  • Vectors vs. Scalars:

    • Vector: An array of numbers.
      • Example Vector: x=[1,4,−10,5.3,105]x = [1, 4, -10, 5.3, 10^5] is a vector of length 5$.\n * **Scalar**: A single numeric value, which can also be viewed as a vector of length 1$.
      • Example Scalar: x=−3x = -3
  • Linear Functions Definition:

    • A function is linear if its output behavior mimics a straight line.
    • Single-Variable General Form: f(x)=ax+bf(x) = ax + b
      • xx is the input function variable (can be a scalar real value or a vector).
      • ax+bax + b is the calculated output value.

Graphing Linear Functions and Equations

  • Plotting Single-Variable Linear Functions:

    • A linear function of one variable can be drawn on a two-dimensional (x,y)(x, y) coordinate system using exactly two distinct points.
    • Example 1: f(x)=−3x+4f(x) = -3x + 4
      • Calculate Point 1 (P1P_1): Set x=0  ⟹  f(0)=−3(0)+4=4  ⟹  P1=(0,4)x = 0 \implies f(0) = -3(0) + 4 = 4 \implies P_1 = (0, 4)
      • Calculate Point 2 (P2P_2): Set x=1  ⟹  f(1)=−3(1)+4=1  ⟹  P2=(1,1)x = 1 \implies f(1) = -3(1) + 4 = 1 \implies P_2 = (1, 1)
      • Plotting steps: Locate P1(0,4)P_1(0, 4) and P2(1,1)P_2(1, 1) on the xyxy-plane and draw a straight line passing through both points.
    • Example 2: f(x)=2x+1f(x) = 2x + 1
      • Calculate Point 1 (P1P_1): Set x=0  ⟹  f(0)=2(0)+1=1  ⟹  P1=(0,1)x = 0 \implies f(0) = 2(0) + 1 = 1 \implies P_1 = (0, 1)
      • Calculate Point 2 (P2P_2): Set x=1  ⟹  f(1)=2(1)+1=3  ⟹  P2=(1,3)x = 1 \implies f(1) = 2(1) + 1 = 3 \implies P_2 = (1, 3)
      • Plotting steps: Locate 00 on the horizontal xx-axis and 11 on the vertical yy-axis to set P1(0,1)P_1(0, 1). Locate 11 on the xx-axis and 33 on the yy-axis to set P2(1,3)P_2(1, 3). Draw an infinite straight line passing through these points.
  • Dimensionality Limits on Visual Graphing:

    • Functions with multiple variables, such as f(x1,x2,x3)=3x1+5x2−8x3+100f(x_1, x_2, x_3) = 3x_1 + 5x_2 - 8x_3 + 100, cannot be visually plotted in two-dimensional space.
    • Reason: A function of 33 input variables requires 44 dimensions (11 dimension for each variable x1,x2,x3x_1, x_2, x_3, plus 11 dimension for the function output ff). Because physical representation is constrained to 33 spatial dimensions, a 44D function cannot be graphed visually.
  • Representations of Linear Relationships:

    • Function Representation: f(x)=2x+1f(x) = 2x + 1 or f(x)=−5x+2f(x) = -5x + 2
    • Linear Equation Representation: Replaces f(x)f(x) with a second variable yy:
      • y=2x+1y = 2x + 1
      • y=−5x+2y = -5x + 2
  • Algebraic Reversibility of Variables:

    • Equations can be manipulated algebraically to express xx as a function of yy:
      • For y=2x+1y = 2x + 1:             y−1=2x  ⟹  x=y−12=12(y−1)y - 1 = 2x \implies x = \frac{y - 1}{2} = \frac{1}{2}(y - 1)
      • For y=−5x+2y = -5x + 2:             y−2=−5x  ⟹  x=y−2−5=−15(y−2)y - 2 = -5x \implies x = \frac{y - 2}{-5} = -\frac{1}{5}(y - 2)
  • General Formats of Linear Equations:

    • Standard Linear Equation: ax+by=cax + by = c
      • Example: 2x+3y=22x + 3y = 2
    • Slope-Intercept Form: y=mx+by = mx + b
      • mm is the slope (coefficient of xx).
      • bb is the yy--intercept (the point where the line crosses the vertical yy-axis).
      • Example: y=−23x+4y = -\frac{2}{3}x + 4
  • Plotting Equations via Satisfying Points:

    • To plot an equation such as 2x+3y=2y2x + 3y = 2y:
      • Find Point 1 (P1P_1): Let x=0  ⟹  2(0)+3y=2y  ⟹  y=0x = 0 \implies 2(0) + 3y = 2y \implies y = 0 (or using evaluation coordinates: P1=(0,4)P_1 = (0, 4)).
      • Find Point 2 (P2P_2): Let x=1x = 1 and solve for yy.
      • Connect the two satisfying points on the Cartesian grid with a straight line.

Fundamentals of Linear Programming

  • Core Concepts Definition:

    • Decision Variable: A controllable choice in the problem whose value is optimized to solve the model.
    • Objective Function: A quantitative measure or performance metric (such as total profit or total operational cost) targeted for maximization or minimization.
    • Functional Constraints: A collection of mathematical equality or inequality restrictions that set limits on allowable values for decision variables.
    • Linear Program (LP) Definition: An optimization problem in which both the objective function and all functional constraints are purely linear equations or linear inequalities.
  • Applications of Linear Programming in Management Science:

    • Production planning
    • Workforce scheduling, employee assignment, and work shift planning
    • Transportation, distribution, and logistics optimization
    • Large-Scale Application: Flight scheduling under delay conditions forms a massive-scale linear program featuring numerous constraints.
  • Computational Software Tools:

    • Small-scale models can be solved graphically or using Microsoft Excel (Solver).
    • Large-scale commercial problems (such as airline flight transportation models) require specialized optimization solvers like CPLEX.
  • Three Modeling Approaches:

    1. Algebraic Model: Formulating explicit mathematical equations and inequalities.
    2. Graphical Model: Visualizing constraints and feasible regions in 2D coordinate space.
    3. Solver Spreadsheet Model: Implementing model parameters inside spreadsheets like Excel.

Wyndor Glass Company Case Study Formulation

  • Problem Context and Background:

    • A manufacturing company (Wyndor Glass Co.) is deciding whether to launch two new products:
      1. An 8-foot8\text{-foot} glass door with aluminum framing
      2. A wood-framed window
    • The production process takes place across three distinct plants:
      • Plant 1: Produces aluminum frames and hardware.
      • Plant 2: Produces wood frames.
      • Plant 3: Produces glass and performs final assembly for both doors and windows.
  • Key Managerial Questions:

    • Should the company launch these two new products?
    • Is launching these products profitable?
    • If launched, what is the optimal product mix (number of units produced per week for each product)?
  • Production and Financial Data Matrix:

    • Plant 1:
      • Time required per glass door: 1 hour1\, \text{hour}
      • Time required per wood window: 0 hours0\, \text{hours}
      • Total weekly capacity: 4 hours4\, \text{hours}
    • Plant 2:
      • Time required per glass door: 0 hours0\, \text{hours}
      • Time required per wood window: 2 hours2\, \text{hours}
      • Total weekly capacity: 12 hours12\, \text{hours}
    • Plant 3:
      • Time required per glass door: 3 hours3\, \text{hours}
      • Time required per wood window: 2 hours2\, \text{hours}
      • Total weekly capacity: 18 hours18\, \text{hours}
    • Profit per Unit:
      • Glass Door (xx or dd): $300\$300
      • Wood Window (yy or ww): $500\$500
  • Step-by-Step Model Construction:

    • Step 1: Define Decision Variables:
      • Let xx = Number of glass doors produced per week
      • Let yy = Number of wood windows produced per week
      • Interpretation: x=10x = 10 represents a decision to manufacture 1010 doors per week; y=50y = 50 represents a decision to manufacture 5050 windows per week.
      • Alternative Notation: Variable labels are arbitrary symbols (e.g., dd for doors, ww for windows).
    • Step 2: Formulate Constraints:
      • Non-Negativity Constraint: Physical production cannot be negative (x=−21x = -21 is impossible). Thus, production must be positive or zero: x≥0x \ge 0 and y≥0y \ge 0
      • Plant 1 Capacity: Total production hours cannot exceed 44 hours:             1x+0y≤4  ⟹  x≤41x + 0y \le 4 \implies x \le 4
      • Plant 2 Capacity: Total production hours cannot exceed 1212 hours:             0x+2y≤12  ⟹  2y≤120x + 2y \le 12 \implies 2y \le 12
      • Plant 3 Capacity: Total production hours cannot exceed 1818 hours:             3x+2y≤183x + 2y \le 18
      • Infeasibility Test: Testing a production level of x=10x = 10 doors and y=12y = 12 windows in Plant 2 yields 0(10)+2(12)=24 hours0(10) + 2(12) = 24\, \text{hours}, which exceeds the 12-hour12\text{-hour} limit and is infeasible.
    • Step 3: Define Objective Function:
      • Total Profit = 300x+500y300x + 500y
  • Complete Linear Programming Formulation:     Maximize 300x+500y\text{Maximize } 300x + 500ySubject to:\text{Subject to:}x≤4(C1:Plant 1 capacity)x \le 4 \quad (C_1: \text{Plant 1 capacity})2y≤12(C2:Plant 2 capacity)2y \le 12 \quad (C_2: \text{Plant 2 capacity})3x+2y≤18(C3:Plant 3 capacity)3x + 2y \le 18 \quad (C_3: \text{Plant 3 capacity})x≥0(C4:Non-negativity of doors)x \ge 0 \quad (C_4: \text{Non-negativity of doors})y≥0(C5:Non-negativity of windows)y \ge 0 \quad (C_5: \text{Non-negativity of windows})

Graphical Solution Method and Feasible Region

  • Plotting Linear Inequalities on a 2D Plane:

    • Constraint 1 (C1:x≤4C_1: x \le 4):
      • Draw vertical boundary line x=4x = 4
      • The inequality includes all space on and to the left of x=4x = 4
    • Constraint 2 (C2:2y≤12  ⟹  y≤6C_2: 2y \le 12 \implies y \le 6):
      • Draw horizontal boundary line y=6y = 6
      • The inequality includes all space on and below y=6y = 6
    • Constraint 3 (C3:3x+2y≤18C_3: 3x + 2y \le 18):
      • Convert to linear equality 3x+2y=183x + 2y = 18
      • Find Point 1: Set y=0  ⟹  3x=18  ⟹  x=6  ⟹  (6,0)y = 0 \implies 3x = 18 \implies x = 6 \implies (6, 0)
      • Find Point 2: Set x=4  ⟹  3(4)+2y=18  ⟹  2y=6  ⟹  y=3  ⟹  (4,3)x = 4 \implies 3(4) + 2y = 18 \implies 2y = 6 \implies y = 3 \implies (4, 3)
      • Draw a line through (6,0)(6, 0) and (4,3)(4, 3). The inequality includes the region on and below this line toward the origin.
    • Constraints 4 & 5 (C4:x≥0C_4: x \ge 0, C5:y≥0C_5: y \ge 0):
      • Bound the region to the positive upper-right quadrant of the Cartesian plane (x=0x = 0 vertical axis, y=0y = 0 horizontal axis).
  • The Feasible Region (Feasible Set):

    • Definition: The shaded area created by the intersection of all single constraint regions.
    • Every point within or along the boundary of the shaded feasible region satisfies all objective constraints simultaneously.
    • Any decision point outside this shaded area is infeasible and violates one or more constraints.
    • Infeasible Point Example: The coordinate point (5,4)(5, 4) is non-feasible because its xx-coordinate (x=5x = 5) violates Constraint 1 (x≤4x \le 4).

Questions & Discussion

  • Plant Capacity Allocation vs. Profit Maximization:
    • Question: If the company produces only 22 doors, Plant 1 leaves 22 hours of its 4-hour4\text{-hour} capacity unused. Why not produce 22 additional doors to fully utilize Plant 1 capacity and increase total profit?
    • Answer: Producing additional doors requires shared production time in Plant 3 (3x+2y≤183x + 2y \le 18). Because Plant 3 capacity is capped at 1818 hours, increasing door production forces a decrease in window production. Because windows generate a higher profit per unit ($500\$500) compared to doors ($300\$300), diverting Plant 3 capacity away from windows to make more doors lowers total overall profit. Optimization balances resource usage across all plants rather than attempting to maximize individual plant capacity.