线性规划概念、公式和解决方法介绍

线性规划是一种数学技术,它用于在一个目标函数和约束都以线性关系表示的模型中确定最优结果--例如利润最大化或成本最小化。

线性规划中的"规划"一词源于军事术语,指的是规划时间表的过程,如协调供应线或有效部署部队。

关键概念

决策变量

决策变量是 优化 问题,表示可以调整的数量,以找到最大化或最小化目标函数同时满足约束的最优解。

目的功能

目标函数是一个数学表达式,它定义了优化问题的目标.在线性规划中,目标函数总是决策变量的线性组合.

限制因素

约束是解决优化问题必须满足的要求.它们被表示为线性不等式或涉及决策变量的方程。制约因素可能来自各种来源,如可用资源、预算限制、时间限制或有形法律。在线性规划问题中,约束可分类如下:

· 不平等制约因素 :这些规则规定一定的关系必须保持,例如AX为系数矩阵,X为决策变量向量,B为常量向量。

· 平等制约因素 :这些要求特定的关系必须准确,以AX=B表示。

可行区域

可行区域是满足约束的所有可能点(或向量)的集合。在几何上,在由决策变量定义的空间中,该区域通常被表示为凸多边形(或更高尺寸的多面体)。

线性规划的基本定理

"线性规划(LP)的基本定理指出,每一个有边界的可行线性程序在可行多面体的零维面(顶点)上都有一个最优解"[1]。这意味着目标函数的最大值或最小值总是发生在可行区域的顶点。此外,这意味着在下列情况下,LP优化问题可能缺乏最佳解决方案[2]:

· 没有可行的区域 :如果不平等约束不兼容,图中没有一个区域能满足所有约束。

· 可行的区域是无限的 当区域无限扩展时,线性程序可能没有有限的最优解。

语言语言问题的数学公式

二元问题

线性规划中的二元性定理指出,任何最小化问题都可以转化为等价最大化问题,即所谓的对偶问题,反之亦然。在原始问题中,只有当目标函数在其双重问题中的最大值也得到时,才能实现目标函数的最小值。原始问题和双重问题之间的这种关系是理解LP二元性理论的关键,它为优化问题提供了更深入的见解。

解决双重问题通常是有利的,特别是当原始问题与决策变量相比有更大数量的约束时。这是因为解决线性规划问题的计算复杂性通常随着约束的数量而增加的更快,而不是变量的数量。在这种情况下,具有较少约束和较多变量的双重问题可以得到更有效的解决。

解决线性规划问题

LP问题可以根据问题的复杂性和维数,用各种方法解决。这些方法从简单的图形化方法到先进的计算算法不等。

图形方法

如前一个例子所示,图形化方法是解决线性规划问题的最简单的方法之一,但仅限于两个变量的情况。有关步骤如下:

· 限制因素和可行性区域图 不平等被描绘成直线,确定了满足所有限制的可行区域。

· 目的函数优化 :通过评价其在可行区域顶点的值,使目标函数最大化或最小化。

简单方法

单纯形法是一种迭代算法,它从可行区域的顶点之一开始,移动到邻近的顶点,相对于当前顶点,它对目标函数的改进最大。该算法继续这个过程,直到它达到最优解,当它到达一个顶点时,所有邻近的顶点要么产生更差的目标值,或者是在可行区域之外。

椭圆法

椭圆法是一种用于求解线性规划问题的中间点算法。与单纯形法不同的是,它是在可行区域的顶点上工作的,椭圆形法与可行区域的内部工作。它以一个初始的椭圆体开始,它封装了整个可行区域,并在每个步骤上改进了这个椭圆体。通过迭代线性不等式约束,该方法逐步减小了椭圆体的体积,使其更接近最优解。

在理论性能方面,保证了椭圆法在多项式时间中的运行,而单纯形法在最坏情况下可以显示指数时间复杂性。这使得椭圆形法在理论上成为大规模问题的一个吸引人的选择,尽管实际使用受到收敛速度较慢的限制,例如中间点法。

内部点方法

点法从可行区域内求出最优解,而不是像单纯形法那样沿边缘移动。它们对大规模问题更有效。这些方法通过跟踪可行区域内部的轨迹来解决LP问题,目的是直接达到最优点。相比之下,单纯形法的轨迹沿边界运动,而椭圆法则从外部包围可行区域。对大规模优化问题来说,点间方法特别有效,因为它们比单纯形方法表现出更好的性能,特别是在处理非常高尺寸的问题时。

应用lp问题

最优运输

统计学和机器学习的一个基本挑战是制定有效的概率分布对之间"距离"的衡量标准。有效的距离函数应满足对称和三角不等式等关键属性.然而,用于比较概率分布的许多常用措施不符合这些标准,因此被归为差异(如KL发散)[4]。

最优运输提供了一个健壮的距离之间的概率分布.最优运输背后的直觉是想象用一堆泥土以最低的成本填补同样体积的一个洞。换言之,它寻求最有效的方法,将质量从一个概率分布X转移到另一个分布Y,同时最小化运输成本。

这可以被理解为一个lp问题:

网络流问题

网络流问题是通过网络优化资源流动所不可或缺的,在网络中,资源可能代表货物、数据或其他商品。这些问题通常涉及一个有向图,其中每个边缘都有一个指定的容量和成本。目标是优化从源节点到接收节点的资源流,但要受边缘和节点的约束。网络流问题的主要类型包括最大流问题、最小成本流问题等。

解决线性规划问题的库

(谷歌) :谷歌开发的一个支持LP和其他约束编程的开源软件套件。它具有高度的可伸缩性,并与多个编程环境集成。

(python最佳运输) :专门为解决问题而设计的python库 最佳运输问题 .它支持包括基于lp的方法在内的多解决器,并广泛应用于机器学习、统计和数据科学等任务,如领域适应、集群和生成建模。

结论

线性规划仍然是优化的基石,为解决物流、金融和AI等领域的各种问题提供了工具。实践者通过掌握LP概念和方法,可以有效地解决理论和现实世界的挑战。