Exercise Sheet 4
Q1. Solve the following linear programs using the Big M Method (and the primal simplex method with tableaux). In both cases you will need to multiply something by 1 before proceeding.
(i) Maximise subject to
(ii) Minimise subject to
Copyright By PowCoder代写 加微信 powcoder
Q2. The linear program subject to
is not feasible. Show this
(i) graphically,
(ii) using the Big M Method.
z = x1 + x2 + x3,
x1 +x2 +x3 10, x1 + x2 5,
x1, x2, x3 0. z = x1 + x2
x1 + 2×2 3, 3×1 x2 4, x1, x2 0.
Max z = 3×1 2×2,
3×1 + 7×2 49, 6×1 + x2 20, 2×1 + x2 13,
x1, x2 0
Q3. A craft shop sells beaded necklaces. For 1.50, they sell a necklace consisting of 10 blue beads, 10 red beads and 10 yellow beads. For 2.00, they sell a necklace consisting of 25 blue beads and 5 red beads. On a particular day, they take delivery of 500 blue beads, 150 red beads and 50 yellow beads.
(i) How many of each necklace should the craft shop make in order to maximise its income (assuming there is su cient demand for all of its products)?
(ii) The shop intends to increase its order of one colour by a small amount. Which colour should the shop order more of?
(iii) Use an appropriate shadow price to estimate the increase in income for 100 more yellow beads. Solve the linear program assuming 100 more yellow beads. Why do you get a di↵erent answer than your estimate?
(iv) Give an interpretation of the reduced cost of x1 and x2.
Q4. Consider the linear program
subject to
Max z = x1 x2
x1 + x2 15, 2×1 + 3×2 17,
x1, x2 0.
(i) Find the optimal solution using the primal simplex method with tableaux.
(ii) Hence determine the optimal solution when the objective function is replaced by z1 = (1 )x1 x2, for all real values of .
(iii) Dothesameforz2 =x1+( 1 )x2.
This becomes subject to
That is, subject to
The tableaux follow.
Max z = x1 + x2 + x3,
x1 +x2 +x3 10, x1 x2 5, x1, x2, x3 0.
Max z = x1 + x2 + x3 Mx6,
x1 +x2 +x3 +x4 10, x1 x2 x5 +x6 5, x1,…,x6 0.
x1 x2 x3 x4 x5 x6
z 1 1 1 0 0 M 0 x4 1 1 1 1 0 0 10
x6 1 1 0 0 1 1 5
Since this is not in canonical form, we rewrite by setting Rz := Rz M Rx6 .
x1 x2 x3 x4 x5 x6
z M+1 M 1 1 0 M 0 5M
x4 1 1 1 1 0 0 10 x6 1 1 0 0 1 1 5
x1 x2 x3 x4 x5 x6
z 0 0 1 0 1 M 1 5
x4 0 2 1 1 1 1 5 x1 1 1 0 0 1 1 5
x1 x2 x3 x4 x5 x6 z02012M 20 x3 0 2 1 1 1 1 5 x1 1 1 0 0 1 1 5
Hence the optimal solution is z = 0 which occurs when (x1, x2, x3) = (5, 0, 5).
(ii) Writing z0 = z, this becomes: subject to
So we get:
Max z0 = x1 x2
x1 + 2×2 3, 3×1 x2 4, x1, x2 0.
Max z0 = x1 x2 Mx4 Mx6 3
subject to
And in the tableaux:
x1 +2×2 x3 +x4 =3, 3×1 x2 x5 +x6 =4, x1,…,x6 0.
x1 x2 x3 x4 x5 x6 z110M0M0 x4 1 2 1 1 0 0 3 x6 3 1 0 0 1 1 4
Butthisisnotincanonicalform,sowesetRz =Rz MRx4 MRx6.
x1 x2 x3 x4 x5 x6
z 4M+1 M+1 M 0 M 0 7M
x4 1 2 11003 x6 3 1 0 0 1 1 4
x1 x2 x3x4 x5 x6
z 0 7M/3+4/3 M 0 M/3+1/3 4M/3 1/3 5M/3 4/3
x4 0 7/3 1 1 1/3 1/3 x1 1 1/3 0 0 1/3 1/3
ary of the ‘ ’ constraint is drawn in red. x2
x1x2x3 x4 x5 x6
0 0 4/7 M 4/7 1/7 M 1/7
The following graph indicates the feasible region bounded by the two ‘’ constraints. The bound-
x2 0 1 3/7 3/7 1/7 1/7 5/7 x1 1 0 1/7 1/7 2/7 2/7 11/7
Since the point satisfying the ‘ ’ constraint lie above and to the right of the red line, the feasible region is empty and so the problem is infeasible.
(ii) We write the program as: subject to
In tableaux:
Max z = 3×1 2×2 Mx6,
3×1 +7×2 +x3 =49, 6×1 +x2 +x4 =20, 2×1 +x2 x5 +x6 = 13,
x1,…,x6 0.
x1 x2 x3 x4 x5 x6
z 3 +2 0 0 0 M 0 x3 3 7 1 0 0 0 49 x4 6 1 0 1 0 0 20 x6 2 1 0 0 1 1 13
Since this is not canonical, we set Rz := Rz M Rx6 .
x1 x2 x3 x4 x5 x6
z 2M 3 M+2 0 0 M 0 13M
x3 3 7 1 0 0 0 49 x4 6 1 0 1 0 0 20 x6 2 1 0 0 1 1 13
x1 x2 x3 x4 x5x6
z 0 2M/3+5/2 x3 0 13/2
0 1/2+M/3 M 0 1 1/2 00 01/600 0 1/3 1 1
19M/3+10 39
z 0 0 5/13+4/39M 9/13+11M/39 M 0 7M/3 5
x2 0 1 2/13 1/13 0 0 6 x1 1 0 1/39 7/39 0 0 7/3 x600 4/39 11/39 117/3
Since the tableau is optimal but x6 6= 0, the linear program is not feasible. (i) We solve the linear program
subject to
Max z = 1.5×1 + 2×2,
10×1 + 25×2 500, 10×1 + 5×2 150,
10×1 50, x1, x2 0.
This becomes subject to
We proceed with tableaux.
Max z = 1.5×1 + 2×2,
10×1 + 25×2 + x3 = 500, 10×1 +5×2 +x4 = 150,
10×1 + x5 = 50, x1,…,x5 0.
x1 x2 x3 x4 x5
z 3/2 2 0 x3 10 25 1 x4 10 5 0 x5 10 0 0
x1 x2 x3 z 7/10 0 2/25 x2 2/5 1 1/25
0 0 500 1 0 150 0 1 50
0 0 40 0 0 20 1 0 50
x4 8 0 1/5
x5 10 0 0 0 1 50
x1x2x3x4 x5
z 0 0 2/25 0 7/100 87/2
x2 0 1 1/25 0 1/25 18 x4 0 0 1/5 1 4/5 10 x1 1 0 0 0 1/10 5
so we should make 5 of the cheaper necklaces and 18 of the more expensive necklaces.
(ii) The blue beads have the largest shadow price, so a small increase in the number of of blue beads will mean on average an increase in the objective function by 8p for each extra blue bead.
(iii) We use the shadow price of the yellow beads to estimate that 100 extra yellow beads will increase the income by 7. We have
x1 x2 x3 x4 x5
z 3/2 2 0 0 0 0 x3 10 25 1 0 0 500
x4 10 5 0 1 0 150 x5 10 0 0 0 1 150
x1 x2 x3 x4 x5
z 7/10 0 2/25 0 0 40 x2 2/5 1 1/25 0 0 20 x4 8 0 1/5 1 0 50 x5 10 0 0 0 1 150
x1 x2 x3 x4 x5
z 0 0 1/16 7/80 0 355/8
x2 0 1 1/20 1/20 0 35/2 x1 1 0 1/40 1/8 0 25/4 x5 0 0 1/4 5/4 1 175/2
(i) We have
The original optimal value added to the estimate is 87/2 + 7 = 50.5, whereas the new optimal is 355/8 = 44.4 These don’t agree as the shadow price is a nominal figure which only holds for small increases in the upper bounds of the constraints.
(iv) The reduced cost of both variables is 0. This means that requiring them to be slightly larger than zero (this constraint replacing the non-negativity constraint) has no e↵ect on the optimal solution. This is to be expected since neither variable is zero for the optimal solution.
x1 x2 x3 x4
z 1 1 0 0 0 x3 1 1 1 0 15 x4 2 3 0 1 17
x1 x2 x3 x4
z 0 5/2 0 1/2 17/2
x3 0 1/2 1 1/2 13/2 x1 1 3/2 0 1/2 17/2
So the optimal solution is z = 17/2 which occurs when (x1, x2) = (17/2, 0). (ii) The optimal tableau becomes
x1 x2 x3 x4
z1 5/2 0 1/2 17/2 x3 0 1/2 1 1/2 13/2 x1 1 3/2 0 1/2 17/2
Since this is not in canonical form, we set Rz := Rz Rx1 .
x1 x2 x3 x4
z1 0 5/2 3 /2 0 1/2 /2 17/2 17 /2 x3 0 1/2 1 1/2 13/2
x1 1 3/2 0 1/2 17/2
This is optimal provided That is,
5/2 3 /2 0, and1/2 /2 0. 5/3, and 1,
which implies simply that 1.
Suppose 1. Then we pivot on the most negative column, and get the following.
x1 x2 x3 x4
z1 0 5/2 3 /2 x3 0 1/2
z1 1+ 1 0 0 0 x3 1 1 1 0 15 x4 2 3 0 1 17
Hence for 1, the optimal solution is z1 = 0 which occurs when (x1, x2) = (0, 0). Since the z1 row contains no negative values for all 1, there are no more cases to consider.
(iii) The tableau is already in canonical form;
0 1/2 /2 17/2 17 /2 1 1/2 13/2
0 1/2 17/2
x1 x2 x3 x4
z2 0 5/2+ 0 1/2 17/2 x3 0 1/2 1 1/2 13/2 x1 1 3/2 0 1/2 17/2
It is optimal whenever 5/2 + 0, i.e. when 5/2. So suppose that 5/2.
x1 x2 x3 x4
z2 0 5/2+ 0 1/2 17/2 x3 0 1/2 1 1/2 13/2 x2 1 3/2 0 1/2 17/2
x1 x2 x3 x4
z2 5/3 2 /3 0 0 1/3 /3 17/3 17 /3 x3 1/3 0 1 1/3 28/3
x2 2/3 1 0 1/3 17/3
This tableau is optimal provided
5/3 2 /3 0, and 1/3 /3 0.
Since we already assumed that 5/2, this tableau is optimal.
5/2, and 1.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com