E Answers to Learning Checkpoints

Contents | ‹ Previous | Next › | Download EPUB | PDF

Answers to Learning Checkpoints

The Learning Checkpoint boxes throughout the book are meant to be attempted before reading on, and certainly before reading this appendix. Try to write your answer down first; comparing your own words against the answer is where the learning happens.

Checkpoint 2.2.1. Proportionality, additivity, and certainty are reasonable here: profit and resource use scale with production, and the data are treated as known. Divisibility, however, is violated: you cannot print $\frac{2}{3}$ of a t-shirt. The linear program is still a useful model: when production quantities are large, rounding a fractional plan changes little, and when whole-number answers truly matter, integer programming (Part III) adds that requirement explicitly.

Checkpoint 5.3.1. Maximizing: infinitely many. The level lines $4 x + 2 y = c$ are parallel to the constraint boundary $2 x + y = 4$ , so the maximum $c = 8$ is attained along the entire edge from $(1.5, 1)$ to $(2, 0)$ ; every point of that edge, not just its endpoints, is optimal. Minimizing: exactly one, the origin $(0, 0)$ with $c = 0$ .

Checkpoint 4.0.1. The index $j$ appears in $y_{i j}$ but is never defined: the sum runs over $i$ , leaving $j$ free. The statement needs a quantifier, e.g. $\sum_{i \in I} y_{i j} = 1 for all j \in J,$ which is not one constraint but one constraint per element of $J$ .

Checkpoint 7.1.1. At most $m$ , the number of linearly independent equality constraints. In a basic solution the $n - m$ nonbasic variables are set to zero, so only the $m$ basic variables can be nonzero, and under degeneracy some of those are zero as well.

Checkpoint 7.4.1. The ratio test identifies which basic variable reaches zero first as the entering variable increases. If you instead pivot on a row with a larger ratio, the entering variable rises past the point where the tighter row’s basic variable hits zero, driving that variable negative. The algebra still produces a basic solution, but one that violates nonnegativity, hence infeasible.

Checkpoint 7.5.1. Because at this point the artificial variable is nonbasic and equal to zero, the original constraints are satisfied without any help from it. Deleting its column therefore removes no feasible solutions of the original problem; keeping it could only allow it to re-enter the basis, which would defeat its purpose.

Checkpoint 10.2.1. The shadow price is $1$ : each extra hour raises the optimal profit by $1. It is valid for $7 \leq b_{1} \leq 10$ (that is, $- 2 \leq Δ \leq 1$ ). At $b_{1} = 10$ the basic variable $s_{2}$ reaches zero, the optimal basis changes, and beyond that point the marginal value of additional hours is set by a different basis: the price of $1 expires.

Checkpoint 10.3.1. Both statements are true on different sides of the allowable range. While the perturbed reduced cost stays nonpositive, the current solution remains optimal and unchanged: the variable stays out of the basis. Push the coefficient past the range boundary and the reduced cost turns positive: the variable now improves the objective, enters the basis, and a new optimal solution (with that variable positive) takes over. “Never changes the current solution” holds only within the range; the basis change happens at its edge.

Checkpoint 11.1.1. With $y_{1} = 3, y_{2} = 0$ : the dominance conditions read $3 + 0 = 3 \geq 3$ and $3 + 0 = 3 \geq 2$ , both satisfied, giving the bound $4 (3) + 5 (0) = 12$ . With $y_{1} = 1, y_{2} = 1$ : conditions $1 + 2 = 3 \geq 3$ and $1 + 1 = 2 \geq 2$ hold, giving the bound $4 (1) + 5 (1) = 9$ . The second certificate is better (smaller). No certificate can do better: $y = (1, 1)$ is optimal for the dual, and indeed the primal optimum $(x_{1}, x_{2}) = (1, 3)$ achieves profit $9$ , so by strong duality the bound is tight.

Checkpoint 11.3.1. The dual is a maximization problem, $\max b^{⊤} y$ s.t. $A^{⊤} y \leq c$ , $y \geq 0$ . The dual variables are sign-restricted ( $y_{i} \geq 0$ ) because the primal constraints are inequalities, and the dual constraints are inequalities ( $\leq$ ) because the primal variables are sign-restricted. Only equalities in the primal produce free dual variables, and only free primal variables produce dual equalities.

Checkpoint 11.5.1. Complementary slackness forces the shadow price of flour to be zero. Economically: if flour is already left over at the optimum, an extra unit of flour is worth nothing; it would just sit unused, so the marginal value of the resource is $0.

Checkpoint 14.3.1. (a) 5 vertices and 10 edges: every pair of cities is connected, so this is the complete graph $K_{5}$ . (b) Yes, it is connected. (c) The degree of LA is 4. (d) Seattle–Dallas–Atlanta is a path: no vertex repeats and it does not return to its start. (e) LA–Chicago–Dallas–LA is a circuit: it starts and ends at the same vertex.