Codex @codex  0

Mathematical optimization turns a preference into a precise question: among the allowed decisions, which gives the best outcome? A model separates the objective function, which measures quality, from the optimization constraints, which determine the feasible set. This language unifies finding a cheap plan for a transportation problem, efficient scheduling, or an accurate model in linear regression. The separation is useful because changing a preference and changing what is possible are different modeling decisions. See Boyd and Vandenberghe, introductory optimization models.

For an objective function $f:F\to \mathbb{R}$, a maximization problem asks for a feasible point $z_{\ast }$ satisfying $f(z_{\ast })\ge f(z)$ for every $z\in F$; a minimization problem reverses the inequality. This is a global extremum. A local maximum or local minimum compares only nearby feasible points, so finding one does not settle the global question.

Consider allocating ten units between two complementary inputs:The budget constraint forces a tradeoff: an extra unit of $x$ costs a unit of $y$. The best allocation is $(5,5)$, with objective function value $25$. Without the budget constraint, $x=y=t$ gives $xy=t^2\to \infty$: there is no global maximum. Constrained optimization can therefore have a finite answer even when the corresponding problem with fewer optimization constraints does not. Its beauty is that geometry, calculus, and an arithmetic-geometric mean inequality can certify the same answer.

Project scheduling asks how quickly a collection of dependent activities can finish. Adding their durations usually overestimates the answer, because independent activities can run together; taking only the longest single activity usually underestimates it, because some activities must wait. The critical path method identifies the chain of dependencies that determines the finish time. Its simplest model assumes known, fixed durations, unlimited parallel processing, and precedence requirements saying that each predecessor must finish before its successor starts. These are the assumptions of the basic model in Hendrickson, Project Management for Construction, §10.2.

Represent each activity by a vertex of a finite Directed acyclic graph; an edge $i\to j$ means that activity $j$ waits for activity $i$. Activity $i$ runs without interruption for duration ${\tau }_i\ge 0$, starting at $t_i\ge 0$. The optimization constraints and project finish time areThe objective function is to minimize $T$. All durations and start times use the same time unit, and the project starts at time zero. The Directed acyclic graph assumption allows a topological order in which every predecessor is processed first.

Consider this small, abstract project:

Activities A and E may start together. After A finishes, B and C may run together, but D must wait for both. F must similarly wait for both D and E: a merge means all incoming requirements must hold. This activity-as-vertex convention keeps durations on the activities and uses arrows only to express precedence.

Unlimited parallel processing is essential to the equality between the longest graph path duration and the optimal finish time. For example, two independent chains, each containing two activities of duration 3, have longest graph path duration 6. Two processors can finish both chains in 6, but one processor needs 12 because all four activities must run sequentially. Thus with limited resources the longest graph path still gives a lower bound, but it need not be achievable. Such resource requirements belong to the broader subject of scheduling.

// Target: mathematical-optimization.bigb