闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

IB2070

2021

IB2070 – MATHEMATICAL PROGRAMMING II

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 [email protected] 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, 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 [email protected].

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.

[Question 1]

(1) Consider the following linear programming problem, in which c1 andc2 are parameters:

(a) Show that the problem is feasible.

(b) Derive the dual of the problem.

(c) Find the condition of c1 andc2 so that the given problem has a finite optimal value. Provide all details of your working. (Hint: check the feasibility of the dual problem.)

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

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

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

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

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

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

(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 ,)2,5( ,)2,4( ,)2,3( ,)1,3( ,)1,2({ = ⃞(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 (i, j) be cij and dij, respectively, for each arc (i, j) ∈ A. Provide all details without omission.

(Hint: Introduce a set of binary variables xij to define a path for the first truck, a set of binary variables yij to define a path for the second truck, and a set of binary variables zij to identify the situation where two trucks use the same arc (i, j).)

[Question 3]

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