xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：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

学霸联盟