type
status
date
slug
summary
tags
category
icon
password
Property
解决线性规划问题有很多数学方法，例如：
- 图解法， 用几何作图的方法并求出其最优解，中学就讲过这种方法，在经济学研究中十分常用；
- 矩阵法， 引进松弛变量将线性规划问题转换成增广矩阵形式后逐次求解， 是单纯性法之前的典型方法；
- 单纯性法， 利用多面体在可行域内逐步构造新的顶点来不断逼近最优解，是线性规划研究的里程碑，至今仍然是最重要的方法之一；
- 内点法，通过选取可行域内部点沿下降方向不断迭代来达到最优解，是目前理论上最好的线性规划问题求解方法；内点法的基本算法不能处理等式约束
- 启发式方法，依靠经验准则不断迭代改进来搜索最优解 ，如贪心法、模拟退火、遗传算法、神经网络。
对于线性规划问题，什么算法是最快的呢？答案是：猜。
佐治亚理工学院彭泱教授在 2021年计算机理论顶会 SODA2021 获得最佳论文（Best paper award at ACM-SIAM symposium on discrete algorithms 2021），正是研究线性规划问题的求解——“Solving sparse linear systems faster than matrix multiplication”，所用的全新思路是：猜，反复猜，迭代猜。
当然，猜起来比较快只是在某些特殊条件下才有效的，至于在什么条件下猜，怎么猜，这不是我们所要关心，所能理解的问题了
一般线性规划问题的标准形式为：
满足所有约束条件的解，称为线性规划问题的可行解；所有可行解构成的集合，称为可行域。
使目标函数达到最小值的解，称为最优解。
线性规划问题的建模和求解，通常按照以下步骤进行：
- 问题定义，确定决策变量、目标函数和约束条件
- 模型构建，由问题描述建立数学方程，并转化为标准形式的数学模型
- 模型求解，用标准模型的优化算法对模型求解，得到优化结果
很多 Python 的第三方包，都提供求解线性规划问题的算法，有的工具包还提供整数规划、非线性规划的算法。例如：
- Scipy 库提供了解简单线性或非线性规划问题，但是不能求解如背包问题的0-1规划问题，或整数规划问题，混合整数规划问题。
- PuLP 可以求解线性规划、整数规划、0-1规划、混合整数规划问题，提供多种针对不同类型问题的求解器。
- Cvxpy 是一种凸优化工具包，可以求解线性规划、整数规划、0-1规划、混合整数规划、二次规划和几何规划问题。
- 此外，SKlearn、DOcplex、Pymprog 等很多第三方工具包也都能求解线性规划问题。