万字教你如何⽤Python实现线性规划
线性规划说明
什么是线性规划？
想象⼀下，您有⼀个线性⽅程组和不等式系统。这样的系统通常有许多可能的解决⽅案。线性规划是⼀组数学和计算⼯具，可让您到该系统的特定解，该解对应于某些其他线性函数的最⼤值或最⼩值。能运行python的软件
什么是混合整数线性规划？
混合整数线性规划是 线性规划 的扩展。它处理⾄少⼀个变量采⽤离散整数⽽不是连续值的问题。尽管乍⼀看混合整数问题与连续变量问题相似，但它们在灵活性和精度⽅⾯具有显着优势。
整数变量对于正确表⽰⾃然⽤整数表⽰的数量很重要，例如⽣产的飞机数量或服务的客户数量。
⼀种特别重要的整数变量是 ⼆进制变量 。它只能取 零 或 ⼀ 的值，在做出是或否的决定时很有⽤，例如是否应该建造⼯⼚或者是否应该打开或关闭机器。您还可以使⽤它们来模拟逻辑约束。
为什么线性规划很重要？
线性规划是⼀种基本的优化技术，已在科学和数学密集型领域使⽤了数⼗年。它精确、相对快速，适⽤于⼀系列实际应⽤。
混合整数线性规划允许您克服线性规划的许多限制。您可以使⽤分段线性函数近似⾮线性函数、使⽤半连续变量、模型逻辑约束等。它是⼀种计算密集型⼯具，但计算机硬件和软件的进步使其每天都更加适⽤。
通常，当⼈们试图制定和解决优化问题时，第⼀个问题是他们是否可以应⽤线性规划或混合整数线性规划。
以下⽂章说明了线性规划和混合整数线性规划的⼀些⽤例：
Gurobi 优化案例研究
线性规划技术的五个应⽤领域
随着计算机能⼒的增强、算法的改进以及更多⽤户友好的软件解决⽅案的出现，线性规划，尤其是混合整数线性规划的重要性随着时间的推移⽽增加。
使⽤ Python 进⾏线性规划
解决线性规划问题的基本⽅法称为，它有多种变体。另⼀种流⾏的⽅法是。
混合整数线性规划问题可以通过更复杂且计算量更⼤的⽅法来解决，例如，它在幕后使⽤线性规划。这种⽅法的⼀些变体是，它涉及使
⽤ 切割平⾯ ，以及。
有⼏种适⽤于线性规划和混合整数线性规划的合适且众所周知的 Python ⼯具。其中⼀些是开源的，⽽另⼀些是专有的。您是否需要免费或付费⼯具取决于问题的规模和复杂性，以及对速度和灵活性的需求。
值得⼀提的是，⼏乎所有⼴泛使⽤的线性规划和混合整数线性规划库都是以 Fortran 或 C 或 C++ 原⽣和编写的。这是因为线性规划需要对（通常很⼤）矩阵进⾏计算密集型⼯作。此类库称为求解器。Python ⼯具只是求解器的包装器。
Python 适合围绕本机库构建包装器，因为它可以很好地与 C/C++ 配合使⽤。对于本教程，您不需要任何 C/C++（或 Fortran），但如果您想了解有关此酷功能的更多信息，请查看以下资源：
构建 Python C 扩展模块
CPython 内部
⽤ C 或 C++ 扩展 Python
基本上，当您定义和求解模型时，您使⽤ Python 函数或⽅法调⽤低级库，该库执⾏实际优化⼯作并将解决⽅案返回给您的 Python 对象。
⼏个免费的 Python 库专门⽤于与线性或混合整数线性规划求解器交互：
SciPy Optimization and Root Finding
PuLP
Pyomo
CVXOPT
在本教程中，您将使⽤SciPy和PuLP来定义和解决线性规划问题。
线性规划⽰例
在本节中，您将看到线性规划问题的两个⽰例：
1. ⼀个说明什么是线性规划的⼩问题
2. ⼀个与资源分配相关的实际问题，它说明了现实世界场景中的线性规划概念
您将在下⼀节中使⽤ Python 来解决这两个问题。
⼩型线性规划问题
考虑以下线性规划问题：
你需要到X和Ÿ使得红⾊，蓝⾊和黄⾊的不平等，以及不平等X ≥0和ÿ ≥0，是满意的。同时，您的解决⽅案必须对应于z的最⼤可能值。
您需要到的⾃变量（在本例中为 x 和 y ）称为 决策变量 。要最⼤化或最⼩化的决策变量的函数（在本例中为 z） 称为 ⽬标函数 、 成本函数 或仅称为 ⽬标 。您需要满⾜的 不等式 称为 不等式约束 。您还可以在称为 等式约束 的约束中使⽤⽅程。
这是您如何可视化问题的⽅法：
红线代表的功能2 X + Ý = 20，和它上⾯的红⾊区域⽰出了红⾊不等式不满⾜。同样，蓝线是函数−4 x + 5 y = 10，蓝⾊区域被禁⽌，因为它违反了蓝⾊不等式。黄线是 − x + 2 y = −2，其下⽅的黄⾊区域是黄⾊不等式⽆效的地⽅。
如果您忽略红⾊、蓝⾊和黄⾊区域，则仅保留灰⾊区域。灰⾊区域的每个点都满⾜所有约束，是问题的潜在解决⽅案。该区域称为 可⾏域 ，其点为 可⾏解 。在这种情况下，有⽆数可⾏的解决⽅案。
您想最⼤化z。对应于最⼤z的可⾏解是 最优解 。如果您尝试最⼩化⽬标函数，那么最佳解决⽅案将对应于其可⾏的最⼩值。
请注意，z是线性的。你可以把它想象成⼀个三维空间中的平⾯。这就是为什么最优解必须在可⾏区域的 顶点 或⾓上的原因。在这种情况下，最佳解决⽅案是红线和蓝线相交的点，稍后您将看到。
有时，可⾏区域的整个边缘，甚⾄整个区域，都可以对应相同的z值。在这种情况下，您有许多最佳解决⽅案。
您现在已准备好使⽤绿⾊显⽰的附加等式约束来扩展问题：
⽅程式 − x + 5 y = 15，以绿⾊书写，是新的。这是⼀个等式约束。您可以通过向上⼀张图像添加相应的绿线来将其可视化：
现在的解决⽅案必须满⾜绿⾊等式，因此可⾏区域不再是整个灰⾊区域。它是绿线从与蓝线的交点到与红线的交点穿过灰⾊区域的部分。后⼀点是解决⽅案。
如果插⼊x的所有值都必须是整数的要求，那么就会得到⼀个混合整数线性规划问题，可⾏解的集合⼜会发⽣变化：
您不再有绿线，只有沿线的x值为整数的点。可⾏解是灰⾊背景上的绿点，此时最优解离红线最近。
这三个例⼦说明了 可⾏的线性规划问题 ，因为它们具有有界可⾏区域和有限解。
不可⾏的线性规划问题
如果没有解，线性规划问题是 不可⾏的 。当没有解决⽅案可以同时满⾜所有约束时，通常会发⽣这种情况。
例如，考虑如果添加约束x + y ≤ −1会发⽣什么。那么⾄少有⼀个决策变量（x或y）必须是负数。这与给定的约束x ≥ 0 和y ≥ 0相冲突。这样的系统没有可⾏的解决⽅案，因此称为不可⾏的。
另⼀个⽰例是添加与绿线平⾏的第⼆个等式约束。这两⾏没有共同点，因此不会有满⾜这两个约束的解决⽅案。
⽆界线性规划问题
⼀个线性规划问题是 ⽆界的 ，如果它的可⾏区域是⽆界，将溶液不是有限。这意味着您的变量中⾄少有⼀个不受约束，可以达到正⽆穷⼤或负⽆穷⼤，从⽽使⽬标也⽆限⼤。
例如，假设您采⽤上⾯的初始问题并删除红⾊和黄⾊约束。从问题中删除约束称为 放松 问题。在这种情况下，x和y不会在正侧有界。您可以将它们增加到正⽆穷⼤，从⽽产⽣⽆限⼤的z值。
资源分配问题
在前⾯的部分中，您研究了⼀个与任何实际应⽤程序⽆关的抽象线性规划问题。在本⼩节中，您将到与制造业资源分配相关的更具体和实⽤的优化问题。
假设⼀家⼯⼚⽣产四种不同的产品，第⼀种产品的⽇产量为x ₁，第⼆种产品的产量为x 2，依此类推。⽬标是确定每种产品的利润最⼤化⽇产量，同时牢记以下条件：
1. 第⼀种、第⼆种、第三种和第四种产品的每单位产品利润分别为 20 美元、12 美元、40 美元和 25 美元。
2. 由于⼈⼒限制，每天⽣产的总数量不能超过五⼗台。
3. 对于每单位第⼀个产品，消耗三个单位的原材料 A。每单位第⼆产品需要两单位原料 A 和⼀单位原料 B。每单位第三产品需要⼀单位
A 和两单位 B。最后，每单位第四产品需要三
B 的单位
4. 由于运输和储存的限制，⼯⼚每天最多可以消耗⼀百单位的原材料 A 和九⼗单位的 B。
数学模型可以这样定义：
⽬标函数（利润）在条件 1 中定义。⼈⼒约束遵循条件 2。对原材料 A 和 B 的约束可以从条件 3 和条件 4 中通过对每种产品的原材料需求求和得出。
最后，产品数量不能为负，因此所有决策变量必须⼤于或等于零。
与前⾯的⽰例不同，您⽆法⽅便地将其可视化，因为它有四个决策变量。但是，⽆论问题的维度如何，原理都是相同的。
线性规划 Python 实现
在本教程中，您将使⽤两个Python 包来解决上述线性规划问题：
1. SciPy 是⼀个⽤于使⽤ Python 进⾏科学计算的通⽤包。
2. PuLP 是⼀个 Python 线性编程 API，⽤于定义问题和调⽤外部求解器。
SciPy 设置起来很简单。安装后，您将拥有开始所需的⼀切。它的⼦包 scipy.optimize 可⽤于线性和⾮线性优化。
PuLP 允许您选择求解器并以更⾃然的⽅式表述问题。PuLP 使⽤的默认求解器是COIN-OR Branch and Cut Solver (CBC)。它连接到⽤于线性松弛的COIN-OR 线性规划求解器 (CLP)和⽤于切割⽣成的COIN-OR 切割⽣成器库 (CGL)。
另⼀个伟⼤的开源求解器是GNU 线性规划⼯具包 (GLPK)。⼀些著名且⾮常强⼤的商业和专有解决⽅案是Gurobi、CPLEX和XPRESS。
除了在定义问题时提供灵活性和运⾏各种求解器的能⼒外，PuLP 使⽤起来不如 Pyomo 或 CVXOPT 等替代⽅案复杂，后者需要更多的时间和精⼒来掌握。
安装 SciPy 和 PuLP