线性规划 （ LP ），也称为 线性优化，是一种在 数学模型 中实现最佳结果（例如最大利润或最低成本）的方法， 其要求由 线性关系 表示。 线性规划是数学规划（也称为数学优化 ）的特例 。

更正式地说，线性规划是一种 优化 线性 目标函数 的技术 ，受 线性等式 和 线性不等式 约束 。 它的 可行区域 是 凸多面体 ，它是定义为 有限多个 半空间的 交集的集合 ，每个半空间由线性不等式定义。 其目标函数是 在该多面体上定义的 实 值 仿射（线性）函数。 线性规划 算法在 多胞形 中找到该函数具有最大（或最小）值的 点（如果存在这样的点）。

线性规划是可以用 标准形式 表示的问题

找到一个向量 � 最大化 � 时间 � 受 � � ≤ 乙 和 � ≥ 0 。

这里的组件 � 是要确定的变量， � 和 乙 给 定向量 ，并且 � 是给定 矩阵 . 其值要最大化的函数 ( � ↦ � 时间 � 在这种情况下）称为 目标函数 。 限制条件 � � ≤ 乙 和 � ≥ 0 指定 要优化目标函数的 凸多面体。

线性规划可以应用于各个研究领域。 它广泛应用于数学，并在较小程度上应用于商业、 经济学 和一些工程问题。 使用线性规划模型的行业包括交通、能源、电信和制造。 事实证明，它对于规划 、 路由 、 调度 、 分配 和设计 中的各种类型问题建模非常有用。

具有两个变量和六个不等式的简单线性程序的图示。可行解集用黄色表示，并形成一个 多边形 ，即二维 多面体 。线性成本函数的最佳值是红线与多边形相交的位置。红线是成本函数的 水平集 ，箭头表示我们优化的方向。 具有三个变量的问题的封闭可行区域是凸 多面体 。给出目标函数固定值的表面是 平面 （未示出）。线性规划问题是找到多面体上具有最高可能值的平面上的点。

历史 [ 编辑 ]

列昂尼德·康托罗维奇 约翰·冯·诺依曼

解决线性不等式系统的问题至少可以追溯到 傅里叶 ，他于 1827 年发表了一种解决线性不等式的方法， ^[1] ，傅里叶-莫茨金消除 法 就是以他的名字命名的。

1939 年，苏联 数学家 和 经济学家 Leonid Kantorovich 给出了与一般线性规划问题等价的线性规划公式 ，并提出了解决该问题的方法。 ^[2] 这是他在 第二次世界大战 期间开发的一种计划支出和回报的方法，以减少军队的成本并增加敌人的损失。 ^{[ 需要引用 ]} 康托罗维奇的工作最初在 苏联 被忽视。 ^[3] 大约与康托罗维奇同时期，荷兰裔美国经济学家 TC Koopmans 将经典经济问题表述为线性规划。 康托罗维奇和库普曼斯后来分享了 1975 年 诺贝尔经济学奖 。 ^[1] 1941年， 弗兰克·劳伦·希区柯克还将交通问题表述为线性规划，并给出了与后来的 单纯形法 非常相似的解决方案 。 ^[2] 希区柯克于1957年去世，诺贝尔奖不追授。

从 1946 年到 1947 年， George B. Dantzig 独立开发了通用线性规划公式，用于解决美国空军的规划问题。 ^[4] 1947年，Dantzig还发明了 单纯形法 ，首次有效地解决了大多数情况下的线性规划问题。 ^[4] 当丹齐格安排与 约翰·冯·诺依曼 会面讨论他的单纯形方法时，诺依曼意识到他一直在 博弈论中研究的问题是等价的，立即猜想了对 偶 理论 。 ^[4] Dantzig 在 1948 年 1 月 5 日未发表的报告《线性不等式定理》中提供了正式的证明。 ^[3] Dantzig 的工作于 1951 年向公众公开。战后几年，许多行业将其应用于各自的领域。每日计划。

Dantzig 最初的例子是找到 70 个人到 70 个工作岗位的最佳分配。 测试所有排列以选择最佳分配所需的计算能力是巨大的； 可能的配置数量超过了 可观测宇宙 中的 粒子数量 。 然而，通过将问题视为线性规划并应用单纯形算法 ，只需片刻即可找到最佳解决方案 。 线性规划背后的理论大大减少了必须检查的可能解决方案的数量。

Leonid Khachiyan 于 1979 年首次证明线性规划问题可以在多项式时间内求解 ， ^[5] 但该领域更大的理论和实践突破出现在 1984 年，当时 Narendra Karmarkar 引入了一种新的 内点方法 来求解线性规划问题。 ^[6]

用途 [ 编辑 ]

由于多种原因，线性规划是广泛使用的优化领域。 运筹学 中的许多实际问题 都可以表示为线性规划问题。 ^[3] 线性规划的某些特殊情况，例如 网络流 问题和 多商品流 问题 ，被认为足够重要，需要对专门算法进行大量研究。 许多其他类型优化问题的算法通过将线性规划问题作为子问题来解决。 从历史上看，线性规划的思想启发了优化理论的许多核心概念，例如对 偶性、 分解以及 凸性 及其概括 的重要性。 同样，线性规划在微观经济学 的早期形成中被大量使用 ，目前也被用于公司管理，例如计划、生产、运输和技术。 尽管现代管理问题日新月异，但大多数企业都希望以有限的资源实现 利润最大化 、成本最小化。 Google 还使用线性规划来稳定 YouTube 视频。 ^[7]

标准形式 [ 编辑 ]

标准形式 是描述线性规划问题的常用且最直观的形式。 它由以下三部分组成：

要最大化的线性（或仿射） 函数

例如 � （ � 1 , � 2 ） = � 1 � 1 + � 2 � 2

问题约束 如下形式

� 11 � 1 + � 12 � 2 ≤ 乙 1 � 21 � 1 + � 22 � 2 ≤ 乙 2 � 31 � 1 + � 32 � 2 ≤ 乙 3

� 1 ≥ 0 � 2 ≥ 0

问题通常用 矩阵 形式 表示，则变为：

最大限度 { � 时间 � ∣ � ε 右 � ∧ � � ≤ 乙 ∧ � ≥ 0 }

其他形式，例如最小化问题、替代形式约束问题以及涉及负 变量 的问题始终可以重写为标准形式的等效问题。

示例 [ 编辑 ]

农民示例的图形解决方案 - 在违反条件的阴影区域之后，距离原点最远的虚线的未阴影区域的顶点给出了最佳组合（它位于农药和土地线上意味着农药和土地限制收入）

假设一个农民有一块农田，比如说 L km ² ，要种植小麦或大麦或两者的某种组合。 农民的肥料数量有限， F 千克，农药数量有限， P 千克。 每平方公里小麦需要 F ₁ 公斤化肥和 P ₁ 公斤农药，而每平方公里大麦则需要 F _{2 公斤} 化肥和 P ₂ 公斤农药。 设S ₁ 为每平方公里小麦的销售价格，S ₂ 为大麦的销售价格。 如果我们分别用x ₁ 和 x ₂ 表示种植小麦和大麦的土地面积，那么通过选择 x ₁ 和 x ₂ 的最佳值可以使利润最大化 。 该问题可以用以下标准形式的线性规划问题来表示：

最大化： � 1 ⋅ � 1 + � 2 ⋅ � 2 （最大化收入（小麦总销量加上大麦总销量）——收入是“目标函数”） � 1 + � 2 ≤ � （总面积限制） � 1 ⋅ � 1 + � 2 ⋅ � 2 ≤ � （肥料限制） 磷 1 ⋅ � 1 + 磷 2 ⋅ � 2 ≤ 磷 （农药限量） � 1 ≥ 0 , � 2 ≥ 0 （不能种植负区域）。

以矩阵形式表示为：

最大化 [ � 1 � 2 ] [ � 1 � 2 ]

受 [ 1 1 � 1 � 2 磷 1 磷 2 ] [ � 1 � 2 ] ≤ [ � � 磷 ] , [ � 1 � 2 ] ≥ [ 0 0 ] 。

增强形式（松弛形式） [ 编辑 ]

线性规划问题可以转换为 增广形式 ，以便应用 单纯形算法 的常见形式。 这种形式引入了非负 松弛变量， 用约束中的等式代替不等式。 然后可以将问题写成以下 块矩阵 形式：

最大化 � :

[ 1 - � 时间 0 0 � 我 ] [ � � � ] = [ 0 乙 ]

� ≥ 0 , � ≥ 0

在哪里 � 是新引入的松弛变量， � 是决策变量，并且 � 是要最大化的变量。

示例 [ 编辑 ]

上面的例子被转换成下面的增强形式：

最大化 � :

[ 1 - � 1 - � 2 0 0 0 0 1 1 1 0 0 0 � 1 � 2 0 1 0 0 磷 1 磷 2 0 0 1 ] [ � � 1 � 2 � 3 � 4 � 5 ] = [ 0 � � 磷 ] , [ � 1 � 2 � 3 � 4 � 5 ] ≥ 0。

二元性 [ 编辑 ]

主条目： 对偶线性规划

每个线性规划问题（称为 原始 问题）都可以转换为对 偶问题 ，它提供了原始问题最优值的上限。 以矩阵形式，我们可以 将原 问题表示为：

最大化 c ^T x ，且满足 A x ≤ b 、 x ≥ 0；

与相应的 对称 对偶问题，

在A ^T y ≥ c , y ≥ 0 的条件下 最小化 b ^T y 。

另一种原始公式是：

在A x ≤ b 的情况下 最大化 c ^T x ；

以及相应的 不对称对 偶问题，

最小化 b ^T y ， 且满足 A ^T y = c , y ≥ 0。

对偶理论有两个基本思想。 其一是（对于对称对偶）对偶线性程序的对偶是原始线性程序。 此外，线性规划的每个可行解都给出了其对偶目标函数最优值的界限。 弱 对偶 定理指出，对偶在任何可行解处的目标函数值总是大于或等于原始在任何可行解处的目标函数值。 强 对偶 定理指出，如果原数有一个最优解 x ^* ，那么对偶也有一个最优解 y ^* ，并且 c ^T x ^* = b ^T y ^* 。

线性规划也可以是无界的或不可行的。 对偶理论告诉我们，如果原数是无界的，那么根据弱对偶定理，对偶是不可行的。 同样，如果对偶是无界的，那么原数必定是不可行的。 然而，对偶和原始都有可能都不可行。 有关详细信息和更多示例， 请参阅 双线性程序。

变体 [ 编辑 ]

覆盖/包装二元性 [ 编辑 ]

覆盖/包装问题对 覆盖问题包装问题最小设定覆盖范围最大套装包装最小边缘覆盖最大匹配最小顶点覆盖最大独立集箱盖箱式包装多边形覆盖长方形包装

使得矩阵 A 以及向量 b 和 c 都是非负的。

例子 [ 编辑 ]

覆盖和打包 LP 通常作为组合问题的 线性规划松弛而出现，并且在 近似算法 的研究中很重要 。 ^[8] 例如， 集合打包问题 、 独立集合问题 和 匹配问题 的LP松弛都是打包LP。 集合覆盖问题 、 顶点覆盖问题 和 支配集问题 的LP松弛 也覆盖LP。

查找 图形 的 分数着色 是覆盖 LP 的另一个示例。 在这种情况下，图的每个顶点都有一个约束，并且 图的 每个 独立组都有一个变量。

互补松弛 [ 编辑 ]

当使用互补松弛定理仅知道原数的最优解时，可以获得对偶的最优解。 该定理指出：

假设 x = ( x ₁ , x ₂ , ... , x _n ) 是原始可行的，并且 y = ( y ₁ , y ₂ , ... , y _m ) 是对偶可行的。 令( w ₁ , w ₂ , ..., w _m ) 表示相应的原始松弛变量，令( z ₁ , z ₂ , ... , z _n ) 表示相应的对偶松弛变量。 那么 x 和 y 对于各自的问题来说是最优的当且仅当

x _j z _j = 0，对于 j = 1, 2, ... , n ，并且

w _i y _i = 0，对于 i = 1, 2, ... , m 。

因此，如果原数的 第 i 个松弛变量不为零，则对偶数的 第 i 个变量等于 0。 同样，如果对偶的 第 j 个松弛变量不为零，则原数的 第 j 个变量等于 0。

这种最优性的必要条件传达了一个相当简单的经济原理。 在标准形式中（最大化时），如果受约束的原始资源存在松弛（即存在“剩余”），则该资源的额外数量必定没有价值。 同样，如果双重（影子）价格非负约束要求存在松弛，即价格不为零，则必定存在稀缺供应（没有“剩余”）。

理论 [ 编辑 ]

最优解的存在性 [ 编辑 ]

在几何上，线性约束定义了 可行区域 ，它是 凸多面体 。 线性函数 是 凸 函数 ，这意味着每个 局部最小值 都是 全局最小值 ； 类似地，线性函数是 凹函数 ，这意味着每个 局部最大值 都是 全局最大值 。

由于两个原因，不一定存在最佳解决方案。 首先，如果约束条件不一致，则不存在可行解：例如，约束条件 x≥2 和 x≤1 不能同时满足； 在这种情况下，我们说 LP 是 不可行的 。 其次，当 多胞形 在目标函数的梯度方向上无界时（其中目标函数的梯度是目标函数系数的向量），则无法获得最优值，因为总是可以这样做优于目标函数的任何有限值。

多面体的最佳顶点（和射线） [ 编辑 ]

否则，如果存在可行解并且约束集有界，则通过凸函数的极大 值 原理 （或者，通过 凹函数 的极小 值原理 ），始终在约束集的边界上获得最佳值， 因为线性函数既有凸函数又有凹函数。 然而，有些问题有不同的最优解； 例如，寻找线性不等式系统的可行解的问题是一个线性规划问题，其中目标函数是零函数（即处处取零值的常数函数）。 对于目标函数为零的可行性问题，如果有两个不同的解，则解的每个凸组合都是一个解。

多面体的顶点也称为 基本可行解 。 选择这个名称的原因如下。 令 d 表示变量的数量。 那么线性不等式的基本定理意味着（对于可行问题）对于 LP 可行区域的每个顶点 x ^* ，存在一组 来自 LP 的 d个（或更少）不等式约束，这样，当我们将这些 d 约束视为 等式的唯一解是 x ^* 。 因此，我们可以通过查看所有约束集（离散集）的某些子集来研究这些顶点，而不是 LP 解的连续体。 这一原理是 求解线性规划的 单纯形算法的基础。

算法 [ 编辑 ]

另请参阅： 数值分析主题列表 § 线性规划

在线性规划问题中，一系列线性约束产生这些变量的可能值的 凸 可行区域 。 在二变量情况下，该区域的形状是凸 简单多边形 。

基础交换算法 [ 编辑 ]

Dantzig 单纯形算法 [ 编辑 ]

单纯 形算法是由 George Dantzig 在 1947 年开发的，它通过在 多胞形 的顶点构造可行解 ，然后沿着多胞形边缘上的路径行走到目标函数值不减的顶点来解决线性规划问题，直到肯定达到了最佳状态。 在许多实际问题中，都会发生“ 停顿 ”：在目标函数没有增加的情况下进行了许多枢轴。 ^{[9] [10]} 在罕见的实际问题中，单纯形算法的常用版本实际上可能会“循环”。 ^[10] 为了避免循环，研究人员制定了新的旋转规则。 ^[11]

在实践中，单纯形 算法 非常有效，如果 采取某些防止 循环的预防措施，可以保证找到全局最优值。 单纯形算法已被证明可以有效地解决“随机”问题，即以立方数的步骤， ^[12] ，这与其在实际问题上的行为相似。 ^{[9] [13]}

然而，单纯形算法在最坏情况下的表现很差：Klee 和 Minty 构建了一系列线性规划问题，对于这些问题，单纯形方法需要执行的步骤数与问题大小呈指数关系。 ^{[9] [14] [15]} 事实上，有一段时间我们不知道线性规划问题是否可以在 多项式时间 内求解，即 复杂度等级为 P 。

十字交叉算法 [ 编辑 ]

与 Dantzig 的单纯形算法类似， 十字交叉算法 是一种在基之间旋转的基交换算法。 然而，十字交叉算法不需要保持可行性，而是可以从可行的基础转向不可行的基础。 十字交叉算法不具有线性规划的 多项式时间复杂度 。 在 最坏的情况 下，两种算法都会访问 D 维 （扰动） 立方体 （克利 -明蒂立方体）的所有 ^二维 角。 ^{[11] [16]}

内点 [ 编辑 ]

与通过遍历多面体集合上的顶点之间的边来找到最优解的单纯形算法相比，内点方法在可行区域的内部移动。

椭圆体算法，遵循 Khachiyan [ 编辑 ]

这是有史以来第一个 用于线性规划的 最坏情况 多项式时间算法。 为了解决具有 n 个变量并且可以用 L 个 输入位 进行编码的问题，该算法运行在 氧 （ � 6 � ） 时间。 ^[5] Leonid Khachiyan在 1979 年通过引入 椭球体方法 解决了这个长期存在的复杂性问题 。 收敛分析有（实数）前身，特别是 Naum Z. Shor 开发的 迭代方法 以及 Arkadi Nemirovski 和 D. Yudin 开发的 近似算法。

Karmarkar 投影算法 [ 编辑 ]

主条目： Karmarkar 算法

Khachiyan 的算法对于建立线性规划的多项式时间可解性具有里程碑式的重要性。 该算法并不是计算上的突破，因为单纯形法对于除特殊构造的线性程序族之外的所有线性程序都更有效。

然而，Khachiyan 的算法激发了线性规划的新研究方向。 1984年， N. Karmarkar 提出了线性规划的 投影方法 。 Karmarkar 的算法 ^[6] 改进了 Khachiyan 的 ^[5] 最坏情况多项式界（给出 氧 （ � 3.5 � ） ）。 Karmarkar 声称他的算法在实际的线性规划中比单纯形法快得多，这一说法引起了人们对内点方法的极大兴趣。 ^[17] 自从Karmarkar的发现以来，许多内点方法被提出并分析。

Vaidya 的 87 算法 [ 编辑 ]

1987年，Vaidya提出了一种运行在 氧 （ � 3 ） 时间。 ^[18]

Vaidya 的 89 算法 [ 编辑 ]

1989 年，Vaidya 开发了一种运行在 氧 （ � 2.5 ） 时间。 ^[19] 从形式上来说，该算法采用 氧 （ （ � + � ） 1.5 � � ） 最坏情况下的算术运算，其中 � 是约束的数量， � 是变量的数量，并且 � 是位数。

输入稀疏时间算法 [ 编辑 ]

2015 年，Lee 和 Sidford 表明，它可以通过 氧 ～ （ （ � � � （ � ） + � 2 ） � � ） 时间， ^[20] 其中 � � � （ � ） 表示非零元素的个数，仍然取 氧 （ � 2.5 � ） 在最坏的情况下。

当前矩阵乘法时间算法 [ 编辑 ]

2019 年，Cohen、Lee 和 Song 将运行时间改进为 氧 ～ （ （ � � + � 2.5 - � / 2 + � 2 + 1 / 6 ） � ） 时间， � 是矩阵乘法 的指数 ， � 是矩阵 乘法的对偶 指数。 ^[21] � 被（粗略地）定义为可以乘以一个的最大数字 � × � 矩阵由一个 � × � � 矩阵中 氧 （ � 2 ） 时间。 在李、宋和张的后续工作中，他们通过不同的方法重现了相同的结果。 ^[22] 这两种算法仍然存在 氧 ～ （ � 2 + 1 / 6 � ） 什么时候 � = 2 和 � = 1 。 结果由于江、宋、韦恩斯坦和张的提高 氧 ～ （ � 2 + 1 / 6 � ） 到 氧 ～ （ � 2 + 1 / 18 � ） 。 ^[23]

内点法和单纯形算法的比较 [ 编辑 ]

目前的观点是，对于线性规划的常规应用，基于单纯形的方法和内点方法的良好实现的效率是相似的。 然而，对于特定类型的 LP 问题，一种类型的求解器可能比另一种更好（有时好得多），并且内点方法与基于单纯形的方法生成的解的结构在支持下显着不同。后者的活动变量集通常较小。 ^[24]

未解决的问题和最近的工作 [ 编辑 ]

计算机科学中未解决的问题 ：

线性规划是否承认强多项式时间算法？

（更多计算机科学中未解决的问题）

线性规划理论中有几个悬而未决的问题，这些问题的解决将代表数学上的根本性突破，并可能代表我们解决大规模线性规划的能力的重大进步。

LP 是否承认 强多项式 时间算法？

LP 是否承认强多项式时间算法来找到严格互补的解决方案？

LP 是否承认实数（单位成本）计算模型中的多项式时间算法？

这组密切相关的问题被 Stephen Smale 列为 21 世纪 18 个最大的未解决问题之一。 用斯梅尔的话说，该问题的第三个版本“是线性规划理论中未解决的主要问题”。 虽然存在求解弱多项式时间线性规划的算法，例如 椭球体方法 和 内点技术 ，但尚未发现能够在约束数量和变量数量方面实现强多项式时间性能的算法。 此类算法的开发将具有巨大的理论意义，并且也许还能在解决大型线性规划方面带来实际收益。

尽管 赫希猜想 最近在更高维度上被证明是错误的，但它仍然留下了以下问题。

是否存在导致多项式时间单纯形变体的主元规则？

所有多面图都具有多项式有界直径吗？

这些问题涉及性能分析和类似单纯形方法的开发。 尽管单纯形算法具有指数时间的理论性能，但其在实践中的巨大效率表明，可能存在以多项式甚至强多项式时间运行的单纯形变体。 了解是否存在任何此类变体将具有重大的实践和理论意义，特别是作为确定LP是否可以在强多项式时间内求解的方法。

单纯形算法及其变体属于边缘跟踪算法家族，之所以如此命名，是因为它们通过沿着多面体的边缘从一个顶点移动到另一个顶点来解决线性规划问题。 这意味着它们的理论性能受到 LP 多胞形上任意两个顶点之间的最大边数的限制。 因此，我们有兴趣了解多面 图 的最大 图论直径 。 已证明所有多胞形都具有次指数直径。 最近对赫希猜想的反驳是证明多面体是否具有超多项式直径的第一步。 如果存在任何这样的多面体，则任何边缘跟随变体都不能在多项式时间内运行。 关于多胞体直径的问题具有独立的数学意义。

单纯形枢轴方法保留了原始（或对偶）可行性。 另一方面，十字枢轴方法不保留（原始或对偶）可行性——它们可能以任何顺序访问原始可行、对偶可行或原始和对偶不可行基。 自 20 世纪 70 年代以来，人们就开始研究这种类型的枢轴方法。 [25] 本质上，这些方法试图在线性规划问题下找到排列多胞体上的最短主元路径。 与多面体图相比，已知排列多面体图具有较小的直径，这允许强多项式时间十字主元算法的可能性，而无需解决有关一般多面体直径的问题。 ^[11]

整数未知数 [ 编辑 ]

如果所有未知变量都要求为整数，则该问题称为 整数规划 （IP）或 整数线性规划 （ILP）问题。 与在最坏情况下可以有效解决的线性规划相比，整数规划问题在许多实际情况（具有有界变量的情况）中都是 NP 困难的 。 0-1 整数规划 或 二进制整数规划 (BIP) 是整数规划的特殊情况，其中变量需要为 0 或 1（而不是任意整数）。 这个问题也被归类为 NP 困难问题，事实上，决策版本是 卡普的 21 个 NP 完全问题 之一。

如果仅要求部分未知变量为整数，则该问题称为 混合整数（线性）规划 （MIP 或 MILP）问题。 这些通常也是 NP 难的，因为它们比 ILP 程序更通用。

然而，IP 和 MIP 问题的一些重要子类是可以有效解决的，最显着的是约束矩阵 完全幺模 并且约束的右侧是整数的问题，或者更一般地说，系统具有总 对偶完整性的问题 （TDI）属性。

求解整数线性规划的高级算法包括：

分支和剪切

分店及价格

如果问题有一些额外的结构，则可以应用 延迟列生成 。

Padberg 和 Beasley 讨论了此类整数规划算法。

积分线性规划 [ 编辑 ]

更多信息： 整体多面体

如果实变量的线性 规划具有 至少一个完整的最优解，即仅由整数值组成，则称该线性规划是完整的。 同样，多面体 磷 = { � ∣ � � ≥ 0 } 如果对于所有有界可行目标函数 c ，线性规划 被称为 积分 { 最大限度 � � ∣ � ε 磷 } 有一个最优的 � * 具有整数坐标。 正如 Edmonds 和 Giles 在 1977 年观察到的那样，我们可以等效地说，多面体 磷 如果对于每个有界可行积分目标函数c ，线性规划的 最优 值 是积分 { 最大限度 � � ∣ � ε 磷 } 是一个整数。

积分线性程序在组合优化 的多面体方面至关重要， 因为它们提供了问题的另一种表征。 具体来说，对于任何问题，解的凸包都是积分多面体； 如果这个多面体有一个很好/紧凑的描述，那么我们可以在任何线性目标下有效地找到最佳可行解。 相反，如果我们可以证明 线性规划松弛 是积分的，那么它就是可行（积分）解的凸包的所需描述。

整个文献中的术语并不一致，因此应小心区分以下两个概念，

在上一节中描述的整数线性程序 中 ，变量被强制约束为整数，并且这个问题通常是 NP 困难的，

在本节描述的 积分线性规划 中，变量不限于整数，而是已经以某种方式证明了连续问题总是具有积分最优值（假设 c 是整数），并且可以有效地找到该最优值，因为所有多项式大小的线性程序都可以在多项式时间内求解。

证明多面体是积分的一种常见方法是证明它是 完全幺模的 。 其他通用方法还有整数分解性质和 全对偶完整性 方法。 其他特定的众所周知的积分 LP 包括匹配多面体、晶格多面体、 子模流多面体以及两个广义多拟阵/ g- 多拟阵的交集 - 例如参见 Schrijver 2003。

求解器和脚本（编程）语言 [ 编辑 ]

许可 许可：

麻省理工学院许可证 用于解决大规模 LP、 QP 、 QCQP 、 NLP 和 MIP 优化 的开源库 阿帕奇v2 Google 的开源线性规划求解器 JuMP.jl MPL许可证 开源建模语言，带有用于大规模 LP、 QP 、 QCQP 、 SDP 、 SOCP 、 NLP 和 MIP 优化的 求解器 用于大规模线性、混合整数和非线性优化的开源建模语言 阿帕奇v2 一个通用约束整数规划求解器，重点是 MIP。 与 Zimpl 建模语言兼容。 阿帕奇v2 一套开源的优化算法，用于 在 Java 中 解决 LP、 QP 、 SOCP 、 SDP 、 SQP

Copyleft（互惠） 许可证：

ALGLIB 通用公共许可证 2+ 来自 ALGLIB 项目的 LP 求解器（C++、C#、Python） 食火鸡约束求解器 增量约束求解工具包，可有效求解线性等式和不等式系统 COIN-OR 的 LP 求解器 通用公共许可证 GNU 线性编程套件，一个 LP/MILP 求解器，具有本机 C API 和许多 (15) 个用于其他语言的第三方包装器。 流网络 的专家支持 。 捆绑 类似 AMPL的 GNU MathProg 建模语言和翻译器。 lp_solve LGPL v2.1 LP 和 MIP 求解器支持 MPS 格式 及其自己的“lp”格式，以及通过其“外部语言接口”(XLI) 的自定义格式。 ^{[26] [27]} 模型格式之间的转换也是可能的。 ^[28] 通用公共许可证 用于增量求解具有各种目标函数的线性方程组的库 通用公共许可证 用于统计计算和图形的编程语言和软件环境

MINTO （混合整数优化器，一种 使用分支定界算法的 整数规划求解器）具有公开可用的源代码 ^[29] ，但不是开源的。

专有 许可证：

人工智能管理系统 一种建模语言，允许对线性、混合整数和非线性优化模型进行建模。 它还提供了约束编程工具。 还可以实现启发式或精确方法形式的算法，例如分支和剪切或列生成。 该工具调用适当的求解器（例如 CPLEX 或类似的）来解决手头的优化问题。 学术许可证是免费的。 ALGLIB Copyleft 许可库的商业版本。 C++、C#、Python。 一种用于大规模线性、混合整数和非线性优化的流行建模语言，提供免费的学生限制版本（500 个变量和 500 个约束）。 通用建模语言和交互式开发环境。 其影响图使用户能够将问题表述为带有决策变量、目标和约束节点的图表。 Analytica Optimizer Edition 包括线性、混合整数和非线性求解器，并选择求解器来匹配问题。 它还接受其他引擎作为插件，包括 XPRESS 、 Gurobi 、 Artelys Kninto 和 MOSEK 。 AP监控器 MATLAB 和 Python 的 API。 通过 MATLAB、Python 或 Web 界面解决示例线性规划 (LP) 问题。 CPLEX 流行的求解器，具有适用于多种编程语言的 API，还具有建模语言，并可与 AIMMS、AMPL、 GAMS 、MPL、OpenOpt、OPL Development Studio 和 TOMLAB 配合使用。 免费供学术使用。 Excel 求解器函数 适应电子表格的非线性求解器，其中函数评估基于重新计算的单元格。 基本版本可作为 Excel 的标准插件使用。 古罗比优化器 IMSL 数值库 C/C++、Fortran、Java 和 C#/.NET 中提供的数学和统计算法集合。 IMSL 库中的优化例程包括无约束、线性和非线性约束最小化以及线性编程算法。 具有 API 的求解器，可用于大规模优化线性、整数、二次、二次曲线和一般非线性程序，并具有随机编程扩展。 它提供了一个全局优化过程，用于为具有连续和离散变量的一般非线性程序找到有保证的全局最优解。 它还具有统计采样 API，可将蒙特卡罗模拟集成到优化框架中。 它具有代数建模语言 ( LINGO ) 并允许在电子表格中建模 ( What'sBest )。 用于符号和数值计算的通用编程语言。 MATLAB 一种用于数值计算的通用且面向矩阵的编程语言。 MATLAB 中的线性规划 除了基本 MATLAB 产品外还需要 Optimization Toolbox ； 可用的例程包括 INTLINPROG 和 LINPROG 数学CAD 所见即所得的数学编辑器。 它具有解决线性和非线性优化问题的功能。 一种通用数学编程语言，包括符号和数值功能。 用于大规模优化的求解器，具有多种语言（C++、java、.net、Matlab 和 python）的 API。 NAG 数值库 由数值算法组 为多种编程语言（C、C++、Fortran、Visual Basic、Java 和 C#）和软件包（MATLAB、Excel、R、LabVIEW） 开发的数学和统计例程集合。 NAG 库的优化章节包括用于稀疏和非稀疏线性约束矩阵的线性规划问题的例程，以及用于优化具有非线性、有界或无约束的二次、非线性、线性或非线性函数的平方和的例程。 NAG 库具有用于局部和全局优化以及连续或整数问题的例程。 一种基于 Java 的优化建模语言，提供免费版本。 ^{[30] [31]} SAS /或 一套用于线性、整数、非线性、无导数、网络、组合和约束优化的求解器； 代数建模语言 OPTMODEL ； 以及针对特定问题/市场的各种垂直解决方案，所有这些都与 SAS 系统 完全集成。 适用于大规模线性规划、二次规划、一般非线性和混合整数规划的求解器。 拥有适用于多种编程语言的 API，还有建模语言 Mosel，并可与 AMPL、 GAMS 配合使用。 免费供学术使用。 可视化模拟 用于动态系统 仿真的 可视 化框图 语言。