Эвристический алгоритм определения главных граней при решении задачи линейного программирования

Abstract

Рассмотрен алгоритм определения внутреннего многогранника из множества вложенных выпуклых многогранников, заданных системой линейных неравенств. Такой алгоритм может эффективно использоваться при решении задачи линейного программирования методом главных граней, являющего реальной альтернативой симплекс-методу. Приведен пример применения алгоритма, показана его вычислительная эффективность.

The algorithm of determination of internal polyhedron is considered from the great number of the inlaid protuberant polyhedrons, linear inequalities set the system. Such algorithm can be effectively used for the decision of task of the linear programming of main verges a method, showing the real alternative to the simplex-method. The example of application of algorithm is resulted, its calculable efficiency is rotined.