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

 

 

Пусть структура транспортной системы состоит из B = {B₁, B₂ … B_N} бункеров, которые пронумерованы индексами i,j = 1…N. Бункера соединяются каналами (i, j), исходящими из i-го бункера и входящими в j-й бункер сети. Задан период оптимизации [0, T] функционирования транспортной системы и точки , разбивающие период [0, T] на интервалы, называемые шагом дискретизации. В дальнейшем моменты времени, отождествляемые с их номерами n, будем обозначать через t. При построении динамической сети каждый бункер заменяется на множество бункеров . Для каждого момента времени на множестве бункеров сети определена функция производства и потребления . Индексом m = 1…M обозначается вид потока (груза), транспортируемого по сети. Если , то бункер пунктом производства m-вида потока, а при - его потребителем. В случае, когда , бункер является перевалочным пунктом. Задано время , затрачиваемое вагонами m-вида потока на проход по каналу от i-го бункера к j-му. Через обозначим вагонопоток по каналу (i, j), выходящий из бункера B_i в бункер B_j в момент t и входящий в последний момент времени t + t_ij. На сети это учитывается следующим образом. Если время хода из бункера B₁ в бункер B₃ равно 2, то поставка, вышедшая из B₁ в момент времени t = 0, поступит в бункер B₃ в момент t = 2 (рис. 5). Если время прибытия поставки выходит за пределы расчетного прибытия, то есть t + t_ij > T, то поставка не рассматривается. Например, если T = 4, то поставка, вышедшая из B₁ в B₃ в момент времени t = 3, не рассматривается, поскольку t + t₁₃ = 5. Состояние бункеров обозначается , что означает запас (остаток) вагонов m-вида потока в бункере B_i с момента времени t –1 до момента t. Возникает петля от бункера к самому себе (рис. 4), но в другой момент времени. При размножении сети во времени петля превращается в обычную дугу (от к , от к и т.д.). Отсюда t_ii = 1.

 

 

Рис. 4.

Схема адаптивной структуры транспортного объекта (пространственная сеть)

 

 

Рис. 5.

Схема адаптивной структуры транспортного объекта (пространственно-временная сеть)

Для каналов определены наличные пропускные способности d_ii(t), зависящие от времени. При i = j величина d_ii(t) означает емкость бункера B_i от момента времени t –1 до t.

Для каждого момента времени t в зависимости от груза задана стоимость транспортировки единицы потока по каналу и стоимость нахождения ее в бункерах .

Известная задача оптимизации функционирования транспортной системы ставится как задача минимизации суммарных транспортных расходов и расходов на хранение (простой) вагонов в бункерах

при условиях, задаваемых

а) уравнением динамики запасов m-вида потока в бункерах

.

При этом:

- рассматриваются только те поставки, которые начинаются и заканчиваются в периоде оптимизации, т.е.

, ;

- состояние бункеров в нулевой момент времени определяется через начальные запасы m-вида потока, т.е.

;

- обязательным является условие неотрицательности вагонопотоков, так как в противном случае задача теряет практический смысл

.

б) уравнением непревышения вагонопотоком пропускной способности канала

Задача является известной многопродуктовой транспортной задачей на сети, в которой пропускная способность каналов и вместимость бункеров хотя и допускает изменение во времени, но задается априори. В модели же необходимо отразит то положение, что пропускную способность каналов и вместимость бункеров можно увеличить за счет уменьшения этих параметров в других элементах, либо варьировать пропускную способность канала на каком-то отрезке времени. Для этого на динамической сети вводятся связи адаптации. Через обозначим поток пропускной способности, выходящий в момент времени t из канала (i, j) в канал (k, l). Содержательно, при i=j величина означает поток емкости в бункер. Если же i=j и k=l, то - означает поток емкости из одного бункера в другой. В случае (i, j) = (k, l) величина есть поток пропускной способности, передаваемый в канале из одного периода в другой. Для каждой связи задается коэффициент замещения . Учитывается время , необходимое для переброски пропускной способности с одного элемента на другой. Другими словами, если пропускная способность канала (i, j) уменьшилась в момент t на величину , то пропускная способность канала (k, l) возрастет на величину в момент времени . Так, если время на переброску пропускной способности из канала, соединяющего бункера B₁ и B₂, в канал между бункерами B₁ и B₃ составляет 1 такт, то на пространственно-временной сети переброска отобразится связью от дуги к дуге , далее от дуги к дуге и т.д., как показано на рис 5. Подобным образом на динамической сети вводятся связи между другими элементами структуры. Поскольку в качестве критерия о целесообразности технологического воздействия на параметры структуры используется стоимостной критерий, вводится переменная , означающая стоимость переброски единицы пропускной способности или емкости.

В качестве нового ограничения следует принять динамику пропускной способности

.

При этом в сеть включаются только те связи адаптации, которые начинаются или заканчиваются в пределах расчетного периода

, .

Начальное распределение пропускных способностей по каналам и емкостей по бункерам в новой постановке ставится

как задача расчета в динамике оптимальных транспортных потоков, остатков вагонов в парках и построения оптимальной динамической структуры при минимуме суммарных расходов

,

где F₂ – расходы на перераспределение мощности между элементами существующей структуры за расчетный период:

,

при ограничениях.

Наличие условия не позволяет применять для решения задачи потоковые алгоритмы на графах.

При формировании критерия оптимальности принимаются во внимание только предстоящие эксплуатационные затраты. Расходы F₁, связанные непосредственно с доставкой вагонов от поставщика потребителю, могут быть аппроксимированы линейной зависимостью, хотя при этом теряются некоторые факторы, нарушающие линейность. Затраты F₂ на проведение мероприятий по перераспределению мощностей между транспортными устройствами, как показало изучение оптимизирующего процесса, также могут быть выражены линейной функцией переменных . Поэтому в силу линейности функционала и ограничений МОДУС является общей задачей линейного программирования с ограничениями типа равенств и неравенств.

 

Метод решения

Для решения задачи необходимо построить матрицу ограничений . Вид этой матрицы удобно описать в терминах, так называемых, блочных или клеточных матриц. Рассечем с помощью горизонтальных и вертикальных линий матрицу на прямоугольные блоки: каждый блок сам представляет собой матрицу.

 

Опишем подробнее структуру матрицы ограничений в аспекте оценки ее максимальной размерности.

Для построения блока образуем вектор запасов размера :

 

 

и вектор поставок размерности :

 

 

Блок строится из условия

 

,

где

 

Конструкцию блока можно представить следующим образом.

 

Через обозначена единичная матрица . Незаполненный блок в соответствует вектору - столбцу поставок . Если поставка разрешена , т.е. то ей в строке – уравнении соответствует – I. В столбцах блока могут стоять только +I, -I и 0.

Для построения блока образуем вектор пропускных способностей размера

 

Вектор переменных изменения пропускных способностей размера имеет вид

 

и далее для

Блок строится из условия

,

где

.

Блок имеет структуру, аналогичную блоку . При этом используется единичная матрица размера . Блок, соответствующий вектору , строится аналогично, как и блок в , соответствующий вектору . В столбцах блока стоят одна единица, одна минус единица, остальные нули. Блоки , реализуют ограничения типа равенств. Тогда

.

Неравенство (52) перепишем в виде

.

Блок строится в соответствии с конструкцией , и неравенства и содержит строк. Каждая строка блока имеет M единиц, а та же строка блока имеет минус единицу. Тогда матрицу ограничений можно представить в виде

.

При слабом заполнении матрицы ограничений размерность задачи линейного программирования может быть весьма значительна. Существенное влияние на размерность оказывает количество бункеров в системе и шагов оптимизации. Несколько уменьшается размерность исключением из векторов , неразрешенных переменных и соответствующих столбцов в матрице A.