Linear Programming Models and Algorithms

Introduction and Context

Linear programming (LP) is a mathematical framework for allocating scarce resources among competing activities when relationships are linear. It is one of the foundational methods of prescriptive analytics: descriptive analytics explains what has happened, predictive analytics estimates what may happen, and optimization identifies what should be done under stated objectives and constraints.

LP is widely used in product mix decisions, transportation, workforce scheduling, blending, portfolio allocation, capacity planning, procurement, and supply-chain design. Its value lies not only in producing an optimal solution, but also in making trade-offs explicit. A well-constructed LP model connects managerial decisions, operational limits, economic value, and measurable data in a transparent structure.

Learning Objectives

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

1. Formulate LP models from managerial and operational descriptions.
2. Distinguish decision variables, objective functions, constraints, and parameters.
3. Solve two-variable models graphically and interpret feasible regions and extreme points.
4. Convert models into standard and canonical forms suitable for algorithms.
5. Explain the simplex method, degeneracy, and optimality conditions.
6. Describe the logic and advantages of interior-point methods.
7. Select and interpret LP models for product mix, blending, allocation, and capacity planning.
8. Evaluate assumptions, limitations, governance concerns, and practical implementation issues.

1. The Structure of a Linear Program

A linear program contains four essential elements:

• Decision variables: unknown quantities to be selected.
• Parameters: known coefficients such as prices, resource requirements, capacities, and costs.
• Objective function: a linear expression to maximize or minimize.
• Constraints: linear equalities or inequalities that define allowable decisions.

A general maximization LP can be written as:

subject to

Here, x_j is the level of activity 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, and b_i is the available amount of resource i. The objective value is Z. Coefficients must be expressed in compatible units: for example, hours per unit multiplied by units produced gives hours.

The model assumes that the objective and constraints are linear. Thus, contribution from two products is additive, and resource use is proportional to activity levels. The model also normally assumes divisibility, meaning fractional values are permitted unless integer restrictions are added.

Decision variables and modeling judgment

Choosing variables is often the most important modeling decision. Variables should represent controllable decisions at the level required by the problem. If a firm decides how many units of products A and B to produce, define x_A and x_B as production quantities. If it decides how much raw material to send to several plants, variables may represent plant-material flows.

A variable should not be introduced merely because a quantity appears in the narrative. It is needed when its value must be determined or when it helps express a logical or accounting relationship.

2. A Worked Formulation: Product Mix

A manufacturer produces desks and tables. Each desk contributes $40 and requires 2 hours of carpentry and 1 hour of finishing. Each table contributes $30 and requires 1 hour of carpentry and 2 hours of finishing. Weekly capacity is 100 carpentry hours and 80 finishing hours. Let:

• x₁ = desks produced per week;
• x₂ = tables produced per week.

The LP is:

subject to

The objective has units of dollars per week. Each constraint has units of hours, and both sides of each inequality therefore have the same unit.

This formulation does not include demand limits, labor availability by employee, setup costs, or minimum production requirements. Such features may be added if they are relevant and can be represented linearly.

3. Graphical Solution and Extreme Points

The graphical method is practical only for one or two decision variables, but it provides essential geometric insight.

For the product-mix model, the boundary lines are:

The feasible region is the set of points satisfying both inequalities and nonnegativity. Its corner points are found as follows:

• Origin: (0,0).
• Carpentry-axis intercept: (50,0), although the finishing constraint permits only 50 desks and is binding there.
• Finishing-axis intercept: (0,40).
• Intersection of the two resource boundaries.

To find the intersection, substitute x₂ = 100 - 2x₁ into the second equation:

Evaluate the objective at the feasible extreme points:

Therefore, the optimal production plan is 40 desks and 20 tables, producing a contribution of $2,200 per week. Both resource constraints are binding at this solution: carpentry use is 2(40)+20=100 hours and finishing use is 40+2(20)=80 hours.

Why extreme points matter

The feasible region of an LP is a convex polyhedron. A fundamental result of linear programming states that if a finite optimum exists, at least one optimum occurs at an extreme point, also called a vertex or basic feasible solution. If the objective is parallel to a boundary edge, every point on that edge may be optimal; this is called alternate optimality.

This result explains the logic of the simplex method: instead of examining every feasible point, the algorithm moves from one extreme point to another while improving the objective, until no improving adjacent extreme point exists.

Figure: The shaded polygon is the feasible region; the marked intersection is optimal for the stated objective.

4. Standard Forms and Canonical Forms

Algorithms require a consistent representation. A common standard form for a minimization problem is:

Here, A is an m × n coefficient matrix, x is the vector of decision variables, b is the right-hand-side vector, and c is the objective-coefficient vector. Equality constraints and nonnegative variables are required in this convention.

A maximization problem with a “less than or equal to” constraint can be converted by adding a nonnegative slack variable. For example:

A surplus variable is subtracted from a “greater than or equal to” constraint. An unrestricted variable can be represented as the difference of two nonnegative variables:

When a natural identity or a “greater than or equal to” constraint prevents an immediate starting basis, artificial variables may be introduced temporarily through the Big-M or two-phase method. Artificial variables are algorithmic devices, not real activities, and must be removed from any feasible final solution.

5. The Simplex Method

The simplex method operates on a basic feasible solution. In a model with m independent equality constraints, a basis generally contains m basic variables; the remaining variables are nonbasic and set to zero. Solving the basis equations gives the current basic solution.

For a maximization problem, a simplified tableau procedure is:

1. Construct a feasible initial basis, often using slack variables.
2. Compute reduced costs or inspect the objective row.
3. Select an entering variable with an improving reduced cost.
4. Apply the minimum-ratio test to select the leaving variable and preserve feasibility.
5. Pivot to obtain a new basis.
6. Repeat until no improving reduced cost remains.

For a minimization problem in standard form, reduced costs are commonly defined as:

where B is the basis matrix, c_B contains objective coefficients of basic variables, and A_j is column j. Under the usual minimization convention, a feasible basic solution is optimal when all reduced costs satisfy r_j ≥ 0. Sign conventions differ across tableau texts, so the convention must be checked before interpreting the objective row.

The simplex method is finite under standard anti-cycling rules, although poor pivot choices can cause cycling in degenerate cases. Its worst-case running time is exponential for certain constructed instances, yet it is highly effective in many practical models.

Duality and shadow prices

Every LP has an associated dual. For the primal maximization model

the dual is

The dual variable y_i is often interpreted as the marginal value, or shadow price, of one additional unit of resource i, subject to the current basis remaining valid. Strong duality states that, when both problems have finite optima, their optimal objective values are equal. This is valuable for managerial interpretation: the primal describes activity levels, while the dual describes the value of scarce resources.

Shadow prices are local sensitivity measures, not unlimited promises. If capacity changes substantially, the optimal basis may change and the reported marginal value may no longer apply.

6. Degeneracy and Special Outcomes

A basic feasible solution is degenerate when one or more basic variables have value zero. Degeneracy can occur when more constraints meet at the same geometric point than are required to define a vertex.

Consequences include:

• a pivot may change the basis without changing the solution or objective;
• the simplex method may require extra iterations;
• cycling is theoretically possible without anti-cycling rules;
• sensitivity interpretations require care.

Common LP outcomes include:

Infeasibility often indicates contradictory policy requirements, incorrect units, or an omitted variable. Unboundedness may indicate a missing capacity, demand, or balance constraint rather than a genuine business opportunity.

7. Interior-Point Methods

Interior-point methods approach an optimum through the interior of the feasible region rather than moving along its edges. A barrier formulation for a nonnegative-variable problem may be expressed as:

The logarithmic barrier discourages variables from reaching zero while μ is positive. As μ decreases toward zero, solutions trace a central path toward an LP optimum under suitable conditions.

Interior-point algorithms are especially attractive for very large, sparse models and often have strong polynomial-time complexity results. They may produce a solution that is extremely close to optimal but not exactly at a vertex; crossover procedures can then identify a basic solution when basis information and sensitivity analysis are required. Simplex methods are often preferred for warm starts and detailed post-optimal analysis, while interior-point methods can be powerful for large-scale numerical optimization. Modern solvers frequently combine methods and automatically select strategies.

8. Common LP Applications

Product mix

A firm chooses production quantities to maximize contribution subject to labor, machine, material, storage, and demand limits. Demand constraints can be written as x_j ≤ d_j, where d_j is maximum sales demand.

Blending

A refinery, food producer, or chemical manufacturer chooses input quantities to meet composition requirements at minimum cost. If x_j is the quantity of ingredient j and q_j is its concentration of a component, a minimum-quality constraint is:

The expression is linear because q_min is a constant. If the required quality is expressed as a ratio involving two decision-dependent quantities, multiplication may be needed to obtain this linear form.

Allocation and transportation

Let x_ij be the amount shipped from origin i to destination j, with unit cost c_ij. The transportation objective is:

Supply and demand constraints enforce flow conservation. Such models support procurement, distribution, and service allocation.

Capacity planning

Capacity planning assigns resources over periods or technologies. A typical constraint is:

where t_j is capacity time per unit and C is available capacity. Multi-period models may include inventory balance:

where I_t is ending inventory, P_t production, and D_t demand in period t.

9. Illustrative Case: Regional Meal Production

Background. A meal-service company supplies two meal types. Meal A contributes $6 per unit and uses 0.5 kitchen hours and 0.2 kg of a protein ingredient. Meal B contributes $8, uses 0.4 kitchen hours and 0.4 kg of protein. Weekly availability is 240 kitchen hours and 160 kg of protein. At most 300 units of Meal A and 280 units of Meal B can be sold.

Problem. Determine the production plan that maximizes weekly contribution.

Let x_A and x_B denote weekly production quantities. The model is:

subject to

Analysis. The kitchen constraint is relatively generous at the demand limits: using 300 and 280 units requires 262 kitchen hours, which exceeds 240. Protein use is 172 kg, also exceeding 160. Thus both resources may influence the solution. A solver should be used because demand limits add additional boundaries. Testing the intersection of the two resource constraints gives:

Subtracting the second equation from the first gives 0.3x_A = 80, so x_A = 266.67. Substitution gives x_B = 266.67. This point satisfies both demand limits. Its contribution is approximately:

However, it is essential to test all relevant extreme points, including intersections involving demand boundaries and axes. For example, producing 0 Meal A and 280 Meal B uses 112 kitchen hours and 112 kg protein and yields $2,240. Producing 300 Meal A and 0 Meal B yields $1,800. The resource intersection gives the larger contribution among these principal candidates, but a complete solver or systematic vertex enumeration should verify every feasible vertex.

Outcome and managerial interpretation. The recommended plan is approximately 266.67 units of each meal if fractional production is operationally acceptable. In practice, meals may require integer quantities, packaging batches, or minimum run sizes. The continuous LP should then be extended to a mixed-integer model or rounded only after checking feasibility and financial impact.

Learning points. The case illustrates the distinction between a mathematical optimum and an implementable plan. Data validation, demand realism, unit consistency, integrality, and sensitivity analysis are as important as the optimization algorithm.

10. Assumptions, Limitations, and Governance

LP relies on proportionality, additivity, divisibility, and known parameters. These assumptions can fail when there are quantity discounts, setup costs, economies of scale, nonlinear production functions, uncertain demand, or logical “if–then” decisions. Integer programming, nonlinear programming, stochastic programming, robust optimization, or simulation may then be more appropriate.

Data quality is a major risk. An optimizer can produce a precise answer from inaccurate costs or capacities. Analysts should document data sources, units, time periods, exclusions, and ownership of each parameter. Constraints should be reviewed with operational experts, and infeasibility reports should be investigated rather than suppressed.

Optimization can also create ethical concerns. A staffing model that minimizes cost may produce unsafe workloads; an allocation model may disadvantage protected groups if historical data encode discrimination. Governance should include fairness checks, scenario testing, human review, audit trails, and explicit accountability. The objective function must reflect all material consequences, not merely the easiest quantity to measure.

11. Technology and Contemporary Practice

Modern LP solvers use presolve, scaling, sparse matrix methods, parallel computation, primal and dual simplex algorithms, interior-point methods, and automated crossover. Modeling languages and Python, R, Julia, and commercial analytics platforms allow analysts to separate data, model logic, and results. Solver status, feasibility tolerances, optimality gaps, and numerical warnings should always be inspected.

AI systems can assist with extracting constraints from documents, generating candidate formulations, detecting anomalous data, and explaining sensitivity results. They should not replace mathematical validation. Every AI-generated model requires independent review of variables, signs, units, boundary conditions, and business interpretation.

Best practice is to build a transparent baseline model, validate it with small test cases, compare solver output with hand calculations where possible, conduct sensitivity and scenario analysis, and communicate both the recommendation and its assumptions.

Chapter Summary

Linear programming models allocate scarce resources by optimizing a linear objective subject to linear constraints. A sound model identifies decision variables, parameters, objective coefficients, units, and operational restrictions. Graphical analysis shows that, when a finite optimum exists, an optimum occurs at an extreme point of the feasible region. The simplex method moves between basic feasible solutions, while interior-point methods approach the optimum through the interior. Standard forms use equality constraints and nonnegative variables, with slack, surplus, and artificial variables supporting algorithmic solution.

Degeneracy, infeasibility, unboundedness, alternate optima, duality, and shadow prices are essential for interpretation. Product mix, blending, transportation, allocation, and capacity planning are major applications. In practice, model quality depends on data governance, assumption testing, sensitivity analysis, ethical review, and implementation constraints such as indivisibility and uncertainty.

Key Terms

Linear program: An optimization model with a linear objective and linear constraints.

Decision variable: A controllable unknown quantity selected by the model.

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

Objective function: The linear expression maximized or minimized.

Constraint: A mathematical restriction on feasible decisions.

Feasible solution: A point satisfying every constraint and sign restriction.

Feasible region: The set of all feasible solutions.

Extreme point: A vertex of a convex feasible region.

Basic feasible solution: A feasible solution associated with a basis.

Slack variable: A nonnegative variable added to a less-than-or-equal constraint.

Surplus variable: A variable subtracted from a greater-than-or-equal constraint.

Artificial variable: A temporary variable used to construct an initial basis.

Simplex method: An algorithm that moves among basic feasible solutions.

Reduced cost: A measure of the objective effect of introducing a nonbasic variable.

Degeneracy: A basic feasible solution with at least one zero basic variable.

Dual problem: The LP associated with a primal model and its resource valuations.

Shadow price: The marginal objective value of relaxing a constraint locally.

Interior-point method: An algorithm that approaches the optimum through the feasible interior.

Presolve: Solver processing that simplifies and strengthens a model before optimization.

Mixed-integer program: An optimization model requiring some variables to take integer values.

Review Questions

Short Answer Questions

1. What are the four essential components of a linear programming model?
2. Why are units important when formulating constraints?
3. What is the difference between a slack variable and a surplus variable?
4. Define degeneracy in the context of the simplex method.
5. What is the managerial interpretation of a shadow price?

Long Answer Questions

1. Explain the geometric basis of the extreme-point theorem and its connection with the simplex method.
2. Describe how a general LP is converted into standard form, including unrestricted variables and artificial variables.
3. Compare simplex and interior-point methods in terms of geometry, computational behavior, and sensitivity analysis.
4. Formulate a blending model with minimum quality, maximum quality, cost, and availability constraints, and explain every term.
5. Discuss the assumptions and limitations of LP in a real business application.

Analytical / Application Questions

1. A company makes two products using labor and machine time. Formulate an LP from supplied contribution, resource-use, capacity, and demand data, then identify which constraints are binding at the optimum.
2. A transportation model is reported as unbounded. Diagnose at least three possible formulation or data problems and specify how each could be tested.
3. An LP recommends fractional production quantities, but products must be manufactured in batches of 50. Explain why simple rounding may fail and propose an appropriate modeling extension.

Multiple Choice Questions with Answers

Question 1

In a linear program, what does a decision variable represent?

A. A known coefficient

B. A controllable quantity selected by the model

C. A constraint violation

D. The solver's running time

Correct Answer: B. A controllable quantity selected by the model

Question 2

For the product-mix model in the chapter, what is the objective value at (x₁, x₂) = (40, 20)?

A. $1,200

B. $2,000

C. $2,200

D. $3,200

Correct Answer: C. $2,200

Question 3

Which condition characterizes a feasible solution?

A. It maximizes every constraint

B. It satisfies all constraints and sign restrictions

C. It contains only integer variables

D. It must lie at the origin

Correct Answer: B. It satisfies all constraints and sign restrictions

Question 4

What is added to a constraint of the form aᵀx ≤ b when converting it to equality form?

A. A surplus variable

B. An unrestricted variable

C. A slack variable

D. A dual variable

Correct Answer: C. A slack variable

Question 5

The simplex method primarily moves between which objects?

A. Random data samples

B. Basic feasible solutions

C. Objective coefficients only

D. Interior points without changing bases

Correct Answer: B. Basic feasible solutions

Question 6

A basic feasible solution is degenerate when:

A. The objective is nonlinear

B. The feasible region is empty

C. At least one basic variable equals zero

D. All variables are unrestricted

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

Question 7

For the primal maximization model with Ax ≤ b and x ≥ 0, what is the usual dual objective?

A. Minimize bᵀy

B. Maximize bᵀy

C. Minimize cᵀy

D. Maximize Aᵀy

Correct Answer: A. Minimize bᵀy

Question 8

What is the main geometric distinction between simplex and interior-point methods?

A. Simplex uses no constraints

B. Interior-point methods approach through the interior rather than along vertices

C. Simplex applies only to nonlinear models

D. Interior-point methods require all variables to be integers

Correct Answer: B. Interior-point methods approach through the interior rather than along vertices

Question 9

In the meal case, what is the approximate solution at the intersection of the two resource constraints?

A. (100, 100)

B. (200, 300)

C. (266.67, 266.67)

D. (300, 280)

Correct Answer: C. (266.67, 266.67)

Question 10

Why may rounding a fractional LP solution be inappropriate when production occurs in batches?

A. Rounding always improves the objective

B. Rounding can violate constraints or alter feasibility

C. LP models cannot contain costs

D. Batch sizes affect only the display of results

Correct Answer: B. Rounding can violate constraints or alter feasibility