Math 340 Assignment 1 Solutions.
Problem 1. Consider the following linear program: • Maximize 3×1 + 2×2 subject to:
◦ x1 − x2 ≤ −1
◦ x1 + x2 ≤ 1
◦ −2×1 + x2 ≤ −2 ◦ x1,x2 ≥0
(a) Use the two-phase simplex method on this linear program to prove it’s infeasible, writing out your dictionary and your choices of entering and leaving variables (and why) at each step. (I’d strongly suggest doing this one by hand – practice with the simplex method is a good thing.)
Solution. We start by inserting slack variables and setting up the initial infeasible dictionary, and then adding the extra variable x0 for the auxiliary problem.
z′ = −2
Now we pivot following the standard rule, letting x1 enter and x3 leave.
x3 = −1 −x1 +x2 x4 = 1 −x1 −x2 x5 = −2 +2×1 −x2
z′ =
We make our pivot to feasibility, letting x0 enter and x5 (the most infeasible slack variable) leave.
x0 = 2 x3=1 x4=3
+x0 +x0 .
+x0 −x0
−2×1 +x2 +x5 −3×1 +2×2 +x5 . −3×1 +x5 +2×1 −x2 −x5
x0 = x1 = x4 =
4 −1×2 +2×3 +1×5 3333
1 +2×2 −1×3 +1×5 3333.
2 −2×2 +x3
z′ = −4 +1×2 −2×3 −1×5
3333 Following the standard rule again, we let x2 enter and x4 leave.
x0 = 1 −1×3 +1×4 +1×5 263
x1 = 1 −1×4 +1×5 33.
x2 = 1 +1×3 −1×4 22
z′ = −1 −1×3 −1×4 −1×5 263
Thus we’ve reached an optimal solution for the auxiliary problem. Since z′ = −x0 maxes out at −1 (strictly less than 0) we conclude that the original problem was infeasible.
(b) Come up with a linear combination of the first three constraints that give an obviously-false inequality, not involving any variables, which proves again that the linear program is infeasible. (For an example of what I mean, if we had constraints x1 ≤ 1 and −x1 ≤ −2 then we could take 1 times the first inequality plus 1 times the second to get 0 = x1 + (−x1) ≤ 1 + (−2) ≤ −1, which is false). Your coefficients may look familiar from part (a) – we’ll see an explanation for these “magic coefficients” a bit later on in the course.
1
Solution. One way to do this is to take 1/2 times the first inequality plus 1/6 times the second plus 1/3 times the third:
0 = 1(x1 − x2) + 1(x1 + x2) + 1(−2×1 + x2) ≤ 1(−1) + 1(1) + 1(−2) = −1. 263263
The coefficients here are exactly the negatives of the ones that show up in the expression for z′ in our final dictionary! This will be explained later on as having to do with duality theory.
Problem 2. Consider the Chvátal’s example of a dictionary that cycles under the standard rule that we
looked at in class:
x5 = −0.5×1 x6 = −0.5×1 x7 = 1 −x1
z=10×1
+5.5×2 +2.5×3 −9×4 +1.5×2 +0.5×3 −x4 .
−57×2 −9×3 −24×4
Perform the simplex method but following Bland’s rule rather than the standard rule, and solve the given LP. At what step do the rules first start to differ? (Feel free to use a computer to help with the computations, but for each step write down which variables you choose to enter and exit and why, and the resulting dictionary).
Solution. Bland’s rule is that we always choose the entering variable to have the smallest subscript among all of those with positive coefficients in z, and the leaving variable having the smallest subscript among the ones that preserve feasibility (note this means the leaving variable is chosen the same way as the standard rule). For our initial dictionary, we choose x1 to enter and x5 to leave, and get
x1 = 11×2 +5×3 x6=−4×2−2×3 x7 = 1 −11×2 −5×3
z = 53×2 +41×3 We next choose x2 to enter and x6 to leave.
x1 = −0.5×3 +2×4
x2 = −0.5×3 +4×4
x7 = 1 +0.5×3 −4×4
z = 14.5×3 −98×4 For the next pivot we have x3 enter and x1 leave.
−18×4 +8×4 +18×4
−2×5 +x5 .
+18×4 −4×2
x3= 2×1
x4 = 0.5×1 −0.5×2 −0.25×5 −1.25×6 . x7 = 1 −x1
+2×5 −204×4 −20×5
−0.25×6
−2.75×6 . −13.25×6 −13.25×6
+2.5×6 −5.5×6 .
−93×6
−0.5×5
−9×2 +10.5×5 −70.5×6
+1.5×2 +0.5×3 −x6 −8×2 +2×3 +9×6 .
−93×2 −21×3 +24×6 2
x2= x1 x3 = −2×1 x7 = 1 −x1
z = −29×1 We choose x4 to enter and x2 to leave.
−2×4 +8×4
+0.25×5 +0.75×5 −0.75×5 −6.75×5
−0.5×5 +1.5×5
+15×5
+4.5×6
z = −20×1 We choose x5 to enter and x3 to leave.
x4 = −0.5×1 x5=4×1 x7 = 1 −x1
z=22×1
We then choose x1 to enter and x4 to leave (which is the place where Bland’s rule starts to differ from the standard rule!)
x1 = 3×2 +x3 −2×4 x5 = 4×2 +2×3 −8×4 x7=1−3×2 −x3
z = −27×2 +x3
We then choose x3 to enter and x7 to leave, which (finally) is a nondegenerate pivot and brings us to the
optimal dictionary.
x1 = 1 −x7 x3 = 1 −3×2 +2×4 +2×6 −x7 . x5 = 2 −2×2 −4×4 +5×6 −2×7
z = 1 −30×2 −42×4 −18×6 −x7
−2×6
+1×6 . +2×4 +2×6
−44×4 −20×6
Problem 3. Take the final (optimal) dictionary you got from Problem 2, and write out all of the pieces
that show up in the formula for the dictionary in matrix notation (as discussed in class on Monday): the
vectors of variables ⃗xB and ⃗xN , the matrices AB and AN , and the vectors ⃗b, ⃗cB and ⃗cN . Compute A−1⃗b B
and confirm this is the vector of constants in your dictionary, and compute ⃗c⊤A−1⃗b and confirm this is the BB
constant in your final expression of z. (This partially checks that our formulas do actually recover the final dictionary).
Solution.
From the last dictionary, x1 , x3 , x5 are the basic variables, so we take x1 x2
⃗xB= x3 ⃗xN=x4. x6
x5 x7
We get AB and AN by splitting up the augmented matrix [A|I] as appropriate, where A is the original
matrix of coefficients (which is the negative of the coefficients from the slack variables!)
0.5 −5.5 −2.5 9 1 0 0 [A|I]=0.5 −1.5 −0.5 1 0 1 0
1000001
0.5 −2.5 1 −5.5 9 0 0 AB=0.5 −0.5 0 AN=−1.5 1 1 0.
100 0001
Similarly we can read off ⃗b and the original vector ⃗c from the first dictionary, which we augment and split up into ⃗cB and ⃗cN according to the choice of basic variables:
0 ⃗b = 0
1
10 −57
−9 ⃗c = −24
0 0
0
10
−57
Finally, we compute A−1 using any method we want to get the inverse of a matrix (a calculator or computer B
is fine):
001 A−1=0 −2 1.
B
⃗c B = − 9
⃗c N =
1 −5 2 3
−24
0 0
0
Then since ⃗b is the third elementary basis vector, A−1⃗b is just the third column of this matrix: B
1 A − 1 ⃗b = 1
B
which is indeed the vector of constant terms in the constraints for our final dictionary. Finally,
1
⃗c⊤A−1⃗b= 10 −9 0 1 =10−9+0=1
B
2
Problem 4. Suppose that you start with a nondegenerate dictionary (all of the constant terms for the constraints are positive) and that after you pick the entering variable via the simplex method, there is not a tie for which variable should leave (so we don’t need to use the “smallest subscript” tiebreaker part of the standard rule). Is it possible for the resulting dictionary to be degenerate? Explain why or why not.
Solution. It cannot be degenerate; we can justify this by thinking about where the constants in the new dictionary come from. Suppose xi entered the dictionary and xj left. For the variable xi that just entered the dictionary, the constant is bj/(−aij) where bj was the constant for the equation for xj in the original dictionary, and aij was the (negative) coefficient of xi in that dictionary. By assumption the original dictionary is nondegenerate, bj > 0, so the new constant bj/(−aij) is also strictly positive.
Then look at the coefficients for the other variables xk that remained in the dictionary from the previous step. If they started with a constant bk and coefficient aik for xi, then after substituting in our new equation
which is the constant term in z in our final dictionary.
for xi the new constant will be
b +a bj . k ik −aij
2
Our assumption that the original dictionary was nondegenerate tells us that bj > 0. Then, go back to how the exiting variable was chosen to be xj: it was picked because we raised the value of xi as much as possible, and found the first basic variable to hit zero was xj, which would have happened when xi = bj/(−aij). Moreover our assumption that there was not a tie means that no other variable hit zero at the same time – so by definition substituting in xi = bj/(−aij) to our formula for xk must still give a positive value. But
making this substitution gives our new constant b + a bj k ik −aij
!
Problem 5. Suppose we have a linear program in standard form, which we write in matrix notation: maximize⃗c·⃗xsubjecttoA⃗x≤⃗band⃗x≥0(wherewefixam×nmatrixAandtwovectors⃗b∈Rn and ⃗c ∈ Rm, and treat ⃗x as a variable in Rn).
(a) Prove that if ⃗x1 and ⃗x2 are two feasible solutions for our constraint, then so is any weighted average of them:
t⃗x1 +(1−t)⃗x2 0≤t≤1.
The set of all of these weighted averages (for all values of t in [0, 1]) forms a line segment between ⃗x1 and ⃗x2. What you’ve proven says that anytime we have two points in our feasible region, the line segment between them is contained in the feasible region too; this is the definition of the feasible region being convex. (Note: You can prove this using algebraic manipulations, but make sure to justify why those manipulations are valid – especially ones involving inequalities of vectors!)
4
Solution. x1 and x2 being feasible means that we have x1,x2 ≥ 0 and Ax1,Ax2 ≤ b. Note that we can multiply an inequality of vectors by a nonnegative coefficient and keep the same inequality (because we can do this for coordinatewise for the real numbers we’re comparing); since 0 ≤ t ≤ 1 we have t, (1 − t) ≥ 0 and thus we can obtain all of the inequalities
tx1 ≥0 (1−t)x2 ≥0 A(tx1)=t(Ax1)≤tb A((1−t)x1)=(1−t)(Ax1)≤(1−t)b
(using that scalar multiplication can be brought inside of matrix multiplication). Next, we note we can add together two inequalities of vectors (of the same size) and get another inequality of vectors, again because we can do this coordinatewise for the real numbers. Adding together the first two inequalities above gives
tx1 +(1−t)x2 ≥0,
the first thing needed for this weighed average to be feasible. Adding together the last two and using that
matrix multiplication distributes over addition we have
Atx1 +(1−t)x2=A(tx1)+A((1−t)x1)≤tb+(1−t)b=b, which is the other thing needed to conclude it’s a feasible solution.
(b) Suppose that x1 and x2 are both optimal solutions to the given LP. Prove that any weighted average tx1 + (1 − t)x2 is also an optimal solution.
Solution. If both are optimal, then their values at the objective function c · x1 and c · x2 are equal to each other and to the optimum value zmax. Then, we can simply compute the value of the objective function at the weighted average, using basic rules for manipulating dot products:
c·tx1 +(1−t)x2=tc·x1 +(1−t)c·x2 =tzmax +(1−t)zmax =zmax,
which is again equal to the optimum value. (And we proved that the weighted average is a feasible solution in part (a)!)
5