Optimization and Decision Models

Introduction

Organizations continually make decisions under scarcity. A software firm allocates developers among projects, a retailer selects inventory quantities, a hospital schedules operating rooms, and a public agency distributes funds among competing programs. In each situation, decision makers seek desirable outcomes while respecting limited resources, technical requirements, policies, and uncertainty. Optimization provides a systematic mathematical language for these choices.

An optimization model represents a decision situation using:

• Decision variables: quantities or choices controlled by the decision maker.
• An objective function: a numerical measure to maximize or minimize.
• Constraints: restrictions that feasible decisions must satisfy.
• Parameters: known or estimated data such as costs, capacities, times, and revenues.
• A solution: a feasible decision, preferably one that produces the best objective value.

Optimization does not replace managerial judgment. It clarifies assumptions, exposes trade-offs, supports transparent comparison, and identifies the consequences of changing resources or priorities.

Learning Objectives

After studying this chapter, you should be able to:

1. Translate practical situations into objective functions and constraints.
2. Distinguish feasible, optimal, integer, linear, and nonlinear models.
3. Solve small linear programs graphically and by systematic reasoning.
4. Formulate and interpret integer and binary decision models.
5. Explain introductory nonlinear optimization and local versus global optima.
6. Apply optimization to resource allocation, scheduling, and cost-benefit decisions.
7. Interpret sensitivity, assumptions, limitations, and ethical implications of models.
8. Use spreadsheet or software solvers responsibly to support data-driven decisions.

1. The Structure of an Optimization Model

A general optimization problem can be written as:

Here, x is a vector of decision variables; f(x) is the objective function; g_i(x) ≤ b_i are inequality constraints; h_j(x) = c_j are equality constraints; and X specifies restrictions such as non-negativity, integrality, or binary values. The symbols b_i and c_j are model parameters.

A maximization objective may represent profit, coverage, service quality, or social benefit. A minimization objective may represent cost, distance, risk, delay, or energy consumption. Units must be consistent: if a cost coefficient is measured in dollars per unit, multiplying it by a quantity in units gives dollars.

1.1 Decision variables

Suppose a bakery produces cakes and bread. Let:

• x₁ = number of cakes produced per day;
• x₂ = number of loaves of bread produced per day.

If production quantities cannot be negative, then x₁ ≥ 0 and x₂ ≥ 0. If only whole products can be produced, x₁ and x₂ must also be integers.

Variables may be continuous, integer, or binary:

1.2 Objective function

If each cake contributes ₹40 and each loaf contributes ₹20, daily contribution is:

The coefficients 40 and 20 are contribution margins, not necessarily selling prices. If a product has selling price p and variable cost c, its contribution per unit is p − c.

1.3 Constraints

Suppose each cake uses 2 hours of labor and each loaf uses 1 hour, while 40 labor hours are available. The labor constraint is:

If the bakery has 30 kg of flour, with 1 kg per cake and 0.5 kg per loaf, the flour constraint is:

The complete model also includes x₁, x₂ ≥ 0. A constraint can be an upper bound, lower bound, equality, logical condition, or capacity relationship.

1.4 Feasible and optimal solutions

A feasible solution satisfies every constraint. The feasible region is the set of all feasible solutions. An optimal solution is a feasible solution with the best objective value. A model can have:

• no feasible solution, when constraints conflict;
• one optimum;
• multiple optimal solutions;
• an unbounded objective, when improvement is possible without limit.

A mathematically optimal solution is meaningful only if the model represents the real decision context adequately.

2. Linear Programming

A linear programming (LP) model has a linear objective and linear constraints. A typical LP is:

The coefficient cⱼ is the objective contribution of one unit of variable xⱼ; aᵢⱼ is the amount of resource i used by one unit of xⱼ; and bᵢ is the available amount of resource i. Linearity assumes proportionality and additivity: doubling an activity doubles its resource use and contributions, and combined activities have summed effects.

2.1 Graphical solution of a two-variable LP

Consider a small furniture producer making tables and chairs. Let:

• x = tables produced per week;
• y = chairs produced per week.

Each table contributes ₹300 and each chair ₹200. The weekly model is:

To identify the feasible-region corner points, find intercepts and the intersection of the two resource boundaries. The carpentry boundary is 4x + 2y = 40, or 2x + y = 20. Its intercepts are (10, 0) and (0, 20). The finishing boundary 2x + 3y = 30 has intercepts (15, 0) and (0, 10).

At the intersection:

Subtracting the first equation from the second gives 2y = 10, so y = 5. Substitution gives 2x + 5 = 20, hence x = 7.5. The relevant corner points are (0, 0), (10, 0), (7.5, 5), and (0, 10).

Evaluate the objective:

The continuous LP optimum is x = 7.5 tables and y = 5 chairs, with contribution ₹3,250. If tables and chairs must be whole units, this solution is not implementable directly; an integer model is needed.

For a feasible two-variable LP with a bounded objective, at least one optimum occurs at a corner point of the feasible polygon. This property motivates the graphical method and, in higher dimensions, algorithms such as the simplex method and interior-point methods.

2.2 Slack and binding constraints

For a constraint of the form resource use ≤ availability, slack is unused capacity:

At (7.5, 5), carpentry use is 4(7.5) + 2(5) = 40, so carpentry slack is 0. Finishing use is 2(7.5) + 3(5) = 30, also with zero slack. Both constraints are binding. A constraint with positive slack is non-binding at the solution.

A binding constraint may indicate a bottleneck. However, zero slack does not automatically mean that increasing capacity will improve the objective; the marginal value of capacity must also be considered.

2.3 Shadow prices and sensitivity

A shadow price estimates the change in optimal objective value from a one-unit increase in a resource right-hand side, while other parameters remain unchanged and the same optimal basis remains valid. It is a local, not universal, estimate.

If an additional hour of carpentry would increase maximum contribution by ₹50 over a small valid range, ₹50 is the carpentry shadow price. It should not be interpreted as a market price or as a guarantee for large capacity changes.

Sensitivity analysis asks questions such as:

• How much can a profit coefficient change before the chosen plan changes?
• Which resource is most valuable to expand?
• What happens if demand or capacity estimates are wrong?

Such analysis is essential because optimization data are often forecasts rather than certainties.

3. Integer and Binary Optimization

LP solutions may be fractional even when real decisions are indivisible. Integer programming (IP) requires some or all variables to be integers:

A mixed-integer linear program (MILP) contains both continuous and integer variables. A binary program uses xⱼ ∈ {0, 1}.

3.1 Project selection

A company has a capital budget of ₹10 million and evaluates four projects. Let x_i = 1 if project i is selected and 0 otherwise.

The model is:

Enumerating feasible combinations for this small example gives:

• A + B: cost 7, benefit 12;
• A + D: cost 6, benefit 10;
• B + C: cost 9, benefit 14;
• B + D: cost 5, benefit 8;
• C + D: cost 8, benefit 12;
• A + B + D: cost 9, benefit 15.

The best listed combination is A + B + D, with cost ₹9 million and benefit ₹15 million. C cannot be added to that combination because the budget would be exceeded. For larger problems, branch-and-bound and cutting-plane methods systematically search and eliminate regions rather than enumerate every combination.

3.2 Logical constraints

Binary variables express policy rules. If project C requires project A, write:

If exactly one of projects A and B may be chosen:

If at most one may be chosen:

If selecting project A activates a fixed cost F, with continuous operating quantity q, a common formulation is:

where M is a valid upper bound. Choosing M unnecessarily large can weaken computational performance and may cause numerical difficulties. It should be based on a defensible capacity or demand limit.

3.3 Scheduling formulation

Let x_{jt} = 1 when job j starts at time period t. If each job starts exactly once:

If a machine can process at most one job in each period, the sum of variables representing jobs occupying that period must not exceed 1. Precedence, release-time, staffing, and deadline constraints can be added. Scheduling models are powerful but require precise definitions of processing time, setup time, breaks, and allowable assignments.

4. Nonlinear Optimization

A model is nonlinear when the objective or at least one constraint includes products, powers, ratios, exponential functions, or other nonlinear relationships. For example, a revenue function may exhibit diminishing returns:

Here x is an activity level and Z is measured in monetary units. The negative quadratic term means that marginal revenue decreases as x increases.

For an unconstrained differentiable problem, an interior optimum must satisfy:

For the example:

Setting the derivative to zero gives x = 100. The second derivative is Z″(x) = −1 < 0, so the function is concave and x = 100 is a maximum. The objective value is 100(100) − 0.5(100²) = 5,000. The bounds do not invalidate this solution because 100 lies between 0 and 120.

For a differentiable multivariable function f(x), an interior stationary point satisfies the gradient condition:

A Hessian matrix of second derivatives can help classify a stationary point. For a maximization problem, a negative-definite Hessian at the point implies a strict local maximum. These tests apply under differentiability and appropriate regularity conditions.

4.1 Local and global optima

A local optimum is best within a neighborhood. A global optimum is best throughout the feasible region. In a concave maximization problem over a convex feasible set, any local maximum is global. In nonconvex problems, several local optima may exist, so a numerical algorithm's result may depend on its starting point.

Common approaches include gradient-based methods, sequential quadratic programming, nonlinear programming solvers, and global-search heuristics. Numerical results should be checked for constraint violations, convergence status, sensitivity to starting values, and plausibility.

4.2 Lagrange multipliers

For a differentiable problem maximizing f(x, y) subject to g(x, y) = b, define:

At an interior constrained optimum, under suitable regularity conditions:

The multiplier λ is interpreted locally as the marginal change in the optimal objective value from relaxing b by one unit. This interpretation requires consistent units and a valid local solution.

5. Decision Models Beyond Optimization

Optimization selects the best modeled alternative, but many managerial decisions also involve uncertainty, multiple criteria, and non-quantifiable values.

5.1 Cost-benefit analysis

A simple net-benefit model is:

For benefits and costs occurring at different times, discounting may be used. With a constant periodic discount rate r, present value is:

CF_t is net cash flow in period t, r is the discount rate per period, and T is the final period. The net present value is the present value of benefits minus the present value of costs. Discounting assumes that timing matters and that r appropriately represents opportunity cost, risk, or policy preference. Intangible effects should not be omitted merely because they are difficult to monetize.

5.2 Expected value under uncertainty

If outcome k occurs with probability p_k and has payoff v_k, expected value is:

The probabilities must satisfy p_k ≥ 0 and ∑k p_k = 1. Expected value is an average over repeated or hypothetical scenarios; it is not a prediction that the average outcome will occur in one instance.

Decision trees represent sequential choices and uncertain events. A risk-neutral decision maker may choose the alternative with the greatest expected value, while a risk-averse decision maker may consider variance, downside exposure, or a utility function.

5.3 Multi-criteria decisions

Cost, quality, equity, reliability, and environmental impact may conflict. A weighted-score model can be written as:

where s_ik is alternative i's standardized score on criterion k and w_k is its weight, with weights commonly normalized so that ∑k w_k = 1. Standardization is essential because criteria may use different units. Weights should be documented and tested through sensitivity analysis. A weighted score is a decision aid, not an objective truth.

6. Illustrative Case: Allocating a Digital Service Budget

This is a fictional illustrative case. A university has ₹12 lakh to improve digital student services. It can fund combinations of four initiatives: a help-desk chatbot, network upgrades, accessibility remediation, and staff training. Each initiative has a one-year estimated benefit score and consumes budget. The administration also requires accessibility remediation if the chatbot is selected, because automated services must be usable by students with disabilities.

Let binary variables x_A, x_N, x_R, and x_T indicate selection. The model is:

The logical constraint x_A ≤ x_R means that selecting A requires R. Feasible combinations include A + R + T, costing 9 and scoring 22; N + R + T, costing 12 and scoring 25; and A + N + R, costing 14, which is infeasible. The combination N + R + T uses the entire budget and has the greatest score among these feasible high-value combinations.

Analysis and interpretation

The model recommends network upgrade, accessibility remediation, and training. It does not recommend the chatbot because the chatbot's cost and required accessibility investment produce a lower score under the stated data. The recommendation depends on the scoring system, estimated costs, and the requirement that accessibility accompany the chatbot.

Governance review

Before implementation, the university should ask:

• Are benefit scores based on evidence, stakeholder consultation, or subjective judgment?
• Does the scoring disadvantage students whose needs are not well represented by historical data?
• Are privacy, cybersecurity, procurement, and accessibility obligations satisfied?
• What happens if costs exceed estimates or benefits arrive later than expected?
• Should a minimum accessibility investment be mandatory regardless of score?

Outcome and learning points

The case demonstrates that a compact binary model can make dependencies explicit and compare portfolios consistently. It also shows that a mathematically optimal portfolio is not automatically ethically or operationally acceptable. Validation, stakeholder review, and monitoring are part of the decision process.

7. Software, Data, and Implementation

Spreadsheet Solver, Python optimization libraries, R packages, and commercial solvers can handle models beyond manual calculation. A responsible workflow is:

1. Define the decision question and objective.
2. Identify variables, units, data sources, and time horizon.
3. Formulate constraints in plain language before coding.
4. Implement the model and test it on a small instance.
5. Verify feasibility independently.
6. Compare the solution with benchmarks and alternative scenarios.
7. Perform sensitivity, stress, and what-if analysis.
8. Present assumptions, limitations, and implementation conditions.
9. Monitor actual outcomes and update the model.

A solver's status message is not proof of a meaningful answer. Common implementation errors include reversed inequalities, incorrect units, omitted non-negativity restrictions, accidental duplicate constraints, and using rounded coefficients that change feasibility.

AI can assist with data cleaning, scenario generation, code suggestions, and natural-language explanations. It should not be trusted to invent constraints, infer sensitive preferences, or make consequential decisions without validation. Human review is required when decisions affect employment, credit, healthcare, education, public access, or other protected interests.

8. Limitations, Ethics, and Best Practices

Optimization models simplify reality. Important limitations include:

• Parameter uncertainty: costs, demand, times, and probabilities may be estimated poorly.
• Model risk: omitted constraints or an inappropriate objective can produce harmful recommendations.
• Conflicting values: a single score may conceal equity or distributional effects.
• Infeasibility: strict requirements may conflict; relaxing a constraint should be justified, not hidden.
• Computational complexity: integer and nonlinear models may be difficult to solve exactly.
• Behavioral response: people may change behavior when policies or allocations change.
• Fairness and privacy: data-driven objectives may reproduce historical discrimination or expose personal information.

Best practice is to maintain an audit trail of data sources, transformations, assumptions, model versions, solver settings, and approvals. Report ranges rather than false precision. Use scenario analysis and, where appropriate, robust or stochastic optimization to represent uncertainty. Explain who benefits, who bears costs, and what appeal or review mechanisms exist.

A useful distinction is between optimization validity and decision legitimacy. Optimization validity concerns whether the mathematics is correctly solved. Decision legitimacy concerns whether the objective, data, constraints, governance, and consequences are acceptable. Both are necessary for professional practice.

Chapter Summary

Optimization models formalize decisions under constraints through decision variables, objective functions, parameters, and feasibility conditions. Linear programming applies when objectives and constraints are linear; graphical analysis reveals corner-point solutions in two variables, while simplex and interior-point methods address larger continuous models. Integer and binary programming represent indivisible choices, project selection, logical dependencies, and scheduling decisions. Nonlinear optimization handles diminishing returns and other nonlinear relationships, but requires attention to local versus global optima and algorithmic convergence.

Cost-benefit analysis, expected value, decision trees, and multi-criteria scoring extend optimization to timing, uncertainty, and competing values. Software enables realistic models, but data validation, sensitivity analysis, ethical review, and transparent governance remain essential. A model should support informed human judgment rather than conceal assumptions or transfer responsibility to a solver.

Key Terms

Decision variable: A controllable quantity or choice represented in a model.

Objective function: A mathematical expression measuring the outcome to maximize or minimize.

Constraint: A condition that feasible decisions must satisfy.

Parameter: A known or estimated model value such as cost, capacity, or probability.

Feasible solution: A decision satisfying every model constraint.

Feasible region: The set of all feasible solutions.

Optimal solution: A feasible solution with the best objective value.

Linear programming: Optimization with linear objective and constraint expressions.

Slack: Unused amount of a resource or constraint allowance.

Binding constraint: A constraint satisfied at equality at a particular solution.

Shadow price: Local marginal value of relaxing a resource or right-hand-side limit.

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

Binary variable: A variable restricted to 0 or 1.

Mixed-integer linear program: A linear model containing both continuous and integer variables.

Nonlinear optimization: Optimization involving nonlinear objective or constraint expressions.

Local optimum: A solution best within a neighborhood.

Global optimum: A solution best over the entire feasible region.

Expected value: Probability-weighted average of possible outcomes.

Net present value: Discounted benefits minus discounted costs.

Sensitivity analysis: Examination of how solutions change when inputs or assumptions vary.

Review Questions

Short Answer Questions

1. Distinguish a decision variable from a parameter.
2. What does it mean for a constraint to be binding?
3. Why can a continuous LP solution be unsuitable for a production decision?
4. State one logical constraint involving binary variables.
5. Distinguish a local optimum from a global optimum.

Long Answer Questions

1. Explain the components of an optimization model and illustrate each with a resource-allocation example.
2. Describe the graphical solution method for a two-variable linear program, including the role of corner points.
3. Explain how integer and binary variables improve the representation of project selection and scheduling decisions.
4. Discuss shadow prices, sensitivity analysis, and the limitations of interpreting marginal values.
5. Explain why mathematical optimality and decision legitimacy are different requirements.

Analytical / Application Questions

1. A firm earns ₹50 per unit of product X and ₹35 per unit of product Y. X uses 2 machine hours and 1 labor hour; Y uses 1 machine hour and 2 labor hours. Weekly capacities are 40 machine hours and 50 labor hours. Formulate the LP and identify whether the point (10, 20) is feasible.
2. A department can select projects P, Q, and R with costs ₹5 lakh, ₹4 lakh, and ₹3 lakh, respectively, under a ₹7 lakh budget. P requires Q, and at least one of Q and R must be selected. Formulate binary constraints for these requirements and identify feasible project combinations.
3. A service investment has net cash flows of −₹100,000 at time 0, ₹60,000 at time 1, and ₹70,000 at time 2. Using a discount rate of 10% per period, calculate its net present value and explain one limitation of the calculation.

Multiple Choice Questions with Answers

Question 1

Which item is the objective function in an optimization model?

A. A restriction on available resources

B. A numerical expression to maximize or minimize

C. A list of data sources

D. A requirement that variables be integers

Correct Answer: B. A numerical expression to maximize or minimize

Question 2

In the furniture LP, what is the objective value at the point (7.5, 5)?

A. ₹2,000

B. ₹3,000

C. ₹3,250

D. ₹4,000

Correct Answer: C. ₹3,250

Question 3

Which condition correctly models that selecting project C requires selecting project A?

A. x_C ≥ x_A

B. x_C + x_A = 0

C. x_C ≤ x_A

D. x_C − x_A ≥ 1

Correct Answer: C. x_C ≤ x_A

Question 4

A binary decision variable can take which values?

A. Any real number

B. Only −1 and 1

C. Only 0 and 1

D. Any nonnegative integer

Correct Answer: C. Only 0 and 1

Question 5

What does positive slack indicate for a resource constraint?

A. The resource is exceeded

B. Unused capacity remains

C. The objective is unbounded

D. The model has no feasible solution

Correct Answer: B. Unused capacity remains

Question 6

For the function Z = 100x − 0.5x², the stationary point occurs at:

A. x = 0

B. x = 50

C. x = 100

D. x = 200

Correct Answer: C. x = 100

Question 7

Which expression represents expected value when outcome k has probability p_k and payoff v_k?

A. The largest v_k

B. ∑k p_kv_k

C. ∑k v_k ÷ p_k

D. ∏k p_kv_k

Correct Answer: B. ∑k p_kv_k

Question 8

In a cost-benefit model, net benefit is generally calculated as:

A. Total cost plus total benefit

B. Total benefit minus total cost

C. Total benefit divided by total cost

D. Total cost minus total benefit

Correct Answer: B. Total benefit minus total cost

Question 9

Which statement about a shadow price is correct?

A. It is always the market price of a resource

B. It is a local estimate of the value of relaxing a constraint

C. It applies only to binary variables

D. It proves that the model is ethically valid

Correct Answer: B. It is a local estimate of the value of relaxing a constraint

Question 10

Why is sensitivity analysis important in practical optimization?

A. It removes the need for data validation

B. It guarantees that uncertain forecasts are correct

C. It examines how solutions respond to changes in assumptions

D. It converts every nonlinear model into a linear model

Correct Answer: C. It examines how solutions respond to changes in assumptions