Linear Programming and Resource Optimization

Introduction

Organizations routinely face decisions about how to allocate scarce resources among competing uses. A manufacturer may decide how many units of several products to produce; a bank may allocate a lending budget across customer segments; a logistics manager may route shipments through a distribution network; and a public agency may allocate personnel across services. Linear programming (LP) provides a rigorous framework for these decisions when relationships among decision variables can be represented linearly.

An LP model identifies decision variables, an objective to maximize or minimize, constraints representing limited resources or policy requirements, and non-negativity restrictions. Its value is not merely computational. LP makes assumptions explicit, reveals trade-offs, identifies bottlenecks, and supports sensitivity analysis. In managerial practice, however, the model is an approximation of reality, not reality itself. Sound decisions therefore require both mathematical solution and managerial interpretation.

Learning Objectives

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

1. Formulate LP models from managerial and operational descriptions.
2. Explain feasible solutions, binding constraints, corner-point optimality and alternative optima.
3. Solve small LPs graphically and interpret solver-based solutions for larger models.
4. Interpret dual values, shadow prices, reduced costs and sensitivity ranges.
5. Apply LP to product mix, budgeting, allocation, transportation and supply-chain decisions.
6. Evaluate assumptions, limitations, governance risks and implementation issues.

1. The Structure of a Linear Programming Model

A general LP model is:

Here, x_j is decision variable j; c_j is the objective coefficient per unit of x_j; a_ij is the amount of resource i required by one unit of x_j; b_i is the available amount or required minimum of resource i; and Z is the objective value. The index i identifies constraints and j identifies activities or products.

The model is linear because variables appear only to the first power, variables are not multiplied by one another, and coefficients are constants over the relevant decision range. Units must be consistent: if labor availability is measured in hours, labor-use coefficients must also be hours per unit.

1.1 Decision variables

Decision variables describe controllable choices, not outcomes that are merely observed. For example, x₁ may represent units of Product A produced per week, while x₂ represents units of Product B.

1.2 Objective function

The objective expresses the criterion for decision quality. It may be contribution margin, profit, service coverage, revenue, cost, emissions or risk-adjusted value. For a profit-maximization model:

where p_j is contribution per unit. If fixed costs do not change with the decision, they may be omitted from the LP objective and added afterward when reporting total profit.

1.3 Constraints

Constraints represent scarce resources, contractual limits, demand, policy conditions or technical requirements. A capacity constraint has the form:

A minimum service or demand requirement may be written as:

An equality constraint is appropriate when a quantity must be exactly balanced, such as a flow-conservation equation.

Non-negativity, x_j ≥ 0, is standard when negative production, shipments or staffing levels have no meaning. Integer or binary restrictions are needed when decisions must be indivisible or logical, such as opening a facility. Such models are mixed-integer linear programs rather than pure LPs.

2. Formulation: From Narrative to Model

A reliable formulation process is:

1. Define the decision horizon and units.
2. Identify controllable decisions.
3. Define the objective and whether it is to be maximized or minimized.
4. Translate each resource, demand and policy statement into a constraint.
5. Add non-negativity, integrality or logical restrictions.
6. Check dimensions, signs and business meaning.
7. Test the model with extreme or known scenarios.

Worked Example 1: Product Mix

A firm produces desks and cabinets. Each desk contributes $50 and requires 4 hours of carpentry and 2 hours of finishing. Each cabinet contributes $40 and requires 3 carpentry hours and 4 finishing hours. Weekly capacity is 240 carpentry hours and 160 finishing hours. Demand is at most 40 desks and 30 cabinets.

Let x₁ be desks and x₂ be cabinets per week. The model is:

The objective coefficients are contribution margins, not selling prices, unless all variable costs have already been incorporated. If a product consumes 4 hours, its coefficient must be 4 hours per unit, and the right-hand side must be hours.

3. Feasible Regions and Graphical Solution

A solution satisfying every constraint and non-negativity condition is feasible. The set of all feasible solutions is the feasible region. In a two-variable LP, each constraint defines a half-plane; their intersection forms the feasible region.

For the product-mix example, the capacity boundaries are:

The feasible region also lies below the demand limits and in the non-negative quadrant. An LP with a finite optimum achieves it at at least one extreme point, or corner point, of the feasible region, provided the feasible region is nonempty and the objective is bounded. This is the basis of the graphical method and the simplex method.

Figure: A feasible region is the intersection of all constraint half-planes; an optimum occurs at an extreme point when the LP has a finite optimum.

To solve graphically, one identifies all corner points, substitutes each into the objective, and selects the best value. The intersection of the two capacity constraints in the example solves:

Multiplying the second equation by 2 gives 4x₁ + 8x₂ = 320. Subtracting the first equation gives 5x₂ = 80, so x₂ = 16. Substitution gives 4x₁ + 48 = 240, hence x₁ = 48. This violates the desk demand limit of 40, so it is not feasible in the complete model. The relevant corner involving x₁ = 40 and the finishing constraint is 80 + 4x₂ = 160, giving x₂ = 20. Its contribution is 50(40) + 40(20) = 2,800. Other feasible corners must be evaluated before concluding optimality; in this example, the corner (40,20) is superior to producing only cabinets or only desks.

A graphical solution is useful for teaching and diagnosis but becomes impractical beyond two or three variables. Spreadsheet solvers, simplex implementations and optimization APIs are used for larger models.

4. Simplex Logic and Solver Interpretation

The simplex method moves from one basic feasible solution to an adjacent one, improving the objective until no improving move remains. Modern solvers may use revised simplex, interior-point methods, presolve reductions and branch-and-bound for integer restrictions. The user need not perform tableau operations manually, but should understand the output.

Typical statuses include:

• Optimal: a best feasible solution has been identified under the model.
• Infeasible: no solution satisfies all constraints; often caused by inconsistent requirements or incorrect units.
• Unbounded: the objective can improve indefinitely; a missing constraint or unrealistic revenue assumption may be responsible.
• Multiple optima: several feasible solutions have the same objective value.

A solver’s optimum is conditional on the data and formulation. It does not validate whether the objective is strategically appropriate or whether coefficients are reliable.

5. Duality and Shadow Prices

Every primal LP has an associated dual LP. For a primal maximization problem with “less than or equal to” resource constraints and nonnegative variables:

Here, A is the resource-use matrix, x is the activity vector, b is the resource-availability vector, c is the contribution vector, and y is the vector of dual values. The transpose A^T changes rows into columns.

The dual assigns an implicit value to each scarce resource. A shadow price, or dual value, estimates the change in optimal objective value from increasing a constraint’s right-hand side by one unit, while other data remain fixed and the same optimal basis remains valid.

If an additional carpentry hour has a shadow price of $6 per hour, management should be willing to pay up to approximately $6 for that hour, subject to the sensitivity range and practical conditions. A nonbinding constraint generally has zero shadow price because unused capacity has no marginal value at the current solution. This does not mean the resource is globally worthless; it means it has no marginal value within the current model and local range.

Weak and strong duality

For any feasible primal and dual solutions, the primal objective cannot exceed the dual objective in a maximization/minimization pair. At optimality, under standard LP conditions, the two objective values are equal. This is strong duality and provides both an economic interpretation and a computational verification.

Complementary slackness

Complementary slackness links unused resources and zero-valued dual variables. For a resource constraint with slack s_i = b_i − ∑_j a_ijx_j,

Thus, if resource i has positive unused capacity, its shadow price is zero; if its shadow price is positive, the constraint must be binding. Similarly, a product with positive reduced cost cannot be produced in an optimal solution under the current basis.

6. Sensitivity Analysis

Sensitivity analysis examines how changes in coefficients affect the solution. It is essential because forecasts, costs, capacities and prices are uncertain.

6.1 Right-hand-side sensitivity

The shadow price estimates the objective change from a one-unit change in b_i:

This approximation is valid only within the reported allowable increase and decrease, where the current optimal basis remains unchanged. Beyond that range, the shadow price may change and the LP should be re-solved.

6.2 Objective-coefficient sensitivity

The allowable range for an objective coefficient indicates how much a contribution or cost can change before the current basis ceases to be optimal. The production quantities may remain unchanged within the range, although the objective value changes.

6.3 Reduced costs

For a variable at zero in a maximization problem, its reduced cost indicates the improvement in its objective coefficient required before it becomes attractive, subject to solver sign conventions. A reduced cost of −$3 may mean that the product’s contribution must increase by $3 per unit before entering the solution. Reports must be interpreted using the solver’s stated convention.

6.4 Limits of local sensitivity

Sensitivity tables are local, ceteris-paribus analyses. They do not automatically capture simultaneous changes, nonlinear demand, competitor reactions, stepwise capacity costs, uncertainty or changes in the feasible basis. Scenario analysis and re-optimization are needed for material changes.

7. Applications Across Management Functions

Product mix

LP selects production quantities subject to labor, machine, material, demand and contractual constraints. It can also incorporate minimum product requirements or quality specifications.

Budgeting and portfolio allocation

A budget model allocates funds among campaigns, projects or customer segments. Constraints may include total budget, minimum strategic spending, risk limits and resource dependencies. If returns are uncertain, deterministic LP should be supplemented by scenario, stochastic or robust optimization.

Workforce and service allocation

Hospitals, call centers and public agencies can allocate staff across shifts or service units. Coverage constraints often require minimum staffing, while labor regulations may impose maximum hours and rest requirements.

Transportation and supply-chain planning

Let x_ij denote units shipped from source i to destination j, and c_ij the cost per unit. A balanced transportation model is:

Here, s_i is supply and d_j is demand, both in compatible shipment units. If total supply exceeds total demand, a dummy destination or an inequality formulation may be used. If transportation costs, capacities or emissions are included, each must be represented consistently.

Network and flow decisions

Flow-conservation constraints ensure that inflow plus external supply equals outflow plus demand at each node. Such models support distribution, transshipment, project scheduling and energy systems planning.

8. Illustrative Case: Regional Medical-Equipment Allocation

Background. A fictional medical-equipment distributor supplies two hospitals from two warehouses. Management wants to minimize weekly shipping cost while meeting demand and warehouse capacity.

Problem. Warehouse W1 can ship 80 units and W2 can ship 60 units. Hospital H1 requires 70 units and H2 requires 50 units. Per-unit shipping costs are:

Let x₁₁, x₁₂, x₂₁, and x₂₂ denote shipments from W1 to H1, W1 to H2, W2 to H1 and W2 to H2. The model is:

Analysis and solution. Total capacity is 140 and total demand is 120, so 20 units of capacity may remain unused. W1 is cheaper for H1, while W2 is cheaper for H2. Assigning W1’s 80 units as 70 to H1 and 10 to H2 leaves W2 to supply 40 to H2 and 20 units unused. Cost is:

An alternative assigning W2 to H2 first and W1 to H1 produces the same allocation logic. A solver should be used to verify the result, particularly if route capacities, fixed charges or service-level constraints are added.

Outcome and learning points. The model makes trade-offs transparent: using W2 for H2 saves $3 per unit compared with W1, while using W1 for H1 saves $1 per unit compared with W2. The analysis also shows why unused capacity is not necessarily a problem: capacity at W2 has no value if all demand is already met and no profitable alternative use exists. In a real organization, lead times, emergency stock, quality, carbon emissions and disruption risk would need to be considered.

9. Assumptions, Limitations and Extensions

LP relies on proportionality, additivity, divisibility, certainty and a well-defined objective.

• Proportionality: resource use and contribution change directly with activity level.
• Additivity: total resource use is the sum of individual activities; there are no unmodeled interactions.
• Divisibility: fractional quantities are acceptable. If not, integer programming is required.
• Certainty: coefficients are treated as known during the decision horizon.
• Linearity: economies of scale, setup costs and nonlinear prices are absent unless approximated by additional variables and constraints.

Common extensions include integer and mixed-integer programming, goal programming for multiple objectives, robust optimization for uncertainty, stochastic programming for probabilistic outcomes, and nonlinear programming for curvature or interaction effects.

Governance and ethical issues

Optimization can reproduce biased priorities if objectives or constraints disadvantage particular groups. A hospital allocation model, for example, should not maximize throughput while ignoring equitable access. Managers should document data sources, assumptions, excluded stakeholders, constraint rationale and approval authority. Models affecting employees, patients, credit applicants or citizens require auditability, privacy protection and meaningful human oversight. An apparently optimal solution may be operationally or ethically unacceptable.

Technology and AI

Cloud solvers and analytics platforms make LP accessible through spreadsheets, Python, optimization APIs and enterprise planning systems. AI can assist with data preparation, demand forecasting and scenario generation, but it should not silently alter constraints or invent coefficients. Forecast uncertainty should be exposed through scenarios, confidence information or robust formulations. Solver logs, model versions and input data should be retained for reproducibility.

10. Best Practices for Managerial Use

1. Begin with the decision, not the software.
2. Define variables and units in plain language.
3. Separate fixed, variable and avoidable costs.
4. Validate every coefficient with operational experts.
5. Check feasibility before interpreting optimality.
6. Examine binding constraints and shadow prices.
7. Run sensitivity and scenario analyses.
8. Test extreme cases and compare with current practice.
9. Include qualitative, legal and ethical constraints.
10. Re-optimize when material data or business conditions change.

Chapter Summary

Linear programming is a framework for allocating scarce resources to maximize or minimize a linear objective. A complete model contains decision variables, an objective function, constraints and appropriate sign or integrality restrictions. Feasible solutions satisfy all constraints; when a finite optimum exists, at least one optimum occurs at an extreme point. Graphical analysis supports two-variable models, while simplex, interior-point and mixed-integer methods support larger applications.

Duality provides an economic interpretation of resource constraints. Shadow prices estimate the marginal value of additional resources within a valid sensitivity range. Reduced costs indicate the improvement needed for an excluded activity to become attractive. Sensitivity analysis is local and must not be treated as a substitute for scenario analysis when several assumptions change simultaneously. LP supports product mix, budgeting, staffing, transportation and supply-chain decisions, but its assumptions, data quality, ethical consequences and governance must be examined before implementation.

Key Terms

Linear programming: A mathematical method for optimizing a linear objective subject to linear constraints.

Decision variable: A controllable quantity whose value is selected by the model.

Objective function: The expression being maximized or minimized.

Constraint: A mathematical restriction on feasible decisions.

Feasible solution: A solution satisfying every model restriction.

Feasible region: The set of all feasible solutions.

Extreme point: A corner point of a convex feasible region.

Binding constraint: A constraint satisfied exactly at the solution.

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

Surplus: Amount by which a greater-than-or-equal requirement is exceeded.

Shadow price: Marginal objective value of relaxing a constraint locally.

Dual problem: The LP associated with the original, or primal, problem.

Complementary slackness: Conditions linking primal slack and dual values at optimality.

Reduced cost: Improvement required in an objective coefficient for a currently zero variable to become attractive, subject to sign convention.

Sensitivity analysis: Study of solution changes resulting from parameter changes.

Transportation model: An LP that allocates shipments between sources and destinations.

Integer programming: Optimization with restrictions requiring some variables to be integers.

Robust optimization: Optimization designed to remain satisfactory under uncertainty.

Review Questions

Short Answer Questions

1. What are the four essential components of a basic LP model?
2. Why must units be consistent in an LP formulation?
3. What is the meaning of a binding constraint?
4. Define a shadow price and state its main limitation.
5. Distinguish pure LP from mixed-integer programming.

Long Answer Questions

1. Explain the process of translating a managerial narrative into an LP model, using a product-mix example.
2. Discuss the geometric meaning of feasible regions, extreme points and optimality.
3. Explain primal-dual relationships, strong duality and complementary slackness.
4. Describe how sensitivity analysis supports managerial decisions and why its results are local.
5. Evaluate the assumptions and ethical risks of using LP in public-service resource allocation.

Analytical / Application Questions

1. A manufacturer has two products, limited labor and machine hours, and upper bounds on demand. Formulate the LP and identify which constraints are likely to be binding. Explain what additional information is required before recommending production quantities.
2. A transportation model reports a positive shadow price for warehouse capacity and zero shadow price for another warehouse. Interpret these results and recommend two managerial actions, noting the relevant sensitivity limitation.
3. A manager proposes replacing an LP with an AI-generated recommendation because the recommendation has a higher predicted profit. Design a governance process comparing the two approaches, including data validation, scenario analysis, fairness, explainability and human approval.

Multiple Choice Questions with Answers

Question 1

Which expression is a valid linear-programming objective for two products?

A. Z = 40x₁ + 30x₂

B. Z = 40x₁² + 30x₂

C. Z = 40x₁x₂ + 30

D. Z = 40/x₁ + 30x₂

Correct Answer: A. Z = 40x₁ + 30x₂

Question 2

A feasible solution is one that:

A. Maximizes the objective regardless of constraints

B. Satisfies every constraint and sign restriction

C. Uses every resource completely

D. Has only integer values

Correct Answer: B. Satisfies every constraint and sign restriction

Question 3

In a maximization LP, a nonbinding resource constraint generally has what shadow price?

A. A negative shadow price

B. A positive shadow price

C. A zero shadow price

D. An undefined shadow price

Correct Answer: C. A zero shadow price

Question 4

For the equations 4x₁ + 3x₂ = 240 and 2x₁ + 4x₂ = 160, the intersection is:

A. (20, 40)

B. (40, 20)

C. (48, 16)

D. (16, 48)

Correct Answer: C. (48, 16)

Question 5

The estimate ΔZ ≈ yᵢΔbᵢ is appropriately interpreted as:

A. A global effect valid for any size change

B. A local objective change within the valid sensitivity range

C. A constraint violation measure

D. A product demand forecast

Correct Answer: B. A local objective change within the valid sensitivity range

Question 6

Which condition is most likely to require integer programming rather than pure LP?

A. Producing continuous quantities of chemicals

B. Allocating divisible advertising expenditure

C. Deciding whether to open a facility

D. Transporting bulk liquid measured in tonnes

Correct Answer: C. Deciding whether to open a facility

Question 7

In a balanced transportation model, the supply constraints normally ensure that:

A. Each destination receives exactly its demand

B. Each source ships exactly its available supply

C. All route costs are equal

D. Every route is used

Correct Answer: B. Each source ships exactly its available supply

Question 8

If total supply is 140 units and total demand is 120 units, the excess capacity is:

A. 10 units

B. 20 units

C. 60 units

D. 260 units

Correct Answer: B. 20 units

Question 9

Strong duality states that, under standard LP conditions at optimality:

A. The primal and dual objective values are equal

B. All constraints are nonbinding

C. All decision variables are integers

D. The primal objective is always zero

Correct Answer: A. The primal and dual objective values are equal

Question 10

Which is a central limitation of deterministic LP?

A. It cannot represent any resource constraint

B. It assumes coefficients are known and relationships are linear

C. It always produces multiple optima

D. It cannot minimize costs

Correct Answer: B. It assumes coefficients are known and relationships are linear