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


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

ных неравенств для многогранников P и P 4),5)
m
. Лучшая из известных
нижняя оценка оптимального значения для данной группы результатов
получена с помощью следующих правильных неравенств5). Для каждо-

го подмножества j1, ..., js ∈ J и i ∈ I введем обозначения U(i, jt) ={k ∈
t−1
I | k ∈ Wij ∩ (
B )},
t
ijq
q=1
s
xkj +
x
+ y
1
kjt
i ≤ 1,
j1, ..., js ∈ J, i ∈ I,
(12)
k∈Wij
t=2 k∈U(i,j
1
t)
xiu ≤ xiv,
u, v ∈ J, i ∈ I, Biv ⊆ Biu,
(13)
xiu = xiv,
u, v ∈ J, i ∈ I, Biu = Biv,
(13′)

где Bij ={k ∈ I : gkj < gij} — это множество предприятий, которые
более предпочтительны для клиента j, чем предприятие i. Будем далее
обозначать через LB3 нижнюю оценку оптимального значения ЗРПК, ко-
торую определяет оптимальное значение непрерывной задачи линейного
программирования (7), (9), (10), (13), (13′) со всеми неравенствами (12),
а через LB2 — оптимальное значение в задаче (7), (9), (10), (13), (13′)
с подмножеством неравенств (12). Известно, что представленные оценки
связаны следующей цепочкой неравенств: LB
5)
1 ≤ LB2 ≤ LB3 .
Вторая группа известных результатов, связанных с нижними оценками
оптимального значения ЗРПК, основана на расширенной постановке за-
дачи в пространстве переменных более высокой размерности. При этом
непрерывная релаксация расширенной формулировки определяет ниж-
нюю оценку оптимального значения исходной задачи. Расширенные по-
становки ЗРПК представляют собой модели ЦЛП для известной комби-
наторной формулировки в виде задачи о паре матриц6). Будем обозначать
нижнюю оценку, получаемую с помощью такой расширенной формулиров-
ки, через LB4. Известно, что LB4 ≥ LB1.
В §2.2 исследуются свойства многогранников ЗРПК. Чаще всего при
анализе задач размещения, например, простейшей задачи размещения
или задачи о p-медиане, исследуют многогранник, в котором ограниче-
ния
xij = 1, j ∈ J заменяются на неравенства
xij ≤ 1, j ∈ J. В
i∈I
i∈I
4 )Л.Е. Горбачевская. Полиномиально разрешимые и N P -трудные двухуровневые задачи стандар-
тизации: дис. ... канд. физ.-мат.наук. Новосибирск, 1998.
5 )L. C´anovas, S. Garc´ia, M. Labb´e, A. Mar´in. A strengthened formulation for the simple plant location
problem with order // Operations Research Letters. — 2007. — V. 35, N 2. — P. 141–150.
6 )Е.В. Алексеева, Ю.А. Кочетов. Генетический локальный поиск для задачи о p-медиане с пред-
почтениями клиентов // Дискр. анализ и исследование операций. — 2007. — Т. 14, № 1. — С. 3–31.
10

случае задачи о p-медиане помимо этого на
yi ≤ p заменяются и огра-
i∈I
ничения
yi = p. Известно, что путем преобразования коэффициентов
i∈I
целевых функций этих задач можно добиться эквивалентности задачи с
неравенствами и исходной задачи с равенствами. Такой прием обычно су-
щественно упрощает исследование свойств задачи, поскольку новый мно-
гогранник оказывается полноразмерным (другими словами, размерность
такого многогранника равна размерности пространства), в частности, для
простейшей задачи размещения и задачи о p-медиане. Оказывается, это
утверждение справедливо и для многогранников ЗРПК.
Обозначим ЗРПК с неравенствами через (P≤), а ее многогранник через
P ≤ (соответственно (P≤
m) и P ≤
m для задачи о p-медиане с предпочтениями
клиентов).
Предложение 1.
Многогранник P ≤ является полноразмерным:
dim(P ≤) = m + mn.
Далее приводятся предложения о некоторых фасетных неравенствах
для многогранников ЗРПК. Неравенство называется фасетным, если раз-
мерность его грани (т.е. пересечения гиперплоскости, соответствующей
этому неравенству, с многогранником) на единицу меньше размерности
многогранника.
Предложение 2. Неравенства xij ≤ 0, i ∈ I, j ∈ J и xij ≤ yi, i ∈ I,
j ∈ J являются фасетными для многогранника P ≤.
Наибольший интерес в исследовании фасетных неравенств для мно-
гогранников ЗРПК представляют неравенства, отражающие специфику
этих задач, а именно, предпочтения клиентов. Весьма важным является
следующее утверждение.
Теорема 1. Если Bij = ∅ для некоторых i ∈ I, j ∈ J, то неравенства
yi +
xkj ≤ 1, i ∈ I, j ∈ J, являются фасетными для многогранника
k∈Wij
P ≤.
Аналогичные утверждения справедливы и для многогранника P ≤
m .
В §2.3 на основе анализа расширенной формулировки задачи о паре
матриц и известных результатов о ее взаимосвязи с задачами (P) и (Pm)6)
построено новое семейство правильных неравенств для многогранников P
и Pm .
Для каждого j ∈ J рассмотрим перестановку ρ(j) = (i1, . . . , im), упо-
рядочивающую по возрастанию элементы столбца j ∈ J матрицы G:
11
1   2   3   4   5   6

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


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