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


PDF просмотр
НазваниеОценки оптимальных значений и методы решения задач размещения с предпочтениями клиентов
страница3/6
КЛИМЕНТОВА КСЕНИЯ БОРИСОВНА
Дата конвертации11.10.2012
Размер91,7 Kb.
ТипАвтореферат
СпециальностьС диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.
Год2010
На соискание ученой степениКандидат физико-математических наук
1   2   3   4   5   6

В работах [1, 2] соавтору И.Л. Васильеву принадлежит идея исследова-
ния полиэдральной структуры ЗРПК на основе взаимосвязей с задачами
о паре матриц и упаковки множества. Теоремы, касающиеся нового семей-
ства правильных неравенств и новой нижней оценки, были сформулиро-
ваны и доказаны автором лично.
Разработка и реализация нового метода ветвей и отсечений, предло-
женного в диссертации, осуществлялись автором лично. Из совместных
публикаций с Ю.А. Кочетовым, А.В. Плясуновым, Е.В. Алексеевой на
защиту выносятся только результаты, полученные автором лично.
Структура и объем диссертации. Диссертация состоит из введе-
ния, трех глав, заключения и списка литературы, включающего 177 на-
именований. Общий объем диссертации составляет 124 страницы, из кото-
рых 107 страниц основного текста, включающего 3 рисунка и 11 таблиц.
Результаты главы 2 опубликованы в работах [1,2,5,7]. Результаты главы 3
опубликованы в работах [1,3,4,6-12].
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении приведены известные из литературы постановки задач
размещения, дан обзор современного состояния научных исследований в
этом направлении, обоснована актуальность темы диссертации, отраже-
ны научная новизна и апробация результатов работы. Кратко изложено
содержание диссертации.
В первой главе диссертации сделан обзор различных комбинаторных
и целочисленных постановок исследуемых задач размещения с предпочте-
ниями клиентов, а также представлены некоторые известные результаты,
необходимые для дальнейшего изложения.
В §1.1 приводятся постановки задач размещения с предпочтениями
клиентов. Пусть задано множество мест для возможного размещения
предприятий I = {1, . . . , m} и множество клиентов J = {1, . . . , n}. Для
каждого места задана стоимость размещения предприятия fi ≥ 0, i ∈ I, а
также известны затраты на обслуживание клиентов C = {cij}, где cij ≥ 0
— стоимость обслуживания j-го клиента предприятием, размещенным на
i-ом месте, i ∈ I, j ∈ J. Кроме того, определены предпочтения клиентов
в виде матрицы G = {gij}, i ∈ I, j ∈ J. Если gi1j < gi2j, i1, i2 ∈ I, j ∈ J,
то j-й клиент из открытых предприятий i1 или i2 выберет предприятие
i1. Требуется разместить некоторое подмножество предприятий на местах
7

из множества I и обслужить всех клиентов с минимальными суммарны-
ми затратами на открытие предприятий и обслуживание клиентов, учи-
тывая при этом предпочтения клиентов. Рассматривается также задача
о p-медиане с предпочтениями клиентов, в которой требуется открыть в
точности p ∈ Z+ предприятий на местах из множества I при условии, что
fi = 0 ∀i ∈ I.
В §1.2 и §1.3 обсуждаются различные определения решений ЗРПК, а
также известные результаты о соотношении этих решений и о взаимосвязи
ЗРПК с задачей о паре матриц.
В §1.4 приведены различные постановки ЗРПК в виде моделей ЦЛП.
Для этого вводятся следующие переменные: yi = 1, если предприятие
открывается на i-ом месте, в противном случае yi = 0, i ∈ I; xij = 1,
если j-й клиент обслуживается из предприятия на i-ом месте, xij = 0
в противном случае, i ∈ I, j ∈ J. С использованием этих переменных
ЗРПК может быть записана в виде задачи двухуровневого целочисленного
программирования
cijxij(y) +
fiyi ↓ min,
(1)
y
i∈I j∈J
i∈I
yi ∈ {0, 1}, i ∈ I,
(2)
где x(y) – оптимальное решение задачи клиентов:
gijxij ↓ min,
(3)
x
i∈I j∈J
xij = 1,
(4)
i∈I
xij ≤ yi,
(5)
xij ∈ {0, 1}, i ∈ I, j ∈ J.
(6)
Известно, что исследуемые ЗРПК в условиях единственности оптималь-
ного выбора клиентов на нижнем уровне могут быть редуцированы к рав-
носильной одноуровневой задаче ЦЛП путем введения дополнительных
ограничений (8):
cijxij +
fiyi ↓ min,
(7)
x,y
i∈I j∈J
i∈I
8

yi +
xkj ≤ 1,
i ∈ I, j ∈ J,
(8)
k∈Wij
xij = 1,
j ∈ J,
(9)
i∈I
0 ≤ xij ≤ yi ≤ 1,
i ∈ I, j ∈ J,
(10)
xij, yi ∈ {0, 1},
i ∈ I, j ∈ J,
(11)
где Wij — множество предприятий, которые менее предпочтительны для
клиента j, чем предприятие i: Wij = {k ∈ I | gkj > gij}.
Будем обозначать задачу (7)–(11) через (P), а многогранник данной
задачи (т.е. выпуклую оболочку точек, удовлетворяющих ограничениям
(8)–(11)) — через P . Можно показать, что решение (x∗, y∗) задачи (P)
представляет собой оптимальное решение ЗРПК.
Замечание. Отметим, что задачу о p-медиане с предпочтениями кли-
ентов можно сформулировать в виде аналогичной модели двухуровнево-
го целочисленного программирования. Одноуровневая постановка такой
задачи будет отличаться от задачи (P) дополнительным ограничением
yi = p при условии fi = 0 ∀i ∈ I, где p ∈ Z+ — параметр, определя-
i∈I
ющий количество открываемых предприятий. Будем обозначать задачу в
такой постановке через (Pm), а ее многогранник — через Pm.
В заключительном §1.5 первой главы представлены теоретические ос-
новы метода отсечений, метода ветвей и границ, а также метода ветвей и
отсечений3).
Во второй главе диссертационной работы исследуются свойства мно-
гогранников ЗРПК, а также вопросы, связанные с построением нижних
оценок оптимальных значений этих задач. Построенные оценки оптималь-
ного значения ЗРПК используются при разработке метода ветвей и отсе-
чений для решения подобного сорта задач.
В §2.1 представлены известные из литературы результаты, касающиеся
получения нижних оценок оптимальных значений ЗРПК. Будем обозна-
чать через LB1 нижнюю оценку, которая является оптимальным значе-
нием линейной (непрерывной) релаксации (7)–(10) задачи ЦЛП (P), т.е.
когда ограничение (11) не принимается в расчет.
Первая группа результатов связана с известными семействами правиль-
3 )G.N. Nemhauser, L.A. Wolsey. Integer and Combinatiorial Optimization. — New York: A Wiley-
Interscience Publication, 1999.
9
1   2   3   4   5   6

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


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