代写MAST 20018、代写Python/Java编程

日期：2022-10-23 12:08

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