Алгоритмы локального поиска для задачи о ρ-медиане с предпочтениями клиентов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

АЛЕКСЕЕВА Екатерина Вячеславовна

АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧИ О Р-МЕДИАНЕ С ПРЕДПОЧТЕНИЯМИ КЛИЕНТОВ

специальность 01 01 09 - дискретная математика и математическая кибернетика

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

003065349

Новосибирск 2007

003065349

Работа выполнена в Институте математики имени С Л Соболева СО РАН

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

профессор В Л Береснев,

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

доцент Ю А Кочетов

Официальные оппоненты доктор технических наук,

профессор В Н Павлов,

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

доцент И Л Васильев

Ведущая организация Институт вычислительной математики

и математической геофизики СО РАН

Защита состоится "24" октября 2007 г в 17 часов на заседании диссертационного совета Д 003 015 01 в Институте математики имени С Л Соболева СО РАН по адресу пр Академика Коптюга, 4, 630090, г Новосибирск

С диссертацией можно ознакомиться в библиотеке Института математики имени С Л Соболева СО РАН

Автореферат разослан "24" сентября 2007 г

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

Д 003 015 01 при Институте математики имени С Л Соболева СО РАН доктор физико-математических наук

Шамардин Ю В

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

Актуальность темы Диссертация посвящепа исследованию задачи о р-медиане с предпочтениями клиентов (МПК) и разработке приближенных алгоритмов ее решения Исследования дискрет пых задач размещения проводятся п Инс1ипу1с математики им С Л Соболева СО РАН с конца 60-х годов Акгуалыюси, исследований обусловлена важными пракшческими приложениями этих моделей Научный интерес вызван также тем, что эти задачи относятся к классу NP-трудных оптимизационных задач для которых разработка точных и приближенных методов решения уже на протяжении 50 лет остается актуальной проблемой

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

Впервые задачи с предпоч1ениями клиентов зарубежными учеными рассматривались в конце 80-х годов [5] В конце 90-х в работах [2, 3] российских коллег была установлена тесная связь задачи с псевдо-булевыми функциями, найдены полиномиально разрешимые случаи задачи и показано сведение к задачам целочисленного линейного программирования (ЦЛП) Как обобщение классической задачи о р-медиане задача МПК является NP-трудной в сильном смысле и не принадлежит классу АРХ Этот факт а также сложность структуры математической модели подталкивают к разработке неполиномиальных приближенных методов, в основе коюрых лежат идеи локального поиска При их разработке возникает вопрос о сложности нахождения локальных онтимумов и их отклонении от глобального оптимума Для изучения этих вопросов, по аналогии с классом NP, вводится класс задач локального поиска PLS (polynomial-time local search problems) В работе [4| исследовался вопрос о вычислительной сложности получения локальных огпимумов для классической задачи о р-медиане Окрестность N\ состоит из допустимых решений, которые находятся от текущего решения на расстоянии Хэмминга равном двум Установлено, что задача локального поиска для р-медианы

с окрестностью Л^ является плотно РЬБ-полной Это означает, в частности что в худшем случае стандартный алгоритм локального спуска требует экспоненциального числа итераций для получения локального оптимума Так как задача МПК является обобщением классической задачи о р-медиане, то это свойство сохраняется и для нее Таким образом построение локального оптимума при использовании стандартного алгоритма локального поиска в худшем случае не является полиномиальной процедурой Однако поведение алгоритмов в худшем случае может сильно отличаться от их поведения в среднем [7] Поэтому разработка алгоритмов нахождения "хорошего" локального оптимума за разумное время является актуальной задачей

Цель работы Разработка и исследование генетических алгоритмов локального поиска для задачи МПК Исследование отклонений локальных огггимумов от глобального и расположения локальных оптимумов в допустимой области Сравнение нижних оценок, полученных сведением рассматриваемой задачи к задачам ЦЛП Создание компьютерной системы поддержки принятия решений (СППР) на основе полученной математической модели и разработанных алгоритмов, позволяющей пользователям проводить многовариантные расчеты

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

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

относительно окреп ноет и N i Исследованы различные формулиропки задачи в терминах задач булева линейною lipoi раммирования Предложена новая формулировка, которая приводит к лучшей нижней оценке чем другие известные Разработаны генетические алгоритмы локального поиска создано программное обеспечение, проведопы тесювые расчеты на трудных в вычислительном отношении примерах

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

Апробация работы Основные результаты диссертации докладывались на международном симпозиуме по исследованию операций "SYM-OP-IS-2003" (i Герцег-Нови, Черногория, 2003), на международной конференции "Дискретный анализ и исследование операций" (г Новосибирск,

2004), на международной конференции по исследованию операций (г Тилбург, Готландия, 2004), на 13-й международной байкальской школе-семинаре (г Северобайкальск 2005), на II, III всероссийских конференциях "Проблемы оптимизации и экономические приложения" (г Омск 2003, 2006) на 18-й мини-евро конференции по алгоритмам локального поиска с переменными окрестностями (г Пуэрто-де-ля-Круз, Испания,

2005), на школе-семинаре "Проблемы оптимизации сложных систем" (г Новосибирск, 2005, 2006), на 22-й европейской конференции по исследованию операций "EURO XXII" (Пра1а, Чехия 2007)

Публикации По теме диссертации автором опубликовано 12 рабог Структура и объем работы. Работа состоит из введения, четырех глав заключения, списка литературы из 77 наименований Общий объем работы — 92 страницы, включая 23 рисунка и 1 таблицу

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

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

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

В разделе 1 1 приводится матемагическая постановка задачи МПК и ее свойства Для это! о вводятся следующие обозначения I = {1, , т} - множество предприятий, .7 = {1, , п}- множество клиентов,

с,3 > 0, г £ 1,2 £ 3- транспортные затраты г-го предприятия при обслуживании ]-го клиента,

9ч — 0, целые, г 6 I,] 6 3- предпочтения клиентов на множестве предприятий, если д,и < д,2], то _?-ый клиент из предприятий \ч выберет предприятие

Переменные задачи у = (у,), X =

_ Г 1, если открывается г-ое предприятие,

\ 0 в противном случае, _ Г 1, если 7-ый клиент обслуживается 1-ым предприятием, \ 0 в противном случае С использованием введенных обозначений задача МПК может быть записана в виде следующей задачи двухуровневого программирования найти

(1)

(2)

у, е {0,1},г € I,

(3)

где Х'(у) оптимальное решение задачи клиентов

mi

16г ]eJ

= 1, J € J,

(5)

<У, г £ I J € J, x,j e {0,1}, I el, J £ J

(6) (7)

Величина F(y, X*) = YLY1 счх'\Ху) имеет смысл суммарных транспортных расходов, которые нужно минимизировать выбором набора из р предприятий Этот набор описывается вектором у Внутренняя экстремальная задача моделирует поведение клиентов каждый из которых выбирает предприятие среди открытых согласно собственным предпочтениям Этот выбор представляет матрица X Для каждого значения переменной у выбор X вообще говоря, может быть не единственным В частности, можно рассматривать кооперативные и антикооперативные стратегии, когда назначения в матрице X приводят к минимизации или максимизации значения величины F(y,X') на множестве оптимальных решений задачи (4)-(7)

Лемма 1 Задача МПК в кооперативной (антикооперативной) постановке сводится к задаче МПК с условием единственности выбора клиентов

Для более общего случая, когда о поведении клиентов заранее ничего не известно, в работе доказана лемма, которая указывает интервал, которому принадлежит значение целевой функции задачи с условием неоднозначности выбора клиентов Далее рассматривается только случай, когда для любого решения у существует единственное оптимальное решение X* Гарантировать эго свойство можно, например, если для каждого ] £ J выполняется условие g4 / g^j Другими словами, каждый клиент для любой пары предприятий может сказать, какое из них для него предпочтительнее В этом случае целевая функция F(y,X*) однозначно определяется вектором у, и для нее вместо F(y,X*) можно пользоваться обозначением F(y) Под оптимальным решением задачи понимается вектор у", удовлетворяющий условиям (2),(3) и доставляющий минимум функции F(y)

В разделе 1 3 приводятся необходимые определения для задач локального поиска и схема стандартного алгоритма локального спуска Этот алгоритм начинает работу с некоторого допустимого решения у задачи (1)-(7), затем просматривает окрестность N(y), и если найдено соседнее решение с лучшим значением целевой функции, то осуществляется переход к лучшему решению В противном случае, алгоритм закапчивает работу, останавливаясь в локальном минимуме Поведение алгоритма может сильно зависеть от правил замещения, т е выбора направления спуска, если таковых несколько Исследовалось пять известных правил замещения

1 спуск в направлении наилучшего элемента в окрестности,

2 спуск в направлении наихудшего элемента,

3 спуск в направлении первого подходящего,

4 спуск в направлении случайного элемента,

5 спуск по круговому правилу

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

В разделе 1 4 обсуждаются результаты экспериментальных исследований

Пункт 14 1 посвящен вычислительным экспериментам для сравнения правил замещения по точности и числу итераций при получении локальных оптимумов Эксперименты показали, что первое правило приводит к наибольшей погрешности Остальные правила, кроме последнего, дают примерно одинаковые результаты Наименьшая погрешность соответствует новому правилу максимальной свободы, которое является более трудоемким, чем предыдущие Что касается зависимости среднего числа шагов локального спуска от размерности задачи, то для всех правил, исключая второе, оно растет почти как линейная функция Второе правило приводит к наибольшему числу шагов локального спуска По-видимому, правила 3,4 являются наиболее подходящими для практических расчетов

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

от одного локальною оптимума к друюму? Как мною шагов г ухудшением нужно сделать, чтобы алгоритмом локального спуска можно было получить другой (лучший) локальный оптимум? Правда ли, чю из "плохого" локального оптимума легко найти путь к "хорошему"? Результаты экспериментов из этого раздела, говорят о том чю ландшафт устроен таким образом, что поит сделать один ша1 с ухудшением даже из хорошего локально! о оптимума (погрешность меньше 5%) и можно получить лучший локальный оптимум достаточно далеко от исходного Эти результаты означают также, чю использование больших окрестностей типа окрестности Лина-Кернигана [6], позволит алгоритму "выбраться" из произвольного локального оптимума с большой погрешностью и найти решение лучшего качества

В пункте 143 аналогичные исследования проводятся для классической задачи о р-медиане

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

В разделе 2 1 вводится описание класса РЬБ (9], сводимости задач в этом классе, приводится список известных РЬЭ-полных задач, среди которых присутствует классическая задача о р-медиане с одной из полиномиально проверяемых окрестностей

В разделе 2 2 обсуждается временная сложность алгоритмов локального поиска Приводится следствие из результатов полученных для задачи о р-медиане, которое показывает, что нахождение локального минимума в задаче МПК с рядом полиномиальных окрестностей является РБРАСЕ-полной задачей

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

Раздел 2 4 посвящен обзору известных теоретических результатов, касающихся качества локальных оптимумов, как приближенных решений оптимизационной задачи Эти результаты остаются верными и для задачи МПК

В разделе 2 5 установлена связь между локально-седловыми точками функции Лагранжа и локальными оптимумами задачи относительно окрестности N1 Приводится сведение задачи МПК к задаче минимизации полинома от булевых переменных Впервые такое сведёние бы по предложено В Л Берсеневым для простейшей задачи размещения [1] В работе Л Е Горбачевской [2] аналогичное сведёние предложено для задачи МПК без граничения на число открываемых предприятий Упорядочим элементы в каждом столбце ] £ 3 по возрастанию

Ч1 < 9Лз < < (8)

Пусть 5Ч = {£ € 1\дк] < },г & 1,3 £ 3 Обозначим Ус^ = сх,

Vс, = с,, - с, ,, 1 < I < т, г, = 1 - у„г € I,] € 3 Рассмотрим '(-1-/

следующую задачу найти минимум полинома

= о)

>«=/ ^ ke.Sn

при ограничениях

г, = т - р, (10)

■е/

г, е{0,1},г€/ (11)

Задача МПК с условием однозначности выбора клиентов эквивалентна задаче минимизации полинома от булевых переменных (9)-(11)

Сведёние задачи МПК к задаче о полиноме используется для того, чтобы сформулировать условия оптимальности Куна-Таккера, а также показать связь локально-оптимальных решений с локально-седловыми точками функции Лагранжа Это сведёние и результаты о РЬБ-полноте задачи МПК свидетельствуют о том, что нахождение локально-седловых точек функции Лагранжа оказывается не менее простой задачей, чем нахождение локальных оптимумов

Заменим ограничения (11) на ограничение 0 < г, < 1,1 е / и выпишем для релаксированной задачи функцию Лагранжа с множителями А, > 0, <т, > 0, г е I

Ь(г, А, ц, а) = Р(г) + А(т - р - ^ г,) + ^ а,(г, - 1) - /х.г,

I е/ гб/ )£/

Определение 14 Вектор (г', А*, ц", сг*) называется седловой точкой относительно окрестности Nх, если

Ь{г\ А, о)<Ь(г*, А*, у.', ст')<Ь(г, А*, /Л а')

для любых А,/1>0 (т>0 и любого вектора г из окрестности N 1(2*)

Обозначим через Р1 (г) частную производную от функции Р(г) по переменной г, Тогда условия оптимальности Куна-Таккера имеют вид

— {г,Х,(1,(т) = Р,'(г) - А + ст, -М„г € I, (12)

дгг

(13)

I е/

(14)

<7,(2, - 1) = 0,г е (15)

ц,Ь=0 ,!€/ (16)

Теорема 10 Длл любого допустимого решения у' задачи МПК следующие утверждения эквивалентны

1) существуют множители Лаграпжа А*, /2' > 0, а' > 0, г € I такие, что вектор (г(у'),\*,ц',а') является седловой точкой функции Ь относительно окрестности N1,

2) у* является локальным оптимумом относительно окрестности N

3) г(у') удовлетворяет условиям Куна-Таккера

В третьей главе для получения нижних оценок оптимума рассматриваются четыре уже известных сведёния задачи МПК к задачам ЦЛП и предлагается два новых сведёния, одно из которых доминирует остальные по значению целевой функции линейной релаксации

Определим множество Тч = {к I | д^ > г € I,] £ 7 Задачу поиска оптимального решения внутренней задачи клиентов (4)-(7) можно заменить следующими неравенствами [2|

ук< 1 - х1}, к € € I,] € J (17)

Отбрасывая условия булевости переменных в задаче (1)-(7) и заменяя задачу клиентов указанным неравенством, получаем линейную релаксацию задачи Обозначим через ЬВ\ ее оптимальное значение Задачу клиентов можно также заменить неравенствами [2]

^€I,]£J (18)

кев,,

или

У, < 1ц+51 У*, г €/,;€./, (19)

Обозначим через LBi и LB$ оптимальные значения линейных релакса-циий задач с этими ограничениями, соответственно Предлагается новая формулировка в виде задачи булева линейного программирования с ограничением

у, < z.j + (20)

Обозначим новую нижнюю оценку LB\ В пункте 3 11 доказана следующая теорема

Теорема 11 LB4 > таx(LBx, ЬВ2, LB3)

Известно [3], что для задачи (1)-(7) можно построить сведение к задаче о паре матриц с дополнительным ограничением на число выбираемых строк

Представим матрицу (с,^) в виде суммы двух матриц = a,j+bt], г 6 1,3 6 J, 1де

aAi = ^i0,c-i+lj >m>J£J> (21)

к-1

b,u = ctU + max{0, c^ -ct{]},k = l, , m, j 6 J, (22) i=i

и перестановка (ij, , i]m),j 6 J соответствует (8) Тогда задача (l)-(7) может быть записана в следующем виде

mm ) rnaxo,, + У^штЬ,,

jeJ ieJ

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

В разделе 3 13 предлагается новое представление в виде задачи о паре матриц, которое позволяет находить нижнюю оценку не хуже, чем LBi Для j-ro столбца матрицы (сц) и соответствующей (8) перестановки (г^, ,г3т) вычислим величины

Д? = min{0, c,i+iJ - ctj}}, 1 = 1, , т. - 1

Пусть Ь} = {/ е {1, т — 1} | Д, <0} Введем дополнительные переменные € {0, 1}, I € ] 6 3 и представим задачу о паре матриц следующим образом найти

т.п({£ ^ - ДМ + ^ £ М + £ £ Д/) (23)

•£/ .76.7

при ограничениях

У, <!..,+ £ г Е I, J Е J, (24)

= 1, ) е -Л (25)

= р, (26)

.е/

о < < у„ г 6 I, ] € (27)

^ > £ 1 е Ь„ з 6 3, / 6 ./, (28)

у{,у„х1: е {0,1}, / € Ь„ ] € г е / (29)

Обозначим через ЫЗ^ оптимальное значение линейной релаксации этой задачи

Теорема 13 ЬВь >

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

Теорема 14 любого N > 0 существуют, такие исходные дан-

ные задачи (1)^(7), что ЬВ§/ЬВ^ > ЛГ

Раздел 3 2 посвящен описанию адаптации процедуры Резенде Вер-нека [8] применительно к задаче МПК, которая будет использоваться в дальнейшем при разработке генетического локального поиска Эта процедура позволяет эффективно, с трудоемкостью 0(тах(п,р)тп), находить парную замену предприятий в алгоритме локального спуска при просмотре окрестности

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

В пункте 3 3 2 предлагается генетический локальный поиск для решения задачи МПК рассматриваются стандартные операторы селекции,

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

Б пунктах 3 3 3 и 3 3 4 приводится описание экспериментальных исследований о влиянии различных операторов в генетическом алгоритме на результат его работы Проводилось сравнение различных операторов скрещивания по скорости сходимости и качеству получаемого локального оптимума при различных видах селекции Тестовые примеры принадлежат классу GAP-C, который является одним из самых сложных классов тестовых задач электронной библиотеки "Дискретные задачи размещения" [10] и нахождение точного решения задачи с помощью коммерческого программного обеспечения оказалось трудоемким процессом В ходе тестирования генетического алгоритма наилучшие результаты показал равномерный оператор, который во всех экспериментах на данном классе приводил к лучшему значению целевой функции, чем другие операторы скрещивания Его успех, наверное, объясняется необычайной сложностью класса тестовых примеров где нахождение глобального оптимума или хорошего приближения представляется весьма сложным делом Также исследовалось поведение операторов скрещивания в зависимости от вероятности мутации Оказалось, что повышение вероятности мутации приводит к сглаживанию различий между операторами скрещивания, и даже отсутствие скрещивания при наличии высокой вероятности мутации приводит к хорошим результатам Тем не менее, удаление из алгоритма операторов скрещивания не является оправданным Для примеров Резенде и Вернека |11] большой размерности, п = т = 500, р = 50, генетический алгоритм с любым из рассмотренных операторов скрещивания дает лучшие результаты, чем без этих операторов

В пункте 3 3 5 проводится сравнение нижних оценок LB4, LBc нижней оценки LBt, полученной точным решением задачи о р-медиане без учета предпочтений клиентов, с верхней оценкой, полученной разработанным генетическим алгоритмом и оптимальным решением Opt задачи МПК, найденным методом ветвей и отсечений коммерческого пакета XPress Рассчитывается величина разрыва между Opt и наилучшей нижней оценкой LB7 Экперименты показали, что добавление предпочтений

в задачу о р-медиане усложняет ее, об этом свидетельствует существенный разрыв между LBj и Opt

В четвертой главе приводится описание системы поддержки принятия решений (СППР), разработанной в ходе выполнения в Институте ма-тема1ики им С Л Соболева СО РАН прикладной НИР по заказу крупной компании, выпускающей машины для сельского хозяйства Интеллектуальным ядром СППР является математическая модель двухуровневого булева программирования, тесно связанная с задачей МПК Использование разработанной СППР позволило сократить номенклатуру выпускаемых сельскохозяйственных машин и увеличить прибыль компании

В разделе 4 1 приводится описание задачи оптимизации парка сельскохозяйственных машин на содержательном уровне Известен список I = {1, ,т} типов машин, выпуском которых занимается компания, а также множество J = {1, , п} групп клиентов, покупающих эти машины Под группой клиентов подразумеваются покупатели, объединенные общими производственными целями (например, выращивание зерна в черноземной зоне) и характеризующиеся одинаковым поведением на рынке сельхозтехники В частности, покупатели из одной группы предпочитают один и тот же тип машин, если он есть в продаже, или готовы заменить его на другой согласно предпочтениям, одинаковым для всех покупателей из данной группы, если этот тип отсутствует

Одним из важных моментов в модели является определение приоритетов каждой группы клиентов по отношению к различным типам машин, а также поведение клиентов на рынке при новом предложении Раздел 4 2 посвящен описанию этого вопроса

Раздел 4 3 содержит математическую модель этой задачи Отличие от задачи МПК состоит, во-первых, в том, что задачи на верхнем и нижнем уровнях являются задачами максимизации Во-вторых, в новой задаче отсутствует требование обслужить всех клиентов В-третьих, заранее не известно число выпускаемых типов машин (отсутствует ограничение 2) В разделе 4 4 приводится сведёние задачи оптимизации парка сельскохозяйственных машин к задаче МПК Завершает четвертую главу раздел 4 4с описанием СППР, в основе которой лежит разработанный в третьей главе генетический алгоритм

В заключении приводится перечень основных результатов диссертации Исследована новая задача о р-медиане с предпочтениями клиентов Экспериментально установлено, что алгоритмы локального спуска

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

Установлено что целочисленное решение задачи о р-медиане с предпочтениями клиентов является локальным оптимумом для окрестности ЛГ1 тогда и только тогда, когда оно удовлетворяет условиям Куна-Таккера Показано что эти условия равносильны существованию множителей Лаг-ранжа, для которых целочисленное решение исходной задачи является локально-седловой точкой относительно окрестности Л^

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

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

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

1 Береснев В Л Об одном классе задач оптимизации параметров однородной технической системы // Управляемые системы Новосибирск Институт математики СО АН СССР, 1971 Вып 9 С 65-74

2 Горбачевская Л Е Полиномиально разрешимые и №-трудные двухуровневые задачи стандартизации Канд диссер физ - мат наук Институт математики им С Л Соболева Новосибирск, 1998

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

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

5 Hanjoul Р , Peeteis D A facility location problem with clients' prefeicncc orderings / / Regional Science and Urban Economics 1987 V 17, Issue 3 P 451 473

6 Kermghan В W , Lm S An effective heuristic procedure foi partitioning giaphs Bell System Tech J 1970 V 49 P 291-307

7 Papadimitriou С H Theoiy of complexity Addison Wesley, 1994

8 Resende M , Werncck R On the implementation of a swap-based local search procedure for the p-median problem // Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX 03) Edited by Richard E Ladnei SIAM Philadelphia 2003 P 119-127

9 Yannakakis M Computational complexity Local Search in Combinatorial Optimization Aarts E and Lenstra J К (Eds ) Chichester John Wiley and Sons 1997 P 19-55

10 http//math nsc ru/AP/benchmarks/index html

11 http //www research att com/' mgcr/data/index html Публикации автора по теме диссертации

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

13 Алексеева Е Правила выбора направления в алгоритме локального спуска для задачи о р-медиане // Тезисы III Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, Россия 2006 С 71

14 Алексеева Е Правила замещения в алгоритме локального спуска для задачи о р-медиане // Труды ИВМиМГ СО РАН Серия информатика Новосибирск Вып 6 2006 С 5-11

15 Алексеева Е , Кочетов Ю Сравнение алгоритмов лагранжевой релаксации и вероятностного округления для задачи о р-медиане //

Материалы II Всероссийской конференции "Проблемы оптимизации и экономические приложения" Омск, Россия, 2003 С 73

16 Алексеева Е , Кочетов Ю , Кочетова Н Критические параметры для задачи размещения с неограниченными мощностями / ' Труды XIII Байкальской международной школы-семинара Том 1 Математическое программирование Иркутск 2005 С 407 412

17 Алексеева Е , Кочетов Ю , Плясунов А Генетический алгори гм для двухуровневой задачи ор-медиане /'/ Тезисы Российской конференции "Дискретный анализ и исследование операций", 2004 С 179

18 Alekseeva Е , Fokin М Kochetov Yu and others Configuration profit tool and configuration optimizer User's manual Novosibirsk, Sobolev Institute of Mathematics 2004

19 Alekseeva E , Kochetov Yu A memetic algorithm for the p-median problem with user preferences// Abstiacts of 22nd European Conference on Operational Research Czechia (Prague), 2007 P 118

20 Alekseeva E , Kochetov Yu Large neighborhood search for the p-median problem // Proceedings SYM-OP-IS 2003, Herceg-Novi, Montenegro, 2003 P 19-21

21 Alekseeva E , Kochetov Y , Levanova T , Loresh M Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research 2005 Volume 15 (1) P 53-63

22 Alekseeva E , Kochetov Yu , Plyasunov A Complexity of local search for the p-median problem / / Extended Abstracts of 18th Mini Euro Conference on VNS Tenerife (Spain), 2005

23 Alekseeva E , Kochetov Yu , Plyasunov A Complexity of local search for thep-median problem // European Journal of Operational Research, 2007, doi 10 1016/j ejor 2006 12 063

Алексеева Екатерина Вячепавовна

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

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

Подписано в печать 27 08 07 Формат 60x84 1/16 Уел печ л 1,0 Уч -изд л 1,0 Тираж 80 экз Заказ .4» 116

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

Введение

Глава 1. Задача о р-медиане с предпочтениями клиентов —

1.1. Постановка задачи и её свойства

1.2. Задача МПК в условиях неоднозначности выбора клиентов

1.3. Алгоритм локального спуска и правила замещения

1.4. Экспериментальные исследования

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

1.4.2. Исследование расположения локальных оптимумов

1.4.3. Сравнительный анализ с классической задачей о р-медиане

Глава 2. Локальные оптимумы и их свойства.

2.1. Сложность задачи локального поиска

2.2. Временная сложность алгоритма локального поиска.

2.3. Вычислительная сложность алгоритма локального поиска в среднем случае.

2.4. Погрешность локальных оптимумов

2.5. Локально седловые точки.

Глава 3. Генетические алгоритмы

3.1. Нижние оценки оптимального решения

3.1.1. Сведения к задачам ЦЛП

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

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

3.2. Процедура Резенде и Вернека

3.3. Генетические алгоритмы

3.3.1. Общая схема алгоритма.

3.3.2. Генетический локальный поиск для задачи МПК

3.3.3. Экспериментальные исследования

3.3.4. Выбор параметров алгоритма.

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

Глава 4. Задача выбора оптимального парка сельскохозяйственных машин

4.1. Постановка задачи на содержательном уровне

4.2. Предпочтения клиентов.

4.3. Математическая постановка задачи

4.4. Сведение к задаче МПК

4.5. Структура системы поддержки принятия решений

4.5.1 Подготовка исходных данных

4.5.2 Блок оптимизации

4.5.3 Анализ полученных результатов и формирование отчётов

Теория дискретных задач размещения является одной из интенсивно развивающихся областей в исследовании операций. Возникновение этих задач и первые попытки их решения приписывают французским и итальянским математикам 17 века и, в частности, Пьеру Ферма (1601-1665). Он интересовался следующей задачей. Заданы три точки на плоскости. Найти такую четвертую точку, что сумма расстояний от неё до трех заданных точек была бы минимальной. Решением этой задачи занимался ученик Галилея, итальянский математик Евангелиста Торричелли (1608-1647). Возможно, что первым, кто сформулировал и решил эту задачу был итальянский математик Батисто Ковальери (1598-1647), однако точное первенство установить уже очень трудно. В начале двадцатого века (1909) Альфред Вебер исследовал более общую задачу о нахождении центра тяжести для трех взвешенных точек, а позже (1941) Курант и Роббинс популяризировали так называемую задачу Штейнера (1796-1863) о нахождении кратчайшей остовной сети для трёх точек на плоскости.

По-настоящему бурное развитие модели размещения получили с рождением вычислительной техники. Линейные модели, модели частично-целочисленного программирования, статистические и динамические модели размещения, а также модели с нелинейными целевыми функциями рождались из приложений по размещению нефтяных и газовых станций, размещению предприятий, станций метро, милицейских и пожарных участков и др. В СССР первые модели размещения предприятий исследовались В.П. Черениным и В.Р. Хачатуровым [19]. Интерес к этим моделям в Институте математике им. C.JI. Соболева СО РАН связан в первую очередь с приложениями в области стандартизации и унификации [1,17,18]. Работы B.J1. Береснева, Э.Х. Гимади, В.Т. Дементьева, Н.И. Глебова, а позже А.И. Давыдова, Ю.А. Кочетова, A.B. Плясунова, Ю.В. Шамардина, JT.E. Горбаневской, A.A. Агеева и др. создали фундамент для разработки программно математического аппарата решения соответствующих экстремальных задач.

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

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

Основными направлениями исследований, как правило, являются:

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

- разработка приближённых алгоритмов с априорными оценками точности;

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

В данной работе исследования ведутся по последнему направлению.

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

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

Пусть задано два конечных множества I = {1,., т} и 3 = {1,., п}. Первое множество будем интерпретировать как множество возможных пунктов размещения предприятий для производства некоторого однородного продукта, второе — множество клиентов, использующих этот продукт. Известны величины Сц, г € I, ] £ .7, задающие транспортные затраты на обслуживание го клиента из г-го пункта. Требуется выбрать из множества / не более р пунктов, в которых следует разместить предприятия, т. е. найти подмножество 5 С / мощности не более р так, чтобы суммарные затраты на обслуживание всех клиентов были бы минимальными. Комбинаторная формулировка задачи имеет следующий вид: %

Установлено [48], что задача о ^медиане является ИР-трудной./ В [5] показано, что если матрица (с^-) есть матрица кратчайших расстояний на дереве, то задача полиномиально разрешима. В [61] доказано, что в общем случае существование приближённого алгоритма с гарантированной относительной погрешностью не более 2^п,т\ где д — произвольный полином от размерности задачи, влечёт совпадение классов Р и ЫР. Особое внимание в литературе уделяется метрическому случаю, когда элементы матрицы (с¿¿) удовлетворяют неравенству треугольника. В этом случае стандартный алгоритм локального спуска приводит к локальному оптимуму с относительной погрешностью не более (3 + где к — число предприятий, которые могут заменяться в решении на другие при каждом локальном улучшении [25]. Каждый шаг такой итерационной процедуры имеет трудоемкость не более 0(тк), но число шагов может оказаться экспоненциальным. Лучший из известных полиномиальных алгоритмов имеет погрешность не более (3 + е), е > О, [53].

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

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

Задачи, в которых рассматриваются только два уровня иерархии, называются задачами двухуровневого программирования. Впервые такие задачи в игровой постановке рассматривались в [70]. В России над этими задачами работали Ю.Гермейер и его ученики [4]. Обзор современного состояния в области двухуровневого программирования можно найти, например, в [24, 73].

В диссертации рассматривается задача о р-медиане с предпочтениями клиентов (МПК). В этой задаче имеются два уровня принятия решений. Они неравноправны. Сначала на верхнем уровне принимается решение об открытии р предприятий. Затем на нижнем уровне, зная места расположения этих предприятий, клиенты самостоятельно выбирают поставщиков, руководствуясь собственными предпочтениями. Задача состоит в том, чтобы выбрать на верхнем уровне открываемые предприятия и обслужить всех клиентов с минимальными суммарными затратами, принимая во внимание тот факт, что поставщиков выбирают не на верхнем, а на нижнем уровне. Если предпочтения на нижнем уровне совпадают с предпочтениями на верхнем уровне, то получаем классическую задачу о р-медиане. Следовательно, задача МПК является КР-трудной в сильном смысле и не принадлежит классу АРХ [13].

Впервые задачи размещения с предпочтениями клиентов рассматривались П. Ханжоулем и Д. Петерсом [42]. Позже аналогичные модели независимо были построены В.Т. Дементьевым, Ю.В. Шамардиным и Л.Е. Горбачевской [6, 7, 8]. В [6] доказано, что если матрица транспортных затрат в целевой функции на верхнем уровне и матрица предпочтений клиентов на нижнем уровне обладают свойством связности, то такая задача решается эффективно. Если же матрица предпочтений является квазивыпуклой, то задача сводится к задаче о "ближайшем соседе" с фиксированным числом точек в оптимальном решении. В [8] исследовалась более общая задача без ограничения на число открываемых предприятий с условием единственности оптимального потребительского выбора. В [2] приводится сведение общего случая задачи МПК без ограничения на число открываемых предприятий к задаче минимизации полиномов от булевых переменных. Это сведение позволяет выявить полиномиально разрешимые случаи решения задачи. Вопрос построения полиномиальных приближенных алгоритмов с гарантированными оценками точности для метрической задачи МПК остаётся на сегодняшний день открытым.

Как обобщение классической задачи о р-медиане задача МПК относится к классу ОТ-трудных задач в сильном смысле. Поэтому для её решения часто используются различные эвристические алгоритмы. На сегодняшний день наиболее успешными при решении практических задач являются итерационные методы локального поиска. К ним можно отнести поиск с запретами [36, 37, 38, 64], поиск с чередующимися окрестностями [44], генетические алгоритмы [39], алгоритмы имитации отжига [20, 50] и другие метаэвристики [51, 33, 63, 65]. Многие из них используют стандартную процедуру локального спуска. Это процесс последовательного движения от текущего к соседнему решению с лучшим значением целевой функции. Процесс останавливается, когда достигнут локальный оптимум, то есть решение, которое не имеет соседнего решения с лучшим значением целевой функции. Предполагается, что для каждого решения задано множество соседних решений или окрестность. Задачу нахождения локального оптимума для заданной окрестности называют задачей локального поиска.

С теоретической точки зрения интересным представляется изучение вычислительной сложности алгоритмов локального поиска, анализ поведения алгоритма в среднем и худшем случаях. Эмпирические результаты показывают, что для многих NP-трудных задач [33, 36, 46, 63, 67] локальный поиск позволяет находить приближенные решения близкие по значению целевой функции к глобальному оптимуму. Причём трудоемкость в среднем часто оказывается полиномиальной. Однако для целого ряда окрестностей и при любом выборе направления спуска число шагов алгоритма в худшем случае, например, для решения задачи о р-медиане, не может быть ограничено сверху полиномом от длины записи исходных данных [13]. Для теоретического анализа вычислительной сложности задач локального поиска используется специальный класс PLS (сокращение от polynomial-time local search problems). С содержательной точки зрения этот класс содержит те задачи, в которых локальная оптимальность может быть проверена за полиномиальное время: для заданного решения требуется определить, является ли оно локальным оптимумом, и если нет, то найти соседнее решение с лучшим значением целевой функции. В этом случае соответствующую окрестность называют полиномиально проверяемой. Если предположить, что NP^co-NP, то в классе PLS нет NP-трудных задач [68, 75]. Другими словами, не существует NP-полных задач, которые за полиномиальное время сводились бы к какой-нибудь задаче локального поиска из класса PLS. Это утверждение показывает, что скорее всего класс PLS не содержит NP-трудных задач. Поэтому задачи локального поиска не так сложны, как NP-трудные, что, в частности, подтверждают и экспериментальные исследования. Нахождение локального оптимума для полиномиально проверяемой окрестности не представляется сложным делом на практике. В классе Р1Д как и в классе удалось выделить наиболее трудные задачи, РЬБ-полные задачи, для которых доказан аналог теоремы Кука [47]. Если существует полиномиальный алгоритм решения хотя бы одной РЬБ-полной задачи, то все задачи из класса РЬБ полиномиально разрешимы. Однако до сих пор неизвестно ни одного полиномиального алгоритма решения РЬБ-полных задач. Построение такого алгоритма было бы сенсацией. Все задачи из класса РЬБ оказались бы полиномиально разрешимыми. Как пишут Я.К. Ленстра и Т. Вредевельд [74] ".скорее всего это не так, потому что существование такого алгоритма потребовало бы разработки достаточно общего подхода для нахождения локальных оптимумов, не менее общего, чем метод эллипсоидов, так как задача линейного программирования с симплексной окрестностью принадлежит классу РЬБ".

Аналогия с линейным программированием здесь весьма уместна и может быть даже глубже, чем кажется. Рождение симплекс метода толкнуло вперёд разработку методов линейного программирования и сегодня это один из самых мощных методов, используемых в приложениях. Он не является полиномиальным при оценке поведения в худшем случае, но в среднем он работает очень эффективно [14, 16, 62]. Аналогичную картину можно наблюдать и с алгоритмами локального спуска. Установлено [75, 13], что в худшем случае для ряда РЬБ-полных задач алгоритм локального спуска требует экспоненциального числа итераций, но в среднем его поведение полиномиально. Это обстоятельство объясняет интерес к таким алгоритмам, исследование их возможностей и модификаций, а также применение в более сложных схемах метаэвристик. Именно эти вопросы являются центральными в диссертации и исследуются на примере задачи МПК.

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

Заключение

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

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

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

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

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

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

3. Береснев В. Л. Об одном классе задач оптимизации параметров однородной технической системы // Управляемые системы. Новосибирск: Институт математики СО АН СССР, 1971. Вып. 9. С. 65-74.

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

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

6. Горбачевская Л. Е. Полиномиально разрешимые и ИР-трудные двухуровневые задачи стандартизации. Кандидатская диссертация физ.-мат. наук, Институт математики им. С.Л.Соболева. Новосибирск, 1998.

7. Горбачевская Л. Е. Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода // Дискрет, анализ и исслед. операций. Сер. 2. 1998. Т. 5, № 2. С. 20-33.

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

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

10. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Кандидатская диссертация физ мат. наук. Омск, 2000.

11. И. Еремеев А. В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 1. С. 47-60.

12. Кочетов Ю. А., Обуховская П. А., Пащенко М. Г. Составление расписаний учебных занятий при достаточном числе аудиторий // Труды ИВМиМГ СО РАН. Серия Информатика. Новосибирск 2007. С. 105112.

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

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

15. Растригин JI. А. Случайный поиск — специфика, этапы истории и предрассудки // Вопросы кибернетики. Вып. 33. 1978. С. 3-16.

16. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.

17. Типовая методика оптимизации многомерных параметрических рядов. М.: Изд-во стандартов, 1975.

18. Типовая методика оптимизации одномерного параметрического (ти-поразмерного) ряда. М.: Изд-во стандартов, 1976.

19. Черенин В. П., Хачатуров В. Р. Решение методом последовательных расчетов одного класса задач о размещении производства // Экономико-математические методы. М.: Наука, 1965. С. 279-290.

20. Aarts Е. Н. L, Korst J.H.M., van Laarhoven P. J. M. Simulated annealing. Local Search in Combinatorial Optimization. Chichester: Wiley. 1997. P. 91-120.

21. Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set // Oper. Res. 1997. V. 45, № 2, P. 226-243.

22. Ahuja R. K., Ergun 0., Orlin J. B., Punnen A. P. A survey of very large-scale neighborhood search techniques // Discrete Appl. Math. 2002. V. 123, Issue 1-3. P. 75-102.

23. Alekseeva E., Fokin M., Kochetov Yu. and others. Configuration profit tool and configuration optimizer. User's manual. Novosibirsk, Sobolev Institute of Mathematics. 2004.

24. Anandalingam G., Friesz T. L. Hierarchucal optimization: an introduction // Ann. Oper. Res. 1992. V. 34, № 1. P. 1-11.

25. Arya V., Garg N., Khandekar R., Meyerson A.,Munaga K.,Pandit V. Local search heuristics for ^-median and facility location problems // SIAM Journal on Computing. 33. 2004. P. 544-562.

26. 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.

27. Avella P., Sassano A., Vasil'ev I. Computational study of large-scale p-median problems // Math. Program. Ser. A 109. 2007. P. 89-114.

28. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems //J. Heuristics. 1998. V. 4, N 4. P. 107-122.

29. Balinski M. L. Integer programming: methods, uses, computation. Managment Science 12. 1965. P. 253-313.

30. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations // Oper. Res. Lett. 1994. V. 16, N 2. P. 101-114.

31. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. In Natural automata and useful simulations. Edited by Pattee H. H. etc. London: Macmillan. 1966. P. 3-42.

32. Burke Ed., Kendall G.(Eds.) Search methodologies. Introductory tutorials in optimization and decision support techiques. Springer. 2005.

33. Dempe S. Foundational of Bilevel Programming. The Netherlands, Dordrecht: Klumer Academic Publishers. 2002.

34. Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc. of the 19-th Design Automation Conference, Los Alamitos, CA: IEEE Comput. Soc. Press, 1982. P. 175-181.

35. Glover F., Laguna M. Tabu search. Boston: Kluwer Acad. Publ., 1997.

36. Glover F. Tabu search. P.I // ORSA J. Comput. 1989. V. 1. P. 190-206.

37. Glover F. Tabu search. P.II // ORSA J. Comput. 1990. V. 2. P. 4-32.

38. Goldberg D. E. Genetic algorithm in search, optimization and machine learning. Reading, MA: Addison-Wesley. 1989.

39. Goldberg D. E. Simple genetic algorithms and the minimal deceptive problem. Genetic Algorithms and Simulated Annealing. Chapter 6. Los Altos, CA, Morgan Kauffman. 1987. P. 74-88.

40. Hammer P.L. Plant Location — a pseudo-boolean approach // Israel J. Technology. 1968. V. 6. № 5. P. 330-332.

41. Hanjoul P., Peeters D. A facility location problem with clients' preference orderings // Regional Science and Urban Economics. 1987. V. 17, Issue 3. P. 451-473.

42. Hansen P., Mladenovic N. An introduction to variable neighborhood search // Meta-heuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer. Acad. Publ., 1998. P. 433-458.

43. Hansen P., Mladenovic N. Developments of variable neighborhood search. Essays and Surveys of Metaheuristics. Boston: Kluwer Acad. Publ., 2002. P. 415-440.

44. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.

45. Ibaraki T., Nonobe K., Yagiura M. (Eds.) Metaheuristics: progress as real solvers. Berlin: Springer, 2005.

46. Johnson D. S., Papadimitriou C. H., Yannakakis M. How easy is local search? // J. of Computer and System Science. 37. 1988. P. 79-100.

47. Kariv O., Hakimi S. An algoritmic approach to network Location Problems. The p-medians // SIAM Journal of Applied Mathematics. 37. 1979. P. 539-560.

48. Kernighan B. W., Lin S. An effective heuristic procedure for partitioning graphs // Bell System Tech. J. 1970. V. 49. P. 291-307.

49. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing //Science. 1983. V. 220, P. 671-680.

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

51. Kochetov Yu., Ivanenko D. Computationally difficult instances for the uncapacitated facility location problem. In Metaheuristics: progress as real solvers. Edited by Ibaraki T. etc. Berlin: Springer, 2005. P. 351-367.

52. Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Third Edition. P. 537-571.

53. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // European J. Oper. Res. 1983. V. 12, № 12. P. 36-81.

54. Krentel M. W. Structure in locally optimal solutions // 30th Annual Symposium on Foundation of Computer Science. IEEE Computer Society Press . Los Alamitos CA. P. 216-222.

55. Krentel M. W. On finding and verifying locally optimal solutions // SIAM Journal on Computing. 1990. № 19. P. 742-751.

56. Martelo S., Toth P. Generalized assigment problem. Knapsack problem. Algorithms and Computer Implementations. John Wiley and Sons Ltd. 1990. P. 189-213.

57. Mirchandani P. B. The p-median problem and generalization. Discrete Location Theory. Edited by Mirchandani P. B, Francis R. L. John Wiley and Sons. 1990. P. 55-119.

58. Mladenovic N.,Brimberg J.,Hansen P., Moreno-Pérez J. The p-median problem: A survey of metaheuristic approaches // European J. of Oper. Res. (to appear)

59. Mautor T. Intensification neighborhoods for local search methods. Essays and Surveys in Metaheuristics. Operation Research Computer Science. Edited by Ribeiro C., Hansen P. Kluwer Acad. Publ. 2001. P. 493-508.

60. Nemhauser G., Wolsey L. Integer and Combinatorial Optimization. John Wiley and Sons. 1988. P. 402.

61. Papadimitriou C. H. Theory of complexity. Addison Wesley, 1994.

62. Pétrowski D.,Taillard S. Metaheuristics for Hard Optimization. Methods and Case Studies. Springer. 2006.

63. Rolland E., Schilling D.A., Current J. R. An efficient tabu search procedure for the p-median problem // European J. of Oper. Res. № 96. 1996. P. 329-342.

64. Resende M., Werneck R. A hybrid heuristic for the p-median problem // Journal of heuristics. 10(1). 2004. P. 59-88.

65. Ribeiro C., Hansen P.(Eds.) Essay and surveys in metaheuristics. Kluwer Academic Publishers. 2002.

66. Schaffer A. A., Yannakakis M. Simple local search problems that are hard to solve // SIAM J. Comput. 1991. V. 20, N. 1. P. 56-87.

67. Schwefel H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.

68. Stackelberg H. V. The theory of market economy. Oxford: Oxford Univ. Press. 1952.

69. Tovey C. A. Local improvement on discrete structures // Local search in combinatorial optimization. Chichester: Wiley, 1997. P. 57-90.

70. Teitz M. B., Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph // J. of Oper. Res. 16(5). 1968. P. 955961.

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

72. Vredeveld T., Lenstra J. K. On local search for the generalized graph coloring problem // Oper. Res. Letters. 2003. V. 31, N. 4. P. 28-34.

73. Yannakakis M. Computational Complexity. Local Search in Combinatorial Optimization. Edited by Aarts E. and Lenstra J. K. Chichester: John Wiley and Sons. 1997. P. 19-55.76. http://www.research.att.com/ mgcr/data/index.html77. http://www.gams.com/