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 .
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com