Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Мельников Андрей Андреевич

Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий

01.01.09 - Дискретная математика и теоретическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

2 3 ОКТ 2014

Новосибирск - 2014

005553595

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель: доктор физико-математических наук, профессор

Береснев Владимир Леонидович

Официальные оппоненты: Родионов Алексей Сергеевич

доктор технических наук, доцент, Институт вычислительной математики и математической геофизики СО РАН, заведующий лабораторией. Васильев Игорь Леонидович кандидат физико-математических наук, доцент, Институт динамики систем и теории управления СО РАН, г. Иркутск, ведущий научный сотрудник.

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образовашш «Омский государственный университет им. Ф.М. Достоевского»

Защита состоится 26 ноября 2014 г. в 17 час. 30 шш. на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090 г. Новосибирск, пр. Ак. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева и на сайте math.nsc.ru. Автореферат разослан 1 октября 2014 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

Ю. В. Шамардин

Актуальность работы. Задачи размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях. Значительный интерес к задачам так же связан с их высокой сложностью. Исследования в области задач размещения ведутся в Институте математики им. C.JI. Соболева СО РАН с конца 60-х годов прошлого столетия. Актуальность этих исследований обусловлена их важными практическими приложениями. Об этом свидетельствует большое число работ, посвященных задачам размещения. Среди них в первую очередь стоит отметить работы Береснева B.JL, Гимади Э.Х., Дементьева В.Т., Гермейера Ю.Б., Шамардина Ю.В., Колоколова A.A., Антипина A.C., Хамисова О.В., Васильева И.Л., Забудского Г.Г., Левановой Т.В. и др. В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения.

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

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Рассмотрена и изучена новая модель конкурентного размещения предприятий. Исследована ее вычислительная сложность. Показано, что задача поиска се оптимального решения является более сложной, чем боль-

шинство известных NP-тpyдныx задач.

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

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

Основные результаты диссертации. 1. Установлено, что дискретная задача конкурентного размещения предприятий Е^^грудна в случае нулевых затрат на открытие предприятий и булевых матриц доходов от обслуживания потребителей. Показано, что задача конкурентного размещения на графах-звездах №-трудна в случае, когда доход от обслуживания каждого из потребителей не зависит от обслуживающего предприятия.

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

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

Личный вклад. Основные научные результаты получены автором

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

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Предложена новая модель конкурентного размещения. Установлена вычислительная сложность поиска ее оптимального решения. Получены численные методы поиска ее точных и приближенных решений. Разработанные методы реализованы в виде программ. Они показали свою эффективность и могут применяться при решении практических задач, а также при преподавании курсов «Исследование операций» и «Теория принятия решений».

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

— Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013;

— Международная конференция по исследованию операций ЕСС02013, Париж, Франция, 2013;

— Международная конференция по исследованию операций ЕШЮ2012, Вильнюс, Литва, 2012;

— Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2012;

— Российская конференция «Дискретная оптимизация и исследование операций», Новосибирск, Алтай, 2010;

— V Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», Кыргызская Республика, г. Бишкек, 2009;

— Научные семинары Института математики им. С.Л. Соболева СО РАН;

Публикации. По теме диссертации автором опубликовано 11 работ, в том числе 5 статей в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, обзора литературы, трех глав, заключения и списка литературы. Список литературы содержит 74 наименования. Объем диссертации — 112 страниц.

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

Дискретная задача конкурентного размещения предприятий, которую далее будем для краткости обозначать СотрИР, является задачей игрока, именуемого Лидером, в следующей игре Штакельберга [7]. Два игрока, Лидер и Последователь, открывают предприятия с целью «захвата» потребителей и оптимизации своих целевых функций. Вид целевых функций игроков аналогичен целевой функции задачи размещения предприятий с порядком [1, 2, 4, 6]. Требуется отыскать множество предприятий, открытие которых максимизирует прибыль Лидера при условии, что часть потребителей будет захвачена Последователем, который, зная решение Лидера, откроет свои предприятия максимизируя свою прибыль.

Для формальной записи задачи введем обозначения. I = {1 ,...,т] — множество предприятий (мест возможного размещения предприятий);

7 = {1,..., п} — множество потребителей; /¿, г € I — затраты Лидера на открытие предприятия г; gi,г £ I — затраты Последователя на открытие предприятия г; Рг^,г 7 — доход, получаемый предприятием Лидера г при обслужи-

вании потребителя у,

qij, г & I, ] 6 ./ — доход, получаемый предприятием Последователя г при обслуживании потребителя j.

Полагается, что выбор предприятия, обслуживающего потребителя ] 6 3, производится с учётом предпочтений потребителя ]. Будем считать, что они задаются отношением линейного порядка на множестве I. Для г, к 6

I отношение г к означает, что из двух открытых предприятий г и к для потребителя ] е J более предпочтительным является предприятие г. Отношение г >:_,- к означает, что либо г к, либо г =

Введем следующие переменные, аналогичные переменным классической задачи размещения предприятий:

хг — переменная, равная единице, если Лидер открывает предприятие г £ /, и принимающая значение ноль в противном случае;

хц — переменная, принимающая значение единица, если предприятие i £ I, открытое Лидером, оказывается наиболее предпочтительным для потребителя ] £ .7 среди всех открытых Лидером предприятий, и ноль в противном случае;

г* — переменная, равная единице, если Последователь открывает предприятие г € I, и принимающая значение ноль в противном случае;

— переменная принимающая значение единица, если предприятие г € I, открытое Последователем, оказывается наиболее предпочтительным для потребителя j £ .7 среди всех предприятий, открытых как Лидером, так и Последователем, и ноль в противном случае.

С использованием введенных переменных задача СотрПР формулируется как следующая задача двухуровневого программирования [5]:

(1)

Хг 4- хк] < 1, г е I,] £ J\

к&Щ)-^

(2)

^ X эд ? X £ 15 ^ £ 3 5

€ {0,1}, ге/,.7'е.7; ((¿г), {¿г})) — оптимальное решение задачи (5)-(8);

(3)

(4)

кеЦИ-^к

zi,zij е {0,1},

(7)

(8)

Сформулированная задача (1)-(8) включает задачу верхнего уровня (1)-(4) и задачу нижнего уровня (5)-(8), в которой допустимое решение задачи (1)-(4) выступает в качестве параметров. Задачу верхнего уровня будем обозначать через £. Её допустимое решение ((жг), (ж,;,)) далее будем обозначать через X. Задачу нижнего уровня при фиксированном X — через 5(Х), а задачу (1)-(8) целиком, соответственно, через (£,30. Целевую функцию (1) задачи £ будем считать целевой функцией задачи (£,5).

Целевая функция (1) задачи £ выражает величину прибыли, получаемой Лидером с учетом потери части потребителей, захваченных Последователем. Ограничения (2)-(4) являются ограничениями задачи размещения с порядком. Неравенства (2) гарантируют, что в случае, если предприятие г открыто Лидером, потребитель ] не будет обслуживаться в предприятии менее привлекательном, чем г. Эти же неравенства гарантируют, что для обслуживания каждого потребителя может быть выбрано только одно предприятие, открытое Лидером. Целевая функция (5) задачи З'(Х) выражает величину прибыли, получаемой Последователем. Неравенства (6) реализуют условия захвата потребителей Последователем при известном решении Лидера. Также эти ограничения показывают, что Последователь не может открыть свое предприятие в месте, где уже открыто предприятие Лидера. Остальные ограничения задачи являются ограничениями классиче-

ской задачи размещения предприятий.

Допустимым решением задачи (£, будем считать пару (А'. Ё), где X — допустимое решение задачи £, а 2 = ((-г*), (гц)) — оптимальное решение задачи Значение целевой функции (1) на допустимом решении (X, задачи (£, обозначим через Ь(Х, 7,).

Поскольку при некоторых допустимых решениях X задачи £ задача 3(Х) может иметь несколько оптимальных решений, вопрос выбора решения Последователя требует конкретизации. В литературе [3, 5] принято выделять два случая: среди оптимальных решений задачи нижнего уровня выбирается то, которое является наиболее либо же наименее выгодным с точки зрения целевой функции (1). Формально, допустимое решение (X, 2) задачи (£, 5) называется гарантированным (в других источниках песси-

мистическим) решением задачи (£,3), если L(X,Z) ^ L(X,Z) для всякого оптималыюго решения Z задачи Допустимое решение (X, Z) задачи (£,3) называется оптимистическим решением задачи (£,3), если L(X, Z) > L(X. Z) для всякого оптимального решения Z задачи 3"(Х).

Заметим, что в случае, когда X нулевое, для построения допустимого гарантированного (оптимистического) решения задачи (£, £) достаточно взять любое оптимальное решение задачи Для любого ненулевого до-

пустимого решения X задачи £ соответствующее допустимое гарантированное (оптимистическое) решение (X, Z) может быть построено в два этапа. На этапе 1 при фиксированном решении X решается задача и вычисляется оптимальное значение F*(X) ее целевой функции. Далее для каждого j € J через ij (х) обозначим наиболее предпочтительное для j предприятие, открытое Лидером, то есть такое к £ что х^ = 1 и к >zj i для всех i £ I таких, что Xi = 1. На этапе 2 при фиксированном X решается следующая вспомогательная задача 3(Х):

^Pi.OrH^y ^ extr (9)

jeJ ¿6/ ^oazh)

- Х>- + ^ F*(x); (Ю)

iei jeJ iei

Xi + Zi+ г € I, j € J; (11)

kei\iyjk

Zi^Zij, iel,jeJ\ (12)

z^zij 6 {0,1}, ie I, j € J.. (13)

Ограничение (10) обеспечивает то, что в качестве допустимых решений выступают только оптимальные решения задачи SX^Q- Целевая функция (9) выражает величину дохода, которую теряет Лидер при открытии предприятий Последователя: для гарантированных решений (9) максимизируется, а для оптимистических минимизируется. Оптимальное решение Z — ((zi), (г^)) этой задачи дает допустимое решение (X, Z) задачи (£, 5)-При этом величина L(X, Z) будет одной и той же при любом оптимальном решении Z вспомогательной задачи ¡?(ЛГ).

Допустимое гарантированное решение (X*,Z*) будем называть опти-

мольным гарантированным решением, если Ь(Х*, 2*) ^ Ь(Х^) для всякого допустимого гарантированного решения (X, 2). Приближенным гарантированным решением будем называть произвольное допустимое гарантированное решение. Приближенное гарантированное решение (Х,2) будем называть (1 — е)-приближенным гарантированным решением, если Ь(Х, 2) ^ (1 —е)Ь(Х*,2*), где (Х*,2*) — оптимальное гарантированное решение. Аналогичную терминологию будем применять, говоря о допустимых оптимистических решениях.

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

Глава 1 посвящена вычислительной сложности задачи СотрРЬР. Дается краткий обзор известных результатов, касающихся вычислительной сложности задач конкурентного размещения. В разд. 1.1 рассматривается частный случай исследуемой задачи, в котором стоимости открытия предприятий равны нулю. Доказана

Теорема 2. Задача СотрРЬР при = = 0 для всех г € I и

6 {0,1} для всех г е 1,3 € .7 является Т,!?-трудной. Разд. 1.2 посвящён важному случаю задачи СотрРЬР, в котором потребители и места возможного размещения предприятий располагаются в вершинах некоторого графа с заданными длинами ребер. Предпочтения потребителей в таком случае задаются расстояниями в данном графе. Доказана Теорема 4. Задача СотрРЬР на графе-звезде при р13 = для всех г € е ./ м р^з = р^ для всех ¿1,12 ё ] е •/ является ЫР-трудпой.

Вторая глава посвящена алгоритму поиска гарантированных решений задачи СотрРЬР с априорной оценкой точности. В разд. 2.1 приводится общая схема метода ветвей и границ. Разд. 2.2 посвящен описанию процедуры вычисления верхней границы для оптимальных значений целевой функции задачи СотрРЬР.

Для всех j € J матрицы доходов полагаем монотонными относительно порядка >~j, то есть для любых г, к е I, г к имеем р^ > рь3, Яц ^ <1к]-

Вектор у € {0,1,*}т назовем частичным решением. Вектор х € Вт назовем продолжением у, если х^ = у* для всех г е / таких, что у г ф *.

Положим 1°(у) = {» е 1\у{ = 0}, 1х(у) = {г' € /|2/г = 1}. Задачу (£,£) с ограничениями = уг \/г е /°(у) и /1(у) будем обозначать (£(у),

В основе вычисления верхней границы Н(у) для значений целевой функции задачи (£(?/), У) лежит построение системы подмножеств {Ij(y)}, где 1]{у) С I для всех j € J, с использованием которой удается сформулировать достаточные условия захвата потребителей Последователем.

Лемма 4. Пусть (Х,И), X = (хц)), 2 = - до-

пустимое гарантированное решение задачи для частичного ре-

шения у. Для всякого ¿о 6 «7 такого, что Ри,]1,хг,1]п > 0 для некоторого

г0 $ /,„ (у), выполняется равенство ^ = 1.

¿е/

Рассмотрим следующую задачу, которую будем называть оценочной и обозначать 5В(у):

Теорема 5. Пусть у — частичное решение, (X, 2) — оптимальное некооперативное решение задачи (£(у),3% Х° — оптимальное решение задачи 25(у). Справедливо неравенство Ь(Х,2) ^ В(Х°).

В разд. 2.3 приводится детальное описание схемы метода ветвей и границ с результатами её экспериментального исследования.

Третья глава посвящена алгоритмам локального поиска для задачи СотрПР. В разд. 3.1 приводится процедура локального поиска по окрестности специального вида и сравниваются различные стратегии просмотра данной окрестности. В разд. 3.2 на основе данной процедуры локального поиска строится метод поиска по обобщенной окрестности.

Многократное вычисление значения целевой функции в процессе про-

Х-1 ^ . ъ £ I, ^ £ «/5

Х1=Уи г € 1°(у) и 1г(у); хи хц С {0,1}, г €/,.?'€.7.

смотра окрестности является затратной процедурой и не может применяться для решения примеров большой размерности. Разд. 3.3 посвящен процедуре быстрой оценки значения целевой функции.

Зафиксируем решение Лидера X = ((жг), (х^)), и пусть хЬ] = 1 для некоторого ¿о £ I. Тогда для всех j £ J для г € I таких, что ¿о >-] г, в силу ограничений (6) имеем г^ = 0. Пользуясь этим свойством задачи удается предложить процедуру разбиения, для которой верна

Лемма 6. Процедура разбиения имеет трудоемкость 0(п3т) и даёт на выходе разбиение множества потребителей {-Л.} и набор попарно не пересекающихся множеств предприятий {Ь}- Для каждого Ь = 1,... ,Т и каждого ^ € Jt если г г^(х) для некоторого г € то г 6 /¡.

Рассматривая вместо задачи ${Х) набор подзадач {Зч(Х)}, где каждая подзадача получена из $(Х) ограничением множества индексов на множество потребителей и множество предприятий в силу леммы 6, цёлевую функцию (5) задачи -5(Х)

- X] + ы*»= 13 _ 539Л + 53 53

¿е/ зе./ ¿6/ t=l \ <е/( j&Jl геи )

можно максимизировать для каждого Ь отдельно.

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

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

В Заключении приводятся основные результаты диссертации.

Публикации автора по теме диссертации.

1. В. JI. Береснев, А. А. Мельников. Приближённые алгоритмы для задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2010, Т. 17, №6, С. 3-19.

2. В. JI. Береснев, Е. Н. Гончаров, А. А. Мельников. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций. Дискретн. анализ и исслед. опер., 2011, Т. 18, №4, С. 3-16.

3. В. JI. Береснев, А. А. Мельников. Метод ветвей и границ для некооперативной задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2014, Т. 21, №2, С. 3-23.

4. А. А. Мельников. Рандомизирова1шый локальный поиск для дискретной задачи конкурентного размещения предприятий. Автоматика и телемеханика, 2014, №4. С 134-152.

5. А. А. Мельников. Вычислительная сложность дискретной задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2014, Т. 21, №4, С. 62-79.

6. Melnikov A., Beresnev V., Kochetov Yu., Computational complexity of the discrete competitive facility location problem. ECC02013 Conf. Proc. 2013. P. 88.

7. А. А. Мельников. Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий. Материалы конференции «Дискретная оптимизация и исследование операций». Новосибирск: Изд-во ин-та математики. 2013. С. 61.

8. Melnikov A., Beresnev V. Branch and bound method for the competitive facility location problem. EUR02012 Conf. Proc. 2012. P. 204.

9. А. А. Мельников. Результаты экспериментального исследования алгоритма ветвей и гратщ для задачи конкурентного размещения предприятий. Материалы конференции «Проблемы оптимизации и экономические приложения». Омск: Изд-во Ом. гос. ун-та. 2012. С. 152.

10. В. Л. Береснев, А. А. Мельников. Алгоритмы локального поиска по обобщенной окрестности для задачи конкурентного размещения предприятий. Материалы конференции «Дискретная оптимизация и исследование операций». Новосибирск: Изд-во ин-та математики. 2010. С. 110.

11. Мельников А. Метод ветвей я границ для задачи конкурентного размещения предприятий. Материалы конференции «Проблемы оптимизации сложных систем». 2009. Новосибирск: Труды ИВМ и МГ. С. 72-77.

Благодарности. Благодарю научный коллектив лаборатории математических моделей принятия решений института математики им. С. JI. Соболева. Владимира Леонидовича Береснева за научное руководство и неоценимую поддержку. Юрия Андреевича Кочетова, Александра Владимировича Плясунова и Александра Вениаминовича Кононова за компетентные рекомендации. Нину Арнольдовну Кочетову, Михаила Георгиевича Пащенко, Сергея Михайловича Лавлинского, Екатерину Вячеславовну Алексееву, Полину Александровну Кононову, Ивана Александровича Давыдова, Артёма Александровича Панина, Алексея Владимировича Хмелёва и Юлию Юрьевну Великанову за дружескую атмосферу и поддержку. Артёма Валерьевича Пяткина, а также официальных оппонентов, Алексея Сергеевича Родионова и Игоря Леонидовича Васильева, взявших на себя труд по прочтению текста диссертации. Состав семинаров «Математические модели принятия решений» и «Дискретные экстремальные задачи» за помощь в подготовке доклада. Ольгу Алексеевну Кирпиченко и Юрия Владиславовича Шамардина за помощь в подготовке процедуры защиты. Работа посвящается моей маме.

Список литературы

1. Васильев И. Л., Климентова К. Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискрет, анализ и исслед. операций. 2009. Т. 16, № 2. С. 21-41.

2. Васильев И. Л., Климентова К. Б., Кочетов Ю. А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журнал вычислительной математики и математической физики. 2009. Т. 49, № 6. С. 1055-1066.

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

4. Canovas L., Garcia S., Labbe M., Marin A. A strengthened formulation for the simple plant location problem with order // Operations Research Letters. 2007. Vol. 35. P. 141-150.

5. Dempe S. Foundations of Bilevel Programming. Dortrecht: Kluwer Acad. Publ., 2002. 332 p.

6. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // Europ. J. Oper. Res. 1983. no. 12. P. 36-81.

7. Stackelberg H. The Theory of the Market Economy. Oxford: Oxford Univ. Press, 1952. 289 p.

Мельников Андрей Андреевич

Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 04.09.14. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ Л'9 83.

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск