University of Liverpool –
Question 1: (0 points) Question 2: (0 points)
When we have a multi-objective problem in which one of more of the constraints or objectives is non-linear, we can no longer rely solely on information about the vertices to find the feasible region in objective space.
Instead we need to map points individually from decision space to objective space. Often the easiest way to do this is by parametrising the points in decision space.
Copyright By PowCoder代写 加微信 powcoder
Consider the multi-objective problem
subject to
maximise 𝑧=𝑥+𝑥,𝑧=𝑥−𝑥
𝑥,𝑥 ≤1, 𝑥,𝑥 ≥0.
The feasible region in decision space is a square, and we can parametrise each component of the boundary using 𝑡 ∈ [0, 1].
The left-hand edge is given by points (0, 𝑡) for 𝑡 ∈ [0, 1]. Each such point maps to (𝑡, − 𝑡) in objective space.
That is, the image in objective space is the segment of the line 𝑧 = − 𝑧 between (0, 0) and (1, − 1).
The right-hand edge is given by points (1, 𝑡). Each such point maps to (1 + 𝑡, 1 − 𝑡). That is, the image is the segment of the line 𝑧 = 2 − 𝑧 between (1, 1) and (2, 0).
The bottom edge is given by points (𝑡, 0) for 𝑡 ∈ [0, 1]. Each such point maps to (𝑡, 𝑡) in objective space.
That is, the image in objective space is the segment of the curve 𝑥 = 𝑥 between the points (0, 0) and (1, 1).
The top edge is given by points (𝑡, 1). Each such point maps to (𝑡 + 1, 𝑡 − 1).
That is, the image is the segment of the curve 𝑧 = (𝑧 + 1) + 1 between (1, − 1) and (2,0
In this case it turns out that the NIS is linear, even though the problem as a whole is not. Let’s try using the same constraints but different objectives:
subject to
maximise 𝑧 = 𝑥 − 3𝑥, 𝑧 = 𝑥 + 𝑥
𝑥,𝑥 ≤1, 𝑥,𝑥 ≥0.
The point (0, 𝑡) maps to (−3𝑡, 𝑡).
That is, the image of the left-hand edge is the segment of the curve 𝑧 = − 3𝑧 between the
points (0, 0) and ( − 3, 1).
The point (1, 𝑡) maps to (1 − 3𝑡, 1 + 𝑡).
That is, the image of the right-hand edge is the segment of the curve 𝑧 = 1 − 3(𝑧 − 1) between the points (1, 1) and ( − 2, 2).
The point (𝑡, 0) maps to (𝑡, 𝑡).
That is, the image of the bottom edge is the segment of the curve 𝑧 = 𝑧 between the
points (0, 0) and (1, 1). Thepoint(𝑡,1)mapsto(𝑡−3,𝑡 +1).
That is, the image of the top edge is the segment of the curve 𝑧 = 1 + (𝑧 + 3) between the points ( − 3, 1) and ( − 2, 2).
Question 3: (0 points)
When we apply the weighting method, the principle being used is that we fix a value of 𝛾, and then search for the maximal constant 𝑐 such that the line
𝑍(𝑧,𝑧) = 𝑐
intersects the feasible region in objective space.
When the NIS was linear, we could identify the solution ‘by eye’. In more general cases we will not usually be able to do this, so we need a calculation-based approach to identify the correct solution.
Having fixed 𝛾, suppose that (𝑧 , 𝑧 ) is the point of the feasible region in objective space that maximises the value of 𝑍.
If the boundary of the feasible region is sufficiently differentiable at (𝑧 , 𝑧 ), then the line
𝑍(𝑧,𝑧) = 𝑐
will be tangent to this boundary curve.
We can calculate the slope of this line using implicit differentiation. Starting from
𝑐=𝑍=(1−𝛾)𝑧 +𝛾𝑧 and differentiating with respect to 𝑧, we find
0 = (1 − 𝛾) + 𝛾 𝑑𝑧 , 𝑑𝑧
𝑑𝑧 = 𝛾 − 1 . 𝑑𝑧 𝛾
Notice that this gives a negative slope for most values of 𝛾, which is as we would expect.
If 𝛾 = 0, the line 𝑍 = 𝑐 is vertical, as we are then maximising 𝑧.
If 𝛾 = 1, the line 𝑍 = 𝑐 is horizontal, as we are then maximising 𝑧.
Suppose that the feasible region in objective space for a bi-criterion problem is described by the constraints
𝑧 + 𝑧 ≤ 1 , 𝑧,𝑧 ≥0.
We can find the gradient of the boundary curve at points in the NIS using implicit differentiation:
1+2𝑧 𝑑𝑧 =0, 𝑑𝑧
𝑑𝑧 = − 1 . 𝑑𝑧 2𝑧
Comparing this with the slope from the weighting method, we find
−1=𝛾−1 2𝑧 𝛾
⇒ 𝑧= 𝛾 2(1 − 𝛾)
⇒ 𝑧 =1−4(1−𝛾).
For 𝛾 = 0,
which is as we would expect. For 𝛾 = 1/2,
Taking 𝛾 = 3/4 gives
(𝑧, 𝑧) = (1, 0),
(𝑧, 𝑧) = (3/4, 1/2) .
(𝑧, 𝑧) = ( − 5/4, 3/2),
which is not in the feasible region. What has gone wrong?
The points of the curve 𝑧 = 1 − 𝑧 are only part of the boundary of the feasible region for 0 ≤ 𝑧
As we increase the value of 𝛾, the corresponding optimal point moves along the NIS from (1, 0)
towards (0, 1). At what value of 𝛾 does it reach (0, 1)? 𝛾 𝛾
1−4(1−𝛾), 2(1−𝛾)=(0,1)
⇔𝛾=1 2(1 − 𝛾)
⇔ 𝛾 = 2 − 2𝛾 ⇔ 𝛾=23
When 𝛾 = 2/3, the maximal value of 𝑍 is 2/3, and the line 𝑍 ( 𝑧 , 𝑧 ) = 23
is tanget to the boundary of the feasible region at the point (0, 1).
Increasing 𝛾 further means we want to put a greater emphasis on maximising 𝑧 rather than 𝑧, but we have already reached the maximum possible 𝑧 value. Therefore changing 𝛾 in the range [ 2/3, 1] does not change the optimal solution.
(We cannot expect methods based on calculus to work well at this point, since the boundary of the feasible region is not differentiable at the corner.)
In summary, using the weighting method, the optimal point is
1 − , (−)
(−)
𝛾 ∈ 0, ,
𝛾 ∈ , 1 .
Question 4: (0 points) Question 5: (1 point)
When using the weighting method, the co-ordinates of the optimal point are continuous functions of 𝛾.
Question 6: (1 point)
If the feasible region in objective space is convex, and the objective functions are linear, then the feasible region in decision space is convex.
Question 7: (1 point)
When using the weighting method, the line 𝑍 = 𝑐 is tangent to the boundary of the feasible region at the optimal point.
Question 8: (1 point)
Sometimes adding a constraint to a problem does not affect the optimal solution.
Question 9: (1 point)
When solving a linear multi-objective problem using 𝜀 constraints and the simplex algorithm, each case we need to consider will give a different formula for the optimal point.
Question 10: (1 point)
We parametrise an edge of the feasible region in decision space using a parameter 𝑡, and map the points to objective space.
When we do this, the range of 𝑡 does not matter.
Question 11: (1 point)
We parametrise an edge of the feasible region in decision space using a parameter 𝑡, and map the points to objective space.
When we do this, we must take 𝑡 ∈ [0, 1].
Question 12: (1 point)
Using the 𝜀–constraints method, every point in the non-inferior set can be chosen as the optimal point.
Question 13: (1 point)
Using the weighting method, every point in the non-inferior set can be chosen as the optimal point.
Question 14: (1 point)
If the feasible region in decision space is convex, then the feasible region in objective space is convex.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com