The Big-M method with the numerical infinite M
The Big-M method with the numerical infinite M
复制标题
数值无限 M 的 Big-M 方法
作者：
M. Cococcioni;Lorenzo Fiaschi
线性规划是最优化理论中一个非常著名和应用广泛的领域。它最著名和最常用的算法之一是所谓的单纯形算法，独立提出的Kantorović和Dantzig之间的30年代末和40年代末。即使单纯形算法非常强大，它也有一个初始化问题：它的起点必须是要解决的问题的可行基本解。为了克服这一问题，可以采用两种方法：两阶段方法和大M方法，这两种方法都有积极和消极的一面。在这项工作中，我们的目标是提出一个非阿基米德和非参数的大M方法的变体，能够克服其经典的对手的缺点（主要是，在设置正确的值为常数M的困难）。我们通过谢尔盖耶夫提出的新型计算方法（称为Grossone方法）实现了这种扩展。我们已经验证了新的算法，通过测试它对三个线性规划问题。
Linear programming is a very well known and deeply applied field of optimization theory. One of its most famous and used algorithms is the so called Simplex algorithm, independently proposed by Kantorovič and Dantzig, between the end of the 30s and the end of the 40s. Even if extremely powerful, the Simplex algorithm suffers of one initialization issue: its starting point must be a feasible basic solution of the problem to solve. To overcome it, two approaches may be used: the two-phases method and the Big-M method, both presenting positive and negative aspects. In this work we aim to propose a non-Archimedean and non-parametric variant of the Big-M method, able to overcome the drawbacks of its classical counterpart (mainly, the difficulty in setting the right value for the constant M). We realized such extension by means of the novel computational methodology proposed by Sergeyev, known as Grossone Methodology. We have validated the new algorithm by testing it on three linear programming problems.