ExamFinch.com My Study

Study guide

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis

Practice this exam

PE Industrial and Systems Exam

Track your progress as you read

Finished sections get a check mark.

1 Exam Overview, Strategy & Systems Foundations

1.1 PE Industrial Exam Format, Official Specification & Reference Handbook Strategy 1.2 System Analysis Tools, Process Definition, Requirements Engineering & QFD 1.3 Performance Measures: Output, Productivity, OEE, Cost & Environmental Sustainability 1.4 Process Types (Discrete, Continuous, Manufacturing, Service) & Value Analysis/Engineering

2 Optimization, Queueing, Simulation, Networks & Markov Chains

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis 2.2 Queueing Theory Models (M/M/1, M/M/s) & Little's Law Applications 2.3 Discrete-Event Simulation, Random Variates & Model Validation 2.4 Graph Theory & Network Models: Shortest Path, Minimal Spanning Tree & Maximum Flow 2.5 Markov Chains: Transition Matrices, Steady-State Probabilities & Absorbing States 2.6 Decision Trees, Expected Value & Bottleneck Analysis (Theory of Constraints)

3 Project Management & Planning

3.1 Project Scheduling with CPM and PERT: Critical Path, Float, Probability & Crashing 3.2 Project Planning & Control: Scope and WBS, Gantt Charts, Critical Chain (CCPM), Risk & Earned Value

4 Facility Layout, Space, Capacity & Material Handling

4.1 Systematic Layout Planning (SLP) & Activity Relationship (REL) Analysis 4.2 Workstation Design, Aisle Sizing & Space Requirements Planning 4.3 Capacity Analysis: Machine Requirements, Scrap Allowances & Personnel Requirements 4.4 Material Handling Equipment Selection, Unit Loads & Handling Principles

5 Site Location, Warehousing & Facility Economics

5.1 Facility Location Models: Center of Gravity & Minisum / Minimax Distance 5.2 Warehousing Systems, Storage Assignment & Order Picking Operations 5.3 Facility Life-Cycle Economics, Replacement Analysis & Rearrangement Costs

6 Demand Forecasting, Production Planning, MRP & JIT

6.1 Demand Forecasting Methods: Moving Averages, Exponential Smoothing & Error Metrics 6.2 Aggregate Planning Strategies & Master Production Scheduling (MPS) 6.3 Material Requirements Planning (MRP), Bill of Materials & Capacity Planning 6.4 Just-in-Time & Lean Production Planning: Pull Systems, Kanban Sizing, Heijunka & SMED

7 Inventory Systems, Scheduling, Logistics & Transportation Modes

7.1 Deterministic Inventory Control: Classical EOQ, EPQ & Quantity Discounts 7.2 Stochastic Inventory Management: Safety Stock, Continuous / Periodic Review & Newsvendor 7.3 Production Sequencing, Dispatching Rules & Johnson's Algorithm 7.4 Supply Chain Logistics, Transportation Simplex & Distribution Network Design 7.5 Transportation Modes, Freight Economics & the Transshipment Model

8 Engineering Economics, Break-Even Analysis & Costing Systems

8.1 Equivalence, Cash Flow Analysis & Discounted Cash Flow Metrics (PW, FW, EAC) 8.2 Rate of Return Analysis (IRR, Incremental IRR) & Benefit-Cost (B/C) Ratios 8.3 Asset Depreciation (MACRS, Straight-Line), Tax Effects & Replacement Decisions 8.4 Break-Even Analysis, Technical Capability Assessment & Costing Systems (Traditional, ABC & Standard Costs)

9 Methods Engineering, Work Measurement, Learning Curves, Line Balancing & Process Planning

9.1 Methods Analysis, Process Charting & Motion Study (Therbligs, 5S) 9.2 Worker–Machine (Man–Machine) Charts, Multiple Activity Analysis & Synchronous Servicing 9.3 Time Study Fundamentals, Performance Rating & Allowance Factors 9.4 Predetermined Motion Time Systems (PMTS, MTM, MOST) & Work Sampling 9.5 Learning Curves: Unit and Cumulative-Average Models, Learning Rates & Applications 9.6 Assembly Line Balancing, Precedence Constraints & Efficiency Heuristics 9.7 Manufacturing & Service Process Planning: Operation Selection, Sequencing, Route Sheets, Fixturing & Mistake Proofing

10 Ergonomics, Human Capacity, Occupational Safety & DART Rates

10.1 Anthropometry, Percentile Design, Workstation Ergonomics & Link Analysis 10.2 Industrial Biomechanics, the NIOSH Lifting Equation & Lifting Aids 10.3 Limits of Human Capacity & Risk-Factor Tools: Work Physiology, Strength, Range of Motion, Vision, RULA & Slip Resistance 10.4 Environmental Ergonomics (Noise, Heat, Illumination), Human-Machine Systems & OSHA Safety 10.5 Safety Codes, Standards & Voluntary Guidelines (OSHA, ANSI, NIOSH, MIL-STD) and DART Rate Calculations

11 Statistical Process Control & Process Capability

11.1 Statistical Process Control for Variables (X-bar/R and X-bar/s Charts) 11.2 Statistical Process Control for Attributes (p, np, c, and u Charts) 11.3 Process Capability Indices (Cp, Cpk, Cpm, Pp, Ppk) & Sigma Levels

12 Design of Experiments, Acceptance Sampling & Quality Systems

12.1 Design of Experiments: 2^k Factorials, ANOVA & Taguchi Robust Design 12.2 Acceptance Sampling: OC Curves, AQL, LTPD, AOQL, Z1.4/MIL-STD-105E & Dodge-Romig 12.3 Quality Systems (Deming, TQM, ISO 9000, Benchmarking), Root Cause Analysis & DMAIC

13 Reliability Engineering & Maintenance Systems

13.1 Reliability Modeling, Failure Rates (lambda) & Life Distributions (Exponential, Weibull) 13.2 System Reliability Architecture: Series, Parallel, k-out-of-n & Redundancy 13.3 Equipment Maintenance Engineering, Availability (A), MTBF/MTTR & RCM

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis

Key Takeaways Explain This Topic AI

A linear program consists of a linear objective function and linear constraints, with continuous decision variables restricted by non-negativity.

Under the Fundamental Theorem of Linear Programming, an optimal solution to a bounded, non-empty feasible region always occurs at an extreme point (corner point) of the convex polyhedron.

Slack variables convert less-than-or-equal constraints into equalities representing unused resource capacity, while surplus variables convert greater-than-or-equal constraints representing excess above minimum requirements.

The shadow price (dual price) quantifies the marginal improvement in the optimal objective value per unit increase in a constraint's right-hand side, holding strictly within its allowable range of feasibility.

The allowable range of optimality specifies the bounds within which an objective function coefficient can vary without altering the optimal decision variable values.

Last updated: October 2026

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis

Linear Programming (LP) is the cornerstone mathematical optimization technique utilized by industrial and systems engineers to allocate scarce operational resources—including labor hours, machine capacities, raw materials, capital, and transportation pathways—to maximize profit or minimize cost. Developed mathematically by George Dantzig in 1947 through the introduction of the Simplex algorithm, LP models system interactions using linear relationships.

Foundations of Mathematical Programming in Industrial Systems

A mathematical optimization model seeks to determine the optimal values of decision variables that optimize an objective function subject to a system of structural constraints.

Core Model Components

Decision Variables ( x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x 1 ​ , x 2 ​ , … , x n ​ ): Controllable, quantifiable continuous entities representing operational levels (e.g., units of product j j j produced per week, operating hours of facility i i i , or barrels of crude oil routed through pipeline k k k ).

Objective Function ( Z Z Z ): A single mathematical expression to be maximized (e.g., total contribution margin, revenue, system throughput) or minimized (e.g., total production cost, scrap generation, delivery transit time):

max ⁡ Z = ∑ j = 1 n c j x j or min ⁡ Z = ∑ j = 1 n c j x j \max Z = \sum_{j=1}^n c_j x_j \quad \text{or} \quad \min Z = \sum_{j=1}^n c_j x_j max Z = ∑ j = 1 n ​ c j ​ x j ​ or min Z = ∑ j = 1 n ​ c j ​ x j ​

where c j c_j c j ​ represents the objective function coefficient (unit profit or unit cost) associated with decision variable x j x_j x j ​ .

Structural Constraints: Mathematical inequalities or equalities defining technological limitations, physical capacities, contractual commitments, or legal regulations:

∑ j = 1 n a i j x j ≤ b i ( Capacity limitation, i ∈ I ≤ ) \sum_{j=1}^n a_{ij} x_j \le b_i \quad (\text{Capacity limitation, } i \in I_{\le}) ∑ j = 1 n ​ a ij ​ x j ​ ≤ b i ​ ( Capacity limitation, i ∈ I ≤ ​ ) ∑ j = 1 n a i j x j = b i ( Exact requirement, i ∈ I = ) \sum_{j=1}^n a_{ij} x_j = b_i \quad (\text{Exact requirement, } i \in I_{=}) ∑ j = 1 n ​ a ij ​ x j ​ = b i ​ ( Exact requirement, i ∈ I = ​ ) ∑ j = 1 n a i j x j ≥ b i ( Minimum specification, i ∈ I ≥ ) \sum_{j=1}^n a_{ij} x_j \ge b_i \quad (\text{Minimum specification, } i \in I_{\ge}) ∑ j = 1 n ​ a ij ​ x j ​ ≥ b i ​ ( Minimum specification, i ∈ I ≥ ​ )

where a i j a_{ij} a ij ​ represents the technological consumption coefficient (the quantity of resource i i i consumed per unit of activity j j j ), and b i b_i b i ​ represents the right-hand side (RHS) parameter indicating the total availability of resource i i i or the minimum requirement.

Non-Negativity Restrictions: Physical operational activities cannot take negative values:

  • x j ≥ 0 ∀ j = 1 , 2 , … , n x_j \ge 0 \quad \forall j = 1, 2, \dots, n x j ​ ≥ 0 ∀ j = 1 , 2 , … , n
  • Fundamental Assumptions of Linear Programming

For an optimization model to be formulated strictly as a linear program, four axiomatic assumptions must hold:

Proportionality: The contribution of each decision variable to both the objective function and the constraints is directly proportional to the value of the variable. There are no volume discounts, setup penalties, or diminishing marginal returns within the modeled domain.

Additivity: The total contribution of all variables to the objective function and constraints is the exact algebraic sum of their individual contributions. No interaction effects or synergetic couplings exist between variables.

Divisibility (Continuity): Decision variables are continuous and may assume any non-negative real value (fractional values are permitted). If decision variables must be integer-valued (e.g., whole airplanes or integer personnel counts), the model belongs to Integer Linear Programming (ILP).

Certainty: All parameters ( c j , a i j , b i c_j, a_{ij}, b_i c j ​ , a ij ​ , b i ​ ) are known constants with deterministic certainty throughout the operational planning horizon.

Graphical Solution Methodology for Two-Variable Problems

When a linear program involves exactly two decision variables ( x 1 , x 2 x_1, x_2 x 1 ​ , x 2 ​ ), the entire optimization space can be evaluated geometrically on a two-dimensional Cartesian plane. This provides visual intuition for high-dimensional simplex geometry.

Step-by-Step Graphical Procedure

Establish the Coordinate Axes: Set x 1 x_1 x 1 ​ on the horizontal axis and x 2 x_2 x 2 ​ on the vertical axis. The non-negativity constraints ( x 1 ≥ 0 , x 2 ≥ 0 x_1 \ge 0, x_2 \ge 0 x 1 ​ ≥ 0 , x 2 ​ ≥ 0 ) immediately restrict all feasible solutions to the first quadrant.

Plot Constraint Boundary Lines: Convert each inequality ∑ a i j x j ≤ b i \sum a_{ij} x_j \le b_i ∑ a ij ​ x j ​ ≤ b i ​ into an equality a i 1 x 1 + a i 2 x 2 = b i a_{i1} x_1 + a_{i2} x_2 = b_i a i 1 ​ x 1 ​ + a i 2 ​ x 2 ​ = b i ​ . Determine the intercepts:

Set x 1 = 0 ⟹ x 2 = b i a i 2 x_1 = 0 \implies x_2 = \frac{b_i}{a_{i2}} x 1 ​ = 0 ⟹ x 2 ​ = a i 2 ​ b i ​ ​

Set x 2 = 0 ⟹ x 1 = b i a i 1 x_2 = 0 \implies x_1 = \frac{b_i}{a_{i1}} x 2 ​ = 0 ⟹ x 1 ​ = a i 1 ​ b i ​ ​ Connect these two points to establish the boundary line.

Determine the Half-Space: Identify which side of the boundary line satisfies the original inequality by testing the origin ( 0 , 0 ) (0, 0) ( 0 , 0 ) . If 0 ≤ b i 0 \le b_i 0 ≤ b i ​ is true, the region containing ( 0 , 0 ) (0, 0) ( 0 , 0 ) is feasible; otherwise, shade the opposite half-space.

Delineate the Feasible Region ( F \mathcal{F} F ): The intersection of all half-spaces forms the feasible region. In linear programming, the feasible region is always a convex polyhedron (or polygon in 2D), meaning that a straight line segment connecting any two points within F \mathcal{F} F lies entirely within F \mathcal{F} F .

Evaluate Extreme Points (Corner Points): By the Fundamental Theorem of Linear Programming , if an optimal solution exists, it occurs at an extreme point (vertex) of the feasible region.

Objective Function Contours (Isoprofit / Isocost Lines): Set Z Z Z to an arbitrary constant Z 0 Z_0 Z 0 ​ to generate the contour line c 1 x 1 + c 2 x 2 = Z 0 c_1 x_1 + c_2 x_2 = Z_0 c 1 ​ x 1 ​ + c 2 ​ x 2 ​ = Z 0 ​ , with slope m = − c 1 c 2 m = -\frac{c_1}{c_2} m = − c 2 ​ c 1 ​ ​ . The gradient vector ∇ Z = [ c 1 , c 2 ] T \nabla Z = [c_1, c_2]^T ∇ Z = [ c 1 ​ , c 2 ​ ] T indicates the direction of steepest increase. Translating the contour line parallel to itself in the direction of ∇ Z \nabla Z ∇ Z until it last touches an extreme point identifies the optimal solution ( x 1 ∗ , x 2 ∗ ) (x_1^*, x_2^*) ( x 1 ∗ ​ , x 2 ∗ ​ ) .

Binding vs. Non-Binding Constraints and Slack/Surplus

Binding Constraint: A constraint that is satisfied as a strict equality at the optimal solution point ( a i 1 x 1 ∗ + a i 2 x 2 ∗ = b i a_{i1}x_1^* + a_{i2}x_2^* = b_i a i 1 ​ x 1 ∗ ​ + a i 2 ​ x 2 ∗ ​ = b i ​ ). The optimal point lies directly on the boundary line. Modifying the RHS b i b_i b i ​ will change the optimal objective value Z ∗ Z^* Z ∗ .

Non-Binding Constraint: A constraint satisfied as a strict inequality at the optimal point ( a i 1 x 1 ∗ + a i 2 x 2 ∗ < b i a_{i1}x_1^* + a_{i2}x_2^* < b_i a i 1 ​ x 1 ∗ ​ + a i 2 ​ x 2 ∗ ​ < b i ​ for a ≤ \le ≤ constraint). The boundary line does not pass through the optimal vertex.

Slack Variable ( s i s_i s i ​ ): Introduced into a ≤ \le ≤ constraint to quantify unused capacity:

s i = b i − ∑ j = 1 n a i j x j ≥ 0 s_i = b_i - \sum_{j=1}^n a_{ij} x_j \ge 0 s i ​ = b i ​ − ∑ j = 1 n ​ a ij ​ x j ​ ≥ 0

For a binding constraint, s i = 0 s_i = 0 s i ​ = 0 . For a non-binding constraint, s i > 0 s_i > 0 s i ​ > 0 .

Surplus Variable ( e i e_i e i ​ ): Subtracted from a ≥ \ge ≥ constraint to represent excess over minimum requirements:

e i = ∑ j = 1 n a i j x j − b i ≥ 0 e_i = \sum_{j=1}^n a_{ij} x_j - b_i \ge 0 e i ​ = ∑ j = 1 n ​ a ij ​ x j ​ − b i ​ ≥ 0

Simplex Algorithm Mechanics & Algebraic Geometry

While graphical analysis is limited to two variables, real industrial problems contain thousands of variables and constraints. The Simplex method solves these problems by moving systematically from one extreme point (basic feasible solution) to an adjacent extreme point with an improved objective value.

Conversion to Standard Form

To apply the Simplex method, the LP must be cast in standard algebraic form:

Maximize the objective function (a minimization problem min ⁡ Z \min Z min Z is converted to max ⁡ ( − Z ) \max (-Z) max ( − Z ) ).

All structural constraints are expressed as strict equalities.

All right-hand side constants are non-negative ( b i ≥ 0 b_i \ge 0 b i ​ ≥ 0 ).

All decision, slack, and surplus variables are non-negative.

For a system with m m m constraints and n n n total variables (after adding slacks and subtracting surpluses), where n > m n > m n > m :

Basic Variables ( m m m variables): Selected variables solved in terms of the non-basic variables. These variables form the basis.

Non-Basic Variables ( n − m n - m n − m variables): Set identically to zero ( x j = 0 x_j = 0 x j ​ = 0 ).

Basic Feasible Solution (BFS): A basic solution where all basic variables satisfy x B , i ≥ 0 x_{B,i} \ge 0 x B , i ​ ≥ 0 . Geometrically, each BFS corresponds exactly to an extreme point of the feasible region.

Simplex Pivot Mechanics

Optimality Check: In a maximization problem, evaluate the reduced costs ( z j − c j z_j - c_j z j ​ − c j ​ ) in the objective row. If all z j − c j ≥ 0 z_j - c_j \ge 0 z j ​ − c j ​ ≥ 0 , the current BFS is globally optimal.

Entering Variable Selection (Pivot Column): Choose the non-basic variable with the most negative reduced cost ( z k − c k < 0 z_k - c_k < 0 z k ​ − c k ​ < 0 ). This variable offers the highest rate of objective improvement per unit increase.

Leaving Variable Selection (Pivot Row / Minimum Ratio Test): To maintain feasibility, the entering variable x k x_k x k ​ can only increase until the first basic variable drops to zero. Compute the ratio of current RHS values to positive technological coefficients in the pivot column:

θ = min ⁡ i : a i k > 0 { b i a i k } \theta = \min_{i : a_{ik} > 0} \left\{ \frac{b_i}{a_{ik}} \right\} θ = min i : a ik ​ > 0 ​ { a ik ​ b i ​ ​ }

The basic variable corresponding to the minimum ratio leaves the basis.

4. Gauss-Jordan Elimination: Perform elementary row operations to transform the pivot element to 1 and all other elements in the pivot column to 0, yielding a new adjacent BFS.

Special Solution Outcomes in Linear Programming

Outcome Graphical Manifestation Simplex Tableau Indicator

Unique Optimal Solution Objective line touches exactly one vertex of F \mathcal{F} F All non-basic reduced costs z j − c j > 0 z_j - c_j > 0 z j ​ − c j ​ > 0

Alternate (Multiple) Optima Objective line is parallel to a binding constraint edge Reduced cost of a non-basic variable is zero ( z k − c k = 0 z_k - c_k = 0 z k ​ − c k ​ = 0 ) at optimality

Unbounded Solution Feasible region is open in direction of optimization Entering variable has no positive pivot coefficients ( a i k ≤ 0 a_{ik} \le 0 a ik ​ ≤ 0 for all i i i )

Infeasible Problem Constraints are mutually contradictory; F = ∅ \mathcal{F} = \emptyset F = ∅ Artificial variables remain positive ( > 0 > 0 > 0 ) in the final optimal tableau

Degeneracy More than n n n constraint boundaries intersect at a single vertex Tie in the minimum ratio test; a basic variable equals zero ( x B , i = 0 x_{B,i} = 0 x B , i ​ = 0 )

Duality Theory & Economic Interpretation

Every linear programming problem, termed the Primal , possesses a corresponding symmetric companion problem termed the Dual . The dual problem provides economic valuation of the primal system's resources.

Primal-Dual Relationships

Consider the symmetric primal-dual formulation:

Primal Problem: max ⁡ Z = c T x subject to A x ≤ b , x ≥ 0 \max Z = \mathbf{c}^T \mathbf{x} \quad \text{subject to} \quad \mathbf{A}\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0} max Z = c T x subject to Ax ≤ b , x ≥ 0

Dual Problem: min ⁡ W = b T y subject to A T y ≥ c , y ≥ 0 \min W = \mathbf{b}^T \mathbf{y} \quad \text{subject to} \quad \mathbf{A}^T\mathbf{y} \ge \mathbf{c}, \quad \mathbf{y} \ge \mathbf{0} min W = b T y subject to A T y ≥ c , y ≥ 0

Where:

y i y_i y i ​ represents the dual decision variable associated with primal constraint i i i .

Each primal constraint corresponds to a dual variable.

Each primal variable corresponds to a dual constraint.

The primal objective coefficients c \mathbf{c} c become the dual RHS vector.

The primal RHS vector b \mathbf{b} b becomes the dual objective coefficients.

The technological matrix A \mathbf{A} A is transposed to A T \mathbf{A}^T A T .

Core Duality Theorems

Weak Duality Theorem: For any primal feasible solution x \mathbf{x} x and any dual feasible solution y \mathbf{y} y :

c T x ≤ b T y \mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y} c T x ≤ b T y

The objective value of any dual feasible solution provides an upper bound on the objective value of any primal feasible solution.

Strong Duality Theorem: If the primal problem has an optimal solution x ∗ \mathbf{x}^* x ∗ , then the dual problem also has an optimal solution y ∗ \mathbf{y}^* y ∗ , and their optimal objective values are identical:

Z ∗ = c T x ∗ = b T y ∗ = W ∗ Z^* = \mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^* = W^* Z ∗ = c T x ∗ = b T y ∗ = W ∗

Complementary Slackness Theorem: Let x ∗ \mathbf{x}^* x ∗ be primal feasible and y ∗ \mathbf{y}^* y ∗ be dual feasible. They are mutually optimal if and only if:

y i ∗ ⋅ ( b i − ∑ j = 1 n a i j x j ∗ ) = 0 ∀ i = 1 , … , m y_i^* \cdot \left( b_i - \sum_{j=1}^n a_{ij} x_j^* \right) = 0 \quad \forall i = 1, \dots, m y i ∗ ​ ⋅ ( b i ​ − ∑ j = 1 n ​ a ij ​ x j ∗ ​ ) = 0 ∀ i = 1 , … , m x j ∗ ⋅ ( ∑ i = 1 m a i j y i ∗ − c j ) = 0 ∀ j = 1 , … , n x_j^* \cdot \left( \sum_{i=1}^m a_{ij} y_i^* - c_j \right) = 0 \quad \forall j = 1, \dots, n x j ∗ ​ ⋅ ( ∑ i = 1 m ​ a ij ​ y i ∗ ​ − c j ​ ) = 0 ∀ j = 1 , … , n

Managerial Consequence: If primal constraint i i i has positive slack ( s i ∗ > 0 s_i^* > 0 s i ∗ ​ > 0 ), its dual valuation is zero ( y i ∗ = 0 y_i^* = 0 y i ∗ ​ = 0 ). Conversely, if a resource has a positive shadow price ( y i ∗ > 0 y_i^* > 0 y i ∗ ​ > 0 ), its corresponding constraint must be strictly binding ( s i ∗ = 0 s_i^* = 0 s i ∗ ​ = 0 ).

Post-Optimality & Sensitivity Analysis

Sensitivity analysis examines how perturbations in input parameters ( c j , b i , a i j c_j, b_i, a_{ij} c j ​ , b i ​ , a ij ​ ) affect the optimal solution without resolving the linear program from scratch.

1. Shadow Price (Dual Value y i ∗ y_i^* y i ∗ ​ )

The shadow price of constraint i i i is the marginal rate of change in the optimal objective value Z ∗ Z^* Z ∗ resulting from a one-unit increase in the right-hand side b i b_i b i ​ :

y i ∗ = ∂ Z ∗ ∂ b i y_i^* = \frac{\partial Z^*}{\partial b_i} y i ∗ ​ = ∂ b i ​ ∂ Z ∗ ​

In a maximization problem, a ≤ \le ≤ resource constraint has y i ∗ ≥ 0 y_i^* \ge 0 y i ∗ ​ ≥ 0 , indicating the maximum price an enterprise should be willing to pay for one additional unit of resource i i i beyond its standard cost.

For a non-binding constraint, surplus capacity exists; hence, y i ∗ = 0 y_i^* = 0 y i ∗ ​ = 0 .

2. Allowable Range of Feasibility (for RHS b i b_i b i ​ )

The range of values for b i b_i b i ​ over which the current optimal basis (set of basic variables) remains unchanged. Within this range:

The shadow price y i ∗ y_i^* y i ∗ ​ remains constant.

The coordinates of the optimal extreme point change linearly as functions of Δ b i \Delta b_i Δ b i ​ .

The optimal objective value changes at the constant rate: Δ Z ∗ = y i ∗ ⋅ Δ b i \Delta Z^* = y_i^* \cdot \Delta b_i Δ Z ∗ = y i ∗ ​ ⋅ Δ b i ​ .

If b i b_i b i ​ is changed beyond the allowable range, the shadow price changes because a different set of constraints becomes binding.

3. Allowable Range of Optimality (for Objective Coefficients c j c_j c j ​ )

The range of values for an objective function coefficient c j c_j c j ​ over which the current optimal extreme point coordinates ( x 1 ∗ , x 2 ∗ , … , x n ∗ ) (x_1^*, x_2^*, \dots, x_n^*) ( x 1 ∗ ​ , x 2 ∗ ​ , … , x n ∗ ​ ) remain strictly identical.

Within this range, the decision variables do not change, but the total objective value changes at rate x j ∗ x_j^* x j ∗ ​ : Δ Z ∗ = x j ∗ ⋅ Δ c j \Delta Z^* = x_j^* \cdot \Delta c_j Δ Z ∗ = x j ∗ ​ ⋅ Δ c j ​ .

In two dimensions, this corresponds to rotating the isoprofit line between the slopes of the two binding constraint lines intersecting at the optimal vertex.

4. Reduced Cost ( r j r_j r j ​ )

The reduced cost of a decision variable x j x_j x j ​ indicates the amount by which its objective function coefficient c j c_j c j ​ must improve before it becomes economical to produce a positive quantity ( x j > 0 x_j > 0 x j ​ > 0 ):

If x j ∗ > 0 x_j^* > 0 x j ∗ ​ > 0 in the optimal solution, its reduced cost is strictly zero ( r j = 0 r_j = 0 r j ​ = 0 ).

If x j ∗ = 0 x_j^* = 0 x j ∗ ​ = 0 (non-basic), r j r_j r j ​ represents the marginal penalty incurred per unit of x j x_j x j ​ introduced into the basis: r j = ∑ i = 1 m a i j y i ∗ − c j r_j = \sum_{i=1}^m a_{ij} y_i^* - c_j r j ​ = ∑ i = 1 m ​ a ij ​ y i ∗ ​ − c j ​ (for maximization).

  • Step-by-Step Worked Numerical Example
  • Problem Formulation: Precision Machining Facility

A precision manufacturing plant produces two advanced aerospace components: Component 1 ( x 1 x_1 x 1 ​ ) and Component 2 ( x 2 x_2 x 2 ​ ) . Each unit generates unit contribution margins of:

  • Component 1: $50/unit
  • Component 2: $40/unit

Production requires processing across three dedicated departmental workcenters with finite available weekly hours:

  • Milling Workcenter: 2 x 1 + 1 x 2 ≤ 100 2x_1 + 1x_2 \le 100 2 x 1 ​ + 1 x 2 ​ ≤ 100 hours available
  • Assembly Workcenter: 1 x 1 + 1 x 2 ≤ 80 1x_1 + 1x_2 \le 80 1 x 1 ​ + 1 x 2 ​ ≤ 80 hours available
  • Finishing Workcenter: 1 x 1 + 3 x 2 ≤ 180 1x_1 + 3x_2 \le 180 1 x 1 ​ + 3 x 2 ​ ≤ 180 hours available

Non-negativity requires x 1 ≥ 0 , x 2 ≥ 0 x_1 \ge 0, x_2 \ge 0 x 1 ​ ≥ 0 , x 2 ​ ≥ 0 .

max ⁡ Z = 50 x 1 + 40 x 2 \max Z = 50x_1 + 40x_2 max Z = 50 x 1 ​ + 40 x 2 ​ s.t. 2 x 1 + x 2 ≤ 100 ( Milling ) \text{s.t.} \quad 2x_1 + x_2 \le 100 \quad (\text{Milling}) s.t. 2 x 1 ​ + x 2 ​ ≤ 100 ( Milling ) x 1 + x 2 ≤ 80 ( Assembly ) x_1 + x_2 \le 80 \quad (\text{Assembly}) x 1 ​ + x 2 ​ ≤ 80 ( Assembly ) x 1 + 3 x 2 ≤ 180 ( Finishing ) x_1 + 3x_2 \le 180 \quad (\text{Finishing}) x 1 ​ + 3 x 2 ​ ≤ 180 ( Finishing ) x 1 , x 2 ≥ 0 x_1, x_2 \ge 0 x 1 ​ , x 2 ​ ≥ 0

Step 1: Constraint Boundary Analysis & Extreme Points

Plotting the boundary equations:

Milling Boundary: 2 x 1 + x 2 = 100 ⟹ ( 0 , 100 ) 2x_1 + x_2 = 100 \implies (0, 100) 2 x 1 ​ + x 2 ​ = 100 ⟹ ( 0 , 100 ) and ( 50 , 0 ) (50, 0) ( 50 , 0 ) .

Assembly Boundary: x 1 + x 2 = 80 ⟹ ( 0 , 80 ) x_1 + x_2 = 80 \implies (0, 80) x 1 ​ + x 2 ​ = 80 ⟹ ( 0 , 80 ) and ( 80 , 0 ) (80, 0) ( 80 , 0 ) .

Finishing Boundary: x 1 + 3 x 2 = 180 ⟹ ( 0 , 60 ) x_1 + 3x_2 = 180 \implies (0, 60) x 1 ​ + 3 x 2 ​ = 180 ⟹ ( 0 , 60 ) and ( 180 , 0 ) (180, 0) ( 180 , 0 ) .

Evaluate all candidate intersections in the positive quadrant:

Origin ( 0 , 0 ) (0, 0) ( 0 , 0 ) : Feasible. Z = 50 ( 0 ) + 40 ( 0 ) = $ 0 Z = 50(0) + 40(0) = \text{\textdollar}0 Z = 50 ( 0 ) + 40 ( 0 ) = $ 0 .

x 1 x_1 x 1 ​ -intercept: The tightest constraint along the x 1 x_1 x 1 ​ -axis is Milling at ( 50 , 0 ) (50, 0) ( 50 , 0 ) . Check other constraints:

  • Assembly: 50 + 0 = 50 ≤ 80 50 + 0 = 50 \le 80 50 + 0 = 50 ≤ 80 (Feasible)
  • Finishing: 50 + 3 ( 0 ) = 50 ≤ 180 50 + 3(0) = 50 \le 180 50 + 3 ( 0 ) = 50 ≤ 180 (Feasible)

Z = 50 ( 50 ) + 40 ( 0 ) = $ 2,500 Z = 50(50) + 40(0) = \text{\textdollar}2{,}500 Z = 50 ( 50 ) + 40 ( 0 ) = $ 2 , 500 .

Intersection of Milling and Finishing: 2 x 1 + x 2 = 100 ⟹ x 2 = 100 − 2 x 1 2x_1 + x_2 = 100 \implies x_2 = 100 - 2x_1 2 x 1 ​ + x 2 ​ = 100 ⟹ x 2 ​ = 100 − 2 x 1 ​ Substitute into Finishing: x 1 + 3 ( 100 − 2 x 1 ) = 180 ⟹ x 1 + 300 − 6 x 1 = 180 ⟹ − 5 x 1 = − 120 ⟹ x 1 = 24 x_1 + 3(100 - 2x_1) = 180 \implies x_1 + 300 - 6x_1 = 180 \implies -5x_1 = -120 \implies x_1 = 24 x 1 ​ + 3 ( 100 − 2 x 1 ​ ) = 180 ⟹ x 1 ​ + 300 − 6 x 1 ​ = 180 ⟹ − 5 x 1 ​ = − 120 ⟹ x 1 ​ = 24 x 2 = 100 − 2 ( 24 ) = 52 x_2 = 100 - 2(24) = 52 x 2 ​ = 100 − 2 ( 24 ) = 52 Verify against Assembly constraint: x 1 + x 2 = 24 + 52 = 76 ≤ 80 ( Feasible! Slack s 2 = 80 − 76 = 4 hours ) x_1 + x_2 = 24 + 52 = 76 \le 80 \quad (\text{Feasible! Slack } s_2 = 80 - 76 = 4 \text{ hours}) x 1 ​ + x 2 ​ = 24 + 52 = 76 ≤ 80 ( Feasible! Slack s 2 ​ = 80 − 76 = 4 hours ) Calculate objective value: Z = 50 ( 24 ) + 40 ( 52 ) = 1 , 200 + 2 , 080 = $ 3,280 Z = 50(24) + 40(52) = 1,200 + 2,080 = \text{\textdollar}3{,}280 Z = 50 ( 24 ) + 40 ( 52 ) = 1 , 200 + 2 , 080 = $ 3 , 280

Intersection of Assembly and Finishing: x 1 + x 2 = 80 ⟹ x 1 = 80 − x 2 x_1 + x_2 = 80 \implies x_1 = 80 - x_2 x 1 ​ + x 2 ​ = 80 ⟹ x 1 ​ = 80 − x 2 ​ Substitute into Finishing: ( 80 − x 2 ) + 3 x 2 = 180 ⟹ 2 x 2 = 100 ⟹ x 2 = 50 , x 1 = 30 (80 - x_2) + 3x_2 = 180 \implies 2x_2 = 100 \implies x_2 = 50, x_1 = 30 ( 80 − x 2 ​ ) + 3 x 2 ​ = 180 ⟹ 2 x 2 ​ = 100 ⟹ x 2 ​ = 50 , x 1 ​ = 30 .

Check Milling constraint: 2 ( 30 ) + 50 = 110 > 100 2(30) + 50 = 110 > 100 2 ( 30 ) + 50 = 110 > 100 ( Infeasible! Violates Milling capacity ).

Intersection of Milling and Assembly: 2 x 1 + x 2 = 100 2x_1 + x_2 = 100 2 x 1 ​ + x 2 ​ = 100 and x 1 + x 2 = 80 x_1 + x_2 = 80 x 1 ​ + x 2 ​ = 80 . Subtracting gives x 1 = 20 , x 2 = 60 x_1 = 20, x_2 = 60 x 1 ​ = 20 , x 2 ​ = 60 .

Check Finishing: 20 + 3 ( 60 ) = 200 > 180 20 + 3(60) = 200 > 180 20 + 3 ( 60 ) = 200 > 180 ( Infeasible! Violates Finishing capacity ).

x 2 x_2 x 2 ​ -intercept: The tightest constraint along the x 2 x_2 x 2 ​ -axis is Finishing at ( 0 , 60 ) (0, 60) ( 0 , 60 ) . Check others:

  • Milling: 2 ( 0 ) + 60 = 60 ≤ 100 2(0) + 60 = 60 \le 100 2 ( 0 ) + 60 = 60 ≤ 100 (Feasible)
  • Assembly: 0 + 60 = 60 ≤ 80 0 + 60 = 60 \le 80 0 + 60 = 60 ≤ 80 (Feasible)

Z = 50 ( 0 ) + 40 ( 60 ) = $ 2,400 Z = 50(0) + 40(60) = \text{\textdollar}2{,}400 Z = 50 ( 0 ) + 40 ( 60 ) = $ 2 , 400 .

Summary of Extreme Points

Vertex ( x 1 , x 2 ) (x_1, x_2) ( x 1 ​ , x 2 ​ ) Milling ( 2 x 1 + x 2 ≤ 100 2x_1+x_2 \le 100 2 x 1 ​ + x 2 ​ ≤ 100 ) Assembly ( x 1 + x 2 ≤ 80 x_1+x_2 \le 80 x 1 ​ + x 2 ​ ≤ 80 ) Finishing ( x 1 + 3 x 2 ≤ 180 x_1+3x_2 \le 180 x 1 ​ + 3 x 2 ​ ≤ 180 ) Status Objective Z = 50 x 1 + 40 x 2 Z = 50x_1 + 40x_2 Z = 50 x 1 ​ + 40 x 2 ​

( 0 , 0 ) (0, 0) ( 0 , 0 ) 0 ≤ 100 0 \le 100 0 ≤ 100 0 ≤ 80 0 \le 80 0 ≤ 80 0 ≤ 180 0 \le 180 0 ≤ 180 Feasible $0

( 50 , 0 ) (50, 0) ( 50 , 0 ) 100 = 100 100 = 100 100 = 100 (Binding) 50 ≤ 80 50 \le 80 50 ≤ 80 50 ≤ 180 50 \le 180 50 ≤ 180 Feasible $2,500

( 24 , 52 ) (24, 52) ( 24 , 52 ) 100 = 100 100 = 100 100 = 100 (Binding) 76 ≤ 80 76 \le 80 76 ≤ 80 (Slack = 4) 180 = 180 180 = 180 180 = 180 (Binding) Optimal $3,280

( 0 , 60 ) (0, 60) ( 0 , 60 ) 60 ≤ 100 60 \le 100 60 ≤ 100 60 ≤ 80 60 \le 80 60 ≤ 80 180 = 180 180 = 180 180 = 180 (Binding) Feasible $2,400

The optimal production plan is x 1 ∗ = 24 x_1^* = 24 x 1 ∗ ​ = 24 units of Component 1 and x 2 ∗ = 52 x_2^* = 52 x 2 ∗ ​ = 52 units of Component 2, yielding a maximum contribution margin of $3,280 .

  • Step 2: Exact Sensitivity Report Derivations
  • A. Shadow Prices ( y 1 ∗ , y 2 ∗ , y 3 ∗ y_1^*, y_2^*, y_3^* y 1 ∗ ​ , y 2 ∗ ​ , y 3 ∗ ​ )

Since Assembly is non-binding ( s 2 = 4 s_2 = 4 s 2 ​ = 4 hours), by Complementary Slackness: y 2 ∗ = $ 0.00 / hour y_2^* = \text{\textdollar}0.00/\text{hour} y 2 ∗ ​ = $ 0.00/ hour

To find the shadow prices of the binding constraints (Milling b 1 b_1 b 1 ​ and Finishing b 3 b_3 b 3 ​ ), perturb b 1 b_1 b 1 ​ by Δ b 1 \Delta b_1 Δ b 1 ​ : 2 x 1 + x 2 = 100 + Δ b 1 2x_1 + x_2 = 100 + \Delta b_1 2 x 1 ​ + x 2 ​ = 100 + Δ b 1 ​ x 1 + 3 x 2 = 180 x_1 + 3x_2 = 180 x 1 ​ + 3 x 2 ​ = 180 From the second equation, x 1 = 180 − 3 x 2 x_1 = 180 - 3x_2 x 1 ​ = 180 − 3 x 2 ​ . Substitute into the first: 2 ( 180 − 3 x 2 ) + x 2 = 100 + Δ b 1 ⟹ 360 − 5 x 2 = 100 + Δ b 1 ⟹ x 2 = 52 − 0.2 Δ b 1 2(180 - 3x_2) + x_2 = 100 + \Delta b_1 \implies 360 - 5x_2 = 100 + \Delta b_1 \implies x_2 = 52 - 0.2\Delta b_1 2 ( 180 − 3 x 2 ​ ) + x 2 ​ = 100 + Δ b 1 ​ ⟹ 360 − 5 x 2 ​ = 100 + Δ b 1 ​ ⟹ x 2 ​ = 52 − 0.2Δ b 1 ​ x 1 = 180 − 3 ( 52 − 0.2 Δ b 1 ) = 24 + 0.6 Δ b 1 x_1 = 180 - 3(52 - 0.2\Delta b_1) = 24 + 0.6\Delta b_1 x 1 ​ = 180 − 3 ( 52 − 0.2Δ b 1 ​ ) = 24 + 0.6Δ b 1 ​

Calculate the rate of change in Z Z Z : Z = 50 ( 24 + 0.6 Δ b 1 ) + 40 ( 52 − 0.2 Δ b 1 ) = 3 , 280 + 30 Δ b 1 − 8 Δ b 1 = 3 , 280 + 22 Δ b 1 Z = 50(24 + 0.6\Delta b_1) + 40(52 - 0.2\Delta b_1) = 3,280 + 30\Delta b_1 - 8\Delta b_1 = 3,280 + 22\Delta b_1 Z = 50 ( 24 + 0.6Δ b 1 ​ ) + 40 ( 52 − 0.2Δ b 1 ​ ) = 3 , 280 + 30Δ b 1 ​ − 8Δ b 1 ​ = 3 , 280 + 22Δ b 1 ​ ⟹ y 1 ∗ = ∂ Z ∗ ∂ b 1 = $ 22.00 / hour \implies y_1^* = \frac{\partial Z^*}{\partial b_1} = \text{\textdollar}22.00/\text{hour} ⟹ y 1 ∗ ​ = ∂ b 1 ​ ∂ Z ∗ ​ = $ 22.00/ hour

Similarly, perturbing Finishing capacity b 3 b_3 b 3 ​ by Δ b 3 \Delta b_3 Δ b 3 ​ : 2 x 1 + x 2 = 100 2x_1 + x_2 = 100 2 x 1 ​ + x 2 ​ = 100 x 1 + 3 x 2 = 180 + Δ b 3 x_1 + 3x_2 = 180 + \Delta b_3 x 1 ​ + 3 x 2 ​ = 180 + Δ b 3 ​ Solving yields x 1 = 24 − 0.2 Δ b 3 x_1 = 24 - 0.2\Delta b_3 x 1 ​ = 24 − 0.2Δ b 3 ​ and x 2 = 52 + 0.4 Δ b 3 x_2 = 52 + 0.4\Delta b_3 x 2 ​ = 52 + 0.4Δ b 3 ​ . Z = 50 ( 24 − 0.2 Δ b 3 ) + 40 ( 52 + 0.4 Δ b 3 ) = 3 , 280 − 10 Δ b 3 + 16 Δ b 3 = 3 , 280 + 6 Δ b 3 Z = 50(24 - 0.2\Delta b_3) + 40(52 + 0.4\Delta b_3) = 3,280 - 10\Delta b_3 + 16\Delta b_3 = 3,280 + 6\Delta b_3 Z = 50 ( 24 − 0.2Δ b 3 ​ ) + 40 ( 52 + 0.4Δ b 3 ​ ) = 3 , 280 − 10Δ b 3 ​ + 16Δ b 3 ​ = 3 , 280 + 6Δ b 3 ​ ⟹ y 3 ∗ = ∂ Z ∗ ∂ b 3 = $ 6.00 / hour \implies y_3^* = \frac{\partial Z^*}{\partial b_3} = \text{\textdollar}6.00/\text{hour} ⟹ y 3 ∗ ​ = ∂ b 3 ​ ∂ Z ∗ ​ = $ 6.00/ hour

B. Allowable Range of Optimality for c 1 c_1 c 1 ​

The binding constraints at ( 24 , 52 ) (24, 52) ( 24 , 52 ) are:

Milling: 2 x 1 + x 2 = 100 ⟹ x 2 = 100 − 2 x 1 2x_1 + x_2 = 100 \implies x_2 = 100 - 2x_1 2 x 1 ​ + x 2 ​ = 100 ⟹ x 2 ​ = 100 − 2 x 1 ​ (Slope m 1 = − 2 m_1 = -2 m 1 ​ = − 2 )

Finishing: x 1 + 3 x 2 = 180 ⟹ x 2 = 60 − 1 3 x 1 x_1 + 3x_2 = 180 \implies x_2 = 60 - \frac{1}{3}x_1 x 1 ​ + 3 x 2 ​ = 180 ⟹ x 2 ​ = 60 − 3 1 ​ x 1 ​ (Slope m 3 = − 1 3 m_3 = -\frac{1}{3} m 3 ​ = − 3 1 ​ )

The slope of the objective function is m Z = − c 1 c 2 = − c 1 40 m_Z = -\frac{c_1}{c_2} = -\frac{c_1}{40} m Z ​ = − c 2 ​ c 1 ​ ​ = − 40 c 1 ​ ​ . For the extreme point ( 24 , 52 ) (24, 52) ( 24 , 52 ) to remain optimal, the slope of the objective contour must lie between the slopes of the two binding constraints: − 2 ≤ − c 1 40 ≤ − 1 3 -2 \le -\frac{c_1}{40} \le -\frac{1}{3} − 2 ≤ − 40 c 1 ​ ​ ≤ − 3 1 ​ Multiply across by − 40 -40 − 40 (reversing the inequality signs): 40 3 ≤ c 1 ≤ 80 ⟹ 13.33 ≤ c 1 ≤ 80.00 \frac{40}{3} \le c_1 \le 80 \implies 13.33 \le c_1 \le 80.00 3 40 ​ ≤ c 1 ​ ≤ 80 ⟹ 13.33 ≤ c 1 ​ ≤ 80.00

Allowable Increase for c 1 c_1 c 1 ​ : 80 − 50 = $ 30.00 80 - 50 = \text{\textdollar}30.00 80 − 50 = $ 30.00

Allowable Decrease for c 1 c_1 c 1 ​ : 50 − 13.33 = $ 36.67 50 - 13.33 = \text{\textdollar}36.67 50 − 13.33 = $ 36.67

C. Allowable Ranges for the Binding Right-Hand Sides

The shadow prices stay valid only while the same two constraints remain binding and every variable stays non-negative.

Milling ( b 1 = 100 + Δ b 1 b_1 = 100 + \Delta b_1 b 1 ​ = 100 + Δ b 1 ​ ): the solution is x 1 = 24 + 0.6 Δ b 1 x_1 = 24 + 0.6\Delta b_1 x 1 ​ = 24 + 0.6Δ b 1 ​ and x 2 = 52 − 0.2 Δ b 1 x_2 = 52 - 0.2\Delta b_1 x 2 ​ = 52 − 0.2Δ b 1 ​ , so Assembly uses 76 + 0.4 Δ b 1 ≤ 80 76 + 0.4\Delta b_1 \le 80 76 + 0.4Δ b 1 ​ ≤ 80 . Assembly becomes binding at Δ b 1 = + 10 \Delta b_1 = +10 Δ b 1 ​ = + 10 , and x 1 x_1 x 1 ​ reaches zero at Δ b 1 = − 40 \Delta b_1 = -40 Δ b 1 ​ = − 40 . Allowable increase = 10 = 10 = 10 hours; allowable decrease = 40 = 40 = 40 hours.

Finishing ( b 3 = 180 + Δ b 3 b_3 = 180 + \Delta b_3 b 3 ​ = 180 + Δ b 3 ​ ): the solution is x 1 = 24 − 0.2 Δ b 3 x_1 = 24 - 0.2\Delta b_3 x 1 ​ = 24 − 0.2Δ b 3 ​ and x 2 = 52 + 0.4 Δ b 3 x_2 = 52 + 0.4\Delta b_3 x 2 ​ = 52 + 0.4Δ b 3 ​ , so Assembly uses 76 + 0.2 Δ b 3 ≤ 80 76 + 0.2\Delta b_3 \le 80 76 + 0.2Δ b 3 ​ ≤ 80 . Assembly becomes binding at Δ b 3 = + 20 \Delta b_3 = +20 Δ b 3 ​ = + 20 , and x 2 x_2 x 2 ​ reaches zero at Δ b 3 = − 130 \Delta b_3 = -130 Δ b 3 ​ = − 130 . Allowable increase = 20 = 20 = 20 hours; allowable decrease = 130 = 130 = 130 hours.

Comprehensive Sensitivity Report

  • Variable Cells Final Value Reduced Cost Objective Coefficient Allowable Increase Allowable Decrease
  • Component 1 ( x 1 x_1 x 1 ​ ) 24 0 50.00 30.00 36.67
  • Component 2 ( x 2 x_2 x 2 ​ ) 52 0 40.00 110.00 15.00
  • Constraints Final Value Shadow Price Constraint RHS Allowable Increase Allowable Decrease
  • Milling Workcenter 100 22.00 100.00 10.00 40.00
  • Assembly Workcenter 76 0.00 80.00 10 30 ( ∞ ) 10^{30} (\infty) 1 0 30 ( ∞ ) 4.00
  • Finishing Workcenter 180 6.00 180.00 20.00 130.00