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
- Subject to Constraints:
- Constant vs. Variable Parameters:
- Fixed values that cannot change in this model: , , , , , , , and .
- Variables that can change: and .
- Value Dependency:
- As decision variables and change, the value of the objective function changes accordingly.
- Numerical Example: If and , the objective function evaluates to
- Practical Meaning of Decision Variables:
- The term "decision" indicates operational decision-making in practice.
- Practical Example: Setting represents an optimized operational decision, such as calculating optimized production demand to equal 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:
- Domain (): The function accepts a vector of real numbers .
- Range (): The function processes the domain inputs and yields a single real value output .
Vectors vs. Scalars:
- Vector: An array of numbers.
- Example Vector: 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:
- Vector: An array of numbers.
Linear Functions Definition:
- A function is linear if its output behavior mimics a straight line.
- Single-Variable General Form:
- is the input function variable (can be a scalar real value or a vector).
- 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 coordinate system using exactly two distinct points.
- Example 1:
- Calculate Point 1 (): Set
- Calculate Point 2 (): Set
- Plotting steps: Locate and on the -plane and draw a straight line passing through both points.
- Example 2:
- Calculate Point 1 (): Set
- Calculate Point 2 (): Set
- Plotting steps: Locate on the horizontal -axis and on the vertical -axis to set . Locate on the -axis and on the -axis to set . Draw an infinite straight line passing through these points.
Dimensionality Limits on Visual Graphing:
- Functions with multiple variables, such as , cannot be visually plotted in two-dimensional space.
- Reason: A function of input variables requires dimensions ( dimension for each variable , plus dimension for the function output ). Because physical representation is constrained to spatial dimensions, a D function cannot be graphed visually.
Representations of Linear Relationships:
- Function Representation: or
- Linear Equation Representation: Replaces with a second variable :
Algebraic Reversibility of Variables:
- Equations can be manipulated algebraically to express as a function of :
- For :
- For :
- Equations can be manipulated algebraically to express as a function of :
General Formats of Linear Equations:
- Standard Linear Equation:
- Example:
- Slope-Intercept Form:
- is the slope (coefficient of ).
- is the --intercept (the point where the line crosses the vertical -axis).
- Example:
- Standard Linear Equation:
Plotting Equations via Satisfying Points:
- To plot an equation such as :
- Find Point 1 (): Let (or using evaluation coordinates: ).
- Find Point 2 (): Let and solve for .
- Connect the two satisfying points on the Cartesian grid with a straight line.
- To plot an equation such as :
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:
- Algebraic Model: Formulating explicit mathematical equations and inequalities.
- Graphical Model: Visualizing constraints and feasible regions in 2D coordinate space.
- 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:
- An glass door with aluminum framing
- 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.
- A manufacturing company (Wyndor Glass Co.) is deciding whether to launch two new products:
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:
- Time required per wood window:
- Total weekly capacity:
- Plant 2:
- Time required per glass door:
- Time required per wood window:
- Total weekly capacity:
- Plant 3:
- Time required per glass door:
- Time required per wood window:
- Total weekly capacity:
- Profit per Unit:
- Glass Door ( or ):
- Wood Window ( or ):
- Plant 1:
Step-by-Step Model Construction:
- Step 1: Define Decision Variables:
- Let = Number of glass doors produced per week
- Let = Number of wood windows produced per week
- Interpretation: represents a decision to manufacture doors per week; represents a decision to manufacture windows per week.
- Alternative Notation: Variable labels are arbitrary symbols (e.g., for doors, for windows).
- Step 2: Formulate Constraints:
- Non-Negativity Constraint: Physical production cannot be negative ( is impossible). Thus, production must be positive or zero: and
- Plant 1 Capacity: Total production hours cannot exceed hours:
- Plant 2 Capacity: Total production hours cannot exceed hours:
- Plant 3 Capacity: Total production hours cannot exceed hours:
- Infeasibility Test: Testing a production level of doors and windows in Plant 2 yields , which exceeds the limit and is infeasible.
- Step 3: Define Objective Function:
- Total Profit =
- Step 1: Define Decision Variables:
Complete Linear Programming Formulation:
Graphical Solution Method and Feasible Region
Plotting Linear Inequalities on a 2D Plane:
- Constraint 1 ():
- Draw vertical boundary line
- The inequality includes all space on and to the left of
- Constraint 2 ():
- Draw horizontal boundary line
- The inequality includes all space on and below
- Constraint 3 ():
- Convert to linear equality
- Find Point 1: Set
- Find Point 2: Set
- Draw a line through and . The inequality includes the region on and below this line toward the origin.
- Constraints 4 & 5 (, ):
- Bound the region to the positive upper-right quadrant of the Cartesian plane ( vertical axis, horizontal axis).
- Constraint 1 ():
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 is non-feasible because its -coordinate () violates Constraint 1 ().
Questions & Discussion
- Plant Capacity Allocation vs. Profit Maximization:
- Question: If the company produces only doors, Plant 1 leaves hours of its capacity unused. Why not produce additional doors to fully utilize Plant 1 capacity and increase total profit?
- Answer: Producing additional doors requires shared production time in Plant 3 (). Because Plant 3 capacity is capped at hours, increasing door production forces a decrease in window production. Because windows generate a higher profit per unit () compared to doors (), 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.