Статическая транспортная задача

Транспортная задача является наиболее разработанным разделом линейного программирования по формальной постановке, методам решения и практическим приложениям. Классическая транспортная задача формулируется следующим образом. Имеется m пунктов производства (A_I, ..., A_m) однородного продукта или взаимозаменяемых продуктов и n пунктов потребления (B_I, ..., B_n). Заданы объемы производства a_i каждого пункта производства и размеры спроса b_jкаждого пункта потребления в одних и тех же единицах. Известны также транспортные издержки c_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j. В термин “транспортные издержки” может вкладываться различный содержательный смысл. Это может быть и стоимость, и расстояние, и время хода, и т.д. Таким образом, транспортные издержки – это некоторый условный параметр, характеризующий перевозки. Пусть x_ij – количество единиц продукта, поставленное из пункта A_i в пункт B_j. Необходимо составить наиболее экономный план перевозок, минимизирующий функцию

;

при условиях:

полного удовлетворения спроса потребителей

;

обеспечения вывоза всего производственного продукта

При этом естественно считать объемы перевозок неотрицательными числами

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

Однако использование СТЗ для оптимизации железнодорожных транспортных систем представляется малополезным из-за несоответствия исходных посылок транспортной задачи в статической постановке и динамической сущности процессов в адаптивных системах. Из-за неритмичности работы поставщиков и потребителей потоки в системе нестабильны и оптимумом объективно является некоторый динамический процесс с перестраиваемой структурой потоков. Таким образом, проблема оптимизации смещается из области поиска наилучшей статической схемы потоков в область совершенствования переходных процессов в потоковых системах. Поясним это простым примером (рис. 1 – 3). Пусть имеется три поставщика и два потребителя. Программа поставщиков не меняется и составляет 5 единиц продукта в единицу времени у поставщика A_I и по 10 единиц – у A₂ и A Программа потребителей должна измениться с исходной, когда B_I потребляет 10 и B₂ – 15 единиц продукта, на другую, когда уже B₂ потребляет 10 единиц, а B_I – 15. При этом некоторым образом меняется и стоимость перевозок.

С помощью СТЗ можно найти оптимальную структуру потоков для обоих вариантов программы (рис. 2 и 3). Однако реальный переход не может произойти мгновенно, так как существуют транспортные издержки (см. рис. 1а).

Смена структуры потоков происходит за 4 такта (см. рис. 1б), при этом время переходного процесса в обеспечении программы работы потребителей участвуют резервы. В пункте B_I потребовалось дополнительно 25 единиц продукта, а в пункте B₂ образовался избыток в 5 единиц. Разница объясняется тем, что на 20 единиц увеличилось число продукта в пути (50 и 70 соответственно).

Таким образом процесс перехода выпадает из оптимизации перевозок с помощью СТЗ. Переходные процессы занимают значительную часть времени функционирования адаптивных ПТС, поэтому СТЗ существенно не адекватен последним. Возникает проблема хранения запасов и, соответственно, учета затрат на это. В условиях неравномерности для обеспечения программ потребителей не всегда выбираются самые дешевые перевозки, так как поставки могут не успевать к нужному моменту времени. Кроме того в реальных условиях изменение режима перевозок, как правило, связано с теми или иными расходами. И нужно решать, что лучше – сменить схему потоков или обеспечить колебания программ за счет резервов при неизменной структуре перевозок.

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

Переходный процесс смены структуры потоков

Рис. 1.

Процесс смены структуры потоков

Рис. 2.

Процесс смены структуры потоков

Рис. 3.

Процесс смены структуры потоков

2.1. Введение элементов динамики в потоковые задачи

Одним из первых элемент динамики в потоковые задачи ввел американский ученый Л.Форд. При определении максимального потока на сети он предложил учитывать фактор времени, т.е. сформулировал задачу о максимальном динамическом потоке. Максимальный динамический поток – это наибольший поток, который может пропустить сеть за определенный период времени. Он не сводится к статическому, умноженному на число тактов времени, так как в начале и конце периода возникают нестационарные режимы. В начале поставки отправляются, но еще не прибывают, в конце прибывают, но уже не отправляются. Задача формулируется следующим образом. Имеется сеть с вершинами s, x, y, t, где s – исток, t – сток, x и y – промежуточные пункты. Пусть и - пропускная способность и время прохождения дуги ; они считаются целыми положительными числами. Пусть - количество потока, выходящее из x по дуге в момент и, значит, прибывающее в y в момент .

Далее, - есть количество, остающееся в x в промежуток времени от до . Если - чистый поток, выходящий из s или входящий в t за p периодов, то задачу можно сформулировать в виде линейной программы:

максимизировать при условиях

,

,

,

,

.

Здесь N – множество вершин графа, , для остатков в узле x. Переменная исключается, если или если при в данной сети нет дуги .

Был предложен и метод решения такой задачи. Статическая сеть «растягивается» (размножается) во времени таким образом, что каждому узлу соответствует узлов в новой сети (по числу тактов времени). Каждой дуге исходной сети соответствуют дуги , , т.е. связи, по которым могут идти поставки с учетом времени хода. Кроме того, добавляются дуги , , представляющие остатки в узле x. Если узлы рассматривать в качестве источников, а узлы - в качестве стоков, то условия, характеризующие p – периодный динамический поток из s в t в исходной сети, в точности совпадут с условиями, характеризующими стационарный поток из источников в стоки в полученной сети. Таким образом, задачу о динамическом потоке можно свести к задаче о статическом потоке.

Как видим, динамика в этой задаче присутствует, однако в усеченном виде. Отсутствуют поставщики и потребители с изменяемой программой, не отражается изменение стоимости перевозок во времени.

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

Ниже сформулирована динамическая транспортная задача с задержками (ДТЗЗ), в которой многообразная динамика отображается наиболее полно.