xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

运筹学代写-MAT021/20

时间：2021-02-14

MAT021/20

Solutions

1 (a) Betty plans to invest a total of £17, 000 in mutual funds, certificates of deposit,

and a high yield savings account. She doesn’t want to invest more in mutual

funds than the sum of her certificates of deposit and savings because of the risk

involved in mutual funds. She also wants the amount in savings to be at least

half the amount in certificates of deposit. Her expected returns are 8.5% on the

mutual funds, 5% on the certificates of deposit, and 3.7% on savings. How much

money should Betty invest in each area in order to have the largest return on her

investments? Formulate this as a linear programming problem, clearly describing

your decision variables, objective function, and constraints. Do not solve the LP

problem. [ 9 marks ]

Model Answer: (Class notes/exercise-practice questions/labs) Let x1 be the

amount invested in mutual funds, x2 the amount in certificates of deposit, and x3

the amount in savings. Then the problem can be written as an LP problem as

follows:

maximise z = 0.085x1 + 0.05x2 + 0.037x3

subject to: x1 + x2 + x3 = 17, 000

x1 − x2 − x3 ≤ 0

−x2 + 2x3 ≥ 0

x1, x2, x3 ≥ 0

(b) Solve the following linear programming problem by using the Dual Simplex Method:

minimise z = 2x1 + 3x2 + 3x3

subject to: x1 − 2x2 ≥ −8

2x2 + x3 ≥ 15

2x1 − x2 + x3 ≤ 25

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Clearly provide the optimal solution for the problem and the corresponding ob-

jective function value. [ 8 marks ]

- 2 -

MAT021/20

Model Answer:

(Class notes/exercise-practice questions)

The initial simplex tableau is:

x1 x2 x3 s1 s2 s3 Solution

2 3 3 0 0 0 0

-1 2 0 1 0 0 8

0 −2∗ -1 0 1 0 -15

2 -1 1 0 0 1 25

It’s infeasible. The leaving variable is s2, and the entering variable is x2 (resp.,

the work column): the ratios/quotients are Qx2 = | 3−2 | and Qx3 = | 3−1 |. Since

Qx2 < Qx3 , the second column is an active column, and the pivot causes x2 to

enter the basis and s2 to leave the basis:

x1 x2 x3 s1 s2 s3 Solution

2 0 3/2 0 3/2 0 -22.5

-1 0 −1∗ 1 1 0 -7

0 1 1/2 0 -1/2 0 7.5

2 0 1.5 0 -1/2 1 32.5

The pivot will cause x3 to enter the basis and s1 to leave the basis:

x1 x2 x3 s1 s2 s3 Solution

1/2 0 0 3/2 3 0 -33

1 0 1 -1 -1 0 7

-1/2 1 0 1/2 0 0 4

1/2 0 0 1.5 1 1 22

This is the final simplex tableau for the problem – the optimal solution is x1 = 0,

x2 = 4, x3 = 7, and z = 33.

(c) The solution to the linear programming problem

maximise z = 5x1 + 8x2

subject to: x1 + x2 ≤ 6

5x1 + 9x2 ≤ 45

x1, x2 ≥ 0

is

x1 x2 s1 s2 Solution

0 0 5/4 3/4 165/4

1 0 9/4 -1/4 9/4

0 1 -5/4 1/4 15/4

.

(i) Perform sensitivity analysis on the coefficient of decision variable x2 in the

objective function. [3 marks]

- 3 -

MAT021/20

Model Answer: (using the formula and explanations from the lecture notes)

5 ≤ t ≤ 9

(ii) Find the solution to the following linear programming problem, without re-

solving it from scratch: [5 marks]

maximise z = 5x1 + 8x2 + 2x3

subject to: x1 + x2 + x3 ≤ 6

5x1 + 9x2 + 2x3 ≤ 45

x1, x2, x3 ≥ 0.

Model Answer: (using the pre-multiplication matrix, formula and explana-

tions from the lecture notes)

x1 x2 x3 s1 s2 Solution

0 0 3/4 5/4 3/4 165/4

1 0 7/4 9/4 -1/4 9/4

0 1 -3/4 -5/4 1/4 15/4

.

- 4 -

MAT021/20

2 (a) The Ayatola Oil Company controls two oil fields. Field 1 can produce up to 40

million barrels of oil per day, and field 2 can produce up to 50 million barrels of oil

per day. Ayatola sells oil to two countries, England and Japan. The company’s

profit per barrel of shipping oil from each of the fields is shown in the following

table:

From\To England Japan

Field 1 £1.5 £2.5

Field 2 £2 £3

Each day, England is willing to buy 40 million barrels, and Japan is willing to

buy 30 million barrels. Formulate a balanced transportation problem to maximise

Ayatola’s profits. Do not solve the problem. [10 marks]

Model Answer: (Class notes/labs) In this transportation problem, we have the

total demand equal to 70 million barrels per day, and the total supply is equal to

90 million barrels per day, i.e. the total supply exceeds the total demand. There-

fore, we need to introduce a dummy country with demand equal to the difference

between the total supply and the total demand, i.e. 90− 70 = 20 million barrels

per day, and profits of shipping oil to this dummy country set equal to 0:

From\To England Japan Dummy

Field 1 £1.5 £2.5 0

Field 2 £2 £3 0

Then we have decision variables xij = number of barrels (in millions) per day

produced at field i and shipped to country j, i = 1, 2, j = 1, 2, 3 (1 – England,

2 – Japan, 3 – Dummy).

Then we have the objective function:

z = 1.5x11 + 2.5x12 + 2x21 + 3x22 −→ max

(total profit from the production and shipping, in million pounds)

subject to:

x11 + x12 + x13 = 40 (Field 1 supply constraint)

x21 + x22 + x23 = 50 (Field 2 supply constraint)

x11 + x21 = 40 (England demand constraint)

x12 + x22 = 30 (Japan demand constraint)

x13 + x23 = 20 (Dummy demand constraint)

xij ≥ 0, (i = 1, 2, j = 1, 2, 3)

(Using a graphical representation of the problem, i.e. drawing a simple diagram

with a bipartite graph representing the problem would be helpful here.)

- 5 -

MAT021/20

(b) Using the Branch-and-Bounds method, solve the following instance of the Knap-

sack Problem:

maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5

subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10

x1, x2, x3, x4, x5 = 0 or 1

Use the ratio choice method to obtain solutions to the LP relaxations of the cor-

responding problems. Provide all the necessary details and explanation, and draw

a Branch-and-Bounds tree of sub-problems for the solution process. [15 marks]

Model Answer: (Class notes and exercise/practice questions)

We consider the linear relaxation of the original problem (P0):

maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5

subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10

0 ≤ x1, x2, x3, x4, x5 ≤ 1

To solve the LP relaxation of (P0), we can use the ratio choice method.

We find the following ratios:

r1 = 10/3 = 3.33,

r2 = 6/2 = 3,

r3 = 7/4 = 1.75,

r4 = 12/6 = 2,

r5 = 9/4 = 2.25.

Thus, r1 > r2 > r5 > r4 > r3.

Therefore, the solution to the LP relaxation of (P0) is x1 = x2 = x5 = 1, x4 = 1/6,

x3 = 0, and z = 27 is an upper bound for any integer solution.

Since this is not an integer solution, consider branching by x4, i.e. subproblems

(P1)=(P0)+(x4 = 1) and (P2)=(P0)+(x4 = 0).

The solution to the LP relaxation of (P1) is x4 = x1 = 1, x2 = 1/2, x3 = x5 = 0,

and z = 25.

The solution to the LP relaxation of (P2) is x4 = 0, x1 = x2 = x5 = 1, x3 = 1/4,

and z = 26.75.

Since these are not integer solutions, and (P2) has a higher objective function

value, we first consider branching (P2) by x3, i.e. subproblems

(P3)=(P2)+(x3 = 1) and (P4)=(P2)+(x3 = 0).

The solution to the LP relaxation of (P3) is x3 = x1 = x2 = 1, x4 = 0, x5 = 1/4,

and z = 25.25.

The solution to the LP relaxation of (P4) is x1 = x2 = x5 = 1, x4 = x3 = 0, and

- 6 -

MAT021/20

z = 25. As the solution to the LP relaxation of (P4) is an integer solution, this

becomes a lower bound, and (P4) is fathomed.

Since an integer solution to (P3) is upper-bounded by 25, because of the lower

bound of 25 from (P4) now, (P3) is fathomed.

Since an integer solution to (P1) is upper-bounded by 25 and is equal to the lower

bound given by (P4) now, (P1) is fathomed (we don’t need to branch (P1) be-

cause we cannot get a better integer solution in that branch).

So, all the nodes of the search tree are fathomed, and the optimal solution to the

original problem (P0) is x1 = x2 = x5 = 1, x4 = x3 = 0, with z = 25.

- 7 -

MAT021/20

3 (a) Give an informal description of the (basic) Assignment Problem. Provide an Inte-

ger Programming formulation of the Assignment Problem. Explain the meaning

of all parameters, variables, and constraints. [ 5 marks ]

Model Answer: (Class notes) In an assignment problem, we have n people

p1, p2, . . . , pn and n jobs w1, w2, . . . , wn, and the cost cij of performing job j by

person i, i = 1, 2, . . . , n, j = 1, 2, . . . , n. We wish to find an assignment of people

to jobs (one person per job and one job per person) such that the total cost of per-

forming the jobs is minimised. The costs are normally given by a matrix C = [cij].

Using zero-one decision variables xij such that xij = 1 iff employee i is assigned

to job j, the assignment problem can be expressed as an IP problem as follows:

min z =

n∑

i=1

n∑

j=1

cijxij

s.t.

n∑

i=1

xij = 1, j = 1, 2, . . . , n

n∑

j=1

xij = 1, i = 1, 2, . . . , n

xij = 0 or 1, i, j = 1, . . . , n,

where the first set of constraints guarantees that each job has exactly one person

assigned to perform it, and the second set of constraints guarantees that each

employee is assigned to exactly one job.

(b) Provide an Integer Programming formulation of the Travelling Salesman Problem

(TSP). Explain the meaning of all parameters, variables, and constraints.[7 marks]

Model Answer: (Class notes) Define zero-one variables xij = 1 iff city i is vis-

ited immediately prior to city j. Let cij represent the distance between cities i

and j (assume that the distances cii are prohibitively high). Suppose that there

are n cities that must be visited on the tour.

- 8 -

MAT021/20

Then the TSP can be expressed as an IP problem as follows:

min z =

n∑

i=1

n∑

j=1

cijxij

s.t.

n∑

i=1

xij = 1, j = 1, 2, . . . , n

n∑

j=1

xij = 1, i = 1, 2, . . . , n

u1 = 1

2 ≤ ui ≤ n, i = 2, . . . , n

ui − uj + 1 ≤ (n− 1)(1− xij), i, j = 2, . . . , n

xij = 0 or 1, i, j = 1, . . . , n

ui is integer, i = 1, . . . , n

The first set of constraints says that you must go into each city j exactly once,

and the second set of constraints says that you must leave each city i exactly once.

These constraints ensure that there are two edges adjacent to each city, one in and

one out. This does not prevent so-called sub-tours of less than n arcs: a sub-tour

occurs when there is a cycle containing a proper subset of the cities. Instead of

having one tour of all of the cities, the solution can eventually be composed of two

or more sub-tours each of less than n arcs. The constraints with ui variables elimi-

nate sub-tours – ui are integer variables representing position of city i on the tour.

(c) Given an instance of the TSP and an instance of the Assignment Problem with

the same costs matrix C = [cij], which of the two instances will eventually have

a smaller value of the objective function on its optimal solution? (Assume that

the costs cii, i = 1, 2, . . . , n, are prohibitively high.) Justify your answer.[3 marks]

Model Answer: (Class notes/unseen) The value of the objective function of the

Assignment Problem is a lower bound for the value of the objective function of

the corresponding TSP since both problems have the same objective function,

but TSP has additional constraints in comparison to the IP formulation of the

assignment problem. In other words, the value of the objective function cannot

improve with additional constraints.

(d) Explain how you would use a greedy heuristic to produce a solution to the TSP.

State one advantage and one disadvantage of a greedy heuristic. [3 marks]

Model Answer: Starting from city i, choose the nearest unvisited city and con-

tinue until all cities have been visited. Advantage is very quick, disadvantage is

that solution is likely to be poor especially towards the end of the process.

- 9 -

MAT021/20

(e) Explain how you would use simulated annealing to produce a solution to the TSP.

Include in your answer a definition of the cost function, neighbourhood and start-

ing solution and state any parameters that are required. State one advantage and

one disadvantage of simulated annealing. [7 marks]

Model Answer:

Starting from a random solution choose two cities at random and swap their

position. Evaluate the effect on the cost function (distance). If the distance is

decreased, accept the change. Otherwise accept if a random number between

0 and 1 is less than exp(−d/t) where d is the increase on distance and t is a

parameter. The value of t is lowered during the search using t = r ∗ t where r is

a parameter ≤ 1. Stop when t is too low to accept further moves. Advantage is

can escape from local optima. Disadvantage is the need to set parameters.

- 10 -

MAT021/20

4 (a) You are given the following set of jobs:

Job Duration Due Time

1 12 23

2 8 15

3 17 34

4 10 20

5 5 13

6 11 35

(i) Define the terms makespan and slack in a scheduling context. [3 marks]

Model Answer: Makespan is the total length of time it takes to complete

all jobs. Slack is the length of time for which a job can be delayed and still

be completed by its due date.

(ii) Produce a schedule using the Critical Ratio method. [3 marks]

Model Answer: Job 2 (finishes at time 8), Job 4 (finishes at time 18), Job

5 (finishes at time 23), Job 1 (finishes at time 35), Job 6 (finishes at time 46),

job 3 (finishes at time 63).

(iii) Produce the schedule which minimises the number of late jobs using Moore’s

Algorithm. [4 marks]

Model Answer: Order is 5-2-4-1-6-3. Only 5 and 2 are on time. Move 2 to

end. New order is 5-4-1-6-3-2. Only 5 and 4 are on time. Move 4 to the end.

new order is 5-1-6-3-2-4. 5, 1 and 6 are on time, so 3 jobs are on time. This

is optimal.

(b) An investor is deciding how to invest £5 million between three different investment

schemes. The table below shows the amounts that can be invested in each of the

three schemes, together with the expected returns. All values stated are in millions

of pounds.

Scheme 1 Scheme 2 Scheme 3

Proposal Cost Revenue Cost Revenue Cost Revenue

1 0 0 0 0 0 0

2 1 1 2 2.5 1 1.5

3 2 3 3 4 3 4

4 3 4 - - - -

Use dynamic programming to determine how much should be invested in each

scheme in order to maximise the expected return. Give all optimal solutions. In-

clude all definitions in your answer. No marks will be awarded if a method other

than dynamic programming is used. [15 marks]

- 11 -

MAT021/20

Model Answer n = schemes left to consider, i = remaining money

f(0, 0) = 0

f(1, 5) = 4

f(1, 4) = 4

f(1, 3) = 4

f(1, 2) = 1.5

f(1, 1) = 1.5

f(1, 0) = 0

f(2, 5) = max(0 + f(1, 5), 2.5 + f(1, 3), 4 + f(1, 2)) = 6.5

f(2, 4) = max(0 + f(1, 4), 2.5 + f(1, 2), 4 + f(1, 1)) = 5.5

f(2, 3) = max(0 + f(1, 3), 2.5 + f(1, 1), 4 + f(1, 0)) = 4

f(2, 2) = max(0 + f(1, 2), 2.5 + f(1, 0)) = 2.5

f(3, 5) = max(0 + f(2, 5), 1 + f(2, 4), 3 + f(2, 3), 4 + f(2, 2)) = 7

Solution is 2 in scheme 1, 0 in scheme 2 and 3 in scheme 3 or

2 in scheme 1, 2 in scheme 2 and 1 in scheme 3 or

2 in scheme 1, 3 in scheme 2

- 12X -

学霸联盟

Solutions

1 (a) Betty plans to invest a total of £17, 000 in mutual funds, certificates of deposit,

and a high yield savings account. She doesn’t want to invest more in mutual

funds than the sum of her certificates of deposit and savings because of the risk

involved in mutual funds. She also wants the amount in savings to be at least

half the amount in certificates of deposit. Her expected returns are 8.5% on the

mutual funds, 5% on the certificates of deposit, and 3.7% on savings. How much

money should Betty invest in each area in order to have the largest return on her

investments? Formulate this as a linear programming problem, clearly describing

your decision variables, objective function, and constraints. Do not solve the LP

problem. [ 9 marks ]

Model Answer: (Class notes/exercise-practice questions/labs) Let x1 be the

amount invested in mutual funds, x2 the amount in certificates of deposit, and x3

the amount in savings. Then the problem can be written as an LP problem as

follows:

maximise z = 0.085x1 + 0.05x2 + 0.037x3

subject to: x1 + x2 + x3 = 17, 000

x1 − x2 − x3 ≤ 0

−x2 + 2x3 ≥ 0

x1, x2, x3 ≥ 0

(b) Solve the following linear programming problem by using the Dual Simplex Method:

minimise z = 2x1 + 3x2 + 3x3

subject to: x1 − 2x2 ≥ −8

2x2 + x3 ≥ 15

2x1 − x2 + x3 ≤ 25

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Clearly provide the optimal solution for the problem and the corresponding ob-

jective function value. [ 8 marks ]

- 2 -

MAT021/20

Model Answer:

(Class notes/exercise-practice questions)

The initial simplex tableau is:

x1 x2 x3 s1 s2 s3 Solution

2 3 3 0 0 0 0

-1 2 0 1 0 0 8

0 −2∗ -1 0 1 0 -15

2 -1 1 0 0 1 25

It’s infeasible. The leaving variable is s2, and the entering variable is x2 (resp.,

the work column): the ratios/quotients are Qx2 = | 3−2 | and Qx3 = | 3−1 |. Since

Qx2 < Qx3 , the second column is an active column, and the pivot causes x2 to

enter the basis and s2 to leave the basis:

x1 x2 x3 s1 s2 s3 Solution

2 0 3/2 0 3/2 0 -22.5

-1 0 −1∗ 1 1 0 -7

0 1 1/2 0 -1/2 0 7.5

2 0 1.5 0 -1/2 1 32.5

The pivot will cause x3 to enter the basis and s1 to leave the basis:

x1 x2 x3 s1 s2 s3 Solution

1/2 0 0 3/2 3 0 -33

1 0 1 -1 -1 0 7

-1/2 1 0 1/2 0 0 4

1/2 0 0 1.5 1 1 22

This is the final simplex tableau for the problem – the optimal solution is x1 = 0,

x2 = 4, x3 = 7, and z = 33.

(c) The solution to the linear programming problem

maximise z = 5x1 + 8x2

subject to: x1 + x2 ≤ 6

5x1 + 9x2 ≤ 45

x1, x2 ≥ 0

is

x1 x2 s1 s2 Solution

0 0 5/4 3/4 165/4

1 0 9/4 -1/4 9/4

0 1 -5/4 1/4 15/4

.

(i) Perform sensitivity analysis on the coefficient of decision variable x2 in the

objective function. [3 marks]

- 3 -

MAT021/20

Model Answer: (using the formula and explanations from the lecture notes)

5 ≤ t ≤ 9

(ii) Find the solution to the following linear programming problem, without re-

solving it from scratch: [5 marks]

maximise z = 5x1 + 8x2 + 2x3

subject to: x1 + x2 + x3 ≤ 6

5x1 + 9x2 + 2x3 ≤ 45

x1, x2, x3 ≥ 0.

Model Answer: (using the pre-multiplication matrix, formula and explana-

tions from the lecture notes)

x1 x2 x3 s1 s2 Solution

0 0 3/4 5/4 3/4 165/4

1 0 7/4 9/4 -1/4 9/4

0 1 -3/4 -5/4 1/4 15/4

.

- 4 -

MAT021/20

2 (a) The Ayatola Oil Company controls two oil fields. Field 1 can produce up to 40

million barrels of oil per day, and field 2 can produce up to 50 million barrels of oil

per day. Ayatola sells oil to two countries, England and Japan. The company’s

profit per barrel of shipping oil from each of the fields is shown in the following

table:

From\To England Japan

Field 1 £1.5 £2.5

Field 2 £2 £3

Each day, England is willing to buy 40 million barrels, and Japan is willing to

buy 30 million barrels. Formulate a balanced transportation problem to maximise

Ayatola’s profits. Do not solve the problem. [10 marks]

Model Answer: (Class notes/labs) In this transportation problem, we have the

total demand equal to 70 million barrels per day, and the total supply is equal to

90 million barrels per day, i.e. the total supply exceeds the total demand. There-

fore, we need to introduce a dummy country with demand equal to the difference

between the total supply and the total demand, i.e. 90− 70 = 20 million barrels

per day, and profits of shipping oil to this dummy country set equal to 0:

From\To England Japan Dummy

Field 1 £1.5 £2.5 0

Field 2 £2 £3 0

Then we have decision variables xij = number of barrels (in millions) per day

produced at field i and shipped to country j, i = 1, 2, j = 1, 2, 3 (1 – England,

2 – Japan, 3 – Dummy).

Then we have the objective function:

z = 1.5x11 + 2.5x12 + 2x21 + 3x22 −→ max

(total profit from the production and shipping, in million pounds)

subject to:

x11 + x12 + x13 = 40 (Field 1 supply constraint)

x21 + x22 + x23 = 50 (Field 2 supply constraint)

x11 + x21 = 40 (England demand constraint)

x12 + x22 = 30 (Japan demand constraint)

x13 + x23 = 20 (Dummy demand constraint)

xij ≥ 0, (i = 1, 2, j = 1, 2, 3)

(Using a graphical representation of the problem, i.e. drawing a simple diagram

with a bipartite graph representing the problem would be helpful here.)

- 5 -

MAT021/20

(b) Using the Branch-and-Bounds method, solve the following instance of the Knap-

sack Problem:

maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5

subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10

x1, x2, x3, x4, x5 = 0 or 1

Use the ratio choice method to obtain solutions to the LP relaxations of the cor-

responding problems. Provide all the necessary details and explanation, and draw

a Branch-and-Bounds tree of sub-problems for the solution process. [15 marks]

Model Answer: (Class notes and exercise/practice questions)

We consider the linear relaxation of the original problem (P0):

maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5

subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10

0 ≤ x1, x2, x3, x4, x5 ≤ 1

To solve the LP relaxation of (P0), we can use the ratio choice method.

We find the following ratios:

r1 = 10/3 = 3.33,

r2 = 6/2 = 3,

r3 = 7/4 = 1.75,

r4 = 12/6 = 2,

r5 = 9/4 = 2.25.

Thus, r1 > r2 > r5 > r4 > r3.

Therefore, the solution to the LP relaxation of (P0) is x1 = x2 = x5 = 1, x4 = 1/6,

x3 = 0, and z = 27 is an upper bound for any integer solution.

Since this is not an integer solution, consider branching by x4, i.e. subproblems

(P1)=(P0)+(x4 = 1) and (P2)=(P0)+(x4 = 0).

The solution to the LP relaxation of (P1) is x4 = x1 = 1, x2 = 1/2, x3 = x5 = 0,

and z = 25.

The solution to the LP relaxation of (P2) is x4 = 0, x1 = x2 = x5 = 1, x3 = 1/4,

and z = 26.75.

Since these are not integer solutions, and (P2) has a higher objective function

value, we first consider branching (P2) by x3, i.e. subproblems

(P3)=(P2)+(x3 = 1) and (P4)=(P2)+(x3 = 0).

The solution to the LP relaxation of (P3) is x3 = x1 = x2 = 1, x4 = 0, x5 = 1/4,

and z = 25.25.

The solution to the LP relaxation of (P4) is x1 = x2 = x5 = 1, x4 = x3 = 0, and

- 6 -

MAT021/20

z = 25. As the solution to the LP relaxation of (P4) is an integer solution, this

becomes a lower bound, and (P4) is fathomed.

Since an integer solution to (P3) is upper-bounded by 25, because of the lower

bound of 25 from (P4) now, (P3) is fathomed.

Since an integer solution to (P1) is upper-bounded by 25 and is equal to the lower

bound given by (P4) now, (P1) is fathomed (we don’t need to branch (P1) be-

cause we cannot get a better integer solution in that branch).

So, all the nodes of the search tree are fathomed, and the optimal solution to the

original problem (P0) is x1 = x2 = x5 = 1, x4 = x3 = 0, with z = 25.

- 7 -

MAT021/20

3 (a) Give an informal description of the (basic) Assignment Problem. Provide an Inte-

ger Programming formulation of the Assignment Problem. Explain the meaning

of all parameters, variables, and constraints. [ 5 marks ]

Model Answer: (Class notes) In an assignment problem, we have n people

p1, p2, . . . , pn and n jobs w1, w2, . . . , wn, and the cost cij of performing job j by

person i, i = 1, 2, . . . , n, j = 1, 2, . . . , n. We wish to find an assignment of people

to jobs (one person per job and one job per person) such that the total cost of per-

forming the jobs is minimised. The costs are normally given by a matrix C = [cij].

Using zero-one decision variables xij such that xij = 1 iff employee i is assigned

to job j, the assignment problem can be expressed as an IP problem as follows:

min z =

n∑

i=1

n∑

j=1

cijxij

s.t.

n∑

i=1

xij = 1, j = 1, 2, . . . , n

n∑

j=1

xij = 1, i = 1, 2, . . . , n

xij = 0 or 1, i, j = 1, . . . , n,

where the first set of constraints guarantees that each job has exactly one person

assigned to perform it, and the second set of constraints guarantees that each

employee is assigned to exactly one job.

(b) Provide an Integer Programming formulation of the Travelling Salesman Problem

(TSP). Explain the meaning of all parameters, variables, and constraints.[7 marks]

Model Answer: (Class notes) Define zero-one variables xij = 1 iff city i is vis-

ited immediately prior to city j. Let cij represent the distance between cities i

and j (assume that the distances cii are prohibitively high). Suppose that there

are n cities that must be visited on the tour.

- 8 -

MAT021/20

Then the TSP can be expressed as an IP problem as follows:

min z =

n∑

i=1

n∑

j=1

cijxij

s.t.

n∑

i=1

xij = 1, j = 1, 2, . . . , n

n∑

j=1

xij = 1, i = 1, 2, . . . , n

u1 = 1

2 ≤ ui ≤ n, i = 2, . . . , n

ui − uj + 1 ≤ (n− 1)(1− xij), i, j = 2, . . . , n

xij = 0 or 1, i, j = 1, . . . , n

ui is integer, i = 1, . . . , n

The first set of constraints says that you must go into each city j exactly once,

and the second set of constraints says that you must leave each city i exactly once.

These constraints ensure that there are two edges adjacent to each city, one in and

one out. This does not prevent so-called sub-tours of less than n arcs: a sub-tour

occurs when there is a cycle containing a proper subset of the cities. Instead of

having one tour of all of the cities, the solution can eventually be composed of two

or more sub-tours each of less than n arcs. The constraints with ui variables elimi-

nate sub-tours – ui are integer variables representing position of city i on the tour.

(c) Given an instance of the TSP and an instance of the Assignment Problem with

the same costs matrix C = [cij], which of the two instances will eventually have

a smaller value of the objective function on its optimal solution? (Assume that

the costs cii, i = 1, 2, . . . , n, are prohibitively high.) Justify your answer.[3 marks]

Model Answer: (Class notes/unseen) The value of the objective function of the

Assignment Problem is a lower bound for the value of the objective function of

the corresponding TSP since both problems have the same objective function,

but TSP has additional constraints in comparison to the IP formulation of the

assignment problem. In other words, the value of the objective function cannot

improve with additional constraints.

(d) Explain how you would use a greedy heuristic to produce a solution to the TSP.

State one advantage and one disadvantage of a greedy heuristic. [3 marks]

Model Answer: Starting from city i, choose the nearest unvisited city and con-

tinue until all cities have been visited. Advantage is very quick, disadvantage is

that solution is likely to be poor especially towards the end of the process.

- 9 -

MAT021/20

(e) Explain how you would use simulated annealing to produce a solution to the TSP.

Include in your answer a definition of the cost function, neighbourhood and start-

ing solution and state any parameters that are required. State one advantage and

one disadvantage of simulated annealing. [7 marks]

Model Answer:

Starting from a random solution choose two cities at random and swap their

position. Evaluate the effect on the cost function (distance). If the distance is

decreased, accept the change. Otherwise accept if a random number between

0 and 1 is less than exp(−d/t) where d is the increase on distance and t is a

parameter. The value of t is lowered during the search using t = r ∗ t where r is

a parameter ≤ 1. Stop when t is too low to accept further moves. Advantage is

can escape from local optima. Disadvantage is the need to set parameters.

- 10 -

MAT021/20

4 (a) You are given the following set of jobs:

Job Duration Due Time

1 12 23

2 8 15

3 17 34

4 10 20

5 5 13

6 11 35

(i) Define the terms makespan and slack in a scheduling context. [3 marks]

Model Answer: Makespan is the total length of time it takes to complete

all jobs. Slack is the length of time for which a job can be delayed and still

be completed by its due date.

(ii) Produce a schedule using the Critical Ratio method. [3 marks]

Model Answer: Job 2 (finishes at time 8), Job 4 (finishes at time 18), Job

5 (finishes at time 23), Job 1 (finishes at time 35), Job 6 (finishes at time 46),

job 3 (finishes at time 63).

(iii) Produce the schedule which minimises the number of late jobs using Moore’s

Algorithm. [4 marks]

Model Answer: Order is 5-2-4-1-6-3. Only 5 and 2 are on time. Move 2 to

end. New order is 5-4-1-6-3-2. Only 5 and 4 are on time. Move 4 to the end.

new order is 5-1-6-3-2-4. 5, 1 and 6 are on time, so 3 jobs are on time. This

is optimal.

(b) An investor is deciding how to invest £5 million between three different investment

schemes. The table below shows the amounts that can be invested in each of the

three schemes, together with the expected returns. All values stated are in millions

of pounds.

Scheme 1 Scheme 2 Scheme 3

Proposal Cost Revenue Cost Revenue Cost Revenue

1 0 0 0 0 0 0

2 1 1 2 2.5 1 1.5

3 2 3 3 4 3 4

4 3 4 - - - -

Use dynamic programming to determine how much should be invested in each

scheme in order to maximise the expected return. Give all optimal solutions. In-

clude all definitions in your answer. No marks will be awarded if a method other

than dynamic programming is used. [15 marks]

- 11 -

MAT021/20

Model Answer n = schemes left to consider, i = remaining money

f(0, 0) = 0

f(1, 5) = 4

f(1, 4) = 4

f(1, 3) = 4

f(1, 2) = 1.5

f(1, 1) = 1.5

f(1, 0) = 0

f(2, 5) = max(0 + f(1, 5), 2.5 + f(1, 3), 4 + f(1, 2)) = 6.5

f(2, 4) = max(0 + f(1, 4), 2.5 + f(1, 2), 4 + f(1, 1)) = 5.5

f(2, 3) = max(0 + f(1, 3), 2.5 + f(1, 1), 4 + f(1, 0)) = 4

f(2, 2) = max(0 + f(1, 2), 2.5 + f(1, 0)) = 2.5

f(3, 5) = max(0 + f(2, 5), 1 + f(2, 4), 3 + f(2, 3), 4 + f(2, 2)) = 7

Solution is 2 in scheme 1, 0 in scheme 2 and 3 in scheme 3 or

2 in scheme 1, 2 in scheme 2 and 1 in scheme 3 or

2 in scheme 1, 3 in scheme 2

- 12X -

学霸联盟