关于算法:IB2070数学分析

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).