Динамическая транспортная задача с задержками

Пусть транспортная система связывает m пунктов производства A_i, i=1,…, m, и n пунктов потребления B_j, j=1,…,n. Предполагается, что каждый пункт производства A_j соединен коммуникациями со всеми пунктами потребления B_j. Для каждого момента времени обозначим:

a_i(t) – объем производства;

x_i^A(t) – запас в пункте производства A_i;

B_j(t) – спрос;

x_j^B(t) – запас в пункте потребления B_j;

- объем поставок, выходящий в момент t из A_i в B_j;

- объем поставок, поступающий в момент t из A_i на B_j;

- приведенные транспортные расходы;

, - приведенные расходы на хранение соответственно в пунктах A_i и B_j.

Время движения из A_i в B_j обозначим t_ij и будем называть задержкой (транспортным запаздыванием); считаем, что для всех i=1,…,m, j=1,…,n. Если же в момент t движение между пунктами A_i и B_j закрыто, то перевозка не рассматривается.

Будем исследовать режим работы, в котором каждый пункт потребления B_j имеет возможность получать поставки из всех пунктов производства A_i, в моменты времени T₀, T₀₊₁,… T₀+T-1. Интервал оптимизации всех пунктов потребления равен [T₀, T₀+T-1] и состоит из T тактов. В нашем случае каждый пункт производства должен иметь возможность сделать T поставок в каждый пункт потребления, и потому интервал времени работы поставщика A_j на потребителя B_j равен [T₀-t_ij, T₀-t_ij+T-1]. Объединяя все указанные интервалы, получим общий интервал функционирования поставщика

,
где T_i = max(t_ij,…, t_in), t_i = min(t_i1,…, t_in)

Отметим, что периоды оптимизации поставщиков в общем случае различны и смещены во времени. Если все задержки t_ij одинаковы, то интервалы, оптимизации поставщиков равны и состоят (так же, как и для потребителей) из T тактов. Если же задержки t_ij=0, то интервалы оптимизации поставщиков и потребителей совпадают. Такой режим работы изучался, например, в /4, 5/.

Поставщик A_i может сделать поставку в момент T₀-T_i+t_i в пункт потребления B_j, если этот момент времени входит в интервал [T₀-t_ij, T₀-t_ij+T-1] обслуживания пунктом A_i пункта B_j. Другими словами, должно выполнятся неравенство: T₀-T_j£T₀-T_i+t_j£T₀-t_ij+T-1, или, что тоже самое: T_i-t_ij£t_i£T_i-t_ij+T-1. Поставка , разрешенная в момент T₀-T_i+t_i , из A_i в B_j придет в момент времени T₀+t=T₀-T_i+t_i+t_ij. Текущее время t потребителей связано с текущим временем t_i поставщика A_i соотношением , а объемы поставок и объемы получения - соотношением .

Обозначим через G_i(T₀-T_i+t_i) множество индексов j пунктов потребления B_j, в которые пункт A_i в момент времени T₀-T_i+t_i может выполнить поставки, прибывающие в эти пункты не ранее момента времени T₀ и не позднее T₀+T-1. Для фиксированных i и t_i индекс j принадлежит множеству G_i(T₀-T_j+t_i), если справедливо неравенство T_i£t_i+t_ij£T_j+T-1, множества G_i(T₀-T_i+t_i) совпадают со множеством всех индексов j=1,…,n.

Общий интервал оптимизации системы поставщиков равен объединению всех интервалов оптимизации поставщиков

,
где .

Таким образом, предлагаемый режим работы приводит к функционированию системы потребителей B_j, j=1,…,n, в интервале [T₀,T₀+T-1], системы поставщиков – в интервале и транспорта – в интервале .

Возможны и другие режимы работы. Например, система поставщиков имеет один и тот же интервал оптимизации [0, T-1], а интервалы оптимизации потребителей могут быть равными по продолжительности, но смещенными во времени и т.д.

В описываемом режиме функционирования и при заданных программах поставщиков и потребителей оптимизация перевозок рассматривается как задача минимизации функционала транспортных расходов и суммарных расходов на хранение

,

при ограничениях, задаваемых:

а) уравнениями динамики запасов у поставщиков и потребителей

,

,

б) уравнением связи поставщиков и потребителей

,

в) начальными и конечными условиями

,

г) условиями неотрицательных запасов и перевозок

, (15)

, (16)

. (17)

Если все транспортные задержки нулевые или совпадают, то постановка превращается в ДТЗ. Сформулированную задачу будем называть динамической транспортной задачей с задержками (ДТЗЗ).

Уравнение динамики изменения суммарного объема запасов

,

используется для сведения ДТЗ к серии СТЗ. В /4/ ДТЗ характеризуется как общая задача линейного программирования, и для ее решения предлагается метод динамического линейного программирования, учитывающий специфику ДТЗ