Оценки оптимальных значений и методы решения задач размещения с предпочтениями клиентов


PDF просмотр
НазваниеОценки оптимальных значений и методы решения задач размещения с предпочтениями клиентов
страница1/6
КЛИМЕНТОВА КСЕНИЯ БОРИСОВНА
Дата конвертации11.10.2012
Размер91,7 Kb.
ТипАвтореферат
СпециальностьС диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.
Год2010
На соискание ученой степениКандидат физико-математических наук
  1   2   3   4   5   6
На правах рукописи
КЛИМЕНТОВА КСЕНИЯ БОРИСОВНА
ОЦЕНКИ ОПТИМАЛЬНЫХ ЗНАЧЕНИЙ И
МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ
С ПРЕДПОЧТЕНИЯМИ КЛИЕНТОВ
05.13.01 – Системный анализ, управление и
обработка информации (в технике, экологии и экономике)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Иркутск – 2010

Работа выполнена в Учреждении Российской академии наук Институте
динамики систем и теории управления Сибирского отделения РАН (ИД-
СТУ СО РАН).
Научный руководитель:
доктор физико-математических наук,
профессор
Стрекаловский Александр
Сергеевич.
Официальные оппоненты: доктор физико-математических наук,
профессор
Колоколов Александр
Александрович;
кандидат технических наук,
доцент
Семенов Александр Анатольевич.
Ведущая организация:
Институт вычислительной
математики и математической
геофизики СО РАН (г. Новосибирск).
Защита состоится 2 декабря 2010 г. в 14.00 ч. на заседании диссертаци-
онного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, Иркутск,
ул. Лермонтова, 134.
С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.
Автореферат разослан 1 ноября 2010 г.
Ученый секретарь
диссертационного совета
д.ф.-м.н.
А.А. Щеглова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Диссертация посвящена теоретическому исследованию полиэдральных
свойств задач размещения с предпочтениями клиентов и построению но-
вых оценок оптимальных значений этих задач, а также разработке и реа-
лизации численных методов поиска оптимальных решений.
Актуальность темы. Задачи размещения представляют большой ин-
терес для специалистов как с теоретической, так и с практической точки
зрения. Большинство таких задач относится к классу NP-трудных, поэто-
му разработка эффективных алгоритмов поиска оптимальных решений
задач размещения в настоящее время является актуальной проблемой в
области методов оптимизации. С другой стороны, актуальность исследо-
ваний задач размещения объясняется широким спектром важных практи-
ческих приложений в технике, экономике и экологии. В частности, модели
размещения возникают при проектировании сетей обслуживания, реше-
нии задач стандартизации, кластерного анализа и т.д. Кроме того, внима-
ние специалистов в области оптимизации в последнее время привлекают
задачи с иерархической структурой, уровни иерархии в которых неравно-
правны.
Задачи размещения с предпочтениями клиентов (ЗРПК) представля-
ют собой один из вариантов двухуровневых обобщений базовых моделей
задач размещения: простейшей задачи размещения и задачи о p-медиане.
В них учитывается дополнительная информация о предпочтениях клиен-
тов, которые могут отличаться от пожеланий поставщика, определяемых
минимизацией транспортных затрат.
Исследованию задач размещения различных классов посвящено боль-
шое количество работ. В России такие задачи исследуются с 70-х годов XX
века под руководством В.Т. Дементьева, В.Л. Береснева, Э.Х. Гимади1),
А.А. Колоколова и др.
Насколько известно, впервые модель ЗРПК была предложена и иссле-
дована P. Hanjoul и D. Peeters2). Позже аналогичные задачи изучались, в
том числе, в работах В.Т. Дементьева, В.Л. Береснева, Э.Х. Гимади, А.А.
Колоколова, Ю.А. Кочетова, Л.Е. Горбачевской.
Для разработки методов поиска оптимальных решений задач размеще-
1 )В.Л. Береснев, Э.Х. Гимади, В.Т. Дементьев. Экстремальные задачи стандартизации. — Ново-
сибирск: Наука, 1978.
2 )P. Hanjoul, D. Peeters. A facility location problem with clients’ preference orderings // Regional Sci.
Urban Econom. — 1987 . — V. 17. — P. 451–473.
3

ния используются модели целочисленного линейного программирования
(ЦЛП). Традиционным подходом к решению задач ЦЛП является метод
ветвей и границ и его модификации, например, метод ветвей и отсечений.
При этом решающую роль в обеспечении скорости работы этих методов
играют верхние и нижние оценки оптимального значения исследуемой за-
дачи, использующиеся для сокращения полного перебора допустимых то-
чек.
Для построения нижних оценок в ЗРПК могут быть использованы так
называемые правильные неравенства, которые определяют полупростран-
ства, содержащие допустимую область задачи (см., например, работы Л.Е.
Горбачевской, M. Labb´e с соавторами), а также формулировки задачи в
пространстве переменных большей размерности — расширенные форму-
лировки (работы Ю.А. Кочетова, Е.В. Алексеевой).
Таким образом, улучшение известных нижних оценок посредством по-
строения новых семейств правильных неравенств, а также разработка но-
вых методов и алгоритмов для поиска оптимальных решений с использо-
ванием методов отсечений для этих семейств неравенств является акту-
альной задачей дискретной оптимизации.
Целью работы является исследование допустимой области ЗРПК и
построение новых семейств правильных неравенств для улучшения из-
вестных оценок оптимальных значений, а также разработка и реализация
численных методов поиска оптимальных решений на основе построенных
неравенств.
Предмет и объект исследования. Объектом исследования являют-
ся модели ЗРПК в целочисленной постановке.
Предмет исследования — построение эффективных методов поиска оп-
тимальных решений в задачах размещения с двухуровневой структурой.
Методы исследования. В работе используются современная теория
комбинаторной оптимизации, теория и методы целочисленного програм-
мирования (алгоритмы отсечений, ветвей и границ, ветвей и отсечений),
элементы линейной алгебры и теории выпуклого анализа, а также совре-
менная методология экспериментальных исследований с применением вы-
числительной техники и коммерческих пакетов прикладных программ для
решения задач оптимизации.
Научная новизна результатов диссертации заключается в улучшении
известных к настоящему времени нижних оценок оптимальных значений
ЗРПК на основе исследования взаимосвязей этих задач с задачей упаков-
4
  1   2   3   4   5   6

Разместите кнопку на своём сайте:
поделись


База данных защищена авторским правом ©dis.podelise.ru 2012
обратиться к администрации
АвтоРефераты
Главная страница