Math 340 Assignment 1 – Due September 29
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).
(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.
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
+2.5×3 −9×4
+5.5×2 +1.5×2
−57×2
−x4 .
+0.5×3
−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).
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).
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.
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 1
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!)
(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.
2