Linear Programming: Formulation and Solution

Introduction and Context

Linear programming (LP) is a mathematical modelling and optimization method for allocating scarce resources among competing activities. In operations management, it supports decisions such as which products to manufacture, how much capacity to assign to each job, how to blend materials, how to schedule a workforce, and how to distribute resources across facilities.

An LP model does not attempt to reproduce every feature of reality. It abstracts a decision problem into three essential elements: decision variables, an objective function, and constraints. The model is useful when relationships between variables are linear and when the relevant data are sufficiently reliable for decision-making.

The central managerial value of LP is not merely the numerical optimum. A well-constructed model reveals the trade-offs embedded in a decision, identifies binding resources, quantifies the value of additional capacity, and exposes infeasibility or excessive ambition in a plan.

Learning Objectives

After studying this chapter, you should be able to:

• identify decision variables, parameters, objectives, and constraints;
• formulate product-mix, capacity, blending, workforce, and resource-allocation models;
• solve two-variable LPs graphically;
• explain the logic of the simplex method and basic feasible solutions;
• distinguish feasibility, optimality, degeneracy, redundancy, and unboundedness;
• interpret shadow prices, slack, and sensitivity information;
• evaluate LP assumptions and communicate model results responsibly.

1. Structure of a Linear Programming Model

A general maximization LP can be written as:

subject to

Here, x_j is the quantity of activity or product j; c_j is its unit contribution to the objective; a_ij is the amount of resource i used by one unit of activity j; b_i is the available amount of resource i; m is the number of constraints; and n is the number of decision variables. The objective value is Z.

The inequality may be changed to ≥ or = where appropriate. A minimization model is written as:

The model assumes that all coefficients are known or treated as fixed estimates, variables are divisible unless explicitly restricted, and total resource use and returns are additive and proportional.

Decision Variables

Decision variables represent controllable choices, not descriptive quantities. For example, in a production problem, x₁ may denote units of Product A manufactured during a week, while x₂ denotes units of Product B. Units must be stated clearly because dimensional consistency is essential.

Objective Function

The objective expresses the criterion to be maximized or minimized. It may be profit, contribution margin, revenue, throughput, service coverage, cost, overtime, distance, or risk. If fixed costs do not change with the decision, they do not affect the optimal choice and may be omitted from the objective, although they should remain in financial reporting.

Constraints

Constraints represent limited resources, contractual requirements, technical relationships, policy rules, or demand conditions. Common forms are:

• ≤: resource availability or capacity;
• ≥: minimum demand, service, or nutritional requirement;
• =: balance, conservation, or exact specification;
• x_j ≥ 0: non-negativity.

2. Formulation of Common Operations Models

2.1 Product-Mix Model

A manufacturer produces products A and B. Each unit of A contributes $40 and requires 2 machine hours and 1 labour hour. Each unit of B contributes $30 and requires 1 machine hour and 2 labour hours. Weekly availability is 100 machine hours and 80 labour hours. Let x₁ and x₂ be weekly units of A and B.

subject to

The coefficients in each constraint carry resource units per product, so the left-hand sides are measured in resource hours and can be compared with available hours.

2.2 Capacity and Routing Model

A service firm assigns work to two centres. Centre 1 can process 600 hours and Centre 2 can process 450 hours. Product X requires 3 hours in Centre 1 and 1 hour in Centre 2; Product Y requires 2 hours in Centre 1 and 3 hours in Centre 2. If contribution margins are $50 and $65 respectively:

If work must follow a prescribed sequence, each centre receives a separate constraint. If capacity is shared, the coefficients must reflect the common pool rather than double-counting it.

2.3 Blending Model

A blend must contain at least 30% protein and 10% fibre. Ingredient P contains 40% protein and 5% fibre and costs $8 per kilogram; ingredient Q contains 20% protein and 15% fibre and costs $5 per kilogram. For a one-kilogram blend, let x₁ and x₂ be kilograms of P and Q.

The equality fixes batch size. Percentages must be converted consistently to fractions, and ingredient quantities must use the same mass unit. If ingredient availability is limited, additional upper-bound constraints are required.

2.4 Workforce Planning Model

Suppose a call centre requires at least 120, 160, and 100 staff-hours in morning, afternoon, and evening periods. A full-time employee provides 8 morning, 8 afternoon, and 4 evening hours; a part-time employee provides 0 morning, 4 afternoon, and 6 evening hours. Let F and P represent numbers of full-time and part-time employees. If their weekly costs are $1,000 and $600:

If employees must be whole persons, integrality is needed: F,P ∈ {0,1,2,…}. The resulting problem is an integer program, not a pure LP. Rounding an LP solution may violate coverage or produce a costly, non-optimal plan.

2.5 Resource-Allocation Model

A manager may allocate a budget among projects. Let x_j be the amount assigned to project j, r_j its expected return per monetary unit, and B the available budget:

Project-specific minimum or maximum allocations, risk limits, and strategic requirements are represented by additional constraints. Expected returns are estimates; therefore, the output should be treated as decision support rather than certainty.

3. Graphical Solution of a Two-Variable LP

The graphical method applies directly only when there are two decision variables. Each constraint is plotted as a boundary line. The side satisfying the inequality is identified using a test point, commonly the origin when it is not on the boundary. The intersection of all satisfying regions is the feasible region.

For a linear objective, an optimum exists at an extreme point of a non-empty bounded feasible polygon, unless multiple optima occur along an edge. Thus, one may evaluate the objective at each corner point.

Worked Example: Product Mix

Return to the product-mix model:

The machine constraint has intercepts (50, 0) and (0, 100). The labour constraint has intercepts (80, 0) and (0, 40). The relevant corner points are:

• (0, 0);
• (50, 0), because machine capacity binds on the x-axis;
• (0, 40), because labour capacity binds on the y-axis;
• the intersection of both resource boundaries.

To find the intersection:

Multiplying the second equation by 2 and subtracting the first gives:

The objective values are:

Therefore, the optimal plan is 40 units of A and 20 units of B, producing a contribution of $2,200. Both resources are fully used: machine use is 2(40)+20=100 hours and labour use is 40+2(20)=80 hours.

If the objective line is parallel to a binding edge, every point on that edge may be optimal. This is called alternate optimality and indicates managerial flexibility among several equally valuable plans.

Figure: Feasible region and optimal corner for the illustrative product-mix model.

4. Simplex Concepts

The simplex method is an algebraic procedure that moves from one basic feasible solution to an adjacent one, improving the objective until no improving move remains. It is suitable for large LPs, where graphical enumeration is impossible.

An LP in standard form has equality constraints and non-negative variables:

A ≤ constraint becomes an equality by adding a non-negative slack variable. For example:

The slack s₁ measures unused machine capacity. For a ≥ constraint, a surplus variable is subtracted; an artificial variable may be required to obtain an initial basis, as in the Big-M or two-phase methods.

A basic solution sets selected non-basic variables to zero and solves for the basic variables. A basic feasible solution additionally satisfies non-negativity. In a non-degenerate basis with m independent constraints, there are typically m basic variables. The simplex method compares reduced costs or tableau indicators to determine whether entering a variable can improve the objective. The ratio test identifies the leaving variable while preserving feasibility.

For a maximization problem in a standard tableau, a positive reduced cost for a non-basic variable generally indicates potential improvement, subject to the chosen tableau convention. Because sign conventions differ across texts and software, the interpretation must always be tied to the displayed tableau rules.

At termination, the current feasible basis is optimal if no non-basic variable can improve the objective. The method is finite for ordinary non-pathological cases, although cycling is theoretically possible; anti-cycling rules such as Bland’s rule prevent indefinite cycling.

5. Feasibility, Optimality, Degeneracy and Unboundedness

Feasibility

A model is feasible if at least one assignment satisfies every constraint, including non-negativity. An infeasible model has no implementable plan. Causes include contradictory requirements, incorrect units, underestimated capacity, or overly strict service standards. An infeasibility diagnosis should examine constraints systematically rather than simply relaxing an arbitrary requirement.

Optimality

An optimal solution is a feasible solution with the best objective value. In an LP, a finite optimum occurs at an extreme point, although more than one extreme point may share the same value. Solver status, constraint satisfaction, and objective calculations should be checked before communicating an answer.

Degeneracy

A basic feasible solution is degenerate when one or more basic variables equal zero. Geometrically, more constraints meet at a corner than are needed to define it. Degeneracy can cause a simplex pivot that does not improve the objective and, in rare cases, cycling. It may also signal redundant or tightly overlapping operational requirements.

Unboundedness

A maximization model is unbounded if the objective can increase indefinitely while all constraints remain satisfied. This usually indicates a missing resource limit, an incorrect inequality direction, or an omitted upper bound. Unboundedness is not a practical recommendation to produce infinitely much; it is a modelling warning.

Redundancy and Inconsistency

A redundant constraint does not change the feasible region because it is implied by other constraints. It may still be valuable as a policy statement. An inconsistent constraint set produces infeasibility. Model review should distinguish a genuinely restrictive rule from a duplicated or incorrectly entered rule.

6. Economic Interpretation and Sensitivity

For a resource constraint, slack is:

For a ≤ constraint, slack is non-negative at a feasible solution and has the same units as resource i. A binding constraint has zero slack. A non-binding constraint may have a zero shadow price under standard LP sensitivity interpretation because a small increase in its right-hand side does not improve the objective locally.

The shadow price, or dual value, of resource i is the marginal improvement in the optimal objective for a one-unit increase in b_i, holding other parameters constant and remaining within the allowable sensitivity range:

The approximation is locally valid; it is not a universal value for large changes. If a machine-hour shadow price is $12 per hour, acquiring one additional hour is economically worthwhile only if its incremental cost is less than $12, assuming the sensitivity range and all other conditions remain valid.

Reduced cost measures the objective penalty associated with forcing a currently zero variable into the solution, under the relevant optimal-basis assumptions. It is useful for assessing products not currently selected, but it does not replace managerial judgement about demand, strategic importance, or omitted qualitative factors.

Sensitivity analysis changes one coefficient or right-hand-side value at a time in its simplest form. Simultaneous changes may invalidate individual ranges. Scenario analysis and re-optimization are preferable when major changes are expected.

7. Applied Case: Alpine Components (Illustrative)

Background

Alpine Components manufactures two custom assemblies, A and B, for industrial customers. Management must decide the weekly product mix. Assembly A contributes $40 per unit and Assembly B contributes $30. The plant has 100 machine hours and 80 labour hours available. Market commitments permit no more than 60 units of A and 50 units of B.

Problem and Formulation

Let x₁ and x₂ denote weekly production quantities:

Analysis and Solution

The unconstrained product-mix optimum previously found was (40, 20). It satisfies both market limits, so the additional demand constraints do not alter the optimal plan. Machine and labour constraints are binding; the demand constraints have slack. The plan yields contribution $2,200.

Management should not conclude that demand limits are unimportant generally. Their current non-binding status means only that small changes in the present model do not affect the optimum. If demand for A falls below 40, or if demand for B falls below 20, the solution must be reconsidered.

Outcome and Implementation

The production schedule should release 40 units of A and 20 units of B, while monitoring actual processing times and labour availability. If overtime is available, its maximum acceptable hourly premium can be compared with the relevant shadow price. If labour hours are uncertain, a buffer or robust scenario analysis may be appropriate.

Learning Points

The case demonstrates the difference between a mathematical optimum and a managerial decision. The optimum depends on contribution definitions, capacity data, market bounds, and divisibility assumptions. A responsible manager validates these assumptions, reviews sensitivity, and communicates which constraints actually drive the recommendation.

8. Assumptions, Limitations and Governance

LP assumes proportionality: doubling activity doubles resource use and contribution. It assumes additivity: total use is the sum of individual uses, with no interaction effects. Divisibility permits fractional solutions, which may be inappropriate for people, vehicles, batches, or projects. Coefficients are treated as known, although costs, processing times, demand, and yields may be uncertain. The usual model also assumes a single objective, whereas real decisions often balance profit, service, resilience, sustainability, and fairness.

Important extensions include integer programming for indivisible decisions, goal programming for multiple objectives, stochastic programming for uncertainty, robust optimization for protection against data variation, and nonlinear programming for economies of scale or congestion.

Governance matters when LP allocates scarce services, labour, healthcare capacity, or public resources. Managers should document data sources, assumptions, objective definitions, constraint priorities, and approval responsibility. A model can reproduce historical bias if its data or service rules are biased. Automated optimization should therefore be audited, stress-tested, and reviewed for distributional effects. Feasibility and efficiency do not automatically imply fairness or legal compliance.

Modern solvers can generate solutions rapidly, and AI tools can assist with data preparation, scenario generation, and formulation review. However, AI-generated models require expert verification: variable meanings, units, inequality directions, coefficient provenance, and solution status must be checked independently. Solver output should never be accepted solely because it appears numerically precise.

Best-Practice Modelling Workflow

1. Define the decision and planning horizon.
2. State decision variables with units and bounds.
3. Define the objective and distinguish contribution from fixed cost.
4. Translate each operational rule into a constraint.
5. Check dimensional consistency and sign conventions.
6. Test a simple feasible solution, if one should exist.
7. Solve using graphical, simplex, or software methods as appropriate.
8. Verify feasibility, objective value, binding constraints, and solver status.
9. Conduct sensitivity and scenario analysis.
10. Present assumptions, risks, and managerial actions with the result.

Chapter Summary

Linear programming provides a disciplined framework for optimizing the allocation of scarce resources. A complete model consists of decision variables, an objective function, constraints, and non-negativity or other domain restrictions. Product-mix, capacity, blending, workforce, and budget-allocation problems can all be represented when relationships are linear and data are sufficiently stable.

Graphical analysis explains the geometry of feasible regions and why an optimum occurs at an extreme point. The simplex method generalizes this logic by moving between basic feasible solutions. Feasibility means that at least one plan satisfies all restrictions; optimality means that the best feasible value has been reached. Degeneracy, redundancy, infeasibility, and unboundedness provide important diagnostic information rather than merely technical classifications.

Slack identifies unused capacity, while shadow prices estimate the marginal value of relaxing a binding resource within a valid sensitivity range. LP results must be interpreted critically because proportionality, divisibility, certainty, and single-objective assumptions may not hold. Sound practice combines mathematical optimization with data validation, sensitivity analysis, ethical governance, and managerial judgement.

Key Terms

Decision variable: A controllable quantity determined by the model.

Parameter: A fixed input such as cost, capacity, or processing time.

Objective function: Mathematical expression to maximize or minimize.

Constraint: A restriction imposed on decisions.

Feasible solution: A solution satisfying every model constraint.

Feasible region: Set of all feasible solutions.

Extreme point: Corner point of a feasible region.

Slack: Unused amount of a resource in a ≤ constraint.

Binding constraint: Constraint satisfied as an equality at the solution.

Surplus variable: Variable subtracted from a ≥ constraint to form equality.

Basic variable: Variable included in the current simplex basis.

Non-basic variable: Variable set to zero in a basic solution.

Basic feasible solution: A basic solution satisfying non-negativity.

Simplex method: Algebraic procedure for improving from one basis to another.

Degeneracy: A basic feasible solution with a zero basic variable.

Unboundedness: Ability to improve the objective indefinitely while remaining feasible.

Shadow price: Marginal value of relaxing a constraint locally.

Reduced cost: Objective impact of introducing a currently zero variable.

Sensitivity analysis: Study of solution changes caused by parameter variation.

Integer programming: Optimization requiring some variables to take integer values.

Review Questions

Short Answer Questions

1. What are the four principal components of a linear programming model?
2. Distinguish a binding constraint from a non-binding constraint.
3. Why is non-negativity imposed on production quantities in most product-mix models?
4. What does a shadow price represent?
5. Why can a fractional workforce solution be operationally inappropriate?

Long Answer Questions

1. Explain the assumptions of proportionality, additivity, divisibility, and certainty in LP, giving one operations example for each.
2. Describe the graphical method for solving a two-variable maximization problem.
3. Explain how slack variables and surplus variables are used in simplex formulations.
4. Compare feasibility, optimality, degeneracy, redundancy, and unboundedness.
5. Discuss how sensitivity analysis improves managerial interpretation of an LP solution.

Analytical / Application Questions

1. A plant makes products X and Y. X contributes $50 and uses 4 cutting hours and 2 finishing hours; Y contributes $40 and uses 2 cutting hours and 3 finishing hours. Weekly capacities are 120 cutting hours and 90 finishing hours. Formulate and solve the product-mix LP graphically.
2. A nutrition blend must weigh 1,000 kg and contain at least 25% protein. Ingredient A contains 40% protein and costs $6/kg; ingredient B contains 15% protein and costs $3/kg. Formulate the cost-minimizing blending model and determine whether the protein requirement binds at the optimum.
3. A solver reports an unbounded maximization model although management expected a finite production plan. Identify three modelling errors that could cause this result and propose diagnostic checks.

Multiple Choice Questions with Answers

Question 1

Which element specifies what the decision-maker is trying to maximize or minimize?

A. Decision variable

B. Objective function

C. Slack variable

D. Feasible region

Correct Answer: B. Objective function

Question 2

In the product-mix example, what is the optimal combination of A and B?

A. 20 units of A and 40 units of B

B. 40 units of A and 20 units of B

C. 50 units of A and 0 units of B

D. 0 units of A and 40 units of B

Correct Answer: B. 40 units of A and 20 units of B

Question 3

A slack variable in a ≤ capacity constraint measures:

A. Excess demand

B. Unused capacity

C. Fixed cost

D. The objective coefficient

Correct Answer: B. Unused capacity

Question 4

Which condition is necessary for a solution to be feasible?

A. It must maximize profit

B. It must satisfy every constraint

C. All constraints must be binding

D. Every variable must be positive

Correct Answer: B. It must satisfy every constraint

Question 5

What does an LP shadow price estimate?

A. The total fixed cost of a resource

B. The marginal objective improvement from one additional resource unit

C. The number of non-basic variables

D. The percentage of unused capacity

Correct Answer: B. The marginal objective improvement from one additional resource unit

Question 6

A basic feasible solution is degenerate when:

A. The objective is unbounded

B. At least one basic variable equals zero

C. There are no constraints

D. All constraints are redundant

Correct Answer: B. At least one basic variable equals zero

Question 7

Which modelling feature is required when employees must be whole persons?

A. A nonlinear objective

B. Integer restrictions

C. A negative slack variable

D. Removal of capacity constraints

Correct Answer: B. Integer restrictions

Question 8

An unbounded maximization model most commonly indicates that:

A. Every resource is overused

B. A limiting constraint or upper bound may be missing

C. The feasible region contains no point

D. The objective has no coefficients

Correct Answer: B. A limiting constraint or upper bound may be missing

Question 9

In a blending model for a one-kilogram product, the equation x₁ + x₂ = 1 represents:

A. Total cost

B. Total blend quantity

C. Minimum protein

D. Available machine time

Correct Answer: B. Total blend quantity

Question 10

Why should solver output be independently verified?

A. LP solutions never satisfy constraints

B. Numerical precision guarantees incorrect results

C. Data, units, formulation, and solver status may be wrong

D. Graphical solutions are always superior

Correct Answer: C. Data, units, formulation, and solver status may be wrong