Week 8: Linear Programming: Solver

This week’s big question: last week you solved a 2-variable LP by graphing. Real problems have dozens of variables and constraints, far too many to draw. How do you solve those? You hand the same three ingredients to Excel’s Solver, but first you have to understand what makes a plan feasible and what Solver is actually doing.

Before the week

Read: Taylor, Introduction to Management Science (13e): Chapter 3, “Linear Programming: Computer Solution and Sensitivity Analysis,” pp. 97–104 (focus: solving an LP with Excel Solver and reading the answer report). The sensitivity half of the chapter is Week 9’s.
Warm-up self-check, recall the parts of an LP from Week 7:

Session 1: Mon, Oct 12 · From model to spreadsheet (TBD)

🧩 Puzzle

The tutoring nonprofit. Each week you schedule reading sessions ($x$) and math sessions ($y$). Each reading session delivers 2 impact points, each math session 3. Room A holds at most 4 reading sessions, Room B at most 5 math sessions, and you have volunteers for at most 7 sessions total. What weekly schedule maximizes impact?

Build the skill 1: what makes a plan feasible?

Before optimizing, you need to recognize a feasible plan: one that breaks none of the limits. Each constraint divides the plane into “OK” and “not OK”; a plan is feasible only if it is on the right side of every line at once. Drag the dot to try plans and watch which limits turn red:

The set of all feasible plans is the feasible region, the white polygon below. Every point inside it is a schedule you could actually run:

A 10-second feasibility check. You do not need a picture to test a single plan. Just substitute it into every constraint. Is the plan 3 reading, 5 math feasible? Check each limit: reading room $3 \le 4$ ✓, math room $5 \le 5$ ✓, volunteers $3 + 5 = 8 \le 7$ ✗. One violation is enough: the plan is infeasible, because eight sessions need eight volunteers and you only have seven. This plug-and-check drill is the whole idea behind the dragging widget, and it is exactly what checking feasibility by hand means.

Build the skill 2: the three cells Solver needs

Solver does for any number of variables what the graphical method did for two. Your spreadsheet needs three things, mapping one-to-one onto the LP you already know how to write:

LP part	In Excel
decision variables	changing cells: Solver adjusts these ($x$, $y$)
objective	objective cell, a formula `=2x + 3y` to maximize
constraints	a left-hand-side cell per limit, compared to its RHS

So the model is:

$\max\ 2x + 3y \quad \text{s.t.}\quad x \le 4,\;\; y \le 5,\;\; x + y \le 7,\;\; x, y \ge 0$.

Put it in standard form first. Solver and the algorithm behind it expect every constraint in standard form: all the variables on the left-hand side, all the constants on the right. That sounds automatic, but real word problems hide variables on the wrong side. Suppose a budget rule says “spending on math sessions must not exceed spending on reading sessions,” i.e. $30y \le 25x$. Before Solver can read it, move every variable left: $25x - 30y \ge 0$. (For the same reason a “constraint” like $x + y = z$, with a variable $z$ stranded on the right, is not in standard form until you rewrite it.) Tidying constraints this way is the step students most often trip on. Do it before you touch the spreadsheet.

Build the skill 3: a worked Solver demo (the 3D-print club)

The tutoring model is abstract on purpose. Here is a concrete, fully-worked production problem in the chapter’s classic two-products-from-two-scarce-resources shape. The kind of make-or-buy decision Solver is built for.

The campus 3D-print club sells two items at the maker fair: keychains ($x$, \$3 profit each) and phone stands ($y$, \$5 profit each). Each week the club has 20 printer-hours (a keychain takes 1 hour, a stand takes 2) and 36 grams of filament (a keychain uses 3 g, a stand uses 2 g). What mix maximizes profit?

The model is $\max\ 3x + 5y$ subject to printer-hours $x + 2y \le 20$ and filament $3x + 2y \le 36$, with $x, y \ge 0$. The three-cell setup is the same recipe as above:

Changing cells: two cells for $x$ and $y$, the quantities Solver will choose.
Objective cell: =3*x + 5*y, set to maximize.
Constraint rows: one LHS cell =1*x + 2*y compared to $\le 20$, and one =3*x + 2*y compared to $\le 36$ (plus $x, y \ge 0$).

Press Solve and Solver returns 8 keychains and 6 phone stands for \$54 profit, and at that plan both resources are used to the last unit ($8 + 12 = 20$ printer-hours, $24 + 12 = 36$ grams). Different numbers, different domain, identical skill: two products, two resources, one profit to maximize. That is the move you will repeat all term.

In practice: a model is only as good as its inputs

Where do the coefficients come from? “2 impact points per reading session” is an estimate. If it is really a range, your optimum may shift. Checking that is next session.
Whole numbers. Solver may answer “2.5 sessions.” If a fraction is meaningless, you need integer programming (a separate technique not covered in this course) not just rounding; rounding can break a constraint or miss the best plan.
The four quiet assumptions. Every LP rests on four things being true: proportionality (twice the sessions, twice the impact. No economies of scale), additivity (the total is the sum of the parts, with no interaction between $x$ and $y$), divisibility (fractional values are allowed), and certainty (the coefficients are known, not guessed). If returns diminish, if two activities interfere, or if your numbers are really rough estimates, the model can give a confident-looking answer that is wrong.
Write it algebraically. Solver reads ordinary linear expressions, not shorthand. A ratio constraint such as $x_1 / x_3 \le 2$ is not a form Solver accepts. Clear the fraction first ($x_1 \le 2x_3$, then $x_1 - 2x_3 \le 0$) so every constraint is a tidy sum of terms.

Back to the puzzle

You have translated words into a feasible region and the three Solver cells, and you can spot an infeasible plan in ten seconds by plug-and-check. You have not solved the tutoring LP yet, but you can now tell a valid schedule from an invalid one, which is half the battle.

In-class group practice (wrap-up)

To close Session 1, formulate a small LP together and map it onto Solver’s three cells. Write your group’s names on the sheet and hand it to your TA before you leave. It counts toward participation.

Download: Week 8 group practice (Word)

Session 2: Wed, Oct 14 · Solver finds: and explains: the optimum (TBD)

🧩 Puzzle

You press Solve and a schedule appears. How do you know Solver found the best one, and what does it tell you besides the answer?

Build the skill 1: Solver walks the corners

The optimum of an LP is always at a corner of the feasible region, so Solver does not check every point: it hops from corner to corner, always to a better one, until no neighbor improves. That systematic corner-walk has a name: the Simplex Method, the algorithm running quietly inside Solver. Press Walk corners to watch it, then Maximize to slide the objective line to that same corner:

The optimum is 2 reading and 5 math sessions = 19 impact points.

Build the skill 2: read the Answer Report

When Solver finishes it can print an Answer Report, a one-page summary in three sections. The Objective (Target) cell section gives the optimal value; the Variable (Adjustable) cells section lists what Solver chose; and the Constraints section reports, for each limit, its Status (Binding or Not Binding) and its Slack. Slack is the leftover (how much of a resource you did not use) so a binding constraint has slack 0 (used to the last unit) and a non-binding one has slack greater than zero. Here is what the report looks like for the tutoring optimum $(x, y) = (2, 5)$:

Section	Item	Value	Status	Slack
Objective cell	total impact	19	,	,
Variable cells	reading $x$	2	,	,
Variable cells	math $y$	5	,	,
Constraints	reading room $x \le 4$	2	Not Binding	2
Constraints	math room $y \le 5$	5	Binding	0
Constraints	volunteers $x+y \le 7$	7	Binding	0

Read it left to right: you ran 2 of an allowed 4 reading sessions, so the reading room has slack 2 (two unused slots) and is not your limit. The math room and the volunteers are both binding (slack 0): those are your real bottlenecks. This little table is exactly what the graded take-home asks you to read off in Excel, so practice naming the binding constraints and their slack here first.

Build the skill 3: what if a coefficient changes?

The optimum can jump to a different corner if a coefficient changes enough. Drag the impact-per-reading slider and watch the optimal corner switch:

Below an impact-per-reading of 3 the best plan favors math; above 3 it favors reading; at exactly 3 the two corners tie: both $(2,5)$ and $(4,3)$ score 21. That tie is not a coincidence: when the objective line runs parallel to a binding edge, every point along that edge is optimal. These are alternative optimal solutions, the textbook case where “the” optimum is really a whole segment of equally-good plans. (So “a linear program has exactly one optimal point” is false. A tie like this is the standard counterexample.) That sensitivity of the answer to the coefficients is sensitivity analysis: the subject of Week 9, previewed here.

In practice: read the report, not just the number

Infeasible / unbounded. If Solver says “no feasible solution,” your constraints contradict each other; “unbounded” means a constraint is missing. Both are modeling errors, not Solver bugs.
Binding ≠ important. A binding constraint limits you now; relaxing a non-binding one changes nothing. The reading room had slack 2, so renting a bigger reading room buys zero extra impact, spend effort on the right bottleneck.
A preview of shadow prices. What is one more unit of a binding resource worth? Add one volunteer session-slot (relax $x+y \le 7$ to $\le 8$): the optimum moves to $(3,5)$ and impact rises from 19 to 21, so that one extra slot bought 2 impact points. That number, 2, is the volunteer constraint’s shadow price, the marginal value of one more unit of your bottleneck. The reading room’s shadow price is \$0 (more of a slack resource is worthless). We compute and trust these next week.
The map is not the territory. Solver optimizes your model. If the model omits something real (equity, morale, a soft limit), the “optimal” plan may be a poor decision. Always sanity-check.

Back to the puzzle

Solver returns 2 reading, 5 math (19 points) and, in the Answer Report, names the two binding limits: the same answer the graph gives, but now it scales to 200 variables. Knowing why (which constraints bind, how much slack the others have, how sensitive the answer is) is what turns a number into a decision.

After-class check

Questions spanning feasibility, the Solver setup, standard form, reading the Answer Report, binding constraints and slack, and alternative optima. Retry freely; nothing is submitted.

Weekly take-home (graded: submit on Canvas)

This week’s take-home is an LP solved in Solver for a city public-works department planning a month of street repairs, and when you open the model sheet, nothing on it computes anything. In the Your model block you define the variables and write the objective and all three constraints from the brief, converting a labor pool quoted in worker-days, and name which cells will play Solver’s three roles. You then test one plan by hand, write the objective and constraint cells as live Excel formulas of your own, run Solver, and read its Answer Report to find which limits bind and which one has room to spare. One short recommendation plus the required AI-use disclosure go on the Free responses sheet. Upload the completed .xlsx on Canvas. That one file is your entire submission.

AI use. Tier 1: AI is allowed as a tool here, provided you disclose it on the Free responses sheet and can reproduce and modify the model unaided in the in-class check below. See Using AI.

Audit the AI’s model (optional practice: Tier 2)

A community health clinic asked an AI assistant to build a scheduling LP of its own. A separate case from your graded take-home. It produced a model, ran Solver, and recommended running no flu-shot clinics at all, and its model contains exactly one error. Download the companion workbook, find and fix the flaw, re-solve, and work out what the mistake would have cost the clinic.

Optional and ungraded, but it is excellent preparation for an in-class checkpoint, and the most realistic task in the course: in practice you will inherit someone else’s model far more often than you build one from scratch. AI is allowed and encouraged here (Tier 2. See Using AI).