8.3 Duality, Sensitivity Analysis, and Integer Linear Programming

FE Industrial and Systems Study Guide Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Exam Overview, CBT Strategy & Handbook Navigation

1.1 FE Industrial Exam Structure, CBT Logistics, and Pacing 1.2 Using the NCEES FE Reference Handbook and Approved Calculators

2 Chapter 2: Mathematics for Industrial Engineers

2.1 Analytic Geometry, Coordinate Systems, and Trigonometry 2.2 Calculus: Differential, Integral, and Series Approximations 2.3 Linear Algebra: Matrix Operations, Systems of Equations, and Vectors

3 Chapter 3: Engineering Sciences Core

3.1 Thermodynamics Fundamentals and Fluid Flow Principles 3.2 Statics, Dynamics, and Mechanics of Materials Core 3.3 Electrical Circuits, DC/AC Analysis, and Power in Industrial Systems

4 Chapter 4: Ethics and Professional Practice

4.1 NCEES Model Rules of Professional Conduct and Technical Society Ethics 4.2 Engineering Licensure, Public Welfare, and Professional Liability 4.3 Engineering Contracts, Intellectual Property, and Conflicts of Interest

5 Chapter 5: Engineering Economics

5.1 Time Value of Money, Discount Factors, and Equivalence 5.2 Evaluating Alternatives: Present Worth, Equivalent Annual Cost, and IRR 5.3 Incremental Rate of Return, Replacement Analysis, and Break-Even 5.4 Depreciation Methods, MACRS, Income Taxes, and Inflation

6 Chapter 6: Probability Foundations & Distributions

6.1 Basic Probability Concepts, Conditional Probability, and Bayes' Theorem 6.2 Discrete Probability Distributions 6.3 Continuous Probability Distributions

7 Chapter 7: Statistical Inference, Regression & Design of Experiments

7.1 Sampling Distributions, Central Limit Theorem, and Confidence Intervals 7.2 Hypothesis Testing: Means, Proportions, and Variances 7.3 Linear Regression, Correlation Analysis, and Design of Experiments (ANOVA)

8 Chapter 8: Data, Logic, Modeling & Linear Programming

8.1 Optimization Modeling: Decision Variables, Objectives, and Constraints 8.2 Linear Programming: Graphical Solutions and Simplex Fundamentals 8.3 Duality, Sensitivity Analysis, and Integer Linear Programming 8.4 Data, Logic Development, and Analytics

9 Chapter 9: Stochastic Models & Simulation

9.1 Queuing Theory: Little's Law, M/M/1, and Multi-Server Systems 9.2 Discrete-Time Markov Chains: Transition Matrices and Steady-State Probabilities 9.3 Discrete-Event Simulation Principles and Monte Carlo Modeling

10 Chapter 10: Engineering Management, Project Planning & Performance Measurement

10.1 Organizational Structure, Leadership, and Worker Motivation Theories 10.2 Project Management: WBS, Critical Path Method (CPM), PERT, and Crashing 10.3 Earned Value Management (EVM), Decision Trees, and Risk Preference 10.4 Performance Measurement: Productivity, KPIs, Wage Systems, and the Balanced Scorecard

11 Chapter 11: Manufacturing & Production Systems

11.1 Manufacturing Processes, Material Processing, and Tolerancing 11.2 Assembly Line Balancing, Takt Time, Cycle Time, and Throughput 11.3 Sustainable Manufacturing, Waste Minimization, and Life-Cycle Assessment

12 Chapter 12: Production Planning, Inventory Control & Sequencing

12.1 Demand Forecasting Methods and Forecast Error Tracking 12.2 Aggregate Planning, Master Production Scheduling (MPS), and MRP 12.3 Deterministic Inventory Models: EOQ, EPQ, and Safety Stock 12.4 Job Sequencing, Dispatching Rules, and Flow Shop Scheduling

13 Chapter 13: Lean Systems & Theory of Constraints

13.1 Lean Foundations: Value Stream Mapping, Seven Wastes, and 5S 13.2 Pull Systems, Kanban, Just-In-Time (JIT), and SMED Setup Reduction 13.3 Theory of Constraints: Bottleneck Identification and Drum-Buffer-Rope

14 Chapter 14: Facilities Planning & Material Handling

14.1 Facility Location Analysis: Qualitative Factor Rating and Centroid Method 14.2 Facility Layout Design and Flow Analysis 14.3 Material Handling Equipment, Warehousing, and AS/RS

15 Chapter 15: Supply Chain Design & Logistics

15.1 Supply Chain Network Architecture and Transportation Modes 15.2 Distribution Strategies, Cross-Docking, and Vehicle Routing 15.3 The Bullwhip Effect, Risk Pooling, and Supply Chain Coordination

16 Chapter 16: Human Factors & Cognitive Ergonomics

16.1 Cognitive Engineering, Human-Machine Interface, Displays, and Controls 16.2 Anthropometric Principles, Percentile Design, and Biomechanical Posture 16.3 Environmental Ergonomics: Industrial Noise, Lighting, and Heat Stress

17 Chapter 17: Physical Ergonomics & Workplace Safety

17.1 Physical Ergonomics: The NIOSH Manual Lifting Equation 17.2 Cumulative Trauma Disorders and Postural Assessment 17.3 Workplace Safety: OSHA Standards, Hazard Analysis, and Control Hierarchy

18 Chapter 18: Work Design & Measurement

18.1 Methods Engineering, Process Charting, and Principles of Motion Economy 18.2 Direct Stopwatch Time Study: Observed Time, Performance Rating, and Allowances 18.3 Predetermined Time Systems, Work Sampling, and Learning Curves

19 Chapter 19: Quality Management, Six Sigma & Analytical Tools

19.1 Quality Philosophies, Total Quality Management, and Cost of Quality 19.2 Six Sigma DMAIC Methodology and Quality Function Deployment 19.3 The Seven Basic Quality Tools, Root Cause Analysis, and Taguchi Loss Function

20 Chapter 20: Statistical Process Control

20.1 Statistical Process Control Principles, Variation, and Run Rules 20.2 Variable Control Charts: X-bar & R, X-bar & S, and Individual-Moving Range 20.3 Attribute Control Charts: Defectives (p, np) and Defects (c, u)

21 Chapter 21: Process Capability & Acceptance Sampling

21.1 Process Capability Indices and Defect Levels 21.2 Acceptance Sampling Concepts and Operating Characteristic Curves 21.3 Sampling Risks, AQL, LTPD, and Standard Sampling Plans

22 Chapter 22: Systems Engineering & Life-Cycle Management

22.1 The Systems Engineering V-Model, Stakeholder Requirements, and Functional Architecture 22.2 Configuration Management, Interface Control, and Verification & Validation 22.3 Life-Cycle Costing, Maintainability, and System Availability

23 Chapter 23: Reliability Engineering & Risk Analysis

23.1 Reliability Mathematics, Hazard Rates, and the Bathtub Curve 23.2 System Reliability Configurations: Series, Parallel, and k-out-of-n Systems 23.3 Failure Modes and Effects Analysis and Fault Tree Analysis

8.3 Duality, Sensitivity Analysis, and Integer Linear Programming

Key Takeaways Explain This Topic AI

The shadow price (dual price) of a constraint quantifies the marginal change in the optimal objective value per unit increase in its right-hand side, remaining constant strictly within the allowable RHS range.

The Strong Duality Theorem guarantees that if a primal linear program has an optimal solution, its dual also has an optimal solution and their optimal objective values are strictly identical (Z* = W*).

Complementary Slackness dictates that if a primal constraint is non-binding (slack > 0), its corresponding dual shadow price must be zero; conversely, if a shadow price is strictly positive, the constraint must be tightly binding.

Integer linear programming (ILP) cannot be solved by simply rounding continuous LP relaxation solutions, as rounding frequently causes severe constraint violations or drastic suboptimality.

The Branch and Bound algorithm systematically searches integer solutions by branching on fractional variables and fathoming (pruning) subproblem nodes based on infeasibility, integrality, or bound inferiority.

Last updated: September 2026

8.3 Duality, Sensitivity Analysis, and Integer Linear Programming

Finding the optimal corner point of a linear program is rarely the end of an industrial engineer's task. Real-world parameters—material costs, labor rates, and machine capacities—are subject to supplier price changes, contract renegotiations, and equipment breakdowns. Sensitivity analysis evaluates how the optimal solution behaves when problem parameters change. Duality theory reveals the fundamental economic valuation embedded within every linear program. When decisions require discrete counts or binary yes/no choices, Integer Linear Programming (ILP) provides the necessary modeling tools.

1. Sensitivity Analysis & Post-Optimality Analysis

Sensitivity analysis (also known as post-optimality analysis) examines how changes in the original LP parameters affect the optimal solution without having to re-solve the entire problem from scratch.

1. Shadow Price (Dual Price, Marginal Value)

The shadow price ( y i ∗ y_i^* y i ∗ ​ ) of constraint i i i represents the rate of improvement in the optimal objective function value ( Z ∗ Z^* Z ∗ ) per unit increase in the right-hand-side capacity ( b i b_i b i ​ ), assuming all other model parameters remain unchanged: y i ∗ = ∂ Z ∗ ∂ b i y_i^* = \frac{\partial Z^*}{\partial b_i} y i ∗ ​ = ∂ b i ​ ∂ Z ∗ ​

Maximization Problem :

For a ≤ \le ≤ capacity constraint: y i ∗ ≥ 0 y_i^* \ge 0 y i ∗ ​ ≥ 0 . Acquiring more capacity expands the feasible region, allowing Z ∗ Z^* Z ∗ to increase (or stay constant).

For a ≥ \ge ≥ requirement constraint: y i ∗ ≤ 0 y_i^* \le 0 y i ∗ ​ ≤ 0 . Raising a minimum requirement tightens the feasible region, reducing total profit.

Non-Binding Constraints : If a constraint has positive slack ( s i ∗ > 0 s_i^* > 0 s i ∗ ​ > 0 ), the resource is not fully utilized. Adding more of an idle resource provides zero operational benefit, so its shadow price is strictly zero ( y i ∗ = 0 y_i^* = 0 y i ∗ ​ = 0 ).

2. Allowable Range of Right-Hand-Side Values ( b i b_i b i ​ )

The shadow price y i ∗ y_i^* y i ∗ ​ is not constant indefinitely. It remains valid only within an interval called the Allowable Range [ b i , min ⁡ , b i , max ⁡ ] [b_{i,\min}, b_{i,\max}] [ b i , m i n ​ , b i , m a x ​ ] , defined as: b i − Allowable Decrease ≤ b i ≤ b i + Allowable Increase b_i - \text{Allowable Decrease} \le b_i \le b_i + \text{Allowable Increase} b i ​ − Allowable Decrease ≤ b i ​ ≤ b i ​ + Allowable Increase

Inside the Range : The current set of basic variables remains optimal. The coordinates of the optimal solution shift linearly, and the change in the optimal objective value is exact: Δ Z ∗ = y i ∗ ⋅ Δ b i \Delta Z^* = y_i^* \cdot \Delta b_i Δ Z ∗ = y i ∗ ​ ⋅ Δ b i ​

Outside the Range : A basis change occurs. The current shadow price is no longer valid, and a new set of binding constraints governs the system.

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

The allowable range for an objective coefficient c j c_j c j ​ defines the interval over which the current optimal corner point ( x 1 ∗ , x 2 ∗ , … , x n ∗ ) (x_1^*, x_2^*, \dots, x_n^*) ( x 1 ∗ ​ , x 2 ∗ ​ , … , x n ∗ ​ ) remains optimal : c j − Allowable Decrease ≤ c j ≤ c j + Allowable Increase c_j - \text{Allowable Decrease} \le c_j \le c_j + \text{Allowable Increase} c j ​ − Allowable Decrease ≤ c j ​ ≤ c j ​ + Allowable Increase

Inside the Range : The optimal production quantities ( x j ∗ x_j^* x j ∗ ​ ) do not change at all! However, the total objective value updates directly: Δ Z ∗ = x j ∗ ⋅ Δ c j \Delta Z^* = x_j^* \cdot \Delta c_j Δ Z ∗ = x j ∗ ​ ⋅ Δ c j ​

Reduced Cost of a Non-Basic Variable : For a variable currently at zero ( x j ∗ = 0 x_j^* = 0 x j ∗ ​ = 0 ), the reduced cost represents the amount by which c j c_j c j ​ must improve before it becomes economical to produce product j j j .

2. Duality Theory and Mathematical Foundations

Every linear program (called the Primal ) has an associated mirror problem called the Dual . If the Primal is a resource allocation problem that maximizes profit, the Dual is a resource valuation problem that minimizes the imputed economic worth of the resources. PRIMAL PROBLEM (Resource Allocation)

• Maximize Z = c^T x subject to Ax <= b, x >= 0
• │
• Duality │ Relationship
• ▼
• DUAL PROBLEM (Resource Valuation)
• Minimize W = b^T y subject to A^T y >= c, y >= 0
• Primal-to-Dual Conversion Rules (The Canonical Form)

Primal Feature (Maximization) Dual Feature (Minimization)

Objective : Maximize Z = ∑ c j x j Z = \sum c_j x_j Z = ∑ c j ​ x j ​ Objective : Minimize W = ∑ b i y i W = \sum b_i y_i W = ∑ b i ​ y i ​

• Number of Decision Variables : n n n variables ( x j x_j x j ​ ) Number of Constraints : n n n constraints
• Number of Constraints : m m m constraints Number of Decision Variables : m m m variables ( y i y_i y i ​ )

Constraint Matrix : A A A ( m × n m \times n m × n ) Constraint Matrix : A T A^T A T ( n × m n \times m n × m , transposed)

Right-Hand Side Vector : b \mathbf{b} b ( m × 1 m \times 1 m × 1 ) Dual Objective Coefficients : b T \mathbf{b}^T b T ( 1 × m 1 \times m 1 × m )

Objective Coefficients : c \mathbf{c} c ( 1 × n 1 \times n 1 × n ) Dual Right-Hand Side Vector : c T \mathbf{c}^T c T ( n × 1 n \times 1 n × 1 )

• i i i -th constraint is ≤ \le ≤ i i i -th dual variable is non-negative ( y i ≥ 0 y_i \ge 0 y i ​ ≥ 0 )
• i i i -th constraint is ≥ \ge ≥ i i i -th dual variable is non-positive ( y i ≤ 0 y_i \le 0 y i ​ ≤ 0 )
• i i i -th constraint is = = = i i i -th dual variable is unrestricted in sign (URS)
• j j j -th primal variable is x j ≥ 0 x_j \ge 0 x j ​ ≥ 0 j j j -th dual constraint is ≥ c j \ge c_j ≥ c j ​
• j j j -th primal variable is URS j j j -th dual constraint is = c j = c_j = c j ​
• Fundamental 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

Any dual feasible solution provides an upper bound on the optimal primal objective value.

Strong Duality Theorem :

If either the primal or the dual problem has a finite optimal solution, then both have optimal solutions, and their optimal objective values are strictly equal : 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 ∗

Infeasibility / Unboundedness Corollaries :

If the Primal is unbounded ( Z → + ∞ Z \to +\infty Z → + ∞ ), the Dual must be infeasible .

If the Dual is unbounded ( W → − ∞ W \to -\infty W → − ∞ ), the Primal must be infeasible .

If the Primal is infeasible, the Dual is either unbounded or infeasible .

Complementary Slackness Theorem :

Let x ∗ \mathbf{x}^* x ∗ and y ∗ \mathbf{y}^* y ∗ be feasible solutions to the primal and dual problems, respectively. They are both optimal if and only if: x j ∗ ⋅ ( Dual Slack j ) = 0 , ∀ j = 1 , … , n x_j^* \cdot (\text{Dual Slack}_j) = 0, \quad \forall j = 1, \dots, n x j ∗ ​ ⋅ ( Dual Slack j ​ ) = 0 , ∀ j = 1 , … , n y i ∗ ⋅ ( Primal Slack i ) = 0 , ∀ i = 1 , … , m y_i^* \cdot (\text{Primal Slack}_i) = 0, \quad \forall i = 1, \dots, m y i ∗ ​ ⋅ ( Primal Slack i ​ ) = 0 , ∀ i = 1 , … , m

Physical insight : If a resource is not fully consumed (Primal Slack > 0 > 0 > 0 ), its economic shadow price must be zero ( y i ∗ = 0 y_i^* = 0 y i ∗ ​ = 0 ). If a resource has a positive shadow price ( y i ∗ > 0 y_i^* > 0 y i ∗ ​ > 0 ), it must be fully exhausted with zero slack.

3. Integer Linear Programming (ILP) Formulations

In many practical engineering contexts, decision variables cannot take fractional values:

Pure Integer Linear Program (PILP) : Every decision variable is restricted to integer values ( x j ∈ Z + x_j \in \mathbb{Z}^+ x j ​ ∈ Z + ).

Mixed-Integer Linear Program (MILP) : Some variables are continuous (e.g., fluid volume, operating hours) while others are integer (e.g., number of machines, batches).

Binary (0-1) Integer Program : Variables are restricted to binary choices: y j ∈ { 0 , 1 } y_j \in \{0, 1\} y j ​ ∈ { 0 , 1 } .

• Core 0-1 Binary Logical Formulations COMMON 0-1 BINARY LOGICAL CONSTRAINTS
• │
• ┌───────────────────────────┼───────────────────────────┐
• ▼ ▼ ▼
• ┌───────────────┐ ┌───────────────┐ ┌───────────────┐
• │ FIXED-CHARGE │ │ MUTUALLY │ │ PRECEDENCE / │
• │ ACTIVATION │ │ EXCLUSIVE │ │ CONTINGENCY │
• │ x <= M * y │ │ y_1 + y_2<= 1│ │ y_B <= y_A │
• └───────────────┘ └───────────────┘ └───────────────┘

Fixed-Charge (Setup) Problems :

A production process incurs a fixed setup cost K K K if initiated, plus a variable cost c c c per unit produced. Let continuous x x x be production volume and binary y ∈ { 0 , 1 } y \in \{0, 1\} y ∈ { 0 , 1 } indicate whether the line is active: Cost = K y + c x \text{Cost} = K y + c x Cost = Ky + c x x ≤ M ⋅ y x \le M \cdot y x ≤ M ⋅ y

Where M M M is a sufficiently large upper bound on maximum possible production ("Big-M"). If y = 0 y = 0 y = 0 , x ≤ 0 ⟹ x = 0 x \le 0 \implies x = 0 x ≤ 0 ⟹ x = 0 . If y = 1 y = 1 y = 1 , x ≤ M x \le M x ≤ M (unconstrained).

Mutually Exclusive Alternatives :

Select at most one project from a set of candidate investments: ∑ j = 1 k y j ≤ 1 \sum_{j=1}^{k} y_j \le 1 j = 1 ∑ k ​ y j ​ ≤ 1

Contingent / Precedence Decisions :

Project B cannot be undertaken unless Project A is approved: y B ≤ y A y_B \le y_A y B ​ ≤ y A ​

The 0-1 Knapsack Problem :

Select items j = 1 , … , n j = 1, \dots, n j = 1 , … , n with values v j v_j v j ​ and weights w j w_j w j ​ to maximize total value without exceeding capacity W W W : Maximize Z = ∑ j = 1 n v j y j subject to ∑ j = 1 n w j y j ≤ W , y j ∈ { 0 , 1 } \text{Maximize } Z = \sum_{j=1}^{n} v_j y_j \quad \text{subject to } \sum_{j=1}^{n} w_j y_j \le W, \quad y_j \in \{0, 1\} Maximize Z = j = 1 ∑ n ​ v j ​ y j ​ subject to j = 1 ∑ n ​ w j ​ y j ​ ≤ W , y j ​ ∈ { 0 , 1 }

• 4. Solving ILP: Branch and Bound Fundamentals
• Why Simple Rounding Fails

A frequent misconception is that an integer program can be solved by relaxing the integrality requirement, solving the continuous LP Relaxation , and rounding the variables to the nearest integer. Rounding is fundamentally flawed :

Rounding can produce an infeasible point that severely violates one or more constraints.

Even if feasible, rounded points can be drastically suboptimal compared to the true integer optimum, which may lie far from the continuous relaxation boundary. Continuous Feasible Region vs. Integer Grid Lattice:

• x_2 ^
• │ / Constraint boundary: x_1 + 2 x_2 <= 5
• 3 ┼ /
• │ / (LP Relaxation Optimum: x_1 = 0, x_2 = 2.5)
• 2 ┼ ●─── [Rounding up to (0, 3) is INFEASIBLE!]
• │ │ ●─ [Rounding down to (0, 2) yields Z = 18]
• 1 ┼ │ ●─ [True Integer Optimum could be (3, 1) yielding Z = 23!]
• │ │
• 0 ┴──┼───┼───┼───┼──> x_1
• 0 1 2 3
• The Branch and Bound Algorithm

Branch and Bound solves ILPs through intelligent enumeration using a tree structure:

LP Relaxation : Drop the integrality condition ( x j ∈ Z x_j \in \mathbb{Z} x j ​ ∈ Z ) and solve as a continuous LP. For a maximization problem, the LP relaxation provides an Upper Bound (UB) on the optimal integer value ( Z IP ∗ ≤ Z LP ∗ Z_{\text{IP}}^* \le Z_{\text{LP}}^* Z IP ∗ ​ ≤ Z LP ∗ ​ ).

Branching : If an integer-restricted variable takes a fractional value (e.g., x 1 = 3.6 x_1 = 3.6 x 1 ​ = 3.6 ), create two mutually exclusive child subproblems: Child 1: x 1 ≤ 3 and Child 2: x 1 ≥ 4 \text{Child 1: } x_1 \le 3 \quad \text{and} \quad \text{Child 2: } x_1 \ge 4 Child 1: x 1 ​ ≤ 3 and Child 2: x 1 ​ ≥ 4

Bounding : Solve the LP relaxation at each newly created child node.

Fathoming (Pruning) Criteria : A branch is pruned (terminated) without further exploration if any of three conditions occurs:

Fathomed by Infeasibility : The node's LP relaxation has no feasible solution.

Fathomed by Integrality : The node's LP relaxation solution satisfies all integer restrictions. If its objective value exceeds the current best known integer solution ( Incumbent ), it becomes the new incumbent ( Z incumbent = Z node Z_{\text{incumbent}} = Z_{\text{node}} Z incumbent ​ = Z node ​ ).

Fathomed by Bound : The node's LP relaxation objective value is worse than or equal to the current incumbent ( Z node ≤ Z incumbent Z_{\text{node}} \le Z_{\text{incumbent}} Z node ​ ≤ Z incumbent ​ for maximization). Since relaxing constraints can only degrade the bound further down the tree, no integer solution in that subtree can beat the incumbent.

• 5. Step-by-Step Worked Engineering Examples
• Worked Example 8.3.1: Sensitivity Report Analysis & Capacity Investment

Problem : A manufacturing plant operates a stamping press and an automated assembly cell. The optimal solution yields a weekly profit of $85,000 . The sensitivity report provides the following data for the two capacity constraints:

Constraint Current RHS ( b i b_i b i ​ ) Slack Shadow Price ( y i ∗ y_i^* y i ∗ ​ ) Allowable Increase Allowable Decrease

• Stamping Press 400 hours 0 $65/hour 60 hours 40 hours
• Assembly Cell 500 hours 45 hours $0/hour 1E+30 ( ∞ \infty ∞ ) 45 hours

An equipment supplier offers to lease the plant 35 additional stamping press hours per week for a flat fee of $1,800 . Should management accept the offer, and what is the net change in weekly profit?

What would be the financial impact of acquiring 20 additional assembly cell hours?

Solution :

Evaluate Stamping Press Lease :

Current available stamping hours = 400 400 400 . Proposed increase Δ b 1 = + 35 \Delta b_1 = +35 Δ b 1 ​ = + 35 hours.

Check Allowable Range: The allowable increase is 60 60 60 hours. Because 35 ≤ 60 35 \le 60 35 ≤ 60 , the proposed increase falls strictly within the allowable range.

The shadow price of $65/hour is valid.

Gross increase in optimal revenue: Δ Z ∗ = y 1 ∗ ⋅ Δ b 1 = ( $ 65 / hour ) × 35 hours = $ 2,275 \Delta Z^* = y_1^* \cdot \Delta b_1 = (\$65/\text{hour}) \times 35\text{ hours} = \$2{,}275 Δ Z ∗ = y 1 ∗ ​ ⋅ Δ b 1 ​ = ( $65/ hour ) × 35 hours = $2 , 275

Subtract the flat lease cost: Net Profit Change = $ 2,275 − $ 1,800 = + $ 475 \text{Net Profit Change} = \$2{,}275 - \$1{,}800 = +\$475 Net Profit Change = $2 , 275 − $1 , 800 = + $475

Engineering Decision : Management should accept the offer ; net profit increases by $475 per week .

Evaluate Assembly Cell Expansion :

Current slack in Assembly Cell is 45 45 45 hours, meaning 45 45 45 hours currently sit idle.

The shadow price is $0/hour .

Adding 20 20 20 more hours increases idle capacity from 45 45 45 to 65 65 65 hours.

Financial Impact : $0 change in profit . Acquiring additional capacity for a non-binding resource provides zero economic value.

Worked Example 8.3.2: Complete Primal-to-Dual Conversion

Problem : Formulate the mathematical dual of the following primal linear program: Maximize Z = 50 x 1 + 80 x 2 Subject to: 1 x 1 + 2 x 2 ≤ 32 ( Machining, hrs ) 3 x 1 + 4 x 2 ≤ 84 ( Finishing, hrs ) 1 x 1 + 0 x 2 ≤ 18 ( Component A limit ) x 1 ≥ 0 , x 2 ≥ 0 \begin{aligned}

• \text{Maximize } & Z = 50 x_1 + 80 x_2 \\
• \text{Subject to: } & 1 x_1 + 2 x_2 \le 32 \quad (\text{Machining, hrs}) \\
• & 3 x_1 + 4 x_2 \le 84 \quad (\text{Finishing, hrs}) \\
• & 1 x_1 + 0 x_2 \le 18 \quad (\text{Component A limit}) \\
• & x_1 \ge 0, \quad x_2 \ge 0

\end{aligned} Maximize Subject to: ​ Z = 50 x 1 ​ + 80 x 2 ​ 1 x 1 ​ + 2 x 2 ​ ≤ 32 ( Machining, hrs ) 3 x 1 ​ + 4 x 2 ​ ≤ 84 ( Finishing, hrs ) 1 x 1 ​ + 0 x 2 ​ ≤ 18 ( Component A limit ) x 1 ​ ≥ 0 , x 2 ​ ≥ 0 ​

Solution :

Determine Dual Variables and Dimensions :

Primal has 3 constraints ⟹ \implies ⟹ Dual has 3 decision variables: y 1 , y 2 , y 3 y_1, y_2, y_3 y 1 ​ , y 2 ​ , y 3 ​ .

Because all primal constraints are ≤ \le ≤ and primal objective is Maximize, dual variables are non-negative: y 1 , y 2 , y 3 ≥ 0 y_1, y_2, y_3 \ge 0 y 1 ​ , y 2 ​ , y 3 ​ ≥ 0 .

Formulate Dual Objective Function :

Primal RHS vector b = [ 32 , 84 , 18 ] T \mathbf{b} = [32, 84, 18]^T b = [ 32 , 84 , 18 ] T becomes dual objective coefficients: Minimize W = 32 y 1 + 84 y 2 + 18 y 3 \text{Minimize } W = 32 y_1 + 84 y_2 + 18 y_3 Minimize W = 32 y 1 ​ + 84 y 2 ​ + 18 y 3 ​

Formulate Dual Constraints (Transpose Matrix A T A^T A T ) :

Primal column 1 coefficients (for x 1 x_1 x 1 ​ ) are [ 1 , 3 , 1 ] T [1, 3, 1]^T [ 1 , 3 , 1 ] T , with primal objective coefficient c 1 = 50 c_1 = 50 c 1 ​ = 50 : 1 y 1 + 3 y 2 + 1 y 3 ≥ 50 1 y_1 + 3 y_2 + 1 y_3 \ge 50 1 y 1 ​ + 3 y 2 ​ + 1 y 3 ​ ≥ 50

Primal column 2 coefficients (for x 2 x_2 x 2 ​ ) are [ 2 , 4 , 0 ] T [2, 4, 0]^T [ 2 , 4 , 0 ] T , with primal objective coefficient c 2 = 80 c_2 = 80 c 2 ​ = 80 : 2 y 1 + 4 y 2 + 0 y 3 ≥ 80 ⟹ 2 y 1 + 4 y 2 ≥ 80 2 y_1 + 4 y_2 + 0 y_3 \ge 80 \implies 2 y_1 + 4 y_2 \ge 80 2 y 1 ​ + 4 y 2 ​ + 0 y 3 ​ ≥ 80 ⟹ 2 y 1 ​ + 4 y 2 ​ ≥ 80

Dual Non-Negativity : y 1 ≥ 0 , y 2 ≥ 0 , y 3 ≥ 0 y_1 \ge 0, \quad y_2 \ge 0, \quad y_3 \ge 0 y 1 ​ ≥ 0 , y 2 ​ ≥ 0 , y 3 ​ ≥ 0

Worked Example 8.3.3: Branch and Bound Tree Traversal

Problem : A project manager maximizes investment returns using binary integer programming. At the root node (Node 0), the continuous LP relaxation yields Z LP = 145.8 Z_{\text{LP}} = 145.8 Z LP ​ = 145.8 with y 1 = 0.6 , y 2 = 1.0 , y 3 = 0.4 y_1 = 0.6, y_2 = 1.0, y_3 = 0.4 y 1 ​ = 0.6 , y 2 ​ = 1.0 , y 3 ​ = 0.4 . An initial feasible integer solution is known with Z incumbent = 120 Z_{\text{incumbent}} = 120 Z incumbent ​ = 120 .

Branching on y 1 y_1 y 1 ​ produces:

Node 1 ( y 1 = 0 y_1 = 0 y 1 ​ = 0 ): Solves to continuous Z LP = 118.5 Z_{\text{LP}} = 118.5 Z LP ​ = 118.5 with y 2 = 1.0 , y 3 = 0.8 y_2 = 1.0, y_3 = 0.8 y 2 ​ = 1.0 , y 3 ​ = 0.8 .

Node 2 ( y 1 = 1 y_1 = 1 y 1 ​ = 1 ): Solves to continuous Z LP = 141.2 Z_{\text{LP}} = 141.2 Z LP ​ = 141.2 with y 2 = 0.7 , y 3 = 0.0 y_2 = 0.7, y_3 = 0.0 y 2 ​ = 0.7 , y 3 ​ = 0.0 .

Explain how the Branch and Bound algorithm processes Node 1 and Node 2.

Solution :

Evaluation of Node 1 ( y 1 = 0 y_1 = 0 y 1 ​ = 0 ) :

The LP relaxation upper bound at Node 1 is Z LP = 118.5 Z_{\text{LP}} = 118.5 Z LP ​ = 118.5 . The current best known integer solution has Z incumbent = 120 Z_{\text{incumbent}} = 120 Z incumbent ​ = 120 . Because 118.5 ≤ 120 118.5 \le 120 118.5 ≤ 120 , Node 1 is Fathomed by Bound Inferiority . No integer solution in this branch can ever exceed 118.5, so Node 1 is pruned without further exploration.

Evaluation of Node 2 ( y 1 = 1 y_1 = 1 y 1 ​ = 1 ) :

The LP relaxation upper bound is Z LP = 141.2 Z_{\text{LP}} = 141.2 Z LP ​ = 141.2 . Since 141.2 > 120 141.2 > 120 141.2 > 120 , this branch could contain an integer solution superior to the current incumbent. However, the solution is not yet all-integer ( y 2 = 0.7 y_2 = 0.7 y 2 ​ = 0.7 is fractional). Therefore, Node 2 cannot be fathomed . The algorithm must branch further on y 2 y_2 y 2 ​ ( y 2 = 0 y_2 = 0 y 2 ​ = 0 and y 2 = 1 y_2 = 1 y 2 ​ = 1 ).

6. NCEES Reference Handbook Tips & Realistic Exam Traps

Extrapolating Shadow Prices Beyond Allowable Limits : On the FE exam, questions frequently test whether you remember the allowable range. If a question asks for the profit increase from adding 100 hours when the allowable increase is only 60 hours, multiplying 100 × y ∗ 100 \times y^* 100 × y ∗ is incorrect! Beyond 60 hours, the basis changes and the shadow price decreases.

Sign Conventions for Dual Prices : Be cautious with constraint senses. For a ≥ \ge ≥ requirement in a maximization problem, increasing the RHS restricts the feasible space, making the shadow price negative. In minimization problems, increasing capacity reduces total cost, giving a negative shadow price.

Transposing the Constraint Matrix : When converting primal to dual, remember that primal constraint rows become dual constraint columns. Missing the transpose operation ( A → A T A \to A^T A → A T ) is the single most common algebraic error on duality exam problems.

Big-M Value Selection : In fixed-charge models x ≤ M y x \le M y x ≤ M y , choosing M M M too small restricts valid production levels, while choosing M M M excessively large ( 10 12 10^{12} 1 0 12 ) introduces severe numerical round-off instability in Simplex solvers.