MATH 4810Computational Modelling

Module 06 · Capstone Project

A Linear Program with Duality and Sensitivity

Formulate a realistic linear program, solve it, construct its dual, interpret the shadow prices, and produce a sensitivity report for a decision-maker.

Weight Counts toward the module component of the course grade Duration ≈ 12 hours Prerequisite Units 6.1 and 6.2

Module 6 capstone

A Linear Program with Duality and Sensitivity

From formulation to a decision-ready sensitivity report.

§ Project brief

The Module 6 capstone is a complete linear-programming study of a decision problem. You will formulate the LP, implement it in a spreadsheet, solve it, construct its dual, interpret the shadow prices and reduced costs, produce a sensitivity report, and recommend a course of action.

The problem should be realistic — a production plan, a resource allocation, a portfolio, a scheduling problem — with at least three decision variables and three constraints. The sensitivity analysis is the most important part of the deliverable; it is what makes the optimal solution useful to a decision-maker.

Sensitivity is the deliverable

The optimal solution is a point. The sensitivity report is what a decision-maker actually needs: which constraints are worth relaxing, which are not, and how robust the recommendation is.

§ Learning outcomes addressed

This capstone assesses

  • Formulate a linear program from a prose decision problem.
  • Implement and solve the LP in a spreadsheet.
  • Verify feasibility and optimality.
  • Construct the dual and verify strong duality.
  • Interpret shadow prices and reduced costs.
  • Produce a sensitivity report with ranges and scenario analysis.

§ Suggested problems

Problem A

Production planning

Multi-product firm with labour, material, and demand constraints. The classic LP.

Problem B

Blending problem

Choose ingredient quantities to meet quality specifications at minimum cost. Common in food and chemical industries.

Problem C

Transportation problem

Ship goods from multiple origins to multiple destinations at minimum cost. Supply and demand constraints.

Problem D

Workforce scheduling

Assign workers to shifts to meet coverage requirements at minimum cost. Common in service industries.

§ Deliverables

Deliverables and weights
Deliverable Weight What it should contain
LP formulation 15% Decision variables, objective, constraints. Units stated for every coefficient.
Spreadsheet model and solution 20% Three-layer architecture. Solver configured and solution obtained. Feasibility verified.
Dual and shadow prices 20% Dual constructed. Strong duality verified. Shadow prices interpreted in decision-relevant terms.
Sensitivity report 25% Ranges for objective coefficients and RHS. Scenario analysis for changes that exceed the ranges.
Recommendation 10% Which resources to acquire and at what cost. Which conclusions are robust.
Technical report 10% Two to four pages covering the model, solution, dual, sensitivity, and recommendation.

§ Milestones

  1. Choose the problem State the decision, the objective, and the constraints. One hour.
  2. Formulate the LP Decision variables with units, objective, constraints. Two hours.
  3. Implement and solve Spreadsheet with three-layer architecture. Two hours.
  4. Verify feasibility and optimality Substitute the solution into each constraint; check binding constraints. One hour.
  5. Construct the dual Write the dual LP. Verify strong duality. Interpret the shadow prices. Two hours.
  6. Produce the sensitivity report Ranges, 100 percent rule, scenario analysis. Two hours.
  7. Write the report and recommendation Two to four pages. Two hours.

§ Rubric

Assessment criteria
Criterion Excellent Satisfactory Needs work
Formulation Complete, precise, units checked. Complete but units not stated. Missing elements or non-linear.
Solution Feasibility verified; binding constraints identified. Solution obtained but not verified. Solver run without checks.
Dual Dual constructed; strong duality verified; shadow prices interpreted. Dual constructed; interpretation terse. Dual missing or incorrect.
Sensitivity Ranges, 100 percent rule, and scenario analysis all present. Ranges present; scenario analysis thin. Sensitivity not performed.
Recommendation Clear, quantitative, conditional on the model. Present but not quantitative. Missing or overclaims.

§ Common pitfalls

Watch for these

  • Reversed inequality directions. The single most common solver configuration error.
  • Reporting shadow prices without their sensitivity ranges. A shadow price is valid only within its range.
  • Extrapolating shadow prices beyond the range. Re-solve when the change exceeds the range.
  • Confusing the dual with an alternative problem. The dual is the same problem from the resource perspective.
  • Recommending an action without stating the model's assumptions. The recommendation is conditional on the model.

§ Submission

What to submit

  • A single ZIP archive named M6-capstone-yourid.zip.
  • The archive contains the LP formulation, the spreadsheet with the solver configuration, the dual construction, the sensitivity report, and the technical report.
  • Submit through the course LMS before the deadline listed on the course schedule.
👤