Метод оптимизации динамической управляемой структуры транспортных систем
Пусть структура транспортной системы состоит из B = {B1, B2 … BN} бункеров, которые пронумерованы индексами i,j = 1…N. Бункера соединяются каналами (i, j), исходящими из i-го бункера и входящими в j-й бункер сети. Задан период оптимизации [0, T] функционирования транспортной системы и точки , разбивающие период [0, T] на интервалы, называемые шагом дискретизации. В дальнейшем моменты времени, отождествляемые с их номерами n, будем обозначать через t. При построении динамической сети каждый бункер заменяется на множество бункеров
. Для каждого момента времени на множестве бункеров сети определена функция производства и потребления
. Индексом m = 1…M обозначается вид потока (груза), транспортируемого по сети. Если
, то бункер пунктом производства m-вида потока, а при
- его потребителем. В случае, когда
, бункер является перевалочным пунктом. Задано время
, затрачиваемое вагонами m-вида потока на проход по каналу от i-го бункера к j-му. Через
обозначим вагонопоток по каналу (i, j), выходящий из бункера Bi в бункер Bj в момент t и входящий в последний момент времени t + tij. На сети это учитывается следующим образом. Если время хода из бункера B1 в бункер B3 равно 2, то поставка, вышедшая из B1 в момент времени t = 0, поступит в бункер B3 в момент t = 2 (рис. 5). Если время прибытия поставки выходит за пределы расчетного прибытия, то есть t + tij > T, то поставка не рассматривается. Например, если T = 4, то поставка, вышедшая из B1 в B3 в момент времени t = 3, не рассматривается, поскольку t + t13 = 5. Состояние бункеров обозначается
, что означает запас (остаток) вагонов m-вида потока в бункере Bi с момента времени t –1 до момента t. Возникает петля от бункера к самому себе (рис. 4), но в другой момент времени. При размножении сети во времени петля превращается в обычную дугу (от
к
, от
к
и т.д.). Отсюда tii = 1.
Рис. 4.
Схема адаптивной структуры транспортного объекта (пространственная сеть)
Рис. 5.
Схема адаптивной структуры транспортного объекта (пространственно-временная сеть)
Для каналов определены наличные пропускные способности dii(t), зависящие от времени. При i = j величина dii(t) означает емкость бункера Bi от момента времени 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) возрастет на величину
в момент времени
. Так, если время на переброску пропускной способности из канала, соединяющего бункера B1 и B2, в канал между бункерами B1 и B3 составляет 1 такт, то на пространственно-временной сети переброска отобразится связью от дуги
к дуге
, далее от дуги
к дуге
и т.д., как показано на рис 5. Подобным образом на динамической сети вводятся связи между другими элементами структуры. Поскольку в качестве критерия о целесообразности технологического воздействия на параметры структуры используется стоимостной критерий, вводится переменная
, означающая стоимость переброски единицы пропускной способности или емкости.
В качестве нового ограничения следует принять динамику пропускной способности
.
При этом в сеть включаются только те связи адаптации, которые начинаются или заканчиваются в пределах расчетного периода
,
.
Начальное распределение пропускных способностей по каналам и емкостей по бункерам в новой постановке ставится
как задача расчета в динамике оптимальных транспортных потоков, остатков вагонов в парках и построения оптимальной динамической структуры при минимуме суммарных расходов
,
где F2 – расходы на перераспределение мощности между элементами существующей структуры за расчетный период:
,
при ограничениях.
Наличие условия не позволяет применять для решения задачи потоковые алгоритмы на графах.
При формировании критерия оптимальности принимаются во внимание только предстоящие эксплуатационные затраты. Расходы F1, связанные непосредственно с доставкой вагонов от поставщика потребителю, могут быть аппроксимированы линейной зависимостью, хотя при этом теряются некоторые факторы, нарушающие линейность. Затраты F2 на проведение мероприятий по перераспределению мощностей между транспортными устройствами, как показало изучение оптимизирующего процесса, также могут быть выражены линейной функцией переменных . Поэтому в силу линейности функционала и ограничений МОДУС является общей задачей линейного программирования с ограничениями типа равенств и неравенств.
Метод решения
Для решения задачи необходимо построить матрицу ограничений .
Вид этой матрицы удобно описать в терминах, так называемых, блочных или клеточных матриц. Рассечем с помощью горизонтальных и вертикальных линий матрицу
на прямоугольные блоки: каждый блок сам представляет собой матрицу.
Опишем подробнее структуру матрицы ограничений в аспекте оценки ее максимальной размерности.
Для построения блока образуем вектор запасов
размера
:
и вектор поставок размерности
:
Блок строится из условия
,
где
![]() |
Конструкцию блока
![Метод оптимизации динамической управляемой структуры транспортных систем Метод оптимизации динамической управляемой структуры транспортных систем - student2.ru](/images/proizvodstvo/metod-optimizacii-dinamicheskoy-upravlyaemoy-struktury-transportnykh-sistem-674351-51.gif)
Через обозначена единичная матрица
. Незаполненный блок в
соответствует вектору - столбцу поставок
. Если поставка
разрешена , т.е.
то ей в строке – уравнении
соответствует – I. В столбцах блока
могут стоять только +I, -I и 0.
Для построения блока образуем вектор
пропускных способностей размера
Вектор переменных изменения пропускных способностей размера
имеет вид
и далее для
Блок строится из условия
,
где
.
Блок имеет структуру, аналогичную блоку
. При этом используется единичная матрица
размера
. Блок, соответствующий вектору
, строится аналогично, как и блок в
, соответствующий вектору
. В столбцах блока
стоят одна единица, одна минус единица, остальные нули. Блоки
,
реализуют ограничения типа равенств. Тогда
.
Неравенство (52) перепишем в виде
.
Блок строится в соответствии с конструкцией
,
и неравенства и содержит
строк. Каждая строка блока
имеет M единиц, а та же строка блока
имеет минус единицу. Тогда матрицу ограничений можно представить в виде
.
При слабом заполнении матрицы ограничений размерность задачи линейного программирования может быть весьма значительна. Существенное влияние на размерность оказывает количество бункеров в системе и шагов оптимизации. Несколько уменьшается размерность исключением из векторов ,
неразрешенных переменных и соответствующих столбцов в матрице A.