Linear Programming
5.1 Model Formulation and Graphical Solution: The Wyndor Case
Linear programming answers how to do the best under limited resources. This section uses the Wyndor Glass product-mix problem to work through four modelling steps and the graphical method.
Management Science and Linear Programming
Management science (or operations research) applies scientific methods to quantitative management problems. Linear programming is its most widely used class of model. Its defining features are:continuous decision variables and linear objectives and constraints.
Case: Product Mix at Wyndor Glass Co.
Wyndor has developed two new products: an 8-foot glass door with an aluminium frame and a 4×6-foot wood-framed window. The company has three plants:
- Plant 1 produces aluminium frames and components, with 4 available hours per week.
- Plant 2 produces wood frames, with 12 available hours per week.
- Plant 3 produces glass and assembles doors and windows, with 18 available hours per week.
The question:should the company introduce both products, and if so, what product mix is best?
| Resource | Required per door | Required per window | Available per week |
|---|---|---|---|
| Plant 1 (hours) | 1 | 0 | 4 |
| Plant 2 (hours) | 0 | 2 | 12 |
| Plant 3 (hours) | 3 | 2 | 18 |
| Unit profit (USD) | 300 | 500 | — |
Analysis: Start with Four Questions
- What decision are we making? How many doors and windows to produce each week—two decision variables.
- What is our objective? Maximise total profit: 300 × doors + 500 × windows.
- Which resources are needed and available? Production hours at three plants, with weekly limits of 4, 12 and 18 hours.
- Are there implicit restrictions? Production cannot be negative, so D ≥ 0 and W ≥ 0.
Four Steps in Spreadsheet Model Building
| Step | Action | Wyndor example |
|---|---|---|
| 1 Data cells | Enter all known data with consistent rows and columns | Unit profits, unit resource use by plant, available weekly hours |
| 2 Variable cells | Create one cell per decision variable; initialise at zero if needed | D (doors) and W (windows) |
| 3 Objective cell | Express the objective in one equation | =SUMPRODUCT(unit_profit, production) |
| 4 Constraints | Calculate resource use and write “requirement relation availability” for each resource | One row for each of the three plants |
Algebraic Model
Graphical-Solution Summary
- Draw the boundary line of each constraint and determine which side is feasible.
- Use all constraints to identify the feasible region.
- Determine the slope of one objective-function contour.
- Shift the contour toward higher objective values until it just touches the feasible region.
- The touching point is the optimal solution (always a corner point).
Four Modelling Questions: Decisions, Objective and Constraints
Classify each of the following five statements within the Wyndor model.
Read the Optimal Solution
Using the original data (door profit 300, window profit 500; plant capacities 4, 12 and 18 hours), find and enter the optimal solution.
5.2 Using Excel Solver
The graphical method teaches the logic, but real problems have dozens of variables and cannot be plotted. Use Excel Solver: give it the spreadsheet model you have already built and let it find the optimum.
Steps
- Define the objective and variable cells Under Data, select Solver; enter the objective cell, choose maximise or minimise, and select all variable cells under “By Changing Variable Cells.”
- Add constraints Select Add and enter the output cell, relation and available amount; do not forget non-negativity (or select “Make Unconstrained Variables Non-Negative”).
- Choose a solution method For linear programmes, select Simplex LP and enable “Assume Linear Model” in Options.
- Solve and read the results Solver writes the optimal values back to the variable cells and can generate Answer, Sensitivity and Limits reports.
The Solver Interface
The four screenshots below show the Solver interface, corresponding to the four steps above. You can follow them in sequence.
Dialog boxes differ slightly across Excel versions, but the steps and field names are the same.
A Common Trap: Solver Returns an Answer but Does Not Guarantee the Model Is Correct
- Solver faithfully finds the optimum of the model you wrote. If the model is wrong, it will still return a polished wrong answer.
- After solving, always check three things: whether constraints are sensible, whether units are consistent, and whether the answer makes business sense.
- If Solver reports “Solver could not find a feasible solution,” suspect incorrect or contradictory constraints before doubting the data.
5.3 Second Case: Profit & Gambit and Typical LP Problems
Case: The Profit & Gambit Advertising Mix
Management wants to advertise three key products—stain remover, laundry detergent and laundry powder—using television and print media. The targets are:
- stain-remover sales must rise by at least 3%; detergent by at least 18%; powder by at least 4%.
- The question:How can these minimum targets be achieved at minimum cost?
| Advertising medium | Stain remover (%) | Laundry detergent (%) | Laundry powder (%) | Unit cost (USD millions) |
|---|---|---|---|---|
| Television advertising (TV) | 0 | 3 | −1 | 1 |
| Print media (PM) | 1 | 2 | 4 | 2 |
| Required | ≥ 3 | ≥ 18 | ≥ 4 | — |
Typical Linear-Programming Problems
| Type | Structural feature | Example |
|---|---|---|
| Resource-allocation problem | resource used ≤ resource available | Wyndor product mix |
| Cost-benefit trade-off | achieved level ≥ minimum requirement; minimise cost | Profit & Gambit advertising mix |
| Blending problem | component-proportion constraints | ingredient, alloy and feed blending |
| Transportation problem | quantity supplied = quantity required | shipping from warehouses to stores |
| Assignment problem | total assigned = demand; total accepted = supply | staff scheduling and task assignment |
Recognising the problem type is useful: the same type has essentially the same model structure, with different data.
Case Discussion: Automobile Assembly (Textbook Case 2-1)
Automobile Alliance produces two models at one plant: the Family Thrillseeker (FT) and the Classy Cruiser (CC). Read the textbook case, discuss it in groups using the four questions—decisions, data, constraints and objective—and write the algebraic model.
Find the Optimal Advertising Mix
Using the Profit & Gambit model above, enter the optimal TV advertisements, print-media advertisements and minimum cost.
5.4 Sensitivity Analysis
Finding the optimum is only the first step. Managers must ask whether the conclusion still holds when parameters change. Sensitivity analysis answers “how far can a parameter change before the conclusion changes?”.
Changes in Objective Coefficients: When Does the Optimal Solution Move?
| Door profit | Optimal solution | Maximum profit | Explanation |
|---|---|---|---|
| 200 | D = 2, W = 6 | 3,400 | Optimum unchanged; profit is lower |
| 300 (original) | D = 2, W = 6 | 3,600 | Original optimum |
| 500 | D = 2, W = 6 | 4,000 | Threshold not yet reached |
| 1,000 | D = 4, W = 3 | 5,500 | Corner changes: doors become valuable enough to use all of Plant 1’s hours |
Changes in Resource Availability: Shadow Prices
The second part of a sensitivity report shows how much the objective can improve if one more unit of each resource is available—the shadow price. It answers whether one hour of overtime is worthwhile.
How to Read Shadow Prices
Using the original capacities (4, 12 and 18 hours), evaluate the following four statements.
5.5 AI-Assisted Modelling: Generate a Draft, Verify Every Line
AI can turn a natural-language description into a plausible-looking linear programme in seconds. It saves typing time and leaves a draft that must be checked line by line.
Prompt (using the five components)
Role: You are an operations-research modelling consultant.
Task: formulate the following production-planning problem as a linear programme.
Data: [paste the Wyndor case description exactly].
Output format: provide decision variables, objective function and constraints (including non-negativity), and list every assumption you make.
Constraint: do not omit any constraint; label every coefficient with its unit in parentheses.
Verification Checklist: Common Errors in AI-Generated Models
| Common error | Symptom | How to verify |
|---|---|---|
| Missing constraint | Writing capacity constraints but omitting non-negativity or demand constraints | Match each sentence in the case and count whether the constraints are complete |
| Reversed objective | Writing minimise when the problem is maximise | First ask: what are we maximising? |
| Inconsistent units | Mixing dollars and labour hours in one expression | Label the unit of every coefficient |
| Forgetting integer restrictions | Allowing fractional output without explanation | Ask: can this variable take a fractional value? |
| Unstated assumption | Assuming unlimited raw materials | Require AI to list every assumption |
Find the Problems in This AI Model Draft
Below is an AI-generated Wyndor model draft (a teaching example). Select a sentence to mark it as “problematic,” then select Check. The draft contains four problems.
Verification framework: are all decision variables present; is the objective maximise or minimise; are the number, direction and units of constraints correct; are assumptions stated?
5.6 Summary and Assignment
- Three components of a linear programme:decision variables, objective function and constraints.
- Four spreadsheet-model steps: data cells, variable cells, objective cell and constraints (using SUMPRODUCT to calculate outputs).
- The graphical method shows the feasible region and corners; Solver calculates the optimum, which always lies at a corner.
- Sensitivity analysis answers “how far can a parameter change before the conclusion changes?” via objective-coefficient ranges and resource shadow prices.
- Solver is responsible only for the model you wrote; if the model is wrong, it will still return a polished wrong answer.
Appendix: Interactive Demonstrations and Classroom Exercises
| Location | Type | Content |
|---|---|---|
| 5.1 | Demonstration | Wyndor graphical workbench: feasible region, isoprofit lines, corners and output cells |
| 5.3 | Demonstration | Profit & Gambit feasible region and minimum cost |
| 5.4 | Demonstration | Objective-coefficient changes: when the optimal corner moves |
| 5.4 | Demonstration | Shadow-price workbench |
| 5.1 | Exercise | Four modelling questions: decisions, objective and constraints |
| 5.1 | Exercise | Read the Optimal Solution |
| 5.3 | Exercise | Find the Optimal Advertising Mix |
| 5.4 | Exercise | How to Read Shadow Prices |
| 5.5 | Exercise | Four problem types in an AI model draft |
Data sources: model parameters from WyndorGlass.xlsx and Profit&Gambit.xlsx; the four interface images are original screenshots of Solver. Every optimal solution, shadow price and allowable range is calculated on the page by enumerating corner points and can be checked against Excel Solver.
Unit Glossary (English–Chinese)
| English | 中文 |
|---|---|
| Linear programming | 线性规划 |
| Decision variable | 决策变量 |
| Objective function | 目标函数 |
| Constraint | 约束条件 |
| Feasible region | 可行区域 |
| Binding constraint | 紧约束 |
| Shadow price | 影子价格 |
| Sensitivity analysis | 敏感性分析 |
| Simplex method | 单纯形法 |