Week 7: Linear Programming: Formulation & Graphical Solution

This week’s big question: when resources are limited, exactly how much of each product should you make to earn the most? You will learn to turn that question into a linear program and solve it by hand, the foundation for everything in Weeks 8–11.

Before the week

• Read: Taylor, Introduction to Management Science (13e): Chapter 2, “Linear Programming: Model Formulation and Graphical Solution,” pp. 54–80 (focus: decision variables, objective, constraints; the graphical method and the feasible region). This is the one chapter all term whose whole body is on target, so read it straight through.
• Warm-up self-check: the one prerequisite the graph method needs (plotting lines and inequalities), plus a quick check on what makes an objective legal:

Session 1: Mon, Oct 5 · Formulating a linear program (TBD)

🧩 Puzzle

The corner bakery. Each morning you bake croissant batches and muffin batches. A croissant batch earns \$4 profit; a muffin batch \$3. But you are limited: the oven gives you 10 hours (2 h per croissant batch, 1 h per muffin batch), and you have 15 units of flour (1 per croissant batch, 3 per muffin batch). How many batches of each should you bake to make the most profit?

You cannot reliably eyeball this, and guessing wastes money. By the end of this session you will be able to write it as a model that can be solved exactly.

This little bakery is a toy stand-in for a serious idea. Linear programming (LP) is the workhorse behind production planning in factories, diet and feed blending on farms, fuel mixing at refineries, and portfolio mixes in finance. Billion-dollar scheduling problems that are, structurally, the same “use scarce resources to do the most good” question. Master the three ingredients on the bakery and the same skill scales to a plant with hundreds of products.

Build the skill 1: the three ingredients of every LP

Every linear program has the same three parts, and naming them (in order) is the skill. The order matters: you cannot write an objective or a constraint until you have decided what the variables are.

1. Decision variables (first, always). What you control. How much to make, buy, ship, or hire. Here, let x = croissant batches and y = muffin batches.
2. Objective. What you want to maximize (or minimize), as a linear expression: \(\text{maximize } Z = 4x + 3y \quad (\text{profit, dollars})\).
3. Constraints. The limits, as linear inequalities: \(2x + y \le 10 \;(\text{oven}), \qquad x + 3y \le 15 \;(\text{flour}), \qquad x \ge 0,\; y \ge 0.\)

The art is the translation: every per-unit number becomes a coefficient, every available total becomes a right-hand side (RHS), and “you cannot make a negative amount” becomes the non-negativity conditions \(x, y \ge 0\). So the bakery problem, stated precisely, is

\(\max\ 4x + 3y \quad \text{subject to}\quad 2x + y \le 10,\;\; x + 3y \le 15,\;\; x, y \ge 0\).

You do not know the answer yet (that is Session 2) but you have done the hard part. Formulation is about half of management science.

Build the skill 2: see the pattern twice (a second product mix)

The three-ingredient recipe is not special to bakeries. Watch it work on a completely different shop, with different units, and notice that the shape of the model is identical.

The print shop. You schedule poster runs (\(x\)) and sticker runs (\(y\)). A poster run earns \$90 profit and uses 3 press-hours and 2 ink cartridges; a sticker run earns \$70 and uses 1 press-hour and 4 cartridges. You have 24 press-hours and 32 cartridges available today.

Apply the recipe in order. Variables: \(x\) = poster runs, \(y\) = sticker runs. Objective: \(\max\ 90x + 70y\) (profit). Constraints: \(3x + y \le 24\) (press-hours), \(2x + 4y \le 32\) (cartridges), \(x, y \ge 0\). Same two-product, two-resource skeleton as the bakery, only the words and numbers changed. Every per-unit number landed as a coefficient; every daily total landed as an RHS. (For the record, this one optimizes at \(x = 6.4\) poster runs and \(y = 4.8\) sticker runs for \$912, and yes, fractional runs are a legal LP answer; the next box explains why.)

What counts as a legal LP

LP earns its power by assuming the world is linear and predictable. Four assumptions, in plain words:

• Proportionality. Doubling a batch doubles its profit and its resource use: no volume discounts, no economies of scale. That is why \(4x\), not \(4x^2\), can model profit.
• Additivity. Total profit is the sum of each product’s profit; products do not interact in the objective or the constraints.
• Divisibility. Fractional answers are allowed: 3.5 batches is a valid LP solution. If you truly need whole units, that is integer programming. A separate technique beyond this course’s LP weeks, not a reason to reject LP here.
• Certainty. The coefficients and RHS values are treated as known, fixed numbers.

One concrete rule follows from all this: an objective or constraint must be a plain weighted sum of the variables. Legal: \(5x + 3y + \tfrac{1}{3}z\). Illegal: \(5xy\) (a product of variables), \(5x/y\) (a ratio), \(x^2\) (a square). If you ever write a variable times or divided by another variable, you have left linear programming behind.

Back to the puzzle

You can now state the bakery problem precisely and know it is a legal LP, a plain weighted sum maximized over linear limits. You do not yet have the numbers \(x\) and \(y\), but you have something more reusable: a template you just applied to a second shop without breaking a sweat.

In practice: formulation is where the real errors hide

• Where do the coefficients come from? “\$4 profit per croissant batch” is an estimate. It bundles ingredient cost, labor, and a sale price that may move. Garbage coefficients give a confidently wrong plan.
• A missing constraint is the most dangerous error. If you forget the flour limit, the model happily recommends an impossible plan. Listing every scarce resource is the formulator’s real job.
• The model is not the world. LP optimizes what you wrote down. If freshness, staff morale, or a contract minimum matters and you left it out, the “optimal” plan can still be a bad decision. Sanity-check the answer.

In-class group practice (wrap-up)

To close Session 1, formulate a small LP together: no graphing yet, just the three ingredients on an original scenario. Write your group’s names on the sheet and hand it to your TA before you leave. It counts toward participation.

• Download: Week 7 group practice (Word)

Session 2: Wed, Oct 7 · Solving it on a graph (TBD)

🧩 Puzzle

Same bakery, same model. There are infinitely many plans that respect the limits: bake 1 and 1, or 2 and 3, or 0.5 and 4.8… Which one is best, and how can you be sure there is not a better plan you never tried?

Build the skill 1: the feasible region and the sliding profit line

With two variables you can see the answer. Each constraint is a line, and “≤” keeps one side of it. All the limits together carve out a feasible region. Every plan that is actually possible. The profit line \(4x + 3y = Z\) keeps the same slope for any profit \(Z\); raising \(Z\) slides it outward. The best plan is the last feasible point the line touches as you push profit up, and that is always a corner of the region.

Try it: drag the profit slider, then press Maximize and watch where the line stops:

The profit line leaves the region last at the corner where the oven and flour limits cross. That corner is x = 3 croissant batches, y = 4 muffin batches, giving Z = \$24, and the graph proves nothing can beat it.

Build the skill 2: the by-hand method when there is no slider

Away from the widget (on paper, or in an in-class checkpoint) there is no slider. The reliable hand procedure is the corner-point method: (A) plot the constraints; (B) list the corners of the feasible region; (C) read the \(x\) and \(y\) values at each corner; (D) compute the objective \(Z\) at each corner; (E) pick the best; (F) state the decision in words. Because the optimum is always a corner, checking the handful of corners is guaranteed to find it. For the bakery:

The biggest \(Z\) is 24 at \((3, 4)\), circle it. Stated in words: bake 3 croissant batches and 4 muffin batches for \$24 profit. That matches the animation exactly, and you can reproduce it with nothing but arithmetic. Drilling this procedure is exactly this week’s graded take-home: the same corner-point tables on three fresh LPs (a different bakery, a print shop, and a dining-hall blend) in the starter workbook linked in the take-home section below.

Slack: which resources are you using up?

At a corner, a constraint is either binding (used to the last unit) or has slack (leftover). Slack is just the gap between what you used and what you had, a leftover that contributes nothing to profit. Compare the two corners:

• At the optimum \((3, 4)\): oven slack \(= 10 - (2\cdot3 + 4) = 0\) and flour slack \(= 15 - (3 + 3\cdot4) = 0\). Both bind. Every oven hour and every unit of flour is spent. Best plans usually sit exactly where the tightest constraints meet.
• At the corner \((5, 0)\): oven slack \(= 10 - (10 + 0) = 0\) (binding), but flour slack \(= 15 - (5 + 0) = 10\). 10 units of flour sit unused. That idle flour is the price of an inferior plan.

That “leftover resource” is exactly what next week’s Solver reports as a slack variable. Keep the word in your pocket.

In practice: three ways an LP can surprise you

Most LPs have one tidy corner optimum, like the bakery. But the chapter warns about three irregular cases, and spotting them is a mark of real fluency:

• Multiple optima. If your profit line is exactly parallel to a binding constraint, a whole edge of plans ties for best. Any point on it is fine. The model is not broken; you simply have several equally good answers.
• Infeasible. If the limits contradict each other (demand a minimum output your resources cannot reach) the feasible region is empty and there is no plan. That is a sign your requirements need to give.
• Unbounded. If you forget a resource limit, the model can push profit up forever and reports infinite profit. That is never a real answer. It is a missing-constraint modeling bug.

A quick look at minimization (the other half of the chapter)

So far we have maximized profit against \(\le\) limits. Many real problems run the other way: minimize cost subject to requirements you must meet. Two things flip.

The dining-hall blend. A dining hall mixes two supplement powders to hit a nutrition target: Brand P costs \$5/scoop (3 g protein, 1 g fiber) and Brand Q costs \$3/scoop (1 g protein, 3 g fiber). Each serving needs at least 16 g protein and at least 12 g fiber.

The model is \(\min\ 5p + 3q\) subject to \(3p + q \ge 16\) (protein), \(p + 3q \ge 12\) (fiber), \(p, q \ge 0\). The two flips: (1) the constraints become \(\ge\) (meet at least the requirement), and (2) you slide the cost line inward, so the optimum is the feasible corner nearest the origin: cheapest, not richest. Drag the cost slider and press Minimize to watch the line slide toward the origin (mirror image of the max case):

For Solver’s standard form, a \(\ge\) requirement uses a surplus variable: subtract the amount above the minimum to turn the inequality into an equation. For example, \(3p+q-s_{\text{protein}}=16\) with \(s_{\text{protein}}\ge0\), where the surplus records protein beyond the required 16 g.

The optimum is where the two requirement lines cross, \(p = 4.5\) and \(q = 2.5\), for a cost of \$30. Always check the corners rather than assuming the crossing wins: the other feasible corners are \((0, 16)\) at \(5(0)+3(16)=\$48\) and \((12, 0)\) at \(5(12)+3(0)=\$60\), both dearer than \$30, so the intersection really is the cheapest blend. (On some problems the minimum sits at an axis corner instead, which is exactly why you check.) Same three-ingredient recipe, mirror-image geometry.

A preview: what if you cannot buy half a scoop?

That answer asked for 4.5 scoops of Brand P. Powder divides happily, so the blend is fine as it stands. But suppose the supplier switches to pre-measured sachets, and you can only buy whole ones. Every dot below is a whole-sachet blend that still clears both nutrition targets:

The tempting repair is to round, and it is worth seeing now that rounding is not reliable. Rounding down to \((4, 2)\) gives only \(3(4) + 2 = 14\) g of protein against a target of 16, so it is not a legal blend at all. Rounding up to \((5, 3)\) is legal but costs \$34. The cheapest whole-sachet blend is neither: it is \((4, 4)\) at \$32, which sits on the protein line exactly. Week 10 comes back to this properly, when the whole-number requirement is part of the model rather than an afterthought.

Back to the puzzle

The bakery’s answer is 3 croissant batches and 4 muffin batches, \$24 profit, found two ways that agree: the sliding profit line in the widget, and the corner-point table you can do by hand. Both limits bind, so there is no slack to spare, the plan squeezes every oven hour and every unit of flour.

Why this matters beyond two variables. Real problems have dozens of variables, far too many to graph. Next week we hand the same three ingredients to Excel’s Solver, which walks the corners for us and reports the slack on every constraint. The graph is your intuition for what Solver is doing under the hood.

After-class check

Questions spanning model formulation, reading the feasible region and corner points, slack, minimization, and the irregular cases (no feasible solution, unbounded, alternate optima). Retry freely; nothing is submitted.

Weekly take-home (graded: submit on Canvas)

This week’s take-home is two linear programs from two briefs (one maximization for a campus recycling center, one minimization for an animal shelter’s feed blend) and neither model is written down for you. In the Your model block you define the variables with their units and write the objective and every constraint from the narrative, converting one capacity that arrives on the wrong time basis. Then you graph each region and enumerate its corners yourself: no corner is named for you, and on the minimization the point where the two lines cross is not the answer. You also identify the constraint that turns out not to matter at all, and the surplus on a minimum the cheapest mix over-delivers. There is no Solver this week. That is Week 8. Two short responses 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.