线性规划：定义、方法和问题

引言

线性规划（LP）是一种数值优化程序，旨在在满足一系列线性等式和不等式约束的条件下，最大化或最小化一个线性目标函数。LP 诞生于 20 世纪，已成为运营研究、经济学、金融学和工程学等各个领域不可或缺的工具。

其核心在于，LP 涉及在资源有限的情况下做出最优决策。“线性”一词指的是目标函数和约束条件的线性，这意味着决策变量之间的关系是成比例的和可加的。目标函数代表要最大化或最小化的数量，例如利润或成本，而约束条件则定义了决策变量必须在其范围内运行的限制。

LP 问题的图形表示通常包括创建一个可行域，所有约束条件的交集，最优解位于该区域内的极端点。然而，随着问题的复杂性增加，会使用更高级的算法，例如单纯形法或内点法，以实现高效和准确的解决方案。

线性规划具有广泛的应用，从生产计划和资源分配到投资组合优化和供应链管理。其灵活性以及解决现实世界挑战的能力使其成为优化和决策领域的基石。

线性规划的定义

一种名为线性规划（LP）的数值优化技术，在运营研究、管理、经济学和工程学等多个学科中使用，以协助决策。线性规划的基本目标是在考虑一系列线性约束的同时，最大化或最小化一个线性目标函数。在此上下文中，“线性”和“可加”这两个词描述了相互作用。

以下是线性规划问题的一般形式的表达式

最大化或最小化：c₁x₁ + c₂x₂ + ... + cnxn

受限于

线性规划的基本组成部分

• 决策变量（X）

理论：决策者希望确定的数量所代表的基本对象称为决策变量。它们是优化过程的基础，是决策者可以影响的因素。

重要性：通过概括决策问题的核心，决策变量使得能够构建模拟决策过程的数学关系。

• 目标函数（Z）

理论：决策者的目标由一个称为目标函数的数学表达式量化。它规定了优化过程中必须最小化或最大化的标准。

重要性：目标函数通过提供一个定量和可衡量的目标，指导优化过程朝着与决策者目标一致的特定结果。

• 局限性

理论：用于制定决策的变量受到约束的限制或约束。它们在定义可行区域和确保解决方案满足现实、实际要求方面发挥着至关重要的作用。

重要性：约束有助于对资源、环境或其他变量施加的限制或约束进行建模。它们将潜在解决方案的范围缩小到可行的解决方案。

• 非负约束

理论：非负约束阻止决策变量取负值。这与行动、资源或数量永远不会为负的实际观点一致。

重要性：通过将参数限制为非负数，模型避免了不切实际或不可行的解决方案，并使其根植于现实世界。

线性规划的类型

• 经典线性规划

普通线性规划的目标是在考虑线性约束的同时优化线性函数。

用例：适用于广泛行业的资源分配、生产调度和优化问题。

• 整数线性规划（ILP）

线性规划的一个变种，其中决策变量只能取整数值。

用例：通常用于离散优化问题，如网络设计和项目调度，当决策变量必须是整数时，此技术很有用。

• 二元线性规划

整数线性规划的一个变种，其中决策变量只能取二元值（0 或 1）。

用例：通常用于二元决策问题，包括二元优化挑战、网络设计、物流以及是/否或开/关场景。

• 混合整数线性规划（MILP）

这个线性规划范式结合了连续和整数决策变量。

用例：在需要某些决策变量取整数值而允许其他变量取连续值的情况下非常实用。

• 多目标线性规划

涉及同时优化多个线性目标函数，每个目标函数代表一个不同的目标或一套要求。

用例：在决策者必须权衡相互竞争的目标之间的权衡时很有用。

• 动态线性规划

考虑随时间的变化，并将线性代码扩展到动态和依赖于时间的环境。

用例：通常用于项目管理、库存和生产控制以及对时间敏感的资源分配。

线性规划的应用

• 生产计划

当在考虑资源限制的情况下，确定要生产的最佳产品组合以最大化利润或最小化成本时，线性规划通常用于优化生产流程。

• 供应链管理和物流

为了降低运输成本、降低存储成本并提高整体供应链效率，它有助于优化分销网络、库存管理和运输路线。

• 金融和优化投资组合

LP 用于在满足资产分配指南、预算限制和风险容忍度等限制的同时，优化投资组合回报。

• 营销和广告活动

它有助于通过在多个渠道分配资源来最大化覆盖范围、影响或消费者参与度，从而优化营销和广告支出。

• 农业资源配置

为了最大化农业产量或利润，农民可以利用线性规划来优化劳动、土地和肥料等资源的配置。

• 项目时间表

为了节省时间和成本，同时实现项目截止日期和限制，LP 协助项目经理有效安排任务和分配资源。

线性规划问题类型

• 线性最大化问题

目标是在考虑一系列线性约束的同时，优化一个线性目标函数。

示例：在资源受限的情况下，找出最佳生产组合以最大化利润。

• 线性最小化问题

目标是满足一系列线性约束并最小化一个线性目标函数。

示例：在具有容量限制的交通系统网络内最小化成本。

• 标准形式线性规划问题

目标是将线性规划问题表示为标准形式，其中决策变量非负且所有约束都是不等式。

示例：混合不等式约束问题的标准形式解。

• 规范形式线性规划问题

与标准形式类似，但所有约束都表示为方程。举一个约束条件为等式的方程问题。

• 可行性问题

确定在指定参数内是否可以找到可行解决方案。

示例：确定线性方程组的解是否满足所有条件。

• 无界线性规划问题

目标函数可以不断改进，可行域是无限的。

制造问题中由于资源过剩而导致的无限利润潜力是一个例子。

用于解决线性规划的方法

• 图解法

这使得它适用于有两个决策变量的情况。最优解位于约束条件的交点上，并且可行区域以图形方式显示。

适用性：仅限于变量和约束较少的问题。

• 单纯形法

这种广泛使用的方法解决了涉及任意数量变量的线性规划问题。直到找到最优解，它才会从一个可行区域顶点重复移动到另一个顶点。

适用性：适用于具有合理数量约束和变量的中等规模问题。

• 对偶单纯形法

单纯形法的一个变种，在解决无界或不现实的线性规划问题方面非常有用。

适用性：当传统单纯形法出现问题时很有用。

• 内点法

这些方法不通过顶点进行导航，而是穿过最小可行区域的中心。对于大规模线性规划问题，它们非常有效。

适用性：非常适合变量和约束非常多的问题。

• 对偶单纯形法

单纯形法的一个变种，在解决无界或不现实的线性规划问题方面非常有用。

适用性：当传统单纯形法出现问题时很有用。

• 内点法

这些方法不通过顶点进行导航，而是穿过最小可行区域的中心。对于大规模线性规划问题，它们非常有效。

适用性：非常适合变量和约束非常多的问题。

• 分支定界法

一种算法方法，它通过逐步将可行区域分解为更小的子问题，并剔除无法容纳最优解的较小问题。

应用：常用于解决混合整数线性规划（MILP）问题。

• 遗传算法

自然选择是这些优化策略的灵感来源。它们处理一个潜在解决方案的种群，该种群在连续的几代中得到改进。

应用：在解决复杂和非线性优化问题方面特别有用。

• 梯度下降

这是一种迭代优化程序，它根据目标函数的斜率确定最陡峭的上升或下降方向。

应用：凸问题非常适合，尤其是在优化和机器学习中。

• Karmarkar 公式

一种基于多项式时间方法的线性规划内点法。

应用：适合复杂的线性规划问题。