2021 Mathematics 340 Homework 3 Due Friday, February 5th
Only part of the problems may be graded. But, you have to submit all the problems. Submit only pdf files.
When choosing an entering variable in the Simplex method, please follow
Anstee’s rule:
– Choose the entering variable with the largest positive coefficient.
– If there is a tie, then choose the one with the smaller subscript.
– If there is a choice of leaving variable, then choose the one with the smallest subscript.
1.
Consider the following linear program: Maximize: 2×1 − x2 + 3×3, subject to:
x1 +x2 +x3 ≤ 2 x1−x2 ≤−1 −x1 +2×2 −x3 ≤ 3,
andx1 ≥0,×2 ≥0,×3 ≥0.
(a) Set up the auxiliary problem, and find a basic feasible solution to the auxiliary
problem.
(b) Use the Simplex method to find a basic optimal solution for the auxiliary problem.
(c) Convert to a basic feasible solution for the original linear program and write down the dictionary for this basic feasible solution. (Do not solve for an optimal solution.)
6 marks
Solution: The auxiliary problem is: Maximize: −x0, subject to:
−x0 +x1 +x2 +x3 ≤ 2 −x0 +x1 −x2 ≤ −1 −x0 −x1 +2×2 −x3 ≤ 3,
andx0 ≥0,×1 ≥0,×2 ≥0,×3 ≥0. An infeasible dictionary is given by:
z= −x0
x4 = 2 x5 = −1 x6 = 3
x0 −x1 −x2 −x3
x0 −x1 +x2
x0 +x1 −2×2 +x3
Page 1 of 5
2021 Mathematics 340 Homework 3 Due Friday, February 5th
We do a special pivot with x0 entering and x5 leaving to get the feasible dictionary:
z = −1 +x5 −x1 +x2
x4 = 3 −x5 −2×2 −x3 x0 =1−x5+x1−x2
x6 = 4 −x5 +2×1 −3×2 +x3
We choose x2 entering because it has a smaller index than x5, and x0 is leaving so we get
z=0 −x0 x4=1+x5−2×1 2×0−x3 x2 =1 −x5 +x1 −x0
x6 = 1 +2×5 −x1 +3×0 +x3
This is optimal, so a basic feasible solution for the original problem is x1 = 0, x2 = 1, x3 =0,×4 =1,×5 =0,×6 =1.
The corresponding feasible dictionary for the original problem is:
z = −1 +x5 +x1 +3×3 x4 = 1 +x5 −2×1 −x3 x2 = 1 −x5 +x1
x6 = 1 +2×5 −x1 +x3
2.
Solve the following LP problem using the simplex method. At each step please state the entering and leaving variables and the current basic feasible solution. Clearly state the optimal solution and the optimal value.
Maximize z = 3×1 + 2×2 + 4×3, subject to
x1 +x2 +2×3 ≤ 4 2×1 +3×3 ≤ 5 2×1 +x2 +3×3 ≤ 7
and x1, x2, x3 ≥ 0. This problem requires 3 pivots. Note: this problem is Q2.1a from Ch ́avtal.
6 marks
Solution: Introduce slack variables and write in dictionary form
z = 3×1 +2×2 +4×3 x4 = 4 −x1 −x2 −2×3 x5 = 5 −2×1 −3×3 x6 = 7 −2×1 −x2 −3×3
Page 2 of 5
2021 Mathematics 340 Homework 3 Due Friday, February 5th
All the variables are potentially entering, but we pick the one with the largest co- efficient — so x3 is the entering variable. It is restricted to be at most 2,5/3,7/3 (respectively). So x5 is the leaving variable.
Pivoting gives
z = 20 +1×1 +2×2 −4×5 333
x3 = 5 −2×1 −1×5 333
x4 = 2 +1×1 −x2 +2×5 333
x6 = 2 −x2 +x5 The current feasible solution is
x1 = x2 = x5 = 0 x3 = 5 x4 = 2 x6 = 2 z = 20 333
Choose x2 to be the entering variable. It is constrained to be at most 2/3, 2 — so x4 is the leaving variable. Pivoting gives
z =8 +x1 −2×4
x2 = x3 = x6 =
So the current feasible solution is
2 +1×1 −x4 +2×5 333
5 −2×1 −1×5 333
4 −1×1 +x4 +1×5 333
x1 = x4 = x5 = 0 x2 = 2 x3 = 5 x6 = 4 z = 8 333
We only have 1 choice of entering variable — x1. It is constrained to be at most 5/2 or 4, so x3 is the leaving variable. Pivoting gives
z = 21 −3×3 −2×4 −1×5 222
x1 = x2 = x6 =
5 −3×3 −1×5 222
3 −1×3 −x4 +1×5 222
1 +1×3 +x4 +1×5 222
Since there are no negative coefficients in the expression for z we are done. The optimal solution is therefore
x1 = 5 x2 = 3 x3 = x4 = x5 = 0 x6 = 1 222
and the optimal value is z = 21 . 2
3. The following dictionary is obtained while solving a standard form LP problem
3 marks
Page 3 of 5
2021 Mathematics 340 Homework 3 Due Friday, February 5th by using the simplex method. What does this dictionary say about the original LP
problem? Explain your answer clearly.
z = 8 +x1 −2×4 +2×6 x2 = 12 −x1 +x4 +x6 x3 = 1 +x1 +x6 x5 = 4 +x1 +x4
4. (a) True/False question. Circle the right choice.
1) Every linear programming problem has an optimal solution. True / False
2) If the feasible region of a linear programming problem is unbounded, then the
Solution:
Letx6 =t. Then,whilekeepingx1 =x4 =0,wehavex2 =12+t,x3 =1+t,x5 =4+t is feasible and z = 8+2t, therefore, as t → +∞, z → +∞. This means that the LP problem is unbounded and has no optimal solution.
5 marks
2 marks
Solution:
1) False 2) False
(b)
linear programming problem does not have an optimal solution. True / False
Justify your answers above. Either prove it or give a counter example.
3 marks
Solution:
1) There are unbounded LPs having no optimal solution. For example,
maximize x subject to x ≥ 10,
has no optimal solution with the maximum value of the objective function the value of the objective function → ∞ as x → ∞.
2) No. For example,
maximize x subject to x ≤ 10,
has unbounded feasible region, but, it still has the optimal solution x = 10.
Page 4 of 5
2021 Mathematics 340 Homework 3 Due Friday, February 5th
5.
Consider an LP:
5 marks
max c·x
subject to Ax ≤ b and x ≥ 0.
Assume the LP has two optimal solutions u and v. Show that for any choice of λ ∈ [0, 1] (i.e. 0 ≤ λ ≤ 1), the point λu+(1−λ)v is also an optimal solution to the same LP. First show that λu + (1 − λ)v has the same value of the objective function as u. Then show λu + (1 − λ)v is a feasible solution to the LP.
Solution:
By the previous question, λu + (1 − λ)v is a feasible solution to the LP. Since u and
v are both optimal, then c · u = c · v. We compute
c · (λu + (1 − λ)v) = λc · u + (1 − λ)c · v = (λ + (1 − λ))c · u = c · u
using c · u = c · v.
To show that λu + (1 − λ)v is feasible we calculate
λu + (1 − λ)v ≥ 0
as both λ ≥ 0 and (1 − λ) ≥ 0, and similarly using the linearity of matrix-vector
multiplication
Aλu + (1 − λ)v = λAu + (1 − λ)Av ≤ λb + (1 − λ)b = b.
We conclude that λu + (1 − λ)v is an optimal solution since it is feasible and has the optimal value of the objective function.
Page 5 of 5