Exercise Sheet 6
(i) Solve the following linear program using the dual simplex method. Min w = 2y1 + 3y2 + y3,
Consider the linear program subject to
A linear program is given by subject to
Copyright By PowCoder代写 加微信 powcoder
subject to
y1 + y2 5,
y2 + y3 6, y1, y2, y3 0.
(ii) Suppose this program is the dual program, and write down the corresponding primal program.
(iii) Write down all complementary slackness equations, and use these to find the solution of the primal program.
max z = 2×1 x2 + x3,
x1 + x2 3, x1 + x3 5, x1, x2 0.
(i) Write down the dual program and the complementary slackness equations.
(ii) Assuming that for an optimal solution not all variables are equal to zero, use only the comple- mentary slackness equations to find the optimal solution.
max z = x2,
5×1 + 6×2 32, 7×1 + 2×2 28,
Write down the dual program, and solve by making a substitution.
(This is the program for Q5 on Exercise Sheet 5, with the non-binding constraint removed.)
(i) We write the program as subject to
max w= 2y1 3y2 y3,
y1 y2 +y4 = 5, y2 y3 +y5 = 6,
y1,…,y5 0. We solve using tableaux and the dual simplex method.
y1 y2 y3 y4 y5
w 2 3 1 0 0 0
y4 1 1 0 1 0 5 y5 0 1 1 0 1 6
y1 y2 y3 y4 y5
w 2 2 0 0 1 6 y4 1 1 0 1 0 5 y3 0 1 1 0 1 6
y1 y2 y3 y4 y5
w 0 0 0 2 1 16
y1 1 1 0 1 0 5 y3 0 1 1 0 1 6
Hence the optimal solution is w = 16, which occurs when (y1, y2, y3) = (5,0,6) (note that there are other possible solutions).
(ii) The primal problem is subject to
max z = 5×1 + 6×2,
x1 2, x1 + x2 3, x2 1, x1, x2 0.
(iii) The complementary slackness equations are
(y1 +y2 5)x1 =0, (y2 +y3 6)x2 =0, (x1 2)y1 = 0, (x1 +x2 3)y2 =0, (x2 1)y3 = 0.
For (y1, y2, y3) = (5, 0, 6) this reduces to
(x1 2)y1 = 0,
giving (x1, x2) = (2, 1).
(x2 1)y3 = 0. 2
(i) The dual program is subject to
min w = 3y1 + 5y2,
y1 + y2 2, y1 1,
y2 1, y1, y2 0.
Hence the complementary slackness equations are
(x1+x2 3)y1 =0, (1) (x1+x3 5)y2 =0, (2) (y1+y2 2)x1 =0, (3)
(y1 + 1)x2 =0, (4) (y2 1)x3 =0. (5)
(ii) From (4) and y1 0 we have x2 = 0. The equations become
(x1 3)y1 = 0, (x1 +x3 5)y2 =0, (y1 +y2 2)x1 =0, (y2 1)x3 = 0.
Given that for an optimal solution z = w, and that not all variables are zero for an optimal solution, we conclude that y1 and y2 are not simultaneously zero for an optimal solution.
Suppose that y1 = 0. Then y2 6= 0 and the equations becomes
x1 +x3 5=0, (y2 2)x1 = 0, (y2 1)x3 = 0.
The first of these says that x1 and x3 can’t both be zero, but by x1 + x2 3, x3 6= 0. Hence y2 = 1 and the equations imply that x3 = 5, giving
(x1, x2, x3) = (0,0,5), (y1, y2) = (0,1). But y1 + y2 2 so this is infeasible.
Suppose that y2 = 0. Then y1 6= 0 and the equations become
x1 3 = 0, (y1 2)x1 = 0, x3 = 0.
Hencex1 =3andx3 =0,givingy1 =2. Sowehave,
(x1, x2, x3) = (3,0,0), (y1, y2) = (2,0).
However, we require y2 1 so this is infeasible. 3
Hence y1 6= 0 and y2 6= 0. Therefore the values of x1, x3 satisfy x1 3 = 0,
x1 +x3 5=0,
so that (x1, x2, x3) = (3, 0, 2) for an optimal solution. Hence the value of y1, y2 satisfy
y1 +y2 2=0, y2 1 = 0.
So (y1 , y2 ) = (1, 1) for an optimal solution. The optimal solution is z = w = 8. Q3. The dual program is
subject to
min w = 32y1 + 28y2,
5y1 7y2 = 0, 6y1 + 2y2 1, y1, y2 0.
We substitute y2 = 57 y1 so that the problem becomes
min w = 52y1
subject to
Since w is increasing, it achieves is minimal value (w = 7) when (y1 , y2 ) =
y1 7 . 52
7 5 52 , 52 .
Exercise Sheet 7
Q1. Consider the following transportation problem.
B1 B2 B3 B4
Find a basic initial feasible solution using each of the following algorithms:
(i) North-West Corner method. (ii) Least Cost method.
(iii) Vogel’s method.
Q2. Solve the following transportation problem starting with the given basic feasible solution.
Q3. Take the optimal solution from Q2, and show that it is optimal by setting u1 = ↵ rather than u1 = 0, and hence explain why it is always su cient to set u1 = 0.
Q1 We state the solutions. Note that in some cases other solutions are also acceptable since we may have to make arbitrary choices.
B1 B2 B3 B4
B1 B2 B3 B4
A2 10 A3 3
B1 B2 B3 B4
Q2 We solve as follows:
15 662 565 02
45 662 232 02
This table is dual feasible and hence optimal.
Q3 We have:
↵+2 ↵+3 ↵+2 ↵2
↵+1 7 ↵+1 5
Since whenever we compute vj ui the ↵ vanishes, it does not matter what value we take for ↵. Hence we may take ↵ = 0.
Exercise Sheet 8
Q1. Show that the following feasible solution is not basic.
A3 9 5 10 5
Q2. For the following unbalanced transportation problem, find an initial basic feasible solution and perform one iteration of the improvement algorithm.
A3 5 9 3 10
Q3. Show that the solution to the following transportation problem is optimal. Find another solution using the improvement algorithm. Are there any more solutions?
Q4. For what non-negative values of c is the following assignment optimal? B1 B2 B3
Q5. Four students are working on a group project. Anya has never studied Maple before. Ben and Deeta have, and it would take either of them 25 minutes to complete the Maple component. Chao is very experienced with Maple, and it would take him only 15 minutes. Deeta is struggling to understand the theory. Chao is the most fluent with the theory, having studied the material before, and it would take him 10 minutes to complete this section. Anya and Ben would take 15 and 25 minutes respectively. Ben and Deeta have practised lots of examples, and so it would only take either of them 10 minutes to complete the examples; but they’re not the strongest at word processing, and this would take either of them 25 minutes. Anya is quite good at examples: it would take her 15 minutes to complete this section. But Chao’s knowledge is much more theoretical, and it would take him 25 minutes to finish the examples. Both Anya and Chao are a little more familiar with word processing, and it would take either of them 20 minutes to write the project up.
It is Wednesday afternoon, so the students want to finish the project in the shortest possible time. Use the Hungarian Algorithm to determine which student should complete which task. How many di↵erent assignments give the same optimal solution?
Q1. Writing the assignment as a graph, we see that it is not connected. Hence it is not a spanning tree, and so the feasible solution is not basic. (Note: it is also not a spanning tree because it contains a non-trivial loop.)
Q2. We introduce a dummy buyer and solve. We have started below with the Least Cost Method, arbitrarily choosing the top right 0 as our least value. Choosing any of the three 0s in the right-hand column would work, but this choice is interesting as our improvement cycle is not just a square.
1 11 2 5
This solution is not optimal. We could go on to solve the problem, but we have already done what the question has asked.
Q3. To show optimality we show that the complementary slackness equations imply dual feasibility; i.e. none of the red entries below are negative. However, one of them is zero so we may apply the improvement algorithm to get an alternative basic optimal solution.
We have left ✓ undetermined after performing the improvement algorithm. If we take ✓ = 3 (as the improvement algorithm says we should), this will give another basic optimal solution. However, for any ✓ 2 (0, 3) we still get an optimal solution: just not a basic optimal solution.
Q4. We have:
Thisisoptimalprovidedthatc 5 0andc 3 0(thatis,whenc 5andc 3). Henceitis optimal when c 5.
Q5. We can form a cost matrix, with the rows corresponding to Anya, Ben, Chao and Deeta respectively, and the columns corresponding to the tasks Maple, theory, examples and writing up respectively:
We perform the standard operations: (1)
M 15 15 20 25 25 10 25 15 10 25 20 25 M 10 25
M 15 5 5 0 10 15 0 5 0 0 15 0 10 M 10 0 5
M 15 5 5 0 10 15 0 5 0 0 15 0 10M 10 0 5
M 20 0 5 0 5 10 0 5 0 0 20 5 5M 15 0 5
M 20 0 5 0 5 10 0 5 0 0 20 5 5M 15 0 5
M 20 0 10 0 0500 0 0 25 5 0M 20 0 0
(1) No change. (2)
(1) No change.
M 20 0 10 0 0500 0 0 25 5 0M 20 0 0
Since there need to be four lines to cover the zeros, we can find an optimal assignment of zeros and we stop the algorithm. The possible assignments are:
M 15 15 20 25 25 10 25 15 10 25 20 25 M 10 25
M 15 15 20 25 25 10 25 15 10 25 20 25 M 10 25
M 15 15 20 25 25 10 25 15 10 25 20 25 M 10 25
M 15 15 20 25 25 10 25 15 10 25 20 25 M 10 25
Exercise Sheet 9
Q1. Show directly from the definition that f(x) = x2 is a convex function.
Q2. In each case, compute the Hessian in order to find a subset of Rn on which f is convex.
(i) f(x,y,z)=xy+yz. (ii) f(x,y)=(x y)2.
(iii) f(x,y)=2×3 9×2 +12x+ey
Q3. Use Lagrange’s method to minimise
subject to
f(x,y)=3×2 2xy+2y2 2x 3y
x + y 1, x 3, y 5, x, y 0.
Q4. Use Lagrange’s method to find the minimal distance from the origin to a point on the curve with equation
x2 +xy 5=0.
Q1. This function is convex if for all x1, x2 2 R, and for all t 2 [0, 1], we have f tx1 + (1 t)x2 tf(x1) + (1 t)f(x2).
(i) The Hessian is
tx21 +(1 t)x2 tx1 +(1 t)x2 2 =t(1 t)(x1 x2)2 0,
1 01A Hf = 1 0 1 .
Then let’s subtract the left hand side from the right hand side (some details are omitted, but you should
as required. The final inequality comes from the fact that each term is non-negative.
The characteristic polynomial is 3 2 = ( 2 2), hence the eigenvalues are 0, ±p2. Since
there is always a negative eigenvalue, this function is not convex anywhere.
(ii) This time
Hf=✓2 2◆, 2 2
H =✓12x 18 0◆. f 0ey
the characteristic polynomial is 2 4 = ( 4), and hence the eigenvalues are 0 and 4. Since neither is negative, this function is convex everywhere.
This function is convex whenever the eigenvalues are non-negative. Since the Hessian is diago- nal, the eigenvalues are the diagonal entries. Since ey is always positive, the function is convex whenever 12x 18 0; i.e. when x 3/2.
Q3. The Lagrangian is
L(x,y, 1, 2, 3)=3×2 2xy+2y2 2x 3y+ 1(x+y 1)+ 2(x 3)+ 3(y 5).
The optimality conditions are
1(x + y 1) + 2(x 3) + 3(y 5) = 0, (8)
1, 2, 3 0. (9) Since the brackets appearing in (3), as well as x and y, are all non-negative, this condition becomes
Similarly from (8) we get
x(6x 2y 2+ 1 + 2)=0, y( 2x+4y 3+ 1 + 3)=0.
1(x + y 1) = 0, 2(x 3) = 0, 3(y 5) = 0.
(12) (13) (14)
Suppose 2 > 0. Then from (13) we have x = 3. But this contradicts (5), so
@L 0: @xj
6x 2y 2+ 1 + 2 0, (1) 2 x + 4 y 3 X+ 1 + 3 0 , (2)
x(6x 2y 2+ 1 + 2)+y( 2x+4y 3+ 1 + 3)=0, (3)
x, y 0, (4) @L 0:
x + y 1 0, (5)
x 3 0, (6) X y 50, (7)
Suppose 3 > 0. Then (14) says that y = 5. But we again get a contradiction from (5), so 3=0.
Suppose 1 =0. Thenifx=0,(1)impliesthat 2y 2 0,whichisacontradiction. Sox>0.
If y = 0 then (2) implies that 2x 3 0, another contradiction, so y > 0. So if we assume that 1 = 0, after having shown that 2 = 3 = 0, (10) and (11) become a system of equations in x and y that has solution x = 7/10, y = 11/10. But this contradicts (5). Hence 1 > 0, and from (11) we conclude that x + y 1 = 0.
Ifx=0theny=1,and(11)becomes1+ 1 =0,whichisimpossible. Sox>0.
If y = 0, then x = 1, and (10) becomes 4 + 1 = 0, which is another contradiction. We conclude that y > 0.
We now have the three equations, coming from (5), (10) and (11):
This system has the unique solution
which is the optimal solution.
x = 5/14, y = 9/14, 1 =16/14, 2 = 3 =0,
x + y 1 = 0, 6x 2y 2+ 1 =0, 2x+4y 3+ 1 =0.
Q4. Minimising the distance d is the same as minimising the distance squared d2 = x2 + y2. Hence we can take the Lagrangian to be
L(x,y, )=x2 +y2 + (x2 +xy 5). At a minimum point, rx,y, = (0, 0, 0). We compute:
Lx = 2x+ (2x+y), Ly =2y+ x,
L = x2 + xy 5.
Eliminating from the first two equations, we get
which rearranges to Solving for x,
x2 2xy y2 = 0.
x± = 2y±p4y2 +4y2 2
= ⇣1 ± p2⌘ y. Substituting into L and simplifying,
which gives
This gives an imaginary root if we choose , so we choose + and we have
⇣4 ± 3p2⌘ y2 5 = 0, y2= 5p.
y=±s 5p ,x=⇣1+p2⌘y
for the minimal distance. Both of these solutions give the same answer when substituted into d2. After simplification,
d2 =10⇣p2 1⌘ so the minimal distance is
d = r10 ⇣p2 1⌘ ⇡ 2. 5
Exercise Sheet 9
Q1. Consider the following constrained optimisation problem:
minimise f(x, y, z) = x2 + 2y2 + 4z2,
subject to
x + y 1. Use the method of barrier functions to solve this problem.
Q2. Consider the function
(i) Use one iteration of Cauchy’s Steepest Descent Method to find an approximation to the minimum,
f(x,y)=x4 2xy+5y2 x y. starting with the initial point x0 = (x0, y0) = (1, 0).
(ii) Use one iteration of the Barzilai–Borwein Gradient Descent Method to find the next approxima- tion.
Q3. Use one iteration of Newton’s method to minimise the function in Q2 using the same initial point.
Q1. The modified function is
F(x,y)=x2 +2y2 +4z2 rln( x y 1). Fx = 2x + r ,
x y 1 Fy = 4y + r
Fz =8z. x y 1
Hence the optimal point has z = 0. Computing Fx Fy = 0, we find y = x/2. Substituting into Fx
gives that
We may rearrange to get
2x r = 0. 3x/2+1
3×2 2x+r = 0,
x ± = 13 ± 31 p 1 + 3 r .
As r ! 0, the solutions are HOWEVER!
When we rearranged the function so that it became a quadratic, at some point we multiplied by 3x/2+1 and hence x = 2/3 is undefined for the modified function F . So why is this not a mistake? We know that F(x,y) models only the similar problem, to minimise f(x,y) subject to x + y < 1, and the constraint is actually binding for the problem that was posed. This demonstrates again that we have to think carefully when applying this method.
(x,y,z) = (0,0,0), (x,y,z) = ( 2/3, 1/3,0).
We check against the constraint to find that only (x, y, z) = ( 2/3, 1/3, 0) satisfies this constraint.
Q2. We calculate (i) Then
rf(x,y)= 4x3 2y 1, 2x+10y 1 .
0 =argminf(x0 rf(x0))
✓✓1◆ ✓ 3 ◆◆
=argminf 0 3 ✓1 3 ◆
= argmin f 3 432
= argmin 81 108 +117 18 .
Di↵erentiating with respect to , we find
81 4 108 3 +117 2 18 0 =324 3 324 2 +234 18=0.
This only has one real solution, ⇡ 0.0862, which is therefore the value of 0. So x1 = x0 0rf(x0)
=✓1◆ 0.0862✓ 3 ◆ ✓0 ◆ 3
= 0.7414 . 0.2586
x1 = x1 x0
= ✓0.7414◆ ✓1◆
✓0.2586 ◆ 0 = 0.2586 ,
f(x1) = rf(x1) rf(x0)
=✓0.1129◆ ✓ 3 ◆ ✓0.1032 ◆ 3
= 2.8871 , 3.1032
= 1.5491 17.9652
x2 = x1 1rfx1
= ✓0.7414◆ 0.0862 ✓0.1129◆
✓0.2586◆ 0.1032 = 0.7317 .
1 = h f(x1), x1i h f(x1), f(x1)i
✓ 2.8871◆ · ✓ 0.2586◆ = ✓ 3.1032 ◆ ✓ 0.2586 ◆
2.8871 · 2.8871 3.1032 3.1032
Q3. We calculate the Hessian and the gradient:
Hf =✓12x2 2◆, rf =✓ 4x3 2y 1 ◆.
At x0, Hence
2 10 2x + 10y 1 ✓◆✓◆
Hf(x0)= 12 2 , rf(x0)= 3 . 2 10 3
x1 = x0 (Hf (x0)) 1 · rf(x0) =✓1◆ 1✓5 1◆✓3◆
0 58 1 6 3
= 1 ✓46◆ 58 15
= ✓0.7931◆ . 0.2586
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com