Page 1 of 5

University of Warwick - Warwick Business School

January 2021

IB2070 – MATHEMATICAL PROGRAMMING II

Open Book Assessment – 2 hours

Instructions:

A. You have 2 hours and 45 minutes in total to complete your assessment and upload it to the

AEP. This includes provision for technical delays.

B. There are three number of questions. You should attempt every question.

C. The number of marks each question will carry is indicated.

D. Save your file with your Student ID number and Module Code before submitting via the AEP.

E. By starting this assessment you are declaring yourself fit to undertake it. You are expected to

make a reasonable attempt at the assessment by answering the questions.

F. Use the AEP immediately to seek advice if you cannot access the assessment, or believe you

are registered to the incorrect paper.

Other information (read the following very carefully):

G. During the online assessment:

i. If you have a question about the content of your assessment you should ask the

Module Convenor/invigilator via the AEP query system. Do not send an email to them,

or to undergraduate@wbs.ac.uk as this will not be answered.

ii. If you experience technical difficulties that prevent you from completing and

submitting your answer file please submit a mitigating circumstances case via my.wbs

(or the University’s portal if you are a non-WBS student). Please do not attach your

answer file as it will not be marked.

H. Your document:

i. You must type your answers in Word (or an equivalent piece of software) and upload

these to the AEP within a single PDF file.

ii. Ensure your answers to each question follow the order in which the questions appear

in the exam paper. Start each new question or question part on a new page (or

separate piece of paper, where handwritten answers are required) and write the

question number at the top of each page of your answers.

iii. Include on each page of your file your Student ID Number, the module code and the

page number (using the format ‘x of y pages’ to confirm how many pages in total you

are submitting).

iv. Within your one, single file you may include images (where required or where you

want to use as part of your answer) (i.e. screenshots, photos or online drawings) of

hand-written calculations, formulae, charts or graphs to complement your answers

and show your workings. These images should be embedded at the point in the

document where they are relevant in your answers.

v. Ensure that you label any images you include to inform and assist the marker. Where

you have handwritten items please write legibly, preferably in dark blue or black ink,

IB2070

Page 2 of 5

and ensure that it is not too faint to be captured by a scan or photograph. Remember,

it is your responsibility to ensure that your work can be read.

I. Academic integrity (plagiarism/collusion):

i. You are allowed to access module materials, notes, resources, other reference

materials and the internet during the assessment.

ii. You should not communicate with any other candidate during the assessment period

as this could be interpreted as collusion and may lead to your work being reviewed for

cheating. This includes the sharing of the exam paper with other students. Collusion is

taken very seriously by the University.

iii. To further maintain the academic integrity of online assessments:

You are asked to provide details of your working out to indicate your approach to

addressing the questions posed.

Warwick Business School reserves the right to viva any students suspected of

cheating.

J. Submitting your answer file:

i. You have an additional 45 minutes beyond the stated duration of the assessment. This

is for finalising your answer file, converting to PDF (if relevant), uploading to the AEP –

ensure you upload the correct document, and submitting. This includes provision for

technical delays.

ii. This online assessment will close at 11:45am UK time and you will not be able to

submit your answer file after that time, unless you have Reasonable Exam

Adjustments.

iii. If you have an agreement that entitles you to additional time (reasonable

adjustments), you should see the amount of additional time you have been granted on

the AEP. If you have any queries regarding the amount of additional time you have

been granted please email exams@wbs.ac.uk.

iv. Only documents submitted via the AEP will be accepted and marked.

v. Incorrect documents submitted via the AEP may be marked and that mark will be

final. You should therefore use the 45 minutes of extra time granted to ensure you

submit the correct document.

vi. Documents sent via email or through the mitigating circumstances portal will not be

marked.

Your assessment starts below.

IB2070

Page 3 of 5

[Question 1]

(1) Consider the following linear programming problem, in which

and

are parameters:

(a) Show that the problem is feasible.

[3 marks]

(b) Derive the dual of the problem.

[8 marks]

(c) Find the condition of

and

so that the given problem has a finite optimal value. Provide

all details of your working. (Hint: check the feasibility of the dual problem.)

[12 marks]

(2) The branch-and-bound algorithm has been used to solve an integer linear programming problem

(IP) of maximizing the investment return. Part of the corresponding branch-and-bound tree is

presented below, where the circled numbers are the optimal values of the corresponding LP

relaxations and, of all eight integer variables,

and

are binary.

(a) Unfortunately, there is one misprint among the circled numbers in the branch-and-bound

tree. Identify this misprinted number and explain your answer.

[5 marks]

(b) Use the information presented in the tree to provide the best (i.e., smallest) upper bound of

the optimal objective value of the original IP problem. Explain your answer.

[7 marks]

(Continued…/)

IB2070

Page 4 of 5

[Question 2]

The following diagram indicates the costs of travelling along the arcs of the network, where a negative

cost represents a profit.

(1) Use the Label Correcting Algorithm to find a cheapest directed path from node 1 to node 5.

Provide all the working details, including every step and the final result: the shortest path you find

and its total length.

[12 marks]

(2) Formulate the shortest-path (i.e., cheapest-path) problem as an integer linear programming (IP)

problem, which is a special case of the minimum-cost network flow problem. Provide all the details

of your formulation: variables, objective function and constraints.

[8 marks]

(3) Construct the dual of the linear program (LP) relaxation of the IP you constructed in part (2).

[10 marks]

(4) Use the dual in part (3) to confirm the optimality of the shortest path you find in part (1).

[5 marks]

(5) The problem in part (2) can be considered as finding a cheapest route for one truck. Now

formulate an IP model for finding the cheapest routes for two trucks (i.e., two directed paths from

node 1 to node 5 with the minimum total cost): Denote by

= {(1,2), (1,3), (2,3), (2,4), (2,5),

(3,4), (4,5) } the set of all seven arcs in the above network. Let the travelling costs of one truck

and two trucks along arc (,)

be

and

, respectively, for each arc (,)

∈ .

Provide all details

without omission.

[15 marks]

(Hint: Introduce a set of binary variables

to define a path for the first truck, a set of binary

variables

to define a path for the second truck, and a set of binary variables

to identify the

situation where two trucks use the same arc (,).)

[Question 3]

Consider the following network, where the number by each arc is the capacity of the arc:

(1) Use the Ford-Fulkerson algorithm to find a maximum flow from node 1 to node 5 in the network

above.

[10 marks]

(2) Identify a cut that can be used to verify the optimality of the maximum flow you have found in

part (1).

版权所有：留学生程序辅导网 2019 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。