MAST 20018 - Discrete Maths and Operations Research
Office 149 - Peter Hall Building
Last updated: October 18, 2022
Contents
1 Introduction to Operations Research 4
2 Modelling in Linear Programming 18
3 The geometry of Linear Programming 34
4 The algebra of Linear Programming 45
5 Solving Linear Programs 68
6 The simplex tableau 84
7 Duality theory 106
8 Sensitivity analysis 154
1
Chapter 1
Introduction to Operations Research
2
Operations Research
“In a nutshell, operations research (O.R.) is the discipline of applying advanced analytical methods to help make better
decisions." INFORMS | What O.R. Is
Figure 1.1: The Operations Research approach [4]
3
Applications of Operations Research
Many applications can be found in areas such as:
Figure 1.2: Applications - Slide by Gurobi ?
4
Jobs in Operations Research
Given the multi-disciplinary nature of Operations Research, jobs in the area cover a number of different profiles. Overall, a
very employable student will have good coding, communication and mathematical skills. I have former students who have
worked at (focusing on Australian Businesses):
Accenture
AECOM
Argon & Co
Australian Department of Defence
Biarri
Cardinal Operations
CSRIO
INESC TEC - Institute for Systems and Computer Engineering, Technology and Science
Intelligent Decision Support - Opturion Pty
Neighbourlytics
Scada Data Analytics
Singapore-MIT Alliance for Research & Technology
Transport Safety Victoria
Victorian Centre for Data Insights
Victoria Police
Workforce analytics
YPC Technologies
For further opportunities, see Careers in Mathematics and Statistics
5
Branches of Operations Research
Mathematical Programming,
Dynamic Programming,
Simulation,
Heuristics and metaheuristics
Stochastic Processes / Queuing Theory,
Inventory Theory,
Graph Theory,
etc.
Figure 1.3: Holistic illustration of the disciplines and problems related to operations research. Image by Alex Elkjaer
Vasegaard
6
Mathematical Programming
Modelling and solving a problem using mathematics.
Figure 1.4: Subfields of Mathematical Optimisation: Retrieved from Wikipedia
7
Choosing the right model
Decision making models are mostly useful when they can be solved. Using a modelling framework allows for solving the
models with generic algorithms for that framework.
The choice of the modelling framework is often guided by the capacity of solution algorithms to solve realistic instances of
a problem.
Figure 1.5: Algorithms shed light on models
8
Linear Programming
Linear programming is a modelling framework in which constraints and objective function are linear expressions on
continuous decision variables.
= min
s.t.
≥ ,
≥ 0
Figure 1.6: Pictorial representation of a 2D Linear Program. Fig from Hartman-Baker et. al.
9
Find the cheapest diet that supply daily requirements of 2000 calories, 55g protein, 800mg calcium.
Food Serving size Energy (Cal) Protein (g) Calcium (mg) Price per serving ($)
Oatmeal 28g 110 4 2 0.30
Chicken 100g 205 32 12 2.40
Eggs 2 large 160 13 54 1.30
Whole milk 250ml 160 8 285 0.90
Cherry pie 170g 420 4 22 0.20
Pork and beans 260g 260 14 80 1.90
Example: The diet problem
Data:
Model:
Solving the problem
import gurobipy as gp
from gurobipy import GRB
#DATA
Food, cal, protein, calcium, price = gp.multidict({
’oatmeal’: [110, 4, 2, .30],
’chicken’: [205, 32, 12, 2.40],
’egg’: [160, 13, 54, 1.30 ],
’milk’: [160, 8, 285, .90 ],
’pie’: [420, 4, 22, .20 ],
’pork’: [260, 14, 80, 1.90 ]})
r = {
’cal’: 2000,
’protein’: 55,
’calcium’: 800}
#MODEL
m = gp.Model("diet")
x = m.addVars(Food, name = ’x’)
calCons = m.addConstr( gp.quicksum( cal[f]*x[f] for f in Food) >= r[’cal’] )
calProt = m.addConstr( gp.quicksum( protein[f]*x[f] for f in Food) >= r[’protein’] )
calCalc = m.addConstr( gp.quicksum( calcium[f]*x[f] for f in Food) >= r[’calcium’] )
m.setObjective( gp.quicksum(price[f]*x[f] for f in Food ),GRB.MINIMIZE)
#Analysis
m.optimize()
# Display Solution
print(’SOLUTION:’)
for v in m.getVars():
if v.x > 1e-6:
print(" ", v.varName, v.x)
# Display optimal solution value
print(’ Cost: ’, m.objVal)
#Requirements provided
print(" Calories: ",sum( x[f].x*cal[f] for f in Food ) )
print(" Protein : ", sum( x[f].x*protein[f] for f in Food ))
print(" Calcium : ", sum( x[f].x*calcium[f] for f in Food ))
Implementation
11
Set parameter Username
Academic license - for non-commercial use only - expires 2022-08-28
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[x86])
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3 rows, 6 columns and 18 nonzeros
Model fingerprint: 0x1ed81c8f
Coefficient statistics:
Matrix range [2e+00, 4e+02]
Objective range [2e-01, 2e+00]
Bounds range [0e+00, 0e+00]
RHS range [6e+01, 2e+03]
Presolve removed 0 rows and 4 columns
Presolve time: 0.00s
Presolved: 3 rows, 2 columns, 6 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 3.950000e+02 0.000000e+00 0s
2 3.7821577e+00 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.00 seconds (0.00 work units)
Optimal objective 3.782157676e+00
SOLUTION:
x[milk] 2.0643153526970957
x[pie] 9.62136929460581
Cost: 3.7821576763485485
Calories: 4371.265560165975
Protein : 55.0
Calcium : 800.0
[Finished in 0.5s]
12
MAST 20018 - Unimelb Handbook
Learning outcomes:
? L1 Comprehend the essential features of problems encountered in Operations Research investigations.
? L2 Develop basic skills required to construct formal mathematical models for practical optimisation problems, and
those required to analyse settings from real-world applications;
L3 Appreciate the extent and limitations of a number of Operations Research techniques for solving real-world
problems.
Generic skills:
GS1 Problem-solving skills: the ability to engage with unfamiliar problems and identify relevant solution strategies;
GS2 Analytical skills: the ability to construct and express logical arguments and to work in abstract or general terms
to increase the clarity and efficiency of analysis;
GS3 Collaborative skills: the ability to work in a team; and
GS4 Time-management skills: the ability to meet regular deadlines while balancing competing commitments
13
MAST 20018 - Syllabus (Operations Research)
1. Mathematical modelling.
2. Linear Programming.
Algebra of linear programming.
The simplex method.
Duality Theory.
14 15
Chapter 2
Modelling in Linear Programming
16
The right level of simplification
Finding the right level of simplification is key in modelling.
—————–
On Exactitude in Science - Jorge Luis Borges, Collected Fictions, translated by Andrew Hurley [1].
...In that Empire, the Art of Cartography attained such Perfection that the map of a single Province occupied the entirety of a
City, and the map of the Empire, the entirety of a Province. In time, those Unconscionable Maps no longer satisfied, and the
Cartographers Guilds struck a Map of the Empire whose size was that of the Empire, and which coincided point for point
with it. The following Generations, who were not so fond of the Study of Cartography as their Forebears had been, saw that
that vast Map was Useless, and not without some Pitilessness was it, that they delivered it up to the Inclemencies of Sun and
Winters. In the Deserts of the West, still today, there are Tattered Ruins of that Map, inhabited by Animals and Beggars; in
all the Land there is no other Relic of the Disciplines of Geography.
Suarez Miranda,Viajes devarones prudentes, Libro IV,Cap. XLV, Lerida, 1658.
—
17
Ceci n’est pas une pipe
We model nature and society to understand how they work. Modelling is the art of interpreting and representing reality.
Figure 2.1: Rene Magritte - The treachery of images
18
Modelling frameworks
Nonlinear Programming
Both constraints and objective function can be nonlinear expressions on the decision variables.
= min ()
s.t.
() ≤ 0,
?() = 0
∈ R.
Figure 2.2: (, ) = () · cos()
19
Linear Programming
The constraints and objective function are linear expressions on continuous decision variables.
= min
s.t.
≥ ,
≥ 0
Figure 2.3: Vertices and simplex path [2]
20
Mixed-Integer Programming
The constraints and objective function are linear expressions on continuous or discrete decision variables.
= min +
s.t.
+ ≥ ,
≥ 0, ∈ R
≥ 0, ∈ Z
If all variables are binary ( ∈ {0, 1}), we have Binary Programming.
If all variables are integer ( ∈ {0, 1}), we have Integer Programming.
Figure 2.4: IP polytope with LP relaxation. Reprinted from Wikimedia Commons, 2010
21
Modelling and solving problems computationally
There are many linear programming solvers available both commercially and free for academic use.
Examples of commercial solvers (also with free academic licences):
CPLEX,
Gurobi,
FICO Xpress
Examples of open source solvers:
Cbc,
GLPK,
The implementation of models is often made with mathematical programming languages or packages such as AMPL,
Julia/JuMP, Gurobipy. Common mathematical software, such as MATLAB also have packages for solving linear programs.
Microsoft Excel Solver also solves linear (integer) and nonlinear optimization problems.
22
Modelling in Linear Programming
23
The company Dovetail produces two kinds of matches: long and short ones. The company makes a profit of 3 (x$1,000)
for every 100,000 boxes of long matches, and 2 (x$1,000) for every 100,000 boxes of short matches. The company has
one machine that can produce both long and short matches, with a total of at most 9 (x100,000) boxes per year. For
the production of matches the company needs wood and boxes: three cubic meters of wood are needed for 100,000
boxes of long matches, and one cubic meter of wood is needed for 100,000 boxes of short matches. The company has
18 cubic meters of wood available for the next year. Moreover, Dovetail has 7 (x100,000) boxes for long matches, and
6 (x100,000) for short matches available at its production site. The company wants to maximize its profit in the next
year. It is assumed that Dovetail can sell any amount it produces.
Example: The Dovetail problem [3]
Variables:
1 ≥ 0: number of 100,000 boxes of long matches produced,
2 ≥ 0: number of 100,000 boxes of short matches produced.
Model:
Let be the maximum profit the company can obtain given such technological and resource constraints.
= max 31 + 22 (2.1)
s.t.
1 + 2 ≤ 9, (2.2)
31 + 2 ≤ 18, (2.3)
1 ≤ 7, (2.4)
2 ≤ 6, (2.5)
1, 2 ≥ 0.
24
Adelaide has two water catchment storage facilities. Storage 1 can store up to 400 megalitres per day. Storage 2 can
store up to 500 megalitres per day. Three secondary dams are supplied from these two facilities: Barossa needs at least
300 megalitres per day, Happy Valley needs at least 200 megalitres per day and Kangaroo Creek needs at least 400
megalitres per day
The distances between storage facilities and the secondary dams are (in kilometres).
Dam 1 Dam 2 Dam 3
Storage Facility 1 75 40 85
Storage Facility 2 20 55 75
Formulate a linear program that minimises the total transportation distances to meet the demands of the secondary
dams, such that capacities of the storage facilities are not violated.
A transportation problem
- quantity transported from storage to damn .
min 7511 + 4012 + 8513 + 2021 + 5522 + 7523
such that
11 + 12 + 13 ≤ 400
21 + 22 + 23 ≤ 500
11 + 21 ≥ 300
12 + 22 ≥ 200
13 + 23 ≥ 400
11, 12, 13, 21, 22, 23 ≥ 0.
25
import gurobipy as gp
from gurobipy import GRB
#DATA
Storages = ["Storage 1","Storage 2"]
Damns = ["Baroosa","Kangaroo Creek", "Happy Valley"]
Cap = {
"Storage 1": 400,
"Storage 2": 500}
Dem = {
"Baroosa": 300,
"Kangaroo Creek": 400,
"Happy Valley": 200}
dist ={
("Storage 1", "Baroosa"): 75,
("Storage 1", "Happy Valley"): 40,
("Storage 1", "Kangaroo Creek"): 85,
("Storage 2", "Baroosa"): 20,
("Storage 2", "Happy Valley"): 55,
("Storage 2", "Kangaroo Creek"): 75,
}
#MODEL
m = gp.Model("transp")
x = m.addVars(Storages,Damns, name = ’x’)
demCons = m.addConstrs( gp.quicksum( x[s,d] for s in Storages) >= Dem[d] for d in Damns )
SupCons = m.addConstrs( gp.quicksum( x[s,d] for d in Damns) <= Cap[s] for s in Storages)
m.setObjective( gp.quicksum( dist[s,d]*x[s,d] for s in Storages for d in Damns ) )
# Analysis
m.optimize()
print(’SOLUTION:’)
print(’ Cost: ’, m.objVal)
for v in m.getVars():
if v.x > 1e-6:
print(" ", v.varName, v.x)
Implementation
26
The classical transportation problem
Data:
- set of origins,
- capacity of origin ∈ .
- set of destinations,
- demand of destination ∈ ,
- distance between origin ∈ and destination ∈ ,
Variables:
- quantity transported between ∈ and ∈ .
Model:
import gurobipy as gp
from gurobipy import GRB
import random
random.seed(1)
#DATA
n = 10 #number of ’storages’
m = 50 #number of ’damns’
Storages = range(n)
Damns = range(m)
cap = {}
for s in Storages:
cap[s] = random.randint(100,1000)
dem = {}
for d in Damns:
dem[d] = random.randint(10,100)
dist = {}
for s in Storages:
for d in Damns:
dist[s,d] = random.randint(10,100)
#MODEL
m = gp.Model("transp")
x = m.addVars(Storages,Damns, name = ’x’)
demCons = m.addConstrs( gp.quicksum( x[s,d] for s in Storages) >= dem[d] for d in Damns )
supCons = m.addConstrs( gp.quicksum( x[s,d] for d in Damns) <= cap[s] for s in Storages)
m.setObjective( gp.quicksum( dist[s,d]*x[s,d] for s in Storages for d in Damns ) )
m.optimize()
print(’SOLUTION:’)
print(’ Cost: ’, m.objVal)
Implementation
28
A steel company must decide how to allocate next week’s time on a rolling mill, which is a machine that takes slabs
of steel and can produce either bands (at 200 tonnes/hour) or coils (at 140 tonnes/hour). Bands and coils can be sold
for $25/tonne and $30/tonne respectively. Based on currently booked orders, the company must produce at least 6000
tonnes of bands and 4000 tonnes of coils. Given that there are 40 hours of production time this week, how many tonnes
of bands and coils should be produced to yield the greatest revenue?
Production planning:
- number of products produced, ∈ {bands, coils}
max 25 + 30
such that