xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

扫码添加客服微信

扫描添加客服微信

运筹学代写-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 -

学霸联盟

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写