Linear Programming: Mathematical Modeling, Graphical Solutions, and Special Cases

Fundamentals of Linear Programming

• Resource Allocation Context: Management decisions routinely focus on making the most effective and efficient use of scarce, limited resources such as labor, capital, machinery, and raw materials.

• Definition of Linear Programming (LP): A widely utilized mathematical modeling technique designed to guide managers in planning, operational scheduling, and decision-making regarding resource allocation.

• Primary Purpose: LP serves as an analytical optimization tool engineered to find the maximum or minimum value of a specific quantity subject to operational limitations.

• Disciplinary Scope: Linear programming is situated within the broader discipline of mathematical programming, an integral branch of management science and operations research.

• Terminology Distinction: In management science, the word programming does not refer to computer programming or software coding; rather, it denotes the mathematical formulation and systematic solving of an operational problem.

• Broad Functional Applications of LP:

  • Accounting: Cost allocation, auditing sample optimization, and budgeting.

  • Agriculture: Crop rotation, land utilization, and livestock feed blending.

  • Finance: Portfolio selection, investment asset allocation, and capital budgeting.

  • Industrial and Manufacturing: Product mix determination, assembly line balancing, and production scheduling.

  • Marketing: Media selection, advertising budget distribution, and campaign scheduling.

  • Military Operations: Deployment logistics, supply chain routing, and strategic resource distribution.

Components of the General Optimization Model

• Objective Function: The mathematical expression that represents the specific goal to be maximized (such as total profit, revenue, or efficiency) or minimized (such as total production cost, scrap, or transit time).

• Decision Variables: The controllable variables that a manager can adjust. The selected numerical values of these variables directly dictate the resulting value of the objective function.

• Constraints: Structural restrictions, limitations, or boundaries placed upon the decision variables. Constraints reflect physical, policy, financial, or technological limitations (e.g., maximum available machine hours or minimum production quotas).

• Parameters: Fixed numerical constants and coefficients present within both the objective function and the constraints. These define unit resource requirements, unit profits or costs, and total resource availabilities.

Core Requirements and Assumptions of Linear Programming

• Four Common Properties of All LP Problems:

  • Optimization Objective: Every LP problem explicitly seeks to maximize or minimize a specific quantitative measure.

  • Presence of Constraints: There must be structural limitations that restrict the degree to which the organization can pursue its objective.

  • Alternative Courses of Action: There must be multiple viable alternatives, production combinations, or variable settings from which management can choose.

  • Linear Relationships: The objective function and all constraint conditions must be expressed entirely as linear equations or linear inequalities (first-degree relationships with no powers, roots, or product-of-variables terms).

• Five Foundational Assumptions of LP:

  • Certainty: Conditions of complete certainty are assumed. All parameters (coefficients in the objective function, resource consumption rates in constraints, and right-hand side capacity limits) are known with exactness and do not fluctuate during the planning period.

  • Proportionality: The contribution of each decision variable to the objective function, as well as its consumption of each constrained resource, is directly proportional to the value of that variable. Economies of scale, volume discounts, and setup costs are absent.

  • Additivity: The total value of the objective function and the total resource utilization in each constraint equal the exact algebraic sum of the individual contributions or resource consumptions resulting from each activity evaluated independently. Synergies and interaction effects do not occur.

  • Divisibility: Decision variables are continuous rather than restricted to integers. Solution values need not be whole numbers; fractional or decimal units (e.g., producing $30.5$ units) are mathematically valid.

  • Nonnegativity: All decision variables must assume values greater than or equal to zero ($x_i \ge 0$). Negative quantities of goods cannot physically be manufactured or consumed.

Systematic Steps in Formulating Linear Programs

• Mathematical Model Development: LP formulation translates a real-world managerial scenario into a structured mathematical representation.

• Step 1: Understand the Problem: Develop a complete understanding of the managerial situation, operational context, resource limitations, and organizational objectives.

• Step 2: Identify Objectives and Constraints: Pinpoint the single quantity to be optimized (maximization or minimization) and list all restrictions, quotas, and limits that constrain performance.

• Step 3: Define Decision Variables: Clearly declare mathematical variables representing the unknown quantities to be determined, specifying their exact units of measure and time intervals.

• Step 4: Construct Expressions: Use the defined decision variables to write explicit mathematical expressions for the objective function and all functional constraints, concluding with nonnegativity statements.

Product Mix Formulation: Flair Furniture Company Case Study

• Product Mix Context: The product mix problem is among the most widespread LP applications. A firm produces two or more items using shared, limited resources (labor, machinery, materials) and seeks to find the specific production quantity for each item that maximizes total profit contribution.

• Case Scenario Details:

  • The Flair Furniture Company produces two products: inexpensive tables ($T$) and chairs ($C$).

  • Production involves two distinct departments: Carpentry and Painting/Varnishing.

  • Each table ($T$) requires $4\,\text{hours}$ of carpentry and $2\,\text{hours}$ of painting and varnishing.

  • Each chair ($C$) requires $3\,\text{hours}$ of carpentry and $1\,\text{hour}$ of painting and varnishing.

  • Available resource capacity during the current production period: $240\,\text{hours}$ of carpentry time and $100\,\text{hours}$ of painting/varnishing time.

  • Profit margins: Each table yields a profit of \\$70, and each chair yields a profit of \\$50.

• Operational Resource and Profit Breakdown:

• Decision Variables Definition:

  • $T = \text{number of tables to produce per week}$

  • $C = \text{number of chairs to produce per week}$

• Complete LP Mathematical Formulation:

  • Objective Function:     $\text{Maximize Profit} = 70T + 50C$

  • Subject to:     $4T + 3C \le 240 \quad (\text{Carpentry labor constraint})$     $2T + 1C \le 100 \quad (\text{Painting and varnishing constraint})$     $T \ge 0, \quad C \ge 0 \quad (\text{Nonnegativity conditions})$

Graphical Solution Methodology: Feasible Region Determination

• Conceptual Definitions:

  • Feasible Region: The set of all possible points that simultaneously satisfy all constraints and sign restrictions in the LP problem.

  • Optimal Solution (Maximization): A point within the feasible region that yields the largest objective function value.

  • Optimal Solution (Minimization): A point within the feasible region that yields the smallest objective function value.

• Steps to Establish the Feasible Region:

  • Step 1: Graph All Constraints: Convert each inequality into an equality line and plot it on the coordinate axes.

  • Step 2: Shade Feasible Half-Spaces: For each constraint, identify the side of the boundary line that satisfies the inequality condition using a test point such as $(0, 0)$.

  • Step 3: Identify the Overlapping Area: The intersection of all shaded half-spaces and nonnegativity conditions defines the feasible region.

• Graphical Implementation for Flair Furniture:

  • Nonnegativity Boundaries ($T \ge 0, C \ge 0$): The vertical axis ($C$-axis) represents the boundary line $T = 0$, meaning all valid points must lie to the right ($T \ge 0$). The horizontal axis ($T$-axis) represents $C = 0$, meaning all valid points must lie above ($C \ge 0$). The search space is entirely confined to the first quadrant.

  • Carpentry Constraint ($4T + 3C \le 240$):

  • Find intercepts for the boundary line $4T + 3C = 240$:

    • When $T = 0$, $3C = 240 \implies C = 80$; intercept is $(0, 80)$.

    • When $C = 0$, $4T = 240 \implies T = 60$; intercept is $(60, 0)$.

  • Connecting these points yields the line. Testing $(0, 0)$ gives $4(0) + 3(0) = 0 \le 240$ (true), so the area below and to the left is feasible.

  • Point verification: Point $(30, 20)$ gives $4(30) + 3(20) = 180 \le 240$ (feasible). Point $(70, 40)$ gives $4(70) + 3(40) = 400 > 240$ (infeasible).

  • Painting and Varnishing Constraint ($2T + 1C \le 100$):

  • Find intercepts for the boundary line $2T + C = 100$:

    • When $T = 0$, $C = 100$; intercept is $(0, 100)$.

    • When $C = 0$, $2T = 100 \implies T = 50$; intercept is $(50, 0)$.

  • Testing $(0, 0)$ yields $2(0) + 0 = 0 \le 100$ (true), meaning the region below and to the left is feasible.

  • Composite Feasible Region: The intersection forms a four-sided convex polygon bounded by the points $(0, 0)$, $(50, 0)$, the boundary intersection, and $(0, 80)$.

Finding the Optimal Solution: Isoprofit Line Method

• Method Concept: An isoprofit line represents every combination of decision variables that yields the exact same total profit. All isoprofit lines for a given LP problem share the identical slope ($-\frac{70}{50} = -1.4$).

• Step-by-Step Procedure:

  • Step 1: Assume an arbitrary, easily calculated profit figure to begin (e.g., \\$2{,}100).

  • Step 2: Formulate the line equation: $70T + 50C = 2{,}100$.

  • Step 3: Calculate the intercepts:

  • If $T = 0$, $C = \frac{2{,}100}{50} = 42$

  • If $C = 0$, $T = \frac{2{,}100}{70} = 30$

  • Plot the line through $(0, 42)$ and $(30, 0)$.

  • Step 4: Select progressively higher profit targets to observe the outward progression:

  • For \\$2{,}800: $70T + 50C = 2{,}800 \implies (0, 56)$ and $(40, 0)$

  • For \\$3{,}500: $70T + 50C = 3{,}500 \implies (0, 70)$ and $(50, 0)$

  • For \\$4{,}200: $70T + 50C = 4{,}200 \implies (0, 84)$ and $(60, 0)$ (located entirely outside the feasible region, indicating infeasibility at this profit level)

  • Step 5: Slide the objective function line in the direction of increasing profit (upward and to the right) while strictly maintaining its slope.

  • Step 6: Identify the final point within the feasible region that the line touches immediately before leaving the region entirely. That point of tangency is the optimal solution.

  • Optimal Solution Result: The last contact point occurs at coordinates $(T = 30, C = 40)$, which lies on the maximum profit line of \\$4{,}100:     $\text{Profit} = 70(30) + 50(40) = 2{,}100 + 2{,}000 = 4{,}100$

Finding the Optimal Solution: Corner Point Method

• Mathematical Foundation: According to the Fundamental Theorem of Linear Programming, an optimal solution to any linear programming problem will always occur at one of the corner points (also referred to as extreme points) of the feasible region.

• Corner Point Method Procedure:

  • Step 1: Graph all constraints and identify the feasible region.

  • Step 2: Identify the coordinates of every corner point bounding the feasible region.

  • Step 3: Calculate the objective function value at each corner point.

  • Step 4: Select the corner point that produces the best value (maximum profit or minimum cost). This is the optimal solution.

• Algebraic Intersection Computation for Flair Furniture:

  • The upper-right extreme point is formed by the intersection of the two binding constraint equations:     $4T + 3C = 240 \quad (1)$     $2T + C = 100 \quad (2)$

  • Solve simultaneously using elimination:

  • Multiply equation (2) by $2$:       $4T + 2C = 200 \quad (3)$

  • Subtract equation (3) from equation (1):       $(4T + 3C) - (4T + 2C) = 240 - 200$       $C = 40$

  • Substitute $C = 40$ into equation (2):       $2T + 40 = 100 \implies 2T = 60 \implies T = 30$

  • The intersection point is $(30, 40)$.

• Profit Evaluation at All Feasible Corner Points:

• Managerial Conclusion: Producing $30\,\text{tables}$ and $40\,\text{chairs}$ per week generates the absolute maximum profit of \\$4{,}100.

Summary Comparison of Graphical Solution Methods

• Isoprofit / Isocost Method:

  • Step 1: Graph all constraints and trace the boundary of the feasible region.

  • Step 2: Select an arbitrary profit (or cost) level and graph the corresponding linear equation to establish its slope.

  • Step 3: Translate the line parallel to itself in the direction of increasing profit (or decreasing cost). The last point touched in the feasible region is the optimal solution.

  • Step 4: Read or compute the coordinates of this final contact point and calculate the optimal objective value.

• Corner Point Method:

  • Step 1: Graph all constraints and find the feasible region.

  • Step 2: Identify all corner points (vertices) of the feasible region, solving constraint equations simultaneously where lines intersect.

  • Step 3: Evaluate the objective function at each corner point.

  • Step 4: Choose the corner point offering the highest value (for maximization) or lowest value (for minimization).

Comprehensive Application: Ali's Woodcarving Company Case Study

• Problem Context: Ali's Woodcarving Co. manufactures two lines of wooden toys: soldiers ($x_1$) and trains ($x_2$).

• Revenue and Cost Parameters:

  • Soldiers: Selling price = \\$27, raw material cost = \\$10, variable labor and overhead cost = \\$14.     \text{Unit Profit Contribution for Soldiers} = 27 - (10 + 14) = 27 - 24 = \\$3

  • Trains: Selling price = \\$21, raw material cost = \\$9, variable labor and overhead cost = \\$10.     \text{Unit Profit Contribution for Trains} = 21 - (9 + 10) = 21 - 19 = \\$2

• Labor Operations and Weekly Limits:

  • Two skilled labor crafts are required: finishing and carpentry.

  • Each soldier requires $2\,\text{hours}$ of finishing labor and $1\,\text{hour}$ of carpentry labor.

  • Each train requires $1\,\text{hour}$ of finishing labor and $1\,\text{hour}$ of carpentry labor.

  • Weekly available labor: Ali can acquire all needed raw materials, but has access to only $100\,\text{hours}$ of finishing labor and $80\,\text{hours}$ of carpentry labor per week.

• Demand Restrictions:

  • Demand for trains is completely unlimited.

  • Market demand for soldiers is limited to a maximum of $40\,\text{soldiers}$ per week ($x_1 \le 40$).

• Data Summary Table:

• Linear Programming Formulation:

  • Decision Variables:

  • $x_1 = \text{number of soldiers manufactured each week}$

  • $x_2 = \text{number of trains manufactured each week}$

  • Objective Function:     $\text{Maximize } P = 3x_1 + 2x_2$

  • Constraints:     $2x_1 + x_2 \le 100 \quad (\text{Finishing hours constraint})$     $x_1 + x_2 \le 80 \quad (\text{Carpentry hours constraint})$     $x_1 \le 40 \quad (\text{Market demand constraint on soldiers})$     $x_1 \ge 0, \quad x_2 \ge 0 \quad (\text{Nonnegativity})$

• Evaluation of Feasible Corner Points:

  • Corner Point 1: (x_1 = 0, x_2 = 0) \implies P = 3(0) + 2(0) = \\$0

  • Corner Point 2: (x_1 = 40, x_2 = 0) \implies P = 3(40) + 2(0) = \\$120

  • Corner Point 3: Intersection of $x_1 = 40$ and finishing line $2x_1 + x_2 = 100$:     $2(40) + x_2 = 100 \implies x_2 = 20$     Check carpentry: $40 + 20 = 60 \le 80$ (satisfied).     Coordinates: (40, 20) \implies P = 3(40) + 2(20) = 120 + 40 = \\$160

  • Corner Point 4: Intersection of finishing constraint ($2x_1 + x_2 = 100$) and carpentry constraint ($x_1 + x_2 = 80$):

  • Subtract equations:       $(2x_1 + x_2) - (x_1 + x_2) = 100 - 80 \implies x_1 = 20$

  • Solve for $x_2$:       $20 + x_2 = 80 \implies x_2 = 60$

  • Check demand constraint: $x_1 = 20 \le 40$ (satisfied).

  • Coordinates: (20, 60) \implies P = 3(20) + 2(60) = 60 + 120 = \\$180

  • Corner Point 5: (x_1 = 0, x_2 = 80) \implies P = 3(0) + 2(80) = \\$160

• Optimal Production Decision: The optimal solution is $(x_1 = 20, x_2 = 60)$. Ali maximizes weekly profit at \\$180 by manufacturing $20\,\text{soldiers}$ and $60\,\text{trains}$ each week.

Special Cases in Linear Programming

• The Four Special Anomalies in LP:

  • No feasible solution (Infeasibility)

  • Unboundedness

  • Redundancy

  • Alternate optimal solutions

• Special Case 1: No Feasible Solution (Infeasibility):

  • Definition: Occurs when no single combination of values for the decision variables satisfies all constraint equations and nonnegativity restrictions simultaneously. The feasible region does not exist (it is empty).

  • Practical Reality: Frequent in complex organizations when conflicting or overly restrictive operating targets are established by different departments.

  • Resolution: One or more constraints must be systematically relaxed, adjusted, or eliminated until an overlapping feasible region emerges.

  • Mathematical Example:     $\text{Maximize } Z$     Subject to:     $x_1 + 2x_2 \le 6$     $2x_1 + x_2 \le 8$     $x_1 \ge 7$     $x_1 \ge 0, \quad x_2 \ge 0$

  • Analysis: The first two constraints restrict the upper limit of $x_1$ to at most $4$ (when $x_2 = 0$ in $2x_1 \le 8$). However, the third constraint mandates that $x_1 \ge 7$. Because $x_1$ cannot simultaneously be less than or equal to $4$ and greater than or equal to $7$, the constraint areas do not overlap.

• Special Case 2: Unboundedness:

  • Definition: Occurs when the value of the objective function can be increased (in a maximization model) or decreased (in a minimization model) indefinitely without violating any constraints.

  • Graphical Appearance: The feasible region is entirely open-ended in the direction of the objective function. The isoprofit line can move infinitely outward without encountering a limiting boundary.

  • Practical Implication: An unbounded solution virtually always indicates an error in model formulation, such as omitting a vital operational constraint or reversing an inequality sign (e.g., using $\ge$ instead of $\le$).

  • Mathematical Example:     $\text{Maximize } Z = 2x_1 - x_2$     Subject to:     $x_1 - x_2 \le 1$     $2x_1 + x_2 \ge 6$     $x_1 \ge 0, \quad x_2 \ge 0$

  • Analysis: As $x_1$ and $x_2$ expand simultaneously toward positive infinity along the boundary ray $x_1 - x_2 = 1$, the objective value $Z = 2x_1 - (x_1 - 1) = x_1 + 1$ increases toward infinity without violating any constraints.

• Special Case 3: Redundancy:

  • Definition: A redundant constraint is a restriction that does not affect, limit, or alter the feasible solution region.

  • Operational Impact: Redundant constraints introduce no mathematical errors into the problem, but identifying and eliminating them simplifies the algebraic model and reduces computation time.

  • Mathematical Example:     $\text{Maximize Profit} = 1X_1 + 2X_2$     Subject to:     $X_1 + X_2 \le 20$     $2X_1 + X_2 \le 30$     $X_1 \le 25$     $X_1 \ge 0, \quad X_2 \ge 0$

  • Analysis: The constraint $X_1 + X_2 \le 20$ inherently restricts $X_1$ to a maximum value of $20$ when $X_2 = 0$. Consequently, the constraint $X_1 \le 25$ lies entirely beyond the active boundary and plays no role in defining the feasible region.

• Special Case 4: Alternate Optimal Solutions (Multiple Optima):

  • Definition: Occurs when two or more distinct extreme corner points yield the exact same optimal objective value.

  • Graphical Condition: Occurs when the slope of the objective function (isoprofit or isocost line) is exactly parallel to the slope of a binding constraint line.

  • Solution Span: Every point located on the line segment connecting the two optimal corner points is also an optimal solution, yielding an infinite number of alternative optimal operating plans.

  • Managerial Significance: Multiple optimal solutions offer management significant operational flexibility. Decision-makers can choose among different production schedules to satisfy non-modeled criteria (such as labor stability, storage room, or supplier loyalty) without sacrificing profit.

  • Mathematical Example:     $\text{Maximize } D = 3x_1 + 2x_2$     Subject to:     $3x_1 + 2x_2 \le 120$     $x_1 + x_2 \le 50$     $x_1 \ge 0, \quad x_2 \ge 0$

  • Analysis: The objective function $D = 3x_1 + 2x_2$ has a slope of $-\frac{3}{2}$, which is identical to the slope of the binding constraint $3x_1 + 2x_2 = 120$. Evaluating the corner points along this boundary:

  • Point $(40, 0) \implies D = 3(40) + 2(0) = 120$

  • Intersection point of $3x_1 + 2x_2 = 120$ and $x_1 + x_2 = 50$ is $(20, 30)$.

  • Point $(20, 30) \implies D = 3(20) + 2(30) = 60 + 60 = 120$

  • Any point lying on the line segment joining $(40, 0)$ and $(20, 30)$ yields $D = 120$.

Resource Utilization: Slack, Surplus, and Constraint Binding

• Mathematical Definitions:

  • Slack:

  • Associated with less-than-or-equal-to ($\le$) constraints, which represent resource availability caps.

  • Measures the unused or unconsumed amount of a limited resource.     $\text{Slack} = (\text{Amount of resource available}) - (\text{Amount of resource used}) = \text{RHS} - \text{LHS}$

  • Surplus:

  • Associated with greater-than-or-equal-to ($\ge$) constraints, which denote minimum requirement specifications.

  • Measures the amount by which an actual operational outcome exceeds the required minimum standard.     $\text{Surplus} = (\text{Actual amount achieved}) - (\text{Minimum required amount}) = \text{LHS} - \text{RHS}$

• Constraint Classification at the Optimal Solution:

  • Binding Constraint: A constraint that has a slack or surplus value of zero ($\text{Slack} = 0$ or $\text{Surplus} = 0$) at the optimal solution. The resource is completely consumed, or the exact minimum requirement is met. Binding constraints form the active boundaries that limit further improvement of the objective function.

  • Nonbinding Constraint: A constraint that has a strictly positive slack or surplus value ($\text{Slack} > 0$ or $\text{Surplus} > 0$) at the optimal solution. Unused capacity remains, or the specification is exceeded. Marginally relaxing a nonbinding constraint has no effect on the optimal solution.

• Computational Reporting: LP computer software solvers systematically generate slack and surplus values for all constraints in their standard sensitivity and optimal solution reports.

• Worked Example: Constraint Slack in the Flair Furniture Case:

  • Given the optimal solution: $T = 30\,\text{tables}$, $C = 40\,\text{chairs}$.

  • Carpentry Constraint ($4T + 3C \le 240$):

  • Actual hours consumed (LHS): $4(30) + 3(40) = 120 + 120 = 240\,\text{hours}$

  • Resource limit available (RHS): $240\,\text{hours}$     $\text{Slack} = \text{RHS} - \text{LHS} = 240 - 240 = 0\,\text{hours}$

  • Status: Binding constraint. All $240\,\text{hours}$ are exhausted.

  • Painting and Varnishing Constraint ($2T + 1C \le 100$):

  • Actual hours consumed (LHS): $2(30) + 1(40) = 60 + 40 = 100\,\text{hours}$

  • Resource limit available (RHS): $100\,\text{hours}$     $\text{Slack} = \text{RHS} - \text{LHS} = 100 - 100 = 0\,\text{hours}$

  • Status: Binding constraint. All $100\,\text{hours}$ are exhausted.

  • Operational Takeaway: Because both constraints are binding, both departments represent operational bottlenecks. To increase total weekly profit above \\$4{,}100, Flair Furniture must acquire additional capacity in both carpentry and painting/varnishing.