Задача размещения заказов и алгоритм ее решения
The paper considers an order allocation problem with a discounts objective function and investigates its features. An algorithm solving this problem is proposed. Such an algorithm includes the ralgorithm for obtaining lower estimations. Additional constrains are generated for initial problem, and al...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2005 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84933 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача размещения заказов и алгоритм ее решения / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 113-119. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84933 |
|---|---|
| record_format |
dspace |
| spelling |
Бойко, В.В. Кузьменко, В.Н. 2015-07-17T05:56:15Z 2015-07-17T05:56:15Z 2005 Задача размещения заказов и алгоритм ее решения / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 113-119. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84933 519.8 The paper considers an order allocation problem with a discounts objective function and investigates its features. An algorithm solving this problem is proposed. Such an algorithm includes the ralgorithm for obtaining lower estimations. Additional constrains are generated for initial problem, and algorithm operation is accelerated. The results of the computational experiments are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Задача размещения заказов и алгоритм ее решения An order allocation problem and an algorithm used to solve it Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Задача размещения заказов и алгоритм ее решения |
| spellingShingle |
Задача размещения заказов и алгоритм ее решения Бойко, В.В. Кузьменко, В.Н. |
| title_short |
Задача размещения заказов и алгоритм ее решения |
| title_full |
Задача размещения заказов и алгоритм ее решения |
| title_fullStr |
Задача размещения заказов и алгоритм ее решения |
| title_full_unstemmed |
Задача размещения заказов и алгоритм ее решения |
| title_sort |
задача размещения заказов и алгоритм ее решения |
| author |
Бойко, В.В. Кузьменко, В.Н. |
| author_facet |
Бойко, В.В. Кузьменко, В.Н. |
| publishDate |
2005 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
An order allocation problem and an algorithm used to solve it |
| description |
The paper considers an order allocation problem with a discounts objective function and investigates its features. An algorithm solving this problem is proposed. Such an algorithm includes the ralgorithm for obtaining lower estimations. Additional constrains are generated for initial problem, and algorithm operation is accelerated. The results of the computational experiments are given.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84933 |
| citation_txt |
Задача размещения заказов и алгоритм ее решения / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 113-119. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT boikovv zadačarazmeŝeniâzakazovialgoritmeerešeniâ AT kuzʹmenkovn zadačarazmeŝeniâzakazovialgoritmeerešeniâ AT boikovv anorderallocationproblemandanalgorithmusedtosolveit AT kuzʹmenkovn anorderallocationproblemandanalgorithmusedtosolveit |
| first_indexed |
2025-11-24T11:37:31Z |
| last_indexed |
2025-11-24T11:37:31Z |
| _version_ |
1850845436919676928 |
| fulltext |
Теорія оптимальних рішень. 2005, № 4 113
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача разме-
щения заказов с целевой функцией,
описывающей наличие скидок. Ис-
следуются особенности этой за-
дачи, предлагается алгоритм ее
решения, включающий использо-
вание r-алгоритма. Генерация до-
полнительных ограничений для
исходной задачи позволяет суще-
ственно ускорить работу алго-
ритма. Приводятся результаты
вычислительных экспериментов.
В.В. Бойко, В.Н. Кузьменко,
2005
ÓÄÊ 519.8
Â.Â. ÁÎÉÊÎ, Â.Í. ÊÓÇÜÌÅÍÊÎ
ÇÀÄÀ×À ÐÀÇÌÅÙÅÍÈß ÇÀÊÀÇÎÂ
È ÀËÃÎÐÈÒÌ ÅÅ ÐÅØÅÍÈß
Введение. Несмотря на многолетний опыт
изучения задач размещения и большое коли-
чество работ, посвященных этому вопросу
[1-5], практические задачи размещения могут
иметь особенности, которые ранее не изуча-
лись. Исследование таких особенностей по-
зволяет построить эффективные алгоритмы
решения новых задач, а также улучшить
предложенные ранее подходы к решению.
В работе [6] рассматривалась задача раз-
мещения заказов с новым видом целевой
функции и ограничений и исследовалась
эффективность применения r-алгоритма [7]
для вычисления оценок в сравнении с тради-
ционно применяемым "простым" субгради-
ентным методом [8]. Проведенные вычисли-
тельные эксперименты показали, что для оп-
ределенных вариантов постановок задач эф-
фективность r-алгоритма выше, чем "просто-
го" субградиентного метода.
В данной работе исследуются особенности
задачи размещения заказов и предлагаются
дополнительные процедуры к традиционной
схеме решения [9]. К особенностям задачи
относятся свойства целевой функции и связь
между коэффициентами целевой функции и
ограничений.
Рассматриваемая задача имеет и приклад-
ное значение. В виде подобной задачи можно
описывать размещение заказов при модели-
ровании процессов в энергетике.
Постановка задачи. Имеется m заказов.
Их необходимо оптимально разместить не
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
114 Теорія оптимальних рішень. 2005, № 4
более, чем у n поставщиков, каждый из которых предоставляет определенные
скидки, зависящие от суммы заказа. Рассматриваются два базовых вида скидок
и их комбинации (рисунок).
Рисунок. Базовые виды скидок
Рассматриваемые функции имеют такие особенности:
а) при наличии скидок вида А функции разрывны, т. е. не выпуклы и не во-
гнуты;
б) для любых видов скидок и их комбинаций справедливо: рост функций
вправо от любой точки происходит не быстрее, чем на линейном отрезке, со-
держащем эту точку.
Математическая постановка задачи, отражающая наличие скидок, такова:
+∑ ∑∑
= = =
n
i
n
i
m
j
ijijii
xy
xcyf
iji 1 1 1
,
min , (1)
niyUxcyL ii
m
j
ijijii ,...,1,
1
=≤≤∑
=
, (2)
00 ,...,1,1
0
niy
d
iIi
i =≤∑
∈
, (3)
mjbx j
n
i
ij ,...,1,
1
=≥∑
=
, (4)
{ }1,0∈iy ; 0≥ijx , (5)
где },...,1{ 00 nI = - множество исходных поставщиков; d
i
I
0
- множество псевдо-
поставщиков, соответствующих скидкам функции исходного поставщика 0i .
При заданных ji ,0 коэффициенты ijc равны для всех d
i
Ii
0
∈ , а множители iα
образуют последовательность, такую, что
tiii α≥≥α≥α= ...1
21
.
Сумма заказа
Сумма
платежа
Скидки A Скидки B
Сумма заказа
Сумма
платежа
ЗАДАЧА РАЗМЕЩЕНИЯ ЗАКАЗОВ И АЛГОРИТМ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2005, № 4 115
Алгоритм решения. В основу алгоритма решения задачи (1) - (5) положен
подход, предложенный для простейшей задачи размещения в [9], и заключаю-
щийся в следующем.
Методом верхнего уровня является метод ветвей и границ. В каждой вер-
шине дерева ветвления вычисляется нижняя оценка путем решения двойствен-
ной задачи субградиентным методом. Двойственная задача получается в резуль-
тате лагранжевой релаксации исходной задачи по ограничениям (4). В процессе
решения двойственной задачи по возможности фиксируются значения еще не-
определенных переменных iy
и определяются наиболее узкие границы UL PP , , в
пределах которых лежит количество вершин размещения заказов в оптимальном
решении. Оптимальное решение находится путем генерации допустимых реше-
ний, соответствующих вершинам дерева ветвления.
Новым в данном алгоритме является использование особенностей задачи
для быстрой генерации допустимых решений и генерация дополнительных ог-
раничений двойственной задачи, увеличивающих оценку.
Сделанные фиксации и дополнительные ограничения верхних уровней учи-
тываются при формулировке оценочных задач последующих уровней дерева
ветвления.
Двойственная оценочная задача. Для нахождения нижней оценки для
вершины дерева ветвления решается следующая задача.
Найти
),(max),,,,(
0,0
10 βλ=Φ
≥β≥λ
FAKKPP
kj
UL , (6)
где значение двойственной функции
+β+λ=βλ ∑∑
==
N
k
kk
m
j
jj dbF
11
),(
λ−α+β−+ ∑ ∑∑∑
= = ==
n
i
n
i
m
j
ijjijii
N
k
kiki
xy
xcyaf
iji 1 1 11
,
)()(min (7)
при ограничениях
niyUxcyL ii
m
j
ijijii ,...,1,
1
=≤≤∑
=
, (8)
10 jij bx ≤≤ , mj ,...,1= , (9)
00 ,...,1,1
0
niy
d
i
Ii
i =≤∑
∈
, (10)
U
n
i
iL PyP ≤≤∑
=1
, (11)
{ } )(\,1,0 102 KKIKiyi ∪=∈∈ ; 0,0 Kiyi ∈= ; 1,1 Kiyi ∈= , (12)
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
116 Теорія оптимальних рішень. 2005, № 4
где 10 , KK - множества фиксированных и 2K - множество неопределенных пе-
ременных iy в текущей вершине дерева ветвления; A - матрица дополнитель-
ных ограничений ( dyA ≥ ), содержащая N строк сгенерированных ограничений
и n столбцов; jj bb ≥1 - превышение заказа, позволяющее использовать выиг-
рыш, предоставляемый скидками вида А.
Решение задачи (7) - (12) сводится к решению ряда "простых" задач рюк-
зачного типа:
Для каждого 0\ KIi ∈ найти
+β−=βλα ∑
=
N
k
kikii af
1
),(
∑
=
λ−+
m
j
ij
k
jij
x
xc
ij 1
)( min , (13)
при ограничениях
i
m
j
ijiji UxcL ≤≤∑
=1
, (14)
10 jij bx ≤≤ , mj ,...,1= . (15)
Для 0Ki ∈ положим
0),(;...,,1,0* =βλα== iij mjx .
Найти
+β+λ=βλ ∑∑
==
N
k
kk
m
j
k
jj dbF
11
),(
∑
∈
βλα+
Ii
ii
y
y
i
),(min , (16)
при ограничениях
00 ,...,1,1
0
niy
d
i
Ii
i =≤∑
∈
, (17)
U
n
i
iL PyP ≤≤∑
=1
, (18)
{ } 2,1,0 Kiyi ∈∈ , (19)
0,0 Kiyi ∈= ; 1,1 Kiyi ∈= .
Указанные задачи быстро решаются "жадным" алгоритмом.
Обозначим множество выбранных вершин размещения при текущих βλ,
{ }1| ** =∈= iyIiM .
Фиксация переменных iy . «Простота» задач (13) - (15) и (16) - (19) позво-
ляет в процессе решения задачи (7) - (12) легко проверять возможность допол-
нительно зафиксировать переменные iy для 2Ki ∈ на значениях, соответст-
вующих оптимальному решению исходной задачи [9]. Для переменных
*
2 MKi ∩∈ проверяется возможность зафиксировать 1=iy (close penalties),
для *
2 \ MKi ∈ соответственно – 0=iy (open penalties). В первом случае фор-
мально должна быть решена задача (16) - (19) при дополнительной фиксации
0=iy . Если Ui ZyF ≥≡βλ )0|,( , где UZ - значение наилучшего найденного
допустимого решения задачи (1) - (5), то фиксируется противоположное значе-
ЗАДАЧА РАЗМЕЩЕНИЯ ЗАКАЗОВ И АЛГОРИТМ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2005, № 4 117
ние 1=iy , если неравенство не выполняется, то переменная iy остается неза-
фиксированной. Во втором случае вычисляется )1|,( ≡βλ iyF и соответственно
фиксируется или нет 0=iy . Учитывая то, что задача (16) - (19) решена и из-
вестно множество *
M , проверка указанного неравенства выполняется путем не-
скольких арифметических операций.
Фактически выполняя такие проверки, мы оцениваем другие ветви дерева,
отличающиеся от рассматриваемой одной дополнительно фиксированной пере-
менной. Причем выбираются такие ветви, которые при заданных βλ, имеют не
меньшее значение функции ),( βλF , чем текущая. Если неравенство выполняет-
ся и переменная фиксируется, то происходит сокращение дерева перебора и
улучшение оценки текущей и последующих ветвей.
Сжатие границ LP , UP . Проверка возможности сжать границы LP , UP
выполняется в процессе решения задачи (16) - (19) и не требует отдельной про-
цедуры. Формально необходимо решить ряд задач (16) - (19) при дополнитель-
ном условии ty
n
i
i =∑
=1
, для всех [ ]UL PPt ,∈ . В результате будут найдены зна-
чения )|,( tF βλ . Новые границы определяются максимальным интервалом
[ ]21, tt , таким, что [ ]21, ttt ∈∀ UZtF <βλ )|,( .
Генерация матрицы дополнительных ограничений A .
В результате выполнения процедур для фиксации переменных может ока-
заться, что ни одна из переменных iy 2Ki ∈ не стала фиксированной. В этом
случае будем проверять возможность одновременно фиксировать переменные,
принадлежащие некоторым множествам *
21 MKM ∩⊆ или *
20 \ MKM ⊆ .
Для 1M выполняется проверка Ui ZMiyF ≥∈≡βλ ),0|,( 1 , для 0M –
Ui ZMiyF ≥∈≡βλ ),1|,( 0 . Если неравенство выполняется, то в матрицу A до-
бавляется ограничение 1
1
≥∑
∈Mi
iy или 10
0
−≤∑
∈
My
Mi
i соответственно. Эффек-
тивность таких ограничений зависит от количества элементов в множествах
01, MM . Чем меньше это количество, тем ограничение эффективнее. Поиск
множеств 01, MM начинается с включения соответственно первого и последне-
го элементов из упорядоченного списка множества 2K , полученного при реше-
нии задачи (16) - (19). Далее включаются следующие элементы, выполняются
проверки и т.д. Такой поиск множеств 01, MM , как правило, приводит к успеху,
и в двойственную задачу включаются дополнительные ограничения.
Генерация допустимых решений. Для генерации допустимого решения,
соответствующего вершине дерева ветвления, решим такую задачу:
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
118 Теорія оптимальних рішень. 2005, № 4
∑ ∑∑
∈ =∈
+=
** 1
* min)(
Mi
m
j
ijij
x
Mi
i xcfMZ
ij
, (20)
*
1
, MixcL
m
j
ijiji ∈≤∑
=
, (21)
mjbx j
Mi
ij ,...,1,
*
==∑
∈
, (22)
*,0 Mixij ∈≥ . (23)
В отличие от исходной постановки (1) - (5) здесь нет верхних границ в огра-
ничениях (21) и ограничения (22) записаны в форме равенства. Если для опти-
мального решения задачи (20) - (23) окажется, что iijij Uxc >∑ для некоторого
подмножества {} UMi = , то существует другое допустимое решение с меньшим
значением целевой функции, в котором псевдопоставщики UMi ∈ заменены
следующими псевдопоставщиками. Если задача (20) - (23) не имеет допустимо-
го решения, то при замене ограничений (22) на соответствующие неравенства
оптимальное значение станет равно )()(
*
*
i
Mi
i LfMZ += ∑
∈
. Поэтому должна ис-
следоваться задача поиска допустимого решения именно в постановке (20)-(23).
Вычислительные эксперименты. Для проведения вычислительных экспе-
риментов были взяты те же тестовые задачи, что и в работе [6]. Результаты экс-
периментов показали, что генерация матрицы дополнительных ограничений по-
зволяет снизить суммарные вычислительные затраты за счет сокращения разме-
ра дерева ветвления и сделать процесс поиска решения более быстрым по срав-
нению с традиционной схемой решения. В таблице приведены результаты этих
экспериментов для задачи Cap131 из библиотеки OR-Library.
Вид и процент
скидок
Традиционная схема
решения задачи.
Исходная постановка
(∑ Xij ≥ bj)
Схема
решения с использование дополни-
тельных ограничений.
Исходная постановка
(∑ Xij ≥ bj)
"Простой" метод
(время, с)
r-алгоритм
(время, с)
"Простой" метод
(время, с)
r-алгоритм
(время, с)
Тип A, 25 191 133 147 121
Тип A, 40 548 545 466 425
Тип A, 50 1413 2492 1167 1955
Тип A, 60 1702 2231 1246 1958
Тип A, 75 1082 1037 845 916
Тип А, 100 275 110 251 86
Тип А и B, 25 126 90 98 76
Тип А и B, 50 106 43 79 34
ЗАДАЧА РАЗМЕЩЕНИЯ ЗАКАЗОВ И АЛГОРИТМ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2005, № 4 119
Заключение. В результате выполненной работы получен новый, более бы-
стрый по сравнению с "традиционными" алгоритм решения рассмотренной за-
дачи размещения заказов. Развитие работы будет направлено на исследование
эффективности предложенного алгоритма при решении других задач размеще-
ния и, в частности, при моделировании процессов в энергетике.
В.В. Бойко, В.М. Кузьменко
ЗАДАЧА РОЗМІЩЕННЯ ЗАМОВЛЕНЬ ТА АЛГОРИТМ ЇЇ РОЗВ’ЯЗУВАННЯ
Розглядається задача розміщення замовлень з цільовою функцією, яка відображає наявність
знижок. Досліджуються особливості цієї задачі та пропонується алгоритм її розв’язування,
який включає використання r-алгоритму. Генерування додаткових обмежень для початкової
задачі дозволяє суттєво прискорити работу алгоритма. Наводяться результати обчислюваль-
них експериментів.
V.V. Boyko, V.N. Kuzmenko
AN ORDER ALLOCATION PROBLEM AND AN ALGORITHM USED TO SOLVE IT
The paper considers an order allocation problem with a discounts objective function and investi-
gates its features. An algorithm solving this problem is proposed. Such an algorithm includes the r-
algorithm for obtaining lower estimations. Additional constrains are generated for initial problem,
and algorithm operation is accelerated. The results of the computational experiments are given.
1. Revelle C.S., Laporte G. The Plant Location Problem: New Models and Research Pros-
pects // Operations Research. – 1996. – 44. – P. 864–874.
2. Correia I., Captivo M.E. A lagrangian heuristic for modular capacitated location problem //
Annals of Operations Research. – 2003. – 122. – P. 141–161.
3. Harkness J., ReVelle C. Facility location with increasing production cost // European
J. of Operational Research. – 2003. – 145. – P. 1–13.
4. Ebery J., Krishnamoorthy M., Ernst A., Boland B. The capacitated multiple allocation hub
location problem: Formulations and algorithms // Ibid. – 2000. – 120. – P. 614–631.
5. Goldengorin B., Kuzmenko V., Stetsyuk P., Tso M. Pricing by an allocation model with dif-
ferent types of discount // Combinatorial Optimization 2004, 28-31 March 2004, Book of
Abstract. – Lancaster: Lancaster University, 2004. – P. 31.
6. Кузьменко В.Н., Гольденгорин Б.И., Тсо М., Стецюк П.И. Сравнение двух субгради-
ентных методов при нахождении оценок для задач размещения // Теория оптималь-
ных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2004. –
С. 108-116.
7. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. –
Киев: Наук. думка, 1979. – 200 с.
8. Held M., Wolfe P., Crowder H. Validation of subgradient optimization // Mathemetical
Programming. – 1974. – N 6. – P. 62–66.
9. Beasley J.E. Lagrangian heuristics for location problems // European J. of Operational Re-
search. – 1993. – 65. – P. 383-399.
Получено 01.04.2005
|