Том 6, серия 2, номер 1, 1999 г., Стр. 43-60

УДК 519.865.3
В. И. Шмырёв
Новый вариант венгерского метода для отыскания равновесия в линейной модели обмена

Аннотация:
Проблема численного отыскания состояния равновесия в линейной модели обмена в принципе решается методом, сводящим дело к некоторой задаче линейной дополнительности. Однако при этом слабо учитывается специфика исходной модели и возникающая задача линейной дополнительности имеет сравнительно большую размерность – порядка произведения числа участников на число продуктов модели. Более экономные процедуры нахождения равновесного состояния в линейной модели обмена были получены на основе применения идей полиэдральной комплемент арности. Учитывая тот факт, что в этих рассмотрениях в качестве вспомогательной задачи фигурирует классическая транспортная задача линейного программирования, для модели с фиксированными бюджетами был предложен метод, использующий идеи венгерского алгоритма решения транспортных задач. При этом в доказательстве конечности процесса существенно использовался факт потенциальности рассматриваемых кусочно-постоянных отображений. В данной работе излагается новый вариант такого алгоритма, который характеризуется монотонным возрастанием вспомогательной функции, задающей текущее значение величины максимального потока, как это имеет место в обычном венгерском методе для транспортных задач.
Библиогр. 9. 

Шмырёв В. И. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 19 мая 1998 г.