微信客服：xiaoxionga100
微信客服：ITCS521
运筹学代写-MAT021
时间：2021-02-14
MAT021
Foundations of Operational Research & Analytics
Week 4
Lecturer: Dr Andrei Gagarin∗
School of Mathematics, Cardiff University
∗Room M/1.29
e-mail: gagarina(at)cardiff.ac.uk
1
• Lectures: Wed, 9–11am and 12–2pm
(on-line, Zoom link:
https://cardiff.zoom.us/j/2153958978?pwd=cG5rbmcxd3plVkR1bksrVUZxVnYzdz09
Meeting ID: 215 395 8978
Password: 231456 )
• Face2face sessions:
1 hour on Thu, Fri (in-class), Mon (on-line equivalent)
• Exercise/practice and former lab questions posted on
Learning Central weekly
(software usage/programming components are optional)
• Final exam: 70% (2 hours)
• Background reading and resources list:
– Winston, W.L. 2004, Operations Research: Applications and Al-
gorithms, 4th ed., Brooks/Cole.
– Hillier, F.S. 2015, Introduction to Operations Research, 10th
ed., McGraw-Hill.
– Winston, W.L., & Venkataramanan, M. 2003, Introduction to
mathematical programming, 4th ed., Thomson-Brooks/Cole.
– Maths Support Service (https://intranet.cardiff.ac.uk/students/study/study-skills)
2
Contents
1 Linear programming (LP) models 4
1.1 Modelling a real-life problem as an LP problem: example . 5
1.2 Solving an LP problem . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Graphically (in 2-variables) . . . . . . . . . . . . . 6
1.2.2 Algorithmically/analytically (the Simplex Method) 8
1.3 LP problem in the standard form . . . . . . . . . . . . . . 9
1.4 Solutions to systems of linear equations vs the LP problem 11
2 The Simplex Method 12
2.1 Pre-multiplication matrix (P ) . . . . . . . . . . . . . . . . 13
2.2 Finding an initial feasible set of basic variables . . . . . . . 15
2.2.1 Artificial variables and the Big-M method . . . . . 15
2.2.2 Two-Phase method . . . . . . . . . . . . . . . . . . 16
3
1 Linear programming (LP) models
Linear programming (LP) modelling consists in formulating a real-life
optimisation problem as a problem of maximising or minimising a linear
objective function satisfying a set of linear constraints. The function and
constraints are expressed in terms of decision variables (xi), which values
we need to find.
• The decision variables must be non-negative, i.e. xi ≥ 0.
• The criterion for selecting the best values of these variables can be
expressed as a linear (objective) function of the variables, i.e. a
function of the form c1x1+c2x2+· · ·+cnxn, which is a linear function
of the decision variables xi with (“cost” or “weight”) coefficients ci
(i = 1, . . . , n). This function is to be minimised or maximised.
• Any limitations/restrictions/constraints can be expressed as a set of
linear equations or inequalities of the form:
a1x1 + a2x2 + · · ·+ anxn = b,
a1x1 + a2x2 + · · ·+ anxn ≤ b,
a1x1 + a2x2 + · · ·+ anxn ≥ b.
The corresponding problem is called a linear programming (LP) problem.
Some typical real-life problems which maybe formulated as LP’s:
• A manufacturer wants to decide how to produce a set of items to
maximise profit, subject to a limited set of resources.
• A financial analyst would like to decide on his/her investment port-
folio to maximise its return.
• A company would like to decide how much product should be shipped
from each of a set of warehouses to their customers to satisfy cus-
tomer demand and minimise delivery costs.
4
1.1 Modelling a real-life problem as an LP problem: example
A small firm produces a number of paints. Three raw materials are used
to make two different paint products – matt and silk. The amount of
raw materials (in tons) needed to make each unit of paint products is as
follows:
Product Material α Material β Material γ
Matt 2/5 0 3/5
Silk 1/2 1/5 3/10
Currently they have available: 20 tons of Material α, 5 tons of Mate-
rial β, and 21 tons of Material γ. The firm estimates that they will make
£40 per ton of Matt and £30 per ton of Silk paint. Given their limited
resources, the firm would like to decide how much of each product should
be produced in order to maximise their profit.
(try to guess the answer... how to solve the problem?)
How can we formulate this problem as a mathematical problem?
We can model this problem as a linear programming problem in the
following way:
Decision variables:
M − quantity of Matt paint;
S − quantity of Silk paint.
Objective function and constraints:
maximise: 40M + 30S −→ max
subject to (constraints): 25M +
1
2S ≤ 20
1
5S ≤ 5
3
5M +
3
10S ≤ 21
M ≥ 0, S ≥ 0
Note: z(M,S) = 40M+30S is a linear objective function of two variables
M and S.
5
1.2 Solving an LP problem
We can solve the problem above graphically or using the Simplex Method.
1.2.1 Graphically (in 2-variables)
To solve graphically: we can deal only with problems in two decision
variables. Simply draw the constraints in the Cartesian plane and identify
the feasible region – the area where all constraints are satisfied. Note that
only the positive quadrant needs to be considered. Once we have drawn
the feasible region, calculate the cost (objective) function at each vertex
(corner) that defines the feasible region. Identify a vertex that optimises
the objective function – this is the optimal solution.
Figure 1: Graphic solution to the LP problem.
6
Exercise: Goldilocks needs to find at least 16 lb of gold and at least
18 lb of silver to pay her monthly rent at the bears cottage. There are
two mines in which Goldilocks can find gold and silver. Each day that
Goldilocks spends in Mine α, she finds 2 lb of gold and 2 lb of silver. Each
day that Goldilocks spends in Mine β, she finds 1 lb of gold and 3 lb of
silver. Formulate an LP problem to help Goldilocks to meet her require-
ments while spending as little time as possible in the mines. Graphically
solve the LP.
In general, a feasible region defined by a set of linear constraints for an
LP problem geometrically is going to be a (convex) polytope in a multi-
dimensional vector space. For example, Platonic solids are polyhedra in
R3 (bounded regions):
Figure 2: Examples of polytopes in R3.
7
1.2.2 Algorithmically/analytically (the Simplex Method)
Rewrite constraints (using slack or surplus/excess variables) as equalities:
maximise: z = 40M + 30S
subject to (constraints): 25M +
1
2S + s1 = 20
1
5S + s2 = 5
3
5M +
3
10S + s3 = 21
M,S ≥ 0, s1, s2, s3 ≥ 0
Here the variables s1, s2, s3 represent the slack in each constraint.
Write the initial Simplex tableau:
Basis z M S s1 s2 s3 Solution
z 1 -40 -30 0 0 0 0
s1 0 2/5 1/2 1 0 0 20
s2 0 0 1/5 0 1 0 5
s3 0 3/5* 3/10 0 0 1 21
Note: at this point we have s1 = 20, s2 = 5, s3 = 21; variables M and
S are equal to 0 and called non-basic; the slack variables are currently
basic variables and ≥ 0. A column for a basic variable consists of exactly
one 1, and all the other values in such a column are equal to 0. For
non-basic variables, the columns consist of some sets of numbers. The
value in the upper right corner is equal to the objective function value
(z). Notice that when maximising, the objective function is rewritten as
z − 40M − 30S = 0 −→ max, i.e. the right-hand side is negated, e.g.
30M − 20S would be entered as −30M + 20S into the Simplex tableaux.
Then we follow the algorithm below to solve the problem. We choose
the M -column as it has the largest negative value in the objective func-
tion (upper) row. The pivot has to be > 0, so could be here in either
Row 1 or Row 3. We calculate the corresponding ratios
r1 =
20
(2/5) = 50 and r3 =
21
(3/5) = 35,
and choose the least of them, i.e. corresponding here to Row 3. There-
fore, M is an entering variable, and s3 is a leaving variable at this point.
8
Basis z M S s1 s2 s3 Solution
z 1 0 -10 0 0 200/3 1400
s1 0 0 3/10* 1 0 -2/3 6
s2 0 0 1/5 0 1 0 5
M 0 1 1/2 0 0 5/3 35
Now we have M = 35, so the new objective value z = 1400, s1 = 6
and s2 = 5. Constraint 3 is now tight as there is no slack, i.e. s3 = 0. We
choose the next pivot for the S-column according to the ratios
r1 =
6
(3/10) = 20, r2 =
5
(1/5) = 25, and r3 =
35
(1/2) = 70.
Therefore, S is an entering variable, and s1 is a leaving variable now.
Basis z M S s1 s2 s3 Solution
z 1 0 0 100/3 0 400/9 1600
S 0 0 1 10/3 0 -20/9 20
s2 0 0 0 -2/3 1 4/9 1
M 0 1 0 -5/3 0 25/9 25
This is optimal as there are no negative values in the upper row (z-
row). Decision variables values: M = 25 and S = 20; corresponding
objective function value: z∗ = 1600. Constraint 2 is slack (as s2 = 1),
and the other two constraints are tight (s1 = s3 = 0).
1.3 LP problem in the standard form
The Simplex Method is a very efficient algorithm/method for finding an
optimal solution to an LP problem. However, before we can use it, the
LP problem must be expressed in/converted to the standard form:
max z = c1x1 + c2x2 + . . .+ cnxn
s.t. a11x1 + a12x2 + . . .+ a1nxn = b1
a21x1 + a22x2 + . . .+ a2nxn = b2
...
am1x1 + am2x2 + . . .+ amnxn = bm
x1, x2, . . . , xn ≥ 0,
where the constants b1, . . . , bm are all non-negative, i.e. b1, b2, . . . , bm ≥ 0.
9
Often the standard form is written in the vector-matrix form:
max z = c¯ x¯
s.t. Ax¯ = b¯
x¯ ≥ 0, (b¯ ≥ 0)
where c¯ = (c1, . . . , cn),
x¯ =
x1
x2
...
xn
, b¯ =
b1
b2
...
bm
, A =
a11 a12 . . . a1n
a21 a22 . . . a2n
...
... . . .
...
am1 am2 . . . amn
.
Converting an LP problem into the standard form:
• If the problem is a minimisation problem, turn it into a maximisation
problem by multiplying the objective function by −1:
e.g., min z = 2x1 − 3x2 becomes max z′ = −2x1 + 3x2 (= −z).
• Less-than-or-equal-to (≤) inequalities are turned into equalities by
introducing slack variables ,
e.g., 2x1 + 5x2 ≤ 7 becomes 2x1 + 5x2 + s1 = 7, where s1 ≥ 0.
• Greater-than-or-equal-to (≥) inequalities are turned into equalities
by introducting surplus/excess variables ,
e.g., 4x1 − 6x2 ≥ 8 becomes 4x1 − 6x2 − s2 = 8, where s2 ≥ 0.
Question: what to do when some constraints have bi < 0? For example,
what if 2x1 − 7x2 + x3 ≥ −17?
Constraints with a negative right-hand side are turned into the standard
form by multiplying both sides by −1, e.g.
3x1 − 7x2 = −5 becomes −3x1 + 7x2 = 5,
3x1 − 7x2 ≤ −9 becomes −3x1 + 7x2 ≥ 9, etc.
10
Example: Transform the following LP problem into the standard form:
min z = −50x1 + 100x2
s.t. 7x1 + 2x2 ≥ 28
2x1 + 12x2 ≤ 24
x1, x2 ≥ 0.
We have
max z′ = 50x1 − 100x2
s.t. 7x1 + 2x2 − s1 = 28
2x1 + 12x2 + s2 = 24
x1, x2, s1, s2 ≥ 0.
1.4 Solutions to systems of linear equations vs the LP problem
• Consider a system of independent linear equations, Ax¯ = b¯, with m
equations and n variables (m ≤ n).
• We can assume m < n (if m = n and detA 6= 0, then there is a
unique solution x¯ = A−1b¯).
• If we set (n−m) of the variables equal to 0, then (normally) we can
find a solution for the m equations with m unknowns.
• We call such solutions basic solutions .
• Not all of the basic solutions satisfy all the LP problem constraints
or non-negativity constraints. Those that do not meet these require-
ments are infeasible solutions. The ones that do meet the restrictions
are called basic feasible solutions .
• Basic feasible solutions correspond precisely to the extreme points
(corners or vertices) of the feasible region.
• Therefore, one of the basic solutions is an optimal solution.
• The variables that are not set to 0 are the basic variables .
• The variables that are set to 0 are the non-basic variables .
11
• The number of basic solutions is just the number of ways we can
choose n−m variables from the set of n variables.
• This number is given by(
n
n−m
)
=
(
n
m
)
=
n!
m!(n−m)!
• Two basic solutions are adjacent if all but one of their basic variables
are the same.
• The Simplex Method starts by picking a basic solution, and then
changes it to an adjacent basic solution only if the objective function
is improved (or stays the same).
• Doing this repeatedly will lead to an optimal solution.
2 The Simplex Method
First, we are going to focus on the simplex method to solve the following
LP problem type (assume b1, b2, . . . , bm are all non-negative):
maximise z = c1x1 + c2x2 + . . .+ cnxn
subject to the constraints: a11x1 + a12x2 + . . .+ a1nxn ≤ b1
a21x1 + a22x2 + . . .+ a2nxn ≤ b2
...
am1x1 + am2x2 + . . .+ amnxn ≤ bm
x1, x2, . . . , xn ≥ 0.
To solve such a problem, we can use the Simplex Method:
Step One - Introduce slack variables si ≥ 0 to convert the inequalities
into equalities.
Step Two - Enter the equations into the initial tableau.
Also, enter the objective function z into the tableau (as negative when
maximising, and positive when minimising).
12
Step Three - Locate the most negative number in the upper (objec-
tive function) row (excluding the last column). The column in which this
value appears is called the work or pivot column.
If there are no negative values, then the solution is optimal (stop and
return the solution).
Step Four - Divide the right-hand column values by the correspond-
ing work column values and choose the row with the smallest positive
ratio. The element in this row and the work column is called the pivot.
Step Five - (Row reduction) Divide the elements of the pivot row by
the pivot value and enter this new row in the next tableau.
Step Six - (Row reduction) Reduce all remaining elements of the pivot
column to zero using suitable multiples of the pivot row.
Return to Step Three.
2.1 Pre-multiplication matrix (P )
When we are carrying out the Simplex Method, we are actually multiply-
ing by a matrix, which is a product of elementary matrices corresponding
to the elementary row operations used. In particular, this applies to the
constraints part of the tableau. This matrix is stored in the columns
that make up the identity matrix in the initial tableau. We can find the
matrix P by simply extracting the columns from the final tableau that
correspond to the “identity matrix” part of the initial tableau.
In the paint problem example, in the initial tableau, the identity ma-
trix is made up of columns corresponding to the slack variables s1, s2, s3.
We can multiply any column in the initial (constraints) matrix [A | b¯] by
the pre-multiplication matrix P and will get the corresponding column
in the final tableau. For example, consider the constants column (b¯):
13
10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
205
21
=
201
25
This can be applied to any column of [A | b¯], e.g., consider the column
corresponding to the variable S: 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
1/21/5
3/10
=
10
0
Now, what if the right-hand side values in the constraints (vector b¯)
change from [20, 5, 21] to [20, 10, 25]? 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
2010
25
=
100/970/9
325/9
Therefore, the current solution (procedure and variables) is still optimal,
but the (optimal) values of the variables has now changed:
S = 100/9 and M = 325/9 (s2 = 70/9).
The (optimal) objective function value also have changed - we can sub-
stitute the new values into the objective function to obtain:
z = 40(325/9) + 30(100/9) = 16, 000/9.
Now, what if the right-hand side values in the constraints (vector b¯)
change from [20, 5, 21] to [25, 10, 10]? 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
2010
10
=
25/9−20/9
−125/9
Therefore, the current solution is now infeasible. This doesn’t mean there
is no feasible solutions to this problem, just that the current solution is
not feasible! (i.e. it doesn’t satisfy the constraints)
14
2.2 Finding an initial feasible set of basic variables
• If all constraints in an LP problem are of the type “at most” (≤) and
b¯ ≥ 0, then the slack variables form an initial feasible set of basic
variables.
• If some of the constraints are of the type “equal” (=) or “at least”
(≥), it can be hard to find an initial feasible set of basic variables to
start the Simplex Method.
2.2.1 Artificial variables and the Big-M method
• Consider the following LP problem in standard form:
max z = 2x1 − 3x2 + 9x3
s.t. x1 − x2 + 4x3 = 10
−7x1 + 3x2 + 5x3 − s1 = 2
x1, x2, x3, s1 ≥ 0.
• It is not easy to find an initial feasible set of basic variables.
• We can introduce artificial variables a1 and a2, a very large positive
number M , and consider the corresponding problem:
max z = 2x1 − 3x2 + 9x3 −Ma1 −Ma2
s.t. x1 − x2 + 4x3 + a1 = 10
−7x1 + 3x2 + 5x3 − s1 + a2 = 2
x1, x2, x3, s1, a1, a2 ≥ 0,
• Because M is very large, any increase in a1 or a2 decreases z consid-
erably.
• Therefore, if there is any feasible solution with a1 = a2 = 0, the
optimal solution will have a1 = a2 = 0.
• An optimal solution with a1 = a2 = 0 will also give a basic feasible
solution for the original problem.
15
• If the optimal solution to the problem with artificial variables has
a1 > 0 or a2 > 0, the original problem has no feasible solution.
• This is so called the Big-M method.
• The Big-M Method is not always practical (poorly suited for com-
puter implementation).
• M must be significantly larger than any other coefficient.
• This may lead to large arithmetic (round-off) errors during operation
of the Simplex Method.
• To discover the original problem has no feasible solution, we had to
solve a larger LP problem (with additional artificial variables)
2.2.2 Two-Phase method
• This method has two phases (artificial variables are introduced for
constraints as before).
• First phase: Solve a minimisation LP problem, whose objective func-
tion is the sum of artificial variables, and whose constraints are the
constraints of the initial LP problem (artificial variables included).
As before, if an optimal solution contains a positive artificial vari-
able, then the initial problem is infeasible. Otherwise, we proceed to
the next phase.
• Second phase: Solve the initial LP problem using the optimal solu-
tion from the first phase as an initial basic solution.
Example:
max z = x1 + 3x2
s.t. 2x1 − x2 ≤ −1
x1 + x2 = 3
x1, x2 ≥ 0.
16
In the first phase, we solve
max za = −a1 − a2
s.t. −2x1 + x2 − s1 + a1 = 1
x1 + x2 + a2 = 3
x1, x2, s1, a1, a2 ≥ 0,
the initial tableau for this phase is:
Basis za x1 x2 s1 a1 a2 Solution
za 1 0 0 0 1 1 0
a1 0 -2 1 -1 1 0 1
a2 0 1 1 0 0 1 3
(can we start the Simplex Method?)
• We perform row operations to change the coefficients of basic vari-
ables a1 and a2 in the z-row to 0 (a necessary condition to start the
Simplex Method with basic variables a1, a2).
• To do that, we add the a1- and a2-rows each multiplied by −1 to the
z-row:
Basis za x1 x2 s1 a1 a2 Solution
za 1 1 -2 1 0 0 -4
a1 0 -2 1 -1 1 0 1
a2 0 1 1 0 0 1 3
• After two iterations of the Simplex Method we get the following final
tableau:
Basis za x1 x2 s1 a1 a2 Solution
za 1 0 0 0 1 1 0
x2 0 0 1 -1/3 1/3 2/3 7/3
x1 0 1 0 1/3 -1/3 1/3 2/3
• In this solution, the artificial variables a1 and a2 are non-basic, i.e.
both equal to 0.
• This indicates that the original problem has a feasible solution.
17
• We use the first phase solution to construct an initial basic solution
for the original problem (the second phase begins).
• We delete the columns of artificial variables ai (i = 1, . . . ,m) and
replace the objective function row with that of the original problem:
Basis z x1 x2 s1 Solution
z 1 -1 -3 0 0
x2 0 0 1 -1/3 7/3
x1 0 1 0 1/3 2/3
(a re-calculated objective function value? not yet!)
• We need to create zeroes in the objective function row in place of
−1 and −3 since x1 and x2 are basic (re-calculations done here!)
• To do this, add the x1-row to the z-row and the x2-row multiplied
by 3 to the z-row (start the Simplex Method after)
Basis z x1 x2 s1 Solution
z 1 0 0 -2/3 23/3
x2 0 0 1 -1/3 7/3
x1 0 1 0 1/3 2/3
• Applying one iteration of the Simplex Method, we get:
Basis z x1 x2 s1 Solution
z 1 2 0 0 9
x2 0 1 1 0 3
s1 0 3 0 1 2
• The optimal solution is x1 = 0, x2 = 3, z∗ = 9.
• If one of the artificial variables remains positive in the optimal so-
lution of the transformed problem (first phase), then the original
problem is infeasible.
• It may take some time to solve the transformed problem only to
discover that the original problem is infeasible.
18
• However this can still give us useful information.
• If a real world problem is infeasible, this usually indicates an error
in formulation of one of the constraints.
• By observing which of the artificial variables remain positive, we can
see which constraints are likely to be wrongly formulated.
• This remark applies equally to the Big-M Method.
19
学霸联盟
Foundations of Operational Research & Analytics
Week 4
Lecturer: Dr Andrei Gagarin∗
School of Mathematics, Cardiff University
∗Room M/1.29
e-mail: gagarina(at)cardiff.ac.uk
1
• Lectures: Wed, 9–11am and 12–2pm
(on-line, Zoom link:
https://cardiff.zoom.us/j/2153958978?pwd=cG5rbmcxd3plVkR1bksrVUZxVnYzdz09
Meeting ID: 215 395 8978
Password: 231456 )
• Face2face sessions:
1 hour on Thu, Fri (in-class), Mon (on-line equivalent)
• Exercise/practice and former lab questions posted on
Learning Central weekly
(software usage/programming components are optional)
• Final exam: 70% (2 hours)
• Background reading and resources list:
– Winston, W.L. 2004, Operations Research: Applications and Al-
gorithms, 4th ed., Brooks/Cole.
– Hillier, F.S. 2015, Introduction to Operations Research, 10th
ed., McGraw-Hill.
– Winston, W.L., & Venkataramanan, M. 2003, Introduction to
mathematical programming, 4th ed., Thomson-Brooks/Cole.
– Maths Support Service (https://intranet.cardiff.ac.uk/students/study/study-skills)
2
Contents
1 Linear programming (LP) models 4
1.1 Modelling a real-life problem as an LP problem: example . 5
1.2 Solving an LP problem . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Graphically (in 2-variables) . . . . . . . . . . . . . 6
1.2.2 Algorithmically/analytically (the Simplex Method) 8
1.3 LP problem in the standard form . . . . . . . . . . . . . . 9
1.4 Solutions to systems of linear equations vs the LP problem 11
2 The Simplex Method 12
2.1 Pre-multiplication matrix (P ) . . . . . . . . . . . . . . . . 13
2.2 Finding an initial feasible set of basic variables . . . . . . . 15
2.2.1 Artificial variables and the Big-M method . . . . . 15
2.2.2 Two-Phase method . . . . . . . . . . . . . . . . . . 16
3
1 Linear programming (LP) models
Linear programming (LP) modelling consists in formulating a real-life
optimisation problem as a problem of maximising or minimising a linear
objective function satisfying a set of linear constraints. The function and
constraints are expressed in terms of decision variables (xi), which values
we need to find.
• The decision variables must be non-negative, i.e. xi ≥ 0.
• The criterion for selecting the best values of these variables can be
expressed as a linear (objective) function of the variables, i.e. a
function of the form c1x1+c2x2+· · ·+cnxn, which is a linear function
of the decision variables xi with (“cost” or “weight”) coefficients ci
(i = 1, . . . , n). This function is to be minimised or maximised.
• Any limitations/restrictions/constraints can be expressed as a set of
linear equations or inequalities of the form:
a1x1 + a2x2 + · · ·+ anxn = b,
a1x1 + a2x2 + · · ·+ anxn ≤ b,
a1x1 + a2x2 + · · ·+ anxn ≥ b.
The corresponding problem is called a linear programming (LP) problem.
Some typical real-life problems which maybe formulated as LP’s:
• A manufacturer wants to decide how to produce a set of items to
maximise profit, subject to a limited set of resources.
• A financial analyst would like to decide on his/her investment port-
folio to maximise its return.
• A company would like to decide how much product should be shipped
from each of a set of warehouses to their customers to satisfy cus-
tomer demand and minimise delivery costs.
4
1.1 Modelling a real-life problem as an LP problem: example
A small firm produces a number of paints. Three raw materials are used
to make two different paint products – matt and silk. The amount of
raw materials (in tons) needed to make each unit of paint products is as
follows:
Product Material α Material β Material γ
Matt 2/5 0 3/5
Silk 1/2 1/5 3/10
Currently they have available: 20 tons of Material α, 5 tons of Mate-
rial β, and 21 tons of Material γ. The firm estimates that they will make
£40 per ton of Matt and £30 per ton of Silk paint. Given their limited
resources, the firm would like to decide how much of each product should
be produced in order to maximise their profit.
(try to guess the answer... how to solve the problem?)
How can we formulate this problem as a mathematical problem?
We can model this problem as a linear programming problem in the
following way:
Decision variables:
M − quantity of Matt paint;
S − quantity of Silk paint.
Objective function and constraints:
maximise: 40M + 30S −→ max
subject to (constraints): 25M +
1
2S ≤ 20
1
5S ≤ 5
3
5M +
3
10S ≤ 21
M ≥ 0, S ≥ 0
Note: z(M,S) = 40M+30S is a linear objective function of two variables
M and S.
5
1.2 Solving an LP problem
We can solve the problem above graphically or using the Simplex Method.
1.2.1 Graphically (in 2-variables)
To solve graphically: we can deal only with problems in two decision
variables. Simply draw the constraints in the Cartesian plane and identify
the feasible region – the area where all constraints are satisfied. Note that
only the positive quadrant needs to be considered. Once we have drawn
the feasible region, calculate the cost (objective) function at each vertex
(corner) that defines the feasible region. Identify a vertex that optimises
the objective function – this is the optimal solution.
Figure 1: Graphic solution to the LP problem.
6
Exercise: Goldilocks needs to find at least 16 lb of gold and at least
18 lb of silver to pay her monthly rent at the bears cottage. There are
two mines in which Goldilocks can find gold and silver. Each day that
Goldilocks spends in Mine α, she finds 2 lb of gold and 2 lb of silver. Each
day that Goldilocks spends in Mine β, she finds 1 lb of gold and 3 lb of
silver. Formulate an LP problem to help Goldilocks to meet her require-
ments while spending as little time as possible in the mines. Graphically
solve the LP.
In general, a feasible region defined by a set of linear constraints for an
LP problem geometrically is going to be a (convex) polytope in a multi-
dimensional vector space. For example, Platonic solids are polyhedra in
R3 (bounded regions):
Figure 2: Examples of polytopes in R3.
7
1.2.2 Algorithmically/analytically (the Simplex Method)
Rewrite constraints (using slack or surplus/excess variables) as equalities:
maximise: z = 40M + 30S
subject to (constraints): 25M +
1
2S + s1 = 20
1
5S + s2 = 5
3
5M +
3
10S + s3 = 21
M,S ≥ 0, s1, s2, s3 ≥ 0
Here the variables s1, s2, s3 represent the slack in each constraint.
Write the initial Simplex tableau:
Basis z M S s1 s2 s3 Solution
z 1 -40 -30 0 0 0 0
s1 0 2/5 1/2 1 0 0 20
s2 0 0 1/5 0 1 0 5
s3 0 3/5* 3/10 0 0 1 21
Note: at this point we have s1 = 20, s2 = 5, s3 = 21; variables M and
S are equal to 0 and called non-basic; the slack variables are currently
basic variables and ≥ 0. A column for a basic variable consists of exactly
one 1, and all the other values in such a column are equal to 0. For
non-basic variables, the columns consist of some sets of numbers. The
value in the upper right corner is equal to the objective function value
(z). Notice that when maximising, the objective function is rewritten as
z − 40M − 30S = 0 −→ max, i.e. the right-hand side is negated, e.g.
30M − 20S would be entered as −30M + 20S into the Simplex tableaux.
Then we follow the algorithm below to solve the problem. We choose
the M -column as it has the largest negative value in the objective func-
tion (upper) row. The pivot has to be > 0, so could be here in either
Row 1 or Row 3. We calculate the corresponding ratios
r1 =
20
(2/5) = 50 and r3 =
21
(3/5) = 35,
and choose the least of them, i.e. corresponding here to Row 3. There-
fore, M is an entering variable, and s3 is a leaving variable at this point.
8
Basis z M S s1 s2 s3 Solution
z 1 0 -10 0 0 200/3 1400
s1 0 0 3/10* 1 0 -2/3 6
s2 0 0 1/5 0 1 0 5
M 0 1 1/2 0 0 5/3 35
Now we have M = 35, so the new objective value z = 1400, s1 = 6
and s2 = 5. Constraint 3 is now tight as there is no slack, i.e. s3 = 0. We
choose the next pivot for the S-column according to the ratios
r1 =
6
(3/10) = 20, r2 =
5
(1/5) = 25, and r3 =
35
(1/2) = 70.
Therefore, S is an entering variable, and s1 is a leaving variable now.
Basis z M S s1 s2 s3 Solution
z 1 0 0 100/3 0 400/9 1600
S 0 0 1 10/3 0 -20/9 20
s2 0 0 0 -2/3 1 4/9 1
M 0 1 0 -5/3 0 25/9 25
This is optimal as there are no negative values in the upper row (z-
row). Decision variables values: M = 25 and S = 20; corresponding
objective function value: z∗ = 1600. Constraint 2 is slack (as s2 = 1),
and the other two constraints are tight (s1 = s3 = 0).
1.3 LP problem in the standard form
The Simplex Method is a very efficient algorithm/method for finding an
optimal solution to an LP problem. However, before we can use it, the
LP problem must be expressed in/converted to the standard form:
max z = c1x1 + c2x2 + . . .+ cnxn
s.t. a11x1 + a12x2 + . . .+ a1nxn = b1
a21x1 + a22x2 + . . .+ a2nxn = b2
...
am1x1 + am2x2 + . . .+ amnxn = bm
x1, x2, . . . , xn ≥ 0,
where the constants b1, . . . , bm are all non-negative, i.e. b1, b2, . . . , bm ≥ 0.
9
Often the standard form is written in the vector-matrix form:
max z = c¯ x¯
s.t. Ax¯ = b¯
x¯ ≥ 0, (b¯ ≥ 0)
where c¯ = (c1, . . . , cn),
x¯ =
x1
x2
...
xn
, b¯ =
b1
b2
...
bm
, A =
a11 a12 . . . a1n
a21 a22 . . . a2n
...
... . . .
...
am1 am2 . . . amn
.
Converting an LP problem into the standard form:
• If the problem is a minimisation problem, turn it into a maximisation
problem by multiplying the objective function by −1:
e.g., min z = 2x1 − 3x2 becomes max z′ = −2x1 + 3x2 (= −z).
• Less-than-or-equal-to (≤) inequalities are turned into equalities by
introducing slack variables ,
e.g., 2x1 + 5x2 ≤ 7 becomes 2x1 + 5x2 + s1 = 7, where s1 ≥ 0.
• Greater-than-or-equal-to (≥) inequalities are turned into equalities
by introducting surplus/excess variables ,
e.g., 4x1 − 6x2 ≥ 8 becomes 4x1 − 6x2 − s2 = 8, where s2 ≥ 0.
Question: what to do when some constraints have bi < 0? For example,
what if 2x1 − 7x2 + x3 ≥ −17?
Constraints with a negative right-hand side are turned into the standard
form by multiplying both sides by −1, e.g.
3x1 − 7x2 = −5 becomes −3x1 + 7x2 = 5,
3x1 − 7x2 ≤ −9 becomes −3x1 + 7x2 ≥ 9, etc.
10
Example: Transform the following LP problem into the standard form:
min z = −50x1 + 100x2
s.t. 7x1 + 2x2 ≥ 28
2x1 + 12x2 ≤ 24
x1, x2 ≥ 0.
We have
max z′ = 50x1 − 100x2
s.t. 7x1 + 2x2 − s1 = 28
2x1 + 12x2 + s2 = 24
x1, x2, s1, s2 ≥ 0.
1.4 Solutions to systems of linear equations vs the LP problem
• Consider a system of independent linear equations, Ax¯ = b¯, with m
equations and n variables (m ≤ n).
• We can assume m < n (if m = n and detA 6= 0, then there is a
unique solution x¯ = A−1b¯).
• If we set (n−m) of the variables equal to 0, then (normally) we can
find a solution for the m equations with m unknowns.
• We call such solutions basic solutions .
• Not all of the basic solutions satisfy all the LP problem constraints
or non-negativity constraints. Those that do not meet these require-
ments are infeasible solutions. The ones that do meet the restrictions
are called basic feasible solutions .
• Basic feasible solutions correspond precisely to the extreme points
(corners or vertices) of the feasible region.
• Therefore, one of the basic solutions is an optimal solution.
• The variables that are not set to 0 are the basic variables .
• The variables that are set to 0 are the non-basic variables .
11
• The number of basic solutions is just the number of ways we can
choose n−m variables from the set of n variables.
• This number is given by(
n
n−m
)
=
(
n
m
)
=
n!
m!(n−m)!
• Two basic solutions are adjacent if all but one of their basic variables
are the same.
• The Simplex Method starts by picking a basic solution, and then
changes it to an adjacent basic solution only if the objective function
is improved (or stays the same).
• Doing this repeatedly will lead to an optimal solution.
2 The Simplex Method
First, we are going to focus on the simplex method to solve the following
LP problem type (assume b1, b2, . . . , bm are all non-negative):
maximise z = c1x1 + c2x2 + . . .+ cnxn
subject to the constraints: a11x1 + a12x2 + . . .+ a1nxn ≤ b1
a21x1 + a22x2 + . . .+ a2nxn ≤ b2
...
am1x1 + am2x2 + . . .+ amnxn ≤ bm
x1, x2, . . . , xn ≥ 0.
To solve such a problem, we can use the Simplex Method:
Step One - Introduce slack variables si ≥ 0 to convert the inequalities
into equalities.
Step Two - Enter the equations into the initial tableau.
Also, enter the objective function z into the tableau (as negative when
maximising, and positive when minimising).
12
Step Three - Locate the most negative number in the upper (objec-
tive function) row (excluding the last column). The column in which this
value appears is called the work or pivot column.
If there are no negative values, then the solution is optimal (stop and
return the solution).
Step Four - Divide the right-hand column values by the correspond-
ing work column values and choose the row with the smallest positive
ratio. The element in this row and the work column is called the pivot.
Step Five - (Row reduction) Divide the elements of the pivot row by
the pivot value and enter this new row in the next tableau.
Step Six - (Row reduction) Reduce all remaining elements of the pivot
column to zero using suitable multiples of the pivot row.
Return to Step Three.
2.1 Pre-multiplication matrix (P )
When we are carrying out the Simplex Method, we are actually multiply-
ing by a matrix, which is a product of elementary matrices corresponding
to the elementary row operations used. In particular, this applies to the
constraints part of the tableau. This matrix is stored in the columns
that make up the identity matrix in the initial tableau. We can find the
matrix P by simply extracting the columns from the final tableau that
correspond to the “identity matrix” part of the initial tableau.
In the paint problem example, in the initial tableau, the identity ma-
trix is made up of columns corresponding to the slack variables s1, s2, s3.
We can multiply any column in the initial (constraints) matrix [A | b¯] by
the pre-multiplication matrix P and will get the corresponding column
in the final tableau. For example, consider the constants column (b¯):
13
10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
205
21
=
201
25
This can be applied to any column of [A | b¯], e.g., consider the column
corresponding to the variable S: 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
1/21/5
3/10
=
10
0
Now, what if the right-hand side values in the constraints (vector b¯)
change from [20, 5, 21] to [20, 10, 25]? 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
2010
25
=
100/970/9
325/9
Therefore, the current solution (procedure and variables) is still optimal,
but the (optimal) values of the variables has now changed:
S = 100/9 and M = 325/9 (s2 = 70/9).
The (optimal) objective function value also have changed - we can sub-
stitute the new values into the objective function to obtain:
z = 40(325/9) + 30(100/9) = 16, 000/9.
Now, what if the right-hand side values in the constraints (vector b¯)
change from [20, 5, 21] to [25, 10, 10]? 10/3 0 −20/9−2/3 1 4/9
−5/3 0 25/9
2010
10
=
25/9−20/9
−125/9
Therefore, the current solution is now infeasible. This doesn’t mean there
is no feasible solutions to this problem, just that the current solution is
not feasible! (i.e. it doesn’t satisfy the constraints)
14
2.2 Finding an initial feasible set of basic variables
• If all constraints in an LP problem are of the type “at most” (≤) and
b¯ ≥ 0, then the slack variables form an initial feasible set of basic
variables.
• If some of the constraints are of the type “equal” (=) or “at least”
(≥), it can be hard to find an initial feasible set of basic variables to
start the Simplex Method.
2.2.1 Artificial variables and the Big-M method
• Consider the following LP problem in standard form:
max z = 2x1 − 3x2 + 9x3
s.t. x1 − x2 + 4x3 = 10
−7x1 + 3x2 + 5x3 − s1 = 2
x1, x2, x3, s1 ≥ 0.
• It is not easy to find an initial feasible set of basic variables.
• We can introduce artificial variables a1 and a2, a very large positive
number M , and consider the corresponding problem:
max z = 2x1 − 3x2 + 9x3 −Ma1 −Ma2
s.t. x1 − x2 + 4x3 + a1 = 10
−7x1 + 3x2 + 5x3 − s1 + a2 = 2
x1, x2, x3, s1, a1, a2 ≥ 0,
• Because M is very large, any increase in a1 or a2 decreases z consid-
erably.
• Therefore, if there is any feasible solution with a1 = a2 = 0, the
optimal solution will have a1 = a2 = 0.
• An optimal solution with a1 = a2 = 0 will also give a basic feasible
solution for the original problem.
15
• If the optimal solution to the problem with artificial variables has
a1 > 0 or a2 > 0, the original problem has no feasible solution.
• This is so called the Big-M method.
• The Big-M Method is not always practical (poorly suited for com-
puter implementation).
• M must be significantly larger than any other coefficient.
• This may lead to large arithmetic (round-off) errors during operation
of the Simplex Method.
• To discover the original problem has no feasible solution, we had to
solve a larger LP problem (with additional artificial variables)
2.2.2 Two-Phase method
• This method has two phases (artificial variables are introduced for
constraints as before).
• First phase: Solve a minimisation LP problem, whose objective func-
tion is the sum of artificial variables, and whose constraints are the
constraints of the initial LP problem (artificial variables included).
As before, if an optimal solution contains a positive artificial vari-
able, then the initial problem is infeasible. Otherwise, we proceed to
the next phase.
• Second phase: Solve the initial LP problem using the optimal solu-
tion from the first phase as an initial basic solution.
Example:
max z = x1 + 3x2
s.t. 2x1 − x2 ≤ −1
x1 + x2 = 3
x1, x2 ≥ 0.
16
In the first phase, we solve
max za = −a1 − a2
s.t. −2x1 + x2 − s1 + a1 = 1
x1 + x2 + a2 = 3
x1, x2, s1, a1, a2 ≥ 0,
the initial tableau for this phase is:
Basis za x1 x2 s1 a1 a2 Solution
za 1 0 0 0 1 1 0
a1 0 -2 1 -1 1 0 1
a2 0 1 1 0 0 1 3
(can we start the Simplex Method?)
• We perform row operations to change the coefficients of basic vari-
ables a1 and a2 in the z-row to 0 (a necessary condition to start the
Simplex Method with basic variables a1, a2).
• To do that, we add the a1- and a2-rows each multiplied by −1 to the
z-row:
Basis za x1 x2 s1 a1 a2 Solution
za 1 1 -2 1 0 0 -4
a1 0 -2 1 -1 1 0 1
a2 0 1 1 0 0 1 3
• After two iterations of the Simplex Method we get the following final
tableau:
Basis za x1 x2 s1 a1 a2 Solution
za 1 0 0 0 1 1 0
x2 0 0 1 -1/3 1/3 2/3 7/3
x1 0 1 0 1/3 -1/3 1/3 2/3
• In this solution, the artificial variables a1 and a2 are non-basic, i.e.
both equal to 0.
• This indicates that the original problem has a feasible solution.
17
• We use the first phase solution to construct an initial basic solution
for the original problem (the second phase begins).
• We delete the columns of artificial variables ai (i = 1, . . . ,m) and
replace the objective function row with that of the original problem:
Basis z x1 x2 s1 Solution
z 1 -1 -3 0 0
x2 0 0 1 -1/3 7/3
x1 0 1 0 1/3 2/3
(a re-calculated objective function value? not yet!)
• We need to create zeroes in the objective function row in place of
−1 and −3 since x1 and x2 are basic (re-calculations done here!)
• To do this, add the x1-row to the z-row and the x2-row multiplied
by 3 to the z-row (start the Simplex Method after)
Basis z x1 x2 s1 Solution
z 1 0 0 -2/3 23/3
x2 0 0 1 -1/3 7/3
x1 0 1 0 1/3 2/3
• Applying one iteration of the Simplex Method, we get:
Basis z x1 x2 s1 Solution
z 1 2 0 0 9
x2 0 1 1 0 3
s1 0 3 0 1 2
• The optimal solution is x1 = 0, x2 = 3, z∗ = 9.
• If one of the artificial variables remains positive in the optimal so-
lution of the transformed problem (first phase), then the original
problem is infeasible.
• It may take some time to solve the transformed problem only to
discover that the original problem is infeasible.
18
• However this can still give us useful information.
• If a real world problem is infeasible, this usually indicates an error
in formulation of one of the constraints.
• By observing which of the artificial variables remain positive, we can
see which constraints are likely to be wrongly formulated.
• This remark applies equally to the Big-M Method.
19
学霸联盟
