Optimization and Resource Allocation

Introduction

Organizations rarely have unlimited labour, capital, equipment, time, inventory, or managerial attention. Business analytics therefore involves not only predicting what may happen, but also determining how scarce resources should be allocated among competing activities. Optimization provides a systematic framework for making such decisions.

A typical optimization problem asks: which decisions produce the greatest benefit, lowest cost, or best service level while satisfying operational restrictions? Examples include deciding a product mix, assigning employees to shifts, routing deliveries, selecting projects, allocating advertising expenditure, and scheduling production.

Linear programming (LP) is the most important introductory optimization method because it represents many practical decisions using linear relationships. Transportation and assignment models are specialized LP structures, while integer programming is required when decisions involve indivisible units, such as opening a warehouse or purchasing a whole number of vehicles.

Learning Objectives

By the end of this chapter, you should be able to:

1. Translate a business situation into decision variables, an objective function, and constraints.
2. Solve small linear programming models graphically and interpret the solution.
3. Explain feasible regions, binding constraints, slack, surplus, and shadow prices.
4. Use spreadsheet or optimization software responsibly to solve and validate models.
5. Conduct basic sensitivity analysis.
6. Formulate transportation, assignment, and integer programming models.
7. Recognize modelling assumptions, limitations, and ethical risks.

1. The Structure of an Optimization Model

An optimization model has four core components:

• Decision variables: quantities controlled by the decision-maker.
• Objective function: a mathematical expression to maximize or minimize.
• Constraints: restrictions imposed by resources, policies, demand, or technology.
• Parameters: known numerical values such as unit profit, capacity, cost, or processing time.

A general linear programming model is:

Here, x_j is decision variable j, c_j is its objective coefficient, a_ij is the amount of resource i used by one unit of activity j, and b_i is the available amount or required level of resource i. The objective value is Z. Coefficients must be measured in compatible units.

The model is linear when variables are multiplied only by constants, added, or subtracted. Expressions such as 5x₁ + 3x₂ are linear; x₁x₂, x₁², and percentage discounts that depend on quantity are not linear without further reformulation.

A disciplined formulation process

1. Define the decision to be made.
2. Choose one variable for each independent decision quantity.
3. State the objective in words before writing mathematics.
4. Translate every relevant limitation into an inequality or equality.
5. Add non-negativity, integrality, or binary restrictions where appropriate.
6. Check units, signs, and whether the model permits unrealistic solutions.
7. Validate the model with managers or process experts.

Example: product mix

A bakery produces standard and premium gift boxes. Let:

• x₁ = number of standard boxes produced per day;
• x₂ = number of premium boxes produced per day.

Suppose contribution margins are $18 and $30 per box. Each standard box uses 2 minutes of assembly and 1 unit of packaging material. Each premium box uses 3 minutes and 2 units. Daily capacity is 240 assembly minutes and 120 packaging units. The model is:

The objective is measured in dollars per day. Each constraint has consistent units: minutes in the first and packaging units in the second.

2. Feasibility and the Graphical Method

A feasible solution satisfies every constraint and variable restriction. The set of all feasible solutions is the feasible region. In a two-variable LP, each inequality can be drawn as a half-plane. Their intersection is the feasible region.

For a maximization or minimization LP with a non-empty bounded feasible region, at least one optimal solution occurs at an extreme point, also called a corner point. This is the basis of the graphical method and reflects a fundamental property of linear programming.

For the bakery model, the boundary lines are:

The intercepts are:

• Assembly line: (120, 0) and (0, 80).
• Packaging line: (120, 0) and (0, 60).

The intersection of the two constraints is found by solving simultaneously. From the packaging equation, x₁ = 120 - 2x₂. Substitution gives:

In this particular example, the two lines meet at (120, 0), and the packaging constraint is more restrictive than assembly throughout the relevant first-quadrant region. The feasible corner points are therefore (0, 0), (120, 0), and (0, 60). Objective values are:

The optimal plan is 120 standard boxes and zero premium boxes, with daily contribution of $2,160. This result may seem surprising if premium boxes have a higher unit margin. The relevant comparison is contribution per scarce packaging unit: standard boxes provide $18 per unit, whereas premium boxes provide $15. Optimization evaluates resource productivity, not unit margin alone.

Graphical interpretation

A contour, or iso-profit, line contains combinations producing the same objective value. Moving this line outward for maximization, the last point touching the feasible region is optimal. Graphical analysis becomes difficult beyond two decision variables, but its logic remains central to software-based optimization.

3. Interpreting Constraints and Solutions

A constraint is binding when it holds as an equality at the optimum. Its unused capacity is zero. A non-binding resource has slack.

For a “less than or equal to” resource constraint:

For a “greater than or equal to” requirement, surplus is:

In the bakery solution (120, 0), assembly use is 240 minutes and packaging use is 120 units. Both constraints are binding, so both have zero slack. If a constraint were 2x₁ + 3x₂ ≤ 300, its slack at the solution would be 60 minutes.

Shadow prices

The shadow price of a resource is the change in optimal objective value associated with a one-unit increase in the right-hand side of a constraint, provided the change remains within the valid sensitivity range and the current optimal basis does not change. It is an opportunity value, not necessarily a market price.

Shadow prices are meaningful only under assumptions such as linearity, stable coefficients, and a sufficiently small change. A resource with positive unused capacity often has a zero shadow price in a maximization model, because obtaining more of it does not improve the current objective.

Multiple, infeasible, and unbounded solutions

• Multiple optimal solutions: two or more feasible points produce the same best objective value. Every point on the connecting edge is also optimal.
• Infeasibility: no solution satisfies all constraints. Causes include contradictory requirements or incorrect units.
• Unboundedness: the objective can improve indefinitely. This often indicates a missing capacity, demand, or non-negativity restriction.
• Degeneracy: more constraints bind at a corner than are needed to define it. Degeneracy can complicate sensitivity interpretation.

4. Sensitivity Analysis

An optimization result is not a permanent truth. Costs, margins, capacities, demand forecasts, and processing times may change. Sensitivity analysis examines how such changes affect the solution.

Objective-coefficient changes

An objective coefficient is the contribution associated with one unit of a decision variable. If a product’s margin changes, the current production plan may remain optimal over a range. The allowable range is determined by comparing the slope of the objective line with slopes of binding constraints. Software commonly reports an allowable increase and decrease.

A change outside the allowable range does not automatically invalidate the model; it means the model should be re-solved because the optimal basis may change.

Right-hand-side changes

Changing a constraint’s right-hand side changes resource availability or a minimum requirement. Within the allowable range, the shadow price estimates the objective change:

This relationship is local. It should not be extrapolated far beyond the reported range, especially when constraints become non-binding or the model becomes infeasible.

What sensitivity analysis cannot do

Sensitivity reports generally examine one parameter at a time while holding others constant. They do not automatically account for correlated changes, uncertain forecasts, nonlinear effects, or managerial reactions. Scenario analysis, simulation, robust optimization, or stochastic programming may be more appropriate when uncertainty is substantial.

5. Solving Models with Spreadsheets and Software

A spreadsheet implementation normally contains:

1. input cells for coefficients and capacities;
2. changing cells for decision variables;
3. formula cells for resource usage and objective value;
4. a solver configuration specifying maximize or minimize, variable cells, constraints, and non-negativity;
5. an output section showing solution values, slacks, and sensitivity information where available.

Dedicated tools such as Excel Solver, OpenSolver, Python optimization libraries, R packages, and commercial solvers can handle larger models. The software should be treated as a computational engine, not as a substitute for formulation and judgement.

Professional validation checklist

• Are all variables clearly defined?
• Are units consistent?
• Are costs, revenues, and contribution margins distinguished?
• Are fixed costs included only when they affect the decision?
• Does every real limitation appear as a constraint?
• Are variables permitted to take fractional values appropriately?
• Is the solver status optimal, feasible, or otherwise qualified?
• Do calculated resource totals satisfy constraints after rounding?
• Has the result been tested under plausible scenarios?
• Can a manager explain why the recommended solution makes sense?

Rounding requires care. A software solution of 14.6 vehicles is not implementable if vehicles are indivisible. Rounding down may restore feasibility but may not be optimal; the rounded plan must be rechecked and, if necessary, optimized as an integer model.

6. Transportation Models

A transportation model determines how much product to ship from each origin to each destination at minimum cost. Let x_ij be the quantity shipped from origin i to destination j, and let c_ij be the cost per unit.

For origins i = 1,...,m and destinations j = 1,...,n:

Here, s_i is supply and d_j is demand. If all supply must be shipped, use equality in the supply constraints. If all demand must be met exactly, use equality in the demand constraints. A balanced problem has total supply equal to total demand. An unbalanced problem can be balanced by adding a dummy origin or destination, with carefully chosen costs representing unused capacity or unmet demand.

Transportation models exploit a special structure and can be solved efficiently. However, real distribution may involve vehicle capacities, fixed route costs, delivery windows, multiple products, or emissions constraints, requiring a richer model.

7. Assignment Models

An assignment model allocates each worker, machine, salesperson, or job to exactly one counterpart. Define binary variable x_ij as 1 if agent i is assigned to task j, and 0 otherwise.

The binary restriction ensures that an agent cannot be fractionally assigned. If the numbers of agents and tasks differ, dummy rows or columns may be introduced. The Hungarian algorithm is a classic specialized method, while general integer-capable solvers provide flexibility for additional constraints.

8. Integer and Binary Decisions

Linear programming permits fractional values unless restricted. Integer programming requires some or all variables to be integers. Binary programming restricts variables to 0 or 1.

Typical binary variables represent yes/no decisions:

• open facility or do not open;
• select project or reject it;
• advertise in a channel or not;
• assign a worker to a shift or not.

A fixed-charge facility model may use continuous flow x_j and binary opening variable y_j:

Here, M_j is a valid upper bound on flow through facility j. If y_j = 0, the constraint forces x_j = 0; if y_j = 1, flow may be positive up to M_j. Choosing an excessively large M_j can weaken computational performance, so bounds should be realistic.

Integer models are often harder to solve than LP models because the solver must search among discrete combinations. The LP relaxation, obtained by temporarily removing integrality, can provide a bound but may produce an infeasible practical plan.

9. Illustrative Case: Regional Meal-Kit Allocation

Background. This illustrative case concerns FreshRoute, a meal-kit company serving three regions from two kitchens. Management must decide weekly shipments while minimizing transport cost and maintaining service commitments.

Problem. Kitchen A can supply 800 kits and Kitchen B 600 kits. Region North requires 500 kits, Central requires 400, and South requires 300. Per-kit shipping costs are:

Supply equals demand, so all capacity must be shipped. Let x_AN, x_AC, and so forth denote shipments.

Analysis. The model minimizes total shipping cost, with each kitchen’s shipments equal to its supply and each region’s receipts equal to its demand. A solver produces the following feasible allocation:

This allocation is feasible, but it is not necessarily optimal merely because it uses low-cost routes. A systematic solver should be used to verify optimality. In fact, shifting 300 kits from A–South to B–South and 300 kits from A–North to B–North would violate B’s supply unless the complete allocation is reconsidered. The case illustrates why local “cheapest route” reasoning can fail when supply and demand interact.

Managerial interpretation. The model may need additional constraints: refrigerated truck capacity, maximum delivery time, regional priority, carbon limits, or minimum use of a kitchen. If a kitchen’s production capacity is uncertain, scenario analysis should examine disruptions rather than relying on one deterministic plan.

Learning points. A good allocation model combines operational detail with transparent assumptions. The reported solution is a recommendation subject to data quality, service requirements, and implementation feasibility—not an unquestionable instruction.

10. Limitations, Ethics, and Governance

Optimization can create an appearance of precision even when inputs are uncertain. Forecast demand may be biased, cost data may omit social effects, and a mathematically optimal plan may be unacceptable to employees or customers.

Important governance practices include:

• document data sources, definitions, dates, and units;
• distinguish measured facts from estimates and managerial preferences;
• test sensitivity to uncertain parameters;
• preserve an audit trail of model versions and solver settings;
• explain recommendations in business language;
• monitor outcomes after implementation;
• provide human review for high-impact decisions.

Fairness is especially important in staff scheduling, credit allocation, healthcare capacity, and public services. An objective such as minimizing cost may indirectly disadvantage vulnerable groups. Constraints may be needed for equitable access, legal compliance, safety, rest periods, or environmental performance. Privacy and data protection obligations also apply when personal information informs allocation decisions.

AI systems can help generate scenarios, detect anomalous data, or propose candidate constraints, but they should not silently invent parameters or make unreviewed high-impact decisions. The optimization model must remain inspectable, reproducible, and accountable.

11. Best Practices for Analysts

1. Start with the decision, not the software.
2. Use meaningful variable names and a documented data dictionary.
3. Separate input data, model logic, and outputs.
4. Keep units visible throughout the model.
5. Use contribution margin rather than revenue when variable costs matter.
6. Include all material operational constraints.
7. Validate extreme cases and simple test instances.
8. Compare the optimized plan with the current policy and sensible heuristics.
9. Report slacks, binding constraints, and sensitivity ranges.
10. Communicate assumptions, uncertainty, and implementation risks.
11. Re-solve after major data or policy changes.
12. Treat optimization as decision support requiring managerial accountability.

Chapter Summary

Optimization converts resource-allocation problems into explicit decision models. A linear programming model contains decision variables, a linear objective, constraints, and variable restrictions. Feasible solutions satisfy all requirements, and an optimal LP solution occurs at an extreme point when the feasible region is suitably bounded. Graphical analysis is useful for two-variable models; software is necessary for larger models but does not replace careful formulation.

Slack identifies unused capacity, while a shadow price estimates the value of an additional unit of a constrained resource within a valid sensitivity range. Transportation models allocate flows between origins and destinations, assignment models make one-to-one allocations using binary variables, and integer programming represents indivisible or yes/no decisions. Reliable practice requires unit checking, validation, sensitivity analysis, transparency, and ethical consideration of affected stakeholders.

Key Terms

Decision variable: A controllable quantity chosen by the model.

Objective function: The expression maximized or minimized.

Constraint: A mathematical representation of a limitation or requirement.

Parameter: A known coefficient or input value in a model.

Linear programming: Optimization with linear objective and constraint relationships.

Feasible solution: A solution satisfying every constraint and variable restriction.

Feasible region: The set of all feasible solutions.

Extreme point: A corner point of a feasible region.

Binding constraint: A constraint satisfied exactly at the solution.

Slack: Unused capacity in a less-than-or-equal resource constraint.

Surplus: Amount above a minimum requirement.

Shadow price: Marginal value of changing a constraint right-hand side within a valid range.

Sensitivity analysis: Examination of solution changes when model inputs vary.

Transportation model: A flow-allocation model from origins to destinations.

Assignment model: A one-to-one allocation model.

Integer programming: Optimization requiring selected variables to be integers.

Binary variable: A variable restricted to 0 or 1.

LP relaxation: A model formed by removing integer restrictions.

Infeasibility: The condition that no solution satisfies all requirements.

Unboundedness: The condition that the objective can improve without limit.

Review Questions

Short Answer Questions

1. What are the four main components of a linear programming model?
2. Define a binding constraint and explain how it differs from a constraint with slack.
3. Why can a product with the highest unit profit fail to be part of the optimal product mix?
4. What is the purpose of a shadow price?
5. Why are binary variables used in assignment and facility-selection decisions?

Long Answer Questions

1. Explain the graphical method for solving a two-variable maximization problem, including feasible-region construction and corner-point evaluation.
2. Discuss the assumptions of linear programming and explain how violations of linearity can affect managerial conclusions.
3. Compare transportation, assignment, and general linear programming models in terms of variables, constraints, and applications.
4. Explain objective-coefficient and right-hand-side sensitivity analysis, including why sensitivity ranges should not be extrapolated indefinitely.
5. Describe a complete workflow for implementing and validating an optimization model in a spreadsheet or dedicated solver.

Analytical / Application Questions

1. A company makes products A and B. A uses 4 labour hours and 2 machine hours; B uses 3 labour hours and 5 machine hours. Weekly availability is 240 labour hours and 200 machine hours, while contribution margins are $40 and $50. Formulate the LP and identify the resource constraints.
2. A distribution manager observes that a cheapest-route shipping plan leaves one warehouse short of demand. Explain why selecting the cheapest route independently for each destination may be invalid, and propose a modelling improvement.
3. A solver recommends opening a facility with a fractional value of 0.63. Explain why this may be unacceptable, formulate an appropriate modelling restriction, and discuss one computational consequence.

Multiple Choice Questions with Answers

Question 1

Which component identifies the quantities controlled by the decision-maker?

A. Decision variables

B. Parameters

C. Objective coefficients

D. Shadow prices

Correct Answer: A. Decision variables

Question 2

In a maximization LP, what does slack in a resource constraint represent?

A. The amount by which demand is exceeded

B. Unused resource capacity

C. The objective value

D. The cost of one additional resource unit

Correct Answer: B. Unused resource capacity

Question 3

A product contributes $24 and uses 3 units of a scarce resource. Its contribution per resource unit is:

A. $8

B. $21

C. $27

D. $72

Correct Answer: A. $8

Question 4

Which condition is required for a variable to represent a yes/no decision?

A. It must be continuous

B. It must be unrestricted

C. It must be binary

D. It must be negative

Correct Answer: C. It must be binary

Question 5

A shadow price is best interpreted as:

A. The fixed cost of a product

B. The marginal value of relaxing a constraint within a valid range

C. The average profit per unit

D. The amount of unused capacity

Correct Answer: B. The marginal value of relaxing a constraint within a valid range

Question 6

Which model is specifically designed to allocate supply from origins to destinations?

A. Assignment model

B. Transportation model

C. Regression model

D. Inventory turnover model

Correct Answer: B. Transportation model

Question 7

If an LP has no solution satisfying all constraints, it is:

A. Unbounded

B. Degenerate

C. Infeasible

D. Balanced

Correct Answer: C. Infeasible

Question 8

In an assignment model, xᵢⱼ = 1 usually means that:

A. Agent i is assigned to task j

B. Task i is assigned to agent j only if cost is zero

C. Agent i is unavailable

D. The assignment cost is doubled

Correct Answer: A. Agent i is assigned to task j

Question 9

What is the main purpose of sensitivity analysis?

A. To remove all constraints

B. To examine how input changes affect the solution

C. To convert every variable into a binary variable

D. To guarantee that forecasts are correct

Correct Answer: B. To examine how input changes affect the solution

Question 10

Why can rounding a fractional solver output be unsafe?

A. Rounding always increases the objective

B. The rounded solution may violate constraints or cease to be optimal

C. Rounding changes a minimization problem into maximization

D. Rounding eliminates all parameters

Correct Answer: B. The rounded solution may violate constraints or cease to be optimal