Исследование задач размещения предприятий и разработка декомпозиционных алгоритмов их решения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Рубанова, Наталия Алексеевна

• Рубанова, Наталия Алексеевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Рубанова, Наталия Алексеевна

Введение.

Глава 1. Задачи оптимального размещения.

1.1 Постановки задач.И

1.2 Вычислительная сложность задач оптимального размещения предприятий.

1.3 Методы решения задач размещения.

Глава 2. Построение и анализ декомпозиционных алгоритмов для простейшей задачи размещения

2.1 Метод регулярных разбиений.

2.2 Анализ дробных накрытий задач.

2.3 Алгоритмы декомпозиции и перебора L-классов для ПЗР.

2.4 Оценки числа итераций для алгоритма декомпозиции Бендерса.

Глава 3. Разработка декомпозиционных алгоритмов для двухуровневой задачи размещения.

3.1 Задачи двухуровневого программирования.

3.2 Сведение к одноуровневой задаче.6G

3.3 Декомпозиционные алгоритмы для двухуровневой задачи

3.4 Исследование декомпозиционных алгоритмов для двухуровневой задачи.

Глава 4. Результаты экспериментальных исследований

4.1 Особенности алгоритмов.

4.2 Результаты экспериментальных исследований для простейшей задачи размещения.

4.3 Вычислительный эксперимент для двухуровневой задачи размещения.

Введение диссертации (часть автореферата) на тему «Исследование задач размещения предприятий и разработка декомпозиционных алгоритмов их решения»

При планировании развития производства, в сфере сервиса и других областях часто возникает необходимость в решении задач оптимального размещения предприятий. Во многих случаях такие задачи являются весьма сложными и требуют применения методов математического моделирования, разработки специальных алгоритмов и программного обеспечения.

Задачи оптимального размещения могут быть описаны в терминах дискретной оптимизации и образуют важное направление в этой области, которое включает изучение структуры и вычислительной сложности задач, разработку и анализ точных и приближенных методов их решения, выделение полиномиально разрешимые случаев, построение семейств "трудных" задач для определенных алгоритмов [4, И, 38, 134].

Можно выделить два основных типа задач, относящихся к указанному классу: задачи размещения предприятий и задачи размещения взаимосвязанных объектов. В задачах первого типа предприятия необходимо расположить в ряде пунктов и назначить им потребителей, которых они будут обслуживать. Область размещения объектов в задачах второго типа может быть различной: линия, плоскость, сеть и т.д., причем эти обьекты могут быть связаны какими-либо коммуникациями.

Значительное число работ посвящено простейшей задаче размещения предприятий (ПЗР) и ее обобщениям, таким как задача размещения с ограничениями на обьемы производства [74, 138, 146], многопродуктовая производственно-транспортная задача [8], динамическая задача размещения предприятий [11, 94], многостадийная задача размещения предприятий [24, 25] и ряд других. В последнее время большой интерес вызывают задачи многоуровневнего программирования, к которым относится,

Бендерса [76, 90, 119, 123, 144], который часто используется в сочетании с другими методами, например, со схемой Балаша [8], перебором L-классов [127, 138]. С теоретической точки зрения метод декомпозиции Бендерса пока еще недостаточно изучен. В частности, актуальными являются вопросы получения оценок числа итераций, исследование глубины отсечений, выделение семейств "трудных"задач и другие. При построении отсечений Бендерса оптимальные значения двойственных переменных определяются неоднозначно, что существенным образом можно использовать для повышения эффективности алгоритмов.

В последнее время в области целочисленного программирования получил развитие предложенный А.А. Колоколовым подход, основанный на регулярных разбиениях евклидова пространства, в частности, на использовании L-разбиений и Lfc-разбиений. Применение такого подхода к задачам целочисленного программирования позволяет изучать структуру задач, вводить и исследовать новые классы отсечений, получать оценки числа итераций алгоритмов, исследовать их устойчивость [6, 41, 43, 56, 57, 60, 130].

Целыо диссертации является является исследование простейшей задачи размещения предприятий и ее обобщения - двухуровневой задачи с использованием регулярных разбиений, разработка и анализ декомпозиционных алгоритмов с отсечениями Бендерса для решения этих задач.

Основными обьектами исследования в диссертации являются простейшая и двухуровневая задачи размещения предприятий. Для их решения разработаны и реализованы точные алгоритмы, основанные на применении декомпозиции Бендерса. В этих алгоритмах решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных подзадач. Для построения производственных подзадач используются дополнительные неравенства (отсечения Бендерса).

Рассматриваемые варианты декомпозиционных алгоритмов отличаются от классических тем, что в них не требуется решать задачу целочисленного программирования при нахождении очередного производственного плана. Эти планы выбираются среди допустимых решений производственной задачи с помощью алгоритма перебора L классов или направленным перебором булевых векторов.

Предложены гибридные варианты данных алгоритмов с различными эвристиками. Исследована глубина используемых отсечений и получены оценки числа итераций алгоритмов на построенных нами семействах задач. Проведен анализ эффективности отсечений в зависимости от способа выбора оптимальных значений двойственных оценок, используемых при их построении.

Кроме того, в работе построены семейства простейших задач размещения с мощными Lfc-разбиениями дробных накрытий задач. Проведены экспериментальные исследования эффективности различных вариантов предложенных алгоритмов.

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Рубанова, Наталия Алексеевна

Основные результаты диссертации заключаются в следующем:

1. Разработаны алгоритмы решения простейшей и двухуровневой задач размещения предприятий, основанные на декомпозиции Бендерса и переборе L-классов.

2. Построены и исследованы семейства рассматриваемых задач размещения, на основе которых получены оценки числа итераций для предложенных декомпозиционных алгоритмов и ряда других алгоритмов целочисленного программирования.

3.Проведен анализ зависимости отсечений Бендерса от выбора оптимальных значений двойственных переменных, найдены оценки глубины отсечений с использованием предложенных семейств, указаны способы повышения эффективности алгоритмов.

4. Выполнена реализация декомпозиционных алгоритмов для простейшей и двухуровневой задач размещения предприятий, проведено их экспериментальное исследование.

Заключение

В диссертации получили дальнейшее развитие и применение методы декомпозиции и регулярных разбиений в дискретной оптимизации. С использованием этих подходов предложены новые варианты точных алгоритмов решения ряда известных задач размещения предприятий, имеющих широкий круг приложений в экономике, управлении, планировании и других областях, изучены некоторые свойства указанных задач и алгоритмов.

Список литературы диссертационного исследования кандидат физико-математических наук Рубанова, Наталия Алексеевна, 2006 год

1. О сложности задач минимизации полиномов от булевых переменных // Управляемые системы.- Новосибирск, 1983. Вып.23.- С.3-19.

2. Агеев А.А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений// Материалы конференции-Новосибирск: Изд-во ИМ СО РАН, 1998.- С.4 10.

3. Агеев А.А., Гарагулов М.М. Новые менее трудоемкие алгоритмы для некоторых частных случаев задачи размещения// Материалы конф.- Новосибирск: Изд-во ИМ СО РАН, 1998.- С.96.

4. Аделыпин А.В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика, 2004.-N 3. С.35-42.

5. Александров Д.А., Кочетов К)А. Алгоритм муравьиной, колонии для задачи о минимальном покрытии// Материалы конференции Новосибирск: Изд-во ИМ СО РАН, 1998. С.106.

6. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978.

7. Береснев B.JI. Эффективный алгоритм, для задачи размещения производства с вполне уравновешенной матрицей// Дискретный анализ и исследование операций, 1998.-Серия 1, т. 5, N1.- С.20-31.

8. Береснев В.JI. Алгоритмы минимизации полиномов от булевых переменных // Проблемы кибернетики, 1979.- Вып. 36. С.225-246.

9. И. Береснев В.Д., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978.

10. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

11. Вознюк И.П., Гимади Э.Х. Задача размещения на сети с учетом пропускных способностей коммуникаций// Труды XI международной Байкальской школы-семинара.- Иркутск, Байкал, 1998. Т.1.-С.114-117.

12. Гермейер Ю.Б. Игры с непротивоположными интересами. Москва: Наука, 1976.

13. Гидоян JI.K., Трубин В.А. О некоторых классах задач размещения деревьев на цепи/ j Кибернетика, 1991.- N 2. С.76-79.

14. Гимади Э.Х. Эффективный алгоритм решения задачи размещения с областями обслуживания, связными относительно ациклической сети// Управляемые системы Новосибирск, 1983.- Выи 23.-С. 12-23.

15. Гимади Э.Х. Задачи размещения на сети с центральносвязными областями обслуживания// Управляемые системы.- Новосибирск, 1984. Вып.25. С.38-47.

16. Гимади Э.Х. Задачи стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами// Управляемые системы- Новосибирск, 1987.-Вып.27,- С.З 11.

17. Гимади Э.Х. Обоснование априорных оценок качества приближенного решения задачи стандартизации// Управляемые системы. Новосибирск, 1987. Вып.27.- С.12-27.

18. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений:Учебное пособие.- Новосибирск, 1991.

19. Гимади Э.Х., Дементьев В.Т. Некоторые задачи выбора оптимальных параметрических рядов и методы их решения (задачи стандартизации)/ / Проблемы кибернетики, 1973 Вып. 27.- С.19-32.

20. Гончаров Е.Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискретный анализ и исследование операций, 1998. Серия 2, т. 5, N 1.- С. 19-39.

21. Гончаров Е.Н. Приближенный алгоритм для задачи размещения по критерию максимума// Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, Байкал, 1998.- С. 125-128.

22. Гончаров Е.Н., Кочетов Ю.А. Вероятностный жадный алгоритм: с ветвлением для многостадийной задачи размещения // Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения".- Иркутск, Байкал, 1998.- С. 121-124.

23. Гончаров Е.Н., Кочетов Ю.А. Трудный класс исходных данных для многостадийной задачи размещения // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения".- Омск, 2003.-С.80.

24. Горбачевская JI.E. К двухуровневой экстремальной задаче выбора номенклатуры шделгш/Препринт.- Новосибирск: ИМ СО РАН, 1998.

25. Горбачевская Л.Е., Дементьев В.Т., Шамардин Ю.В. Двухуровневая экстремальная задача выбора номенклатуры изделий: Препринт- Новосибирск: ИМ СО РАН, 1997.

26. Горбачевская Л.Е., Дементьев В.Т., Шамардин Ю.В. Двухуровневая задача стандартизации в условиях однозначного выбора потребителей // Дискретный анализ и исследование операций, 1999. Серия 2, т. 6, N 2.- С.3-16.

27. Горбачевская Л.Е., Кочетов Ю.А. Вероятностная эвристика для двухуровневой задачи размещения // Труды XI между-нар. Байкальской школы-семинара "Методы оптимизации и их приложения".- Иркутск, Байкал, 1998-С.249-252.

28. Гришухин В.П. Полиномиалъносгпъ в простейшей задаче размещения: Препринт. Москва: ЦЭМИ АН СССР, 1987.

29. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи./ Пер. с англ.- Москва: Мир, 1982.

30. Девятерикова М.В. Об устойчивости L- накрытий задач булева программирования.// Матер, междунар. конф. "Дискретный анализ и исследование операций". Новосибирск, 2000. - С.145.

31. Дементьев В.Т. Производство экологического оборудования в условиях рыночной экономики и госдотаций. // Труды III междунар. конф. "Математические проблемы экологии",- Новосибирск, 1996.-С.100-102.

32. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во НГУ, 1996.

33. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. Москва: Наука, 1981.

34. Еремеев А.В. Генетический алгоритм для задачи о минимальном покрытии// Материалы конф.- Новосибирск: Изд-во ИМ СО РАН, 1998.- С.21-24.

35. Еремеев А.В. Генетические алгоритмы и некоторые задачи дискретной оптимизации// Тез. докл. междунар. конф. "Проблемы оптимизации и экономические прилож.мск: ОмГУ, 1997.- С.47.

36. Заблоцкая О.A. L-разбиение многогранника стандартизации// Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд Омск: ОмГУ, 1987.- С.151-154.

37. Забудский Г.Г.О целочисленной постановке одной задачи размещения объектов на линии// Управляемые системы. Новосибирск, 1990. Вып.30.- С. 35-45.

38. Забудский Г.Г., Леванова Т.В. Разработка алгоритмического и программного обеспечения для решения задач оптимальной компоновки// Тез. конф. "Проблемы повышения эффективности создаваемых и внедряемых АСУ".- Омск, 1988.- С.26.

39. Заикина Г.М., Колоколов А.А., Леванова Т.В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 25 41.

40. Заозерская Л.А. Некоторые гибридные алгоритмы для задачи о покрытии// Труды XI Всерос. конф. "Математическое программирование и приложения".- Екатеринбург, 1997.- С.100.

41. Заозерская Л.А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества// Труды XI Междунар. школы-семинара "Методы оптимизации и их приложения". Иркутск,Байкал, 1998.-Т.1.- С.139-142.

42. Ильев В.П. Алгоритмы с оценками для задачи о р-медиане на минимум и ее обобщений // Матер. III Всероссийской конф."Проблемы оптимизации и экономические приложения".-Омск, 2006.- С.32.

43. Карп Р . Сводимость комбинаторных проблем// Кибернетический сборник, 12 Москва: Мир, 1975.- С. 16-58.

44. Ковалев М.М. Матроиды в дискретной оптимизации. Минск: Изд-во "Университетское", 1989 - 222с.

45. Колоколов А.А. О лексикографической структуре некоторых выпуклых многогранных множеств// Тез. докл. V Всесоюзн. конф. по проблемам теоретической кибернетики. Новосибирск, 1980.-С.77-79.

46. Колоколов А.А. Регулярные отсечения при решении задач целочисленной оптимизации// Управляемые системы.- Новосибирск: ИМ СО АН СССР, 1981,- Вып. 21.- С. 18 25.

47. Колоколов А.А. Методы дискретной оптимизации:// Учебное пособие Омск: ОмГУ, 1984.

48. Колоколов А.А. Построение алгоритмов целочисленного программирования на основе Lразбиений// Тез. докл. конф. "Математическое программирование и приложения".- Свердловск, 1991.-С.86.

49. Колоколов А.А. Выпуклые множества с альтернирующим L разбиением// Межвуз. сб. научн. трудов "Моделирование и оптимизация систем сложной структуры".- Омск: ОмГУ, 1987. С.144 150.

50. Колоколов А.А. Регулярные разбиения в целочисленном программировании/ / Сб. научн. трудов "Методы решения и анализа задач дискретной оптимизации". Омск, 1992.- С.67-93.

51. Колоколов А.А. Применение регулярных разбиений в целочисленном программировании // Известия вузов. Математика, 1993. N 12. С. 11-30.

52. Колоколов А.А. Регулярные разбиения и метод ветвей и границ// Тез. докл. конф. "Математическое программирование и приложения".- Екатеринбург, 1993.- С.61.

53. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном, программировании, j/ Сиб. журнал исслед. операций.- Новосибирск, 1994. Т.1, N 2. С.18-39.

54. Колоколов А.А.,Девятерикова М.В. Регулярные разбиения и устойчивость задач целочисленного программирования // Тез. докл. конф. "Математическое программирование и приложения" Екатеринбург, 1999.- С.161-162.

55. Колоколов А.А.,Девятерикова М.В. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика, 2004. -N 3,- С.48-54.

56. Колоколов А.А., Косарев НА. Исследование отсечений Бендерса для задачи о р-медиане// Матер. Всерос. конф. "Проблемы оптимизации и экономические приложения". Омск, 2003. С.96.

57. Колоколов А.А., Косарев Н.А., Рубанова Н.А. Исследование отсечений Бендерса в декомп. алгоритмах решения некоторых задач размещения// Омский научный вестник, 2005. -N 2. С.76-80.

58. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

59. Вестник Омского ун-та.- Омск: ОмГУ, 1996. N 1. -С.21 23.

60. Колоколов А.А.,Рубанова Н.А. Декомпозиционный метод решения двухуровневой задачи стандартизации //Матер, междунар. копф. "Математика в вузе".- Великий Новгород, 2000 С. 142-143.

61. Колоколов А.А.,Рубанова Н.А. Об одном декомпозиционном методе решения двухуровневой задачи стандартизации // Сб. научных трудов конф. с межд. участием "Новые технологии ж/д транспорту". Омск: ОмГУПС, 2000.- С.121-124.

62. Колоколов А.А.,Рубанова Н.А. Об одном декомпозиционном алгоритме решения двухуровневой задачи размещения // Труды XII междунар. конф. Иркутск, Байкал, 2001 Т.1. С.207-210.

63. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. Москва: Наука, 1969.

64. Коротин К.Е. Модификация метода поиска глобального экстремума в задаче размещения многоугольников в полосе.// Харьков: Ин-т пробл. машиностр. НАН Украины, 1998.

65. Косарев Н.А.,Рубанова Н.А. Об отсечениях Бендерса для некоторых задач размещения предприятий // Матер. Рос. конф."Дискретный анализ и исследование операций".- Новосибирск, 2004. С. 164.

66. Кочетов Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации// Матер, конф.- Новосибирск: Изд-во ИМ СО РАН, 1998.- С.21-24.

67. Кочетов Ю.А. Локальный поиск для дискретных задач размещения // Матер. III Всероссийской конф."Проблемы оптимизации и экономические приложения".- Омск, 2006. С.47.

68. Кочетов Ю.А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями// Дискретный анализ и исследование операций, 2003,-Серия 2, Т.10, N 1.- С.11-43.

69. Кочетов Ю.А., Плясунов А.В. Полиномиально разрешимый класс задач двухуровневого линейного программирования// Дискретный анализ и исследование операций, 1997.- Серия 2, том 4, N 2.- С.23-33.

70. Кочетов Ю.А., Плясунов А.В. Задача выбора ряда изделий с частичным внешним финансированием// Дискретный анализ и исследование операций, 2002.- Серия 2, том 9, N 2.- С.78-96.

71. Кук С. А .Сложность процедур вывода теорем/ / Кибернетический сборник, 12 Москва: Мир, 1975 - С.5-15.

72. Леванова Т.В. Исследование декомпозиционных алгоритмов для решения некоторых задач размещения// Тез. докл. конф. "Математическое программирование и приложения".- Екатеринбург, 1997,- С.144-145.

73. Лэсдои Л.С. Оптимизация больших систем. Москва: Наука, 1975.

74. Линкер Н.В. Оценка погрешности градиентного алгоритма для задачи о р-медиане // Матер. Рос. конф. "Дискретный анализ и исследование операций". Новосибирск, 2002. С.213.

75. Мину М.Математическое программирование. Теория и алгоритмы. Москва: Наука, 1990.

76. Пападимитриу X., Стайнглиц К. Комбинаторная оптимизация: Алгоритмы и сложность./ Пер. с англ.- Москва: Мир, 1985.

77. Панюков А.В. Алгоритмы локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети// Изв. АН СССР, Техн. кибернетика, 1981. N 6 С.180-184.

78. Панюков А.В. Алгоритмы размещения прямоугольных объектов// Матер. Всес. конф. "Декомпозиция и координация в сложных системах". Челябинск, 1987.- С.80-89.

79. Пащенко М.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств // Дискретный анализ и исследование операций, 1997,- Серия 2, т.4, N 1- С.40-53.

80. Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности// Труды XI межд. школы-семинара. Иркутск, Байкал, 1998.- т.1- С.175-178.

81. Плясунов А.В. Полиномиально-разрешимая задача двухуровневого вогнутого программирования// Тез. докл. межд. конф. "Сибирская конференция по исследованию операций".- Новосибирск, 1998.- С.94.

82. Рубанова Н.А. О мощности L-накрытий простейшей задачи размещения // Матер. Рос. конф."Дискретный анализ и исследование операций". Новосибирск, 2002.- С.215.

83. Рубанова Н.А. Анализ простейшей задачи размещения предприятий с использованием Ьк-разбиения j j Вестник Омского уи-та.-Омск: ОмГУ, 2003. N 1. - С.15-17.

84. Рубанова Н.А. О числе итераций алгоритма Бендерса для двухуровневой задачи размещения предприятий // Матер. V Межд. науч.-техн. конф. "Динамика систем, механизмов и машин".- Омск, 2004,- кн. 2,- С.329.

85. Рубанова Н.А. Исследование декомпозиционных алгоритмов решения некоторых задач размещения // Матер. III Всерос. конф."Проблемы оптимизации и экономические приложения". Омск, 2006.- С.119.

86. Рыков И.А. Двухуровневая задача выбора цен на продукцию предприятий /j Матер. Рос. конф."Дискретный анализ и исследование операций". Новосибирск, 2004.- С. 146.

87. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- Киев: Наукова думка, 1988.

88. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка, 1986.

89. Схрейвер А. Теория линейного и целочисленного программирования.! Пер. с англ. В 2-х т. Москва: Мир, 1991.

90. Филимонов Д.В. О дискретной минимаксной задаче размещения с древовидной структурой связей и ограничениями на максимально допустимые расстояния// Матер. III Всерос. конф."Проблемы оптимизации и экономические приложения".- Омск, 2006. С. 130.

91. Хачатуров В.Р. Математические методы регионального программирования. Москва: Наука, 1989.

92. Ху Т.С. Целочисленное программирование и потоки в сетях.! Пер. с англ.- Москва: Мир, 1974.

93. Шамардин К).В. Трехуровневые задачи размещения производства:11репщпт.- Новосибирск: ИМ СО РАН, 1998.

94. Adolfson D., Ни Т.С. Optimal Linear Ordering// SIAM Jornal on Applied Mathematics, 1973.- V.25, N 3,- P.403-423.

95. Ageev A.A., Sviridenko M.I.Approximation Algorithms for some Problems with cardinalyty-type contraints // Труды XI межд. in колы-семинара "Методы оптимизации и их приложения".- Иркутск, Байкал, 1998.- С.107-110.

96. Anandalingam G., Frtesz T.L.Hierarchucal optimization: an introduction //Ann. Oper. Res., 1992.- V.34, N 1. P. 1-11.

97. Anandalingam G., White D.J.Solution Method for the linear static Stackelberg problem using penaiity functions// IEEE Transactions on Automatic Control, 1990.- V.35, N 10.- P. 1170-1173.

98. Audet C., Hansen P.,Jaumard В., Savard G.Links between Linear Bilevel and Mixed 0-1 Programming Problems// .Journal of Opt. Theory and Appl., 1997.- V.93, N 2.- P. 273 300.

99. Arora S., Raghavan P., Rao S. Approximation schemes for the continuous p-center problem on a tree// SIAM J. Algebraic Discrete Methods 1, 1980.- N 4,- P.370-375.

100. Bard J.F., Moore J.T. A branch and bound algorithm for the bilevel programming problem // SIAM J. Sci. Stat. Cornput., 1990.- V.ll, N 2,- P.281-292.104105106107108109110111112

101. Beasley J.E. An algorithm for solving large capacitated warehouse location problems// Europ. J. of Oper. Res., 1988.- N 33.- P.314-325.

102. Ben-Ayed O. Bilevel linear programming // Comput. Oper. Res., 1993,- V. 20, N 5,- P.485 501.

103. Benders J. F. Partitioning Procedures for Solving of Mixed-variables Programming Problems// Numer. Math., 1962. V.4, N 3.- P.238-252.

104. Blair C. The computational complexity of multi-level linear programs // Ann. Oper. Res., 1992.- V. 34, N 1. P.13-19.

105. Calamai P.H., Vicente L.N. Generating linear and linear-quadratic bilevel programming problems // ACM Transactions on Mathematical Software, 1994,- V. 20. P.103-119.

106. Chvatal V. A greedy heuristic for the set-covering problem// Math.Oper. Res.,1979.- V. 4, N 8.- P.789-810.

107. Chudak F.A. Improved approximation algorithms for iincapacitated facility location// IPC06 Proceedings, 1998.

108. Dempe S. A Simple Algorithm for the Linear Bilevel Programming Problem // Optimization, 1987. V.18, N 3. P.373 - 385.

109. Dempe S. Discret Bilevel Optimization Problems // Report № 12: University Leipzig, 1996.

110. Discrete Location Theory/ Ed. by Pitu B.Mirchamdani and Richard L.Franscis, 1990., by John Wiley & Sons, Inc.

111. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process// Report No. TR-91-016. Milan: Politecnico di Milano, 1991.

112. Dudas Т., Klinz В., Woeginger G.J. The computational complexity of multi-level programming problems revisited// Reports from the Optimization Grup at the TU Graz, 1995.-N 49.

113. Efroymson M.E., Ray T.L. A branch-bound algorithm for plant location // Oper. Res., 1966,- V. 14, N 3.- P.361-368.

114. Erlenkotter Б.А.Л dual-based procedure for iincapacitated faciliti location // Oper. Res., 1978.- V. 26, N 6.- P.992 1009.

115. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem. In Proceedings of OR'98, Springer-Verlag, 1999.- P.175-181.

116. Gascon V., Benchakroun A., Ferland J. Benders decomposition for network design problems with underlying tree structure // Investigacion Operativa, 1997. N 6,- P.165-180.

117. Gomory R.E. Outline of an Algorithm for integer Solution to Linear Programme// Bull. Amer. Math.Soc., 1958.- V. 65, N5.- P.275- 278.

118. Guha S., Khuller S. Greedy strikes back: improved facility location algorithms// The Ninth Annual ACM SIAM Symposium on discrete algorithms (SODA), 1998. P.649-654.

119. D.S. Hochbaum Heurustics for the fixed cost median problem// Math. Progr., 1982.-N 22,- P. 148 162.

120. Hooker J.N., Ottosson G. Log ic-based Benders decomposition. // Mathematical Programming Series A., 2003 V.96, N 1.- P.33-60.

121. Il'ev V., Linker N .Performance garantees of a greedy algorithm for minimizing a supermodular set function // Europ. J. of Oper. Res., 2006. V.171, N 2,- P.648-660.

122. Kariv 0., Hakimi L. An algorithmic approach to network location problems. II: The р-medians// SIAM J. Appl. Math.,1979. V. 37, N 3. P.539-560.

123. Kolokolov A.A. On the L-structure of the integer linear programming problems //Proceedings of the 16th IFIP-TC7 Conference on System Modelling and Optimization.- Compiegne, France, 1993. P. 756 760.

124. Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems// Triennal Symposium on Transportation Analysis II. Preprints. Capri, Italy, 1994. V.l. P. 179-183.

125. Kolokolov A.A., Eremeev A.V., Rubanova N.A. Decomposition and L-class Enumeration Algorithms for Solving of some Bilevel Plant Location Problems// XII Meeting of EURO Working Group on Location Analysis. Abstracts Barselona, 2000, P.8. P. 179 183.

126. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem// Journal of Mathematical Modelling and Algorithms, 2006.-Vol.5, N 2. P.189-199.

127. Kolokolov A.A., Kosarev N.A. On Stability of Some Benders Decomposition Algorithms for p-median Problem// In Proceedings of European Chapter on Combinatorial optimization ECCO-18.- Minsk, 2005. P.23.

128. Kolokolov A.A., Kosarev N.A., Rubanova N.A. On Iterations Number of Benders Decomposition Algorithms for Some Facility Location

129. Problems //In Proceedings of European Chapterian on Combinatorial optimization ECCO-18.- Minsk, 2005.- P.27.

130. Kolokolov A.A., Levanova T.V. Some L-class Enumeration Algorithms for Simple Plant Location Problem //Abstr. of International Conference on Oper. Res. Berlin, 1994.- P.75.

131. Kolokolov A.A., Levanova T.V. Some Hybrid Algorithms for the Production-Transportation Problem // Preprints of 8th IF AC Symposium.- Greece, 1997.- P. 896.

132. Krarup J. Fixed-cost and other network flow problems // Ph. D. thesis, IMSOR, Technical University of Denmark, 1967.

133. Krarup J., Pruzan P.M. The simple plant location problem: survay and synthesis // European J. Oper. Res., 1983. V.12, N 1. P. 36-81.

134. M. Laguna, F. Glover Bandwing Packing: A tabu Search Approach // Managment Science, 1993,- V. 39, N.4- P.492-500.

135. Lin J.-H., Vitter J.S., Approximation algorithms for geometric median problems// Inform. Process. Lett. 44, 1992,- N 5.-P. 245-249.

136. Levanova Т. V. Some decomposition algorithms for plant location problem// Book of Abstracts Symposium on Operation Research-Germany, Magdeburg, 1999.- P.76.

137. Local search in Combinatorial optimization/ Edited by E.Aarts and J.K.Lenstra, 1997, John Wiley and Sons Ltd.

138. Love R.F., Wong J.Y. On Solving a One-Dimensional Space Allocation Problem with Integer Programming// INFOR- V.12, N2.- P.139-143.

139. Moore J.T., Bard J.F.The fixed integer linear bilevel programming problem// Oper. Res., 1990.- V. 38, N 5,- P.911-921.

140. Narula S.C., Nwosu F.D. Two-level hierarchical programming problem// Essays and surves on multiple criteria decision making. P.Hansen ed., Springer-Verlab. Berlin, 1983.- P. 290 299.

141. Orlin J.V., Punnen A.P., Schulz A.S.Approximate local search in combinatorial optimization// SIAM J. Comput., 2004.-V. 33, N 5.-P.1201-1214.

142. Randazzo D., Luna H.P.L., Mahey P. Benders Decomposition For Local Access Network Design With Two Technologies // Discrete Mathematics and Theoretical Computer Science 4, 2001.- P.235-246.

143. Reeves C.R. Genetic Algorithms for the Operations Researcher// INFORMS J. on Computing, 1997. V. 9, N 3. - P.231 250.

144. R. Shridharan Invited Reviw. The capasitated plant location problem// Europ. J. of Operational Research, 1995.-N 87. P. 203-213.

145. Stackelberg H.V. The Theory of the Market Economy.// Oxford: Oxford Univ. Press., 1952. J. of Operational Research, 1995.-N 87-P. 203 213.

146. Vicente L.N., Calamai P.H. Bilevel and Multilevel Programming: A Bibliography Review.// Journal of Global Opt., 1994,- V. 5 P. 291 306.