close

Вход

Забыли?

вход по аккаунту

?

Стохастическая постановка динамической транспортной задачи с задержками с учетом случайного разброса времени доставки и времени потребления..pdf

код для вставкиСкачать
СТОХАСТИЧЕСКАЯ ПОСТАНОВКА
ДИНАМИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ
С ЗАДЕРЖКАМИ С УЧЕТОМ
СЛУЧАЙНОГО РАЗБРОСА ВРЕМЕНИ ДОСТАВКИ
И ВРЕМЕНИ ПОТРЕБЛЕНИЯ
случайных отклонений от планового ритма потребления. Учет
случайного разброса параметров требует стохастической постановки ДТЗЗ.
Для формирования задачи оптимизации в стохастической
постановке необходимо сделать анализ взаимодействия отправителя и получателя в случайной среде. Сделаем это на примере
взаимодействия распределительного склада со складом у получателя.
Александров А.Э.
(УрГУПС, Екатеринбург)
AAlexandrov@controlling.su
Якушев Н.В.
(УрГУПС, Екатеринбург)
yak@ural-trans.ru
Множество задач оптимального управления потоками может быть эффективно решено на основе применения подхода
под общим названием «Динамическая транспортная задача с
задержками» (ДТЗЗ). ДТЗЗ впервые была разработана доктором
технических
наук,
лауреатом
государственной
премии
П.А.Козловым. Указанный подход представляет собой развитие
содержательной постановки задачи линейного программирования в динамическую область. Под «динамикой» здесь понимается учет фактора времени при формировании структуры задачи –
продолжительности доставки, распределения объемов производства и потребления во времени, изменение запасов продукта
в конечных и промежуточных пунктах. Примерами решаемых
задач может служить расчет планов подвода порожняка в соответствии с ритмом погрузки, планов согласованного подвода
грузов к морским портам, подвода сырья к крупным потребителям, подвода маршрутов с энергоносителями к ТЭЦ и т.п.
Бурное развитие логистики в последнее десятилетие побуждает к исследованию возможностей применения данного
подхода и в транспортно-складских системах. Здесь важно
учесть не только транспортные расходы, но и потери на стыке
транспорт – потребитель. Потери на стыке могут возникать как
следствие случайного разброса времени доставки грузов и
5
Рис. 1. Структура потерь при фиксированном спросе
и случайном времени хода
1. Детерминированный спрос и случайное время
доставки
Пусть время доставки τ ij (t ) поставки u ij (t ) имеет случайный разброс (рис. 1), то есть в каждый момент отправления t оно
будет τ ij ± ϕ j (t ) , где τ ij – нормативное значение, ϕ j (t ) – случайная величина. В этом случае, если время доставки будет
(τ ij − ϕ j (t )) , возникнет раннее прибытие и, соответственно,
дополнительное
6
хранение
груза.
Если
же
время
будет
(τ ij + ϕ j ( t )) , то появляется эффект позднего прибытия и будет
от недопоставки. При позднем потреблении ( t j + ϕ *j (t )) и пла-
ущерб от недопоставки (в общем случае). Случайная величина
ϕ (t ) имеет какое-то распределение. При этом, как правило,
удельная стоимость хранения c1 значительно меньше удельного
ущерба от недопоставки c2 . ДТЗЗ в стохастической постановке
должна учитывать этот эффект (будет рассмотрено ниже).
новом прибытии – затраты на дополнительное хранение.
2. Детерминированное время хода и случайный спрос
Рис. 3. Взаимодействие складов при случайном разбросе во
времени доставки и времени потребления
3. Случайное время хода и случайное потребление
Здесь накладываются друг на друга два случайных процесса
(рис. 3). Поставка u ij (t ) может придти с опережением –
Рис. 2. Структура потерь при детерминированном времени
доставки и случайном спросе
( tij − ϕ j ( t )) и с опозданием – ( tij + ϕ j (t )) . В свою очередь,
В этом случае эффекты аналогичны предыдущему примеру,
хотя причины различны (рис. 2). Отклонение времени потребления от планового ϕ *j (t ) имеет случайный характер. Случайная
величина ϕ *j ( t ) имеет некоторое распределение. При раннем
потреблении (t j − ϕ *j (t )) и плановом прибытии возникнет ущерб
7
момент потребления может быть раньше планового –
(t j − ϕ *j (t )) и позже – (t j + ϕ *j (t )) . Случайные величины ϕ j (t ) и
ϕ *j (t ) имеют свои распределения. Для упрощения постановки
задачи оптимизации взаимодействия складов в стохастической
постановке желательно два случайных процесса свести к одному. Трудность, однако, возникнет в том, что опережение во
8
времени прибытия и опережение в потреблении приводит к
разным последствиям. В первом случае возникают дополнительные затраты на хранение, а во втором – ущерб от недопоставки.
Но возможны различные сочетания.
Рис. 5. Увеличение потерь при несовпадающем характере
отклонения во времени прибытия и потребления
Б) Несовпадающий характер отклонений.
При раннем прибытии (τ ij − ϕ j (t )) и позднем потреблении
Рис. 4. Уменьшение потерь при совпадающем характере
отклонения во времени прибытия и потребления
( t j + ϕ *j (t )) возникают большие затраты на хранение (рис. 5а).
А) Совпадающий характер отклонений.
При раннем прибытии и раннем потреблении ущербы
уменьшаются (рис. 4а). Возможно даже полное совпадение, при
котором дополнительные потери исчезают. Конечно, в зависимости от степени опережения в этих двух процессах будут либо
дополнительные затраты на хранение, либо дополнительный
ущерб от недопоставки.
Аналогичные эффекты возникают и при совпадающем отклонении – опоздании во времени прибытия и времени потребления (рис. 4б).
9
Наоборот, при позднем прибытии (τ ij + ϕ j (t )) и раннем потреблении (t j − ϕ *j (t )) будет большой ущерб от недопоставки (рис.
5б). Поэтому имеется определенная трудность в наложении этих
двух случайных процессов.
Можно было бы перейти от величины ϕ *j ( t ) к величине
( −ϕ *j (t )) . Тогда отклонение в одну и туже сторону случайных
величин ϕ j (t ) и ( −ϕ *j (t )) приводит к одному и тому же содержательному эффекту. При отклонении от момента планового
10
потребления в сторону «раньше» – дополнительные затраты на
хранение, в сторону «позже» – ущерб от недопоставки, то есть
мы переходим к задаче с детерминированным временем доставки τ ij и случайном разбросе во времени потребления
( t j ± ϕ j (t )) , где случайная величина ϕ j (t ) описывает комбинацию двух случайных процессов.
Стохастическую постановку ДТЗЗ будем формулировать
следующим образом – найти оптимальную по минимуму суммарных затрат на перемещение и простои динамическую структуру потоков с учетом ущерба от недопоставок при случайном
разбросе в потреблении. Разброс во времени хода мы включили
в разброс в потреблении. То есть функционал примет вид
J 1 + J 2 + J 3 + J 4 → min ,
T
где J 1 = ∑
∑
cij ( t )uij (t )
t =0 pi , p j ∈Ρ
J
2
=
Τ
∑ ∑
– транспортные расходы,
«центр распределения» нецелесообразно. Очевидно, что груз в
этом случае необходимо поставлять с некоторым запасом времени, чтобы суммарные потери от случайного разброса J 3 + J 4
были минимальными. Обоснуем выбор точки рационального
прибытия t0 . Рассмотрим это для примера единичной поставки
u ij ( t ) = 1 (строгость вывода от этого не пострадает). Пусть
готовность к потреблению описывается функцией плотности
распределения вероятности ϕ (t ) . Если t < t0 , возникает ущерб
от недопоставки. Если ущерб пропорционален ( t − t0 ) , то матеt0
матическое ожидание потерь будет равно
3
∞
штраф от простоя груза на складе ∫ ϕ ( t )c2 (t − t0 ) dt .
t0
c ii ( t ) u ii ( t ) – затраты на хранение запасов.
t =0 pi∈Ρ
=
t0
∫ u ij ( t ) c 1 ( t 0
С2
С1
− t ) dt ,
−∞
а дополнительные затраты на хранение
∞
t0 M
J 4 = ∫ uij (t )ϕ ( t )c2 (t − t0 )dt .
t0
Так как единичный ущерб от недопоставки c1 , как правило,
больше единичных затрат на хранение, то привозить груз в
11
В
случае, когда груз придет раньше того времени, когда производство будет готово его принять (правее точки t0 ), мы получаем
Составляющие J 3 и J 4 зависят от вида и параметров закона распределения. Если груз прибыл в момент t0 и момент
потребления t должен был произойти раньше (t < t0 ) , то возникает ущерб от недопоставки, а если t > t0 , то появляется дополнительные затраты на хранение. Пусть c1 – единичный ущерб от
недопоставки, c2 – единичные затраты на хранение грузов,
тогда ущерб от недопоставки равен
J
∫ ϕ (t ) c1 ( t0 − t ) dt .
−∞
Рис. 6. Определение наивыгоднейшего t0
12
Таким образом, общее математическое ожидание штрафа
при подводе груза к точке потребления t0 будет равно
Ф=
∞
t0
∫ ϕ (t ) ⋅C1 (t0 − t )dt
+ ∫ ϕ ( t ) ⋅C 2 (t − t0 )dt =
−∞
t0
∂Φ
= − C2 + (C1 + C 2 ) ∫ ϕ (t ) ⋅dt + (C1 + C 2 )t0ϕ ( t0 ) ∂t0
−∞
(C1 + C2 )t0ϕ (t0 ) .
t0
t0
∞
−∞
t0
t0
∞
= C1t0 ∫ ϕ ( t ) ⋅dt – C1 ∫ ϕ ( t )tdt – C 2 t0 ∫ ϕ (t ) ⋅dt + C 2 ∫ ϕ (t )tdt =
−∞
t0
t0
∂Φ
= − C 2 + (C1 + C 2 ) ∫ ϕ (t ) ⋅dt = 0 ,
∂t0
−∞
или


= t0  C1 ∫ ϕ (t ) dt − C2 ∫ ϕ (t )dt  – C1 ∫ ϕ (t )tdt + C2 ∫ ϕ (t )t dt (*)
 −∞

t0
−∞
t0


∞
t0
∞
t0
∞
Так как
∫ ϕ (t )t dt
есть ничто иное, как определение мате-
−∞
∫ ϕ ( t ) ⋅dt = 1 ,
легко в подынтеграль-
−∞
ных выражениях можно перейти к одному интервалу интегрирования:
t0
t0
∞


C 2 ∫ ϕ (t )t dt = C 2  M − ∫ ϕ (t )t dt  = C 2 M – C 2 ∫ ϕ (t )tdt
t0
−∞
−∞


∞
t
C 2 ∫ ϕ ( t ) ⋅dt = C2 – C2 ∫ ϕ ( t ) ⋅dt
t0
t0
 t0

Ф = t0  C1 ∫ ϕ (t )dt − C 2 + C2 ∫ ϕ ( t )dt  – C1 ∫ ϕ ( t )tdt + C2 M –
 −∞

−∞
−∞


t0
– C 2 ∫ ϕ ( t )tdt = C2 (M − t0 ) + (C1 + C 2 )t0 ∫ ϕ (t ) ⋅dt –
−∞
Таким образом, мы получили условие минимума функционала, достигаемое в такой точке t0 , для которой
t0
C2
1 + C2
∫ ϕ (t )dt = C
−∞
Действительно, при значениях C2 , значительно превышающих C1 , выражение
t0
∫ ϕ ( t ) ⋅dt
должно быть ближе к единице,
чтобы минимизировать большие штрафы по C2 . И, наоборот,
при значениях C1 , значительно превышающих C2 , подынтегральное выражение должно быть ближе к нулю, то есть минимизировать большие штрафы по C1 .
Таким образом, в случае со случайным разбросом динамическая задача в стохастической постановке организует прибытие
с запасом времени в зависимости от величины возможного
ущерба.
Подставляя полученные выражения в (*), получаем:
t0
= C2
−∞
−∞
t0
t0
(C1 + C 2 ) ∫ ϕ (t ) ⋅dt
−∞
∞
матического ожидания, а
Наша задача – найти такое значение t0 , при котором значение Ф достигает своего минимума. Поэтому берем производную
Ф по t0 и приравниваем ее к нулю.
−∞
t0
– (C1 + C 2 ) ϕ (t )tdt
∫
−∞
13
14
1/--страниц
Пожаловаться на содержимое документа