代写COMP3910、代写Java、Python课程编程

日期：2022-03-24 11:29

COMP3910: Coursework 2

Submission: Gradescope

Deadline: 17:00 GMT, Friday 25 March 2022

Award: This piece of summative coursework is worth 10% of your grade

Problem 1 (modelling) [12 marks]

A company needs to purchase components X and Y to produce toys. Components X and Y can

be purchased from three suppliers, A, B and C. The purchase costs of the components are detailed

in the middle part of the table below. The required quantities of the components are shown in the

last column.

Cost Supplier Total

per unit A B C requirement

Component X ￡ 54 ￡ 56 ￡ 61 400

Component Y ￡ 120 ￡ 110 ￡ 106 500

Delivery per order ￡ 75 ￡ 80 ￡ 70

The following requirements should be satis?ed.

(i) Each supplier has a ?xed delivery charge for the whole order, independent on the size of the

order and the product types. Delivery charges are shown in the last row of the table.

(ii) Supplier C has a minimum order size of at least 100 units of components Y (if a non-zero

amount of components Y are ordered from C).

(iii) Supplier A will only accept an order which is worth at least ￡ 25,000, without taking into

account delivery charges and independently on the component type (components X, components

Y, or both).

The objective is to arrange the supply of the required components minimising the total cost.

Formulate an ILP. No need to present an explanation.

Use variables xA, xB and xC for the number of components X purchased from A, B and C,

respectively.

Similarly, use variables yA, yB and yC for the number of components Y purchased from A, B and

C, respectively.

You may need additional variables in your model.

1

Problem 2 (B&B for the knapsack problem) [28 marks]

An energy company has n = 4 electricity generators, each of which can be regulated independently

of one another. Each generator can be either switched o§ or it can operate in one of the two

modes: at a normal rate, as indicated in the table below, or at a double rate, producing double

power output at a double cost.

The following table shows the cost to operate each generator at a normal rate and the power

output.

Generators Demand

i = 1 i = 2 i = 3 i = 4 b

Operating cost ci 14 13 10 12

(in thousands of pounds)

Power output ai 10 7 4 3 12

(in Gigawatt)

The company wishes to select generators and their operation modes in order to meet the expected

12 Gigawatt demand at the smallest possible operating cost. The corresponding problem can be

modelled as the knapsack problem with the cost minimisation objective:

min f =

Pn

i=1

cixi

s.t. Pn

i=1

aixi  b;

xi 2 f0; 1; 2g; i = 1; : : : ; n:

(1)

For the instance under the consideration, the model is of the form:

min f = 14x1 +13x2 +10x3 +12x4

s.t. 10x1 +7x2 +4x3 +3x4  12

xi 2 f0; 1; 2g ; i = 1; : : : ; 4:

The problem is similar to the one considered in Chapter 7, but there are two points of di§erence:

the direction of optimisation (minimisation) and the sign in the inequality constraint ().

2.1 For the minimisation problem (1), the branch and bound algorithm needs the formula for

calculating lower bounds for each node of the search tree.

Suppose generators are numbered so that(2)

Consider a node of the search tree with the ?rst k variables ?xed,

x1 = h1; : : : ; xk = hk;

and the remaining variables xk+1, . . . , xn non-?xed. The task is to prove the following

formula for calculating a lower bound for that node:

(3)

You can use the arguments similar to those presented in Chapter 7 for calculating upper

bounds for the max-problem. [7 marks]

2

2.2 Suppose in problem (1) all data are integer and consider the following expressions derived from

(3):

Select all correct options. (Penalty [-1] for each incorrect answer ).

LB0

is not a true lower bound for some instances

LB0

is a correct lower bound for all instances

LB00 is not a true lower bound for some instances

LB00 is a correct lower bound for all instances

Both formulae, LB0 and LB00, are correct lower bounds for all instances and it does not

matter which one is used

Both formulae, LB0 and LB00, are correct lower bounds for all instances, but LB0

should

be preferred

Both formulae, LB0 and LB00, are correct lower bounds for all instances, but LB00 should

be preferred

[6 marks]

2.3 Find an optimal solution by the branch-and-bound algorithm. Present the search tree. Use

the depth-?rst strategy, selecting each time the most promising node among all child nodes

of the same parent node. Number the nodes of the tree in the order they are obtained. State

the optimal solution and its cost. [15 marks]

3