Сетевые постановки транспортных задач

Пусть транспортная сеть состоит из пунктов, соединенных направленными дугами (p_i, p_j), , . Пусть [0, T] – интервал оптимизации функционирования промышленно-транспортной системы (ПТС). Для каждого момента времени на множестве P пунктов сети определена функция производства и потребления q_i(t). Если , то пункт производства p_i называется источником, если , то пункт потребления p_j называется стоком, и если , то пункт p_i называется перевалочным, t=0,1,…,T. Каждый путь (p_i, p_j) характеризуется пропускной способностью , и транспортным запаздыванием . При i=jd_ii(t) означает величину емкости склада пункта p_i. Обозначим через U_ij(t), t = 0,1,…,T объем поставок на пути (p_i, p_j), выходящий в момент t из пункта p_i и приходящий в момент t + t_ij в пункт p_j. Если путь (p_i, p_j) отсутствует или t + t_ij > T, то полагаем U_ij(t) = 0. Ясно, что все U_ij(Т) = 0, . Поставка U_ii(t) означает запас пункта p_i в момент t. Поэтому t_ii = 1. Пусть c_ij(t), , расходы на перевозку единицы объема поставок из момента p_i. Для каждого пункта потребления p_j период, в течении которого отсутствуют поставки, равен [0, t_i – 1], где t_i = min(t_ji), . Будем предполагать, что запаса в нулевой момент времени нет, т.е. справедливо

.

Задача оптимизации функционирования промышленной транспортной системы ставится как задача минимизации суммарных транспортных расходов и расходов на хранение.

.

Ограничения:

,

,

,

, ,

.

Задачу будем называть динамической транспортной задачей (ДТЗЗ) в сетевой постановке. Очевиден содержательный смысл ограничений: уравнение является балансным соотношением; неравенство означает неотрицательность поставок, ограниченных пропускными способностями коммуникаций; время прибытия и время отправления поставок должны принадлежать интервалу оптимизации [0, T]; условия являются начальными и конечными условиями на запасы.

Учитывая ограничения и суммируя по t уравнение , получим для каждого пункта p_j соотношение

.

Суммированием по i соотношения получим уравнение

,

доставляющее необходимое условие разрешимости ДТЗЗ в сетевой постановке.