1.4.4 Linear Programming Fundamentals¶

Optimize objective functions within feasible regions to find maximum or minimum values.

定义¶

Linear Programming is a mathematical optimization technique used to find the maximum or minimum value of a linear objective function subject to a system of linear constraints (inequalities and/or equations). The feasible region is the set of all points that satisfy all constraints simultaneously, and the optimal solution occurs at a vertex (corner point) of this region. Formally, a linear programming problem has the form: optimize \(f(x, y) = ax + by\) subject to a system of linear inequalities that define the feasible region in the coordinate plane. The objective function is linear, and all constraints are linear inequalities of the form \(Ax + By \leq C\), \(Ax + By \geq C\), or \(Ax + By = C\).

核心公式¶

\(\text{Objective Function: } f(x, y) = ax + by\)
\(\text{Standard Constraint Form: } Ax + By \leq C \text{ or } Ax + By \geq C\)
\(\text{Corner Point Theorem: The optimal value occurs at a vertex of the feasible region}\)
\(\text{Feasible Region: } \{(x, y) : \text{all constraints are satisfied simultaneously}\}\)
\(\text{Optimal Solution: } (x^*, y^*) = \arg\max_{(x,y) \in \text{Feasible Region}} f(x, y)\)

易错点¶

⚠️ Forgetting to check all corner points of the feasible region—students often find only some vertices and miss the actual optimal solution, which must be evaluated at every corner point
⚠️ Incorrectly graphing inequality constraints by using solid lines instead of dashed lines for strict inequalities (\(<\) or \(>\)), or shading the wrong region, leading to an incorrect feasible region
⚠️ Confusing the direction of inequality signs when manipulating constraints, especially when multiplying or dividing by negative numbers, which reverses the inequality
⚠️ Failing to recognize that the feasible region may be unbounded, in which case the optimal solution may not exist or may occur at infinity, rather than assuming a solution always exists at a corner point