使用 Python 进行线性规划

发布时间:2021-12-29 10:27:23 人气:354 作者:多测师

  解决线性规划问题的基本方法称为单纯形法,它有多种变体。另一种流行的方法是内点法。

  混合整数线性规划问题可以通过更复杂且计算量更大的方法来解决,例如分支定界法,它在幕后使用线性规划。这种方法的一些变体是分支和切割方法,它涉及使用切割平面,以及分支和价格方法。

  有几种适用于线性规划和混合整数线性规划的合适且众所周知的 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

使用 Python 进行线性规划

  不可行的线性规划问题

  如果没有解,线性规划问题是不可行的。当没有解决方案可以同时满足所有约束时,通常会发生这种情况。

  例如,考虑如果添加约束 x + y ≤ −1 会发生什么。那么至少有一个决策变量(x 或 y)必须是负数。这与给定的约束 x ≥ 0 和 y ≥ 0 相冲突。这样的系统没有可行的解决方案,因此称为不可行的。

  另一个示例是添加与绿线平行的第二个等式约束。这两行没有共同点,因此不会有满足这两个约束的解决方案。

  无界线性规划问题

  一个线性规划问题是无界的,如果它的可行区域是无界,将溶液不是有限。这意味着您的变量中至少有一个不受约束,可以达到正无穷大或负无穷大,从而使目标也无限大。

  例如,假设您采用上面的初始问题并删除红色和黄色约束。从问题中删除约束称为放松问题。在这种情况下,x 和 y 不会在正侧有界。您可以将它们增加到正无穷大,从而产生无限大的 z 值。

  资源分配问题

  在前面的部分中,您研究了一个与任何实际应用程序无关的抽象线性规划问题。在本小节中,您将找到与制造业资源分配相关的更具体和实用的优化问题。

  假设一家工厂生产四种不同的产品,第一种产品的日产量为 x ₁,第二种产品的产量为 x 2,依此类推。目标是确定每种产品的利润最大化日产量,同时牢记以下条件:

  第一种、第二种、第三种和第四种产品的每单位产品利润分别为 20 美元、12 美元、40 美元和 25 美元。

  由于人力限制,每天生产的总数量不能超过五十台。

  对于每单位第一个产品,消耗三个单位的原材料 A。每单位第二产品需要两单位原料 A 和一单位原料 B。每单位第三产品需要一单位 A 和两单位 B。最后,每单位第四产品需要三 B 的单位

  由于运输和储存的限制,工厂每天最多可以消耗一百单位的原材料 A 和九十单位的 B。

  以上内容为大家介绍了使用 Python 进行线性规划,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/

返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线