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

• Плясунов Александр Владимирович
• доктор наук
• 2020

Оглавление диссертации доктор наук Плясунов Александр Владимирович

1.2.1 Введение

1.2.2 Математическая модель

1.2.3 Эвристики

1.2.4 Окрестностные структуры

1.2.5 Метаэвристики Gen и VND

1.2.6 Гибридные алгоритмы LS+Gen и LS+VND

1.2.7 Вычислительные результаты

1.3 Двухуровневые задачи размещения с фабричным, равномерным и дискриминационным ценообразованием

1.3.1 Постановки задач

1.3.2 Вычислительная сложность

2 Конкурентные модели размещения производства и ценообразования

2.1 Задача о (г|р)-центроиде: история и вычислительная сложность

2.1.1 Постановка задачи

2.1.2 Вычислительная сложность задачи на евклидовой плоскости

2.1.3 Вычислительная сложность задачи конкурента на евклидовой плоскости

2.2 Точный метод для решения задачи о (г|р)-центроиде

2.2.1 Переформулировка задачи о (г|р)-центроиде

2.2.2 Одноуровневая постановка

2.2.3 Стандартная задача распознавания и эвристики

2.2.4 Схема метода решения задачи (2.1)-(2.8)

2.2.5 Вычислительные эксперименты

2.2.6 Заключение

2.3 Модели конкурентного размещения производства и ценообразования

2.3.1 Содержательная постановка. Основные обозначения

и соглашения

2.3.2 Раздел рынков и вычисление монопольных цен

2.3.3 Математические модели

2.3.4 Вычислительная сложность задачи СРЬР

2.3.5 Приближённые алгоритмы решения задачи СРЬР

2.3.6 Вычислительный эксперимент

2.3.7 Заключение

3 Методы декомпозиции для решения двухуровневых задач с ранцевыми ограничениями на нижнем уровне

3.1 Задача выбора ряда изделий с частичным внешним финансированием и ограничениями на объемы производства

3.1.1 Математическая модель

3.1.2 Декомпозиция допустимой области

3.1.3 Применение Лагранжевых релаксаций для построения нижних оценок

3.1.4 Сравнение нижних оценок

3.1.5 Верхние оценки

3.2 Задача с многоинвариантным ранцем на нижнем уровне

4 Модели планирования государственно-частного партнерства

4.1 Математические модели государственно-частного партнерства

4.2 Вычислительная сложность

4.3 Приближённые алгоритмы

4.4 Модельный полигон

4.5 Численный анализ свойств решений

4.6 Заключение

5 Двухуровневые задачи размещения хабов и ценообразо-

вания

5.1 Математическая модель

5.2 Существование равновесия Штакельберга в общей задаче

5.3 Равновесие Нэша

6 О сводимости задач двухуровневого программирования к

задачам векторной оптимизации

6.1 Основные определения

6.2 Сводимость двухуровневой задачи к задаче векторной оптимизации

6.3 Сводимости в частных случаях

6.3.1 Сводимости, использующие необходимые условия оптимальности

6.3.2 Случай линейной задачи нижнего уровня

6.3.3 Двухуровневая задача с линейной задачей о ранце

на нижнем уровне

6.4 Задачи с дискретными переменными

6.4.1 Задача о р-медиане с предпочтениями клиентов

6.5 Заключение

Заключение

Литература

269

Введение

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

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

Введение диссертации (часть автореферата) на тему «Двухуровневые модели размещения и ценообразования: вычислительная сложность и методы решения»

Актуальность темы

Исследование мотивировано сравнительно скромным объемом работ по математическому моделированию иерархических процессов размещения производства и ценообразования, теоретическому исследованию соответствующих моделей и их актуальностью для анализа широкого спектра производственных и экономических ситуаций, возникающих на практике [1, 2, 3].

Процессы размещения производства и ценообразования обычно исследуются отдельно и независимо друг от друга [3, 4, 5]. Основная причина этого связана с тем, что они относятся к разным горизонтам планирования. Процессы размещения относятся к долговременному планированию, а процессы ценообразования относятся к краткосрочному планированию. Как следствие, в большинстве случаев сначала выбирается размещение, а затем цены. Таким образом, разделение размещения и ценообразования при моделировании сужает возможности анализа исследуемой ситуации [6, 7]. Поэтому современные подходы к выбору эффективного механизма взаимодействия процессов размещения производства и ценообразо-

вания основываются на их совместном анализе в рамках одной модели

[7, 8, 9, 10].

В настоящее время в исследованиях экстремальных задач основные акценты переносятся на учёт конкуренции, динамики, иерархии, разного рода условий равновесия, обратные задачи оптимизации и неопределенность в исходных данных [11, 12, 13, 14, 15, 16, 17, 18, 19]. Однако в подавляющей части этих исследований рассматриваются задачи, в которых лишь одно лицо принимает решения. Последнее обстоятельство ограничивает применимость этих математических моделей для анализа двухуровневых или многоуровневых иерархических процессов, в которых последовательно принимают решения два и более игроков.

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

Отличительной чертой исследуемых процессов является наличие иерархии среди лиц (игроков), принимающих решения последовательно и стремящихся достичь наилучшего результата в рамках своего уровня компетенции. В процессе математического моделирования подобных иерархических процессов используются средства, позволяющие адекватно представлять получаемые результаты при принятии решений игроками. Общий подход к решению этой проблемы связан с представлением иерархического процесса в виде системы вложенных оптимизационных моделей. Особенностью моделей такого типа является появление внутренних параметрических оптимизационных задач с ограничениями в виде теоретико-множественных включений. Каждое из подобных ограничений требует, чтобы определенная часть переменных многоуровневой задачи являлась оптимальным решением некоторой внутренней экстремальной задачи [20, 21].

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

гих подходов возникают трудности принципиального характера [22].

Как следствие, двухуровневые задачи имеют существенно более высокую вычислительную сложность. Даже проверка решения подобной задачи на допустимость, как правило, требует решения МР-трудной внутренней оптимизационной задачи [23, 24, 25, 26, 33, 34]. Если оптимальное решение данной задачи не единственно, то появляются дополнительные проблемы, связанные с вычислением целевой функции верхнего уровня. Выбор разных оптимальных решений во внутренней задаче может приводить к разным значениям целевой функции верхнего уровня. Появляются нюансы в определении оптимального решения, которые приводят к появлению новых понятий оптимистического и пессимистического решений [21, 35]. Кроме того, существует проблема совместности ограничений верхнего уровня при выборе оптимальных решений на нижних уровнях. В пессимистичной постановке игрок на нижнем уровне может сознательно выбирать оптимальное решение, «ломающее» систему ограничений игрока на верхнем уровне. Подобная возможность приводит к необходимости дальнейшего уточнения понятий оптимистического и пессимистического решений [36, 37].

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

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

Исследования последних лет показывают, что с точки зрения теории вычислительной сложности двухуровневые задачи - существенно более сложный объект, чем их классические одноуровневые аналоги. Например, задача о (г|р)-центроиде (конкурентная задача о р-медиане) [24, 25, 26, 99] является ^^-трудной в любом из вариантов: дискретном, на сети или евклидовой плоскости. Этот результат говорит о том, если Р = МР, то данная задача может быть решена переборным алгоритмом, который время от времени должен обращаться к решению некоторой МР-полной задачи, и для нее не может существовать детерминированного или недетерминированного точного алгоритма с полиномиальным временем работы [38]. Аналогично, если известно, что оптимизационная задача является МРО-трудной относительно подходящей сводимости, сохраняющей аппроксимируемость, то нет никаких оснований для существования полиномиальных приближенных алгоритмов с хорошими оценками относительного уклонения приближенного решения от оптимального при условии, что Р = МР [38]. Подобные результаты были получены для двухуровневых моделей государственно-частного партнерства [33, 32].

Известны довольно простые двухуровневые задачи, для оценки аппроксимируемости которых уже недостаточно первого уровня аппрокси-мационной иерархии. Поэтому, достраивая классическую аппроксимаци-онную иерархию до второго уровня, мы получаем инструмент, позволяющий более тонко характеризировать аппроксимируемость двухуровневых задач. В качестве примера приведем конкурентные задачи размещения и ценообразования исследованные в [23], которые принадлежат классу Ро1у-АРХр. Также известно, что задачи планирования государственно-частного партнерства лежат в классе ^р О Э ЫРО (строгое включение следует из того, что данный класс задач является МРО-трудным, и в случае совпадения классов ^р О и ЫРО следовало бы, что Р = МР) [34].

Еще одно важное направление исследований связано с классической парадигмой теории вычислительной сложности, которая говорит о ситуации "в худшем случае"[38]. Иными словами, если мы возьмем произвольный вход МР-трудной оптимизационной задачи, то на нем точному алгоритму не обязательно потребуется экспоненциальное число операций для нахождения оптимального решения. Точно так же, если мы возьмем произвольный вход плотно-РЬб'-трудной задачи локального поиска [39, 40, 41], то не обязательно, что алгоритму локального поиска

потребуется экспоненциальное число шагов для отыскания локального оптимума. Аналогичная ситуация с МРО-трудными оптимизационными задачами. Совершенно не обязательно, что приближенный алгоритм решения выполнит на заданном входе экспоненциальное число шагов или оценка уклонения приближенного решения от оптимального окажется очень большой. В связи с этим следует также отметить, что существующая теория вычислительной сложности практически ничего не говорит о количестве плохих входов или их распределении. И это обстоятельство существенно повышает роль вычислительного эксперимента в итоговой оценке качества точных и приближенных алгоритмов, а также в разработке трудных входов для этих алгоритмов или наоборот легких входов [39]. Более того, современная вычислительная практика показывает, что приближенные алгоритмы, основанные на локальном поиске и метаэв-ристиках, позволяют получать приближенные решения весьма высокого качества для очень сложных с точки зрения теории задач. Однако точные алгоритмы в этом плане оказываются в худшей ситуации. Например, практика применения такого известного метода, как метод ветвей и границ, для решения МР-трудных задач показывает, что основную долю вычислительного времени основанные на этом методе алгоритмы тратят на проверку того, что текущий рекорд, являющийся оптимальным решением и найденный на достаточно ранней стадии его работы, действительно является оптимумом. По этой причине в последние годы появились исследования, целью которых является разработка гибридных алгоритмов, совмещающих лучшие качества метаэвристик и точных методов [4, 25, 26]. Поскольку отсутствуют подходы, позволяющие оценить долю "трудных"входов среди входов, имеющих ограниченную сверху и снизу длину, всегда есть надежда, что на реальных входах задачи достаточно большой размерности разрабатываемые гибридные алгоритмы могут оказаться практически эффективными. Вышеизложенное можно рассматривать как гипотезу, которая поддаётся практической проверке. Если в процессе вычислительного эксперимента время работы изучаемого алгоритма на входах, длины которых попадают в некоторый ограниченный интервал, оказывается ограниченным значением некоторого полинома от длины входа, то это обстоятельство может свидетельствовать в пользу данной гипотезы.

Таким образом, настоящая работа, направленная на создание и исследование математических моделей двухуровневых иерархических процессов размещения производства и ценообразования, на разработку эффек-

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

Целью диссертационной работы является:

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

2. Разработка математического аппарата для анализа и решения исследуемых задач, включая:

а). установление связей рассматриваемых задач с полиномиальной и аппроксимационной иерархиями;

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

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

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

Основные результаты диссертации (Для каждого результата приведены ссылки на журнальные статьи автора)

1. Введены новые сложностные классы, расширяющие аппроксима-ционную иерархию, которые позволили выяснить вычислительную сложность и качество аппроксимации следующих задач двухуровне- вого программирования: конкурентного размещения и ценообразова- ния и задач планирования государственно-частного партнёрства. В частности, задачи первого типа принадлежат новому классу Ро1у-АРХр [23], а задачи второго типа являются МРО-трудными относительно АР-сводимости и принадлежат новому классу ЕРО [32, 33, 34]. Установлена Ер* -трудность этих задач [23, 34, 42].

2. Исследована сложность аппроксимации двухуровневых задач размещения и ценообразования с различными стратегиями ценообразования. Установлено, что эти задачи являются Poly-APX-полными относительно AP-сводимости, то есть при выполнении гипотезы P = NP для данных классов задач, не существует полиномиальных точных алгоритмов решения, а также не существует FPTAS- и PTAS-алгоритмов, полиномиальных приближенных алгоритмов с константной и логарифмической от длины записи исходных данных оценкой точности аппроксимации [43, 44, 45].

3. Предложен новый подход к моделированию двухуровневых конкурентных процессов при выборе хабов, топологии транспортных сетей и оптимального ценообразования. Показано, что существует равновесие Штакельберга как для кооперативного, так и некооперативного взаимодействия игроков. Более того, для лидера всегда существует решение, приносящее ему максимальную прибыль, независимо от того, соглашаются ли игроки придерживаться ценового равновесия по Штакельбергу или склонны к ценовой войне и поиску равновесия по Нэшу [46, 47, 48].

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

5. Разработан новый точный метод решения двухуровневых задач размещения и ценообразования, основанный на идее гибридизации. Данным методом получены новые эффективные алгоритмические схемы:

- точный гибридный итерационный алгоритм, основанный на идеях декомпозиции и генерации отсечений для задачи о (г|р)-центроиде [25, 26];

- точные гибридные алгоритмы на основе декомпозиции, метода отсечений и метода поиска с запретами для двухуровневой задачи с фабричным ценообразованием [4].

6. Разработаны новые гибридные приближенные методы решения для следующих двухуровневых задач размещения и ценообразования:

- двухэтапные эвристики на основе локального поиска, генетической эвристики и методе спуска с чередующимися окрестностями для задач размещения и фабричного ценообразования [45];

- рандомизированные методы локального поиска для моделей конкурентного размещения и ценообразования [23];

- итерационные методы стохастического локального поиска, использующие плотные верхние границы на значение целевой функции лидера для моделей планирования государственно-частного партнёрства [32, 33, 34, 50, 51].

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

1. Рассмотрены новые постановки двухуровневых задач размещения с различными стратегиями ценообразования. Исследована их вычислительная и аппроксимационная сложность. Для задачи размещения с фабричным ценообразованием и медианным ограничением разработаны гибридные двухэтапные эвристики на основе генетического локального поиска и локального поиска с чередующимися окрестностями. Для двухуровневой задачи с фабричным ценообразованием на основе метода декомпозиции разработаны гибридные точные и приближенные алгоритмы решения.

2. Предложены новые модели конкурентного размещения и ценообразования. В них раздел спроса реализуется на основе модели ценовой войны Бертрана. Максимальный доход каждого игрока задаётся невоз-растающей функцией, монотонно зависящей от себестоимости обслуживания каждого рынка. Показано, что такие модели принадлежат второму уровню полиномиальной иерархии и второму уровню аппроксимаци-онной иерархии. Предложены гибридные приближенные эвристики на основе локального поиска и альтернирующей эвристики. Для задачи о (г|р)-центроиде разработан новый точный итерационный алгоритм на основе метода декомпозиции и метода отсечений.

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

4. Разработаны и исследованы новые двухуровневые модели плани-

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

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

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

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

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

- Российская конференция «Дискретный анализ и исследование операций», Новосибирск, 1996, 1998, 2000, 2002, 2004;

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

- Байкальская международная школа-семинар «Методы оптимизации и их приложения», Иркутск, 1995, 2001, 2005, 2008, 2011, 2014, 2017;

- Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 1999, 2001, 2007, 2011, 2015;

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

- Всероссийская конференция «Проблемы оптимизации и их приложения», Омск, 2018;

- Всеросиийская конференции «Интеллектуализация обработки информации» (ИОИ) Пафос, Кипр, 2010, Будва, Черногория, 2012;

- Всероссийская конференция «Математические методы распознавания образов» (ММРО), Светлогорск, 2015;

- Международная конференция «Discrete Optimization and Operations Research (DOOR 2016)», Владивосток, 2016;

- Международный симпозиум по исследованию операций (OR), Германия, Брауншвайг, 1996, Йена, 1997, Карлсруэ 2006, Аугсбург, 2008;

- Конференция Европейского общества по исследованию операций (EURO), Прага, Чехия, 2007, Лиссабон, Португалия, 2010;

- Международный симпозиум по математическому программированию (ISMP), Берлин, Германия, 2012;

- Международная конференция по метаэвристикам (MIC), Сингапур, 2013;

- Международная конференция «Optimization and Applications» (OPTIMA), Петровац, Черногория, 2011, 2013, 2015, 2017;

- Международная конференция «Mathematical Optimization Theory and Operations Research (MOTOR 2019)», Екатеринбург, 2019.

Результаты диссертации докладывались на семинарах:

- «Математические модели принятия решений», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

- «Дискретные экстремальные задачи», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

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

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

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

Объем и структура диссертации. Диссертация состоит из введения, шести глав и списка литературы (216 наименований). Объем диссертации — 288 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации посвящена двухуровневым задачам размещения и ценообразования. Математические модели размещения и/или ценообразования — большая и неотъемлемая часть исследования операций и комбинаторной оптимизаци. Эта область исследований выделилась в самостоятельное направление в виде задач размещения производства (Location theory) в 70-80 годы прошлого столетия [1, 2, 3, 52, 53, 54]. В России большой вклад в эти исследования внесли В. Черенин, В. Ха-чатуров, В. Трубин, С. Лебедев, а в Институте математики Сибирского отделения Академии наук - В. Береснев, Э. Гимади, В. Дементьев, Ю.

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

Современные подходы к выбору эффективного механизма взаимодействия процессов размещения производства и ценообразования основываются на их совместном анализе в рамках одной модели [7, 8, 9, 10]. Однако для оценки качества принимаемых решений необходимо уметь адекватно оценивать и реакцию рынка, в частности, потребителей на предлагаемый вариант размещения и ценообразования. С этой целью удобно моделировать весь процесс в виде задачи двухуровневого программирования [21, 35].

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

Задача фабричного ценообразования (МР) относится, как и многие другие интересные задачи комбинаторной оптимизации, к классу труд-норешаемых задач. Рассмотрим соответствующую ей задачу оценивания ОРТмр, которая является задачей распознавания. Если к входу задачи МР присоединить целочисленный параметр к, то получим вход задачи оценивания, в которой надо определить, является ли к оптимальным значением целевой функции на множестве допустимых решений задачи МР или нет.

Список литературы диссертационного исследования доктор наук Плясунов Александр Владимирович, 2020 год

Литература

[1] Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 335 с.

[2] Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Изд-во Инст. математики, 2005. 408 с.

[3] Eiselt, H.A., Marianov, V. Foundations of Location Analysis. New York: Springer, 2011. 510 p.

[4] Панин А.А., Плясунов А.В. Задача ценообразования. Часть 1: Точные и приближенные алгоритмы решения // Дискретный анализ и исследование операций. 2012. Серия 2, Том 9, № 2. С. 31-40.

[5] Vives, X. Oligopoly pricing: old ideas and new tools. Cambridge: MIT Press, 1999.

[6] Hanjoul P., Hansen P., Peeters D. and Thisse J-F Uncapacitated plant location under alternative spatial price policies // Management Science. 1990. V. 36, No. 1. P. 41-57.

[7] Aboolian R., Berman O. and Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // Journal of the Operational Research Society. 2008. V. 59. P. 1506-1519.

[8] Aboolian R., Berman O., Krass D. Competitive facility location model with concave demand // Eur. J. Opl. Res. 2007. V. 181. P. 598-619.

[9] Dasci A., Laporte G. Location and pricing decisions of a multistore monopoly in a spatial market //J. Region Sci. 2004. V. 44. P. 489-515.

[10] Serra D. and ReVelle C. Competitive locations and pricing on networks // Geographic Anal. 1999. V. 31. P. 109-129.

11

12

13

14

15

16

17

18

19

20

21

22

23

Eiselt H.A., Laporte G. Sequential location problems // Eur. J. Oper. Res. 1996. V.96. P. 217-242.

Eiselt H.A., Laporte G., Thisse J.-F Competitive location models: a framework and bibliography // Transportat. Sci. 1993. V. 27. P. 44 -54.

Hay D.A Sequential entry and entry-deterring strategies in spatial competition // Oxford Econom. Papers. 1976. V. 28. P. 240 - 257.

Prescott E.C., Vissher M Sequential location among firms with foresight // Bell J. Econom. Papers. 1977. V. 8. P. 378 - 393.

von Stackelberg H. Marktform und Gleichgewicht. Vienna: Springer, 1934.

Kress D., Pesch E. Sequential competitive location on networks // Eur. J. Oper. Res. 2012. V. 217. P. 483 - 499.

Garcia M.D., Fernandez P., Pelegrin B On price competition in location-price models with spatially separated markets // TOP. 2004. V. 12. P. 351 - 374.

Snyder L.V. Facility location under uncertainty: a review // Journal IIE Transactions. 2006. Vol. 38. P. 547-564.

Pang J.-S. Three modeling paradigms in mathematical programming // Mathematical Programming. 2010. Vol. 125. P. 297-323.

Bard J.F. Practical bilevel optimization: algorithms and applications. Dordrecht: Kluwer Academic Publishers, 1998. 476 P.

Dempe S.J. Foundations of bilevel programming. Dordrecht: Kluwer Academ. Publishers. 2002. 309 p.

Moore J.T., Bard J.F. The mixed integer linear bilevel programming problem //Operations Research. 1990. Vol. 38(5). P. 911-921.

Панин А.А., Пащенко М.Г., Плясунов А.В. Двухуровневые модели для дискретной задачи размещения производства и ценообразования // Автоматика и телемеханика. 2014. № 4. C. 153-169.

Davydov I., Kochetov Yu., Plyasunov A On the complexity of the (r|p)-centroid problem in the plane // TOP 2013. Vol. 22, Issue 2, P. 614-623.

[25] Alekseeva E., Kochetova N., Kochetov Y., Plyasunov A. Heuristic and exact methods for the discrete (r|p)-centroid problem // Lecture Notes in Computer Science. Springer, Heidelberg (EvoCOP). 2010, Vol. 6022. P. 11-22.

[26] Alekseeva E., Kochetov Y., Plyasunov A. An exact method for the discrete (r|p)-centroid problem // Journal of Global Optimization. 2015. Vol. 63, Issue 3. P. 445-460.

[27] Quiggin J. Risk, PPPs and the public sector comparator // Australian Accounting Review. 2004. V. 14, No. 33. P. 51-61.

[28] Owen G., Merna A. The Private Finance Initiative // Engineering, Construction and Architectural Management. 1997. Vol. 4, No. 3. P. 163-177.

[29] Резниченко Н. В. Модели государственно-частного партнерства // Вестн. С.-Петерб. ун-та. Сер. Менеджмент. 2010. Вып. 4. C. 63.

[30] Лавлинский С. М. Государственно-частное партнерство на сырьевой территории - экологические проблемы, модели и перспективы // Проблемы прогнозирования. 2010. № 1. С. 99-111.

[31] Лавлинский С. М., Калгина И. С. О методах оценки механизма государственно-частного партнерства в минерально-сырьевой сфере Забайкальского края // Вестник ЗабГУ. 2012. № 9(88). С. 96-102.

[32] Лавлинский С.М., Панин А.А., Плясунов А.В. Двухуровневая модель планирования государственно-частного партнерства //Автоматика и телемеханика. 2015. № 11. С. 89-103.

[33] Лавлинский С.М., Панин А.А., Плясунов А.В. Сравнение моделей планирования государственно-частного партнерства // Дискретный анализ и исследование операций. 2016. Т. 23, № 3. С. 35-60.

[34] Лавлинский С.М., Панин А.А., Плясунов А.В. Модели Штакель-берга в территориальном планировании //Автоматика и телемеханика. 2019. № 2. С. 111-124.

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

[36] Иваненко Д.С., Плясунов А. В. О сводимости задачи двухуровневого программирования к задаче векторной оптимизации // Труды ИВМиМГ СО РАН. Сер. Информатика. Новосибирск, 2005. Вып. 5. С. 132-143.

[37] Губарева А. В. Панин А. А., Плясунов А. В., Сом Л. В. О трехуровневой задаче конкурентного ценообразования с равномерной и фабричной ценовыми стратегиями // Дискретный анализ и исследование операций. 2019. Т. 26, № 1. С. 55-73.

[38] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. — Berlin: Springer-Verlag, 1999.

[39] Kochetov Yu., Ivanenko D. Computationally difficult instances for the uncapacitated facility location problem. In: T. Ibaraki et al. (eds.) Metaheuristics: progress as real solvers. Springer, 2005, P. 351-367.

[40] Кочетов Ю.А., Пащенко М.Г., Плясунов А.В. О сложности локального поиска в задаче о р-медиане // Дискрет. анализ и исслед. операций. Сер. 2. — 2005. — Т. 12, № 2. — С. 44-71.

[41] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the р-median problem // European J. Oper. Res. — 2008. — V. 191 — P.736-752.

[42] Кононов А. В. Панин А. А., Плясунов А. В. Двухуровневая модель конкурентного размещения и ценообразования с неравномерным разделом спроса // Дискретный анализ и исследование операций. 2019. Т. 26, № 3. С. 27-45.

[43] Панин, А., Плясунов, А. Задача ценообразования. Часть 2: Вычислительная сложность // Дискретный анализ и исследование операций. 2012. Т. 19, № 6. С. 56-71.

[44] Панин А. А., Плясунов А. В. О сложности двухуровневых задач размещения и ценообразования // Дискретный анализ и исследование операций. 2014. Т. 21, № 5. С. 54-66.

[45] Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэври-стик для решения двухуровневой задачи размещения предприятий

и фабричного ценообразования // Дискретный анализ и исследование операций. 2015. Т. 22, № 3. C. 36-54.

[46] Cvokic D., Kochetov Yu., Plyasunov A. The Existence of Equilibria in the Leader-Follower Hub Location and Pricing Problem // In: Doerner K., Ljubic I., Pflug G., Tragler G. (eds). Operations Research Proceedings 2015. Springer. 2015. P. 539-544.

[47] Cvokic D., Kochetov Yu., Plyasunov A. A leader-follower hub location problem under fixed markups // In: Kochetov Y., Khachay M., Beresnev V., Nurminski E., Pardalos P. (eds) Discrete Optimization and Operations Research. DOOR 2016. Lecture Notes in Computer Science. Springer, Cham. 2016, Vol. 9869. P. 331-344.

[48] Cvokic D., Kochetov Yu., Plyasunov A. and Savic A. A (r|p)hub-centroid problem under the price war // Lecture Notes in Computer Science. 2019. Vol. 11548. P. 126-139.

[49] Иваненко Д.С., Плясунов А.В. О сводимости задачи двухуровневого программирования к задаче векторной оптимизации // Дискретный анализ и исследование операций. Серия 2. 2007. Т.14, № 1. С. 72-99.

[50] Lavlinskii S., Panin A., Plyasunov A. Public-private partnership models with tax incentives: numerical analysis of solutions // Communications in Computer and Information Science. 2018. Vol. 871. P. 220-234.

[51] Lavlinskii S., Panin A., Plyasunov A. Stackelberg model and public-private partnerships in the natural resources sector of Russia // Lecture Notes in Computer Science. 2019. Vol. 11548. P. 201-215.

[52] Drezner Z. (Ed.) Facility Location. A Survey of Applications and Methods. Springer, 1995. 571 p.

[53] Eiselt H. A., Sandblom C. -L. Decision Analysis, Location Models, and Scheduling Problems. Springer, 2004. 380 p.

[54] Drenzer Z., Eiselt H.A. Consumers in competitive location models // Z. Drenzer, H. Hamacher (Eds.) Facility Location. Applicatios and Theory. Springer, 2004. P. 151-178.

[55] Roboredo M.C., Pessoa A.A. A branch-and-cut algorithm for the discrete (r|p)-centroid problem // European J. Oper. Res. 2013. V. 224, No. 1. P. 101-109.

[56] Carrizosa, E., Davydov, I. and Kochetov Yu. A new alternating heuristic for the (r|p)-centroid problem on the plane // Oper. Res. Proc. 2011. Springer, 2012. P. 275 - 280.

[57] Hekmatfar M, Pishvaee M (2009) Hub Location Problem, In: Zanjirani R (ed), Hekmatfar M (ed) Facility Location, Physica-Verlag HD, Heidelberg, pp 243-270.

[58] Serra D, ReVelle Ch (1999) Competitive Location and Pricing on Networks. Geographical Analysis 31(2):109-129.

[59] Bouhtou M., Grigoriev A., Van Der Kraaij A.F., Van Hoesel S., Spieksma F., Uetz M. Pricing bridges to cross a river // Naval Research Logistics. 2007. V. 54, No. 4. P. 411-420.

[60] Grigoriev A., van Loon J., Sviridenko M., Uetz M., and Vredeveld T. Optimal Bundle Pricing with Monotonicity Constraint // Operations Research Letters. 2008. V. 36, No.5. P. 609-614.

[61] Панин А.А Генетический алгоритм для одной задачи ценообразования // Труды ИВМиМГ СО РАН серия Информатика. 2009. Вып. 9. С. 190-196.

[62] Плясунов А.В О вычислительных возможностях метаэвристик // Материалы Российской конференции "Дискретная оптимизация и исследование операций Владивосток, 7-14 сентября 2007. Новосибирск: Издательство Института математики, 2007. С. 284-285.

[63] Alekseeva E., Kochetova N., Kochetov Y., Plyasunov A. A hybrid memetic algorithm for the competitive p-median problem // Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, Russia, June 3 - 5, 2009. - P. 1516-1520.

[64] Rebeiro C.C., Hansen P. Essays and surveys in metaheuristics. Boston: Kluwer Academic Publishers, 2002. P. 651.

[65] Chandru V., Hooker J.N. Optimization Methods for Logical Inference // Wiley-Interscience, 1999.

[66] Dechter R. Constraint Processing // Morgan Kaufmann, 2003. 480 P.

[67] van Hentenryck P., Milano M. Hybrid Optimization // Springer Optimization and Its Applications. 2011. Vol. 45. P. 570.

[68] Hooker J.N Integrated Methods for Optimization // Springer, 2007. 486 P.

[69] Hooker J.N Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction // Wiley-Interscience, 2000.

[70] Lodi A., Milano M., Toth P Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems // LNCS. 2010. Vol. 6140. P. 369.

[71] Marriott K., Stuckey P Programming with Constraints: An Introduction // The MIT Press, 1998.

[72] Magnanti T.L., Wong R.D Decomposition methods for facility location problems // Mirchandani P.D., Francis R.L. (Eds). Discrete Location Theory. - Wiley and Sons, 1990. - P. 439-478.

[73] Gote G., Laughton M.A Large scale mixed integer programming: Benders-type heuristics // European Journal of Operational Research. 1984. Vol. 16. P. 327-333.

[74] McDaniel D., Devine M A modified Benders partitioning algoritm for mixed integer programming // Management Science. 1977. Vol. 24. P. 312-319.

[75] Vanderbeck F., Wolsey L.A. Reformulation and decomposition of integer programs // Monreal, 2009. CORE DP Vol. 16.

[76] Плясунов А. Гибридные методы решения сложных комбинаторных задач, использующие декомпозицию // Сборник докладов 8-й международной конференции "Интеллектуальная обработка информации Республика Кипр, г. Пафос, 17-24 октября, 2010. - С. 286-289.

[77] Дементьев В.Т., Шамардин Ю.В. Задача о выборе цен на продукцию при условии обязательного удовлетворения спроса // Дискретный анализ и исследование операций. 2002. Серия 2. Том 9, № 2. С. 31-40.

[78] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 С.

[79] Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир. 1991. Т. 1. 360 С.

[80] Attallah M. Algorithms and theory of computation handbook. Boca Raton: CRC Press LLC, 1999. 1312 P.

[81] Leggette E.W., Jr., Moore D.J. Optimization problems and the polynomial hierarchy // Theoretical Computer Science. 1981. Vol. 15, № 3. P. 279-289.

[82] Geoffrion A.V. Generalized Benders decomposition // Journal of Optimization Theory and Application. 1972. Vol. 10, No. 4. P. 237260.

[83] Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.

[84] Hotelling H. Stability in competition // Econom. J. 1929. V. 39. P. 41 - 57.

[85] Lederer Ph. J. and Thisse J.-F. Competitive location on network under delivered pricing // Oper. Res. Lett. 1990. V. 9, No. 3, 147-153.

[86] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem // Electronic Notes in Discrete Mathematics. 2012. Vol. 39. P. 29-34.

[87] Davydov, I., Kochetov, Yu., Mladenovic N., Urosevic D. Fast metaheuristic for the discrete (r|p)-the centroid problem, Automation and Remote Control. (2014), (in press).

[88] Kochetov Yu.A., Plyasunov A.V. Genetic local search for the graph partitioning problem under cardinality constraints // Computational Mathematics and Mathematical Physics. 2012. Vol. 52, N 1. P. 157167.

[89] Kochetov Y., Alekseeva E., Levanova T., Loresh M. Large neighborhood local search for the р-median problem // Yugoslav Journal of Oper. Res. 2005. V. 15, № 1. P. 53-63.

[90] Bazgan C., Escoffer B., and Paschos V. Th. Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness // Theoret. Comput. Sci. 2005. Vol. 339. P. 272-292.

[91] Crescenzi P., Kann V., Silvestri R., and Trevisan L. Structure in approximation classes // SIAM J. COMPUT., 1999, Vol. 28, No. 5. P. 1759-1782.

[92] Slater P.I. Maximin facility location // Journal of Research of the National Bureau of Standards. Sect. B. 1975. V.79. P. 107-115.

[93] Hakimi S. L. Locations with spatial interactions: competitive locations and games // In: Mirchandani P. B., Francis R. L. (Eds.) Discrete Location Theory. Wiley & Sons, 1990. P. 439-478.

[94] Hakimi S. L. On locating new facilities in a competitive environment // European J. Oper. Res. 1983. V. 12, N 1. P. 29-35.

[95] Давыдов И.А. Локальный поиск с запретами для дискретной задачи о (г|р)-центроиде // Дискретный анализ и исследование операций. —2012. Т. 19, № 2. С. 19-40.

[96] Kochetov Y. A. Facility location: discrete models and local search methods // In: Chvatal. V. (Ed.): Combinatorial Optimization. Methods and Applications. Amsterdam: IOS Press, 2011, P. 97-134.

[97] Alekseeva E., Kochetov Yu. Matheuristics and exact methods for the discrete (r|p)-centroid problem / El-G. Talbi, L.Brotcorne (Eds.) Metaheuristics for Bi-level Optimization (Studies in Computational Intelligence). Springer, 2013. P. 189 - 219.

[98] Давыдов И.А., Кочетов Ю.А., Младенович Н., Уросевич Д. Быстрые метаэвристики для дискретной задачи о (r^-центроиде // АиТ. 2014, № 4, С. 106-119.

[99] Noltermeier H., Spoerhase J., Wirth H.C. Multiple voting location and single voting location on trees // Eur. J. Oper. Res. 2007. V. 181. P. 654 - 667.

[100] Davydov I., Kochetov Y., Carrizosa E. A local search heuristic for the (r|p)-centroid problem in the plane // Computers and Operations Research. 2014. Vol. 52, Part B. P. 334-340.

101

102

103

104

105

106

107

108

109

110

111

112

Teramoto S., Demanie E.D., Uehara R. The Voroni game on graphs and its complexity // Journal of Graph Algorithms and Applications. 2011. V.15, No.4. P. 485-501.

Hakimi S.L. On locating new facilities in a competitive environment. 1981, ISOLDE Conference, Skodsborg, Denmark.

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

Plastria F., Vanhaverbeke L. Discrete models for competitive location with foresight // Computers & Operations Research. 2008. V.35, No.3. P. 683-700.

Bauer A., Domshke W., Pesch E. Competitive location on a network // European Journal of Operational Research. 1993. V. 66. P. 372--391.

Campos-Rodriguez C.M., Moreno-Perez J.A. Relaxation of the condorcet and simpson conditions in voting location // European J. Oper. Res. 2003. V.145. P. 673-683.

Spoerhase, J., Wirth, H. (r,p)-centroid problems on paths and trees // J. Theor. Comp. Sci. Archive. 2009. 410, 47-49, 5128-5137.

Spoerhase J., Wirth H.C. (r; p)-Centroid problems on paths and trees. Tech. Report 441, Inst. Comp. Science, University of Wiirzburg, 2008.

Megiddo N., Supowit K. On the complexity of some common geometric location problems // SIAM J. Comput. 1984. V. 13, No. 1. P. 182-196.

Hansen P., Labbe M. Algorithms for voting and competitive location on a network // Transportation Science. 1988. 22(4), 278-288.

Drezner Z. Competitive location strategies for two facilities // Regional Science and Urban Economics. 1982. V.12. P. 485-493.

Carrizosa E., Conde E., Munoz-Marquez M., Puerto J. Simpson points in planar problems with locational constraints. The round-norm case // Mathematics of Operations Research. 1997. V.22. P. 276-290.

[113] Carrizosa E., Conde E., Munoz-Marquez M., Puerto J. Simpson points in planar problems with locational constraints. The polyhedral-gauge case // Mathematics of Operations Research. 1997. V.22. P. 291-300.

[114] Banik A., Das S., Maheshwari A., Smid M. The discrete voronoi game in a simple polygon, in: D.-Z. Du, G. Zhang (Eds.) Computing and Combinatorics, COCOON, LNCS 7936. 2013, Springer, Berlin. P. 197207.

[115] Campos-Rodriguez C.M., Santos-Penate D.R., Moreno-Perez J.A. An exact procedure and LP formulations for the leader-follower location problem // TOP, 18 (1), 97-121 (2010).

[116] Davydov I., Kochetov Y., Carrizosa E. VNS heuristic for the (r\p)-centroid problem on the plane // Electronic Notes in Discrete Mathematics. 2012. Vol. 39. P. 5-12.

[117] Schaefer M., Umans C. Completeness in the polynomial-time Hierarchy: Part I: A compendium // ACM Sigact News, Complexity Theory Column. 2002. V. 37, No. 33. P. 32-49.

[118] Ghosh A., Craig C. A Location allocation model for facility planning in a competitive environment // Geographical Analysis. 1984. V. 16. P. 39-51.

[119] Benati S., Laporte G. Tabu search algorithms for the (r\Xp)-medianoid and (r\p)-centroid problems // Location Science. 1994. V. 2. P. 193204.

[120] Serra D., ReVelle C. Market capture by two competitors: the preemptive capture problem //J. Reg. Sci. 1994. V. 34, No. 4. P. 549-561.

[121] Campos-Rodriguez C.M., Moreno Perez J.A., Santos-Penate D.R. Particle swarm optimization with two swarms for the discrete (r\p)-centroid problem // LNCS. 2012. V. 6927, P. 432-439.

[122] Beresnev V., Mel'nikov A.: Approximate algorithms for the competitive facility location problem //J. Appl. Indust. Math. 2011. V. 5, No. 2. P. 180-190.

[123] Resende M.G.C., Werneck R.F. A hybrid multistart heuristic for the uncapacitated facility location problem // European J. Oper. Res. 2006. V. 174, No. 1, P. 54-68.

124

125

126

127

128

129

130

131

132

133

134

135

Mirchandani P. B., Francis R. L. (eds.) Discrete Location Theory, Wiley & Sons, 1990. P. 439-478.

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

Campos-Rodriguez C.M., Moreno Perez J.A. Multiple voting location problems // European J. Oper. Res. 2008. V. 191. P. 437-453.

Hansen P., Mladenovic N. Variable neighborhood search: principles and applications // European J. Oper. Res. 2001. V. 130. P. 449-467.

Talbi E.G. A taxonomy of hybrid metaheuristics // Journal of Heuristics. 2002. V. 8. P. 541-564.

Talbi E-G. Metaheuristics: from design to implementation. Wiley, 2009. 500 P.

Alekseeva, E., Beresnev, V., Kochetov, Y. et al. Benchmark library: Discrete Location Problems (Russia), http : //math.nsc.ru/AP/benchmarks/english.html.

Kücükaudin H., Aras N., Altinel I.K. Competitive facility location problem with attractiveness adjustment of the follower. A bilevel programming model and its solution // European J. Oper. Res. 2011. V. 208. P. 206-220.

Plastria F., Carrizosa E. Optimal location and design of a competitive facility // Math. Program. 2004. Ser A. V. 100. P. 247-265.

Saidani N., Chu F., Chen H. Competitive facility location and design with reactions of competitors already in the market // European J. Oper. Res. 2012. V. 219. P. 9-17.

Hamacher H.W., Nickel S. Classification of location models // Locat. Sci. 1998. V. 6. P. 229 - 242.

Plastria F. Sequential location problems // Eur. J. Oper. Res. 2001. V. 129. P. 461-470.

Aboolian R., Berman O., Krass D. Competitive facility location and design problem // Eur. J. Oper. Res. 2007. V. 182. P. 40 - 62.

[137] Береснев В. Л., Мельников А. А. Приближённые алгоритмы для задачи конкурентного размещения предприятий // Дискретн. анализ и исслед. операций. 2010. т. 17. № 6. C. 3 -- 19.

[138] Франк Р.Х Микроэкономика и поведение. М.: ИНФРА-М, 2000. 696 С.

[139] Yates, A.J. Hotelling and the New York stock exchange // Econom. Lett. 1997. V. 56. P. 107- 110.

[140] Yai, F.-C. Sequential locations in directional markets // Region. Sci. Urban Econom. 2001. V. 31. P. 535 - 546.

[141] Pelegrin B., Fernandez P., Garcia M.D., Cano S. On the location of new facilities for chain epansion under delivered pricing // Omega. 2012. V. 40. P. 149 - 158.

[142] Bhadury J., Eiselt H.A., Jaramillo J.H. An alternating heuristic for medianoid and centroid problems in the plane // Comput. Oper. Res. 2003. V. 30. P. 553 - 565.

[143] Sherali H.D., Soyster A.L. Convergence analysis and algorithmic implications of twodynamic processes toward an oligopoly — competitive fringe equilibrium set // Comput. Oper. Res. 1988. V. 15. P. 69 - 81.

[144] Алексеева Е.В., Кочетов Ю.А. Генетический локальный поиск для задачи о р-медиане с предпочтениями клиентов. // Дискрет. анализ и исслед. операций. Cер. 2. 2007. Т. 14, № 1. С. 3-31.

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

[146] Плясунов А. В. Полиномиально разрешимый класс задач двухуровневого нелинейного программирования // Дискрет. анализ и ис-след. операций. Сер. 2. 2000. Т. 7, № 2. С. 89-113.

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

[148] Guha S., Khuller S. Greedy strikes back: improved facility location algorithms. //J. Algorithms. 1999. V. 31. P. 228-248.

[149] Sridharam R. The capacitated plant location problem // European J. Oper. Res. 1995. V. 87. P. 203-213.

[150] Иваненко Д. С., Плясунов А. В. Полиномиально разрешимая задача выбора ряда изделий с частичным внешним финансированием // Математическое программирование и приложения. Екатеринбург, 2003. C. 120-121.

[151] Cornuejols G., Sridharan R., Thizy J. M. A comparison of heuristics and relaxations for the capacitated plant location problem // European J. Oper. Res. 1991. V. 50, N 3. P. 280-297.

[152] Geoffrion A. Lagrangean relaxation for integer programming // Math. Programming Study. 1974. V. 2. P. 82-114.

[153] Nemhauser G., Wolsey L. Integer and combinatorial optimization. New York: John Wiley & Sons, 1988.

[154] HirschW. M., Dantzig G. B. The fixed charge problem // Naval Res. Logist. Quart. 1968. V. 15, N 3. P. 413-424.

[155] Kochetov Yu., Ivanenko D. Computationally difficult instances for the uncapacitated facility location problem // Proceedings of the 5th Metaheuristics international conference. Kioto, 2003. P. 41.1-41.6.

[156] Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Часть I. М: МГУ, 2001. C. 87-117.

[157] Ribeiro C.C. Hansen P. (Eds.) Meta-heuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer. Acad. Publ., 1998.

[158] Dyer M.E. A O(n) algorithm for the multiple-choice knapsack linear program // Math. Programming. 1984. V.29, N.1. P. 57-63.

[159] Рапопорт Э. О. О некоторых проблемах моделирования земельной ренты в условиях многоукладной экономики // Сиб. журн. индустр. матем. 2011. Т. 14, № 2. С. 95-105.

[160] Audet C., Savard G., Zghal W New Branch-and-Cut Algorithm for Bilevel Linear Programming //J. Optim. Theory Appl. 2007. Vol. 134. P. 353-370.

[161] DeNegre S. T., Ralphs T. K A Branch-and-cut Algorithm for Integer Bilevel Linear Programs // Operations Research/Computer Science Interfaces. 2009. Vol. 47. P. 65-78.

[162] Кочетов Ю. А Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики. 2008. № 4. С. 788-807.

[163] Eggermont C.E.J., Woeginger G.J. Motion planning with pulley, rope, and baskets // Theory Comput. Syst. 2013. V. 53, No. 4. P. 569-582.

[164] Лавлинский С. М Модели индикативного планирования социально-экономического развития ресурсного региона // Новосибирск: Издательство СО РАН. 2008.

[165] Глазырина И. П., Лавлинский С. М., Калгина И. С Государственно-частное партнерство в минерально-сырьевом комплексе Забайкальского края: проблемы и перспективы // География и природные ресурсы. 2014. № 4. С. 99-105.

[166] Alumur S., Kara B. Network hub location problems: the state of the art // European journal of Operational Research. 2008. V. 190, No.1. P. 1-21.

[167] Campbell J., O'Kelly M. Twenty-five years of hub location research // Transportation Science. 2012. 46(2):153-169.

[168] Farahani R., Hekmatfar M., Arabani A., Nikbakhsh E. Hub location problems: a review of models, classification, solution techniques, and applications // Computers & Industrial Engineering. 2013. V. 64, No. 4. P. 1096-1109.

[169] Marianov V., Serra D., ReVelle Ch. Location of hubs in a competitive environment // European Journal of Operational Research. 1999. V. 114, No. 2. P. 363-371.

[170] Eiselt H., Marianov V. A conditional p-hub location problem with attraction functions // Computers & Operations Research. 2009. V. 36, No. 12. P. 3128-3135.

[171] Gelareh S., Nickel S., Pisinger D. Liner shipping hub network design in a competitive environment // Transportation Research Part E: Logistics and Transportation Review. 2010. V. 46, No. 6. P. 991-1004.

[172] Mahmutogullari I., Kara B. Hub location under competition // European Journal of Operational Research. 2016. V. 250, No. 1. P. 214-225.

[173] Sasaki M., Fukushima M. Stackelberg hub location problem // Journal of the Operations Research Society of Japan. 2001. V. 44, No. 4. P. 390-405.

[174] Adler N., Smilowitz K. Hub-and-spoke network alliances and mergers: price-location competition in the airline industry // Transportation Research. Part B. 2007. V. 41, No. 4. P. 394-409.

[175] Sasaki M., Campbell J.F., Ernst A.T., Krishnamoorthy M. Hub Arc Location with Competition // Technical Report of the Nanzan Academic Society Information Sciences and Engineering. 2009.

[176] de Menzes A., Vieira J. Willingness to pay for airline services attributes: evidence from a stated preferences choice game // European Transport. 2008. V. 39. P. 1-13.

[177] Lambrecht A., Seim K., Vilcassim N., Cheema A., Chen Y., Crawford G., Hosanagar K., Raghuram I., Koenigsberg O., Lee R., Miravete E., Sahin O. Price discrimination in service industries // Mark Lett. 2012. V. 23. P. 423-438.

[178] Friesz T., Tobin R., Miller T. Existence theory for spatially competitive network facility location models // Annals of Operations Research. 1989. V. 18. P. 267-276.

[179] Labbe M., Hakimi S. Market and Location Equilibrium of Two Competitors // Operations Research. 1991. V. 39, No. 5. P. 749-756.

[180] Miller T., Tobin R., Friesz T. Stackelberg games on a network with cournot-nash oligopolistic competitors // Journal of Regional Science. 1991. V. 31, No. 4. P. 435-454.

[181] Pelegrin-Pelegrin B., Dorta-Gonzalez P., Fernandez-Hernandez P. Finding location equilibria for competing firms under delivered pricing // Journal of the Operational Research Society. 2011. V. 62. P. 729-741.

[182] Kiigukaydin H., Aras N., Kuban Altinel I. A leader-follower game in competitive facility location // Computers & Operations Research. 2012. V. 39, No. 2. P. 437-448.

[183] Fernández J., Salhi S., Toth B. Location equilibria for continuous competitive facility location problem under delivered pricing // Computers & Operations Research. 2014. V. 41. P. 185-195.

[184] O'Kelly M.E., Luna H.P.L., de Camargo R.S., Miranda G. Hub location problems with price sensitive demands // Networks and Spatial Economics. 2015. V. 15, No. 4. P. 917-945.

[185] Lüer-Villagra A., Marianov V. A competitive hub location and pricing problem // European Journal of Operational Research. 2013. V. 231, No. 3. P. 734-744.

[186] Bierlaire M. Discrete choice models. In: Labbe M. (ed), Laporte G. (ed), Tanczos K. (ed), Toing Ph. (ed) Operations Research and Decision Aid Methodologies in Traffic and Transportation Management, Berlin Heidelberg: Springer, 1998. P. 203-227.

[187] Ortúzar J., Willumsen L. Modelling Trasnport, 4th ed. West Sussex: Wiley-Blackwell, UK, 2011.

[188] Haase K., Müller S. A comparison of linear reformulations for multinomial logit choice probabilities in facility location models // European Journal of Operational Research. 2014. V. 232. P. 689-691.

[189] Alekseeva E., Kochetov Yu. Matheuristics and Exact Methods for the Discrete (r|p)-Centroid Problem In: Talbi El-Ghazali (ed) Metaheuristics for Bi-level Optimization. Berlin Heidelberg: SpringerVerlag, 2013, P. 189-219.

[190] Sasaki M. Hub network design model in a competitive environment with flow threshold // Journal of the Operations Research Society of Japan. 2005. V. 48. P. 158-71.

[191] Corless R.M., Gonnet G.H., Hare D.E., Jeffrey D.J., Knuth D.E. On the Lambert W function. // Advances Computational Maths. 1996. V. 5, P. 329-359.

[192] Антипин А.С. Равновесное программирование: методы градиентного типа // Автоматика и телемеханика. 1997. N 8. С. 125-137.

[193] Зоркальцев В.И., Хамисов О.В. Равновесные модели в экономике и энергетике. Новосибирск: Наука, 2006.

194

195

196

197

198

199

200

201

202

203

204

Antipin A.S. From optima to equilibria // Dynamics of non-homogeneous systems. Proceedings of ISA RAS, 2000, v. 3, P. 35-64.

Плясунов А. В. Задача двухуровневого линейного программирования с многовариантным ранцем на нижнем уровне // Дискрет. анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 1. С. 44-52.

Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач М.: Наука. Главная редакция физико-математической литературы, 1982.

Ehrgott M. A multicriteria optimization Berlin - Heidelberg: Springer, 2005.

Bard J. Optimality conditions for the bilevel programming problem // Naval Research Logistics Quarterly. 1984. Vol. 31, N 1. P. 13-26.

Unlii G. A linear bilevel programming algorithm based on bicriteria programming // Computers and Operations Research. 1987. Vol. 14, N 2. P. 173-179.

Wen U., Hsu S. A note on a linear bilevel programming algorithm based on bicriteria programming // Computers and Operations Research.

1989. Vol. 16, N 1. P. 79-83.

Candler W., A linear bilevel programming algorithm: a comment // Computers and Operations Research. 1988. Vol. 15, N 3. P. 297-298.

Clarke P., Westerberg A. A Note on the Optimality Conditions for the Bilevel Programming Problem // Naval Research Logistics. 1988. Vol. 35, N 5. P. 413-418.

Haurie A., Savard G., White D. A note on an efficient point algorithm for a linear two-stage optimization problem // Operations Research.

1990. Vol. 38, N 3. P. 553-555.

Marcotte P., Savard G. A note on the pareto optimality of solutions to the linear bilevel programming problem // Computers and Operations Research. 1991. Vol. 18, N 4. P. 355-359.

Fiilop J. On the equivalence between a linear bilevel programming problem and linear potimization over the efficient set Technical report WP 93-1, Laboratory of operations research and decision systems,

Computer and automation Institute, Hungarian academy of sciences, 1993.

[206] Fliege J., Vicente L.N. A multicriteria approach to bilevel optimization Preprint Number 03-08, Pre-Publicacoes do Departamento de matemútica, Universidade de Coimbra, 2003.

[207] Goh,C. J., YangX.Q. A nonlinear Lagrangian theory for nonconvex optimization //J. Optimization Theory and Applications. 2001. V. 109, N 1. P. 99-121.

[208] Dempe, S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints // Optimization, 2003. Vol. 52, P. 333-359.

[209] Мальцев А. И. Алгебраические системы М.: Наука, 1970.

[210] Fliege J., Vicente L. N. Multicriteria approach to bilevel optimization // J. of Optimization Theory and Applications. 2006. V. 131, N 2. P. 209-225.

[211] Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения) М.: Наука. Главная редакция физико-математической литературы, 1969.

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

[213] Емеличев В.А., Ковалёв М.М., Кравцов М.К. Многогранники, графы, оптимизация. К. - М.: Наука. Главная редакция физико-математической литературы, 1981.

[214] Rubinov A.M., Gasimov R.N. Scalarization and nonlinear scalar duality for vector optimization with preferences that are not necessarily a pre-order relation // Journal of Global Optimization. 2004. V. 29, N 4. P. 455-477.

[215] Ruuska S., Miettinen K. and Wiecek M.M. Connections between singlelevel and bilevel multiobjective optimization // Journal of Optimization Theory and Applications. 2012. V. 153, No. 1. P. 60-74.

[216] Pieume C.O., Fotso L.P., Siarry P. Solving bilevel programming problems with multicriteria optimization techniques // OPSEARCH. 2009. V. 46, Issue 2. P. 169-183.