Q1. Consider the linear program subject to
Exercise Sheet 5
max z = 7×1 + 3×2
3×1 x2 10, x1 + 3×2 15,
Copyright By PowCoder代写 加微信 powcoder
x1, x2 0.
(i) Solve this linear program using the primal simplex algorithm with tableaux.
(ii) Verify that ci = ci Pnj=1 aj,iyj for each i cPorresponding to a decision variable xi.
(iii) Verify that the optimal value satisfies z? = nj=1 bjyj.
(iv) Write the dual program, solve it (you might need to multiply some things by 1 before using the
Big M Method), and make similar verifications as in (ii) and (iii).
(v) Verify that the linear program and the dual program have the same optimal value.
Q2. State the dual to the following linear program, but do not solve it. Max z = 2×1 + x2 + x3,
subject to
x1 +x2 +2×3 3, x2 + x3 1, x1, x2, x3 0.
Q3. Explain why the following program is unbounded:
max z = 3×1 + x2,
subject to
x1 x2 0, x1, x2 0.
State what conclusions (if any) you can draw about the dual program.
Q4. Explain why the following program is infeasible:
max z = 2×1 + 2×2,
subject to
x1 + 3×2 7, 4×1 + 3×2 39,
x1, x2 0.
State what conclusions (if any) you can draw about the dual program.
Q5. A linear program is given by subject to
max z = x2,
5×1 + 6×2 32, 7×1 + 2×2 28, x1 + 6×2 13,
Solve this program graphically, noting that x1 is an unconstrained variable (that is, we don’t require x1 0). State the dual program.
(i) We have
x1 x2 x3 x4
z 7 3 0 0 0 x3 3 1 1 0 10 x4 1 3 0 1 15
x1 x2 x3 x4
z 0 16/3 7/3 0 70/3 x1 1 1/3 1/3 0 10/3 x4 0 10/3 1/3 1 35/3
x1 x2 x3 x4
z 0 0 9/5 8/5 42
x1 1 0 3/10 1/10 9/2
(ii) We verify
(iii) We verify
(iv) The dual program is
subject to
0 1 1/10 3/10 7/2 0 = 7 3(9/5) 1(8/5),
0 = 3 + (9/5) 3(8/5). 42 = 10(9/5) + 15(8/5).
min w = 10y1 + 15y2,
3y1 + y2 7, y1 + 3y2 3, y1, y2 0.
y1 y2 y3 y4 y5 y6
w 10 15 0 M 0 M 0 y4 3 1 1 1 0 0 7 y6 1 3 0 0 1 1 3
y1 y2 y3 y4 y5 y6
w 2M + 10 4M + 15 M 0 M 0 10M
y4 3 1 11007 y6 1 3 0 0 1 1 3
y1 y2 y3 y4 10M/3+15 0 M 0 10/3 0 1 1
M/3+5 4/3M 5 6M 15
1/3 1/3 6 y2 1/3 100 1/3 1/3 1
y1y2y3 y4 y5 y6
w 0 0 9/2 y1 1 0 3/10 y2 0 1 1/10
M 9/2 7/2 3/10 1/10 1/10 3/10
M 7/2 42 1/10 9/5 3/10 8/5
Then the dual program is subject to
Q3. The tableaux are:
min w = 3y1 y2,
y1 2, y1 y2 1, 2y1 y2 1.
z 3 1 0 0 x3 1 1 1 0
z 0 4 3 0 x1 1 1 1 0
0 = 10 + 3(9/2) 1(7/2),
0 = 15 + 1(9/2) + 3(7/2), 42 = 7(9/2) 3(7/2).
(Note the unusual signs – the coe cients aj,i are the negatives of how they appear in the tableau as we write this identity only for ‘’ constraints.)
(v) We observe that the optimal values coincide. Specifically, z? = w? = 42.
Q2. The given program is not in primal form, so we need to replace the ‘ ’ constraint with x2 x3 1.
Now there is no viable pivot and hence the program is unbounded (a graphical or algebraic argument is also acceptable). Since for any feasible solution zˆ to the primal program, and for any feasible solution wˆ to the dual program, we have zˆ wˆ (by the Weak Duality Property), the dual program is infeasible.
Q4. The tableaux are:
x1 x2 x3 x4 x5
z 2 2 0 0 M 0 x3 1 3 1 0 0 7 x5 4 3 0 1 1 39
x1 x2x3x4x5
z 4M+2 3M 2 0 M 0 39M
x3 1 3 1 0 0 7 x5 4 3 0 1 1 39
x1 x2 x3 x4 x5
z 0 9M 8 2 + 4M M 0 11M 14
x1 1 3 1 0 0 7 x5 0 9 4 1 1 11
Since the artificial variable x5 6= 0 in the optimal solution, the problem is not feasible (a graphical or algebraic argument is also acceptable). We may not make any conclusions about the dual program using the corollary of Weak Duality, as this corollary is an ‘if-then’ statement: just because a program is infeasible, doesn’t mean its dual is necessary unbounded. However, it does mean that the dual program has no optimal solution by the contrapositive of the Strong Duality Property, which states that a linear program has no optimal solution if and only if its dual program has no optimal solution.
Q5. Solving graphically:
So the optimal solution is z = 7 which occurs at (x1, x2) = ( 2, 7). We currently have no way to state the dual program for a program of this form; we only know how to do it when all variables satisfy a non-negativity constraint. We will cover the method for dealing with this next week. Why not try to figure it out for yourself first?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com