数学规划

数学规划 (Mathematical Programming)

数学规划（Mathematical Programming），又称数学优化（Mathematical Optimization），是运筹学与应用数学的核心分支，研究在给定约束条件下如何从一个可行集合中选取最优方案，使得某个目标函数达到极大值或极小值。它广泛应用于经济学、工程、管理科学和人工智能等领域，是现代决策科学与运筹学的理论基石。

数学规划的标准形式可表述为：在约束条件 $g_i(x) \leq 0$（$i=1,\dots,m$）及 $h_j(x)=0$（$j=1,\dots,p$）之下，求决策变量 $x \in \mathbb{R}^n$ 使目标函数 $f(x)$ 达到最优。依据目标函数和约束函数的线性或非线性、变量的连续或离散等特征，数学规划可分为多种类型。

线性规划 (Linear Programming, LP)

线性规划是数学规划中最基本也最成熟的分支。其目标函数和所有约束条件均为决策变量的线性函数。LP 的可行域是凸多面体，最优解必定出现在可行域的顶点（极点）上，这一几何性质是单纯形法（Simplex Method）的理论基础。

1947年，乔治·丹齐格（George Dantzig）在兰德公司从事军事后勤规划时提出了单纯形法：沿着可行域多面体的边沿，从一个顶点高效移动到相邻的更优顶点，直至抵达最优解。单纯形法在实践中表现极为出色，被列为20世纪最重要的十大算法之一。与此同期，苏联数学家列昂尼德·坎托罗维奇（Leonid Kantorovich）独立发展了线性规划理论，并因其在资源最优配置方面的贡献获得1975年诺贝尔经济学奖——他也是唯一因数学规划研究而获诺贝尔奖的数学家。

LP 的核心理论成果是对偶理论（Duality）：每一个原始线性规划问题都对应一个对偶问题，在适当条件下二者的最优目标函数值相等。对偶变量（影子价格）度量了资源约束的边际价值：它告诉决策者增加一单位某种资源能够带来多大的目标函数改善。这一概念直接为经济学中的影子价格和资源配置理论提供了严格的数学框架。

1984年，纳伦德拉·卡马卡（Narendra Karmarkar）提出了内点法（Interior Point Method），从可行域内部逼近最优解，在理论上被证明具有多项式时间复杂度，并在大规模稀疏问题上显著优于单纯形法。内点法的出现标志着线性规划进入现代计算时代。

非线性规划 (Nonlinear Programming, NLP)

当目标函数或约束条件中至少有一个为非线性时，问题即属于非线性规划。NLP 的理论核心是KKT条件（Karush-Kuhn-Tucker Conditions）：由 Karush（1939）、Kuhn 与 Tucker（1951）各自独立提出的最优性必要条件，将拉格朗日乘数法推广至包含不等式约束的情形。对于凸规划问题——目标函数为凸且可行域为凸集——满足 KKT 条件的点即为全局最优解。

求解 NLP 的数值方法主要包括：梯度下降法及其变体（牛顿法、拟牛顿法）、序列二次规划（Sequential Quadratic Programming, SQP）、罚函数法与增广拉格朗日法等。近年来，随机梯度下降（SGD）及其动量变体（Adam、RMSprop）已成为深度学习训练的核心优化引擎，将非线性规划推向了人工智能的前沿。

整数规划与组合优化 (Integer Programming, IP)

当部分或全部决策变量被限定为整数时，问题进入整数规划范畴。若变量仅为0或1，则为0-1规划（Binary Programming）。整数规划的难度远高于连续变量情形——决策变量的离散性破坏了可行域的凸性，使问题从多项式可解变为 NP-困难（NP-Hard）。

整数规划的主流求解方法包括：分支定界法（Branch and Bound）：通过将可行域递归分割为子问题并以松弛解为界剪枝搜索树，由 Land 与 Doig（1960）提出；割平面法（Cutting Plane）：不断添加线性不等式剔除不满足整数要求的松弛解，以格莫瑞割（Gomory Cut）最为经典；分支切割法（Branch and Cut）：合二为一的现代主流框架，也是 CPLEX、Gurobi 等商业求解器的核心算法。

整数规划的典型应用场景包括：设施选址（Facility Location）、旅行商问题（TSP）、车辆路径问题（VRP）、生产调度与排班、网络设计等。在经济学中，整数规划常用于离散选择建模——如企业进入/退出决策（0-1变量）、投资组合中不可分割资产的选取等。

动态规划 (Dynamic Programming, DP)

动态规划由理查德·贝尔曼（Richard Bellman）于1950年代创立，其核心思想是最优性原理（Principle of Optimality）：一个最优策略的子策略在相应的子问题上也必须是最优的。DP 将复杂决策问题分解为相互关联的阶段，通过递归求解贝尔曼方程获得全局最优解。

动态规划在经济学中的地位尤为特殊。宏观经济学中的拉姆齐增长模型（Ramsey Growth Model）、消费平滑（Consumption Smoothing）和实际经济周期（RBC）模型均以贝尔曼方程表述为动态规划问题。马尔可夫决策过程（MDP）——强化学习的数学基础——本质上是随机动态规划。罗伯特·卢卡斯（Robert Lucas）、托马斯·萨金特（Thomas Sargent）等经济学家将动态规划推广至宏观经济政策的动态一致性分析，深刻影响了现代中央银行政策框架。

经济学的核心工具

数学规划为经济学提供了从规范分析到计算求解的完整方法论体系。在微观层面，消费者理论中的效用最大化与支出最小化构成一对 primal-dual 问题；生产者理论中的成本最小化与利润最大化同样依赖于线性规划和非线性规划技术。在宏观层面，动态随机一般均衡（DSGE）模型通过在约束条件下求解代表性个体跨期最优选择，将动态规划与非线性和随机规划融为一体。随着计算经济学（Computational Economics）的兴起和 Gurobi、CPLEX、Ipopt 等求解器性能的飞跃，数学规划正推动经济学从定性分析向大规模定量模拟不断深化。