COMP4041 LINEAR AND DISCRETE OPTIMIZATION 2021-2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
A LEVEL 4 MODULE, AUTUMN SEMESTER 2021-2022
LINEAR AND DISCRETE OPTIMIZATION (COMP4041)
QUESTION 1 – Graphical Method (20 Marks)
Answers to this question including graphs automatically produced by some software are not valid. Consider the following LP (linear programming) model with decision variables X1 and X2 :
Minimize: Z = 15X1 + 20X2
2X1 – 3X2 ≤ 6 (2)
X1 + X2 ≥ 6 (3)
X1 ≥ 0 (4)
X2 ≥ 0 (5)
A. Apply the graphical method to solve the above LP model. Make sure to clearly identify the following in the graph: all constraints, objective function, feasible region, optimal CPF (corner point feasible) solution, binding constraints and non-binding constraints.
[10 marks]
B. Consider the original LP model of question 1.A. The following change is made to the model. Constraint (2) changes to 2X1 – 3X2 = 6. Identify the new CPF solution and then solve the problem algebraically by solving the corresponding system of equations.
[5 marks]
C. Consider the original LP model of question 1.A. The following change is made to the model. Constraint (3) changes to 3X1 + 4X2 > 23. Identify the new CPF solution and then solve the problem algebraically by solving the corresponding system of equations.
[5 marks]
QUESTION 2 – Simplex Method (20 Marks)
Consider the following LP (linear programming) model with decision variables X1 and X2 :
Subject to: X1 ≤ 4 (1)
X1 + 3X2 ≤ 15 (2)
2X1 + X2 ≤ 10 (3)
X1 ≥ 0 (4)
X2 ≥ 0 (5)
Apply the algebraic Simplex method (the tabular Simplex method is not accepted as valid answer) to solve this model starting from the CPF (0,0) and until an optimal solution is found. Make sure to clearly label each step identifying elements (basic/non-basic variables, BF solution) and calculations when applying the method.
[20 marks]
QUESTION 3 – Modelling a Selection Optimization Problem (40 Marks)
Some manufacturing company wants to decide which of N new items to produce and how many units (must be integer) of each item to produce. There is a fixed cost Ci associated with starting the production of item i. The net revenue per unit of item i is given by Ri. The objective is to maximize the total profit (total net revenue minus start-up fixed costs). Let Xi be the decision variable giving the number of units produced of item i. The following constraints are imposed:
• No more than half of the N items are to be produced (assume N is even)
• Item 3 can be produced only if either product 1 or 2 is produced (or both items)
• Item 4 can be produced if and only if product 3 and product 5 are both produced
• For item 1, either no units are produced or exactly Q units must be produced
• The start-up fixed cost summed over all items produced is either equal to S or equal to T
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]
QUESTION 4 – Modelling a Goal Programming Problem (20 Marks)
A city parks department has £600 million to build recreational facilities and wants to determine how many of each facility to build. The four types of facilities listed below are considered. The total demand has been estimated to be 7 gyms, 10 athletic fields, 8 tennis courts and 12 swimming pools. For each facility, the cost, number of hectares required and expected usage, are shown below.
Facility Cost (£millions) Required Hectares Expected Usage (people/week)
|
Gymnasium |
80 |
4 |
1500 |
|
Athletic field |
24 |
8 |
3000 |
|
Tennis court |
15 |
3 |
500 |
|
Swimming pool |
40 |
5 |
1000 |
The parks department has a total of 50 hectares of land for construction (although more land could be located if necessary). The council has established the goals listed below. The objective of the goal programming model is to minimize the deviation from these goals.
1. The parks department should spend the total £600 million (otherwise the amount not spent will be returned to the government).
2. The facilities should be used by 20,000 or more people weekly.
3. The parks department wants to avoid having to acquire land beyond the 50 hectares presently available.
4. If more land is required, the additional amount should be limited to 10 hectares.
5. The parks department would like to meet the estimated demand for each type of facility.
Write down all the required algebraic expressions to express the goal programming model for the above optimization problem. For each algebraic expression, make sure to explain parameters, decision variables and the rationale for the formulation.
[20 marks]
2022-08-12