本文介绍了如何在Python语言中快速得到线性规划的可行解？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

目标：计算两个凸多面体的交集。

我使用scipy.spatial.HalfspaceIntersection来执行此操作。下图显示了生成的交叉点：

我的问题：确定初始可行点。

您看，scipy.spatial.HalfspaceIntersection的当前Python实现需要将interior_point作为参数传递。

interior_point : ndarray of floats, shape (ndim,)
在由半空格定义的区域内清晰地指向。也称为可行点，可以通过线性规划获得。

现在，我正在手动提供可行点，因为我只是在起草一个原型来试验HalfspaceIntersection。 但现在我不想手动指定它。

SciPy的优化模块scipy.optimize.linprog实现了两个通用的线性规划(LP)求解器：单纯形和内点。但它们似乎需要一个成本函数。[1]

由于我希望花费尽可能少的处理时间来计算此可行点，我想知道如何才能在没有成本函数的情况下运行这些LP方法中的任何一个，即只运行到解决方案已达到可行状态。

问题：

1. scipy.optimize.linprog计算此可行内点是否正确？

2. 如果是，如果没有成本函数，我如何使用单纯形或内点？

3. 为什么scipy.spatial.HalfspaceIntersection首先要求将aninterior point作为参数传递？据我所知，半空间的交集就是去掉一组给定的不平等的多余的不等。为什么这需要一个可行点？

推荐答案

您可以指定不变成本函数，例如0。

举个例子：

%pylab
from scipy.optimize import linprog
A = array([[1] + 9 * [0], 9 * [0] + [1]])
b = array([1, 1])

测量此方法的性能表明它非常高效：

%time
res = linprog(c=zeros(A.shape[1]), A_eq=A, b_eq=b)

输出：

CPU times: user 5 µs, sys: 1 µs, total: 6 µs
Wall time: 11 µs

而且，根据res.nit，我们只用了2次迭代就完成了。

结果res.x正确：

array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.])

请注意，单纯形算法旨在找到由线性约束定义的多面体的顶点。据我所知，基于内点的方法没有这样的偏好，尽管我不熟悉Scipylinprog背后的实现。因此，由于您的要求是点是"明显位于由半空格定义的区域内"，因此我建议使用以下方法之一：

• 任一，将method='interior-point'传递给linprog。
• 或计算不同的顶点，并利用多面体是凸的：
  1. 向常量目标函数添加一些噪声(例如，通过np.random.randn)
  2. 通过改变噪声种子(np.random.seed)解决噪声增强LP的多个实例。
  3. 最后，使用解的平均值作为最终内点"清楚地位于区域内"。

由于不清楚内点的边距需要有多大，我预计第二种方法(噪声增强LP)更可靠。

这篇关于如何在Python语言中快速得到线性规划的可行解？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持吉威生活！

[英文标题]How to quickly get a feasible solution to a linear program in Python?

声明：本媒体部分图片、文章来源于网络，版权归原作者所有，如有侵权，请联系QQ:330946442删除。