5. 数学优化
数学优化研究如何在满足一定条件下最小化或最大化目标函数，工程、经济学、金融、人工智能里都用得上。一个问题通常拆成三部分：目标函数、约束条件、求解方法。
5.1 优化问题的基本概念
5.1.1 目标函数
目标函数是需要优化的函数，可以是需要最大化的效益函数或需要最小化的成本函数。目标函数通常表示为 $f(x)$，其中 $x$ 是决策变量。
- 示例：最大化利润 $f(x) = 3x_1 + 2x_2$，其中 $x_1$ 和 $x_2$ 是生产量。
5.1.2 约束条件
约束条件是对决策变量的限制条件，通常表示为等式或不等式。约束条件定义了可行域，即所有满足这些条件的解的集合。
- 示例：生产约束条件 $x_1 + x_2 \leq 10$，表示生产量不能超过10单位。
5.1.3 可行解与最优解
- 可行解：满足所有约束条件的解称为可行解。
- 最优解：在所有可行解中使目标函数达到最优值的解称为最优解。
5.2 优化问题的分类
5.2.1 线性规划
线性规划是一类优化问题，其中目标函数和约束条件都是线性的。可以用标准的线性规划方法（如单纯形法、内点法）来求解。
- 示例：
- 目标函数：最大化 $2x_1 + 3x_2$
- 约束条件： $$ \begin{cases} x_1 + 2x_2 \leq 6 \ 3x_1 + x_2 \leq 9 \ x_1 \geq 0 \ x_2 \geq 0 \end{cases} $$
5.2.2 非线性规划
非线性规划处理的目标函数或约束条件中至少有一个是非线性的。这类问题通常比线性规划更复杂，需要更复杂的算法（如牛顿法、拟牛顿法）。
- 示例：
- 目标函数：最小化 $f(x) = x_1^2 + x_2^2$
- 约束条件：$x_1 + x_2 = 1$
5.2.3 整数规划
整数规划中的决策变量必须是整数。这种类型的优化问题可以用于调度、分配等问题。分支定界法和割平面法是常用的求解方法。
- 示例：
- 目标函数：最大化 $5x_1 + 7x_2$
- 约束条件： $$ \begin{cases} 3x_1 + 4x_2 \leq 15 \ x_1, x_2 \text{ 必须是整数} \end{cases} $$
5.2.4 动态规划
动态规划用于分阶段决策的问题，每个阶段的决策影响后续阶段。它通常用于求解最优化路径问题和资源分配问题。
- 示例：计算从起点到终点的最短路径。
5.3 优化算法
5.3.1 单纯形法
单纯形法是一种用于解决线性规划问题的算法。它通过在可行域的顶点之间移动来寻找最优解。
- 示例：使用
gonum的optimize包求解无约束优化问题（带线性约束的线性规划需要额外的库支持）：gopackage main import ( "fmt" "gonum.org/v1/gonum/optimize" ) func main() { // 目标函数: f(x) = (x0 - 3)^2 + (x1 - 2)^2，理论最小值在 (3, 2) problem := optimize.Problem{ Func: func(x []float64) float64 { return (x[0]-3)*(x[0]-3) + (x[1]-2)*(x[1]-2) }, } // 使用 Nelder-Mead 单纯形算法求解 result, err := optimize.Minimize(problem, []float64{0, 0}, nil, &optimize.NelderMead{}) if err != nil { fmt.Println("优化失败:", err) return } fmt.Println("最优解:", result.X) // 输出: 最优解: [3.0000000000000004 2] fmt.Println("目标函数值:", result.F) // 输出: 目标函数值: 1.9721522630525295e-31 }
5.3.2 牛顿法
牛顿法是一种用于求解非线性优化问题的迭代算法，通过利用目标函数的二阶导数来加速收敛。
- 示例：go
package main import ( "fmt" "math" ) func newtonMethod(f func(float64) float64, df func(float64) float64, x0 float64, tol float64, maxIter int) float64 { x := x0 for i := 0; i < maxIter; i++ { fx := f(x) dfx := df(x) if math.Abs(dfx) < tol { return x } x = x - fx/dfx } return x } func main() { f := func(x float64) float64 { return x*x - 2 } df := func(x float64) float64 { return 2 * x } root := newtonMethod(f, df, 1, 1e-6, 100) fmt.Println("根:", root) }
5.3.3 遗传算法
遗传算法是一种基于自然选择和遗传学的优化算法，适用于求解复杂的优化问题，如组合优化问题。
- 示例：优化问题的适应度函数、选择、交叉和变异操作的实现需要根据具体问题进行定制。
5.4 应用实例
5.4.1 资源分配
在制造业和项目管理中，优化资源分配可以最大化效益或最小化成本。例如，优化生产计划、员工排班等。
5.4.2 机器学习
许多机器学习算法，如支持向量机、神经网络训练，涉及到优化问题，通过优化目标函数来提高模型的性能。
5.4.3 物流与运输
在物流和运输领域，优化路径、配送计划能实打实降低成本。
总结
这里从目标函数和约束条件整理线性、非线性、整数、动态规划四类问题，并记录三种解法：线性问题用单纯形法，非线性用牛顿法，组合优化可以试遗传算法。前两个例子用 gonum/optimize 就能直接跑。