Exercise Sheet 11
Q1. Consider the bicriterion problem: maximise
{z1 =−2x+3y,z2 =2x+y}
subject to
Copyright By PowCoder代写 加微信 powcoder
x − y ≤ 4, x + 3y ≤ 20, −2x + 5y ≤ 15,
(a) Find the vertices of the feasible region in both decision space and objective space. (b) Hence find the non-inferior set, and the ideal and nadir solutions.
(c) Use the weighting method to identify the optimal solution as a function of the weight parameter γ.
(d) Use the ε-constraint method to identify the optimal solution as a function of ε1, which is a lower bound for z1.
Q2. For the bicriterion problem in Q1, set the components of the ideal solution as targets for the objectives, and use the goal programming method to set up (without solving) a linear program to determine the optimal solution (assuming no penalties for overshooting, and uniform penalties for undershooting).
We solve pairs of equations simultaneously to get the vertices of the feasible region and construct the following table.
Objective Space Inferior To (0, 0) A, B
(9,3) – (5,15) – (−4, 20) –
Decision Space
(−8,8) B, C
(b) Hence the non-inferior set consists of the line segments between A and B and between B and C.
The ideal and nadir solutions are
z⋆ = (9, 20), ˆz = (−4, 3).
(c) We use the weighting method by introducing the objective function Z = (1 − γ)z1 + γz2,
where γ ∈ [0, 1].
For γ = 0, Z = z1 and this is maximised at A. The objective Z is maximised along the line segment between A and B when
5(1 − γ) + 15γ = 9(1 − γ) + 3γ,
i.e. when γ = 1/4. The objective Z is maximised along the line segment between B and C when −4(1 − γ) + 20γ = 5(1 − γ) + 15γ,
i.e. when γ = 9/14. Hence (using A − B to represent the line segment between A and B etc),
γ ∈ [0, 1/4)
γ ∈ (1/4, 9/14) γ = 9/14
γ ∈ (9/14, 1]
A A − B B B − C C
(d) We can deduce the following optimal solutions from the graph (or from the simplex tableaux). Each is computed by observing that the path follows a straight line, and calculating the linear equation that has the correct start and end points for the value of the parameter.
ε1 ∈(−∞,−4] ε1 ∈ [−4,5] ε1 ∈[5,9] ε1 ∈ (9, ∞)
Optimal (Decision) (8,4)
Optimal (Objective) (−4,20)
ε1, 160 − 5ε1 45 −5ε1,15 −1ε1 (ε1,30−3ε1)
Infeasible 2
20 − 1ε1, 40 + 1ε1
Q2. The required linear program is subject to
− 2 x + 3 y = 2x + y =
x − y ≤ x + 3y ≤ −2x + 5y ≤
9 − d −1 , 20 − d−2 ,
4, 20, 15,
x, y, d−1 , d−2 ≥ 0.
The word ‘uniform’ implies that the penalties α1− and α2− are equal, so we may just take them equal
to 1. We then find that the optimal solutions occurs when (x, y) = (5, 5).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com