Exercise Sheet 3
Q1. Alice is planning an active city break and is looking at discounted passes to attractions. She has decided that she wants to visit 3 ‘gold’ attractions and 4 ‘silver’ attractions, and to take 3 cruises. An ‘ultra’ pass grants access to 2 gold attractions, 2 silver attractions and 1 cruise, and costs e50; a ‘mega’ pass grants access to 1 gold attraction, 4 silver attractions and 2 cruises, and costs e40. This is summarised in the following table.
Gold Silver Cruise Cost Ultra 2 2 1 50 Mega 1 4 2 40
Required 3 4 3 Formulate (but do not solve) a linear program to minimise Alice’s cost.
Copyright By PowCoder代写 加微信 powcoder
Q2. Alice’s tourist agency buys its tickets from the management company of the attractions. By taking into account Alice’s demands, formulate (but do not solve) a linear program (in terms of the price per attraction) that maximises the price at which the management company may sell Alice’s tickets to the agency.
Q3. Solve the following linear programs graphically, indicating any binding or redundant constraints. (a) maxz=x1+3×2 subjectto
(b) maxz=x2+2×2 subjectto
(c) min w = y2 subject to
4×1 + 5×2 0, 8×1 3×2 56,
x1, x2 0.
x2 12, x1 + x2 19, 9×1 + x2 99,
x1, x2 0.
y1 + 2y2 15, y1 + 4y2 15,
y1 + y2 6, 2y1 + 11y2 55.
Q4. Solve the following linear programs using the primal simplex algorithm in tableaux form. (a) Maximise z = 3×1 + 4×2 subject to
x1 + 2×2 4, 2×1 x2 5, 3×1 5, x1, x2 0.
x1 + x2 + x3 4, 3×1 + x3 10,
x1, x2, x3 0. Max z = 2×1 + cx2
x1 + x2 d, x1 + kx2 5, x1 5, x1, x2 0.
(b) Maximise z = x1 2×2 + x3 subject to
Q5. Consider the following linear program:
subject to
Sketch the feasible region for c = 3, d = 1, k = 2, and answer the following questions using your sketch.
(a) For the given values of c, d, k, what are the optimal values of x1, x2, z?
(b) Keeping c = 3, k = 2 and increasing d, what is the smallest value of d such that x1 +x2 d becomes redundant?
(c) Keeping c = 3,d = 1 and decreasing k, what is the largest value of k such that x1 +ky 5 becomes redundant?
(d) Keeping d = 1, k = 2, for what range of c is the optimal solution (x1 , x2 ) unchanged?
Q1. Let y1 be the number of ‘ultra’ passes bought, and y2 be the number of ‘mega’ passes. The required program is
subject to
min w = 50y1 + 40y2
2y1 + y2 3, 2y1 + 4y2 4, y1 + 2y2 3, y1, y2 0.
Q2. Let x1, x2, x3 be the respective prices for Gold, Silver and Cruise attractions. The required program is max z = 3×1 + 4×2 + 3×3,
subject to
2×1 +2×2 +x3 50, x1 +4×2 +2×2 40,
x1, x2, x3 0.
The inequalities come from the fact that agency will not buy the product at a higher price than it sells
Q3. (a) The feasible region is as follows, with a z = constant line shown in red.
7 6 5 4 3 2 1
Hence the linear program is optimised at (x1,x2) = (10,8), with z = 34. We see that both of the
constraints
4×1 + 5×2 0, 8×1 3×2 56
are binding, and the redundant constraint is x1 0. 3
1 2 3 4 5 6 7 8 9 10
(b) This time, the feasible region with a z = constant line in red are as shown. x2
9 8 7 6 5 4 3 2 1
x1 1 2 3 4 5 6 7 8 9 10 11
According to the gradient of the z = constant line, the optimal solution is (x1,x2) = (7,12) with z = 31. The constraints
x2 12, x1 + x2 19
are binding. There are no redundant constraints (even though the constraint 9×1 + x2 99 is not binding, it still defines one of the boundary components of the feasible region so it is not redundant).
(c) Finally we have
6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10 11 12 13
Since we are minimising, the optimal solution is (y1 , y2 ) = (9, 3) with w = 3. The constraints y1 + 2y2 15,
y1 + y2 6, are binding. The constraint 2y1 + 11y2 55 is redundant.
On each iteration we mark the pivot in grey and proceed. On the first iteration, after choosing our pivoting column (with the most negative entry in the z row), the ratio test (dividing the value in the right-column and by the value in the pivoting column and seeing which is minimal) has one one legal possibility since only one entry in this column is positive.
x1 x2 x3 x4 x5
z 3 4 0 0 0 0 x3 1 2 1 0 0 4 x4 2 1 0 1 0 5 x5 3 0 0 0 1 5
The variable x2 becomes basic, the variable x3 becomes non-basic, so the first row operation is R2 := 12 R3 to force the pivot to equal 1. All other row operations are of the form Rj := Rj ↵iR3, where ↵i is chosen in such a way that all other entries in the pivoting row becomes 0 so that the new tableau is in canonical form. This time we have something to check with the ratio test: since 5/3 < 7/(5/2) < 2/(1/2), we get our pivot.
x1 x2 x3 x4 x5
z 1 0 2 0 0 8 x2 1/2 1 1/2 0 0 2 x4 5/2 0 1/2 1 0 7 x5 3 0 0 0 1 5
Then after similar operations to put the next tableau into canonical form we get
x1 x2 x3 x4 x5
z 0 0 2 0 1/3 29/3
x2 0 1 1/2 0 1/6 7/6 x4 0 0 1/2 1 5/6 17/6 x1 1 0 0 0 1/3 5/3
Since there are no more negatives in the z row, the optimal solution is (x1,x2) = (5/3,7/6) with z = 29/3.
Details are omitted from these calculations, but the algorithm is almost identical to the previous solution. However, we have more than one choice for the first step. Did you try to same as below? If so, try the other one. Do you get the same answer?
x1 x2 x3 x4 x5
z 1 2 1 0 0 0 x4 1 1 1 1 0 4 x5 3 0 1 0 1 10
x1 x2 x3 x4 x5 z030104 x3 1 1 1 1 0 4 x5 2 1 0 1 1 6
the given constants, the feasible region follows.
Hence we have compute that z = 4 is optimal, and this occurs when (x1, x2, x3) = (0, 0, 4). Does it occurs for any other value? Notice that x1 is a nonbasic variable, but its entry in the z row is 0. This means that increasing x1 shouldn’t change the answer. Try to make x1 a basic variable (replacing x3 or x5) and see what happens.
The optimal values are (x1, x2) = (3, 4), z = 6.
The line x1 + 2x2 = 5 (bounding a constraint) meets the axis at (0, 5/2). Hence if d increases to the point where x1 + x2 = d meets the axis at the same point, the corresponding constraint becomes redundant. That is, d = 5/2.
The lines x1 + x2 = 1 and x1 = 5 (bounding corresponding constraints) intersect at the point (x1,x2) = (5,6). If the value of k is reduced to the point where x1 +kx2 = 5 meets this intersection, then the corresponding constraint becomes redundant. That is, when k = 5/3.
As c decreases past the point that z =constant is parallel to x1 + x2 = 1, the optimal solution changes. This happens when c = 2. As c increase past the point that z =constant is parallel to x1 + 2x2 = 5, the optimal solution changes. This is when c = 4. Hence, for c 2 [2, 4], (x1 , x2 ) = (3, 4) is optimal. Note that z changes whenever c changes.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com