MATH 4810 Computational Modelling

Module 06 · Optimization

Optimization, Duality, and Sensitivity

Formulate decision problems as linear programs, solve them in a spreadsheet, and then interrogate the answer. Duality, shadow prices, reduced costs, and sensitivity ranges turn an optimal solution into decision-relevant information.

2 units · 6 lessons 2 laboratories Assignment 5 option ≈ 20 hours

Module 06

Optimization, Duality, and Sensitivity

Linear programming formulation, spreadsheet solution, duality theory, and the sensitivity analysis that makes an optimum usable.

§ Overview

The source course expects students to formulate optimization problems using linear programming, state and apply the fundamental duality theorem, and analyze models with and without computer software. This module delivers all three, and treats sensitivity analysis as an inseparable part of solving a linear program.

Unit 6.1

Linear programming models.

Unit 6.2

Duality and sensitivity.

Laboratories 11–12

Linear programming and sensitivity analysis.

Assignment 5 option

Optimization model under Assignment 5.

§ Learning outcomes

By the end of Module 6 you will be able to

  • Formulate linear programming models from decision problems.
  • Implement and solve a linear program in a spreadsheet.
  • Check feasibility and optimality, and verify that the solver's answer is the answer to your problem.
  • Explain and apply the fundamental duality theorem.
  • Analyze shadow prices, reduced costs, binding constraints, and sensitivity ranges.

6.1 Linear Programming Models

Translate a decision problem into decision variables, an objective, and constraints — then build it in a spreadsheet and test it.

Lesson 1

Decision variables, objectives, and constraints

Translate a decision problem into linear-programming form.

 Lesson 2

Spreadsheet implementation and solver use

Build, solve, and check a linear program in a spreadsheet.

 Lesson 3

Feasibility, optimality, and model checking

Test that the solver's answer is the answer to your problem.

6.2 Duality and Sensitivity

Every linear program has a dual. The dual supplies marginal values and the ranges within which those values remain valid — the information a decision-maker actually needs.

Lesson 1

Dual models and the fundamental duality theorem

Construct the dual and state what duality guarantees.

 Lesson 2

Shadow prices and reduced costs

Interpret dual values as marginal rates of change.

 Lesson 3

Sensitivity ranges and scenario analysis

Find the ranges within which the interpretation holds.

§ Laboratories

Lab 11

Linear programming

Formulate and solve a linear program in a spreadsheet, then verify the solution by hand on a small instance.

Lab 12

Duality and sensitivity analysis

Construct the dual, interpret shadow prices and reduced costs, and compute sensitivity ranges.

§ Assignment 5 option

Optimization model · 10% (under Assignment 5)

Students who choose the optimization option for Assignment 5 formulate and solve a linear program, construct its dual, and report shadow prices, reduced costs, and sensitivity ranges with an interpretation for a decision-maker.

Full assignment brief →

§ Common pitfalls

Watch for these

  • Solver output does not guarantee that the model represents the intended decision problem. An optimal solution to a mis-specified linear program is still a mis-specified answer.
  • Shadow prices are valid only within specified sensitivity ranges. Beyond the allowable increase or decrease, the dual values change and the reported interpretation no longer holds.
👤