COMP4041 LINEAR AND DISCRETE OPTIMIZATION 离散优化
A LEVEL 4 MODULE, AUTUMN SEMESTER 2020-2021 LINEAR AND DISCRETE OPTIMIZATION (COMP4041)
Suggested Time to Answer the Paper: ONE HOUR AND THIRTY MINUTES Maximum Time Allowed to Submit Answers in Moodle: 48 HOURS
This is a take-home and open-book exam with answers to be submitted in Moodle no later than the DATE/TIME indicated in the Moodle dropbox. The Academic Integrity Statement and general Instructions and Advice are also available in Moodle.
Answer ALL THREE QUESTIONS
Submit your answers containing all the work you wish to have marked as a single PDF file, with each page in the correct orientation, to the dropbox in the module’s Moodle page.
You may write/draw your answers on paper and then scan them to a PDF file, or you may type/draw your answers into electronic form directly and generate a PDF file. Guidance on scanning can be found through the Faculty of Science Moodle Page Guidance for Remote Learning.
Your solutions should include complete explanations and should be based on the material covered in the module. Make sure your PDF file is easily readable and does not require magnification. Text/drawing which is not in focus or is not legible for any other reason will be ignored.
Use the following naming convention for your PDF file: StudentID_COMP4041. Include your student ID number at the top of each page of your answers. Do not include your name.
Staff are not permitted to answer assessment or teaching queries during the period in which your examination is live. If you spot what you think may be an error on the exam paper, note this in your submission but answer the question as written.
You must produce the answers by yourself only. You must be careful to avoid plagiarism, collusion or false authorship. Remember that before accessing this exam paper in Moodle, you must have confirmed to have read and understood the Faculty of Science Statement on Academic Integrity. This statement refers to, and does not replace, the University policy which stipulates severe penalties for academic misconduct. You are also not allowed to share this exam paper with anyone else or post it anywhere online.
COMP4041E1
COMP4041E1 1 Next Page
QUESTION 1 – Graphical Method (30 Marks)
Consider the LP-model below for a production problem where decision variables X1 and X2 give the amount of products P1 and P2 to be manufactured, so a pair (X1,X2) gives a production plan. The objective function maximizes the total profit. Three materials: A, B and C in limited supply are used to produce both P1 and P2. Constraints (1), (2) and (3) restrict the use of materials A, B, and C respectively, to their limited availability.
Maximize: Subject to:
Z=10X1 + 8X2 X1+2X2≤22 (1) X1 + X2 ≤ 12 (2) 5X1+3X2≤45 (3) X1 ≥ 0 (4) X2 ≥ 0 (5)
A. Apply the graphical method to solve this LP model. Make sure to clearly indicate the following in the graph: all constraints, objective function, feasible region, optimal CPF (corner point feasible) solution, binding constraints and not-binding constraints.
[10 marks]
B. Consider the original LP model in part A. The production team wants to know if it is possible to adjust the profit per unit of the products in order to have the same optimal profit (same objective value) calculated before while having distinct alternative production plans (multiple optimal solutions). However, they want to avoid an increase in the profit per unit of product P1 (i.e. not more than 10) and the amount produced of P1 (i.e. X1) must be 2.5 at least. Note that nothing else in the model should change, only the profits. Explain and illustrate your answer.
[10 marks]
C. Consider the original LP model in part A. Assume that both products P1 and P2 can now be produced using materials A and B only, i.e. there is no need to consider constraint (3) corresponding to material C. It has been decided to set the profit per unit of product P2 to 8, i.e. as in the original model. The production team wants to set the profit per unit of product P1 such that there is a single optimal solution involving the production of both products (that is, producing zero units of one of the products is not acceptable). Explain how the profit per unit of product P1 should be set. Explain and illustrate your answer.
[10 marks]
COMP4041E1 2 Next Page
COMP4041E1
QUESTION 2 – Simplex and B&B Methods (30 Marks)
A. Consider the following LP (linear programming) model with decision variables X1 and X2:
Maximize: Subject to:
Z = 9X1 + 9X2
X1 + 2X2 <= 22 (1) X1 + X2 <= 12 (2) 5X1 + 3X2 <= 45 (3) X1 >= 0 (4) X2 >= 0 (5)
Despite this being an LP model, the aim is to find an integer CPF optimal solution. Apply the algebraic Simplex method (tabular Simplex method not accepted as answer) to solve this model starting from the CPF (0,0) and until an integer optimal solution is found. Make sure to label clearly each step and calculations carried out when applying the method.
[15 marks] B. Consider the following BIP (binary integer programming) model with decision variables X1, X2, X3
Maximize: Z = X1 + 3X1 + 5X3+ 7X4
Subject to: X1 + 2X2 + 10X3+ 20X4 X1 + 2X2 2
X1, X2, X3, X4 are binary
20 (1) (2) (3)
Apply the Branch & Bound method to solve this BIP model. Your answer must illustrate and explain step by step, how the method is applied. This should include the search tree with explanation of the sequence in which the nodes are explored until the optimal solution is found. Specify and justify the branch ordering criteria that you used.
[15 marks]
COMP4041E1 3 Next Page
COMP4041E1
QUESTION 3 – Modelling an Optimization Problem (40 Marks)
The management of a catering company wants to decide which of N foods and how much of each to serve in their next event. They want to determine the cheapest mix subject to their client’s requirements. There is a cost C(i) associated with the production of one unit of food i. There is also a fixed setup cost S(i) if food i is served. Each unit of food i has L(i) total-calories from which F(i) are fat-calories. There should be no less than L1 total-calories but less than L2 in the food mix served. At most 20% of the total-calories in the mix should be fat-calories. Out of the N possible foods, half of them are cold foods and the other half are hot foods (N is even). The client wants twice as many hot foods as cold foods in the mix. The client wants at least one choice of cold food in the event. The foods can be produced all in site A or all in site B (it is not possible to use both sites simultaneously). Preparing one unit of (hot or cold) food i in site A requires Q(i) units of time while in site B requires R(i) units of time. The total number of time units available for food preparation for this event is T. One of the sites A or B will be used but this will be decided later. It is assumed that each food can be produced in fractional values if required.
Write down all the required algebraic expressions to express the optimization model for the above optimization problem. For each algebraic expression, make sure to explain parameters, decision variables and the rationale for the formulation.
[40 marks]
COMP4041E1 4 End
COMP4041E1
The University of Nottingham
SCHOOL OF COMPUTER SCIENCE