ТРЕХ- И ЧЕТЫРЕХИНДЕКСНЫЕ ЗАДАЧИ С ВЛОЖЕННОЙ СТРУКТУРОЙ |
| 3 | |
| 2012 |
| научная статья | 519.852 | ||
| 163-169 | линейное программирование, многоиндексные задачи, задачи транспортного типа, сводимость, потоковые алгоритмы |
| Рассматриваются многоиндексные задачи линейного программирования транспортного типа. Один из подходов к решению таких задач - сведение их к задаче поиска потока в сети. Описана концепция такого сведения, в основу которой положено соответствие между переменными исходной задачи и дугами вспомогательной сети. Ранее было показано, что условие 2-вложенности многоиндексных задач является достаточным условием сводимости. В работе доказано, что (в рамках рассматриваемой концепции сводимости) условие 2-вложенности является необходимым и достаточным условием сводимости в трех- и четырехиндексном случае. |
 |
| 1 . Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. 2006. №. 6. С. 194-205. 2 . Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального планирования производства // Автоматика и телемеханика. 2010. № 10. C. 148-155. 3 . Прилуцкий М.Х., Костюков В.Е. Оптимизационные задачи объёмно-календарного планирования для нефтеперерабатывающих предприятий // Системы управления и информационные технологии. 2007. №2.1 (28). С. 188-192. 4 . Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т. М.: Мир, 1991. 5 . Гейл Д. Теория линейных экономических моделей. М.: Мир, 1969. 6 . Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио и связь, 1982. 7 . Junginger W. On representatives of multi-index transportation problems // Europ J. of Operational Research. 1993. V. 66 (3). P. 353-371. 8 . Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 9 . Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 10 . Spieksma F.C.R. Multi-index assignment problems: complexity, approximation, applications? / in: P.M. Pardalos, L.S. Pitsoulis (Eds.). Nonlinear Assignment Problems: Algorithms and Applications. Dordrecht: Kluwer Academic Publishers, 2000. P. 1-11. 11 . Сергеев С.И. Новые нижние границы для трипланарной задачи назначения. Использование классической модели // Автоматика и телемеханика. 2008. № 12. С. 53-75. 12 . Гимади Э.Х., Глазков Ю.В. Об асимптотически точном алгоритме решения одной модификации трехиндексной планарной задачи о назначениях // Дискретный анализ и исследование операций. Сер. 2. 2006. Т. 13. № 1. С. 10-26. 13 . Афраймович Л.Г. Трехиндексные задачи линейного программирования с вложенной структурой // Автоматика и телемеханика. 2011. № 8. С. 109-120. 14 . Афраймович Л.Г., Прилуцкий М.Х. Многопродуктовые потоки в древовидных сетях // Известия РАН. Теория и системы управления. 2008. № 2. С. 57-63. 15 . Катеров А.С. Исследование сводимости трёхиндексных транспортных задач к поиску потока в сети с применением параллельных вычислений // Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. М.: МГУП им. Ивана Фёдорова, 2011. С. 47-57. |