Качество ограничений геометрических объектов и разрыв двойственности в полубесконечном линейном программировании

Abstract

The paper considers the model of geometric object constraints defined by feasible set of semi-infinite linear programming problem (SILP). Quality geometric method for analyzing SILP duality relations based on the use of the conical hull of the system constraints coefficients is proposed. A relation between presence of the duality gap and nonclosure of the conical hull boundary of points in a multidimensional space is established. An SILP example with three variables illustrates that problems with the duality gap are not exotic. The possibility of applying the system MATLAB for numerical quality analysis of geometrical objects constraints is under discussion. We put forward a hypothesis that the duality gap of SILP adversely affects on the quality of geometric objects constraints.

Рассматривается модель ограничений геометрического объекта, задаваемая допустимым множеством полубесконечной задачи линейного программирования (ПбЛП). Предлагается качественный геометрический способ анализа соотношений двойственности ПбЛП, основанный на использовании конической оболочки коэффициентов системы ограничений. Устанавливается связь наличия разрыва двойственности с незамкнутостью границы конической оболочки точек в многомерном пространстве. На примере ПбЛП с тремя переменными показывается, что задачи с разрывом двойственности не являются экзотическими. Обсуждается возможность применения системы MATLAB для численного анализа качества ограничений геометрических объектов. Выдвигается гипотеза об отрицательном влиянии разрыва двойственности задачи ПбЛП на качество ограничений геометрических объектов.