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

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

РУБАНОВА Наталия Алексеевна

□03055055

ИССЛЕДОВАНИЕ ЗАДАЧ РАЗМЕЩЕНИЯ ПРЕДПРИЯТИЙ И РАЗРАБОТКА ДЕКОМПОЗИЦИОННЫХ АЛГОРИТМОВ ИХ РЕШЕНИЯ

05.13.18 —математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени

кандидата физико-математических наук

Екатеринбург - 2007

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

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

наук, профессор

Колоколов Александр Александрович

Официальные оппоненты: доктор физико-математических

наук, профессор Мазуров Владимир Данилович, кандидат физико-математических наук, доцент

Симанчев Руслан Юрьевич

Ведущая организация: Институт автоматики и процессов

управления ДВО РАН

Защита состоится 17 января 2007 г. в 15:00 часов на заседании диссертационного совета К212.286.01 по присуждению ученой степени кандидата физико-математических наук при Уральском государственном университете им. A.M. Горького по адресу: 620083, Екатеринбург, пр. Ленина, 51, комн. 248.

С диссертацией можно ознакомиться в библиотеке Уральского государственного университета им. A.M. Горького.

Автореферат разослан 2006 г.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Задачи оптимального размещения могут быть описаны в терминах дискретной оптимизации и образуют важное направление исследований в этой области, которое включает в себя изучение структуры и вычислительной сложности задач, разработку и анализ точных и приближенных методов их решения, выделение полиномиально разрешимых случаев, построение семейств "трудных" задач для определенных алгоритмов [1, 4, 7,19, 20, 21]. Значительное число исследований посвящено простейшей задаче размещения и различным ее обобщениям, в том числе двухуровневой задаче размещения [3, 6, 11, 13, 22].

Рассматриваемые задачи относятся к классу NP-трудных проблем дискретной оптимизации [22], вследствие чего особую важность приобретает создание специальных алгоритмов их решения. Во многих случаях для разработки таких алгоритмов используются модели и методы целочисленного программирования (ЦП). Среди известных подходов к решению указанных задач размещения выделяются метод ветвей и границ, алгоритмы отсечения, метод направленного перебора и т.д. Для решения частично целочисленных задач широкое распространение получил метод декомпозиции Бендерса [12, 17, 18, 23], который пока еще недостаточно изучен с теоретической точки зрения. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач и другие. При построении отсечений Бендерса оптимальные значения двойственных переменных определяются неоднозначно, что может существенным образом повлиять на эффективность алгоритмов. Исследования в этом направлени позволяют разрабатывать способы получения более сильных отсечений [20].

Для исследования задач целочисленного программирования, разработки и анализа алгоритмов A.A. Колоколовым был предложен подход, основанный на регулярных разбиениях, наиболее изученным из которых к настоящему времени является L-разбиение [9]. С помощью L-разбиения изучается сложность решения задач ЦП и их структура, вводятся новые классы отсечений, строятся оценки числа итераций различных алгорит-

мои, исследуется устойчивость задач и алгоритмов, разрабатываются новые алгоритмы [2, 8, 10]. Указанный подход оказался достаточно эффективным и для задач оптимального размещения [7, 11].

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на Меж-

дународной научно-методической конференции "Математика и пузе" (Великий Новгород, 2000), Международной конференции "XII Meeting of EURO Working Group on Location Analysis" (Барселона, 2000), конференции с международным участием "Новые технологии ж/д транспорту" (Омск, 2000), XII Международной Байкальской конференции "Методы оптимизации и их приложения" (Иркутск, 2001), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международной конференции "European Chapter on Combinatorial Optimization ECCO XVIII" (Минск, 2005), на научных семииарах Омского филиала Института математики им C.J1. Соболева СО РАН и Института математики и механики УрО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [24-35].

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

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

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

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

В п. 1.1 содержатся комбинаторные и целочисленные постановки ряда задач размещения производства, при этом особое внимание уделяется простейшей задаче размещения (ПЗР) и различным ее обобщениям.

Рассматривается следующая постановка ПЗР. Дано конечное множество I = {1,..., п} пунктов возможного размещения предприятий, производящих некоторый продукт в неограниченном количестве, и список клиентов J = {l,...,m}. Известны стоимости размещения предприятий с-1 в указанных пунктах г Е I и затраты Сц на удовлетворение спроса каждого клиента j G J предприятием, расположенным в пункте г. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные затраты на размещение предприятий и обслуживание клиентов были минимальны. Модель целочисленного линейного программирова-

ния (ЦЛП) для ПЗР имеет вид:

(1) (2) (3)

iel iel jeJ

Xij ^ Xiji 2 iE /, J £ J,

iel

zit Xij G {0,1}, iel, j £ J,

где Хц = 1, если клиент прикрепляется к г-му пункту и 0 - в противном случае; 2^ = 1, если предприятие г открыто и 0 - в противном случае. •

К числу задач размещения производства относятся также р-простейшая задача размещения, р-активная простейшая задача размещения, задача о р-медиане, задача размещения с ограничениями на объемы производства, двухуровневая задача размещения и др [1, 4, 6, 20].

Двухуровневая задача размещения (ДЗР) состоит в следующем. Производитель некоторого продукта стремится разместить свои предприятия в ряде пунктов таким образом, чтобы, минимизировать суммарные затраты, складывающиеся из затрат с? на размещение предприятия в г-м пункте, а также затрат су на обслуживание j-гo клиента предприятием, расположенным в г-м пункте, г 6 I,] £ J. В свою очередь каждый клиент ] этого производителя выбирает один из предложенных пунктов г, в котором величина его затрат на обслуживание минимальна.

Обозначим г = (г,-), х — (сс;;'), г е I, ] 6 3. Пусть = 1, если предприятие в г-м пункте входит в число открытых, и .г* = 0 в противном случае; жу = 1, если клиент обслуживается предприятием, расположенным в г-м пункте, и хц = 0 в противном случае. Тогда модель целочисленного линейного программирования для ДЗР имеет вид:

F(z, х) = Y, c°izi + Л Л CijXij min

(4)

iel ieljeJ

при условиях

zi e {0,i},t6 /,2^0,

где x - оптимальное решение задачи:

Y, dijXij -» min ieljeJ

при условиях

(6)

Y,Xij - 1, Xij < Zi, Xij € {0,1}, i 6 I,j e J. iel

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

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

Глава & посвящена исследованию простейшей задачи размещения.

В п. 2.1 излагается подход к анализу и решению задач ЦП, основанный на разбиениях пространства Яп на классы эквивалентности, называемые Ь-классами.

Пусть х,у 6 Нп и х у у. Будем говорить, что точки хну отделимы, если найдется л 6 для которого х У г У у. Точка 2 называется отделяющей. Если а; и у не являются отделимыми, то они считаются ¿-эквивалентными.

Это отношение разбивает любое множество I С Д" на непересекающиеся Ь-классы. Соответствующее фактор-множество Х/Ь называется Ь-разбиением множества X. Каждая точка я е X С образует отдельный класс, остальные классы разбиения состоят только из нецелочисленных точек и называются дробными.

Для частично целочисленных задач, к которым можно отнести и ПЗР, по аналогии с ¿-разбиением введено Ьк-разбиение (где к - число целочисленных переменных задачи, к < п) [8]. Пусть х е В.п. Обозначим хк- вектор, составленный из первых к координат вектора х. Векторы х,у е Яп (хк у ук) являются ¿¿-эквивалентными, если не существует отделяющей их точки г е Zn^k такой, что хк У гк У ук . Здесь Е'1,к- множество всех тг-мерных векторов, у которых первые к координат целые.

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

Рассмотрим лексикографический вариант модели (1)-(3). Введем переменную ¿о и ограничение

г0 ~ Е СуЯу = 0. (8)

Упорядочим переменные задачи, входящие в соотношения (2), следующим образом:

Соответствующий такому порядку переменных выпуклый многогранник,

заданный ограничениями (2),(8) и

О < < 1, Хц >0, г е е (9)

обозначим П. Тогда задача (1)-(3) может быть записана в лексикографической постановке:

найти г* = 1ехтт(£1 П Еы+г),

где? N = п(тп + 1). При этом оптимальное значение переменной г0 равно оптимальному значению Р* целевой функции Г(г,х) задачи (1)-(3). Важную роль при исследовании задачи и алгоритмов ее решения играет дробное накрытие:

П, = {х е 0,-.х-<г для всех г е (П П

Известно [21], что при £ Z, г £ 1,з 6 J для любых фикси-

рованных целых г2,..., гп в многограннике Г2 всегда найдется точка {го,г1, ...,гп,хп,х12, ...,Х1т, ...,х„1,х„2, —хпт), у которой хц бИ, ¿6/, 1 £ 3. Причем значения переменных £ £ 7 легко определяются аналитически: в каждом столбце у матрицы (су) находится элемент Су- = шгп{су : г^ = 1}. В случае, когда таких элементов несколько, выбирается любой из них. Соответствующая первхменная хц полагается равной 1, остальные х= 0.

Пусть к = п + 1. Мощность множества С1+/Ьк, называемого ¿^-накрытием задачи, может оказать существенное влияние на процесс решения задачи. Поэтому представляет интерес изучение ¿¿¿-структуры множества П».

Рассмотрим задачу размещения (1)-(3), у которой т = п > 3. Введем целочисленную константу М > 4 и определим коэффициенты задачи следующим образом:

с? = М, ге I, ( М 1 ... 1 \ 1 М ... 1

С =

\

(10)

1 1 ... м #

Теорема 2.1 Если коэффициенты простейшей задачи размещения удовлетворяют условиям (10), то справедлива оценка (^ - 2)(п - 1) < \П*/Ьк\ < М(п - 2) - (п - 3).

Оценки, полученные в теореме 2.1 являются линейными относительно входных параметров М и п. Мощность ¿¿—накрытия задач этого семейства возрастает с увеличением коэффициентов целевой функции. Вместе

с тем интересно построить примеры ПЗР, мощность Ьк~накрытий которых экспоненциально зависит от размерности задачи.

Рассмотрим для этого ПЗР (1 )-(3), у которой |/| = п + р, |7| = п, где Р > 1, Р € 2. Введем целочисленную константу М > 5 и определим коэффициенты задачи следующим образом:

О, если г < р, М, иначе,

I Си с12 с13 ... с1п \

С =

Ср1 Ср 2 СрЗ

М 1 1

1 М 1

1 1 1

1 1

м

(И)

где су > М, при г — 1, е 3.

Теорема 2.2 Если коэффициенты простейшей задачи размещения удовлетворяют условиям (11)1 то справедлива оценка \^/Ьк\ > (2Р — 1)(М — 4)(п — 2).

В п. 2.3 излагаются алгоритмы перебора ¿-классов и декомпозиции Бендерса для простейшей задачи размещения.

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

При фиксированном производственном плане ¿ь ..., ¿„ получается следующая задача прикрепления клиентов Т(2)-.

ЕЕ

¿е/j£J

тт

при условиях

Е Яу = 1, з е Л

¿е/

О < хц <ги г е I, ] е 7. Двойственная к Т(г) задача О(г) имеет вид:

Е из - Е Е

¿6/ j€J

тах

при условиях

Щ - гиу < сц, г € I,3 е ./, Щ] > 0, г £ ^ 6 .7.

Обозначим /(г) = ¡(г,х{г)), где я (.г) - оптимальное решение задачи

Т(г), начальное значение рекорда целевой функции задачи. Введем

множество Г = {г : Е ^ > 1, 0 < ^ < 1,1 € /} и опишем общую схему ¿6/

рассматриваемых нами декомпозиционных алгоритмов.

Процесс. Т> Положим Г« = Г, = +оо .

Итерация к, к > 1

Шаг 1. Ищем некоторый производственный план € Г^. Если такого плана не существует, то процесс завершается. План, на котором достигается рекорд р(к~г\ является оптимальным. В противном случае переходим на шаг 2.

Шаг 2. Решая задачу прикрепления клиентов при фиксированном находим оптимальное решение х^. Вычисляем рекорд

Шаг 3. Строим по некоторому правилу линейное неравенство (отсечение):

Л + + (12)

Добавляем неравенство (12) к системе ограничений многогранника Г^ и, обозначив получившуюся область через переходим к сле-

дующей итерации (на шаг 1).

Будем предполагать, что отсечения (12) в процессе Т> обладают следующими свойствами:

a) точка г^ не удовлетворяет неравенству (12),

b) отсечение (12) не исключает никакую целочисленную точку г1 е Г«, для которой /(г') <

Свойство "а" позволяет гарантировать конечность процесса V, а свойство "Ь"~ оптимальность найденного им решения. В качестве неравенств

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

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

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

Отсечение Бендерса для ПЗР имеет вид:

аз)

¿6/ зез

Здесь г б /, j £ J - оптимальные значения переменных задачи

на к-й итерации процесса Т>. В общем случае оптимальное решение задачи -О(г^) не единственно, поэтому по точке г^ может быть построено несколько различных отсечений.

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

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

Рассмотрены два способа вычисления оптимальных значений двойственных переменных.

Первый способ:

= тт{с^- : г ё 1 £ (ЛйЛ

Второй способ:

иФ = пип{су : 4к) = 1. * е 3 е ^

= ге/, Л (15)

|'де ij = а^тт{су : г 6 /Р'}, 3 € 3- Формулы используются, если

> 2. В случае, когда = 1, оптимальные значения двойственных переменных вычисляются по формулам (14).

Обозначим через Т> процесс £>, в котором производственные планы генерируются в порядке лексикографического возрастания, начиная с лексикографически минимального плана г^ с координатами г!1' = 0,..., = = 1, а отсечения (13) строятся с использо-

ванием оценок (14).

Теорема 2.4 При решении процессом V простейшей задачи размещения, коэффициенты которой удовлетворяют условиям (11), будет построено не более п отсечений.

При этом глубина таких отсечений не менее, чем 2П_1.

Выберем М > 2 и рассмотрим ПЗР, у которой гг = т, а коэффициенты имеют вид :

с? = 1, г € ( I М ...

V М М ...

Обозначим /0 = {г £ I : = 0}, Д = {г € / : ^ = 1}. Если отсечение (13) строится по плану на котором достигается рекордное значение целевой функции, то оно будет выглядеть следующим образом:

Е(2- + £ * < \1к,\ ~ 1.

Так как 2 — М < 0, то оно отсекает только план а значит его глубина равна 1. При М — 3 оно по виду напоминает вполне регулярные отсечения для задач булева программирования [9].

Рассмотрим процесс V решения задачи семейства (16) с использованием двойственных оценок (15). Если на плане ¿^ достигается рекорд целевой функции и > 2, то отсечение Бендерса будет иметь следующий вид:

2>>1Л(к)1 + 1-

¿е/

Очевидно, что оно отсекает все планы, у которых |/1| <

Таким образом, установлено, что выбор оптимальных значений двойственных оценок может оказывать существенное влияние на глубину отсечений Бендерса и что глубина отсечений для ПЗР может принимать значения от 1 до а, где а > 2П~1.

М \ М

1 >

(16)

Основные результаты главы приводятся в работах [24,25,28-30,35|.. В третьей главе предлагаются и исследуются декомпозиционные алгоритмы для двухуровневой задачи размещения (ДЗР).

В п. 3.1 содержится краткий обзор задач двухуровнего программирования. В и. 3.2 рассмотрено сведение двухуровневой задачи размещения к одноуровневой задаче ЦЛП путем добавления линейных неравенств. В |б| показана эквивалентность ДЗР следующей одноуровневой задаче/.

х) = £ + £ £ пип

¿е/

при условиях

2» е {0, О,

< Хц + £ *к, г £ 1,3 е

кеБц

£ х^ = 1, Хг, < х^ £ {0,1), г £ 1,з £

ш

где Бц = {к £ I : ¿у < г £ ё / Предполагается, что Ф йц для всех г ф к,] £ то есть выбор каждого потребителя однозначен. Декомпозиционные алгоритмы решения полученной одноуровневой задачи, аналогичные алгоритмам для ПЗР, предлагаются в п. 3.3. П. 3.4 посвящен оценкам числа итераций указанных алгоритмов. Отсечение Бендерса для одноуровневой задачи, эквивалентной ДРЗ, имеет вид:

+ £(4> - и?'))* ~ Е £ £ < Р(к) - Е у(-\ (17) (к) (к) (к)

где - оптимальные значения двойственных переменных на

к-й итерации процесса V.

Рассматривается следующий способ вычисления оптимальных значений двойственных переменных:

{к) ■ ■ _ т

у5 = тщ,£( ] £ </,

( (к) 1 и(к) _ I с^- - у) \ если Хц = 1,

4 \ 0, иначе, г £ /,; е

= 0, г £ 1,1 £ 7.

Пусть М > 2, п — т, коэффициенты ДЗР с°, с^- г 5 з б 3 удовлетворяют условиям (11), а матрица I) произвольна.

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

начиная с лексикографически минимального плана г^1' с координатами г]1' = 0,..., = 0, г^ — 1, а отсечения (17) строятся с использованием оценок (18), будет построено не более п отсечений.

Пусть тп = п и М > 2, коэффициенты ДЗР с^. г удовлетворяют условиям (16), а матрица В имеет вид:

е /, з е J

D =

п + 1 п+ 1

2 3

1

п+ 1

2 \ 3

Тогда в процессе Т> решения любой задачи такого семейства среди отсечений имеется определенное число отсечений глубины 1.

Таким образом, установлено, что глубина отсечений Бендерса для ДЗР также может изменяться от 1 до а, где а > 2п~1.

Основные результаты главы приводятся в работах [26, 27, 31, 34].

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

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

Исследовалась зависимость числа итераций алгоритмов от способа выбора оптимальных значений двойственных переменных, используемых при построении отсечений, правил выбора целочисленных точек, по которым строятся отсечения Бендерса, числа сохраняемых отсечений, упорядочения переменных, предварительного применения эвристических алгоритмов. Исследования проводились на тестовых задачах из электронной библиотеки Института математики СО РАН размерности до п = т = 150 и электронной библиотеки OR-Library [13| размерности до п — 25, т = 50, на задачах из семейств ПЗР, описанных в главе 2, в том числе обладающих мощными дробными накрытиями, с размерностью до п — т — 100, а также на задачах со случайными данными. Выполнено экспериментальное сравнение различных вариантов предлагаемых алгоритмов между собой, а также с известным пакетом CPLEX 6.5. На тестовых задачах из библиотеки ИМ СО РАН декомпозиционные

алгоритмы показали существенное преимущество по времени решения по сравнению с указанным пакетом.

В п. 4.2 исследуются разработанные нами декомпозиционные алгоритмы решения двухуровневой задачи размещения. Эксперимент проводился на случайно сгенерированных задачах размерности п = т = 30 и на задачах из семейств ДЗР, описанных в главе 3, размерности п — т = 50. Исследовалась зависимость числа итераций алгоритмов от числа сохраняемых отсечений, предварительного применения эвристических алгоритмов и других параметров.

Проведенный эксперимент позволил сделать ряд выводов, в частности:

1) построение отсечений по всем порождаемым "перспективным" производственным планам часто дает лучший результат по сравнению с использованием для этих целей только "улучшающих" планов;

2) время решения задачи декомпозиционными алгоритмами существенным образом зависит от способа упорядочения переменных;

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

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

Основные результаты главы приводятся в работе {33].

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

Список используемой литературы I

j

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

[2] Адельшин A.B. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика - 2004.-N 3- С.35-42.

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

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

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

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

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

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

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

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

[11] Колоколов A.A., Леванова Т.В. Задачи оптимального размещения предприятий и метод декомпозиции Бендерса : Учебно-методическое пособие,- Омск: ОмГУ, 2004.

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

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

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

¡15] Bonders Л. F. Partitioning procedures for solving of mixed-variables programming problems // Numer. Math., 1962,- V 4, N 3. P.238-252.

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

]17] Gascon V., Benchakroun A., Ferland J. Benders decomposition for network design problems with underlying tree structure // Investigación Operativa, 1997.-N 6 - P.165-180.

[18] Hooker J.N., Ottosson G. Logic-based Benders decomposition // Mathematical Programming Series A., 2003.-V.96, N 1,- P.33-60.

119] Kolokolov A.A. Decomposition algorithms for solving of some production-transportation problems // Triennal Symposium on Transportation Analysis II. Preprints.- Capri, 1994.-V.1.- P. 179-183.

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

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

[22] 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.

[23] Randazzo D., Luna H.P.L., Mahey P. Benders decomposition for local access network design with two technologies // Discrete Mathematics and Theoretical Computer Science, 2001.-N 4.- P.235-246. Работы автора по теме диссертации

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

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

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

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

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

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

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

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

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

[33] Рубанова Н.А. Экспериментальное исследование алгоритмов декомпозиции Бендерса для некоторых задач размещения: Препринт- Омск: ОмГУПС, 2006.

[34] Kolokolov А.А., 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.

[35] Kolokolov A.A., Kosarev N.A., Rubanova N.A. On iterations number of Benders decomposition algorithms for some facility location problems // In Proceedings of European Chapter on Combinatorial optimization ECCO-18.- Minsk, 2005.- P.27.

Типография ОмГУПСа, 2006. Тираж 120 экз. Заказ 956. 644046, г. Омск, пр. Маркса, 35.

Введение.

Глава 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. Выполнена реализация декомпозиционных алгоритмов для простейшей и двухуровневой задач размещения предприятий, проведено их экспериментальное исследование.

Заключение

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

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.