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

• Автор: Климентова, Ксения Борисовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Иркутск
• Количество страниц: 124 с. : ил.

Оглавление
Введение
Глава 1 Задачи размещении с предпочтениями клиентов и методы целочисленного программирования

1.1 Постановка задами

1.2 Различные понятия решения

1.3 Взаимосвязь с задачей о парс матриц

1.4 Целочисленные формулировки задачи.

1.5 Методы целочисленного программирования.

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

1.5.2 Метод отсечений

1.5.3 Метод ветвей и границ.

1.5.4 Эвристические методы
1.5.5 Метод ветвей и отсечений .
1.6 Заключительные замечания
Глава 2 Нижние оценки и метод отсечений для задач размещения с предпочтениями клиентов
2.1 Известные нижние оценки
2.1.1 Известные правильные неравенства.
2.1.2 Реакция к задаче о паре матриц
2.2 Свойства многогранника задачи размещения с предпочтениями клиентов
2.3 Новые правильные неравенства.
2.4 Взаимосвязь с задачей упаковки множества.
2.4.1 Задача упаковки множества.
2.4.2 Неравенства клик для задач размещения с предпочтениями клиентов
2.5 Метод отсечений для нового семейства правильных неравенств.
2.6 Заключительные замечания.
Глава 3 Численная реализация метода ветвей и отсечений для задач размещения с предпочтениями клиентов
3.1 Тестовые задачи
3.2 Численное сравнение нижних оценок.
3.3 Верхние оценки и метод имитации отжига.
3.4 Поиск оптимального решения задачи
3.5 Задача кластерного анализа
3.6 Кластеризация раковых клеток
3.7 Заключительные замечания
Заключение
Литература


Кроме того, задачи размещения имеют широкий спектр практических приложений, в том числе в технике, в экологии и экономике. Простейшая задача размещения, задача о р-медиане, задачи размещения с ограничениями на мощность производства [, 2] сами но себе имеют практические экономические постановки и могут быть использованы при решении различных экономических задач проектирования сетей обслуживания: размещении предприятий, филиалов фирмы или банка, нефтяных и газовых месторождений (, , , ]. Приложения этих моделей к задачам стандартизации и унификации исследовались, например, в работах [6. Практическое приложение задачи о р-медиане к задачам, возникающим в автомобильной промышленности, рассматривалось в работах [7, ]. Рассмотрим для примера подробную формулировку этой прикладной задачи. Каждый легковой автомобиль может комплектоваться различным набором опций. Такой набор называют конфигурацией. Покупатель но своему желанию может дополнительно к базовой комплектации выбрать установку подушек безопасности, системы ABS, кондиционера и т. В соответствии с набором опций должен быть установлен определенный набор электропроводки, гарантирующий подключение указанных дополнительных устройств. В современном автомобиле число опций может доетшнть -, а число их комбинаций может превышать несколько десятков тысяч. В силу технологических особенностей каждый набор электропроводки изготавливается как единое целое, и только ограниченное количество этих наборов может быть доступно на сборочном конвейере. Если необходимая конфигурация электропроводки недоступна, то она должна быть замещена совместимой. Под совместимой подразумевается такая конфигурация, которая содержит по крайней мере электропроводку для подключения всех необходимых опций. При такой замене часть электропроводки не используется (дарится покупателю), и в связи с этим возникают избыточные производственные издержки, которые необходимо минимизировать. Сформулированная задача носит название задачи оптимального замещения. В работах [7, ] для ее моделирования и решения использовалась задача о р-медиане. Они могут быть использованы при разработке маршрутов транспорта (например, линий метро), при проектировании автодорог и трубопроводов. Кроме того, задача поиска медианного цикла использовалась для размещения почтовых ящиков и мусорных контейнеров (7). Модели задач размещения взаимосвязанных объектов применялись для решения задачи проектирования расположения модулей технологического оборудования швейного производства и при анализе оптимальности размещения технологического оборудования нефтехимического предприятия ||. Особо следует отметить приложения задач размещения к задачам кластеризации и классификации данных. Такие задачи, в свою очередь, имеют огромное количество приложений, например, в банковской деятельности, системах распознавания образов [, , ', 4), а также других областях экономики, техники и экологии, медицины. Б задаче кластерного анализа имеется некоторое множество объектов, которое нужно разбить на псисрссекающисся подмножества, называемые кластерами. Сходные" с точки зрения некоторого критерия объекты должны оказаться в одинаковых кластерах, а "различные" — в разных. Для решения задачи кластерного анализа естественным образом могут быть использованы задачи размещения. В этом случае предполагается, что множество клиентов и множество мест для размещения пунктов обслуживания совпадают (7 = . Как упоминалось выше, решение задач размещения в такой постановке представляет собой "звезды" с открытым пунктом обслуживания (или медианой) посредине (см. В задаче кластерного анализа каждая такая "звезда" представляет собой кластер, а соответствующая медиана называемся представители* кластера. Задача о р-медианс применялась для кластерного анализа в работах [, 9, 0, 6, 0, 9, 7, 2). Например, в [] исследовалась задача автоматического распознавания и классификации дефектов, которая возникает при разработке системы машинного зрения, работающей в режиме реального времени при производстве полупроводников. Задача о р-медпане здесь использовалась для решения задачи кластерного анализа на этапе обучения системы.