Исследование и решение минимаксных и минисуммных задач размещения на сетях
Диссертация
Значительное число работ в области исследования операций посвящено решению проблем планировки и расположения объектов. Задачи размещения имеют обширную сферу практического применения, поскольку область, в которой производится размещение, может иметь различную структуру, и термин «объект» может трактоваться достаточно широко. Такие задачи возникают при размещении различных пунктов обслуживания… Читать ещё >
Содержание
- Глава 1. Полиномиальные алгоритмы решения задач на деревьях с ограничениями на максимальные расстояния
- 1. 1. Постановка задач
- 1. 2. Алгоритмы решения непрерывной минимаксной задачи
- 1. 3. Решение дискретной минимаксной задачи
- 1. 4. Минисуммная задача размещения
- Глава 2. Алгоритмы ветвей и границ решения задач размещения на произвольных сетях
- 2. 1. Сложность минимаксных и минисуммных задач
- 2. 2. Эквивалентная задача математического программирования
- 2. 3. Дискретная минимаксная задача размещения. '
- 2. 4. Решение минисуммной задачи размещения
- 2. 5. Вычислительный эксперимент
- Глава 3. Эвристические алгоритмы решения задач размещения на произвольных сетях
- 3. 1. Алгоритмы последовательного одиночного размещения
- 3. 2. Генетические алгоритмы
- 3. 3. Алгоритмы поиска с запретами
- 3. 4. Вычислительный эксперимент
Список литературы
- Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем // М.: Радио и связь. 1985. -200 с.
- Агеев А.А. Графы, матрицы и простейшая задача размещения // Управляемые системы. Новосибирск, 1989. — Вып. 29. — С.3−10.
- Агеев А.А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений // Материалы конференции. Новосибирск, 1998. — С.4−10.
- Александров Д.А., Кочетов Ю. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Материалы конференции. Новосибирск, 1998. — С.106.
- Ахмедов И.С., Сигал И. Х. Задача компоновки схемы генплана промпредприятий и некоторые подходы к ее решению // ВЦ АН СССР. М., 1983. — № 270. — 57 с.
- Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. // Львов: Вища школа. Изд-во Львовского ун-та, 1981. 168 с.
- Береснев В.Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации // Новосибирск, 1978. 333 с.
- Гимади Э.Х. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Управляемые системы. Новосибирск, 1987. — Вып. 27. — С.12−27.
- Гончаров Е.Н., Кочетов Ю. А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения // Труды XI междунар. Байкальской школы-семинара «Методы по-тимизации и их приложения». Иркутск, 1998. — С.121−124.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи // М.: Мир, 1982. 416 с.
- Долгий А.Б., Еремеев А. В., Колоколов А. А., Сигаев B.C. Оптимизация размещения буферных устройств в автоматических линиях // Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». Иркутск, 2001. — Т. 1. — С.150−155.
- Еремеев А.В. Генетический алгоритм для задачи о минимальном покрытии // Материалы конф. Новосибирск, 1998. — С.21−24.
- Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. 2000. — Т. 7, N 1. -С.47−60.
- Забудский Г. Г. Задачи оптимального размещения объектов на линии с минимально допустимыми расстояниями. // Препринт АН СССР. Новосибирск, 1990. — 32 с.
- Забудский Г. Г. О некоторых задачах размещения на графах // Труды XI Междунар. Байкальской школы-семинара. Иркутск, 1998. — С.135−138.
- Забудский Г. Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. Новосибирск, 1990. — Вып.30. — С.35−45.
- Забудский Г. Г., Колмычевская Н. В., Леванова Т. В. Оптимизация размещения технологического оборудования на генплане // Тез. симп. «Системы программного обеспечения решения задач оптимального планирования». М., 1988. — С.148.
- Забудский Г. Г., Нежинский И. В. Решение задачи размещения в евклидовом пространстве с запрещенной областью // Вестн. Омского ун-та. 1999. — JY* 2. — С.17−19.
- Забудский Г. Г., Филимонов Д. В. Алгоритм решения минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Омский науч. вест. 1999. — Вып. 9. — С.37−40.
- Забудский Г. Г., Филимонов Д. В. Алгоритмы решения задач размещения на деревьях с ограничениями на максимальные расстояния / / Материалы международной конференции «Дискретный анализ и исследование операций». Новосибирск, 2000. — С.165.
- Забудский Г. Г., Филимонов Д. В. О минимаксной и минисуммной задачах размещения на сетях // Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». Иркутск, 2001. — Т. 1. — С.150−155.
- Забудский Г. Г., Филимонов Д. В. Решение дискретной минимаксной задачи размещения на сети // Изв. вузов. Математика. -2004. № 5. — С. ЗЗ-Зб.
- Забудский Г. Г., Филимонов Д. В. Решение дискретных минимаксных и минисуммных задач размещения на сетях // Материалы российской конференции «Дискретный анализ и исследование операций». Новосибирск, 2002. — С.210.
- Забудский Г. Г., Филимонов Д. В. Решение минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Материалы XI Всероссийской конференции «Математическое программирование и приложения». Екатеринбург, 1999. — С.114.
- Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супер модулярной функции // Дискретный анализ и исследование операций. Сер. 1. 1998. — Т. 5, № 4. — С.45−60.
- Исследование операций // В 2-х томах. Пер. с англ. Под редакцией Моудера Дж., Элмаграби С. М.: Мир, 1981. — 677 с.
- Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // ДАН СССР. 1974 — Т. 215, № 1. — С.49−52.
- Колоколов А.А. Выпуклые множества с альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры: Межвуз. сб. научн. труд. ОмГУ. Омск, 1987.- С.144−150.
- Колоколов А.А. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. — 75 с.
- Колоколов А.А. Применение регулярных разбиений в целочисленном программировании // Изв. вузов. Математика. 1993. — № 12.- С.11−30.
- Колоколов А.А. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемые системы. Новосибирск, 1981. — Вып. 21. — С.18−25.
- Колоколов А.А. Регулярные разбиения в целочисленном программировании // В сб. научн. тр. «Методы решения и анализа задач дискретной оптимизации». Под ред. А. А. Колоколова. Омск, 1992. — С.67−93.
- Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исслед. операций. Новосибирск, 1994. — Т. 1, № 2. — С.18−39.
- Колоколов А.А., Леванова Т. В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения II Вестник Омского ун-та. Омск, 1996. — JV2 1.- С.21−23.
- Корбут А.А., Финкелыптейн Ю. Ю. Дискретное программирование // М.: Наука, 1969. 386 с.
- Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // В сб. лекций «Дискретная математика и приложения». Москва, 2001. — С.84−117.
- Леванова Т.В. Двойственный жадный алгоритм для задачи о р-медиане и ее обобщений // Препринт 98−4. Омск: Омский госуниверситет, 1998. — 13 с.
- Леванова Т.В. Исследование декомпозиционных алгоритмов для решения некоторых задач размещения // Тез. докл. конф. «Математическое программирование и приложения». Екатеринбург, 1997. — С.144−145.
- Майника Э. Алгоритмы оптимизации на сетях и графах // Пер. с англ. М.: Мир, 1981. — 323 с.
- Панюков А.В. Алгоритмы локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети // Изв. АН СССР, Техн. киб-ка. 1981. — № 6. — С.180−184.
- Панюков А.В. Алгоритмы размещения прямоугольных объектов // Матер. Всес. конф. «Декомпозиция и координация в сложных системах». Челябинск. — 1987. — С.80−89.
- Панюков А.В. Декомпозиция задачи размещения прямоугольных объектов // Декомпозиция и координация в сложных системах. Тез. докл. Всес. конф. Челябинск, 1986. — С.53−58.
- Панюков А.В. Квазицелочисленностъ релаксационного многогранника задачи Вебера // Методы оптимизации и их приложения. Труды XI международной Байкальской школы-семинара. -Иркутск, 1998. С.171−174.
- Панюков А.В., Пельцвергер Б. В. Оптимальное размещение дерева в конечном множестве // Журнал вычислительной математики и математической физики. 1988. — Т. 28. — С.618−620.
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность // Пер. с англ. М.: Мир, 1985. — 512 с.
- Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности // Труды XI международной Байкальской школы-семинара. Иркутск, 1998. — С.175−178.
- Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации // Киев: Наукова думка, 1988. -472 с.
- Стоян Ю.Г., Кулиш Е. Н. Автоматизация проектирования компоновки оборудования летательных аппаратов. М.: Машиностроение. — 1984. — 192 с.
- Стоян Ю.Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. Киев: На-укова думка, 1986. — 268 с.
- Стрекаловский А.С., Васильев И. Л. Об одном подходе к решению квадратичной задачи о назначениях // Материалы XI Всероссийской конференции «Математическое программирование и приложения». Екатеринбург, 1999. — С.253−254.
- Стрекаловский А.С., Васильева A.M. Поиск глобального решения в задаче размещения // Материалы международной конференции «Дискретный анализ и исследование операций». Новосибирск, 2000. — С.121.
- Таха X. Введение в исследование операций М.: Издат. дом «Вильяме», 2001. — 912 с.
- Трубин В.А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой j j Кибернетика. 1978. — № 6. — С.67−70.
- Филимонов Д.В. Алгоритм размещения объектов на дереве с минимаксным критерием и максимальными расстояниями // Материалы научной молодежной конференции «Молодые ученые на рубеже третьего тысячелетия». Омск, 2001. — С.84.
- Филимонов Д.В. О способах построения нижних оценок для задач размещения взаимосвязанных объектов на сетях // Материалы Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 2003. — С.111.
- Филимонов Д.В. Решение дискретной минимаксной задачи размещения на древовидной сети // Материалы ежегодного научного семинара аспирантов и студентов-выпускников «Под знаком ?». Омск, 2003. — С.58−61.
- Филимонов Д.В. Решение минисуммной задачи размещения на линии с ограничениями на максимальные расстояния // Материалы Российской конференции «Дискретный анализ и исследование операций». Новосибирск, 2004. — С.170.
- Филимонов Д.В. Эвристические алгоритмы решения минимаксных и минисуммных задач размещения на сетях // Препринт. -Омск: Омск, госуниверситет, 2003. 15 с.
- Филимонов Д.В., Забудский Г. Г. Некоторые алгоритмы размещения взаимосвязанных объектов на сетях // Материалы 12-й Всероссийской конференции «Математическое программирование и приложения». Екатеринбург, 2003. — С.235.
- Форд JI.P., Фалкерсон Д. Р. Потоки в сетях // М.: Мир, 1966.
- Хамисов О.В. Поиск глобального минимума функций, имеющих выпуклые и вогнутые опорные функции // Материалы XI Всероссийской конференции «Математическое программирование и приложения». Екатеринбург, 1999. — С.272−273.
- Adolfson D., Ни Т.С. Optimal Linear Ordering// SIAM Jornal on Applied Mathematics. 1973. — V. 25, № 3. — P.403−423.
- Cabot V., Francis R.L., Stary M.A. A network flow solution to a rectilinear distance facility location problem // AIIE Trans. 2. 1970.- P.132−141.
- Cerny V. A thermodinamical approach to the traveling salesman problem: an efficient simulated algorithm // J. of Optimization Theory an Applic. 1985. — № 45. — P.41−55.
- Chhajed D., Francis R.L., Lowe T.J. Contributions of operation research to location analysis. Invited review // Location Science. 1993.- Vol. 1, № 4. P.263−287.
- Daskin M. A new approach to solving the vertex p-center problem to optimality: algorithm and computational results // Communications of the Operational Research Society of Japan. 2000. — № 45(9). -P.428−436.
- Dearing P.M., Francis R.L. A network flow solution to a multifacility minimax location problem involving rectilinear distances // Transportation Science. 1974. — Vol. 8 — P. 126−141.
- Dearing P.M., Francis R.L., Lowe T.J. Convex location problems on tree networks // Oper. Res. 1976. — № 24(4).
- Discrete Location Theory // Ed. by Mirchamdani P.B., Franscis R.L.- John Wiley & Sons, Inc., 1990.
- Elzinga J., Hearn D., Randolph W.D. Minimax multifacility location problem with euclidean distances // Transportation Science. 1976.- Vol. 10, № 4.
- Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem // Proc. of Operations Research (OR'98). Springer Verlag, 1999. — P.175−181.
- Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the 1st International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. — P.297−303.
- Erkut E., Francis R.L., Lowe T.J., Tamir A. Equivalent mathematical programming formulations of monotonic tree network location problems // Oper. Res. 1989. — № 37(3). — P.447−461.
- Erkut E., Francis R.L., Tamir A. Distance-constrained multifacility minimax location problems on tree network j j Networks. 1992. -№ 22. — P.37−54.
- Francis R.L., Lowe T.J., Ratliff D.H. Distance constraints for tree network multifacility location problems // Oper. Res. 1978. — № 26(4). — P.570−595.
- Gimadi E.Kh. The asimptotical Performance of Approximation Solution for some Simple Plant Location Problems // Abstracts of Iter-national Conference on Operations Research, Zurich. 1998. — P.49.
- Gomory R.E. All Integer Programming Algorithm// Industrial Sheduling. Ed. Muth J.F., Thompson G.l. Prentice-Hall, Englewoods Cliffs. 1963. — P. 193−206.
- Gomory R.E. Outline of an Algorithm for integer Solution to Linear Programme// Bull. Amer. Math. Soc. 1958. — V. 65, № 5.- P.275−278.
- Hochbaum D.S. Heurustics for the fixed cost median problem // Math. Progr. 1982. — № 22. — P. 148−162.
- Jacobsen S.K. An algorithm for the minimax Weber problem // European J. Oper. Res. 1981. — № 6. — P.144−148.
- Kacprzyk J., Stanczak W. A discrete approximation of the Weber problem with euclidean distance // Applicationes Mathematicae. -1984. XVIII. 2. — P.257−270.
- Kariv O., Hakimi S.L. An algorithmic approach to network location problems. I: The p-centers // SIAM J. Appl. Math. 1979. — Vol. 37, № 3. — P.513−538.
- Kariv O., Hakimi S.L. An algorithmic approach to network location problems. II: The p-medians // SIAM J. Appl. Math. 1979.- Vol. 37, № 3.
- Kirkpatrik S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. — № 220. — P.671−680.
- Kolen A. Location problems on trees and in rectilinear plane // Stitchting Mathematish Centrum. Amsterdam, 1982.
- Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On Hybrid L-class Enumeration and Genetic Algorithm for Set Covering Problem //15.th Conference of the International Federation of Operational Research Societies (IFORS'99): Abstr. Pekin, 1999. — P.117.
- Koopmans T.C., Beckmann M.J. Assigment problems and the location of economic activites // Econometrica. 1957. — Vol. 25, № 1.- P.53−76.
- Krarup J., Pruzan P.M. The simple plant location problem: survey and synthesis // European J. Oper. Res. 1983. — V. 12, № 1. -P. 36−81.
- Laguna M., Glover F. Bandwing Packing: A Tabu Search Approach // Managment Science. 1993. — Vol. 39, № 4.- P.492−500.
- Levanova T.V. Some decomposition algorithms for plant location problem // Symp. on Operations Research (SOR99). Magdeburg, 1999. — P.76.
- Lundy M., Mees A. Convergence of an annealing algorithm // Math. Progr. 1986. — № 34. — P. lll-124.
- Malhotra V.M., Kumar M.P., Maheshwari S.N. An 0(V3) Algorithm for Finding Maximum Flows in Networks // Inf. Proc. Letters. 1978.- V. 7, № 6. P.277−278.
- Panyukov A.V., Pelzwerger B.V. Polinomial algorithns to finite Veber problem for a tree network // Journal of Computational and Applied Mathematics. 1991. — № 35. — P.291−296.
- Picard J.C., Queranne M. On the One-Dimensional Space Allocation Problem // Oper. Res. 1981. — Vol. 29. — P.371−391.
- Picard J.C., Ratliff D.H. A cut approach to the rectilinear distance facility location problem // Oper. Res. 1978. — № 26(3). — P.422−433.
- Reeves C.R. Genetic Algorithms for the Operations Researcher // INFORMS Journal on Computing. 1997. — V. 9, № 3. — P.231−250.
- Wesolowsky G.O. The Weber problem: history and perspectives // Location Science. 1993. — Vol. 1, № 1. — P.5−23.
- Zabudsky G.G. Some Resalts for the One-Dimensional Space Allocation Problem // Symp. on Operations Research (SOR99). Jena, 1997. — P.50.
- Zabudsky G.G., Filimonov D.V. An algorithm for minimax location problem on tree with maximal distances // Proc. of the Second International Workshop «Discrete Optimization Methods in Production and Logistics» (DOM2004). Omsk-Irkutsk, 2004. — P.81−85.
- Zabudsky G.G., Filimonov D.V. An algorithm for the location problem on tree with maximal distances // Symp. on Operations Research (SOR99). Magdeburg, 1999. — P.115.
- Zabudsky G.G., Filimonov D.V. Solving discrete minimax location problem on networks // International Conference on Operations Research. Klagenfurt, 2002. — P.153.