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

Аннотация

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