MATH 4810Computational Modelling

Module 06 · Unit 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.

3 lessons ≈ 8 hours Laboratory 11 Feeds Assignment 5

Unit 6.1

Linear Programming Models

Formulation, spreadsheet implementation, and the checks that confirm the solution is the answer to your problem.

  1. Unit 6.1
  2. Unit 6.2

§ Overview

A linear program is a mathematical representation of a decision problem: which quantities to choose, to maximize or minimize what, and subject to which limitations. The art of linear programming is not in solving the problem — the solver does that — but in stating it correctly, and in checking that the solver's answer corresponds to the decision problem you actually meant to solve.

This unit covers the three modelling steps (specify the decision variables, the objective, and the constraints), the spreadsheet implementation and solver use, and the feasibility and optimality checks that confirm the solution. The interpretation of the solution in terms of the decision is a modelling activity, not a technical one, and is emphasised throughout.

Lesson 1

Decision variables, objectives, and constraints

Lesson 2

Spreadsheet implementation and solver use

Lesson 3

Feasibility, optimality, and model checking

Laboratory 11

Linear programming

§ Learning outcomes

By the end of Unit 6.1 you will be able to

  • Identify the decision variables in a decision problem.
  • State the objective function and the constraints in linear form.
  • Recognise when a problem cannot be represented as a linear program.
  • Implement a linear program in a spreadsheet.
  • Apply the solver and verify the solution against the constraints.
  • Check that the solver's optimum is feasible, optimal, and consistent with the intended decision problem.

§ Lessons

Lesson 1

Decision variables, objectives, and constraints

Translate a decision problem into linear-programming form. The three ingredients of every LP model.

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.

§ Anatomy of an LP

Every linear program has three parts:

  1. Decision variables. The quantities the decision-maker chooses. Usually denoted x₁, x₂, …, xₙ.
  2. Objective function. A linear function of the decision variables to be maximized or minimized.
  3. Constraints. Linear inequalities or equalities that the decision variables must satisfy. Often accompanied by nonnegativity restrictions.
Feasible region of a two-variable linear program A two-dimensional plot with x1 on the horizontal axis and x2 on the vertical axis. Several constraint lines bound a shaded convex region in the first quadrant. A dashed line representing the objective function touches the region at a corner, which is the optimal solution. x₁ x₂ optimum feasible region
Figure 6.1. Feasible region of a two-variable LP. The region is bounded by the constraint lines. The optimal solution, shown by the red dot, lies at a corner of the region — a general property of linear programs.

Corner solutions

The optimal solution of a linear program lies at a corner (vertex) of the feasible region, unless the objective is parallel to a constraint edge, in which case an entire edge may be optimal. This is why LP algorithms search the vertices of the feasible region rather than the interior.

§ Self-check

Check your understanding

Question 1

A linear program is defined by:

Show answer

Decision variables, an objective, and constraints.

Question 2

The feasible region of a linear program is:

Show answer

A convex polygon (or polytope). The intersection of linear constraints is always convex.

Question 3

The optimal solution of a linear program is attained at:

Show answer

A vertex of the feasible region. If the objective is parallel to a constraint edge, an entire edge may be optimal.

Question 4

The nonnegativity restriction x_j ≥ 0 is:

Show answer

A modelling decision that depends on the problem. Some variables must be nonnegative by their meaning; others may be free.

Question 5

A nonlinear objective function:

Show answer

Cannot be modelled as a linear program. Linear programming requires linear objectives and constraints.

👤