О матричной коррекции двойственной пары несобственных задач линейного программирования по минимуму взвешенной евклидовой матричной нормы
Аннотация
В статье рассматривается матричная коррекция двойственной пары несобственных задач линейного программирования с минимальной взвешенной евклидовой нормой. Взвешивание обеспечивается путем умножения расширенной матрицы коррекции слева и справа на невырожденные матрицы. Основной целью взвешивания является включение в задачу линейного программирования сведений о трудоемкости коррекции расширенной матрицы системы ограничений. Под матричной коррекцией в данной статье подразумевается изменение (коррекция) любых коэффициентов системы ограничений с целью обеспечения ее совместности. Указанная проблема сведена к вспомогательной задаче безусловной дифференцируемой минимизации. Обоснованием этого перехода является представленная в статье теорема об оптимальной по минимуму взвешенной евклидовой нормы коррекции двойственной пары несобственных задач линейного программирования. Данная теорема является следствием теоремы о существовании решения задачи коррекции расширенной матрицы ограничений двойственной пары несобственных задач линейного программирования по минимуму взвешенной евклидовой нормы. В свою очередь, последняя теорема базируется на теореме о матричном решении обратной задачи линейного программирования. Формулировки последних теорем также приводятся в статье. В качестве возможного инструмента численного решения данной задачи рассмотрен квазиньютоновский алгоритм Бройдена-Флетчера-Голдфарба-Шанно. Рассматривается задача поиска расширенной матрицы коррекции, минимальной по взвешенной евклидовой норме. Данная задача определяется следующими параметрами: расширенной матрицей системы ограничений, невырожденными весовыми матрицами и начальным приближением. Решение представлено аргументом целевой функции и ее значением. Приведены результаты вычислительных экспериментов по исследованию сходимости предложенного алгоритма по целевой функции и по аргументу.
Скачивания
Литература
2. Khachay, M. Yu. On Approximate Algorithms of a Minimal Committee of a Linear Inequalities System // Pattern Recognition and Zimage Analysis. – 2003. – vol. 13, no. 3., pp. 459-464.
3. Еремин, И. И. Несобственные задачи математического программирования / И. И. Еремин, А. А. Ватолин // Проблемы управления и теории информатизации. – 1989. – Т. 18, No6. – С. 1–23.
4. Ерохин, В. И. Согласование материального баланса крупного нефтеперерабатывающего завода в условиях неполных данных / В. И. Ерохин, А. Ю. Лаптев, Н. В. Лисицын // Известия Российской академии наук. Теория и системы управления. – 2010. –№ 2. – С. 130–140.
5. Скарин, В. Д. О некоторых универсальных методах коррекции несобственных задач выпуклого программирования // Автоматика и телемеханика. – 2012. – № 2. – С. 99–110.
6. Горелик, В. А. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса / В. А. Горелик, В. И. Ерохин // Моделирование, оптимизация и декомпозиция сложных динамических процессов. – М. : ВЦ РАН, 2001. – С. 51–56.
7. Горелик, В. А. Оптимальная (по минимуму полиэдральной нормы) матричная коррекция несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования / В. А. Горелик, В. И. Ерохин // Моделирование, декомпозиция и оптимизация сложных динамических процессов. – М : ВЦ РАН, 2004. – С. 35–63.
8. Горелик, В. А. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы / В. А. Горелик, В. И. Еро-хин. – М. : ВЦ РАН, 2004. – 193 с.
9. Ерохин, В. И. Минимальные по евклидовой норме матричные коррекции задач линейного программирования / В. И. Ерохин, А. С. Красников, М. Н. Хвостов // Автоматика и телемеханика. – 2012. – № 2. – С. 11–24.
10. Попов, Л. Д. Лексикографическая регуляризация и двойственность для несобственных задач линейного программирования / Л. Д. Попов, В. Д. Скарин // Труды института математики и механики УрО РАН. – 2015. – Т. 21, № 3. – С. 279–291.
11. Ерохин, В. И. Матричная коррекция несобственных задач линейного программирования по минимуму евклидовой нормы с произвольными весами и фиксированными элементами // Математическое программирование: Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал 2–8 июля 2005 года. Том I. – Иркутск: ИСЭМ СО РАН, 2005. – С. 105–110.
12. Хвостов, М. Н. О достаточных условиях разрешимости несобственных задач ЛП 1-го рода после матричной коррекции их допустимой области по минимуму взвешенной евклидовой нормы с учетом структурных ограничений // Вестник Воронежского государственного университета. Серия: Физика. Математика. – 2015. – №2. – С. 150–167.
13. Еремин, И. И. Двойственность для несобственных задач математического программирования / И. И. Еремин, А. А. Ватолин. – Свердловск : ИММ УрО РАН, 1985. – 50 с.
14. Ерохин, В. И. Матричная коррекция двойственной пары несобственных задач линейного программирования // Журнал вычислительной математики и математической физики. – 2007. – Т.47, № 4. – С. 587– 601.
15. Ерохин, В. И. Матричная коррекция двойственной пары несобственных задач линейного программирования с блочной структурой / В. И. Ерохин, А. С. Красников // Журнал вычислительной математики и математической физики. – 2008. – Т. 48, № 1. – С. 80–89.
16. Волков, В. В. Минимальная по евклидовой норме матричная коррекция пары двойственных задач линейного программирования / В. В. Волков, В. И. Ерохин, А. С. Красников, А. В. Разумов, М. Н. Хвостов // Журнал вычислительной математики и математической физики. – 2017. – Т. 57, № 11. – С. 1788–1803.
17. Еремин, И. И. Двойственность для несобственных задач линейного программирования // Математические заметки. – 1982, – Т. 32, № 2, – С. 229–238.
18. Erokhin, V. I. Matrix correction minimal with respect to the Euclidean norm of a pair of dual linear programming problems / V. I. Erokhin, A. S. Krasnikov, V. V. Volkov, M. N. Khvostov // CEUR Workshop Proceedings 9th. – 2016. – С. 196–209.
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
