鸡兔同笼是经典题目了, 引出线性方程组也很自然, 毕竟这里的翻译都是 1 : 1 的, 或者变量名从 x 改回 鸡 都是可以的.
为什么线性方程组可以拿来求解线性约束呢?
实际生活遇到的问题基本都是不等式约束, 比如至多只能用多少钱买东西.
于是我们学到了线性规划, 学到了画图, 推平行的直线来找最优解.
然后我们会发现, 似乎非常多的时候, 极值点都是在端点找到的, 或者说凸的区域的端点(线性不等式约束下正好满足”凸多边形在任意一条边的一侧”这个定义.
背后联系
下面来自 llm, 我就引用了.
单纯形法 (Simplex Method):
- 核心思想: 单纯形法是一种迭代算法，它从可行域的一个顶点开始，沿着可行域的边界（棱）移动到相邻的顶点，在每个顶点处评估目标函数值。由于最优解一定在可行域的顶点上，单纯形法通过不断移动到目标函数值更好的相邻顶点，最终找到最优解。
- 优点:
- 概念直观，易于理解。
- 在实际应用中，通常表现良好，迭代次数相对较少。
- 缺点:
- 在最坏情况下，时间复杂度是指数级的，尽管这种情况在实际中很少出现。
- 对于大规模问题，计算效率可能较低。
- 只能处理线性规划问题。
而这里 可行域的顶点 正是线性方程组对应直线的交点.
所以我们可以用求解线性方程组的方法来找满足约束的解.
背包问题
对于优化问题，还有个经典题目/方法：背包问题。都属于组合优化问题。
用背包解一下鸡兔同笼吧.
背包是求解约束优化的, 如果我把优化目标设成指定值
迭代法
然后求解线性方程组, 除了高斯消元法, 还有雅可比迭代法(出自数值分析)
LLM 给了个另外的, 我贴在下面了.
内点法 (Interior-Point Methods):
- 核心思想: 内点法从可行域的内部开始，沿着一个中心路径移动到最优解。它避免了像单纯形法那样在可行域的顶点之间跳跃，而是通过迭代逐步逼近最优解。常见的内点法包括障碍函数法、原始-对偶路径跟踪法等。
- 优点:
- 具有多项式时间复杂度，理论上比单纯形法更高效，尤其对于大规模问题。
- 可以推广到非线性规划问题。
- 缺点:
- 概念相对复杂，实现较为困难。
- 每一次迭代的计算量比单纯形法大。
- 需要良好的初始点，否则可能收敛缓慢。
总结比较:
特性 | 单纯形法 | 内点法 |
起始点 | 可行域顶点 | 可行域内部 |
移动路径 | 沿着可行域边界 | 穿过可行域内部 |
迭代次数 | 通常较少 | 通常较多 |
单次迭代计算量 | 较小 | 较大 |
时间复杂度 | 指数级 (最坏情况), 实际中通常较好 | 多项式级 |
适用范围 | 线性规划 | 线性规划、非线性规划 |
大规模问题 | 效率较低 | 效率较高 |
问了 llm 发现似乎是运筹学的领域, 找了本书翻翻看吧.
