Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/43726
Title: Качество ограничений геометрических объектов и разрыв двойственности в полубесконечном линейном программировании
Other Titles: The quality of geometric objects constraints and the duality gap in semi-infinite linear programming
Authors: Trofimov, S. P.
Ivanov, A. V.
Трофимов, С. П.
Иванов, А. В.
Issue Date: 2016
Publisher: Издательство УМЦ УПИ
Citation: Трофимов С. П. Качество ограничений геометрических объектов и разрыв двойственности в полубесконечном линейном программировании / С. П. Трофимов, А. В. Иванов // Компьютерный анализ изображений: Интеллектуальные решения в промышленных сетях (CAI-2016) : сборник научных трудов по материалам I Международной конференции 5-6 мая 2016 г./ Под общ. ред. А. Г. Тягунова. — Екатеринбург: Изд-во УМЦ УПИ, 2016. — С. 92-97.
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 для численного анализа качества ограничений геометрических объектов. Выдвигается гипотеза об отрицательном влиянии разрыва двойственности задачи ПбЛП на качество ограничений геометрических объектов.
Keywords: LINEAR PROGRAMMING PROBLEM
DUALITY GAP
FEASIBLE SET
CONICAL HULL OF COEFFICIENTS
SYSTEM OF LINEAR INEQUALITIES
DUALITY RELATION CRITERIA
CONVEX UNCLOSED CONE
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
РАЗРЫВ ДВОЙСТВЕННОСТИ
МНОЖЕСТВО ДОПУСТИМЫХ РЕШЕНИЙ
КОНИЧЕСКАЯ ОБОЛОЧКА КОЭФФИЦИЕНТОВ
СИСТЕМА ЛИНЕЙНЫХ НЕРАВЕНСТВ
КРИТЕРИЙ СООТНОШЕНИЯ ДВОЙСТВЕННОСТИ
ВЫПУКЛЫЙ НЕЗАМКНУТЫЙ КОНУС
URI: http://hdl.handle.net/10995/43726
Conference name: I Международная конференция «Компьютерный анализ изображений: Интеллектуальные решения в промышленных сетях (CAI-2016)»
Conference date: 05.05.2016-06.05.2016
RSCI ID: https://elibrary.ru/item.asp?id=28344575
ISBN: 978-5-8295-0480-9
Origin: Компьютерный анализ изображений: Интеллектуальные решения в промышленных сетях (CAI-2016). — Екатеринбург, 2016.
Appears in Collections:Конференции, семинары

Files in This Item:
File Description SizeFormat 
cai-2016-19.pdf1,18 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.