Том 6, серия 2, номер 1, 1999 г., Стр. 61-77
УДК 519.865.3
В. И. Шмырёв, Ю. А. Воленко
Венгерский метод для отыскания равновесия в линейной модели обмена с фиксированными бюджетами
Аннотация:
Известно, что задача отыскания равновесия в линейной модели с фиксированными бюджетами сводится к некоторой задаче математического программирования с линейными ограничениями. Однако эффективных конечных алгоритмов для решения задач возникающего класса предложено не было. Принципиально иной подход к проблеме, основанный на идеях полиэдральной комплементарности, был развит в работах одного из авторов. Этот подход позволил не только прояснить некоторые качественные аспекты проблемы, но и разработать достаточно простые и эффективные алгоритмы симплексного типа, обеспечивающие нахождение равновесия за конечное число шагов. Предлагаемый в настоящей работе алгоритм является дальнейшим продвижением в этом направлении, показывая применимость идей венгерского метода решения транспортных задач. Это выявляет более тесную связь с конструкциями линейного программирования. Использование алгоритма Форда–Фалкерсона для задачи о максимальном потоке позволяет избавиться от характерного для симплексных процедур предположения о невырожденности.
Библиогр. 8.
Шмырёв В. И. 1
Воленко Ю. А. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 12 октября 1998 г.
